Graph Matching via Multiplicative Update Algorithm
As a fundamental problem in computer vision, graph matching problem can usually be formulated as a Quadratic Programming (QP) problem with doubly stochastic and discrete (integer) constraints. Since it is NP-hard, approximate algorithms are required. In this paper, we present a new algorithm, called Multiplicative Update Graph Matching (MPGM), that develops a multiplicative update technique to solve the QP matching problem. MPGM has three main benefits: (1) theoretically, MPGM solves the general QP problem with doubly stochastic constraint naturally whose convergence and KKT optimality are guaranteed. (2) Empirically, MPGM generally returns a sparse solution and thus can also incorporate the discrete constraint approximately. (3) It is efficient and simple to implement. Experimental results show the benefits of MPGM algorithm.
This paper presents a novel method (MPMG) to solve QP graph matching problem. The graph matching problem is formulated as argmax_x(x^TWx) where W encodes the pair-to-pair and node-to-node affinities and x is the desired permutation matrix (in vector form). The desired solution is a permutation encoding the optimal matching, also expressed as doubly stochastic (entries >= 0, rows/columns sum to 1) and discrete (entries in {0,1}). The standard approaches to solving the QP is to relax the NP-hard problem (relaxation can be for either the doubly-stochastic constraint or the discrete constraint). This proposed MPMG solution follows the Lagrange multiplier technique which moves the doubly-stochastic constraint into the error term. This proposed approach, along with proofs for convergence and KKT-optimality are a a novel contribution for this graph matching formulation. Experimentally, evidence is provided that shows the approach converges near a sparse/discrete solution even though the constraint is not explicitly modeled in the solution, which is the most promising feature of the method. However, there are some concerns regarding the experimental details which might jeopardize the strength of the empirical claims.
Other state of the art techniques do rely on iterative solutions, so the paper should mention the convergence criterion especially for experiments like figure 1 where the MPMG is initialized with RRWM, it would be useful to make sure that the convergence criterion for RRWM is appropriately selected for these problems.
Following up on the previous comment, it seems initialization with RRWM is used for FIgure 1 but initialization with SM for the subsequent experiments. Furthermore, regarding the experiments, how is performance time computed? Is this including time for the initialization procedure, or just the subsequent MPGM iterations after initialization?
Also, RRWM also requires an initialization. In [3] the basic outline of the algorithm uses uniform, so is it a fair comparison at all for MPMG that uses a established algorithm as initialization vs RRWM which uses uniform? If the details have been handled properly perhaps more explanation should be given in the text to clarify these points. In light of these points it is hard to take anything meaningful away from the experiments provided.
In the experiments, how are the node-to-node affinities determined (diagonals of W)? I think this is not described in the paper.
Image feature point matching would not actually be solved as a graph matching problem in any practical scenario (this is true for a number of reasons not limited to number of features, pair-to-pair affinities, robustness to large # of outliers). As the paper suggests, there are many other practical labeling problems which are typically solved using this QP formulation and perhaps the paper would have more value stronger