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: 10507
Venue: VLDB
Year: 2011
Pagerank: 6.4780097e-05
Overall Rank: 4,853 | 66.71%
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
442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018398144
3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.3214417e-05
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
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,109	QueryArtisan: Generating Data Manipulation Codes for Ad-hoc Analysis in Data Lakes	2025	VLDB	5.1347137e-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
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
431	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018577017
574	Management of Probabilistic Data: Foundations and Challenges	2007	PODS	0.00016278855
1,049	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012415522
2,328	Towards Graph Containment Search and Indexing	2007	VLDB	8.745748e-05
2,509	Foundations of Probabilistic Answers to Queries	2005	SIGMOD	8.4857765e-05
2,569	ProTDB: Probabilistic Data in XML	2002	VLDB	8.4090027e-05
3,318	On the Complexity of Managing Probabilistic XML Data	2007	PODS	7.5247776e-05
6,917	Query Efficiency in Probabilistic XML Models	2008	SIGMOD	5.7400564e-05

Semantically Similar Papers

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