CSGO: Constrained-softassign gradient optimization for large graph matching

Graph matching aims to find correspondences between two graphs. This paper proposes a unifying constrained gradient optimization framework that systematically incorporates classical algorithms, including graduated assignment, spectral matching, and projected fixed-point algorithms. 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 and enhance their performance. Second, we introduce a scalable softassign as the constraining operator for large graph matching problems. Compared to conventional softassign, our approach offers superior scalability, outstanding robustness, and excellent efficiency. The advanced constraining operator enables CSGO to handle large graph matching tasks, thereby demonstrating impressive performance in our experiments. Notably, in attributed graph matching tasks, CSGO achieves an over 10x increase in speed compared to current constrained gradient algorithms.