seminar

Graph matching aims to find correspondences between two graphs, which is a fundamental problem in computer vision and pattern recognition. We unify several famous graph matching algorithms into the same framework: the constrained gradient method. These algorithms differ in the step size parameter or constraining operator. We propose an adaptive step size parameter to guarantee the underlying algorithms’ convergence and enhance robustness. As for the constraining operator aspect, we first redesign a classical spectral matching algorithm by transforming the graph matching problem into a one-dimensional linear assignment problem, which can be solved efficiently by sorting two vectors. Besides, we propose an adaptive softassign that automatically tunes the parameter based on a given error bound to guarantee efficiency and accuracy. Several Sinkhorn formulas introduced in this study can also be used in optimal transport problems. The resulting graph matching algorithm enjoys higher accuracy than the previous state-of-the-art large graph matching algorithms.



•Binrui Shen, Qiang Niu, Shengxin Zhu, Adaptive Softassign via Hadamard-Equipped Sinkhorn, in: CVPR, 2024.
•Binrui Shen, Qiang Niu, Shengxin Zhu, Dynamical softassign and adaptive parameter tuning for graph matching, ARXIV.2208.08233.
•Binrui Shen, Qiang Niu, Shengxin Zhu, Lightning graph matching, ARXIV.2310.14701.