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
9910
Venue
VLDB
Year
2009
Pagerank
0.00015106325
Overall Rank
951 | 93.39%
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,644 Finding Related Tables in Data Lakes for Interactive Data Science 2020 SIGMOD 0.00011041787
2,525 Connected Substructure Similarity Search 2010 SIGMOD 8.5981082e-05
2,996 FedKNN: Secure Federated k-Nearest Neighbor Search 2024 SIGMOD 7.7586458e-05
3,849 TaGSim: Type-aware Graph Similarity Learning and Computation 2022 VLDB 6.7064042e-05
3,862 A Partition-Based Approach to Structure Similarity Search 2014 VLDB 6.687769e-05
3,873 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB 6.6779082e-05
3,987 COMMIT: A Scalable Approach to Mining Communication Motifs from Dynamic Networks 2015 SIGMOD 6.5605514e-05
4,328 How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach 2015 SIGMOD 6.2866586e-05
6,074 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 5.2242306e-05
6,080 Answering Top-k Representative Queries on Graph Databases 2014 SIGMOD 5.2214553e-05
6,839 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 4.9109527e-05
8,069 Computing Approximate Graph Edit Distance via Optimal Transport 2025 SIGMOD 4.5934204e-05
9,439 On-the-Fly Token Similarity Joins in Relational Databases 2014 SIGMOD 4.3423824e-05
9,580 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 4.3234342e-05
10,487 Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods 2025 SIGMOD 4.1945683e-05
10,692 Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond 2025 VLDB 4.1945683e-05
10,696 S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics 2025 VLDB 4.1945683e-05
11,818 NED: An Inter-Graph Node Metric Based On Edit Distance 2017 VLDB 4.1945683e-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
171 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038830709
203 Graph Indexing: A Frequent Structure-based Approach 2004 SIGMOD 0.00034889335
301 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00028370644
334 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00027081079
336 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00027020919
753 A Platform Based on the Multi-dimensional Data Model for Analysis of Bio-Molecular Structures 2003 VLDB 0.0001719168
900 Graph Indexing: Tree + Delta >= Graph 2007 VLDB 0.00015495155
2,438 Towards Graph Containment Search and Indexing 2007 VLDB 8.8214248e-05
3,199 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3927291e-05
4,406 Approximate Matching of Hierarchical Data Using pq-Grams 2005 VLDB 6.2141638e-05
6,732 An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data 2006 VLDB 4.9477058e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
919 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00015343179
7,708 Efficient Top-k Algorithms for Approximate Substring Matching 2013 SIGMOD 4.6721808e-05
11,818 NED: An Inter-Graph Node Metric Based On Edit Distance 2017 VLDB 4.1945683e-05
10,692 Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond 2025 VLDB 4.1945683e-05
3,862 A Partition-Based Approach to Structure Similarity Search 2014 VLDB 6.687769e-05
3,199 Similarity Evaluation on Tree-structured Data 2005 SIGMOD 7.3927291e-05
3,752 Computing Graph Edit Distance via Neural Graph Matching 2023 VLDB 6.7879009e-05
10,487 Graph Edit Distance Estimation: A New Heuristic and A Holistic Evaluation of Learning-based Methods 2025 SIGMOD 4.1945683e-05
11,559 Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees 2020 SIGMOD 4.1945683e-05
6,839 Boosting Graph Similarity Search through Pre-Computation 2021 SIGMOD 4.9109527e-05