Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases

Summary: Subgraph similarity search in large probabilistic graphs with correlated edges; #P-complete. Filter-and-verify with PMI to bound subgraph isomorphism probability; tight lower/upper bounds; efficient verification via sampling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10521
Venue: VLDB
Year: 2012
Pagerank: 6.6779082e-05
Overall Rank: 3,873 | 73.06%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 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
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
5,031	Event Pattern Matching over Graph Streams	2015	VLDB	5.7499783e-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,887	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	4.2621158e-05
10,692	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	4.1945683e-05
11,264	Approximating Probabilistic Group Steiner Trees in Graphs	2023	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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
417	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00023794574
572	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00019887011
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
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
951	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00015106325
1,162	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.0001358105
1,450	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011925844
2,560	Foundations of Probabilistic Answers to Queries	2005	SIGMOD	8.5402003e-05
4,958	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.8031038e-05
8,765	Efficient Query Answering in Probabilistic RDF Graphs	2011	SIGMOD	4.456315e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
572	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00019887011
1,635	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001105793
6,172	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB	5.170101e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
2,525	Connected Substructure Similarity Search	2010	SIGMOD	8.5981082e-05
6,441	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0603113e-05
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
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
4,958	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.8031038e-05