Fast matching via ergodic markov chain for super-large graphs. (October 2020)

• Record Type: Journal Article
• Authors: Zheng, Yali; Pan, Lili; Qian, Jiye; Guo, Hongliang
• Is Part Of: Pattern recognition. Volume 106(2020:Oct.)
• Publication Date: 2020-10
• Subjects: Spectral matching -- Graph matching -- Ergodic markov chain -- Space complexity; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2020.107418
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: the graph matching problem is formulated as an Ergodic Markov chain, and the process of matching is addressed to reach the steady-state of the Markov chain. our algorithm solves the matching problem in O ( n 2 ) space complexity by taking the decomposition of probability transition matrix, and the property leads the algorithm to the matching of super-large graphs (for example, graphs with the number of points over 1000) in limited computing resource and RAM. our algorithm is evaluated on both the synthetic and the real datasets, and demonstrate that the proposed approach and algorithm is significantly faster and smaller memory than SM, RRWM and FaSM with no loss of accuracy. Abstract: In theory, graph matching is a combinatorial problem. One state-of-the-art technique in graph matching, called spectral matching, relaxes the matching problem for consistent correspondence into spectral decomposition of the affinity matrix of graphs, but the most variations of spectral based algorithms suffer from their O ( n 4 ) memory requirement. In this paper we propose a probabilistic spectral matching approach, in which the graph matching problem is formulated as an ergodic Markov chain, and the process of matching is addressed to reach the steady-state of the Markov chain. The approach decomposes the probability transition matrix, and solves the matching problem in O ( n 2 ) space complexity using limited computing resource and RAM. This property makes the approach suitable for super-large graphs matching (for example, graphs with the number of points over 1000). We evaluate our algorithm on both the synthetic and the real datasets, and demonstrate that the proposed approach is significantly faster, and consumes smaller memory than SM, RRWM and FaSM with no loss of accuracy.