STRUCTURAL MATCHING BY DISCRETE RELAXATION

This paper describes a Bayesian framework for performing relational gr aph matching by discrete relaxation. Our basic aim is to draw on this framework to provide a comparative evaluation of a number of contrasti ng approaches to relational matching. Broadly speaking there are two m ain aspects to this study. Firstly we locus on the issue of how relati onal inexactness may be quantified. We illustrate that several popular relational distance measures can be recovered as specific limiting ca ses of the Bayesian consistency measure. The second aspect of our comp arison concerns the way in which structural inexactness is controlled. We investigate three different realizations ai the matching process w hich draw on contrasting control models. The main conclusion of our st udy is that the active process of graph-editing outperforms the altern atives in terms of its ability to effectively control a large populati on of contaminating clutter.