A Novel Method for Graph Matching
Pages 177 - 181
Abstract
Graph matching is a fundamental NP-hard problem in computer science. We propose an approximate graph matching method. To match the nodes of two graphs, our method first constructs an association graph. For each pair of nodes within the association graph, our method computes their mutual consistency on the basis of the distance information and angle information of the original graphs' nodes. The consistencies of all pairs of nodes form an affinity matrix. With the affinity matrix, our method then performs random walks on the association graph to achieve a stable quasi-stationary distribution. Discretizing the distribution on the basis of the Hungarian algorithm, our method finally obtains the matching between the nodes of the two original graphs. The experimental results demonstrate the effectiveness of our method on graph matching.
References
[1]
Riesen, K., Jiang, X., and Bunke, H. 2010. Exact and inexact graph matching: methodology and applications, 217--247. DOI= https://link.springer.com/chapter/10.1007%2F978-1-4419-6045-0_7.
[2]
Gold, S., Rangarajan, A. 1996. A graduated assignment algorithm for graph matching, 377--388. DOI= https://ieeexplore.ieee.org/document/491619.
[3]
Cho, M., Lee, J., and Lee, K. M. 2010. Reweighted random walks for graph matching, 492--505. DOI= https://link.springer.com/chapter/10.1007%2F978-3-642-15555-0_36.
[4]
Mills-Tettey, G. A., Stentz, A., Dias, M. B. 2007. The dynamic Hungarian algorithm for the assignment problem with changing costs. Carnegie Mellon University. DOI= http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.8170.
[5]
Leordeanu, M., Hebert, M. 2005. A spectral technique for correspondence problems using pair wise constraints, 14821489. DOI= https://ieeexplore.ieee.org/document/1544893?arnumber=1544893.
[6]
Timothée Cour, Srinivasan, P., Shi, J. 2006. Balanced Graph Matching. Conference on Advances in Neural Information Processing Systems, 313--320. DOI= https://ieeexplore.ieee.org/document/6287355/.
[7]
Jiang, B., Zhao, H., Tang, J., and Luo, B. 2014. A sparse nonnegative matrix factorization technique for graph matching problems. Pattern Recognition.47(2), 736--747. DOI=https://www.sciencedirect.com/science/article/abs/pii/S0031320313003476.
[8]
Jiang B, Tang J, Ding CH, Luo B. 2017. Nonnegative orthogonal graph matching. In: Association for the advance of artificial intelligence, 4089--4095. DOI= https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14405.
[9]
Cour T, Shi J. 2007. Solving Markov random fields with spectral relaxation. In: Artificial intelligence and statistics, 75--82. DOI= https://www.researchgate.net/publication/220319870_Solving_Markov_Random_Fields_with_Spectral_Relaxation.
[10]
Nie W, Ding H, Liu A, Deng Z, Su Y. 2018. Subgraph learning for graph matching. Pattern Recognition Letters. DOI=https://www.sciencedirect.com/science/article/abs/pii/S0167865518302897.
[11]
Wang T, Ling H, Lang C, Feng S. 2017. Graph Matching with Adaptive and Branching Path Following. In: IEEE transactions on pattern analysis and machine intelligence, 2853--2867. DOI= https://ieeexplore.ieee.org/document/8089364.
[12]
D. Khue Le-Huu, Paragios, N. 2017. Alternating Direction Graph Matching. In: IEEE Conference on computer vision and pattern recognition, 6253--6261. DOI= https://ieeexplore.ieee.org/document/8100005.
[13]
Leordeanu, M., Hebert, M., and Sukthankar, R. 2009. An Integer Projected Fixed Point Method for Graph Matching and MAP Inference. In: Conference on Neural Information Processing Systems, 1114--1122. DOI= https://www.researchgate.net/publication/221619668_An_Int eger_Projected_Fixed_Point_Method_for_Graph_Matching_and_MAP_Inferencehttps://www.researchgate.net/publication/221619668_An_Integer_Projected_Fixed_Point_Method_for_Graph_Matching_and_MAP_Inference.
[14]
D. Khuê Lê-Huu, Paragios, N. 2017. Alternating direction graph matching. In: IEEE Conference on computer vision and pattern recognition, 6253--6261. DOI= https://ieeexplore.ieee.org/document/8100005.
[15]
Cho, M., Sun, J., Duchenne, O., Ponce, J. 2014. Finding matches in a haystack: a max-pooling strategy for graph matching in the presence of outliers. In: IEEE Conference on computer vision and pattern recognition, 2083--2090. DOI= https://ieeexplore.ieee.org/document/8089364.
[16]
Jiang, B., Tang, J., Luo, B. 2019. Efficient Feature Matching via Nonnegative Orthogonal Relaxation. International Journal of Computer Vision, 127(9), 1345--1360. DOI= https://link.springer.com/article/10.1007/s11263-019-01185-1.
Index Terms
- A Novel Method for Graph Matching
Recommendations
Graph matching based on local and global information of the graph nodes
AbstractGraph matching is an essential NP-problem in computer vision and pattern recognition. In this paper, we propose an approximate graph matching method. This method formulates the problem of computing the correspondences between two graphs as a ...
A novel graph matching method based on multiple information of the graph nodes
AbstractGraph matching is a fundamental NP-problem in computer graphics and computer vision. In this work, we present an approximate graph matching method. Given two graphs to be matched, the proposed method first constructs an association graph to ...
A graph matching method and a graph matching distance based on subgraph assignments
During the last decade, the use of graph-based object representation has drastically increased. As a matter of fact, object representation by means of graphs has a number of advantages over feature vectors. As a consequence, methods to compare graphs ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2020
250 pages
ISBN:9781450387859
DOI:10.1145/3422713
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 October 2020
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- Project of Jinan Scientific Research Leaders Laboratory
- Natural Science Foundation of Shandong Province
Conference
ICBDT 2020
ICBDT 2020: 2020 3rd International Conference on Big Data Technologies
September 18 - 20, 2020
Qingdao, China
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 55Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in