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

arXiv: https://arxiv.org/abs/1402.1267 · HTML: https://mlsanity.com/paper/1402.1267/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2014.

## Built on by (most cited first, 29 of 29)

- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Community Detection in the Stochastic Block Model by Mixed Integer Programming](https://mlsanity.com/paper/2101.12336/) (2021)
- [Is it easier to count communities than find them?](https://mlsanity.com/paper/2212.10872/) (2022)
- [Phase Transition for Stochastic Block Model with more than √n Communities (II)](https://mlsanity.com/paper/2511.21526/) (2025)
- [Semidefinite Programming for Community Detection with Side Information](https://mlsanity.com/paper/2105.02816/) (2021)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [Phase Transition for Stochastic Block Model with more than √n Communities](https://mlsanity.com/paper/2509.15822/) (2025)
- [Community Detection: Exact Recovery in Weighted Graphs](https://mlsanity.com/paper/2102.04439/) (2021)
- [A class of network models recoverable by spectral clustering](https://mlsanity.com/paper/2104.10347/) (2021)
- [Lattice partition recovery with dyadic CART](https://mlsanity.com/paper/2105.13504/) (2021)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [A Worker-Task Specialization Model for Crowdsourcing: Efficient Inference and Fundamental Limits](https://mlsanity.com/paper/2111.12550/) (2021)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [A pseudo-likelihood approach to community detection in weighted networks](https://mlsanity.com/paper/2303.05909/) (2023)
- [Bounded Projection Matrix Approximation with Applications to Community Detection](https://mlsanity.com/paper/2305.15430/) (2023)
- [Implications of sparsity and high triangle density for graph representation learning](https://mlsanity.com/paper/2210.15277/) (2022)
- [Community Detection with Known, Unknown, or Partially Known Auxiliary Latent Variables](https://mlsanity.com/paper/2301.04088/) (2023)
- [Phase transition for detecting a small community in a large network](https://mlsanity.com/paper/2303.05024/) (2023)
- [Optimal community detection in dense bipartite graphs](https://mlsanity.com/paper/2505.18372/) (2025)
- [A Goodness-of-fit Test on the Number of Biclusters in a Relational Data Matrix](https://mlsanity.com/paper/2102.11658/) (2021)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)
- [Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold](https://mlsanity.com/paper/2205.11677/) (2022)
- [Spatio-temporal Value Semantics-based Abstraction for Dense Deep Reinforcement Learning](https://mlsanity.com/paper/2405.15829/) (2024)
- [Regularized Projection Matrix Approximation with Applications to Community Detection](https://mlsanity.com/paper/2405.16598/) (2024)
- [Robust Detection of Planted Subgraphs in Semi-Random Models](https://mlsanity.com/paper/2508.02158/) (2025)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)
- [Flexible Online Representation Learning Based on Similarity Matching](https://mlsanity.com/paper/2606.01546/) (2026)

## Abstract (arXiv)

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 impossible regime, where all algorithms fail; (2) the hard regime, where the computationally expensive Maximum Likelihood Estimator (MLE) succeeds; (3) the easy regime, where the polynomial-time convexified MLE succeeds; (4) the 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.