Revisiting the Generalization of Neural Graph Edit Distance Models

Zhouyang Liu; Ning Liu; Yixin Chen; Jiezhong He; Dongsheng Li

cs.LGOct 3, 2026

Revisiting the Generalization of Neural Graph Edit Distance Models

Authors: Zhouyang Liu, Ning Liu, Yixin Chen, Jiezhong He, Dongsheng Li

Organizations: National University of Defense Technology · Information Support Force Engineering University

Abstract

Neural approaches to Graph Edit Distance (GED) have achieved strong results under standard within-dataset evaluation, but much less is known about how well these models transfer across graph collections. We conduct a systematic study of this problem using exact GED supervision across diverse graph datasets and a broad set of representative learning-based methods. Our results reveal a pronounced gap between within-collection performance and cross-collection transfer. Models that perform well on their training collections often lose this advantage when evaluated on structurally different data. Training on multiple source collections substantially improves zero-shot transfer and provides a better starting point when limited supervision is available for a new target collection. Further analysis shows that transfer behavior varies with the source--target direction and the structural characteristics of the collections involved. These findings suggest that conventional within-collection evaluation provides only a partial view of the generalization behavior of neural GED models and motivate broader evaluation across heterogeneous graph collections.

Figures & tables

Figure 1: Landscape of existing exact GED resources.

Dataset	Domain	$\#$ Graphs	$\#$ Node Labels	$\|\mathcal{V}\|$	GED	#Exact Pairs
AIDS	Molecular	1,488	27	11 / 12 / 20	10 / 16 / 42	1,106,325
BZR	Molecular	404	10	35 / 46 / 57	20 / 45 / 93	37,781
COX2	Molecular	465	8	41 / 46 / 56	16 / 27 / 59	78,100
DHFR	Molecular	719	9	42 / 54 / 71	28 / 55 / 107	124,714
PTC_MR	Molecular	328	18	13 / 23.3 / 64	19 / 41 / 134	52,706
MUTAG	Molecular	175	7	17 / 23.6 / 28	15 / 27 / 43	15,220

Table 1: Statistics of the graph collections in GSCBench. Graph size and GED are reported as median / 90th percentile / maximum.

Figure 2: Graph-level characteristics across the 11 collections.

Figure 3: Spearman correlations between GED and six pair-level structural signals.

Figure 4: Relative distribution shifts across graph collections under four structural views (the darker the more similar).

Method	In-collection			Cross-collection			$\Delta$ Rank
Method	MAE Rank	P@10 Rank	Top-5 Rate	MAE Rank	P@10 Rank	Top-5 Rate	$\Delta$ Rank
SimGNN	12.82	14.54	0/11 (0.0%)	11.51	14.56	0/110 (0.0%)	1.30
GMN-emb	10.20	8.66	1/11 (9.1%)	4.02	3.98	83/110 (75.5%)	6.18
GMN-match	4.00	6.01	7/11 (63.6%)	2.96	4.33	98/110 (89.1%)	1.04
GraphSim	13.22	13.63	0/11 (0.0%)	12.27	10.93	2/110 (1.8%)	0.95
H2MN	12.31	12.41	0/11 (0.0%)	11.01	13.40	4/110 (3.6%)	1.30

Table 2: Single-Source Generalization method-level rank summary.

Figure 5: In- and Cross-collection MAE to approximation.

Panel of Figure 6 — Figure 6: Multi-source training relative to single-source baselines.

	Seen MAE		Seen P@10		Unseen MAE		Unseen P@10
Method	Rank	$\Delta$	Rank	$\Delta$	Rank	$\Delta$	Rank	$\Delta$
SimGNN	13.17 $\to$ 8.33	+4.83	16.08 $\to$ 11.58	+4.50	11.20 $\to$ 10.00	+1.20	16.20 $\to$ 11.60	+4.60
GMN-emb	10.67 $\to$ 4.50	+6.17	8.67 $\to$ 4.42	+4.25	2.00 $\to$ 3.40	-1.40	2.20 $\to$ 4.60	-2.40
GMN-match	3.83 $\to$ 3.00	+0.83	5.58 $\to$ 4.17	+1.42	1.80 $\to$ 3.80	-2.00	2.40 $\to$ 4.40	-2.00
GraphSim	13.17 $\to$ 12.67	+0.50	14.00 $\to$ 13.67	+0.33	13.00 $\to$ 12.00	+1.00	8.80 $\to$ 12.40	-3.60
H2MN	13.00 $\to$ 9.00	+4.00	13.00 $\to$ 9.58	+3.42	11.60 $\to$ 10.20	+1.40	14.60 $\to$ 11.20	+3.40

