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: 10522
Venue: VLDB
Year: 2012
Pagerank: 6.673504e-05
Overall Rank: 3,873 | 73.09%
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
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
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
5,017	Event Pattern Matching over Graph Streams	2015	VLDB	5.7505967e-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,886	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	4.2580321e-05
10,700	Fused Gromov-Wasserstein Alignment for Graph Edit Distance Computation and Beyond	2025	VLDB	4.1905499e-05
11,266	Approximating Probabilistic Group Steiner Trees in Graphs	2023	VLDB	4.1905499e-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
202	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034881375
415	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00023774838
576	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00019858777
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
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
949	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.0001510288
1,159	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00013584223
1,448	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011928845
2,564	Foundations of Probabilistic Answers to Queries	2005	SIGMOD	8.5325119e-05
4,959	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.7992713e-05
8,762	Efficient Query Answering in Probabilistic RDF Graphs	2011	SIGMOD	4.4520434e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
576	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00019858777
1,630	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011073047
6,165	An In-Depth Comparison of s-t Reliability Algorithms over Uncertain Graphs	2019	VLDB	5.1731827e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
2,524	Connected Substructure Similarity Search	2010	SIGMOD	8.5993622e-05
6,436	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0554554e-05
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
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
4,959	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.7992713e-05