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.3093118e-05
Overall Rank: 4,997 | 66.51%
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
440	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018235529
3,612	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.1436297e-05
3,644	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	7.1224321e-05
3,826	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	6.9787375e-05
5,311	How to Build Templates for RDF Question/Answering —An Uncertain Graph Similarity Join Approach	2015	SIGMOD	6.1703949e-05
6,180	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.8425819e-05
9,884	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1037285e-05
10,371	QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes	2025	VLDB	5.0010514e-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.00026634326
439	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018247958
590	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00015876538
1,069	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012164865
2,387	Towards Graph Containment Search and Indexing	2007	VLDB	8.5236741e-05
2,567	Foundations of Probabilistic Answers to Queries	2005	SIGMOD	8.266408e-05
2,627	ProTDB: Probabilistic Data in XML	2002	VLDB	8.1909465e-05
3,390	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.3292374e-05
7,080	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.5901209e-05

Semantically Similar Papers

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