  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.
