graph edit distance
**Graph Edit Distance (GED)** is a **similarity metric between two graphs defined as the minimum total cost of edit operations (node insertions, node deletions, edge insertions, edge deletions, node substitutions, edge substitutions) required to transform one graph into the other** — providing an intuitive, flexible, and label-aware distance measure that captures both structural and attribute differences between graphs.
**What Is Graph Edit Distance?**
- **Definition**: Given two graphs $G_1$ and $G_2$, the Graph Edit Distance is: $GED(G_1, G_2) = min_{(e_1, ..., e_k) in gamma(G_1, G_2)} sum_{i=1}^{k} c(e_i)$, where $gamma(G_1, G_2)$ is the set of all valid edit paths (sequences of edit operations) transforming $G_1$ into $G_2$, and $c(e_i)$ is the cost of edit operation $e_i$. The edit operations include: inserting or deleting a node, inserting or deleting an edge, and substituting a node or edge label.
- **Cost Function**: Each edit operation has an associated cost that can be customized for the application domain. For molecular graphs, substituting a carbon atom for a nitrogen atom might cost 0.5, while deleting a ring-closure bond might cost 2.0. Uniform costs ($c = 1$ for all operations) give the simplest measure, but domain-specific cost functions produce more meaningful distances.
- **NP-Hardness**: Computing the exact GED is NP-hard — it requires searching over all possible node correspondences between the two graphs, which grows factorially with graph size. For graphs with more than approximately 20 nodes, exact computation becomes intractable, necessitating approximation methods.
**Why Graph Edit Distance Matters**
- **Intuitive Interpretability**: GED provides a natural, human-understandable notion of graph difference — "these two molecules differ by one atom substitution and one bond deletion." Unlike embedding-based distances (which compress graph structure into opaque vectors), GED pinpoints exactly which structural changes distinguish two graphs.
- **Molecular Database Search**: Searching a database of millions of molecular graphs for compounds similar to a query molecule is a fundamental operation in drug discovery. GED provides a principled similarity measure that accounts for both structural topology (bond patterns) and atom-level attributes (element types, charges). Approximate GED methods enable fast retrieval of structurally similar candidates.
- **Error-Tolerant Pattern Matching**: Real-world graphs contain noise — missing edges, misattributed nodes, partial observations. GED provides error-tolerant graph comparison that gracefully handles these imperfections — two graphs can be "close" despite small structural differences, unlike exact graph matching which requires perfect agreement.
- **Neural GED Approximation**: Graph Matching Networks (Li et al., 2019) and SimGNN learn to predict GED from graph pair embeddings, providing $O(N^2)$ or even $O(N)$ approximate GED computation — enabling GED-based graph retrieval at the scale of millions of graphs where exact computation is impossible.
**GED Computation Methods**
| Method | Type | Complexity | Graph Size |
|--------|------|-----------|-----------|
| **A* Search** | Exact | $O(N!)$ worst case | $leq$ 12 nodes |
| **Bipartite Matching (BP)** | Lower bound | $O(N^3)$ | $leq$ 100 nodes |
| **Beam Search** | Approximate | $O(b cdot N^2)$ | $leq$ 500 nodes |
| **SimGNN** | Neural approximation | $O(N^2)$ forward pass | $leq$ 10,000 nodes |
| **Graph Matching Network** | Neural approximation | $O(N^2)$ with cross-attention | $leq$ 10,000 nodes |
**Graph Edit Distance** is **structural typo counting** — measuring how many atomic changes (insertions, deletions, substitutions) separate one graph from another, providing the most interpretable and flexible graph similarity metric at the cost of computational intractability that drives the search for neural approximation methods.