Reading Edit Operations Out of Graph Similarity Embeddings

Neural graph similarity models turn each graph into a single vector, so that comparing two molecules, programs or meaning graphs becomes a fast vector distance instead of an expensive combinatorial search. The standard target is graph edit distance: the cheapest sequence of node and edge insertions, deletions and relabelings that turns one graph into the other. These models are fast, but they return only a number. They do not say which edits make two graphs differ. They also break when edits have unequal costs, which is the usual case in practice. This proposal asks a simple question. When such a model is trained to predict edit distance, does the difference between two graph vectors break down, approximately linearly, into a sum of directions, one per type of edit operation? If it does, the edit operations themselves supply the missing "vocabulary" for interpreting graph embeddings. The model's opaque score could then be turned into an edit profile, meaning a count of how many edits of each type separate the two graphs. That profile could be re-costed under any edit-cost scheme without retraining.

The method fits in two sentences. We build a dictionary of edit directions by embedding many graph pairs that differ by exactly one known edit, which costs nothing to label. We then explain any new pair by sparsely decomposing its embedding difference over that dictionary, and we test with linear probes whether the recovered edit counts match the true optimal edit paths and predict edit distances under non-uniform costs.

Core Claim

For a frozen encoder $f$ trained on uniform-cost edit distance, let $\Delta z = f(G_1) - f(G_2)$. Let $d_k$ be the average embedding shift caused by a single edit of type $k$. Examples are "insert a carbon node," "delete an edge between N and O," or "relabel C to N." We claim that

$$\Delta z \approx \sum_{k} c_k\, d_k,\qquad c_k \ge 0,$$

where $c_k$ closely tracks the number of type-$k$ operations in an optimal edit path. The approximation should hold best at intermediate encoder layers and should degrade gracefully as the edit distance grows. If the claim holds, two things follow. A non-uniform edit distance with per-type costs $w_k$ can be estimated as $\sum_k w_k \hat c_k$ from a model that never saw those costs. The decomposition also gives a human-readable account of why two graphs are far apart.

The claim can fail. Edit operations need not compose additively in a nonlinear encoder, and the model may encode distance in a way that cannot be split into edit types. Finding out which is true is the scientific contribution in either case.

Relation to Prior Work

Two papers motivate the gap. GraSP shows that single-graph embeddings with no cross-graph interaction can predict edit distance and maximum common subgraph accurately. It combines random-walk positional encodings, gated residual convolutions and multi-scale pooling. It treats the resulting vectors as black boxes, and its nonlinear tensor head leaves open whether similarity is linearly organized at all. Graph Edit Distance Evaluation Datasets: Pitfalls and Mitigation shows two problems: the standard benchmarks leak through isomorphic graphs, and Euclidean-distance models such as GMN-Embed and GREED degrade badly under non-uniform edit costs. That second finding is exactly what an edit-profile readout would try to fix.

Two papers supply the method. Probing Graph Representations introduced pairwise probing. It builds molecule pairs that differ by one functional group and checks whether $\Delta z$ points in a consistent direction. It also found that middle layers retain structure best. We reuse the pairwise construction, but we apply it to similarity models rather than property predictors, and to a complete basis of edit types rather than a handful of chemical groups. SpLiCE decomposes CLIP embeddings by non-negative sparse regression over a 15,000-word concept vocabulary after mean-centering. We borrow its solver and its centering step. We replace the text vocabulary, which graphs lack, with an edit vocabulary that is defined by construction.

Other papers constrain the design. Graph dictionary learning methods, namely Online Graph Dictionary Learning with its Gromov-Wasserstein atoms and Mahalanobis upper bound, and Generative Graph Dictionary Learning, learn structural atoms such as communities and motifs, but those atoms are redundant and not tied to edit distance. Our atoms are fixed operations, so redundancy can be measured directly rather than regularized away. EUGENE produces explicit edit paths without supervision, but it runs an optimization for each pair and cannot index graphs. We aim for a coarser output, a count per edit type rather than a node-level path, at vector-lookup cost. The extractability-versus-use caution raised by Akhondzadeh et al. and by work on the non-linear representation dilemma applies here too. For that reason we test whether edit directions carry the model's own predicted distance, and not only whether they can be decoded.

Research Program

We train GraSP and GMN-Embed on uniform-cost edit distance on deduplicated versions of AIDS700nef, LINUX and IMDB, following the isomorphism-aware splits from the pitfalls paper, and freeze them. For each dataset we enumerate the edit types observed in its label alphabet. We then generate single-edit pairs by applying one random edit of each type to training graphs. We keep only valid graphs and check exactly that the edit distance is 1. At every layer's pooled representation we estimate $d_k$ as the mean $\Delta z$ over its single-edit pairs. We record a consistency score for each direction, the mean cosine to that average, as a pairwise-probe diagnostic.

