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: 13040
Venue: VLDB
Year: 2023
Pagerank: 6.781373e-05
Overall Rank: 3,756 | 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,072	Computing Approximate Graph Edit Distance via Optimal Transport	2025	SIGMOD	4.5890162e-05
9,486	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3300131e-05
9,936	Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach	2025	SIGMOD	4.2441896e-05
10,233	Efficient GNN Training on Giant Graphs with Collective Batching and Scheduling	2026	VLDB	4.1905499e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	4.1905499e-05
10,314	Chipmink: Efficient Delta Identification for Massive Object Graphs	2026	VLDB	4.1905499e-05
10,497	Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods	2025	SIGMOD	4.1905499e-05
10,700	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	4.1905499e-05
10,847	Machine Learning for Graph Data Management and Query Processing	2025	VLDB	4.1905499e-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
2,988	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7752463e-05
3,781	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7691344e-05
3,851	TaGSim: Type-aware Graph Similarity Learning and Computation	2022	VLDB	6.6999444e-05
4,837	Entity Resolution with Hierarchical Graph Attention Networks	2022	SIGMOD	5.8835638e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
949	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.0001510288
6,436	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0554554e-05
11,563	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1905499e-05
6,835	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	4.9065543e-05
11,826	NED: An Inter-Graph Node Metric Based On Edit Distance	2017	VLDB	4.1905499e-05
10,700	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	4.1905499e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	4.1905499e-05
3,851	TaGSim: Type-aware Graph Similarity Learning and Computation	2022	VLDB	6.6999444e-05
8,072	Computing Approximate Graph Edit Distance via Optimal Transport	2025	SIGMOD	4.5890162e-05
10,497	Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods	2025	SIGMOD	4.1905499e-05