Ground Truth Correspondence Between Nodes to Learn Graph-Matching Edit-Costs

摘要

The Graph Edit Distance is the most used distance between Attributed Graphs and it is composed of three main costs on nodes and arcs: Insertion, Deletion and Substitution. We present a method to learn the Insertion and Deletion costs of nodes and edges defined in the Graph Edit Distance, whereas, we define the Edit Cost Substitution data dependent and without parameters (for instance the Euclidean distance). In some applications, the ground truth of the correspondence between some pairs of graphs is available or can be easily deducted. The aim of the method we present is the learning process depends on these few available ground truth correspondences and not to the classification set that in some applications is not available. To learn these costs, the optimisation algorithm tends to minimise the Hamming distance between the ground truth correspondences and the automatically extracted node correspondences. We believe that minimising the Hamming distance makes the matching algorithm to find a good correspondence and so, to increase the recognition ratio of the classification algorithm in a pattern recognition application.