Softening Discrete Relaxation

This paper describes a new framework for relational graph matching. Thestarting point is a recently reported Bayesian consistency measure which gauges structural differences using Hamming distance. Themain contributions of the work are threefold. Firstly, we demonstrate how the discrete components of the cost function canbe softened. The second contribution is to show how the softened cost function can be used to locate matches using continuous nonlinear optimisation. Finally, we show how the resulting graphmatching algorithm relates to the standard quadratic assignment problem. 1 Introduction Graph matching [6, 5, 7, 2, 3, 12, 11J is a topic of central importance in pattern perception. The main computational issues are how to compare inexact relational descriptions (7J and how to search efficiently for the best match [8J. These two issues have recently stimulated interest in the connectionist literature (9, 6, 5, lOJ. For instance, Simic [9], Suganathan et al. (101 and Gold et ai.