Graph Edit Distance (GED)

The core of GED is a user-defined cost function that assigns a penalty to each atomic graph edit operation. Standard operations include:

• Node Insertion/Deletion: Adding or removing an isolated vertex.
• Edge Insertion/Deletion: Adding or removing a connection between existing vertices.
• Node Substitution: Replacing a vertex label (e.g., changing a carbon atom to a nitrogen atom). The flexibility to weight these operations differently allows domain experts to tune the metric; for example, deleting a node can be penalized more heavily than substituting its label, reflecting chemical stability constraints.

Computing the exact GED between two graphs is an NP-complete problem, meaning the worst-case runtime grows exponentially with graph size. This is formally proven by reduction from the subgraph isomorphism problem. For practical applications, exact computation via A* search with bipartite heuristics is typically limited to graphs with fewer than 16 nodes. For larger molecular graphs, practitioners rely on approximation algorithms or neural network-based regression models that predict GED directly from learned embeddings.

When cost functions satisfy specific constraints, GED defines a proper distance metric in the space of graphs. The required axioms are:

• Non-negativity: The distance is always zero or positive.
• Identity of Indiscernibles: The distance is zero if and only if the graphs are isomorphic.
• Symmetry: The distance from graph A to B equals the distance from B to A.
• Triangle Inequality: The direct distance between two graphs is never greater than the sum of distances via an intermediate graph. These properties make GED suitable for metric indexing structures like BK-trees for fast similarity search.

A widely used approximation algorithm, often called BP-GED, reformulates the edit distance problem as an assignment problem on a cost matrix. The algorithm:

• Constructs a complete bipartite graph between the node sets of the two input graphs.
• Assigns costs to node substitutions, insertions, and deletions based on local structural context.
• Solves the resulting linear sum assignment problem using the Hungarian algorithm in cubic time. This method provides a fast upper bound on the true GED and is the default approach in many cheminformatics libraries.

In cheminformatics, GED is often specialized as Chemical Edit Distance where edit costs are derived from chemical principles. Key adaptations include:

• Bond-breaking penalties: Edge deletions are weighted by bond dissociation energies.
• Stereo-aware substitution: Node substitution costs account for chirality and stereochemistry mismatches.
• Maximum Common Subgraph (MCS) connection: For specific cost functions, GED is mathematically equivalent to the size of the MCS, linking it to substructure-based similarity metrics. This makes GED a gold standard for quantifying lead optimization changes in medicinal chemistry.

To bypass the NP-complete bottleneck, modern approaches train Graph Neural Networks (GNNs) to directly regress GED values. The standard paradigm involves:

• A Siamese GNN architecture where two graphs are encoded into fixed-length embedding vectors by weight-shared networks.
• A Neural Tensor Network or attention-based interaction layer that computes a similarity score from the pair of embeddings.
• Training on synthetically generated graph pairs with pre-computed exact GED labels for small graphs, then generalizing to larger structures. Models like SimGNN and GraphSim achieve sub-second inference with high correlation to true GED.