Graph matching refers to finding node correspondence between graphs, such that the corresponding node and edge's affinity can be maximized. In addition with its NP-completeness nature, another important challenge is effective modeling of the node-wise and structure-wise affinity across graphs and the resulting objective, to guide the matching procedure effectively finding the true matching against noises. To this end, this paper devises an end-to-end differentiable deep network pipeline to learn the affinity for graph matching. It involves a supervised permutation loss regarding with node correspondence to capture the combinatorial nature for graph matching. Meanwhile deep graph embedding models are adopted to parameterize both intra-graph and cross-graph affinity functions, instead of the traditional shallow and simple parametric forms e.g. a Gaussian kernel. The embedding can also effectively capture the higher-order structure beyond second-order edges. The permutation loss model is agnostic to the number of nodes, and the embedding model is shared among nodes such that the network allows for varying numbers of nodes in graphs for training and inference. Moreover, our network is class-agnostic with some generalization capability across different categories. All these features are welcomed for real-world applications. Experiments show its superiority against state-of-the-art graph matching learning methods.
翻译:图表匹配指在图形之间找到节点对应, 这样对应的节点和边缘的亲近性可以最大化。 除了其 NP 完整性性质外, 另一个重要挑战就是在图形之间对节点和结构亲近性进行有效建模, 从而指导匹配程序, 从而有效地找到与噪音之间的真正匹配。 为此, 本文设计了一个端到端的深端网络管道, 以学习图形匹配的亲近性 。 它涉及到与节点对应以捕捉图形匹配的组合性对应性质的节点对齐性有关的监管变异性损失。 同时, 深度的图形嵌入模型被采用, 将内部和跨面的亲近性功能, 而不是传统的浅度和简单的准度形式( 如: 高调内心) 进行比较, 以指导匹配程序有效地找到二阶边缘以外的更高阶结构 。 调损失模型对于节点的数量是不可知的, 嵌入模型在节点中被共享, 网络允许对不同数字的无线嵌入模型进行参数的参数, 将显示整个类图中的所有实验性网络的优度 。 将显示系统 。 这些直观的路径 将显示为不同路径 。