Learning graph-matching edit-costs based on the optimality of the oracle's node correspondences

The Graph edit distance is the most used distance between attributed graphs and it is defined as the minimum amount of required distortion to transform one graph into the other. Six Edit operations define this distortion: insertion, deletion and substitution of nodes and arcs. To quantitatively determine the degree of distortion, a penalty cost to each edit operation is defined according to the amount of distortion that it introduces in the transformation. Although a proper definition of these costs is a cornerstone of classification or clustering applications, little research has been done to automatically find them. Usually, they are established through a manual validation process. This paper presents an optimization method to learn the value of these costs such that the Hamming distance between an oracle's node correspondence and the automatically correspondence is minimized. Experimental validation shows that the clustering and classification experiments drastically increase their accuracy with the automatically learned costs respect some usual cost values. (C) 2015 Elsevier B.V. All rights reserved.