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: h17ccecb83c055597
Venue: VLDB
Year: 2020
Pagerank: 5.1230858e-05
Overall Rank: 9,840 | 33.85%
DOI: 10.14778/3401960.3401964

Incoming Non-self Citations Over Time

Authors

1. Shubhangi Agarwal (Indian Institute of Technology)
2. Sourav Dutta (Huawei Research Centre)
3. Arnab Bhattacharya (Indian Institute of Technology)

BibTeX Citation

@article{agarwal_vldb20,
        title = {{ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs}},
        author = {Agarwal, Shubhangi and Dutta, Sourav and Bhattacharya, Arnab},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {10},
        pages = {1654--1668},
        doi = {10.14778/3401960.3401964},
        url = {https://doi.org/10.14778/3401960.3401964},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,452	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1745448e-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
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020765078
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020124083
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018286607
601	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00015732701
1,063	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012208695
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011898162
1,244	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011353487
1,260	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011296964
1,414	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.0001073756
2,235	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7779518e-05
2,376	Towards Graph Containment Search and Indexing	2007	VLDB	8.5543073e-05
3,036	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.731521e-05
3,499	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	7.2549774e-05
3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.1706333e-05
3,820	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	7.005206e-05
4,969	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.3332415e-05
5,096	Querying Graph Patterns	2011	PODS	6.2743507e-05
5,478	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	6.1142386e-05
6,161	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.8647415e-05
7,357	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.5432592e-05
8,257	Mining Statistically Significant Substrings using the Chi-Square Statistic	2012	VLDB	5.3674031e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,585	Breaking Structural Isolation: Scalable Graph Clustering via Community-Aware Sampling and Structural Entropy	2026	VLDB
2	4,303	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
3	11,985	Structural Generalizability: The Case of Similarity Search	2021	SIGMOD
4	5,477	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
5	1,400	Scalable Similarity Search for SimRank	2014	SIGMOD
6	1,100	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD
7	3,369	Connected Substructure Similarity Search	2010	SIGMOD
8	4,969	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
9	7,357	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD
10	3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB