Comparing Stars: On Approximating Graph Edit Distance

Summary: Proposes three polynomial-time bounds for graph edit distance, enabling scalable approximation for graph data. Introduces AppFull and AppSub for bound-driven graph search; results show pruning and scalability on real and synthetic graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10101
Venue: VLDB
Year: 2009
Pagerank: 0.00012117375
Overall Rank: 1,115 | 92.36%
DOI: 10.14778/1687627.1687631

Incoming Non-self Citations Over Time

Authors

1. Zhiping Zeng (Tsinghua University)
2. Anthony K.H. Tung (National University of Singapore)
3. Jianyong Wang (Tsinghua University)
4. Jianhua Feng (Tsinghua University)
5. Lizhu Zhou (Tsinghua University)

BibTeX Citation

@article{zeng_vldb09,
        title = {{Comparing Stars: On Approximating Graph Edit Distance}},
        author = {Zeng, Zhiping and Tung, Anthony K.H. and Wang, Jianyong and Feng, Jianhua and Zhou, Lizhu},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687631},
        url = {https://doi.org/10.14778/1687627.1687631},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,303	Finding Related Tables in Data Lakes for Interactive Data Science	2020	SIGMOD	0.0001123653
3,311	Connected Substructure Similarity Search	2010	SIGMOD	7.5353184e-05
3,439	COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks	2015	SIGMOD	7.4144782e-05
3,522	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	7.3491042e-05
3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.3214417e-05
3,906	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD	7.0287643e-05
3,933	TaGSim: Type-aware Graph Similarity Learning and Computation	2022	VLDB	7.00884e-05
5,168	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.3353772e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
5,965	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD	6.0256454e-05
7,152	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	5.6872619e-05
8,126	Computing Approximate Graph Edit Distance via Optimal Transport	2025	SIGMOD	5.4827332e-05
9,383	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB	5.2755515e-05
9,613	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	5.2447096e-05
9,665	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.2406724e-05
10,764	Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods	2025	SIGMOD	5.093636e-05
10,939	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	5.093636e-05
12,021	NED: An Inter-Graph Node Metric Based On Edit Distance	2017	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026138589
272	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022695855
302	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021963347
322	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00021275303
727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014565738
1,196	A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures	2003	VLDB	0.00011714981
2,328	Towards Graph Containment Search and Indexing	2007	VLDB	8.745748e-05
3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.8155543e-05
4,566	Approximate Matching of Hierarchical Data Using pq-Grams	2005	VLDB	6.6275286e-05
7,559	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.5985266e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	776	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB
2	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
3	12,021	NED: An Inter-Graph Node Metric Based On Edit Distance	2017	VLDB
4	10,939	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB
5	3,522	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
6	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
7	3,423	Computing Graph Edit Distance via Neural Graph Matching	2023	VLDB
8	10,764	Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods	2025	SIGMOD
9	11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
10	7,152	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD