Graph Matching via Multiplicative Update Algorithm
Bo Jiang, Jin Tang, Chris Ding, Yihong Gong, Bin Luo
Abstract
As a fundamental problem in computer vision, graph matching 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 whose convergence and KKT optimality are guaranteed. (2) Em- pirically, MPGM generally returns a sparse solution and thus can also incorporate the discrete constraint approximately. (3) It is efficient and simple to implement. Experimental results show the benefits of MPGM algorithm.
BibTeX
@inproceedings{NIPS2017_d1e946f4,
author = {Jiang, Bo and Tang, Jin and Ding, Chris and Gong, Yihong and Luo, Bin},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Graph Matching via Multiplicative Update Algorithm},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/d1e946f4e67db4b362ad23818a6fb78a-Paper.pdf},
volume = {30},
year = {2017}
}