Publication
On the graph edit distance costs: properties and applications
Journal Article (2012)
Journal
International Journal of Pattern Recognition and Artificial Intelligence
Pages
1260004
Volume
26
Number
5
Doc link
http://dx.doi.org/10.1142/S021800141260004X
File
Abstract
In this article, we model the edit distance as a function in a labelling space. We consider the labelling space a Euclidean space where coordinates correspond to the graph edit insertion and deletion costs. Through this model, we characterize a class of cost. A class of cost is defined as a region, in the labelling space, where all the graph edit distances are obtained using the same optimal labelling. Moreover, we characterise the graph edit distance value through the labelling space. This new point of view of the graph edit distance gives us the opportunity of defining some interesting properties that are useful to a better understanding of the graph edit distance. Finally, we show the usefulness of these properties through some applications.
Categories
pattern recognition.
Author keywords
graph edit distance, graph edit costs, graph similarity, graph distance, errorcorrecting graph isomorphism
Scientific reference
A. Solé, F. Serratosa i Casanelles and A. Sanfeliu. On the graph edit distance costs: properties and applications. International Journal of Pattern Recognition and Artificial Intelligence, 26(5): 1260004, 2012.
Follow us!