Symbolic graph matching with the EM algorithm

This paper describes how relational graph matching can be effected using the expectation and maximisation algorithm. According to this viewpoint, matching is realised as a two-step iterative EM-like process. Firstly, updated symbolic matches are located so as to minimise the divergence between the model and data graphs. Secondly, with the updated matches to hand probabilities describing the affinity between nodes in the model and data graphs may be computed. The probability distributions underpinning this study are computed using a simple model of uniform matching errors. As a result, the expected likelihood function is defined over a family of exponential distributions of Hamming distance. We evaluate our matching method and offer comparison with both mean-field annealing and quadratic assignment. (C) 1998 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.