Graph edit distance


In mathematics and computer science,[Connected component (graph theory)|] graph edit distance is a measure of similarity between two graphs.
The concept of graph edit distance was first formalized mathematically by Alberto Sanfeliu and King-Sun Fu in 1983.
A major application of graph edit distance is in inexact graph matching, such
as error-tolerant pattern recognition in machine learning.
The graph edit distance between two graphs is related to the
string edit distance between strings.
With the interpretation of strings as
connected, directed acyclic graphs of
maximum degree one, classical definitions
of edit distance such as Levenshtein distance,
Hamming distance
and Jaro–Winkler distance may be interpreted as graph edit distances
between suitably constrained graphs. Likewise, graph edit distance is
also a generalization of tree edit distance between
rooted trees.

Formal definitions and properties

The mathematical definition of graph edit distance is dependent upon the definitions of
the graphs over which it is defined, i.e. whether and how the vertices and edges of the
graph are labeled and whether the edges are directed.
Generally, given a set of graph edit operations, the graph edit distance between two graphs and, written as can be defined as
where denotes the set of edit paths transforming into and is the cost of each graph edit operation.
The set of elementary graph edit operators typically includes:
Additional, but less common operators, include operations such as edge splitting that introduces a new vertex into an edge, and edge contraction that eliminates vertices of degree two between edges. Although such complex edit operators can be defined in terms of more elementary transformations, their use allows finer parameterization of the cost function when the operator is cheaper than the sum of its constituents.
A deep analysis of the elementary graph edit operators is presented in
And some methods have been presented to automatically deduce these elementary graph edit operators

Applications

Graph edit distance finds applications in handwriting recognition, fingerprint recognition and cheminformatics.

Algorithms and complexity

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.
In addition to exact algorithms, a number of efficient approximation algorithms are also known. Most of them have cubic computational time
Moreover, there is an algorithm that deduces an approximation of the GED in linear time
Despite the above algorithms sometimes working well in practice, in general the problem of computing graph edit distance is NP-complete, and is even hard to approximate.