Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs

Summary: Mining statistically significant connected subgraphs in vertex-labeled graphs via chi-square; supports discrete and multi-dimensional continuous labels. Edge contraction creates a super-graph to prune the search; dense graphs yield few super-vertices, sparse graphs trade accuracy for speed, achieving ~96% of optimal chi-square and scalable on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb48d668f6e2fd05d
Venue: SIGMOD
Year: 2014
Pagerank: 5.5432592e-05
Overall Rank: 7,357 | 50.54%
DOI: 10.1145/2588555.2588574

Incoming Non-self Citations Over Time

Authors

1. Akhil Arora (Indian Institute of Technology Kanpur)
2. Mayank Sachan (Indian Institute of Technology Kanpur)
3. Arnab Bhattacharya (Indian Institute of Technology Kanpur)

BibTeX Citation

@inproceedings{arora_sigmod14,
        title = {{Mining Statistically Significant Connected Subgraphs in Vertex Labeled Graphs}},
        author = {Arora, Akhil and Sachan, Mayank and Bhattacharya, Arnab},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2588555.2588574},
        url = {https://dl.acm.org/doi/10.1145/2588555.2588574},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,939	ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks	2016	SIGMOD	5.6391078e-05
9,840	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1230858e-05
9,860	GARUDA: A System for Large-Scale Mining of Statistically Significant Connected Subgraphs	2016	VLDB	5.1178924e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2,010	Mining Significant Graph Patterns by Leap Search	2008	SIGMOD	9.1914756e-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	2,042	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB
2	2,692	A Model-based Approach to Attributed Graph Clustering	2012	SIGMOD
3	375	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB
4	11,220	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB
5	11,321	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB
6	8,342	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB
7	3,902	CSV: Visualizing and Mining Cohesive Subgraphs	2008	SIGMOD
8	8,257	Mining Statistically Significant Substrings using the Chi-Square Statistic	2012	VLDB
9	7,606	Mining Attribute-structure Correlated Patterns in Large Attributed Graphs	2012	VLDB
10	9,840	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB