Abstract

Due to its wide range of applications, matching betweentwo graphs has been extensively studied and remains an ac-tive topic. By contrast, it is still under-exploited on howto jointly match multiple graphs, partly due to its intrinsiccombinatorial intractability. In this work, we address this challenging problem in a principled way under the rank-1 tensor approximation framework. In particular, we formulate multi-graph matching as a combinational optimization problem with two main ingredients: unary matching overgraph vertices and structure matching over graph edges,both of which across multiple graphs. Then we propose an efficient power iteration solution for the resulting NP-hard optimization problem. The proposed algorithm has several advantages: 1) the intrinsic matching consistency across multiple graphs based on the high-order tensor optimization; 2) the free employment of powerful high-order node affinity; 3) the flexible integration between various types of node affinities and edge/hyper-edge affinities. Experiments on diverse and challenging datasets validate the effectiveness of the proposed approach in comparison with state-ofthe-arts.