基于中心性度量的改进自适应图匹配方法

doi:10.7523/j.ucas.2025.009

摘要/Abstract

摘要： 图匹配（Graph matching）是指在两个图之间寻找最优节点对应关系的组合优化问题,广泛应用于计算机视觉和模式识别等领域。该问题是NP难题,许多算法已经被提出以近似求解。在实际应用中,由于噪声或缺失数据,大多数匹配任务会遇到包含异常点的节点集合,这对现有的图匹配方法构成挑战。在此前的工作中,自适应图匹配方法通过修改图匹配优化问题的目标函数和约束条件,提供了一种有效的解决方案,能够实现非离群点之间的匹配。节点中心性是网络科学中的一个概念,通过不同的度量标准对节点的重要性进行排名,也可以用来区分图中的异常点。在本文中,我们将节点中心性度量作为一种筛选离群点的标准,引入到自适应图匹配的正则化项中,旨在提升匹配的准确率和召回率。我们的工作还为研究节点中心性在不同图之间提取信息提供了新的视角。通过对合成数据和实际图像的实验,验证了引入节点中心性后图匹配性能的提升。

关键词: 图匹配, 节点中心性, 离群点, PATH方法

Abstract: 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.

Key words: Graph matching, node centrality, outliers, PATH method

中图分类号:

O224

石祥盛, 姜志鹏. 基于中心性度量的改进自适应图匹配方法[J]. 中国科学院大学学报, DOI: 10.7523/j.ucas.2025.009.

SHI Xiangsheng, JIANG Zhipeng. A modified adaptive graph matching method based on centrality measures^*[J]. Journal of University of Chinese Academy of Sciences, 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.