Timezone: »

Generalizing Graph Matching beyond Quadratic Assignment Model
Tianshu Yu · Junchi Yan · Yilin Wang · Wei Liu · baoxin Li

Wed Dec 05 02:00 PM -- 04:00 PM (PST) @ Room 210 #89

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.

Author Information

Tianshu Yu (Arizona State University)
Junchi Yan (Shanghai Jiao Tong University)
Yilin Wang (Adobe)
Wei Liu (Tencent AI Lab)
baoxin Li (Arizona State University)

More from the Same Authors