Bayesian graph edit distance
- 1 June 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 22 (6) , 628-635
- https://doi.org/10.1109/34.862201
Abstract
This paper describes a novel framework for comparing and matching corrupted relational graphs. The paper develops the idea of edit-distance originally introduced for graph-matching by Sanfeliu and Fu [1]. We show how the Levenshtein distance can be used to model the probability distribution for structural errors in the graph-matching problem. This probability distribution is used to locate matches using MAP label updates. We compare the resulting graph-matching algorithm with that recently reported by Wilson and Hancock. The use of edit-distance offers an elegant alternative to the exhaustive compilation of label dictionaries. Moreover, the method is polynomial rather than exponential in its worst-case complexity. We support our approach with an experimental study on synthetic data and illustrate its effectiveness on an uncalibrated stereo correspondence problem. This demonstrates experimentally that the gain in efficiency is not at the expense of quality of match.Keywords
This publication has 23 references indexed in Scilit:
- Genetic algorithms for structural editingPublished by Springer Nature ,1998
- Genetic algorithm parameter sets for line labellingPattern Recognition Letters, 1997
- Inexact graph matching using genetic searchPattern Recognition, 1997
- The normalized string editing problem revisitedPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1996
- A constrained edit distance between unordered labeled treesAlgorithmica, 1996
- Organizing large structural modelbasesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1995
- Parametric string edit distance and its application to pattern recognitionIEEE Transactions on Systems, Man, and Cybernetics, 1995
- Computation of normalized edit distance and applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1993
- Simple Fast Algorithms for the Editing Distance between Trees and Related ProblemsSIAM Journal on Computing, 1989
- The String-to-String Correction ProblemJournal of the ACM, 1974