Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2208.08233 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913604712792064 |
|---|---|
| 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. This paper integrates several well-known graph matching algorithms into a framework: the constrained gradient method. The primary difference among these algorithms lies in tuning a step size parameter and constraining operators. By leveraging these insights, we propose an adaptive step size parameter to guarantee the underlying algorithms' convergence, simultaneously enhancing their efficiency and robustness. For the constraining operator, we introduce a scalable softassign for large graph matching problems. Compared to the original softassign, our approach offers increased speed, improved robustness, and reduced risk of overflow. The advanced constraining operator enables a CSGO for large graph matching, which outperforms state-of-the-art methods in experiments. Notably, in attributed graph matching tasks, CSGO achieves an over 10X increase in speed compared to current constrained gradient algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_08233 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | CSGO: Constrained-Softassign Gradient Optimization For Large Graph Matching Shen, Binrui Niu, Qiang Zhu, Shengxin Combinatorics Machine Learning Graph matching aims to find correspondences between two graphs. This paper integrates several well-known graph matching algorithms into a framework: the constrained gradient method. The primary difference among these algorithms lies in tuning a step size parameter and constraining operators. By leveraging these insights, we propose an adaptive step size parameter to guarantee the underlying algorithms' convergence, simultaneously enhancing their efficiency and robustness. For the constraining operator, we introduce a scalable softassign for large graph matching problems. Compared to the original softassign, our approach offers increased speed, improved robustness, and reduced risk of overflow. The advanced constraining operator enables a CSGO for large graph matching, which outperforms state-of-the-art methods in experiments. Notably, in attributed graph matching tasks, CSGO achieves an over 10X increase in speed compared to current constrained gradient algorithms. |
| title | CSGO: Constrained-Softassign Gradient Optimization For Large Graph Matching |
| topic | Combinatorics Machine Learning |
| url | https://arxiv.org/abs/2208.08233 |