A fast projected fixed-point algorithm for large graph matching
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(n3) per iteration and space complexity O(n2). 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.
Duke Scholars
Published In
DOI
ISSN
Publication Date
Volume
Start / End Page
Related Subject Headings
- Artificial Intelligence & Image Processing
- 4611 Machine learning
- 4605 Data management and data science
- 4603 Computer vision and multimedia computation
- 0906 Electrical and Electronic Engineering
- 0806 Information Systems
- 0801 Artificial Intelligence and Image Processing
Citation
Published In
DOI
ISSN
Publication Date
Volume
Start / End Page
Related Subject Headings
- Artificial Intelligence & Image Processing
- 4611 Machine learning
- 4605 Data management and data science
- 4603 Computer vision and multimedia computation
- 0906 Electrical and Electronic Engineering
- 0806 Information Systems
- 0801 Artificial Intelligence and Image Processing