Position-aware and structure embedding networks for deep graph matching

• Published in: Pattern recognition 2023-04, Vol.136, p.109242, Article 109242
• Main Authors: Chen, Dongdong, Dai, Yuxing, Zhang, Lichi, Zhang, Zhihong, Hancock, Edwin R.
• Format: Article
• Language: English
• Subjects: Deep Neural Network; Graph Embedding; Graph Matching
• ISSN: 0031-3203; 1873-5142
• DOI: 10.1016/j.patcog.2022.109242

•This paper introduces the relative position information related to the matching of key points by constructing an anchor set for small graphs extracted from images, which is shown to be effective in graph matching experiments.•This paper introduces subgraph arrangement structure information into the graph matching task and implements a hierarchical and comprehensive extraction of image features.•The proposed position-aware node embedding module and subgraph-based structural embedding module can be added to existing deep learning graph matching methods, further boosting the graph matching performance. Graph matching refers to the process of establishing node correspondences based on edge-to-edge constraints between graph nodes. This can be formulated as a combinatorial optimization problem under node permutation and pairwise consistency constraints. The main challenge of graph matching is to effectively find the correct match while reducing the ambiguities produced by similar nodes and edges. In this paper, we present a novel end-to-end neural framework that converts graph matching to a linear assignment problem in a high-dimensional space. This is combined with relative position information at the node level, and high-order structural arrangement information at the subgraph level. By capturing the relative position attributes of nodes between different graphs and the subgraph structural arrangement attributes, we can improve the performance of graph matching tasks, and establish reliable node-to-node correspondences. Our method can be generalized to any graph embedding setting, which can be used as components to deal with various graph matching problems answered with deep learning methods. We validate our method on several real-world tasks, by providing ablation studies to evaluate the generalization capability across different categories. We also compare state-of-the-art alternatives to demonstrate performance.