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: 12070
Venue: VLDB
Year: 2020
Pagerank: 4.3234342e-05
Overall Rank: 9,580 | 33.36%
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.3888791e-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
350	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026365067
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362
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
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
1,454	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011913289
1,844	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010341077
2,438	Towards Graph Containment Search and Indexing	2007	VLDB	8.8214248e-05
2,551	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5572574e-05
3,101	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.5598015e-05
3,720	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	6.8192237e-05
3,873	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	6.6779082e-05
4,179	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	6.3800553e-05
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
4,958	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.8031038e-05
5,159	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	5.6587631e-05
6,393	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.0837624e-05
6,572	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.005963e-05
7,737	Mining Statistically Significant Substrings using the Chi-Square Statistic	2012	VLDB	4.6642145e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,393	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.0837624e-05
4,791	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9188595e-05
11,480	Structural Generalizability: The Case of Similarity Search	2021	SIGMOD	4.1945683e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
1,539	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00011460415
1,775	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010602927
2,525	Connected Substructure Similarity Search	2010	SIGMOD	8.5981082e-05
4,958	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.8031038e-05
6,572	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.005963e-05
3,873	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	6.6779082e-05