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: hfac1a4fc6423cfd9
Venue: VLDB
Year: 2009
Pagerank: 0.00011898162
Overall Rank: 1,133 | 92.39%
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,293	Finding Related Tables in Data Lakes for Interactive Data Science	2020	SIGMOD	0.00011149857
3,306	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD	7.4422756e-05
3,369	Connected Substructure Similarity Search	2010	SIGMOD	7.3698379e-05
3,498	COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks	2015	SIGMOD	7.2551144e-05
3,569	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	7.1987748e-05
3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.1706333e-05
3,994	TaGSim: Type-aware Graph Similarity Learning and Computation	2022	VLDB	6.8678851e-05
5,290	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.1937978e-05
5,444	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1268526e-05
6,027	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD	5.9112117e-05
7,206	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	5.5862482e-05
8,231	Computing Approximate Graph Edit Distance via Optimal Transport	2025	SIGMOD	5.3722895e-05
9,235	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	5.2056825e-05
9,568	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB	5.1571823e-05
9,788	On-the-Fly Token Similarity Joins in Relational Databases	2014	SIGMOD	5.1272311e-05
9,840	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1230858e-05
11,187	Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods	2025	SIGMOD	4.9793485e-05
12,316	NED: An Inter-Graph Node Metric Based On Edit Distance	2017	VLDB	4.9793485e-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
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
192	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00025659453
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022599109
293	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021943678
330	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00020838159
736	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014363536
1,216	A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures	2003	VLDB	0.00011490695
2,376	Towards Graph Containment Search and Indexing	2007	VLDB	8.5543073e-05
3,108	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.640323e-05
4,663	Approximate Matching of Hierarchical Data Using pq-Grams	2005	VLDB	6.4810192e-05
7,699	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB	5.4751052e-05

Semantically Similar Papers

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