Table 3: Relative rank changes after multi-source training.

Figure 7: Limited-target adaptation with and without multi-source pretraining.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Resource	Connected	Remove Iso.	Alignment	Runtime	Timeout	GED Solver
Classic	✓	$\times$	$\times$	$\times$	–	A* / Approx.
GraphEdX	$\times$	$\times$	$\times$	✓	n.r.	MIP-F2
Gelato	$\times$	$\times$	✓	$\times$	n.r.	MIP-F2
GRAIL	$\times$	$\times$	$\times$	$\times$	600 s	MIP-F2
Ours	✓	✓	✓	✓	300 s	AStar-LSa

Appendix

Table 4: Comparison of GED benchmark resources. A checkmark indicates that the property is consistently satisfied by the released benchmark used in our comparison. “n.r.” indicates that a fixed timeout is not explicitly reported.

Figure 8: Spearman correlations between exact GED and the frequency difference of each graphlet type.

Setting	Runs / Method	Total	Configuration
In-collection	55	1,100	11 collections $\times$ 5 runs
Zero-shot transfer	550	11,000	11 sources $\times$ 10 targets $\times$ 5 runs
Multi-source pretraining	1	20	Fixed multi-source pool
Limited-target fine-tuning	45	900	5 targets $\times$ 3 budgets $\times$ 3 runs
Few-shot / Scratch	165	3,300	11 targets $\times$ 3 budgets $\times$ 5 runs
Total	816	16,320

Appendix

Table 5: Scale of the experimental evaluation.

Collection	Hungarian	VJ	Beam	FGWAlign	Oracle Approx.
AIDS	9.1748	9.7393	3.4365	1.6830	1.2106
BZR	30.4388	41.4946	14.4075	9.1885	5.8971
COX2	40.2620	56.0973	15.7913	10.4754	6.4562
DHFR	32.8957	51.0385	12.6850	13.5718	6.7223
PTC_MR	8.3955	8.9508	4.9713	3.8320	2.3268
MUTAG	9.0095	9.3844	6.5564	1.9485	1.5965

Appendix

Table 6: MAE of approximation baselines across graph collections.

Collection	Hungarian	VJ	Beam	FGWAlign	Oracle Approx.
AIDS	0.1811	0.1832	0.6521	0.6336	0.8151
BZR	0.4250	0.4266	0.6469	0.6312	0.8219
COX2	0.4560	0.4187	0.7400	0.6053	0.8227
DHFR	0.4617	0.4713	0.6348	0.6061	0.7730
PTC_MR	0.3904	0.3750	0.6231	0.5577	0.7250
MUTAG	0.5679	0.5714	0.6643	0.7750	0.8536

Appendix

Table 7: P@10 of approximation baselines across graph collections.

Figure 10: Source-to-target Precision@10 changes.

Method	In-collection			Cross-collection			$\Delta$ Rank
Method	MAE Rank	P@10 Rank	Top-5 Rate	MAE Rank	P@10 Rank	Top-5 Rate	$\Delta$ Rank
SimGNN	12.96	14.35	0/11 (0.0%)	11.49	14.54	0/110 (0.0%)	1.47
GMN-emb	10.24	8.96	1/11 (9.1%)	4.01	3.96	84/110 (76.4%)	6.23
GMN-match	3.91	5.94	8/11 (72.7%)	2.95	4.36	98/110 (89.1%)	0.95
GraphSim	13.24	13.58	0/11 (0.0%)	12.26	10.92	2/110 (1.8%)	0.97
H2MN	12.29	12.48	0/11 (0.0%)	11.00	13.39	4/110 (3.6%)	1.29

