Graph Edit Distance: Basics and History

摘要

Defining a metric between objects is a basic step of any pattern recognition algorithm. Using graphs, this notion of distance is not straightforward. Among the different distances between graphs that one may imagine, the Graph Edit Distance has progressively become a standard tool within the structural pattern recognition framework. Indeed, this distance allows to take into account fine differences between graphs, may be easily tuned and may satisfy all the axioms of a distance. Basically, the most common definition of the graph edit distance is based on the notion of edit path. An edit path between two graphs G_1 and G_2 is a sequence of node/edge removal/substitution or insertion operations transforming G_1 into G_2. Each edit path may be associated to a cost hence defining the Graph Edit Distance between G_1 and G_2 as the minimal cost of all edit paths between these two graphs. Within this survey, we will first review some definitions and properties of the Graph Edit Distance in order to set up a framework which will allow us to review the main families of methods used to compute the graph edit distance. Among them, we may cite methods based on a tree search or methods based on integer programming.