Lightning graph matching
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911969984905216 |
|---|---|
| author | shen, Binrui. niu, Qiang. zhu, Shengxin. |
| author_facet | shen, Binrui. niu, Qiang. zhu, Shengxin. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_14701 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Lightning graph matching shen, Binrui. niu, Qiang. zhu, Shengxin. Combinatorics Spectral Theory 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. |
| title | Lightning graph matching |
| topic | Combinatorics Spectral Theory |
| url | https://arxiv.org/abs/2310.14701 |