Softening Discrete Relaxation

Part of Advances in Neural Information Processing Systems 9 (NIPS 1996)

Bibtex Metadata Paper


Andrew Finch, Richard Wilson, Edwin Hancock


This paper describes a new framework for relational graph match(cid:173) ing. The starting point is a recently reported Bayesian consistency measure which gauges structural differences using Hamming dis(cid:173) tance. The main contributions of the work are threefold. Firstly, we demonstrate how the discrete components of the cost func(cid:173) tion can be softened. The second contribution is to show how the softened cost function can be used to locate matches using continuous non-linear optimisation. Finally, we show how the res(cid:173) ulting graph matching algorithm relates to the standard quadratic assignment problem.