Graph edit distance

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.¹ 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.⁶⁷⁸⁹¹⁰

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 (also known as elementary graph operations), the graph edit distance between two graphs ${\displaystyle g_{1}}$ and ${\displaystyle g_{2}}$, written as ${\displaystyle GED(g_{1},g_{2})}$ can be defined as

${\displaystyle GED(g_{1},g_{2})=\min _{(e_{1},...,e_{k})\in {\mathcal {P}}(g_{1},g_{2})}\sum _{i=1}^{k}c(e_{i})}$

where ${\displaystyle {\mathcal {P}}(g_{1},g_{2})}$ denotes the set of edit paths transforming ${\displaystyle g_{1}}$ into (a graph isomorphic to) ${\displaystyle g_{2}}$ and ${\displaystyle c(e)\geq 0}$ is the cost of each graph edit operation ${\displaystyle e}$.

The set of elementary graph edit operators typically includes:

vertex insertion to introduce a single new labeled vertex to a graph.

vertex deletion to remove a single (often disconnected) vertex from a graph.

vertex substitution to change the label (or color) of a given vertex.

edge insertion to introduce a new colored edge between a pair of vertices.

edge deletion to remove a single edge between a pair of vertices.

edge substitution to change the label (or color) of a given edge.

Additional, but less common operators, include operations such as edge splitting that introduces a new vertex into an edge (also creating a new edge), and edge contraction that eliminates vertices of degree two between edges (of the same color). Although such complex edit operators can be defined in terms of more elementary transformations, their use allows finer parameterization of the cost function ${\displaystyle c}$ 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.^1415161718 And some algorithms learn these costs online:¹⁹

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

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 ^{2324 25 26}

²⁷ however, the runtime of at least one algorithm is linear in the number of nodes while still being cubic in the node degree.²⁸

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²⁹).

Tree Edit Distance (TED) represents the minimum cost of transforming one tree into another using three operations: insertion, deletion, and replacement. The first polynomial-time TED algorithm was proposed by Tai in 1979³⁰. In 1989, Kaizhong Zhang and Dennis Shasha proposed the most well-known TED algorithm³¹, which introduced Dynamic Programming (DP) techniques to solve TED and has a worst-case time complexity of O(n⁴). This method employs a series of DP tables, where each table computes the edit distance between a subpart of the first input tree and a subpart of the second input tree. Since then, substantial research efforts³²³³³⁴ have focused on improving its sequential time complexity, and it has been proven that O(n³) is the lowest theoretical bound³⁵.

Despite these sequential improvements, TED remains computationally expensive for large trees, and its parallelization is highly non-trivial³⁶. Specifically, TED computation involves both intra-table and inter-table data dependencies: entries within a DP table depend on previously computed entries, while the computation of each DP table depends on results from other tables¹⁰. These intricate dependencies hinder parallel execution. Moreover, the severe workload imbalance across DP tables further complicates scheduling and reduces parallel resource utilization.

X-TED¹⁰ is a massively parallel framework for TED computation that addresses these structural challenges. It employs a new preprocessing algorithm to efficiently determine dependency relationships among DP tables by analyzing only the tree structures. Based on this dependency information, X-TED groups independent DP tables into batches and processes them in parallel. To handle tables of different sizes, X-TED further adopts a dynamic parallelization strategy that allocates different levels of parallel resources according to each table’s size. Extensive experiments on multicore CPUs and GPUs using real-world and synthetic trees demonstrate the effectiveness of X-TED for large-scale TED computation¹⁰.