An Energy Function and Continuous Edit Process for Graph Matching

The contributions of this article are twofold. First, we develop a new nonquadratic energy function for graph matching. The starting point is a recently reported mixture model that gauges relational consistency using a series of exponential functions of the Hamming distances between graph neighborhoods. We compute the effective neighborhood potentials associated with the mixture model by identifying the single probability function of zero Kullback divergence. This new energy function is simply a weighted sum of graph Hamming distances. The second contribution is to locate matches by graduated assignment. Rather than solving the mean-field saddle-point equations, which are intractable for our nonquadratic energy function, we apply the soft-assign ansatz to the derivatives of our energy function. Here we introduce a novel departure from the standard graduated assignment formulation of graph matching by allowing the connection strengths of the data graph to update themselves. The aim is to provide a means by which the structure of the data graph can be updated so as to rectify structural errors. The method is evaluated experimentally and is shown to outperform its quadratic counterpart.