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

Introduction

In this paper we consider two closely related problems: planted clustering and submatrix localization, both concerning the recovery of hidden structures from a noisy random graph or matrix.

Planted Clustering: Suppose that out of a total of $n$ nodes, $rK$ of them are partitioned into $r$ clusters of size $K$, and the remaining $n-rK$ nodes do not belong to any clusters; each pair of nodes is connected by an edge with probability $p$ if they are in the same cluster, and with probability $q$ otherwise. Given the adjacency matrix $A$ of the graph, the goal is to recover the underlying clusters (up to a permutation of cluster indices). By varying the values of the model parameters, this formulation covers several classical models including planted clique, planted coloring, planted densest subgraph, planted partition, and stochastic block model (cf. Definition 1 and discussion thereafter).

We are particularly interested in the setting where the number $r$ of clusters or submatrices may grow unbounded with the problem dimensions $n$, $n_{L}$, and $n_{R}$ at an arbitrary rate. We may call this the high-rank setting because $r$ equals the rank of a matrix representation of the clusters and submatrices (cf. Definitions 1 and 2). The other parameters $K$, $p$, $q$, and $\mu$ are also allowed to scale with $n$ or $(n_{L},n_{R})$.

These two problems have been studied under various names such as community detection, graph clustering/bi-clustering, and reconstruction in stochastic block models, and have a broad range of applications. They are used as generative models for approximating real-world networks and data arrays with natural cluster/community structures, such as social networks , gene expressions , and online ratings . They serve as benchmarks in the evaluation of algorithms for clustering , bi-clustering , community detection , and other network inference problems. They also provide a venue for studying the average-case behaviors of many graph theoretic problems including max-clique, max-cut, graph partitioning, and coloring . The importance of these two problems are well-recognized in many areas across computer science, statistics, and physics .

The planted clustering and submatrix localization problems exhibit an interplay between statistical and computational considerations. From a statistical point of view, we are interested in identifying the range of the model parameters for which the hidden structures—in this case the clusters and submatrices—can be recovered from the noisy data $A$. The values of the parameters $n,r,K,p,q,\mu$ govern the statistical hardness of the problems: the problems become more difficult with smaller values of $p-q$, $\mu$, $K$, and larger $r$, because the observations are noisier and the sought-after structures are more complicated. A statistically powerful algorithm is one that can recover the hidden structures for a large region of the model parameter space.

From a computational point of view, we are concerned with the running time of different recovery algorithms. An exhaustive search over the solution space (i.e., all possible clusterings or locations of the submatrices) may make for a statistically powerful algorithm, but is computationally intractable. A simpler algorithm with lower running time is computationally more desirable, but may succeed only in a smaller region of the model parameter space and thus has weaker statistical power.

Therefore, it is important to take a joint statistical-computational view to the planted clustering and submatrix localization problems, and to understand the tradeoffs between these two considerations. How do algorithms with different computational complexity achieve different statistical performance? For these two problems, what is the information limit (under what conditions on the model parameters does recovery become infeasible for any algorithm), and what is the computational limit (when does it become infeasible for computationally tractable algorithms)?

The results on this paper sheds light on the above questions. For both problems, our results demonstrate, in a precise and quantitative way, the following phenomenon: The parameter space can be partitioned into four disjoint regions, such that each region corresponds to statistically easier instances of the problem than the previous one, and recovery can be achieved by simpler algorithms with lower running time. Significantly, there might exist a large gap between the statistical performance of computationally intractable algorithms and that of computationally efficient algorithms. We elaborate in the next two subsections.

For concreteness, we first consider the planted clustering problem in the setting $r\geq 2$, $p>q$ and $p/q=\Theta(1)$. This covers the standard planted bisection/partition/$r$-disjoint-clique models.

The statistical hardness of cluster recovery is captured by the quantity $\frac{(p-q)^{2}}{q(1-q)}$, which is essentially a measure of the Signal-to-Noise Ratio (SNR). Our main theorems identify the following four regimes of the problem defined by the value of this quantity. Here for simplicity, the results use the notation $\overset{\bm{.}}{\gtrsim}$ and $\overset{\bm{.}}{\lesssim}$, which ignore constant and $\log n$ factors; our main theorems do capture the $\log n$ factors.

The Impossible Regime: $\frac{(p-q)^{2}}{q(1-q)}\overset{\bm{.}}{\lesssim}\frac{1}{K}$. In this regime, there is no algorithm, regardless of its computational complexity, that can recover the clusters with a vanishing probability of error.

The Hard Regime: $\frac{1}{K}\overset{\bm{.}}{\lesssim}\frac{(p-q)^{2}}{q(1-q)}\overset{\bm{.}}{\lesssim}\frac{n}{K^{2}}$. There exists a computationally expensive algorithm—specifically the Maximum Likelihood Estimator (MLE)—that recovers the clusters with high probability in this regime (as well as in the next two easier regimes; we omit such implications in the sequel). There is no known polynomial-time algorithm that succeeds in this regime.

The Easy Regime: $\frac{n}{K^{2}}\overset{\bm{.}}{\lesssim}\frac{(p-q)^{2}}{q(1-q)}\overset{\bm{.}}{\lesssim}\frac{\sqrt{n}}{K}$. There exists a polynomial-time algorithm—specifically a convex relaxation of the MLE—that recovers the clusters with high probability in this regime. Moreover, this algorithm provably fails in the hard regime above.

The Simple Regime: $\frac{(p-q)^{2}}{q(1-q)}\overset{\bm{.}}{\gtrsim}\frac{\sqrt{n}}{K}$. A simple algorithm based on counting node degrees and common neighbors recovers the clusters with high probability in this regime, and provably fails outside this regime (i.e., in the hard and easy regimes).

We illustrate these four regimes in Figure 1 assuming the scaling $p=2q=\Theta(n^{-\alpha})$ and $K=\Theta(n^{\beta})$ for two constants $\alpha,\beta\in(0,1)$. Here cluster recovery becomes harder with larger $\alpha$ and smaller $\beta$. In this setting, the four regimes correspond to four disjoint and non-empty regions of the parameter space. Therefore, a computationally more expensive algorithm leads to an order-wise (polynomial in $n$) enhancement in the statistical power. For example, when $\alpha=1/4$, the simple, polynomial-time, and computationally intractable algorithms succeeds for $\beta$ larger than $0.75$, $0.625$, and $0.25$, respectively. There is a similar hierarchy for the allowable sparsity of the graph, given by $\alpha<0.25$, $\alpha<0.5$, and $\alpha<0.75$ assuming $\beta=0.75$.

The results in the impossible and hard regimes together establish the minimax recovery boundary of the planted clustering problem, and show that the MLE is statistically order-optimal. These two regimes are separated by an “information barrier”: in the impossible regime the graph does not carry enough information to distinguish different cluster structures, so recovery is statistically impossible.

Our performance guarantees for the convexified MLE improve the best known results for polynomial time algorithms in terms of the scaling, particularly in the setting when the number of clusters are allow to grow with $n$. We conjecture that no polynomial-time algorithm can perform significantly better and succeed in the hard regime, i.e., the convexified MLE achieves the computational limit order-wise. While we do not prove the conjecture, there are many supporting evidences; cf. Section 2.3. For instance, there is a “spectral barrier”, determined by the spectrum of an appropriately defined noise matrix, that prevents the convexified MLE and spectral clustering algorithms from succeeding in the hard regime. In the special setting with a single cluster, the work by proves that no polynomial-time algorithm can reliably recover the cluster if $\beta<\alpha/4+1/2$ conditioned on the planted clique hardness hypothesis.

The simple counting algorithm fails outside the simple regime due to a “variance barrier” which is associated with the fluctuations of the node degrees and the numbers of common neighbors. The simple algorithm is statistically order-wise weaker than the convexified MLE in separating different clusters.

