A fast projected fixed-point algorithm for large graph matching

DOI10.1016/J.PATCOG.2016.07.015MaRDI QIDQ2417841zbMATHOpenAlexFDO

Authors Yao Lu, Kaizhu Huang, Cheng-Lin Liu

Publication date 29 May 2019

Published in Pattern Recognition (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.1114

zbMATH Keywords

graph matchingpoint matchingfeature correspondencelarge graph algorithmprojected fixed-point

Mathematics Subject Classification ID

Applications of graph theory (05C90) Pattern recognition, speech recognition (68T10) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Abstract: We propose a fast approximate algorithm for large graph matching. A new projected fixed-point method is defined and a new doubly stochastic projection is adopted to derive the algorithm. Previous graph matching algorithms suffer from high computational complexity and therefore do not have good scalability with respect to graph size. 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)$. In addition to its scalability, our algorithm is easy to implement, robust, and able to match undirected weighted attributed graphs of different sizes. While the convergence rate of previous iterative graph matching algorithms is unknown, our algorithm is theoretically guaranteed to converge at a linear rate. Extensive experiments on large synthetic and real graphs (more than 1,000 nodes) were conducted to evaluate the performance of various algorithms. Results show that in most cases our proposed algorithm achieves better performance than previous state-of-the-art algorithms in terms of both speed and accuracy in large graph matching. In particular, with high accuracy, our algorithm takes only a few seconds (in a PC) to match two graphs of 1,000 nodes.

Recommendations

• Graph matching based on dot product representation of graphs
• A sparse nonnegative matrix factorization technique for graph matching problems
• scientific article; zbMATH DE number 2090223
• Algorithms for approximate graph matching
• Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis

Cites work

• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• An Algorithm for Subgraph Isomorphism
• An eigendecomposition approach to weighted graph matching problems
• Concerning nonnegative matrices and doubly stochastic matrices
• Error-Correcting Isomorphisms of Attributed Relational Graphs for Pattern Analysis
• Functional Operators (AM-22), Volume 2
• On complexity of matrix scaling
• On the complexity of nonnegative-matrix scaling
• Protein classification by matching and clustering surface graphs
• Scene Labeling by Relaxation Operations
• The approximation of fixed points of compositions of nonexpansive mappings in Hilbert space
• The quadratic assignment problem
• Video indexing and similarity retrieval by largest common subgraph detection using decision trees

Cited in

(8)

• Graph matching based on dot product representation of graphs
• Node matching computation between two large graphs in linear computational cost
• Landmark-based \(k\)-factorization multi-view subspace clustering
• CDPA: common and distinctive pattern analysis between high-dimensional datasets
• scientific article; zbMATH DE number 2090220 (Why is no real title available?)
• A sparse nonnegative matrix factorization technique for graph matching problems
• Near-rings on digital Hopf groups
• Lightning graph matching

Describes a project that uses

Uses Software

• SIFT

This page was built for publication: A fast projected fixed-point algorithm for large graph matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2417841)