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⁴) and a space complexity of O(n⁴), 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²). Numerical experiments demonstrate the efficiency of LiSA, supported by theoretical analysis.