Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices

Abstract

We consider two closely related problems: planted clustering and submatrix localization. The planted clustering problem assumes that a random graph is generated based on some underlying clusters of the nodes; the task is to recover these clusters given the graph. The submatrix localization problem concerns locating hidden submatrices with elevated means inside a large real-valued random matrix. Of particular interest is the setting where the number of clusters/submatrices is allowed to grow unbounded with the problem size. These formulations cover several classical models such as planted clique, planted densest subgraph, planted partition, planted coloring, and stochastic block model, which are widely used for studying community detection and clustering/bi-clustering. For both problems, we show that the space of the model parameters (cluster/submatrix size, cluster density, and submatrix mean) can be partitioned into four disjoint regions corresponding to decreasing statistical and computational complexities: (1) the \emph{impossible} regime, where all algorithms fail; (2) the \emph{hard} regime, where the computationally expensive Maximum Likelihood Estimator (MLE) succeeds; (3) the \emph{easy} regime, where the polynomial-time convexified MLE succeeds; (4) the \emph{simple} regime, where a simple counting/thresholding procedure succeeds. Moreover, we show that each of these algorithms provably fails in the previous harder regimes. Our theorems establish the minimax recovery limit, which are tight up to constants and hold with a growing number of clusters/submatrices, and provide a stronger performance guarantee than previously known for polynomial-time algorithms. Our study demonstrates the tradeoffs between statistical and computational considerations, and suggests that the minimax recovery limit may not be achievable by polynomial-time algorithms.

We updated the statements for Theorems 2.1 and 2.3. Partial results appeared at the International Conference on Machine Learning (ICML) 2014

References in corpus (5)

• Graph spectra and the detectability of community structure in networks
• Finding large average submatrices in high dimensional data
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Breaking the Small Cluster Barrier of Graph Clustering

Cited by in corpus (69)

• Evaluating Overfit and Underfit in Models of Network Community Structure
• Mutual Information in Rank-One Matrix Estimation
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms
• Statistical and computational trade-offs in estimation of sparse principal components
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• A Spectral Framework for Anomalous Subgraph Detection
• A Survey on Theoretical Advances of Community Detection in Networks
• Computational Barriers to Estimation from Low-Degree Polynomials
• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Two-Sample Tests for Large Random Graphs Using Network Statistics
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Density Evolution in the Degree-correlated Stochastic Block Model
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Semidefinite Programs for Exact Recovery of a Hidden Community
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• Community Recovery in Graphs with Locality
• Average-case Hardness of RIP Certification
• Submatrix localization via message passing
• Scalable and Robust Community Detection with Randomized Sketching
• The Overlap Gap Property in Principal Submatrix Recovery
• PECOK: a convex optimization approach to variable clustering
• Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method
• A class of network models recoverable by spectral clustering
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
• Universality of Computational Lower Bounds for Submatrix Detection
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• Hierarchical community detection by recursive partitioning
• Covariate Regularized Community Detection in Sparse Graphs
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Sharp Computational-Statistical Phase Transitions via Oracle Computational Model
• Information Limits for Recovering a Hidden Community
• Optimal link prediction with matrix logistic regression
• Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E|{\log }^{\ast }|V|)$ Time
• Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models
• Lattice partition recovery with dyadic CART
• Tensor SVD: Statistical and Computational Limits
• Statistical Limits of Convex Relaxations
• Exact recovery and sharp thresholds of Stochastic Ising Block Model
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• Community Detection in the Stochastic Block Model by Mixed Integer Programming
• A Time-Varying Network for Cryptocurrencies
• A Multiscale Scan Statistic for Adaptive Submatrix Localization
• Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
• Non-Convex Exact Community Recovery in Stochastic Block Model
• A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits
• Partial recovery bounds for clustering with the relaxed $K$means
• Pair-Matching: Links Prediction with Adaptive Queries
• Statistical and Computational Tradeoff in Genetic Algorithm-Based Estimation
• Distribution-Free, Size Adaptive Submatrix Detection with Acceleration
• Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm
• Distribution free optimality intervals for clustering
• Random Subgraph Detection Using Queries
• Compressed spectral screening for large-scale differential correlation analysis with application in selecting Glioblastoma gene modules
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature
• EXIT Analysis for Community Detection
• Algorithms for an Efficient Tensor Biclustering
• Distribution-free Detection of a Submatrix
• Logspace Reducibility From Secret Leakage Planted Clique