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: 4779
Venue: SIGMOD
Year: 2014
Pagerank: 5.005963e-05
Overall Rank: 6,572 | 54.29%
DOI: 10.1145/2588555.2588574

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,974	ROLL: Fast In-Memory Generation of Gigantic Scale-free Networks	2016	SIGMOD	4.8780906e-05
9,575	GARUDA: A System for Large-Scale Mining of Statistically Significant Connected Subgraphs	2016	VLDB	4.325244e-05
9,580	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	4.3234342e-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
1,747	Mining Significant Graph Patterns by Leap Search	2008	SIGMOD	0.00010691242
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
2,909	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9305767e-05
2,807	A Model-based Approach to Attributed Graph Clustering	2012	SIGMOD	8.0905959e-05
313	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00028097557
10,535	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	4.1945683e-05
10,681	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.1945683e-05
8,210	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	4.5581054e-05
3,480	CSV: Visualizing and Mining Cohesive Subgraphs	2008	SIGMOD	7.0538737e-05
7,737	Mining Statistically Significant Substrings using the Chi-Square Statistic	2012	VLDB	4.6642145e-05
7,614	Mining Attribute-structure Correlated Patterns in Large Attributed Graphs	2012	VLDB	4.6947636e-05
9,580	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	4.3234342e-05