Relational matching with mean field annealing

This paper describes a new framework for constructing mean-field energy functions for use in relational matching. The starting point is the Bayesian relational consistency model of Wilson and Hancock (1995). Hitherto, the optimisation of the consistency measure has been effected by the deterministic hill climbing process known as discrete relaxation which is prone to local convergence if local maxima are present. By applying ideas from statistical physics to the configurational matching probabilities we determine the effective potentials of an equivalent Boltzmann distribution. Formally, these potentials are weighted sums of the Hamming distances between matched neighbourhoods in the data graph and their counterparts in the model graph. Adopting a simple softening ansatz we derive mean-field equations for minimising the global graph matching potential. This provides an efficient means of locating the global optima of the Bayesian consistency measure