Relational matching with stochastic optimisation

This paper describes a novel framework for performing relational graph matching by stochastic optimisation. The starting point for this study is a configurational probability measure which gauges the consistency of relational matches using a compound exponential function of Hamming distance. In order to overcome some of the well documented shortcomings of deterministic updating, we develop two contrasting stochastic optimisation strategies. The first of these exploits the apparatus of statistical physics to compute the Boltzmann distribution that models the configurational probability measure so that relational matching may be performed by simulated annealing. The second approach is a genetic hill climbing algorithm which is motivated by the way in which our configurational probability measure models matching errors. Because the genetic optimisation commences with a pool of random matches, it obviates the need for accurate initialisation. Moreover, it can recover consistent matches exploiting only structural information from the graphs under match.