


























Graph matching aims to find correspondences between two graphs. It is a fundamental task in pattern recognition. The classical spectral matching algorithm has time complexity $\mathcal{O}(n^4)$ and space complexity $\mathcal{O}(n^4)$, where $n$ is the number of nodes. Such a complexity limits the applicability to large-scale graph matching tasks. This paper proposes an efficient redesign of spectral matching by transforming the graph matching problem into a 1D linear assignment problem, which can be solved efficiently by sorting two $n \times 1$ vectors. The resulting algorithm is named the lightning spectral assignment method (LiSA), which enjoys a complexity of $\mathcal{O}(n^2)$. Numerical experiments demonstrate the efficiency and the theoretical analysis of the strategy.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。