Database Paper Browser

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
9911
Venue
VLDB
Year
2009
Pagerank
0.0001510288
Overall Rank
949 | 93.41%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank Citing Paper Year Venue Pagerank
1,643 Finding Related Tables in Data Lakes for Interactive Data Science 2020 SIGMOD 0.00011031534
2,524 Connected Substructure Similarity Search 2010 SIGMOD 8.5993622e-05
2,997 FedKNN: Secure Federated k-Nearest Neighbor Search 2024 SIGMOD 7.7569625e-05
3,851 TaGSim: Type-aware Graph Similarity Learning and Computation 2022 VLDB 6.6999444e-05
3,864 A Partition-Based Approach to Structure Similarity Search 2014 VLDB 6.6813849e-05
3,873 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 6.673504e-05
3,950 COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks 2015 SIGMOD 6.5925643e-05
4,323 How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach 2015 SIGMOD 6.281058e-05
6,080 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 5.219249e-05
6,085 Answering Top-k Representative Queries on Graph Databases 2014 SIGMOD 5.2165029e-05
6,835 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 4.9065543e-05
8,072 Computing Approximate Graph Edit Distance via Optimal Transport 2025 SIGMOD 4.5890162e-05
9,444 On-the-Fly Token Similarity Joins in Relational Databases 2014 SIGMOD 4.3382418e-05
9,523 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 4.3273374e-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,704 S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics 2025 VLDB 4.1905499e-05
11,826 NED: An Inter-Graph Node Metric Based On Edit Distance 2017 VLDB 4.1905499e-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
172 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038837872
202 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00034881375
302 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00028343691
334 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00027077424
337 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00027002505
750 A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures 2003 VLDB 0.0001718364
895 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015498104
2,432 Towards Graph Containment Search and Indexing 2007 VLDB 8.8247178e-05
3,206 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3855924e-05
4,402 Approximate Matching of Hierarchical Data Using pq-Grams 2005 VLDB 6.2086707e-05
6,734 An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data 2006 VLDB 4.9434384e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
916 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015326675
7,707 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6676985e-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
3,864 A Partition-Based Approach to Structure Similarity Search 2014 VLDB 6.6813849e-05
3,206 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3855924e-05
3,756 Computing Graph Edit Distance via Neural Graph Matching 2023 VLDB 6.781373e-05
10,497 Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods 2025 SIGMOD 4.1905499e-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