Our main theorems apply beyond the special setting above and allow for general values of $p$, $q$, $K$, and $r$. The four regimes and the statistical-computational tradeoffs can be observed for a broad spectrum of planted problems, including planed partition, planted coloring, planted $r$-disjoint-clique and planted densest-subgraph models. Table 1 summarizes the implications of our results for some of these models. More precise and general results are given in Section 2.

2 Submatrix Localization: The Four Regimes

Similar results hold for the submatrix localization problem. Consider the setting with $n_{L}=n_{R}=n$ and $K_{L}=K_{R}=K$. The statistical hardness of submatrix localization is captured by the quantity $\mu^{2}$, which is again a measure of the SNR. In the high SNR setting with $\mu^{2}=\Omega(\log n)$, the submatrices can be trivially identified by element-wise thresholding. In the more interesting low SNR setting with $\mu^{2}=O(\log n)$, our main theorems identify the following four regimes, which have the same meanings as before:

The Impossible Regime: $\mu^{2}\overset{\bm{.}}{\lesssim}\frac{1}{K}$. All algorithm fail in this regime.

The Hard Regime: $\frac{1}{K}\overset{\bm{.}}{\lesssim}\mu^{2}\overset{\bm{.}}{\lesssim}\frac{n}{K^{2}}$. The computationally expensive MLE succeeds, and it is conjectured that no polynomial-time algorithm succeeds here.

The Easy Regime: $\frac{n}{K^{2}}\overset{\bm{.}}{\lesssim}\mu^{2}\overset{\bm{.}}{\lesssim}\frac{\sqrt{n}}{K}$. The polynomial-time convexified MLE succeeds, and provably fails in the hard regime.

The Simple Regime: $\frac{\sqrt{n}}{K}\overset{\bm{.}}{\lesssim}\mu^{2}\overset{\bm{.}}{\lesssim}1$. A simple thresholding algorithm succeeds, and provably fails outside this regime.

We illustrate these four regimes in Figure 1 assuming $\mu^{2}=\Theta(n^{-\alpha})$ and $K=\Theta(n^{\beta})$. In fact, the results above hold in the more general setting where the entries of $A$ are sub-Gaussian.

3 Discussions

This paper presents a systematic study of planted clustering and submatrix localization with a growing number of clusters/submatrices. We provide sharp characterizations of the minimax recovery boundary with the lower and upper bounds matching up to constants. We also give improved performance guarantees for convex optimization approaches and the simple counting/thresholding algorithms. In addition, complementary results are given on the failure conditions for these algorithms, hence characterizing their performance limits. Our analysis addresses several challenges that arise in the high-rank setting. The results in this paper highlight the similarity between planted clustering and submatrix localization, and place under a unified framework several classical problems such as planted clique, partition, coloring, and densest graph.

The central theme of our investigation is the interaction between the statistical and the computational aspects in the problems, i.e., how to handle more noise and more complicated structures using more computation. Our study parallels a recent line of work that takes a joint statistical and computational view on inference problems ; several of these works are closely related to special cases of the planted clustering and bi-clustering models. In this sense, we investigate two specific but fundamental problems, and we expect that the phenomena and principles described in this paper are relevant more generally. Below we provide additional discussions, and comment on the relations with existing work.

Several recent works investigate the problems of single-submatrix detection/localization , planted densest subgraph detection and sparse principal component analysis (PCA) (cf. Section 1.4 for a literature review). Even earlier is the extensive study of the statistical/computational hardness of Planted Clique. The majority of these works focus on the rank-one setting with a single clique, cluster, submatrix or principal component. This paper considers the more general high-rank setting where the number $r$ of clusters/submatrices may grow quickly with the problem size. This setting is important in many empirical networks , and poses significant challenges to the analysis. Moreover, there are qualitative differences between these two settings. We discuss one such difference in the next paragraph.

In the previous work on the rank-one case of the submatrix detection/localization problem and the sparse PCA problem , it is shown that simple algorithms based on averaging/thresholding have order-wise similar statistical performance as more sophisticated convex optimization approaches. In contrast, for the problems of finding multiple clusters/submatrices, we show that convex relaxation approaches are statistically much more powerful than the simple counting/thresholding algorithm. Our analysis reveals that the power of convex relaxations lies in separating different clusters/submatrices, but not in identifying a single cluster/submatrix. Our results thus provide one explanation for the (somewhat curious) observation in previous work regarding the lack of benefit of using sophisticated methods, and demonstrate a finer spectrum of computational-statistical tradeoffs.

Several recent works on planted densest subgraph and submatrix detection have focused on the detection or hypothesis testing version of the problems, i.e., detecting the existence of a dense cluster or an elevated submatrix (cf. Section 1.4 for literature review). In this paper, we study the (support) estimation version of the problems, where the goal is to find the precise locations of the clusters/submatrices. In general estimation appears to be harder than detection. For example, if we consider the scalings of $\mu$ and $K$ in Figure 1 of this paper, and compare with Figure 1 in which studies submatrix detection, we see that the minimax localization boundary is $\beta=\alpha$, whereas the minimax detection boundary is at a higher value $\beta=\min\{\alpha,\alpha/4+1/2\}$. For the planted densest subgraph problem, we see a similar gap between the minimax detection and estimation boundaries if we compare our results with results in . In addition, it is shown in that if $\beta>\alpha/4+1/2$, the planted submatrix or densest subgraph can be detected in linear time; if $\beta<\alpha/4+1/2$, no polynomial-time test exists assuming the hardness of the planted clique detection problem. For estimation, we prove the sufficient condition $\beta>\alpha/2+1/2$, which is the best known performance guarantee for polynomial-time algorithms—again we see a gap between detection and estimation. For detecting a sparse principal component, see the seminar work for proving computational lower bounds conditioned on the hardness of Planted Clique.

It is a simple exercise to extend our results to a variant of the planted clustering model where the graph adjacency matrix has sub-Gaussian entries instead of Bernoulli, corresponding to a weighted graph clustering problem. Similarly, we can also extend the submatrix location problem to the setting with Bernoulli entries, which is the bi-clustering problem on an unweighted graph and covers the planted bi-clique problem as a special case.

4 Related Work

There is a large body of literature, from the physics, computer science and statistics communities, on models and algorithms for graph clustering and bi-clustering, as well as on their various extensions and applications. A complete survey is beyond the scope of this paper. Here we focus on theoretical work on planted clustering/submatrix localization concerning exact recovery of the clusters/submatrices. Detailed comparisons of existing results with ours are provided after we present each of our theorems in Sections 2 and 3. We emphasize that our results are non-asymptotic and applicable to finite values of $n,n_{L}$ and $n_{R}$, whereas some of the results below require $n\to\infty$.

The planted clique model ($r=1$, $p=1$, $q=1/2$) is the most widely studied planted model. If the clique has size $K=o(\log n)$, recovery is impossible as the random graph ${\mathcal{G}}(n,1/2)$ will have a clique with at least the same size; if $K=\Omega(\log n)$, an exhaustive search succeeds ; if $K=\Omega(\sqrt{n})$, various polynomial-time algorithms work ; if $K=\Omega(\sqrt{n\log n})$, the nodes in the clique can be easily identified by counting degrees . It is an open problem to find polynomial-time algorithms which succeed in the regime with $K=o(\sqrt{n})$, and it is believed that this cannot be done . The four regimes above can be considered as a special case of our results for the general planted clustering model. The planted densest subgraph model generalizes the planted clique model by allowing general values of $p$ and $q$. The detection version of this problem is studied in , and conditional computational hardness results are obtained in .

