A fast projected fixed-point algorithm for large graph matching. (December 2016)

• Record Type: Journal Article
• Authors: Lu, Yao; Huang, Kaizhu; Liu, Cheng-Lin
• Is Part Of: Pattern recognition. Volume 60(2016:Dec.)
• Page Start: 971
• Page End: 982
• Publication Date: 2016-12
• Subjects: Graph matching -- Projected fixed-point -- Large graph algorithm -- Feature correspondence -- Point matching; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2016.07.015
• Languages: English
• ISSNs: 0031-3203

Abstract

Abstract: We propose a fast algorithm for approximate matching of large graphs. Previous graph matching algorithms suffer from high computational complexity and therefore do not have good scalability. By using a new doubly stochastic projection, for matching two weighted graphs of n nodes, our algorithm has time complexity only O ( n 3 ) per iteration and space complexity O ( n 2 ) . We proved that our algorithm converges at a super-logarithmic rate. Experiments on large synthetic and real graphs (over 1000 nodes) were conducted to evaluate the performance of various algorithms. Results show that due to its fast convergence, our algorithm is more than an order of magnitude faster than the previous state-of-the-art algorithms, while maintaining comparable accuracy in large graph matching. Abstract : Highlights: Low time complexity O ( n 3 )/iteration for two graphs of n nodes. Super-logarithm convergence guarantee. Large graph matching experiments.