In mathematics and computer science, graph edit distance (GED) is a measure of similarity (or dissimilarity) between two graphs.
The concept of graph edit distance was first formalized mathematically by Alberto Sanfeliu and King-Sun Fu in 1983.
[1] A major application of graph edit distance is in inexact graph matching, such as error-tolerant pattern recognition in machine learning.
[2] The graph edit distance between two graphs is related to the string edit distance between strings.
Likewise, graph edit distance is also a generalization of tree edit distance between rooted trees.
denotes the set of edit paths transforming
Although such complex edit operators can be defined in terms of more elementary transformations, their use allows finer parameterization of the cost function
A deep analysis of the elementary graph edit operators is presented in [11][12][13] And some methods have been presented to automatically deduce these elementary graph edit operators.
[14][15][16][17][18] And some algorithms learn these costs online:[19] Graph edit distance finds applications in handwriting recognition,[20] fingerprint recognition[21] and cheminformatics.
[22] Exact algorithms for computing the graph edit distance between a pair of graphs typically transform the problem into one of finding the minimum cost edit path between the two graphs.
The computation of the optimal edit path is cast as a pathfinding search or shortest path problem, often implemented as an A* search algorithm.
Most of them have cubic computational time [23][24] [25] [26] [27] Moreover, there is an algorithm that deduces an approximation of the GED in linear time [28] Despite the above algorithms sometimes working well in practice, in general the problem of computing graph edit distance is NP-hard (for a proof that's available online, see Section 2 of Zeng et al.), and is even hard to approximate (formally, it is APX-hard[29]).