基于边对注意力的跨图嵌入深度图匹配

Cross-Graph Embedding with Edge-Wise Attention for Deep Graph Matching

摘要: 图匹配问题(GM)旨在建立两个图的点集之间的一致性，同时保持它们的边集之间的一致性，在数学上可以被刻画为二次组合优化问题。随着图神经网络的兴起和发展，基于深度学习的图匹配方法应用图神经网络技术将每个图的几何结构信息嵌入到结点特征，从而将二阶组合优化的图匹配问题松弛为线性分配问题。然而，这样的图匹配模型在本质上忽略了二阶的边对相似度信息，即没有考虑边集之间的一致性，从而导致这类模型在精度上有所损失。针对上述问题，本文提出了一种新型基于嵌入技术的深度图匹配网络，该网络充分考虑了边对相似性信息：基于二图匹配生成的关联图，将边对相似性信息(等价于关联图上的边)作为跨图嵌入的注意力信息，构造一个跨图注意力模块。本文基于公开数据集进行评估实验，结论表明本文的方法在精度上超越了已有的模型。除此之外，本文的方法相比于目前精度最高的模型，在内存消耗上具有优势，体现了该模型具有处理大规模图匹配任务的潜力。

Abstract: Graph matching problem (GM) refers to establishing correspondences between two set of points while keeping the consistency between their edge sets and can be mathematically formulated as a quadratic combinatorial optimization problem. With the success of graph neural network (GNN), recent learning-based graph matching research attempts to solve the problem by way of linear assignment via transferring local structure information into node embedding at each graph. However, such a technique omits second-order pairwise edge similarity in essence causing the decrease of accuracy. Based on this issue, this paper proposes a novel embedding-based graph matching network fully considering the pairwise edge similarity. Edge-to-edge similarity, equivalent to associated edges, is aggregated into nodes in the association graph derived from two matching graphs, to amplify the discriminativeness of crossgraph node embedding. Experimental evaluations are conducted on public datasets, and results show that our method outperforms the state-of-the-art in accuracy. In addition, compared with the state-of-the-art, the proposed method has superiority in space consumption, indicating the potential to solve large-scale graph matching problems.