Computing Graph Edit Distance via Neural Graph Matching

Summary: Introduce GEDGNN, a GNN that jointly predicts GED and a node-matching matrix, enabling recovery of edit paths via a k-best matching post-processing step—bridging regression-based GNNs and constructive edit-path algorithms. Achieves 4.9–74.3% MAE reduction vs prior GNNs and 53.6–88.1% MAE reduction on edit-path-derived GED vs state-of-the-art Noah across real and synthetic graphs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13039
Venue: VLDB
Year: 2023
Pagerank: 6.7879009e-05
Overall Rank: 3,752 | 73.90%
DOI: 10.14778/3594512.3594514

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,069	Computing Approximate Graph Edit Distance via Optimal Transport	2025	SIGMOD	4.5934204e-05
9,484	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3341665e-05
9,935	Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach	2025	SIGMOD	4.2482599e-05
10,233	Efficient GNN Training on Giant Graphs with Collective Batching and Scheduling	2026	VLDB	4.1945683e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	4.1945683e-05
10,302	Chipmink: Efficient Delta Identification for Massive Object Graphs	2026	VLDB	4.1945683e-05
10,487	Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods	2025	SIGMOD	4.1945683e-05
10,692	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	4.1945683e-05
10,843	Machine Learning for Graph Data Management and Query Processing	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
3,001	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7404487e-05
3,778	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7747398e-05
3,849	TaGSim: Type-aware Graph Similarity Learning and Computation	2022	VLDB	6.7064042e-05
4,837	Entity Resolution with Hierarchical Graph Attention Networks	2022	SIGMOD	5.8892326e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
951	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00015106325
6,441	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0603113e-05
11,559	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1945683e-05
6,839	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	4.9109527e-05
11,818	NED: An Inter-Graph Node Metric Based On Edit Distance	2017	VLDB	4.1945683e-05
10,692	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	4.1945683e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	4.1945683e-05
3,849	TaGSim: Type-aware Graph Similarity Learning and Computation	2022	VLDB	6.7064042e-05
8,069	Computing Approximate Graph Edit Distance via Optimal Transport	2025	SIGMOD	4.5934204e-05
10,487	Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods	2025	SIGMOD	4.1945683e-05