Efficient Subgraph Search over Large Uncertain Graphs
Summary: Subgraph search on large uncertain graphs with possible-world semantics. A #P-complete problem is tackled with filtering via a probabilistic inverted index (PIndex) over optimally selected subgraph features, plus exact/bound verification and experiments. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Ye Yuan
- 2. Guoren Wang
- 3. Haixun Wang
- 4. Lei Chen
Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 651 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB | 0.00018648572 |
| 3,636 | Efficient and Effective Algorithms for Clustering Uncertain Graphs | 2019 | VLDB | 6.8976555e-05 |
| 3,873 | Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases | 2012 | VLDB | 6.6779082e-05 |
| 4,179 | The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs | 2014 | SIGMOD | 6.3800553e-05 |
| 4,328 | How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach | 2015 | SIGMOD | 6.2866586e-05 |
| 6,393 | On Uncertain Graphs Modeling and Queries | 2015 | VLDB | 5.0837624e-05 |
| 9,580 | ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs | 2020 | VLDB | 4.3234342e-05 |
| 9,961 | QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes | 2025 | VLDB | 4.2294678e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 203 | Graph Indexing: A Frequent Structure-based Approach | 2004 | SIGMOD | 0.00034889335 |
| 612 | Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism | 2008 | VLDB | 0.0001920234 |
| 627 | Management of Probabilistic Data: Foundations and Challenges | 2007 | PODS | 0.00018959005 |
| 1,162 | k-Nearest Neighbors in Uncertain Graphs | 2010 | VLDB | 0.0001358105 |
| 2,438 | Towards Graph Containment Search and Indexing | 2007 | VLDB | 8.8214248e-05 |
| 2,560 | Foundations of Probabilistic Answers to Queries | 2005 | SIGMOD | 8.5402003e-05 |
| 2,774 | ProTDB: Probabilistic Data in XML | 2002 | VLDB | 8.134432e-05 |
| 3,589 | On the Complexity of Managing Probabilistic XML Data | 2007 | PODS | 6.9427709e-05 |
| 6,681 | Query Efficiency in Probabilistic XML Models | 2008 | SIGMOD | 4.9643102e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,862 | A Partition-Based Approach to Structure Similarity Search | 2014 | VLDB | 6.687769e-05 |
| 651 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB | 0.00018648572 |
| 6,393 | On Uncertain Graphs Modeling and Queries | 2015 | VLDB | 5.0837624e-05 |
| 10,696 | S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics | 2025 | VLDB | 4.1945683e-05 |
| 8,765 | Efficient Query Answering in Probabilistic RDF Graphs | 2011 | SIGMOD | 4.456315e-05 |
| 5,854 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD | 5.3006473e-05 |
| 6,406 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.0765917e-05 |
| 572 | Substructure Similarity Search in Graph Databases | 2005 | SIGMOD | 0.00019887011 |
| 2,525 | Connected Substructure Similarity Search | 2010 | SIGMOD | 8.5981082e-05 |
| 3,873 | Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases | 2012 | VLDB | 6.6779082e-05 |