Graph Matching via Multiplicative Update Algorithm

Graph matching is a fundamental problem in computer vision and machine learning area. This problem can usually be formulated as a Quadratic Programming (QP) problem with doubly stochastic and discrete (integer) constraints. Since it is NP-hard, approximate algorithms are required. In this paper, we present a new algorithm, called Multiplicative Update Graph Matching (MPGM), that develops a multiplicative update technique to solve the QP matching problem. MPGM has three main benefits: (1) theoretically, MPGM solves the general QP problem with doubly stochastic constraint naturally and directly whose convergence and KKT optimality are guaranteed. (2) Empirically, MPGM generally returns a sparse solution and thus can also incorporate the discrete constraint approximately in its optimization. (3) It is efficient and simple to implement. Experiments on both synthetic and real-world matching tasks show the benefits of MPGM algorithm.