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 |
|---|---|---|---|---|
| 648 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB | 0.00018688754 |
| 3,622 | Efficient and Effective Algorithms for Clustering Uncertain Graphs | 2019 | VLDB | 6.9021704e-05 |
| 3,873 | Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases | 2012 | VLDB | 6.673504e-05 |
| 4,165 | The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs | 2014 | SIGMOD | 6.3843974e-05 |
| 4,323 | How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach | 2015 | SIGMOD | 6.281058e-05 |
| 6,373 | On Uncertain Graphs Modeling and Queries | 2015 | VLDB | 5.0875991e-05 |
| 9,523 | ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs | 2020 | VLDB | 4.3273374e-05 |
| 9,960 | QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes | 2025 | VLDB | 4.2254157e-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 |
|---|---|---|---|---|
| 202 | Graph Indexing: A Frequent Structure-based Approach | 2004 | SIGMOD | 0.00034881375 |
| 616 | Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism | 2008 | VLDB | 0.00019068362 |
| 630 | Management of Probabilistic Data: Foundations and Challenges | 2007 | PODS | 0.00018942778 |
| 1,159 | k-Nearest Neighbors in Uncertain Graphs | 2010 | VLDB | 0.00013584223 |
| 2,432 | Towards Graph Containment Search and Indexing | 2007 | VLDB | 8.8247178e-05 |
| 2,564 | Foundations of Probabilistic Answers to Queries | 2005 | SIGMOD | 8.5325119e-05 |
| 2,783 | ProTDB: Probabilistic Data in XML | 2002 | VLDB | 8.1268718e-05 |
| 3,592 | On the Complexity of Managing Probabilistic XML Data | 2007 | PODS | 6.9362111e-05 |
| 6,682 | Query Efficiency in Probabilistic XML Models | 2008 | SIGMOD | 4.9596732e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,864 | A Partition-Based Approach to Structure Similarity Search | 2014 | VLDB | 6.6813849e-05 |
| 648 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB | 0.00018688754 |
| 6,373 | On Uncertain Graphs Modeling and Queries | 2015 | VLDB | 5.0875991e-05 |
| 10,704 | S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics | 2025 | VLDB | 4.1905499e-05 |
| 8,762 | Efficient Query Answering in Probabilistic RDF Graphs | 2011 | SIGMOD | 4.4520434e-05 |
| 5,903 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD | 5.2757528e-05 |
| 6,386 | Mining and Indexing Graphs for Supergraph Search | 2013 | VLDB | 5.0820608e-05 |
| 576 | Substructure Similarity Search in Graph Databases | 2005 | SIGMOD | 0.00019858777 |
| 2,524 | Connected Substructure Similarity Search | 2010 | SIGMOD | 8.5993622e-05 |
| 3,873 | Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases | 2012 | VLDB | 6.673504e-05 |