Appendix

Table 8: Single-Source Generalization rank summary for the D-Q (test versus train/validation) test-pair view. GEDRanker is excluded before run-level ranking.

Method	In-collection			Cross-collection			$\Delta$ Rank
Method	MAE Rank	P@10 Rank	Top-5 Rate	MAE Rank	P@10 Rank	Top-5 Rate	$\Delta$ Rank
SimGNN	12.31	11.87	0/11 (0.0%)	11.58	13.33	0/110 (0.0%)	0.73
GMN-emb	11.02	11.22	0/11 (0.0%)	4.07	4.97	81/110 (73.6%)	6.94
GMN-match	4.75	5.59	7/11 (63.6%)	2.96	4.93	97/110 (88.2%)	1.79
GraphSim	13.53	14.13	0/11 (0.0%)	12.34	10.23	3/110 (2.7%)	1.19
H2MN	11.95	12.48	0/11 (0.0%)	11.07	12.20	3/110 (2.7%)	0.87

Appendix

Table 9: Single-Source Generalization rank summary for the Q-Q (test versus test) test-pair view. GEDRanker is excluded before run-level ranking.

Figure 11: Best validation epochs for limited-target adaptationand training from scratch.

Explore similar work

Towards Metric-Faithful Neural Graph Matching
May 7, 2026Jyotirmaya Shivottam, Subhankar MishraGraph Neural Networks Neural Representation Geometry
1National Institute of Science Education and Research (NISER), Bhubaneswar, India · 2Homi Bhabha National Institute, Mumbai, India
To Learn is to Wander: Learning Across Graphs and Tasks with Random Walks
Oct 5, 2026Louis Tichelman, Xingyue Huang, Jinwoo Kim +1Multi-Task Learning Transfer Learning
TU Wien · AITHYRA · University of Oxford +1
Graph Neural Networks for Scalable and Transferable Node Centrality Approximation
Jul 10, 2026Samra Sana, Giorgio Mantica, Saul ImbriciGraph Neural Networks Domain Generalization
Center for Nonlinear and Complex Systems, Università degli Studi dell’Insubria, Como, Italy

May 7, 2026J/K move · Enter open · S save

Towards Metric-Faithful Neural Graph Matching

Jyotirmaya Shivottam, Subhankar Mishra

1National Institute of Science Education and Research (NISER), Bhubaneswar, India · 2Homi Bhabha National Institute, Mumbai, India

Graph Neural Networks Neural Representation Geometry Graph Matching

Open paper AskPDF arXiv

Graph Edit Distance (GED) is a fundamental, albeit NP-hard, metric for structural graph similarity. Recent neural graph matching architectures approximate GED by first encoding graphs with a Graph Neural Network (GNN) and then applying either a graph-level regression head or a matching-based alignment module. Despite substantial architectural progress, the role of encoder geometry in neural GED estimation remains poorly understood. In this paper, we develop a theoretical framework that connects encoder geometry to GED estimation quality for two broad classes of neural GED estimators: graph similarity predictors and alignment-based methods. On fixed graph collections, where the doubly-stochastic metric

d_{\mathrm{DS}}

is comparable to GED, we show that graph-level bi-Lipschitz encoders yield controlled GED surrogates and improved ranking stability; for matching-based estimators, node-level bi-Lipschitz geometry propagates to encoder-induced alignment costs and the resulting optimized alignment objective. We instantiate this perspective using FSW-GNN, a bi-Lipschitz WL-equivalent encoder, as a drop-in replacement in representative neural GED architectures. Across representative baselines and benchmark datasets, the resulting geometry-aware variants significantly improve GED prediction and ranking metrics. A faithfulness case study of untrained encoders, together with ablations and transfer experiments, supports the view that these gains arise from improved representation geometry, positioning encoder geometry as a useful design principle for neural graph matching.

Abstract

Explore similar work

Towards Metric-Faithful Neural Graph Matching

To Learn is to Wander: Learning Across Graphs and Tasks with Random Walks

Graph Neural Networks for Scalable and Transferable Node Centrality Approximation