Generalizing Graph Matching beyond Quadratic Assignment Model

Graph matching has received persistent attention over decades, which can be formulated as a quadratic assignment problem (QAP). We show that a large family of functions, which we define as Separable Functions, can approximate discrete graph matching in the continuous domain asymptotically by varying the approximation controlling parameters. We also study the properties of global optimality and devise convex/concave-preserving extensions to the widely used Lawler's QAP form. Our theoretical findings show the potential for deriving new algorithms and techniques for graph matching. We deliver solvers based on two specific instances of Separable Functions, and the state-of-the-art performance of our method is verified on popular benchmarks.

Authors

• Tianshu Yu Chinese University of Hong Kong, Shenzhen
• Junchi Yan School of Artificial Intelligence & Department of CSE & MoE Lab of AI, Shanghai Jiao Tong University
• Yilin Wang Adobe
• Wei Liu University of Technology Sydney
• Baoxin Li Arizona State University

Keywords

No keywords are indexed for this paper.