Neural Computation, Vol 10, 1873-1894, Copyright © 1998 by The MIT Press
An Energy Function and Continuous Edit Process for Graph Matching
Andrew M. Finch, Richard C. Wilson and Edwin R. Hancock
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.
