基于熵驱动双随机矩阵的图匹配神经网络

doi:10.16451/j.cnki.issn1003-6059.202506004

Abstract
Figure/Table
References
Related Citation (15)

Download: PDF (7275 KB) HTML (1 KB)
Export: BibTeX | EndNote (RIS)

Abstract Graph matching is intended to establish node correspondence between two graph structures. Existing methods generally neglect the critical role of node matching confidence in graph matching tasks. To fully utilize the matching confidence between nodes to control the propagation of node feature information, an entropy-driven doubly stochastic matrix based graph matching neural network(EDSGM) is proposed. Node features, edge features and the similarity functions for graph matching tasks are jointly learned by deep neural networks, and the graph matching problem is simplified using graph embedding methods. The matching entropy is constructed using the doubly stochastic matrix representing the graph matching results, and the intra-graph node embedding layer and cross-graph information embedding layer are built to form an adaptive graph embedding module based on the matching entropy. This design not only achieves dimensionality reduction and problem simplification in the feature space, but also makes the propagation of node information more efficient, thereby improving matching accuracy. Furthermore, all neural network modules in EDSGM can be trained end-to-end in a supervised manner, and the same neural network can effectively handle multiple categories of graph matching tasks. Experiments demonstrate that EDSGM achieves state-of-the-art graph matching accuracy across multiple categories on Pascal VOC, SPair-71k, and Willow ObjectClass graph datasets. The results validate that matching entropy enhances the efficiency of node feature propagation and improves graph matching accuracy.

Key words： Graph Matching Deep Learning Graph Embedding Matching Entropy

Received: 16 April 2025

ZTFLH:

TP391

Fund:Supported by National Natural Science Foundation of China(No.12271235), Natural Science Foundation of Fujian Province(No.2021J06029,2024J08070), Science and Technology Project of Minnan Normal University(No.KJ2021020), High-Level Cultivation Project of Minnan Normal University(No.MSGJB2022010)

Corresponding Authors: HUANG Meixiang, Ph.D., lecturer. Her research inte-rests include image processing and machine learning.

About author:: CAO Shuyuan, Master student. Her research interests include machine learning and graph neural network.
LU Fuliang, Ph.D., professor. His research interests include graph theory and its applications.
TU Liangping, Ph.D., professor. His research interests include machine learning and artificial intelligence.

	Service

	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	CAO Shuyuan
	HUANG Meixiang
	LU Fuliang
	TU Liangping

Cite this article:

CAO Shuyuan,HUANG Meixiang,LU Fuliang等. Entropy-Driven Doubly Stochastic Matrix Based Graph Matching Neural Network[J]. Pattern Recognition and Artificial Intelligence, 2025, 38(6): 538-551.

URL:

http://manu46.magtech.com.cn/Jweb_prai/EN/10.16451/j.cnki.issn1003-6059.202506004 OR http://manu46.magtech.com.cn/Jweb_prai/EN/Y2025/V38/I6/538