For an arbitrary test pair we solve a non-negative LASSO for $\hat c$. Deletion and insertion are represented as separate atoms, so the sign ambiguity lives in the dictionary and not in the coefficients. Ground truth for evaluation comes from exact solvers on small graphs, which give optimal edit paths from which we read true type counts $c^\ast$. Exact solutions are used only for evaluation, never to build the dictionary. We then vary what the encoder has seen: a randomly initialized encoder as the standard probing control, a graph autoencoder that was never trained on edit distance, and the edit-distance-trained models. This separates "the architecture makes edits linear" from "similarity training makes edits linear."

Baselines

The naive reference point is the label-histogram bound. The difference between the two graphs' node-label and edge-label-pair histograms already gives a lower bound on node insertions, deletions and relabelings, and it recovers some edge counts. Any edit profile that only matches this bound has learned nothing structural. We therefore report every metric separately on the part of the edit profile the histogram cannot determine, mainly edge edits in graphs with matching label counts. We count as beating it only if the dictionary improves correlation with $c^\ast$ on that residual.

The strongest direct competitor is a supervised linear probe: ridge regression from $\Delta z$ (and from $|\Delta z|$) to $c^\ast$, trained on exact-solver edit paths. It uses the same frozen embeddings, the same layers and the same test pairs, with cross-validated regularization and a label budget matched to the pair counts. It is strongest because it is given the true answers the dictionary never sees. The dictionary counts as winning if it comes within a small margin of this probe while using only free single-edit labels. We also report the probe's label cost in exact-solver hours.

For non-uniform costs, the strongest existing method is GraSP retrained directly on each non-uniform cost setting (NU-GED, NUE-GED, L-GED from the pitfalls paper) with the same tuning budget as the uniform model. The file reports GraSP's advantage only as relative figures: an 11.9% improvement in precision at 10 over the previous best on AIDS, and for EUGENE up to a 72% reduction in mean absolute error on AIDS versus supervised methods. No reported result was found on Lacuna for absolute non-uniform-cost error of any model, so we will produce those numbers ourselves. Beating this baseline means matching retrained-model error within a fixed tolerance with zero retraining, or exceeding the Euclidean-distance models the pitfalls paper shows degrading.

An unsupervised sparse autoencoder trained on $\Delta z$ serves as the ablation for our key ingredient, grounding atoms in known edits. If its learned atoms align with the $d_k$ and predict $c^\ast$ equally well, the grounding is unnecessary.

Why not just…?

Why not just train a supervised probe from embedding differences to edit counts? This is the real threat, and it is run as a baseline. Its weakness is labels: every training target needs an optimal edit path from an NP-hard solver, the very bottleneck that motivated neural similarity models. The dictionary needs only single-edit pairs. If the supervised probe is far better, we will report that edit information is present but not additively organized. That is a substantive negative result, and it would narrow the claim to "decodable, not compositional."

Why not just run EUGENE or an exact solver when an explanation is needed? Those methods give finer, node-level paths and should be used when a path is truly required. They do not scale to explaining ranked results across an indexed database, because they cost a full optimization per pair. We will report wall-clock time per explained pair next to profile accuracy, so the tradeoff is visible and not merely asserted.

Why not just retrain for each cost scheme? Retraining works when costs are fixed and labels are affordable. Each new cost scheme, though, needs a fresh set of exact labels and a fresh model. The experiment against retrained GraSP shows directly how much accuracy re-costing a single edit profile gives up.

Why not just learn graph dictionary atoms with optimal transport? Online GDL and FRAME atoms describe what graphs are made of, not how two graphs differ under edit distance, and FRAME reports redundant atoms. We include Online GDL's Mahalanobis proxy as a reference for ranking, but it does not target edit distance.

Decisive Checks

Four results decide the proposal. First, the additivity test: for pairs built by applying $m$ known edits, the relative error $\|\Delta z - \sum_k c_k d_k\|/\|\Delta z\|$, plotted against $m$ and against layer. We expect it to stay small at intermediate layers for small $m$. If it is large even at $m=2$, the core claim fails.

Second, profile recovery: on deduplicated AIDS, LINUX and IMDB test pairs, Spearman correlation and exact-match rate between $\hat c$ and $c^\ast$, reported on the histogram-undetermined residual and compared with the supervised probe and the autoencoder control.

Third, cost transfer: mean absolute error of $\sum_k w_k \hat c_k$ under the pitfalls paper's non-uniform settings, against retrained GraSP and the Euclidean-distance models.

Fourth, use rather than mere extractability: we project the found directions out of the embeddings and measure how much the frozen model's own predicted distance changes, relative to projecting out random directions of the same size. Large changes indicate the model actually relies on edit directions.

As an out-of-distribution stress test, we repeat the additivity and recovery checks on Mutagenicity and ogbg-molhiv pairs with larger edit distances.