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.1206606e-05
Overall Rank: 9,847 | 33.82%
DOI: 10.14778/3401960.3401964
PDF: Download (CC BY-NC-ND 4.0)

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,461	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1720952e-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.00020756016
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020116134
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018278591
601	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00015725619
1,064	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012202916
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011892544
1,247	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011348258
1,261	Distance-Constraint Reachability Computation in Uncertain Graphs	2011	VLDB	0.00011291616
1,414	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010732477
2,238	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7738068e-05
2,377	Towards Graph Containment Search and Indexing	2007	VLDB	8.5503022e-05
3,037	Injecting Uncertainty in Graphs for Identity Obfuscation	2012	VLDB	7.727861e-05
3,499	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	7.2515431e-05
3,604	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB	7.1672388e-05
3,821	The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs	2014	SIGMOD	7.0018898e-05
4,971	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	6.3302434e-05
5,099	Querying Graph Patterns	2011	PODS	6.2713809e-05
5,483	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	6.1113443e-05
6,164	On Uncertain Graphs Modeling and Queries	2015	VLDB	5.8619652e-05
7,361	Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs	2014	SIGMOD	5.5406351e-05
8,263	Mining Statistically Significant Substrings using the Chi-Square Statistic	2012	VLDB	5.3648648e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,591	Breaking Structural Isolation: Scalable Graph Clustering via Community-Aware Sampling and Structural Entropy	2026	VLDB
2	4,304	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
3	11,991	Structural Generalizability: The Case of Similarity Search	2021	SIGMOD
4	5,481	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,971	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
9	7,361	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