Fast matching via ergodic markov chain for super-large graphs

作者：

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(n2) 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.

摘要

•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(n2) 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.

论文关键词：Spectral matching,Graph matching,Ergodic markov chain,Space complexity

论文评审过程：Received 24 October 2018, Revised 25 September 2019, Accepted 3 May 2020, Available online 5 May 2020, Version of Record 28 May 2020.

论文官网地址：https://doi.org/10.1016/j.patcog.2020.107418