Timezone: »

Graph Matching via Multiplicative Update Algorithm
Bo Jiang · Jin Tang · Chris Ding · Yihong Gong · Bin Luo

Tue Dec 05 05:45 PM -- 05:50 PM (PST) @ Hall A

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.

Author Information

Bo Jiang (Anhui University)
Jin Tang
Chris Ding (University of Texas at Arlington)
Yihong Gong
Bin Luo

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors