Lightning graph matching.

The spectral matching algorithm is a classic method for finding correspondences between two graphs, a fundamental task in pattern recognition. It has a time complexity of O (n 4) and a space complexity of O (n 4) , where n is the number of nodes. However, such complexity limits its applicability to large-scale graph matching tasks. This paper proposes a redesign of the algorithm by transforming the graph matching problem into a one-dimensional linear assignment problem. This transformation enables efficient solving by sorting two n × 1 vectors. The resulting algorithm is named the Lightning Spectral Assignment Method (LiSA), which enjoys a complexity of O (n 2). Numerical experiments demonstrate the efficiency of LiSA, supported by theoretical analysis. [ABSTRACT FROM AUTHOR]