Graph matching(GM), referred to find the optimal correspondence of nodes between two graphs, is a combinatorial optimization problem applied in various fields of computer vision and pattern recognition. This problem is NP-hard and many algorithms have been proposed to solve it approximately. In real world, a majority of matching tasks encounter the vertex sets with outliers due to the noise or missing data which is challenging for recent GM methods. A previous work, adaptive graph matching, provided an effective approach to realize inliers matching by modifying both the objective function and constraints of GM optimization problem. Node centrality, a concept in networks sciences ranking the importance of nodes based on different measures, can also be employed to distinguish outliers in graph. In this paper, we introduce the centrality measures into adaptive graph matching as an additional regularization term aiming to accomplish improved performance. Our works also derive an insight to study the information extracted by node centrality between graphs. Experiments on synthetic data and real world images illustrate the advantage of incorperating node centrality.
SHI Xiangsheng
,
JIANG Zhipeng
. A modified adaptive graph matching method based on centrality measures*[J]. Journal of University of Chinese Academy of Sciences, 0
: 250411
.
DOI: 10.7523/j.ucas.2025.009
[1] Livi L, Rizzi A.The graph matching problem[J]. Pattern Analysis and Applications, 2013, 16(3): 253-283. DOI: 10.1007/s10044-012-0284-8.
[2] Yan J C, Yin X C, Lin W Y, et al.A short survey of recent advances in graph matching[C]//Proceedings of the 2016 ACM on International Conference on Multimedia Retrieval. June 6 - 9, 2016, New York, New York, USA. ACM, 2016: 167-174. DOI: 10.1145/2911996.2912035.
[3] Loiola E M, de Abreu N M M, Boaventura-Netto P O, et al. A survey for the quadratic assignment problem[J]. European Journal of Operational Research, 2007, 176(2): 657-690. DOI: 10.1016/j.ejor.2005.09.032.
[4] Gold S, Rangarajan A.A graduated assignment algorithm for graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(4): 377-388. DOI: 10.1109/34.491619.
[5] Leordeanu M, Hebert M.A spectral technique for correspondence problems using pairwise constraints[C]//Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1. October 17-21, 2005, Beijing, China. IEEE, 2005: 1482-1489. DOI: 10.1109/ICCV.2005.20.
[6] Cour T, Srinivasan P, Shi J. Balanced Graph Matching[EB/OL]. (2006)[2025-02-26].https://proceedings.neurips.cc/paper_files/paper/2006/file/d1c373ab1570cfb9a7dbb53c186b37a2-Paper.pdf.
[7] Zass R, Shashua A.Probabilistic graph and hypergraph matching[C]//2008 IEEE Conference on Computer Vision and Pattern Recognition. June 23-28, 2008, Anchorage, AK, USA. IEEE, 2008: 1-8. DOI: 10.1109/CVPR.2008.4587500.
[8] Zaslavskiy M, Bach F, Vert J P.A path following algorithm for the graph matching problem[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(12): 2227-2242. DOI: 10.1109/TPAMI.2008.245.
[9] Leordeanu M, Hebert M, Sukthankar R.An integer projected fixed point method for graph matching and MAP inference[C]//Neural Information Processing Systems, 2020.
[10] Cho M, Lee J, Lee K M.Reweighted random walks for graph matching[C]// Computer Vision - ECCV 2010. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010: 492-505. DOI: 10.1007/978-3-642-15555-0_36.
[11] Cho M, Sun J, Duchenne O, et al.Finding matches in a haystack: A max-pooling strategy for graph matching in the presence of outliers[C]//2014 IEEE Conference on Computer Vision and Pattern Recognition. June 23-28, 2014, Columbus, OH, USA. IEEE, 2014: 2091-2098. DOI: 10.1109/CVPR.2014.268.
[12] Yang X, Qiao H, Liu Z Y.Outlier robust point correspondence based on GNCCP[J]. Pattern Recognition Letters, 2015, 55: 8-14. DOI: 10.1016/j.patrec.2014.12.011.
[13] Yang X, Liu Z Y.Adaptive graph matching[J]. IEEE Transactions on Cybernetics, 2018, 48(5): 1432-1445. DOI: 10.1109/TCYB.2017.2697968.
[14] Yang X, Liu Z Y, Qiao H.A continuation method for graph matching based feature correspondence[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 42(8): 1809-1822. DOI: 10.1109/TPAMI.2019.2903483.
[15] Wang F D, Xue N, Yu J G, et al. Zero-assignment constraint for graph matching with outliers[EB/OL].2020. 2003.11928.(2020-03-26)[2025-02-27] https://arxiv.org/abs/2003.11928v1.
[16] Newman M.Networks: An Introduction[M]. Oxford: Oxford University Press, 2010. DOI: 10.1093/acprof:oso/9780199206650.001.0001.
[17] Costantini L, Sciarra C, Ridolfi L, et al. Measuring node centrality when local and global measures overlap[J]. Physical Review. E, 2022, 105(): 044317. DOI: 10.1103/PhysRevE.105.044317.
[18] Dwivedi S P. Inexact graph matching using centrality measures[EB/OL].2021. 2201.04563.(2021-12-31)[2025-02-27] https://arxiv.org/abs/2201.04563v1.
[19] Zhou F, De la Torre F. Factorized graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(9): 1774-1789. DOI: 10.1109/TPAMI.2015.2501802.
[20] Bloch F, Jackson M O, Tebaldi P.Centrality measures in networks[J]. Social Choice and Welfare, 2023, 61: 413-453. DOI: 10.1007/s00355-023-01456-4.
[21] Liu Z Y, Qiao H.GNCCP-graduated NonConvexityand concavity procedure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(6): 1258-1267. DOI: 10.1109/TPAMI.2013.223.
[22] Frank M, Wolfe P.An algorithm for quadratic programming[J]. Naval Research Logistics Quarterly, 1956, 3(1/2): 95-110. DOI: 10.1002/nav.3800030109.
[23] Kuhn H W.The Hungarian method for the assignment problem[J]. Naval Research Logistics Quarterly, 1955, 2(1/2): 83-97. DOI: 10.1002/nav.3800020109.
[24] Vogelstein J T, Conroy J M, Lyzinski V, et al. Fast approximate quadratic programming for large (brain) graph matching[EB/OL].2011. 1112.5507.(2011-12-23)[2025-02-27] https://arxiv.org/abs/1112.5507v5.
