Learning Edit Cost Estimation Models for Graph Edit Distance

International audienceOne of the most popular distance measures between a pair of graphs is the Graph Edit Distance. This approach consists of finding a set of edit operations that completely transforms a graph into another. Edit costs are introduced in order to penalize the distortion that each edit operation introduces. Then, one basic requirement when we design a Graph Edit Distance algorithm, is to define the appropriate edit cost functions. On the other hand, Machine Learning algorithms has been applied in many contexts showing impressive results, due, among other things, its ability to find correlations between input and output values. The aim of this paper is to bring the potentialities of Machine Learning to the Graph Edit Distance problem presenting a general framework in which this kind of algorithms are used to estimate the edit costs values for node substitutions