DBScholar

Back to papers

Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases

Summary: Targets subgraph similarity search in large probabilistic graphs with correlated edge occurrences, proving the problem #P-complete. A PMI-based filter derives tight probability bounds for pruning, followed by efficient sampling-based verification. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
10709
Venue
VLDB
Year
2012
Pagerank
7.3214417e-05
Overall Rank
3,548 | 75.66%
DOI
10.14778/2311906.2311908

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{yuan_vldb12,
        title = {{Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases}},
        author = {Yuan, Ye and Wang, Guoren and Chen, Lei and Wang, Haixun},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {9},
        pages = {800--811},
        doi = {10.14778/2311906.2311908},
        url = {https://doi.org/10.14778/2311906.2311908},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank Citing Paper Year Venue Pagerank
442 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018398144
3,559 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 7.3095916e-05
3,738 The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs 2014 SIGMOD 7.1602939e-05
4,503 Event Pattern Matching over Graph Streams 2015 VLDB 6.6597953e-05
5,168 How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach 2015 SIGMOD 6.3353772e-05
6,037 On Uncertain Graphs Modeling and Queries 2015 VLDB 5.9990983e-05
9,665 ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs 2020 VLDB 5.2406724e-05
10,037 Graph Exploration: From Users to Large Graphs 2017 SIGMOD 5.1729561e-05
10,939 Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond 2025 VLDB 5.093636e-05
11,463 Approximating Probabilistic Group Steiner Trees in Graphs 2023 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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
366 Scalable Semantic Web Data Management Using Vertical Partitioning 2007 VLDB 0.00020039981
431 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018577017
442 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018398144
574 Management of Probabilistic Data: Foundations and Challenges 2007 PODS 0.00016278855
591 Substructure Similarity Search in Graph Databases 2005 SIGMOD 0.0001603683
1,049 k-Nearest Neighbors in Uncertain Graphs 2010 VLDB 0.00012415522
1,115 Comparing Stars: On Approximating Graph Edit Distance 2009 VLDB 0.00012117375
1,254 Distance-Constraint Reachability Computation in Uncertain Graphs 2011 VLDB 0.0001147266
2,509 Foundations of Probabilistic Answers to Queries 2005 SIGMOD 8.4857765e-05
4,853 Efficient Subgraph Search over Large Uncertain Graphs 2011 VLDB 6.4780097e-05
8,935 Efficient Query Answering in Probabilistic RDF Graphs 2011 SIGMOD 5.3483178e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 591 Substructure Similarity Search in Graph Databases 2005 SIGMOD
2 1,181 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB
3 5,890 An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs 2019 VLDB
4 5,370 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD
5 3,311 Connected Substructure Similarity Search 2010 SIGMOD
6 6,149 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB
7 442 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB
8 9,383 S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics 2025 VLDB
9 8,935 Efficient Query Answering in Probabilistic RDF Graphs 2011 SIGMOD
10 4,853 Efficient Subgraph Search over Large Uncertain Graphs 2011 VLDB