Subsequent work considers the setting with $r\geq 1$ planted cliques , as well as the planted partition model (a.k.a. stochastic block model) with general values of $p>q$ . A subset of these results allow for growing values $r$. Most existing work focuses on the recovery performance of specific polynomial-time algorithms. The state-of-the-art recovery results for planted $r$-disjoint-clique are given in , and for planted partition in ; see for a survey of these results. The setting with $p<q$ is sometimes called the heterophily case, with the planted coloring model ($p=0$) as an important special case . Our performance guarantees for the convexified MLE (cf. Table 1) improve upon the previously known results for polynomial-time algorithms. Also, particularly when the number of clusters $r$ is allowed to scale arbitrarily with $n$, matching upper and lower bounds for the information-theoretic limits were previously unknown. This paper identifies the minimax recovery thresholds for general values of $p,q,K$ and $r$, and shows that they are achieved by the MLE. Our results also suggest that polynomial-time algorithms may not be able to achieve these thresholds in the growing $r$ setting with the cluster size $K$ sublinear in $n$.

Complementary to the achievability results, another line of work focuses on converse results, i.e., identifying necessary conditions for recovery, either for any algorithm, or for any algorithm in a specific class. For the planted partition model with $K=\Theta(n)$, necessary conditions for any algorithm to succeed are obtained in using information-theoretic tools. For spectral clustering algorithms and convex optimization approaches, more stringent conditions are shown to be needed . We generalize and improve upon the existing work above.

Since the conference version of this paper is published , a number of papers have appeared on the information-theoretic limits of exact recovery under the stochastic block model. Under the special setting with $r=2$ and $K=n/2$, the recovery threshold with sharp constants is identified in for $p,q=O(\log n/n)$, and in for general scalings of $p,q$. Very recently, proved the sharp recovery threshold for the more general case where $r=O(1)$, $K=\Theta(n)$ and the in-cluster and cross-cluster edge probabilities are heterogeneous and scale as $\log n/n$. Notably, when the number of clusters $r$ is bounded, sharp recovery thresholds may be achieved by polynomial-time algorithms, in particular, by the semi-definite programming relaxation of the maximum likelihood estimator . Our results are optimal up to absolute constant factors, but are non-asymptotic and apply to a growing number of clusters/submatrices of size sublinear in $n$.

While not the focus of this paper, approximate cluster recovery (under various criteria) has also been studied, e.g., for planted partition with $r=O(1)$ clusters in . These results are not directly comparable to ours, but often the approximate recovery conditions differ from the exact recovery conditions by a $\log n$ factor. When constant factors are concerned, the existence of a hard regime is also conjectured in .

The statistical and computational tradeoffs in locating a single submatrix (i.e., $r=1$) are studied in , where the information limit is shown to be achieved by a computationally intractable algorithm order-wise. The success and failure conditions for various polynomial-time procedures are also derived. The work focuses on success conditions for a convex relaxation approach; we improve the results particularly in the high-rank setting. The single-submatrix detection problem is studied in , and the recent work by establishes the conditional hardness for this problem.

5 Paper Organization and Notation

The remainder of this paper is organized as follows. In Section 2 we set up the planted clustering model and present our main theorems for the impossible, hard, easy, and simple regimes. In Section 3 we turn to the submatrix localization problem and provide the corresponding theorems for the four regimes. Section 4 provides a brief summary with a discussion of future work. We prove the main theorems for planted clustering and submatrix localization in Sections 5 and 6, respectively.

Let $a\vee b=\max\{a,b\}$ and $a\wedge b=\min\{a,b\}$, and $[m]=\{1,2,\ldots,m\}$ for any positive integer $m$. We use $c_{1},c_{2}$ etc. to denote absolute numerical constants whose values can be made explicit and are independent of the model parameters. We use the standard big-O notations: for two sequences $\{a_{n}\},\{b_{n}\}$, we write $a_{n}\lesssim b_{n}$ or $a_{n}=O(b_{n})$ to mean $a_{n}\leq c_{1}b_{n}$ for an absolute constant $c_{1}$ and all $n$. Similarly, $a_{n}\gtrsim b_{n}$ means $a_{n}=\Omega(b_{n})$, and $a_{n}\asymp b_{n}$ means $a_{n}=\Theta(b_{n})$.

Main Results for Planted Clustering

Suppose $n$ nodes (which are identified with $[n]$) are divided into two subsets $V_{1}$ and $V_{2}$ with $|V_{1}|=rK$ and $|V_{2}|=n-rK$. The nodes in $V_{1}$ are partitioned into $r$ disjoint clusters $C^{\ast}_{1},\ldots,C^{\ast}_{r}$ (called true clusters), where $|C^{\ast}_{m}|=K$ for each $m\in[r]$ and $\bigcup_{m=1}^{r}C^{\ast}_{m}=V_{1}$. Nodes in $V_{2}$ do not belong to any of the clusters and are called isolated nodes. A random graph is generated based on the cluster structure: for each pair of nodes and independently of all others, we connect them by an edge with probability $p$ (called in-cluster edge density) if they are in the same cluster, and otherwise with probability $q$ (called cross-cluster edge density).

We emphasize again that the values of $p$, $q$, $r$, and $K$ are allowed to be functions of $n$. The goal is to exactly recover the true clusters $\{C^{\ast}_{m}\}_{m=1}^{r}$ up to a permutation of cluster indices given the random graph.

The model parameters $(p,q,r,K)$ are assumed to be known to the algorithms. This assumption is often not necessary and can be relaxed . It is also possible to allow for non-uniform cluster sizes , and heterogeneous edge probabilities and node degrees . These extensions are certainly important in practical applications; we do not delve into them, and point to the referenced papers above and the references therein for work in this direction.

The planted clustering model generalizes several classical planted models.

Planted $r$-Disjoint-Clique . Here $p=1$ and $0<q<1$, so $r$ cliques of size $K$ are planted into an Erdős-Rényi random graph $G(n,q)$. The special case with $r=1$ is known as the planted clique problem .

Planted Densest Subgraph . Here $0<q<p<1$ and $r=1$, so there is a subgraph of size $K$ and density $p$ planted into a $G(n,q)$ graph.

Planted Partition . Also known as the stochastic blockmodel . Here $n=rK$ and $p,q\in(0,1)$. The special case with $r=2$ can be called planted bisection . The case with $p<q$ is sometimes called planted noisy coloring or planted $r$-cut .

Planted $r$-Coloring . Here $n=rK$ and $0=p<q<1$, so each cluster corresponds to a group of disconnected nodes that are assigned with the same color.

For clarity we shall focus on the homophily setting with $p>q$; results for the $p<q$ case are similar. In fact, any achievability or converse result for the $p>q$ case immediately implies a corresponding result for $p<q$. To see this, observe that if the graph $A$ is generated from the planted clustering model with $p<q$, then the flipped graph $A^{\prime}:=J-A-I$ ($J$ is the all-one matrix and $I$ is the identity matrix) can be considered as generated with in/cross-cluster edge densities $p^{\prime}=1-p$ and $q^{\prime}=1-q$, where $p^{\prime}>q^{\prime}$. Therefore, a problem with $p<q$ can be reduced to one with $p^{\prime}>q^{\prime}$. Clearly the reduction can also be done in the other direction.

1 The Impossible Regime: Minimax Lower Bounds

In this section, we characterize the necessary conditions for cluster recovery. Let $\mathcal{Y}$ be the set of cluster matrices corresponding to $r$ clusters of size $K$; i.e.,

We use $\widehat{Y}\equiv\widehat{Y}(A)$ to denote an estimator which takes as input the graph $A$ and outputs an element of $\mathcal{Y}$ as an estimate of the true $Y^{*}$. Our results are stated in terms of the Kullback-Leibler (KL) divergence between two Bernoulli distributions with means $u$ and $v$, denoted by $D(u\|v):=u\log\frac{u}{v}+(1-u)\log\frac{1-u}{1-v}$. The following theorem gives a lower bound on the minimax error probability of recovering $Y^{*}$.

Suppose $128\leq K\leq n/2$. Under the planted clustering model with $p>q$, if one of the following two conditions holds:

where the infimum ranges over all measurable function of the graph.

The theorem shows it is fundamentally impossible to recover the clusters with success probability close to 1 in the regime where (1) or (2) holds, which is thus called the impossible regime. This regime arises from an information/statistical barrier: The KL divergence on the LHSs of (1) and (2) determines how much information of $Y^{*}$ is contained in the data $A$. If the in-cluster and cross-cluster edge distributions are close (measured by the KL divergence) or the cluster size is small, then $A$ does not carry enough information to distinguish different cluster matrices.

It is sometimes more convenient to use the following corollary, derived by upper-bounding the KL divergence in (1) and (2) using its Taylor expansion. This corollary was used when we overviewed our results in Section 1.1. See table 1 for its implications for specific planted models.

Suppose $128\leq K\leq n/2$. Under the planted clustering model with $p>q$, if any one of the following three conditions holds:

Note the asymmetry between the roles of $p$ and $q$ in the conditions (1) and (2); this is made apparent in Corollary 2.2. To see why the asymmetry is natural, recall that by a classical result of , the largest clique in a random graph $G(n,q)$ has size $k_{q}=\Theta(\log n/\log(1/q))$ almost surely. Such a clique cannot be distinguished from a true cluster if $K\lesssim k_{q}$, even when $p=1$. This is predicted by the condition (5). When $q=0$, cluster recovery requires $p\gtrsim\frac{\log(rK)}{K}$ to ensure all true clusters are connected within themselves, matching the condition (4). The term $K$ on the RHS of (1) and (4) is relevant only when $K\leq\log(rK)$. Potential improvement on this term is left to future work.

When $r=1$ and $q=1/2$, our results recover the $K=\Theta(\log n)$ threshold for the classical planted clique problem. For planted partition with $r=O(1)$ clusters of size $K=\Theta(n)$ and $p/q=\Theta(1)$, the work in establishes the necessary condition $p-q\lesssim\sqrt{p/n}$; our result is stronger by a logarithmic factor. The work in also considers planted partition with $r=2$ and focus on the special case with the scaling $p,q=\Theta(\log(n)/n)$; they establish the condition $p+q-2\sqrt{pq}<2\log(n)/n$, which is consistent with our results up to constants in this regime. Compared to previous work, we handle the more general setting where $p,q$ and $r$ may scale arbitrarily with $n$.

2 The Hard Regime: Optimal Algorithm

In this subsection, we characterize the sufficient conditions for cluster recovery which match the necessary conditions given in Theorem 2.1 up to constant factors. We consider the Maximum Likelihood Estimator of $Y^{*}$ under the planted clustering model, which we now derive. The log-likelihood of observing the graph $A$ given a cluster matrix $Y\in\mathcal{Y}$ is

Given $A$, the MLE maximizes the the log-likelihood over the set $\mathcal{Y}$ of all possible cluster matrices. Note that $\sum_{i<j}Y_{ij}=r\binom{K}{2}$ for all $Y\in\mathcal{Y}$, so the last three terms in (6) are independent of $Y$. Therefore, the MLE for the $p>q$ case is given as in Algorithm 1.

Algorithm 1 is equivalent to finding $r$ disjoint clusters of size$K$ that maximize the number of edges inside the clusters (similar to Densest $K$-Subgraph), or minimize the number of edges outside the clusters (similar to Balanced Cut) or the disagreements between $A$ and $Y$ (similar to Correlation Clustering in ). Therefore, while Algorithm 1 is derived from the planted clustering model, it is in fact quite general and not tied to the modeling assumptions. Enumerating over the set $\mathcal{Y}$ is computationally intractable in general since $|\mathcal{Y}|=\Omega(e^{rK})$.

The following theorem provides a success condition for the MLE.

Under the planted clustering model with $p>q$, there exists a universal constant $c_{1}$ such that for any $\gamma\geq 1$, the optimal solution $\widehat{Y}$ to the problem (7)–(8) is unique and equal to $Y^{*}$ with probability at least $1-16(\gamma rK)^{-1}-256n^{-1}$ if both of the following hold:

We refer to the regime in which the condition (9) holds but (14) below fails as the hard regime, as clustering is statistically possible but conjectured to be computationally hard (cf. Conjecture 2.8). The conditions (9) above and (1)–(2) in Theorem 2.1 match up to a constant factor under the mild assumption $K\geq\log(rK)$. This establishes the minimax recovery boundary for planted clustering and the minimax optimality of the MLE up to constant factors.

By lower bounding the KL divergence, we obtain the following corollary, which is sometimes more convenient to use. See Table 1 for its implications for specific planted models.

For planted clustering with $p>q$, there exists a universal constant $c_{2}$ such that for any $\gamma\geq 1$, the optimal solution $\widehat{Y}$ to the problem (7)–(8) is unique and equal to $Y^{*}$ with probability at least $1-16(\gamma rK)^{-1}-256n^{-1}$ provided

The condition (10) can be simplified to $K(p-q)^{2}\gtrsim q(1-q)\log n$ if $q=\Theta(p)$, and to $Kp\log\frac{p}{q}\gtrsim\log n,Kp\gtrsim\log(rK)$ if $q=o(p)$. These match the converse conditions in Corollary 2.2 up to constants.

Theorem 2.3 provides the first minimax results tight up to constant factors when the number of clusters is allowed to grow, potentially at a nearly-linear rate $r=O(n/\log n)$. Interestingly, for a fixed cluster size, the recovery boundary (9) depends only weakly on the number of clusters $r$ though the logarithmic term. For $r=1$ and $p=2q=1$, we recover the recovery boundary for planted clique $K\asymp\log n$. For the planted densest subgraph model where $p/q=\Theta(1)$, $p$ bounded away from $1$ and $Kq\gg 1$, the minimax detection boundary is shown in to be $\frac{(p-q)^{2}}{q}\asymp\min\{\frac{1}{K}\log\frac{n}{K},\frac{n^{2}}{K^{4}}\}$; our results show that the minimax recovery boundary is $\frac{(p-q)^{2}}{q}\asymp\frac{\log n}{K}$, which is strictly above the detection boundary because $\frac{n^{2}}{K^{4}}$ can be much smaller than $\frac{\log n}{K}.$ For the planted bisection model with two equal-sized clusters: if $p,q=\Theta(\log(n)/n)$, the sharp recovery boundary is found in and to be $K(\sqrt{p}-\sqrt{q})^{2}>\log n$, which is consistent with our results up to constants; if $p,q=O(1/n)$, the correlated recovery limit is shown in to be $K(p-q)^{2}>p+q$, which is consistent with our results up to a logarithmic factor.

3 The Easy Regime: Polynomial-Time Algorithms

In this subsection, we present a polynomial-time algorithm for the planted clustering problem and show that it succeeds in the easy regime described in the introduction.

Our algorithm is based on taking a convex relaxation of the MLE in Algorithm 1. Note that the objective function (7) in the MLE is linear, but the constraint $Y\in\mathcal{Y}$ involves a set $\mathcal{Y}$ that is discrete, non-convex and exponentially large. We replace this non-convex constraint with a trace norm (a.k.a. nuclear norm) constraint and a set of linear constraints. This leads to the convexified MLE given in Algorithm 2. Here the trace norm $\|Y\|_{*}$ is defined as the sum of the singular values of $Y$. Note that the true $Y^{*}$ is feasible to the optimization problem (11)–(13) since $\|Y^{*}\|_{*}=\text{trace}(Y^{*})=rK.$

The optimization problem in Algorithm 2 is a semidefinite program (SDP) and can be solved in polynomial time by standard interior point methods or various fast specialized algorithms such as ADMM; e.g., see . Similarly to Algorithm 1, this algorithm is not strictly tied to the planted clustering model as it can also be considered as a relaxation of Correlation Clustering or Balanced Cut. In the case where the values of $r$ and $K$ are unknown, one may replace the hard constraints (12) and (13) with an appropriately weighted objective function; cf. .

The following theorem provides a sufficient condition for the success of the convexified MLE. See Table 1 for its implications for specific planted models.

Under the planted clustering model with $p>q$, there exists a universal constant $c_{1}$ such that with probability at least $1-n^{-10}$, the optimal solution to the problem (11)–(13) is unique and equal to $Y^{*}$ provided

When $r=1$, we refer to the regime where the condition (14) holds and (17) below fails as the easy regime. When $r>1$, the easy regime is where (14) holds and (17) or (18) below fails.

If $p/q=\Theta(1)$, it is easy to see that the smallest possible cluster size allowed by (14) is $K=\Theta(\sqrt{n})$ and the largest number of clusters is $r=\Theta(\sqrt{n})$, both of which are achieved when $p,q,|p-q|=\Theta(1)$. This generalizes the tractability threshold $K=\Omega(\sqrt{n})$ of the classic planted clique problem. If $q=o(p)$ (we call it the high SNR setting), the condition (14) becomes to $Kp\gtrsim\max\{\log n,\sqrt{qn}\}$. In this case, it is possible to go beyond the $\sqrt{n}$ limit on the cluster size. In particular, when $p=\Theta(1)$, the smallest possible cluster size is $K=\Theta(\log n\vee\sqrt{qn})$, which can be much smaller than $\sqrt{n}$.

Theorem 2.5 immediately implies guarantees for other tighter convex relaxations. Define the sets $\mathcal{B}:=\{Y|Eq.\eqref{eq:linear}\text{ holds}\}$ and

The constraint in Algorithm 2 corresponds to $Y\in\mathcal{S}_{1}\cap\mathcal{B}$, while $Y\in\mathcal{S}_{2}\cap\mathcal{B}$ is the constraint in the standard SDP relaxation. Clearly $\left(\mathcal{S}_{1}\cap\mathcal{B}\right)\supseteq\left(\mathcal{S}_{2}\cap\mathcal{B}\right)\supseteq\mathcal{Y}.$ Therefore, if we replace the constraint (12) with $Y\in\mathcal{S}_{2}$, we obtain a tighter relaxation of the MLE, and Theorem 2.5 guarantees that it also succeeds to recover $Y^{*}$ under the condition (14). The same is true if we consider other tighter relaxations, such as those involving the triangle inequalities , the row-wise constraints $\sum_{j}Y_{ij}\leq K,\forall i$ , the max norm or the Fantope constraint . For the purpose of this work, these variants of the convex formulation make no significant difference, and we choose to focus on (11)–(13) for generality.

We have a partial converse to the achievability result in Theorem 2.5. The following theorem characterizes the conditions under which the trace norm relaxation (11)–(13) provably fails with high probability; we suspect the standard SDP relaxation with the constraint $Y\in\mathcal{S}_{2}\cap\mathcal{B}$ also fails with high probability under the same conditions, but we do not have a proof.

Under the planted clustering model with $p>q$, for any constant $1>\epsilon_{0}>0$, there exist positive universal constants $c_{1},c_{2}$ for which the following holds. Suppose $c_{1}\log n\leq K\leq\frac{n}{2}$, $q\geq c_{1}\frac{\log n}{n}$ and $p\leq 1-\epsilon_{0}$. If

then with probability at least $1-n^{-10}$, $Y^{\ast}$ is not an optimal solution of the program (11)–(13).

Theorem 2.7 proves the failure of our trace norm relaxation that has access to the exact number and sizes of the clusters. Consequently, replacing the constraints (12) and (13) with a Lagrangian penalty term in the objective would not help for any value of the Lagrangian multipliers. Under the assumptions of Theorems 2.5 and 2.7, by ignoring log factors, the sufficient and necessary condition for the success of our convexified MLE is

whereas the success condition (10) for the MLE simplifies to

We refer to for a survey of the performance of state-of-the-art polynomial-time algorithms under various planted models. Theorem 2.5 matches and in many cases improves upon existing results in terms of the scaling. For example, for planted partition, the previous best results are $(p-q)^{2}\gtrsim p(K\log^{4}n+n)/K^{2}$ in and $(p-q)^{2}\gtrsim pn\operatorname{polylog}n/K^{2}$ in . Theorem 2.5 removes some extra $\log n$ factors, and is also order-wise better when $q=o(p)$ (the high SNR case) or $1-q=o(1)$. For planted $r$-disjoint-clique, existing results require $1-q$ to be $\Omega((rn+rK\log n)/K^{2})$ , $\Omega(\sqrt{n}/K)$ or $\Omega((n+K\log^{4}n)/K^{2})$ . We improve them to $\Omega((n+K\log n)/K^{2})$.

Our converse result in Theorem 2.7 is inspired by, and improves upon, the recent work in , which focuses on the special case $p>1/2>q$, and considers a convex relaxation approach that is equivalent to our relaxation (11)–(13) but without the additional equality constraint in (13). The approach is shown to fail when $K^{2}(p-\frac{1}{2})^{2}\lesssim qn$. Our result is stronger in the sense that it applies to a tighter relaxation and a larger region of the parameter space.

Limits of polynomial-time algorithms

By comparing the recovery limit established in Theorems 2.1 and 2.3 with the performance limit of our convex method established in Theorem 2.5, we get two strikingly different observations. On one hand, if $pK\log n=\Omega(nq)$ and $\log K=\Omega(\log n)$, the recovery limit and performance limit of our convex method coincide up to constant factors at $K(p-q)^{2}\asymp p(1-q)\log n$. Thus, the convex relaxation is tight and the hard regime disappears up to constants, even though the hard regime may still exist when constant factors are concerned . In this case, we get a computationally efficient and statistically order-optimal estimator. On the other hand, if $pK\log n=o(nq)$, there exists a substantial gap between the information limit and performance limit of our convex method. We conjecture that no polynomial-time algorithm has order-wise better statistical performance than the convexified MLE and succeeds significantly beyond the condition (14).

For any constant $\epsilon>0$, there is no algorithm with running time polynomial in $n$ that, for all $n$ and with probability at least $1/2$, outputs the true $Y^{\ast}$ of the planted clustering problem with $p>q$ and

If the conjecture is true, then in the asymptotic regime $p=2q=n^{-\alpha}$ and $K=n^{\beta}$, the computational limit for the cluster recovery is given by $\beta=\frac{\alpha}{2}+\frac{1}{2}$, i.e., the boundary between the green regime and red regime in Fig. 1.

A rigorous proof of Conjecture 2.8 seems difficult with current techniques. There are other possible convex formulations for planted clustering. The space of possible polynomial-time algorithms is even larger. It is impossible for us to study each of them separately and obtain a converse result as in Theorem 2.7. There are however several evidences that support the conjecture:

The special case with $p=2q=1$ corresponds to the $K=o(\sqrt{n})$ regime for the classical Planted Clique problem, which is conjectured to be computationally hard , and was used as an assumption for proving other hardness results . Conjecture 2.8 can be considered as a generalization of the Planted Clique conjecture to the setting with multiple clusters and general values of $p$ and $q$, and may be used to study the computational hardness of other problems .

It is shown in that for the special setting with a single cluster, no polynomial-time algorithm can reliably recover the planted cluster if $\beta<\alpha/4+1/2$ conditioned on the planted clique hardness hypothesis. Here the planted clique hardness hypothesis refers to the statement that for any fixed constants $\gamma>0$ and $\delta>0$, there exist no randomized polynomial-time tests to distinguish an Erdős-Rényi random graph ${\mathcal{G}}(n,\gamma)$ and a planted clique model which is obtained by adding edges to $K=n^{1/2-\delta}$ vertices chosen uniformly from ${\mathcal{G}}(n,\gamma)$ to form a clique.

As discussed earlier, if (16) holds, then the graph spectrum is dominated by noise and fails to reveal the underlying cluster structure. The condition (16) therefore represents a “spectral barrier” for clustering. The work in uses a similar spectral barrier argument to prove the failure of a large class of algorithms that rely on the graph spectrum; our Theorem 2.7 shows that the convexified MLE fails for a similar reason.

In the sparse graph case with $p,q=O(1/n)$, it is argued in , using non-rigorous but deep arguments from statistical physics, that it is intractable to achieve the correlated recovery under Condition (16).

4 The Simple Regime: A Counting Algorithm

In this subsection, we consider a simple recovery procedure in Algorithm 3, which is based on counting node degrees and common neighbors.

We note that steps 1 and 2 of Algorithm 3 are considered in and respectively for the special cases of recovering a single planted clique or two planted clusters. Let $E$ be the set of edges. It is not hard to see that step 1 runs in time $O(|E|)$ and step 2 runs in time $O(n|E|)$, since each node only needs to look up its local neighborhood up to distance two. It is possible to achieve even smaller expected running time using clever data structures.

The following theorem provides sufficient conditions for the simple counting algorithm to succeed. Compared to the previous work in , our results apply to general values of $p,q$, $r$, and $K$. See Table 1 for its implications for specific planted models.

For planted clustering with $p>q$, there exist universal constants $c_{1},c_{2}$ such that Algorithm 3 correctly finds the isolated nodes with probability at least $1-2n^{-1}$ if

and finds the clusters with probability at least $1-4n^{-1}$ if further

If $p,q\to 1$ as $n\to\infty$, we can obtain slightly better performance by counting the common non-neighbors in Step 2, which succeeds under condition (18) with $p$ and $q$ replaced by $1-p$ and $1-q$, respectively, i.e., the RHS of (18) simplifies to $c_{2}n(1-q)^{2}\log n$.

In the case with a single clusters $r=1$, we refer to the regime where the condition (17) holds as the simple regime; in the case with $r>1$, the simple regime is where both conditions (17) and (18) hold. It is instructive to compare these conditions with the success condition (14) for the convexified MLE. The condition (17) has an additional $\log n$ factor on the RHS. This means when $r=1$ and the only task is to find the isolated nodes, the counting algorithm performs nearly as well as the sophisticated convexified MLE. On the other hand, when $r>1$ and one needs to distinguish between different clusters, the convexified MLE order-wise outperforms the counting algorithm whenever $p/q=\Theta(1)$, as the condition (18) is order-wise more restrictive than (14). Nevertheless, when $p,q,p-q=\Theta(1)$, both algorithms can recover $\widetilde{O}(\sqrt{n})$ clusters of size $\widetilde{\Omega}(\sqrt{n})$, making the simple counting algorithm a legitimate candidate in such a setting and a benchmark to which other algorithms can be compared with.

In the high SNR case with $q=o(p)$, the counting algorithm can recover clusters with size much smaller than $\sqrt{n}$; e.g., if $p=\Theta(1)$ and $q=o(1)$, it only requires $K\gtrsim\max\{\log n,\sqrt{qn\log n}\}$.

We have a (nearly-)matching converse to Theorem 2.9. The following theorem characterizes when the counting algorithm provably fails.

Under the planted clustering model with $p>q$, for any constant $0<\epsilon_{0}<1$, there exist universal constants $c_{1},c_{2}>0$ for which the following holds. Suppose $K\leq\frac{n}{2}$, $p\leq 1-\epsilon_{0}$, $q\geq c_{1}\log n/n$ and $Kp^{2}+nq^{2}\geq c_{1}\log n$. Algorithm 3 fails to correctly identify all the isolated nodes with probability at least $1/4$ if

and fails to correctly recover all the clusters with probability at least $1/4$ if

Theorem 2.11 requires a technical condition $Kp^{2}+nq^{2}\geq c_{1}\log n$, which is actually not too restrictive. If $Kp^{2}+nq^{2}=o(\log n)$, then two nodes from the same cluster will have no common neighbor with probability $(1-p^{2})^{K}(1-q^{2})^{n-K}\geq\exp[-\Theta(p^{2}K+q^{2}(n-K))]=\exp[-o(\log n)]$, so Algorithm 3 cannot succeed with the probability specified in Theorem 2.9.

Apart from some technical conditions, Theorems 2.9 and 2.11 show that the conditions (17) and (18) are both sufficient and necessary. In particular, the counting algorithm cannot succeed outside the simple regime, and is indeed strictly weaker in separating different clusters as compared to the convexified MLE. Our proof reveals that the performance of the counting algorithm is limited by a variance barrier: The RHS of (17) and (18) are associated with the variance of the node degrees and common neighbors (i.e., $d_{i}$ and $S_{ij}$ in Algorithm 3), respectively. There exist nodes whose degrees deviate from their expected value on the order of the standard deviation, and if the condition (17) does not hold, then the deviation will outweigh the difference between the expected degrees of the isolated nodes and those of the non-isolated nodes. A similar argument applies to the number of common neighbors.

Main Results for Submatrix Localization

In the language of bi-clustering, the sets $\left\{C^{\ast}_{1},\ldots,C^{\ast}_{r}\right\}$ are called left clusters and $\{D^{\ast}_{1},\ldots,D^{\ast}_{r}\}$ are called right clusters. Row (column, resp.) indices which do not belong to any cluster are called isolated left (right, resp.) nodes. One can think of $A$ as the bipartite affinity matrix between the $n_{L}$ left nodes and $n_{R}$ right nodes, and the goal is to recover the left and right clusters. Similarly as before, we define the bi-clustering matrix $Y^{*}\in\left\{0,1\right\}^{n_{L}\times n_{R}}$, where $Y^{\ast}_{ij}=1$ if and only if $(i,j)\in C^{\ast}_{m}\times D^{\ast}_{m}$ for some $m\in[r]$. The problem reduces to recovering $Y^{\ast}$ given $A$.

As before, all the parameters $\mu,K_{L},K_{R},r$ are allowed to scale with $n_{L}$ and $n_{R}$, and we assume that their values are known. Note that it is without loss of generality to assume the mean of $A_{ij}$ is zero outside the submatrices and the variance of $A_{ij}$ is one, because otherwise we can shift and rescale $A$. The above model generalizes the previous submatrix localization/detection models and bi-clustering models which consider the special case with a single submatrix (i.e., $r=1$).

In the next four subsections, we shall focus on the low-SNR setting $\mu^{2}=O(\log n)$ and present theorems establishing the four regimes. These results parallel those for the planted clustering. In the high SNR setting $\mu^{2}=\Omega(\log n)$, the submatrices can be easily identified by naive element-wise thresholding, so we deal with this case separately in the last subsection.

The following theorem gives conditions on $(n_{L},n_{R},K_{L},K_{R},\mu)$ under which the minimax error probability is large and thus it is informationally impossible to reliably locate the submatrices. With slight abuse of notation, we use $\mathcal{Y}\subset\left\{0,1\right\}^{n_{L}\times n_{R}}$ to denote the set of all possible bi-clustering matrices corresponding to $r$ left (right, resp.) clusters of equal size $K_{L}$ ($K_{R}$, resp.).

Under the submatrix localization model, suppose $\{A_{ij}\}$ are Gaussian random variables, $K_{L}\leq n_{L}/2$, $K_{R}\leq n_{R}/2$, and $n_{L},n_{R}\geq 128$. If

The regime where (21) holds is called the impossible regime, corresponding to an information barrier that no algorithm can break. We note the similarity between the impossible regimes for submatrix localization and planted clustering. In particular, if we assume the in/cross-cluster edges in planted clustering have comparable variance, i.e., $\frac{p(1-p)}{q(1-q)}=\Theta(1)$, then the conditions (21) and (3) coincide up to constant factors by setting $n_{L}=n_{R}=n,K_{L}=K_{R}=K$ and $\mu=\frac{p-q}{\sqrt{q(1-q)}}$. Such correspondence also exists in the next three regimes.

Theorem 3.1 holds in the general high rank setting with arbitrary $r$. In $r=1$ case, our result recovers the minimax lower bound in .

2 The Hard Regime: Optimal Algorithm

Recall that $\mathcal{Y}$ is the set of all valid bi-clustering matrices. We consider the combinatorial optimization problem given in Algorithm 4. In the setting where $\{\Delta_{ij}\}$ are Gaussian random variables, this can be shown to be the MLE of $Y^{*}$.

Theorem 3.2 below provides a success condition for Algorithm 4.

Suppose $K_{L},K_{R}\geq 8$. There exists a constant $c_{1}$ such that with probability at least $1-512en^{-1}$, the optimal solution to the problem (22) is unique and equals $Y^{*}$ if

We refer to the regime where the condition (23) holds and (27) fails as the hard regime. Note that the bound (23) matches (21) up to a constant factor, so they are minimax optimal. Therefore, Theorems 3.1 and 3.2 together establish the minimax recovery boundary for submatrix localization at $\mu^{2}\asymp\frac{\log n}{K_{L}\wedge K_{R}}.$

Theorem 3.2 provides the first minimax-optimal achievability result when the number $r$ of submatrices may grow with $n_{L}$ and $n_{R}$. In particular, $r$ is allowed to grow at a nearly linear rate $r=O(n/\log n)$ assuming $n_{L}=n_{R}=n$. In the special case with a single planted submatrix ($r=1$), Theorem 3.2 recovers the achievability result in .

3 The Easy Regime: Polynomial-Time Algorithms

As previous, we obtain a convex relaxation of the combinatorial MLE formulation (22) by replacing the constraint $Y\in\mathcal{Y}$ with the trace norm and linear constraints, for which we use the fact that the true $Y^{*}$ satisfies $\left\|Y^{*}\right\|_{*}=r\sqrt{K_{L}K_{R}}$. This is given as Algorithm 5, which is a semidefinite program (SDP) and can be solved in polynomial time.

The following theorem provides a sufficient condition for the success of Algorithm 5.

There exists a universal constant $c_{1}$ such that with probability at least $1-n^{-10}$, the optimal solution to the program (26)–(26) in Algorithm 5 is unique and equals $Y^{*}$ if

When $r=1$, the easy regime refers to where the condition (27) holds but (29) fails. When $r>1$, the easy regime is where the condition (27) holds but (30) fails. Suppose $n_{L}=n_{R}=n$ and $K_{L}=K_{R}=K$; the convexified MLE is guaranteed to succeed when $\mu^{2}\gtrsim\frac{K\log n+n}{K^{2}}$.

The following theorem provides a nearly matching converse to Theorem 3.3.

There exist positive universal constants $c_{1},c_{2}$ such that the following holds. Under the submatrix localization model, suppose $\mu\leq 1/100$, $n_{L}=n_{R}=n$, $K_{L}=K_{R}=K$, $c_{1}\log n\leq K\leq\frac{n}{2}$, and $(\Delta_{ij})$ are Gaussian random variables. If

then with probability at least $1-n^{-10}$, any optimal solution to the convex program (26)–(26) has a different support from $Y^{*}$.

As in the planted clustering model, we conjecture that no polynomial-time algorithm can achieve better statistical performance than the convexified MLE.

For any constant $\epsilon>0$, there is no algorithm with running time polynomial in $n$ that, for all $n$ and with probability at least $1/2$, outputs the true $Y^{\ast}$ for the submatrix localization problem with $\mu\leq 1$, $n_{L}=n_{R}=n$, $K_{L}=K_{R}=K\geq c_{1}\log n$ and

The achievability and converse results in Theorems 3.3 and 3.4 hold even when $r$ grows with $n$. In the special case with $r=1$, the work in considers a convex relaxation of sparse singular value decomposition; they focus on the high SNR regime with $\mu^{2}\gtrsim\log n$, and show that the performance of their convex relaxation is no better than a simple element-wise thresholding approach (cf. Section 3.5). Our convex program is different from theirs, and succeeds in the low SNR regime provided $\mu^{2}\gtrsim\frac{K\log n+n}{K^{2}}$. The work in studies the success conditions of a convex formulation similar to ; with the additional assumption of bounded support of the distribution of $A_{ij}$, they show that their approach succeeds under an order-wise more restricted condition $\mu^{2}\gtrsim\frac{n\cdot r}{K^{2}}$.

4 The Simple Regime: A Thresholding Algorithm

We consider a simple thresholding algorithm as given in Algorithm 6. The algorithm computes the column and row sums of $A$ as well as the correlation between the columns and rows. It is similar in spirit to the simple counting Algorithm 3 for the planted clustering problem.

Steps 1, 2 and 3 of the algorithm run in time $O(n_{L}n_{R})$, $O(n_{L}^{2}n_{R}+n_{R}^{2}n_{L})$ and $O(n_{L}n_{R})$, respectively. We note that Step 1 is previously considered in for locating a single submatrix. The following theorem provides success conditions for this simple algorithm.

There exist universal constants $c_{1},c_{2}$ such that Algorithm 6 identifies the isolated nodes with probability at least $1-en_{L}^{-1}-en_{R}^{-1}$ if

and exactly recovers $Y^{\ast}$ with probability at least $1-e(rK_{L})^{-1}-e(rK_{R})^{-1}-en^{-1}$ if further

When $r=1$, we refer to the regime for which the condition (29) holds as the simple regime. When $r>1$, the simple regime is where both conditions (29) and (30) hold.

We provide a converse to Theorem 3.6. The following theorem shows that the conditions (29) and (30) are also (nearly) necessary for the simple thresholding algorithm to succeed.

Suppose that $K_{L},K_{R}\geq\log n$. Under the submatrix localization model where the distributions of $\{A_{ij}\}$ are Gaussian, there exist universal constants $c_{1},c_{2}$ such that with probability at least $1-n^{-10}$, Algorithm 6 fails to correctly identify all the isolated nodes if

and fails to correctly recover all the clusters if $n_{L}\geq rK_{R}$, $n_{R}\geq rK_{L}$ and

When $n_{L}=n_{R}=n$, $K_{L}=K_{R}=K$, Theorems 3.6 and Theorem 3.7 establish that the recovery boundary for the simple thresholding algorithm is $\mu^{2}\asymp\frac{n\log n}{K^{2}}$ if $r=1$, and $\mu^{2}\asymp\frac{\sqrt{n\log n}}{K}$ if $r>1$ and $rK=\Theta(n)$. Comparing with the success condition (27) for the convex optimization approach, we see that the simple thresholding algorithm is order-wise less powerful in separating different submatrices. Similar to planted clustering, the performance is determined by the variance barrier associated with the variance of the quantities $d_{i}$ and $S_{ii^{\prime}}$ computed in Algorithm 6.

5 The High SNR Setting

As mentioned before, the high SNR setting with $\mu^{2}=\Omega(\log n)$ can be handled by a simple element-wise thresholding algorithm, which is given in Algorithm 7.

For the special case with one submatrix ($r=1$), the success of element-wise thresholding in the high SNR setting is proved in . Their result can be easily extended to the general case with $r\geq 1$. We record this result in Theorem 3.8 below. The theorem also shows that element-wise thresholding fails if $\mu^{2}=o(\log n)$, so it is not very useful in the low SNR setting.

There exists a universal constant $c_{1}>4$ such that the following holds. Algorithm 7 outputs $\widehat{Y}=Y^{*}$ with probability at least $1-n^{-3}$ provided

If the distributions of the $A_{ij}$’s are Gaussian, and $K_{L}\leq n_{L}/2$ or $K_{R}\leq n_{R}/2$, then with probability at least $1-n^{-3}$, the output of Algorithm 7 satisfies $\widehat{Y}\neq Y^{*}$ if

Discussion and Future Work

In this paper, we show that the planted clustering problem and the submatrix localization problem admit successively faster algorithms with weaker statistical performance. We provide sufficient and necessary conditions for the success of the combinatorial MLE, the convexified MLE and the simple counting/thresholding algorithm, showing that they work in successively smaller regions of the model parameters. This represents a series of tradeoffs between the statistical and computational performance. Our results indicate that there may exist a large gap between the information limit and the computational limit, i.e., the information limit might not be achievable via polynomial-time algorithms. Our results hold in the high-rank setting with a growing number of clusters or submatrices.

Several future directions are of interest. Immediate goals include removing some of the technical assumptions in our theorems. It is useful in practice to identify a finer spectrum, ideally close to a continuum, of computational-statistical tradeoffs. It is also interesting to extend to the settings with overlapping clusters and submatrices, and to the cases where the values of the model parameters are unknown. Proving our conjectures on the computational hardness in the hard regime is also interesting and such attempt has been pursued in .

Proofs for Planted Clustering

Throughout this section, we consider the planted clustering model with $p>q$. Let $n_{1}:=rK$ and $n_{2}:=n-rK$ be the numbers of non-isolated and isolated nodes, respectively.

In the sequel we will make use of the following upper and lower bounds on the KL divergence $D(u\|v)$ between two Bernoulli distributions with parameter $u\in$ and $v\in$. We have

where $(a)$ follows from the inequality $\log x\leq x-1,\forall x\geq 0$. Moreover, viewing $D(x\|v)$ as a function of $x$ and using a Taylor’s expansion, we can find some $\xi\in[u\wedge v,u\vee v]$ such that

where $(b)$ follows because $D^{\prime}\left(v\|v\right)=0$ and $D^{\prime\prime}\left(\xi\|v\right)=1/[\xi(1-\xi)]$.

Theorem 2.1 is established through the following three lemmas, each of which provides a sufficient condition for having a large error probability.

We first bound $\log|\mathcal{Y}|$. Simple counting gives that $|\mathcal{Y}|=\binom{n}{n_{1}}\frac{n_{1}!}{r!(K!)^{r}}$, where $n_{1}=\triangleq rK$. Note that $\binom{n}{n_{1}}\geq(\frac{n}{n_{1}})^{n_{1}}$ and $\sqrt{n}(\frac{n}{e})^{n}\leq n!\leq e\sqrt{n}(\frac{n}{e})^{n}$. It follows that

This implies $\log|\mathcal{Y}|\geq\frac{1}{2}n_{1}\log\frac{n}{K}$ under the assumption that $8\leq K\leq n/2$ and $n\geq 32$.

Next we upper bound $I(Y^{\ast};A)$. Note that $H(A)\leq\binom{n}{2}H(A_{12})$ because the $A_{ij}$’s are identically distributed by symmetry. Furthermore, $A_{ij}$’s are independent conditioned on $Y^{\ast}$, so $H(A|Y^{\ast})=\binom{n}{2}H(A_{12}|Y_{12}^{\ast})$. It follows that $I(Y^{\ast};A)=H(A)-H(A|Y^{\ast})\leq\binom{n}{2}I(Y^{\ast}_{12};A_{12})$. We bound $I(Y^{\ast}_{12};A_{12})$ below. Simple counting gives

It follows that $I(Y^{*};A)\leq\binom{n}{2}I(Y^{*}_{12}\|A_{12})\leq\frac{n_{1}}{8}\log\frac{n}{K}$. Substituting into (39) gives

where the last inequality holds because $K\leq n/2$ and $n_{1}\geq 32$. This proves the sufficiency of (37).

We turn to the second part of the lemma. Notice that

where $(a)$ holds due to $\alpha\leq\frac{n_{1}K}{n^{2}}$ and (35); $(b)$ holds because $\beta(1-\beta)\geq\alpha p(1-p)+(1-\alpha)q(1-q)\geq(1-\alpha)q(1-q)$ thanks to the concavity of $x(1-x)$. Combining the last displayed equation with (38) implies (37). ∎

We construct $\bar{\mathcal{Y}}$ as follows. Let $Y_{0}$ be the cluster matrix such that the clusters $\{C_{l}\}_{l=1}^{r}$ are given by $C_{l}=\left\{(l-1)K+1,\ldots,lK\right\}$. Informally, each $Y_{i}$ with $i\geq 1$ is obtained from $Y_{0}$ by swapping the cluster memberships of node $K$ and $K+i$. Formally, for each $i\in[\bar{M}]$: (1) if node $(K+i)$ belongs to cluster $C_{l}$ for some $l$, then $Y_{i}$ is the cluster matrix such that the first cluster consists of nodes $\{1,2,\ldots,K-1,K+i\}$ and the $l$-th cluster is given by $C_{l}\setminus\{K+i\}\cup\{K\}$, and all the other clusters identical to those according to $Y_{0}$; (2) if node $(K+i)$ is an isolated node in $Y_{0}$ (i.e., does not belong to any cluster), then $Y_{i}$ is the cluster matrix such that the first cluster consists of nodes $\{1,2,\ldots,K-1,K+i\}$ and node $K$ is an isolated node, and all the other clusters identical to those according to $Y_{0}$.

where (a) follows from the convexity of KL divergence, and (b) follows by our construction of $\left\{Y_{i}\right\}$. If (40) in the lemma holds, then $I(Y^{\ast};A)\leq\frac{1}{4}\log(n-K)=\frac{1}{4}\log\left|\bar{\mathcal{Y}}\right|.$ Since $\log(n-K)\geq\log(n/2)\geq 4$ if $n\geq 128$, it follows from (41) that the minimax error probability is at least $1/2$. ∎

By the assumptions (42) we have $p\leq 1/8$ and

where $(a)$ uses the inequality $1-x\geq e^{-2x},\forall x\in[0,\frac{1}{2}]$. Applying Chebyshev’s inequality, we get

where the last inequality holds due to (45) and $p\leq 1/8$. It follows that $\rho_{1}\geq\frac{3}{4}$. If we let $\rho_{2}$ denote the probability that there exits a disconnected node among the next $rK/2$ nodes $rK/2+1,\ldots,rK$, then by symmetry $\rho_{2}\geq\frac{3}{4}$. Therefore $\rho=\rho_{1}\rho_{2}\geq 1/2$, proving the sufficiency of (42).

where $(a)$ follows from (43) and $q^{K}=\left(1-(1-q)\right)^{K}\geq\exp\left(-2(1-q)K\right)$ since $1-q\leq 1/2$. Let $\rho^{\prime}_{2}$ be the probability of having a betrayed node in cluster $2$ and by symmetry $\rho^{\prime}_{2}\geq 3/4$. We thus get $\rho^{\prime}=\rho^{\prime}_{1}\rho^{\prime}_{2}\geq 1/2$, proving the sufficiency of (43). ∎

We can now prove Theorem 2.1 by combining the above three lemmas.

Since $256\leq 2K\leq n$, we have the following relations between the log terms:

Our goal is to show that if the condition (1) or (2) holds, then the minimax error probability is large.

First assume (1) holds. By (36) we know condition (1) implies

$(i)$ If $p\leq 2q$, then (48) implies $K(p-q)^{2}\leq\frac{1}{48}q(1-q)\log(rK)$; it follows from (35) and (47) that $KD(p\|q)\leq\frac{1}{48}\log(rK)\leq\frac{1}{24}\log(n-K)$ and thus Lemma 2 proves the conclusion. $(ii)$ If $p>2q$, (48) implies $Kp\leq\frac{1}{24}\log(rK)\wedge K\leq\min\{\frac{1}{24}K,\frac{1}{12}\log(\frac{rK}{2})\}$ and Lemma 3 proves the conclusion.