Efficient Subgraph Search over Large Uncertain Graphs

Summary: Studies threshold-based probabilistic subgraph search under possible-world semantics in large uncertain graph databases, proving the task #P-complete. Combines an optimally selected-feature probabilistic inverted index (PIndex) with exact and bound verification for practical search. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h4ec58d381423e494
Venue: VLDB
Year: 2011
Pagerank: 6.3332415e-05
Overall Rank: 4,969 | 66.60%
DOI: 10.14778/1920841.1920952

Incoming Non-self Citations Over Time

Authors

1. Ye Yuan (Northeastern University)
2. Guoren Wang (Northeastern University; Wuhan University)
3. Haixun Wang (Microsoft)
4. Lei Chen (Hong Kong University of Science and Technology)

BibTeX Citation

@article{yuan_vldb11,
        title = {{Efficient Subgraph Search over Large Uncertain Graphs}},
        author = {Yuan, Ye and Wang, Guoren and Wang, Haixun and Chen, Lei},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {3},
        number = {1},
        pages = {876--887},
        doi = {10.14778/1920841.1920952},
        url = {https://doi.org/10.14778/1920841.1920952},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018197688
3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.1706333e-05
3,632	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	7.1494448e-05
3,820	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	7.005206e-05
5,290	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.1937978e-05
6,161	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.8647415e-05
9,840	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1230858e-05
10,337	QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes	2025	VLDB	5.0200193e-05

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
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018286607
587	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015933201
1,063	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012208695
2,376	Towards Graph Containment Search and Indexing	2007	VLDB	8.5543073e-05
2,562	Foundations of Probabilistic Answers to Queries	2005	SIGMOD	8.297533e-05
2,617	ProTDB: Probabilistic Data in XML	2002	VLDB	8.2219007e-05
3,378	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.3569859e-05
7,057	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.6113229e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,569	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
2	443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
3	6,161	On Uncertain Graphs Modeling and Queries	2015	VLDB
4	9,568	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB
5	9,097	Efficient Query Answering in Probabilistic RDF Graphs	2011	SIGMOD
6	5,477	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
7	6,642	Mining and Indexing Graphs for Supergraph Search	2013	VLDB
8	601	Substructure Similarity Search in Graph Databases	2005	SIGMOD
9	3,369	Connected Substructure Similarity Search	2010	SIGMOD
10	3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB