JUNCHI YAN ET AL. CONSISTENCY-DRIVEN ALTERNATING OPTIMIZATION FOR MULTI-GRAPH MATCHING: A UNIFIED APPROACH 1 Consistency-driven Alternating Optimization for Multi-Graph Matching: a Unified Approach

Abstract—The problem of graph matching in general is NP-complete and many approximate pairwise matching techniques have been proposed. For a general setting in real applications, it typically requires to find the consistent matchings across a batch of graphs. Sequentially performing pairwise matching is prone to error propagation along the pairwise matching sequence, and the sequences generated in different pairwise matching orders can lead to contradictory solutions. Motivated by devising a robust and consistent multiple-graph matching model, we propose a unified alternating optimization framework for multi-graph matching. In addition, we define and use two metrics related to graph-wise and pairwise consistencies. The former is used to find an appropriate reference graph which induces a set of basis variables and launches the iteration procedure. The latter defines the order in which the considered graphs in the iterations are manipulated. We show two embodiments under the proposed framework that can cope with the non-factorized and factorized affinity matrix, respectively. Our multi-graph matching model has two major characters: i) the affinity information across multiple graphs are explored in each iteration by fixing part of the matching variables via a consistency-driven mechanism; ii) the framework is flexible to incorporate various existing pairwise graph matching solvers in an “out-of-box ” fashion, and also can proceed with the output of other multi-graph matching methods. The experimental results on both synthetic data and real images empirically show that the proposed framework performs competitively with the state-of-the-art. I