[1] HALLER S, FEINEIS L, HUTSCHENREITER L, et al. A Compa-rative Study of Graph Matching Algorithms in Computer Vision // Proc of the 17th European Conference on Computer Vision. Berlin, Germany: Springer, 2022: 636-653.
[2] WANG R Z, WANG R X, MANJREKAR M, et al. Neural Graph Matching Improves Retrieval Augmented Generation in Molecular Machine Learning[C/OL].[2025-03-17]. https://arxiv.org/abs/2502.17874.
[3] PHAM K, HUYNH C, LIM S N, et al. Composing Object Relations and Attributes for Image-Text Matching // Proc of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2024: 14354-14363.
[4] MARTÍNEZ-OTZETA J M, RODRÍGUEZ-MORENO I, MENDIALD-UA I, et al. RANSAC for Robotic Applications: A Survey. Sensors, 2022, 23(1). DOI: 10.3390/s23010327.
[5] ZHANG Z Y.Iterative Point Matching for Registration of Free-Form Curves and Surfaces. International Journal of Computer Vision, 1994, 13(2): 119-152.
[6] CHO M, LEE J, LEE K M.Reweighted Random Walks for Graph Matching // Proc of the 11th European Conference on Computer Vision. Berlin, Germany: Springer, 2010: 492-505.
[7] YAN J C, YIN X C, LIN W Y, et al. A Short Survey of Recent Advances in Graph Matching // Proc of the ACM International Confe-rence on Multimedia Retrieval. New York, USA: ACM, 2016: 167-174.
[8] LIAO X W, XU Y, LING H B.Hypergraph Neural Networks for Hypergraph Matching // Proc of the IEEE/CVF International Conference on Computer Vision. Washington, USA: IEEE, 2021: 1246-1255.
[9] ZHU H, WANG X Q, XU G X, et al. A Self-Paced Learning Based Transfer Model for Hypergraph Matching. Information Sciences, 2022, 590: 253-266.
[10] YAN J C, LI C S, LI Y, et al. Adaptive Discrete Hypergraph Matching. IEEE Transactions on Cybernetics, 2018, 48(2): 765-779.
[11] TAN H R, WANG C, WU S T, et al. Ensemble Quadratic Assignment Network for Graph Matching. International Journal of Computer Vision, 2024, 132(9): 3633-3655.
[12] LEORDEANU M, HEBERT M. A Spectral Technique for Corres- pondence Problems Using Pairwise Constraints // Proc of the 10th IEEE International Conference on Computer Vision. Washington, USA: IEEE, 2005, I: 1-8.
[13] COUR T, SRINIVASAN P, SHI J B. Balanced Graph Matching // Proc of the 20th International Conference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 2006: 313-320.
[14] GOLD S, RANGARAJAN A.A Graduated Assignment Algorithm for Graph Matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(4): 377-388.
[15] CHO M, ALAHARI K, PONCE J.Learning Graphs to Match // Proc of the IEEE International Conference on Computer Vision. Washington, USA: IEEE, 2013: 25-32.
[16] ZANFIR A, SMINCHISESCU C.Deep Learning of Graph Ma-tching // Proc of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2018: 2684-2693.
[17] WANG R Z, YAN J C, YANG X K.Combinatorial Learning of Robust Deep Graph Matching: An Embedding Based Approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45(6): 6984-7000.
[18] GAO Q K, WANG F D, XUE N, et al. Deep Graph Matching under Quadratic Constraint // Proc of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2021: 5069-5078.
[19] LIU L F, HUGHES M C, HASSOUN S, et al. Stochastic Iterative Graph Matching. Proceedings of Machine Learning Research, 2021, 139: 6815-6825.
[20] ROLÍNEK M, SWOBODA P, ZIETLOW D, et al. Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers // Proc of the 16th European Conference on Computer Vision. Berlin, Germany: Springer, 2020: 407-424.
[21] LIN Y J, YANG M X, YU J, et al. Graph Matching with Bi-level Noisy Correspondence // Proc of the IEEE/CVF International Conference on Computer Vision. Washington, USA: IEEE, 2023: 23305-23314.
[22] LIU H, SCAGLIONE A, WAI H T.Blind Graph Matching Using Graph Signals. IEEE Transactions on Signal Processing, 2024, 72: 1766-1781.
[23] YU T S, WANG R Z, YAN J C, et al. Learning Deep Graph Matching with Channel-Independent Embedding and Hungarian Attention[C/OL].[2025-03-17]. https://openreview.net/pdf?id=rJgBd2NYPH.
[24] FEY M, LENSSEN J E, MORRIS C, et al. Deep Graph Matching Consensus[C/OL].[2025-03-17]. https://arxiv.org/pdf/2001.09621.
[25] FEY M, LENSSEN J E, WEICHERT F, et al. SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels // Proc of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2018: 869-877.
[26] JIANG B, SUN P F, LUO B.GLMNet: Graph Learning-Matching Convolutional Networks for Feature Matching. Pattern Recognition, 2022, 121. DOI: 10.1016/j.patcog.2021.108167.
[27] LOIOLA E M, DE ABREU N M M, BOAVENTURA-NETTO P O, et al. A Survey for the Quadratic Assignment Problem. European Journal of Operational Research, 2007, 176(2): 657-690.
[28] WANG R Z, YAN J C, YANG X K.Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-Graph Matching. IEEE Transa-ctions on Pattern Analysis and Machine Intelligence, 2022, 44(9): 5261-5279.
[29] BURKARD R E, ÇELA E.The Quadratic Assignment Problem // DU D Z, PARDALOS P M, eds. Handbook of Combinatorial Optimization. Berlin, Germany: Springer, 1998: 1713-1809.
[30] ZHOU F, DE LA TORRE F. Factorized Graph Matching // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2012: 127-134.
[31] BROMILEY P A, THACKER N A, BOUHOVA-THACKER E. Sha-nnon Entropy, Renyi Entropy, and Information[C/OL]. [2025-03-17].https://www.researchgate.net/publication/253537416.
[32] YU J C, XU T Y, RONG Y, et al. Graph Information Bottleneck for Subgraph Recognition[C/OL].[2025-03-17]. https://arxiv.org/pdf/2010.05563.
[33] ARGHAL R, LEI E, BIDOKHTI S S.Robust Graph Neural Networks via Probabilistic Lipschitz Constraints. Proceedings of Machine Learning Research, 2022, 168: 1073-1085.
[34] ZHAO G P, WANG T, LI Y D, et al. Entropy-Aware Self-Trai-ning for Graph Convolutional Networks. Neurocomputing, 2021, 464: 394-407.
[35] BROMLEY J, GUYON I, LECUN Y, et al. Signature Verification Using a "Siamese" Time Delay Neural Network // Proc of the 7th International Conference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 1993: 737-744.
[36] KIPF T N, WELLING M. Semi-supervised Classification with Gra-ph Convolutional Networks[C/OL]. [2025-03-17].https://arxiv.org/pdf/1609.02907.
[37] SINKHORN R.A Relationship between Arbitrary Positive Matrices and Doubly Stochastic Matrices. The Annals of Mathematical Statistics, 1964, 35(2): 876-879.
[38] CUTURI M. Sinkhorn Distances: Lightspeed Computation of Optimal Transport // Proc of the 27th International Conference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 2013, II: 2292-2300.
[39] KUHN H W.The Hungarian Method for the Assignment // JÜN-GER P M, ed. 50 Years of Integer Programming. Berlin, Germany: Springer, 2019: 27-47.
[40] SERRATOSA F, SOLÉ-RIBALTA A,CORTÉ X. Automatic Lear-ning of Edit Costs Based on Interactive and Adaptive Graph Recognition // Proc of the 8th International Conference on Graph-Based Representations in Pattern Recognition. Berlin, Germany: Sprin-ger, 2011: 152-163.
[41] EVERINGHAM M, VAN GOOL L, WILLIAMS C K I, et al. The Pascal Visual Object Classes(VOC) Challenge. International Journal of Computer Vision, 2010, 88(2): 303-338.
[42] MIN J H, LEE J, PONCE J, et al. SPair-71k: A Large-Scale Ben-chmark for Semantic Correspondence[C/OL].[2025-03-17]. https://arxiv.org/abs/1908.10543.
[43] DENG J, DONG W, SOCHER R, et al. ImageNet: A Large-Scale Hierarchical Image Database // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2009: 248-255.
[44] SIMONYAN K, ZISSERMAN A.Very Deep Convolutional Networks for Large-Scale Image Recognition[C/OL]. [2025-03-17].https://arxiv.org/pdf/1409.1556.