SYMBOLIC GRAPH MATCHING WITH THE EM ALGORITHM

This paper describes how relational graph matching can be effected usi ng the expectation and maximisation algorithm. According to this viewp oint, matching is realised as a two-step iterative EM-like process. Fi rstly, updated symbolic matches are located so as to minimise the dive rgence between the model and data graphs. Secondly, with the updated m atches to hand probabilities describing the affinity between nodes in the model and data graphs may be computed. The probability distributio ns underpinning this study are computed using a simple model of unifor m matching errors. As a result, the expected likelihood function is de fined over a family of exponential distributions of Hamming distance. We evaluate our matching method and offer comparison with both mean-fi eld annealing and quadratic assignment. (C) 1998 Pattern Recognition S ociety. Published by Elsevier Science Ltd. All rights reserved.