Skip to yearly menu bar Skip to main content


Poster

Generalizing Graph Matching beyond Quadratic Assignment Model

Tianshu Yu · Junchi Yan · Yilin Wang · Wei Liu · baoxin Li

Room 210 #89

Keywords: [ Combinatorial Optimization ] [ Computer Vision ]


Abstract:

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.

Live content is unavailable. Log in and register to view live content