Lightning graph matching
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |