DBScholar

Back to papers

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.00011857445
Overall Rank
1,136 | 92.39%
DOI
10.14778/1687627.1687631

Incoming Non-self Citations Over Time

Authors

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,268 Finding Related Tables in Data Lakes for Interactive Data Science 2020 SIGMOD 0.00011243615
3,319 FedKNN: Secure Federated k-Nearest Neighbor Search 2024 SIGMOD 7.4141554e-05
3,366 Connected Substructure Similarity Search 2010 SIGMOD 7.3548555e-05
3,508 COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks 2015 SIGMOD 7.2281243e-05
3,582 A Partition-Based Approach to Structure Similarity Search 2014 VLDB 7.1715746e-05
3,612 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 7.1436297e-05
4,012 TaGSim: Type-aware Graph Similarity Learning and Computation 2022 VLDB 6.8419352e-05
5,311 How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach 2015 SIGMOD 6.1703949e-05
5,467 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 6.1037173e-05
6,043 Answering Top-k Representative Queries on Graph Databases 2014 SIGMOD 5.8889868e-05
7,226 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 5.5651409e-05
8,257 Computing Approximate Graph Edit Distance via Optimal Transport 2025 SIGMOD 5.3519906e-05
9,268 Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond 2025 VLDB 5.1860131e-05
9,601 S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics 2025 VLDB 5.1376962e-05
9,825 On-the-Fly Token Similarity Joins in Relational Databases 2014 SIGMOD 5.1084057e-05
9,884 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.1037285e-05
11,255 Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods 2025 SIGMOD 4.9605343e-05
12,365 NED: An Inter-Graph Node Metric Based On Edit Distance 2017 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

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.00026634326
195 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00025589066
272 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00022559588
294 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021884041
331 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00020800828
734 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00014334121
1,218 A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures 2003 VLDB 0.00011456626
2,387 Towards Graph Containment Search and Indexing 2007 VLDB 8.5236741e-05
3,118 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.6114853e-05
4,679 Approximate Matching of Hierarchical Data Using pq-Grams 2005 VLDB 6.4567077e-05
7,717 An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data 2006 VLDB 5.4545945e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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