ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs

Summary: ChiSeL enables subgraph similarity search in large probabilistic graphs via chi-square scores for candidate vertex matches. Greedy expansion prioritizes high chi-square matches, handling edge, label, and vertex uncertainty; validated on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12071
Venue: VLDB
Year: 2020
Pagerank: 4.3273374e-05
Overall Rank: 9,523 | 33.82%
DOI: 10.14778/3401960.3401964

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,135	Sage: A System for Uncertain Network Analysis	2022	VLDB	4.3846727e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
351	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026351742
502	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021528261
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
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,444	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011941836
1,448	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011928845
1,848	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010331574
2,432	Towards Graph Containment Search and Indexing	2007	VLDB	8.8247178e-05
2,557	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5484449e-05
3,106	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.5550946e-05
3,707	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	6.8223857e-05
3,873	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	6.673504e-05
4,165	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	6.3843974e-05
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
4,959	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.7992713e-05
5,158	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	5.6510256e-05
6,373	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.0875991e-05
6,571	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.0014639e-05
7,736	Mining Statistically Significant Substrings using the Chi-Square Statistic	2012	VLDB	4.6597633e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,373	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.0875991e-05
4,760	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9342555e-05
11,484	Structural Generalizability: The Case of Similarity Search	2021	SIGMOD	4.1905499e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
1,542	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00011447877
1,715	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010776518
2,524	Connected Substructure Similarity Search	2010	SIGMOD	8.5993622e-05
4,959	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.7992713e-05
6,571	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.0014639e-05
3,873	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	6.673504e-05