CSGO: Constrained-Softassign Gradient Optimization For Large Graph Matching
This work addresses efficiency and robustness issues in graph matching, particularly for large-scale applications, though it is incremental as it builds on and improves existing constrained gradient methods.
The paper tackled the problem of large graph matching by proposing CSGO, a framework that integrates existing algorithms with an adaptive step size and a scalable softassign operator, resulting in over 10X speed increase in attributed graph matching tasks compared to current methods.
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.