Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

Introduction

In this paper, we focus on the following particular cases:

Binary symmetric stochastic block model (assuming $n$ is even):

where $a\neq b$ and $0<\rho<1$ are fixed constants, and study the problem of exactly recovering the clusters (up to a permutation of cluster indices) from the observation of the graph $G$.

Exact cluster recovery under the binary symmetric stochastic block model is studied in and a sharp recovery threshold is found.

Under the binary symmetric stochastic block model (1), if $(\sqrt{a}-\sqrt{b})^{2}>2$,If $b>0$, $(\sqrt{a}-\sqrt{b})^{2}=2$ is also sufficient for exact recovery as shown by . But for $b=0$, since $a=2$, the ER random graph $G(n/2,2\log n/n)$ contains isolated vertices with probability bounded away from zero and exact recovery is impossible. the clusters can be exactly recovered up to a permutation of cluster indices with probability converging to one; if $(\sqrt{a}-\sqrt{b})^{2}<2$, no algorithm can exactly recover the clusters with probability converging to one.

The optimal reconstruction threshold in Theorem 1 is achieved by the maximum likelihood (ML) estimator, which entails finding the minimum bisection of the graph, a problem known to be NP-hard in the worst case [18, Theorem 1.3]. Nevertheless, it has been shown that the optimal recovery threshold can be attained in polynomial time using a two-step procedure : First, apply the partial recovery algorithms in to correctly cluster all but $o(n)$ vertices; Second, flip the cluster memberships of those vertices who do not agree with the majority of their neighbors. It remains open to find a simple direct approach to achieve the exact recovery threshold in polynomial time. It was proved in that a semidefinite programming (SDP) relaxation of the ML estimator succeeds if $(a-b)^{2}>8(a+b)+\frac{8}{3}(a-b)$. Backed by compelling simulation results, it was further conjectured in that the SDP relaxation can achieve the optimal recovery threshold. In this paper, we resolve this conjecture in the positive.

In addition, we prove that the SDP relaxation achieves the optimal recovery threshold for the planted dense subgraph model (2) where the cluster size $K$ scales linearly in $n$. This conclusion is in sharp contrast to the following computational barrier established in : If $K$ grows and $p,q$ decay sublinearly in $n$, attaining the statistical optimal recovery threshold is at least as hard as solving the planted clique problem (See Section 3 for detailed discussions).

Since the initial posting of this paper to arXiv, a number of interesting papers have been posted, some extending or improving our results. Another resolution of the conjecture in was given in independently. A sharp characterization of the threshold for exact recovery for a general class of stochastic block models is derived in , which includes the two cases considered in this paper as special cases. Extensions of this paper appear in , showing SDP provides exact recovery up to the information theoretic threshold for a fixed number of equal sized clusters or two unequal sized clusters. More recently, the preprint shows similar optimality results of SDP for $o(\log n)$ number of equal-sized clusters and establishes optimality results of SDP for a fixed number of clusters with unequal sizes.

Let $A$ denote the adjacency matrix of the graph $G$, $\mathbf{I}$ denote the identity matrix, and $\mathbf{J}$ denote the all-one matrix. We write $X\succeq 0$ if $X$ is positive semidefinite and $X\geq 0$ if all the entries of $X$ are non-negative. Let ${\mathcal{S}}^{n}$ denote the set of all $n\times n$ symmetric matrices. For $X\in{\mathcal{S}}^{n}$, let $\lambda_{2}(X)$ denote its second smallest eigenvalue. For any matrix $Y$, let $\|Y\|$ denote its spectral norm. For any positive integer $n$, let $[n]=\{1,\ldots,n\}$. For any set $T\subset[n]$, let $|T|$ denote its cardinality and $T^{c}$ denote its complement. We use standard big $O$ notations, e.g., for any sequences $\{a_{n}\}$ and $\{b_{n}\}$, $a_{n}=\Theta(b_{n})$ or $a_{n}\asymp b_{n}$ if there is an absolute constant $c>0$ such that $1/c\leq a_{n}/b_{n}\leq c$. Let ${\rm Bern}(p)$ denote the Bernoulli distribution with mean $p$ and ${\rm Binom}(n,p)$ denote the binomial distribution with $n$ trials and success probability $p$. All logarithms are natural and we use the convention $0\log 0=0$.

Stochastic block model

The cluster structure under the binary symmetric stochastic block model can be represented by a vector $\sigma\in\{\pm 1\}^{n}$ such that $\sigma_{i}=1$ if vertex $i$ is in the first cluster and $\sigma_{i}=-1$ otherwise. Let $\sigma^{\ast}$ correspond to the true clusters. Then the ML estimator of $\sigma^{\ast}$ for the case $a>b$ can be simply stated as

which maximizes the number of in-cluster edges minus the number of out-cluster edges. This is equivalent to solving the NP-hard minimum graph bisection problem. Instead, let us consider its convex relaxation similar to the SDP relaxation studied in . Let $Y=\sigma\sigma^{\top}$. Then $Y_{ii}=1$ is equivalent to $\sigma_{i}=\pm 1$ and $\sigma^{\top}\mathbf{1}=0$ if and only if $\langle Y,\mathbf{J}\rangle=0$. Therefore, (3) can be recast as

Notice that the matrix $Y=\sigma\sigma^{\top}$ is a rank-one positive semidefinite matrix. If we relax this condition by dropping the rank-one restriction, we obtain the following convex relaxation of (4), which is a semidefinite program:

We remark that (5) does not rely on any knowledge of the model parameters except that $a>b$; for the case $a<b$, we replace $\mathop{\arg\max}$ in (5) by $\mathop{\arg\min}$. The SDP formulation introduced in is slightly different from ours: it did not impose the constraint $\langle\mathbf{J},Y\rangle=0$ and the objective function is the inner product between a weighted adjacency matrix and $Y.$

Let $Y^{\ast}=\sigma^{\ast}(\sigma^{\ast})^{\top}$ and ${\mathcal{Y}}_{n}\triangleq\{\sigma\sigma^{\top}:\sigma\in\{-1,1\}^{n},\sigma^{\top}\mathbf{1}=0\}$. The following result establishes the optimality of the SDP procedure:

It is worthy to note the relationship between our SDP relaxation and other related formulations that appeared previously in the literature. In fact, (5) coincides with the SDP studied in [14, p. 659] for MIN BISECTION, where a sufficient condition is obtained in [14, Lemma 19] that is not optimal. The SDP relaxation considered in [17, Equation (15)] for MAX BISECTION is equivalent to (5) with max replaced by min (used when $a<b$) and $\langle\mathbf{J},Y\rangle=0$ by $\langle\mathbf{J},Y\rangle\leq 0$. The proof of Theorem 2 shows that this more relaxed version also works. Finally, we note that the SDP used in can be viewed as a penalized version of (5) with $-\frac{1}{2}\langle\mathbf{J},Y\rangle$ added to the objective function.

Theorem 2 naturally extends to the semirandom model considered in , where after a graph is instantiated from the SBM, a monotone adversary can add in-cluster edges and delete cross-cluster edges arbitrarily. Although this process may appear to make the cluster structure more visible, such an adversarial model is known to foil many procedures based on degrees, local search or graph spectrum . By design, the SDP (5) enjoys robustness against such a monotone adversary, which has already been observed in and proved in [9, Lemma 1]. More specifically, let $\widetilde{A}$ denote the adjacency matrix of the altered graph. Whenever $Y^{\ast}$ is the unique maximizer of (5), i.e., $\langle A,Y^{*}\rangle>\langle A,Y\rangle$ for any other feasible $Y$, then $Y^{*}$ is also the unique maximizer of (5) with $A$ replaced by $\widetilde{A}$. To see this, note that, by Cauchy-Schwartz inequality, $Y\succeq 0$ and $Y_{ii}=1$ imply that $|Y_{ij}|\leq 1$ for all $i,j$. Consequently, $\langle\widetilde{A}-A,Y\rangle\leq\sum|\widetilde{A}_{ij}-A_{ij}|=\langle\widetilde{A}-A,Y^{*}\rangle$. Then $\langle\widetilde{A},Y\rangle=\langle A,Y\rangle+\langle\widetilde{A}-A,Y\rangle<\langle A,Y^{*}\rangle+\langle\widetilde{A}-A,Y^{*}\rangle=\langle\widetilde{A},Y^{*}\rangle$, establishing the unique optimality of $Y^{*}$.

Planted dense subgraph model

In this section we turn to the planted dense subgraph model in the asymptotic regime (2), where there exists a single cluster of size $\lfloor\rho n\rfloor$. To specify the optimal reconstruction threshold, define the following function: For $a,b\geq 0$, let

where $\tau^{\ast}\triangleq\frac{a-b}{\log a-\log b}$ if $a,b>0$ and $a\neq b$. We show that if $\rho f(a,b)>1$, exact recovery is achievable in polynomial-time via SDP with probability tending to one; if $\rho f(a,b)<1$, any estimator fails to recover the cluster with probability tending to one regardless of the computational costs. The sharp threshold $\rho f(a,b)=1$ is plotted in Fig. 1 for various values of $\rho$.

We first introduce the maximum likelihood estimator and its convex relaxation. For ease of notation, in this section we use a vector $\xi\in\{0,1\}^{n}$, as opposed to $\sigma\in\{\pm 1\}^{n}$ used in Section 2 for the SBM, as the indicator function of the cluster, such that $\xi_{i}=1$ if vertex $i$ is in the cluster and $\xi_{i}=0$ otherwise. Let $\xi^{\ast}$ be the indicator of the true cluster. Assuming $a>b$, i.e., the vertices in the cluster are more densely connected, the ML estimation of $\xi^{\ast}$ is simply

which maximizes the number of in-cluster edges. Due to the integrality constraints, it is computationally difficult to solve (11), which prompts us to consider its convex relaxation. Note that (11) can be equivalentlyHere (11) and (12) are equivalent in the following sense: for any feasible $\xi$ for (11), $Z=\xi\xi^{\top}$ is feasible for (12); for any feasible $Z,\xi$ for (12), either $\xi$ or $-\xi$ is feasible for (11). formulated as

where the matrix $Z=\xi\xi^{\top}$ is positive semidefinite and rank-one. Removing the rank-one restriction leads to the following convex relaxation of (12), which is a semidefinite program.

We note that, apart from the assumption that $a>b$, the only model parameter needed by the estimator (13) is the cluster size $K$; for the case $a<b$, we replace $\mathop{\arg\max}$ in (13) by $\mathop{\arg\min}$.

Let $Z^{*}=\xi^{*}(\xi^{*})^{\top}$ correspond to the true cluster and define {\mathcal{Z}}_{n}=\big{\{}\xi\xi^{\top}:\xi\in\{0,1\}^{n},\xi^{\top}\mathbf{1}=K\big{\}}. The recovery threshold for the SDP (13) is given as follows.

Under the planted dense subgraph model (2), if

Next we prove a converse for Theorem 3 which shows that the recovery threshold achieved by the SDP relaxation is in fact optimal.

Under the planted dense subgraph model, our investigation of the exact cluster recovery problem thus far in this paper has been focused on the regime where the cluster size $K$ grows linearly with $n$ and $p,q=\Theta(\frac{\log n}{n})$, where the statistically optimal threshold can be attained by SDP in polynomial time. However, this need not be the case if $K$ grows sublinearly in $n$. In fact, the exact cluster recovery problem has been studied in in the following asymptotic regime:

where $c>1$ and $\alpha,\beta\in(0,1)$ are fixed constants. The statistical and computational complexities of the cluster recovery problem depend crucially on the value of $\alpha$ and $\beta$ (see [22, Figure 2] for an illustration):

$\beta>\frac{1}{2}+\frac{\alpha}{2}$: the planted cluster can be perfectly recovered in polynomial-time with high probability via the SDP relaxation (13).In fact, an even looser SDP relaxation than (13) has been shown to exactly recover the planted cluster with high probability for $\beta>\frac{1}{2}+\frac{\alpha}{2}$. See [10, Theorem 2.3].

$\frac{1}{2}+\frac{\alpha}{4}<\beta<\frac{1}{2}+\frac{\alpha}{2}$: the planted cluster can be detected in linear time with high probability by thresholding the total number of edges, but it is conjectured to be computationally intractable to exactly recover the planted cluster.

$\alpha<\beta<\frac{1}{2}+\frac{\alpha}{4}$: the planted cluster can be exactly recovered with high probability via ML estimation; however, no randomized polynomial-time solver exists 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. For various hardness results of problems reducible from the planted clique problem, see and the references within.

$\beta<\alpha$: regardless of the computational costs, no algorithm can exactly recover the planted cluster with vanishing probability of error.

Consequently, assuming the planted clique hardness hypothesis, in the asymptotic regime of (16) when $\alpha\in(0,\frac{2}{3})$ (and, quite possibly, the entire range $(0,1)$), there exists a significant gap between the information limit (recovery threshold of the optimal procedure) and the computational limit (recovery threshold for polynomial-time algorithms). In contrast, in the asymptotic regime of (2), the computational constraint imposes no penalty on the statistical performance, in that the optimal threshold can be attained by SDP relaxation in view of Theorem 3.

Proofs

In this section, we give the proofs of our main theorems. Our analysis of the SDP relies on two key ingredients: the spectrum of Erdős-Rényi random graphs and the tail bounds for the binomial distributions, which we first present.

Let ${\mathcal{G}}(n,p)$ denote the Erdős-Rényi random graph model with the edge probability $p_{ij}=p$ for all $i,j$. Results similar to Theorem 5 have been obtained in for the special case of ${\mathcal{G}}(n,\frac{c_{0}\log n}{n})$ for some sufficiently large $c_{0}$. In fact, Theorem 5 can be proved by strengthening the combinatorial arguments in [15, Section 2.2]. Here we provide an alternative proof using results from random matrices and concentration of measures and a seconder-order stochastic comparison argument from .

where $(a),(d)$ follow from the Jensen’s inequality; $(b)$ follows because $C-C^{\prime}$ has the same distribution as $(C-C^{\prime})\circ M$, where $\circ$ denotes the element-wise product; $(c),(f)$ follow from the triangle inequality; $(e)$ follows from the fact that $D-D^{\prime}$ has the same distribution as $E-E^{\prime}$. Then, we apply the result of Seginer which characterized the expected spectral norm of i.i.d. random matrices within universal constant factors. Let $X_{j}\triangleq\sum_{i=1}^{n}E_{ij}^{2}$, which are independent ${\rm Binom}(n,p)$. Since $\mu$ is symmetric, [33, Theorem 1.1] and Jensen’s inequality yield

for some universal constant $\kappa$. In view of the following Chernoff bound for the binomial distribution [27, Theorem 4.4]:

for all $t\geq 6np$, setting $t_{0}=6\max\{np/\log n,1\}$ and applying the union bound, we have

where the last inequality follows from $np\geq c_{0}\log n$. Assembling (17) – (20), we obtain

2 Tail of the Binomial Distribution

Let $k_{n},k_{n}^{\prime}\in[m]$ be such that $k_{n}=\tau\rho\log n+o(\log n)$ and $k^{\prime}_{n}=\tau^{\prime}\rho\log n+o(\log n)$ for some $0\leq\tau\leq a$ and $\tau^{\prime}\geq b$. Then

We use the following non-asymptotic bound on the binomial tail probability [7, Lemma 4.7.2]: For $U\sim{\rm Binom}(n,p)$,

where $\lambda=\frac{k}{n}\in(0,1)$ and $d(\lambda\|p)=\lambda\log\frac{\lambda}{p}+(1-\lambda)\log\frac{1-\lambda}{1-p}$ is the binary divergence function. Then (23) follows from (24) by noting that $d(\frac{k_{n}^{\prime}}{m}\|\frac{b\log n}{n})=(b-\tau^{\prime}\log\frac{b{\rm e}}{\tau^{\prime}}+o(1))\frac{\log n}{n}$.

To prove (22), we use the following bound on binomial coefficients [7, Lemma 4.7.1]:

3 Proofs for the stochastic block model

The following lemma provides a deterministic sufficient condition for the success of SDP (5) in the case $a>b$.

Then $\widehat{Y}_{{\rm SDP}}=Y^{\ast}$ is the unique solution to (5).

where $(a)$ holds because $\langle S^{\ast},Y\rangle\geq 0$; $(b)$ holds because $\langle Y^{\ast},S^{\ast}\rangle=(\sigma^{\ast})^{\top}S^{\ast}\sigma^{\ast}=0$ by (27). Hence, $Y^{\ast}$ is an optimal solution. It remains to establish its uniqueness. To this end, suppose ${\widetilde{Y}}$ is an optimal solution. Then,

where $(a)$ holds because $\langle\mathbf{J},{\widetilde{Y}}\rangle=0$; $(b)$ holds because $\langle A,{\widetilde{Y}}\rangle=\langle A,Y^{\ast}\rangle$ and ${\widetilde{Y}}_{ii}=Y^{*}_{ii}=1$ for all $i\in[n]$. In view of (27), since ${\widetilde{Y}}\succeq 0$, $S^{\ast}\succeq 0$ with $\lambda_{2}(S^{*})>0$, ${\widetilde{Y}}$ must be a multiple of $Y^{*}=\sigma^{\ast}(\sigma^{\ast})^{\top}$. Because ${\widetilde{Y}}_{ii}=1$ for all $i\in[n]$, ${\widetilde{Y}}=Y^{\ast}$. ∎

The theorem is proved first for $a>b$. Let $D^{\ast}=\mathsf{diag}\left\{{d^{\ast}_{i}}\right\}$ with

and choose any $\lambda^{*}\geq\frac{p+q}{2}$. It suffices to show that $S^{*}=D^{\ast}-A+\lambda^{\ast}\mathbf{J}$ satisfies the conditions in Lemma 3 with probability $1-n^{-\Omega(1)}$.

By definition, $d^{\ast}_{i}\sigma_{i}^{\ast}=\sum_{j}A_{ij}\sigma^{\ast}_{j}$ for all $i$, i.e., $D^{\ast}\sigma^{\ast}=A\sigma^{\ast}$. Since $\mathbf{J}\sigma^{\ast}=0$, (27) holds, that is, $S^{*}\sigma^{*}=0$. It remains to verify that $S^{\ast}\succeq 0$ and $\lambda_{2}(S^{\ast})>0$ with probability at least $1-n^{-\Omega(1)},$ which amounts to showing that

Applying the union bound implies that $\min_{i\in[n]}d^{\ast}_{i}\geq\frac{\log n}{\log\log n}$ holds with probability at least $1-n^{1-(\sqrt{a}-\sqrt{b})^{2}/2+o(1)}$. It follows from the assumption $(\sqrt{a}-\sqrt{b})^{2}>2$ and (30) that the desired (29) holds, completing the proof in the case $a>b$.

For simplicity so far we have focused on the case where $p=\frac{a\log n}{n},q=\frac{b\log n}{n}$ with $a,b$ being fixed constants. If we are strictly above the recover threshold, namely, $(\sqrt{a}-\sqrt{b})^{2}>2$, Theorem 2 shows that the probability of error is polynomially small in $n$, which cannot be improved by MLE (though a better exponent is conceivable). Now, if we allow $a=a_{n}$ and $b=b_{n}$ to vary with $n$, the following result for the optimal estimator (MLE) has been obtained in that gives the second-order refinement of Theorem 1: If $a_{n},b_{n}=\Theta(1)$, then clusters can be exactly recovered up to a permutation of cluster indices with probability converging to $1$ if and only if

for some universal constant $C$, which is stronger than the optimal condition (31). It is unclear whether (32) is necessary, nor do we know if SDP requires $(\sqrt{a_{n}}-\sqrt{b_{n}})^{2}-2$ to be positive to succeed.

4 Proofs for the planted densest subgraph model

Then $\widehat{Z}_{{\rm SDP}}=Z^{\ast}$ is the unique solution to (13).

where $(a)$ follows because $\langle S^{\ast},Z\rangle\geq 0$, $\langle D^{\ast},Z-I\rangle\leq 0$, and $\langle B^{\ast},Z\rangle\geq 0$; $(b)$ holds due to $d^{\ast}_{i}(Z^{\ast}_{ii}-1)=0,\forall i$; $(c)$ holds because $B^{\ast}_{ij}Z^{\ast}_{ij}=0,\forall i,j$ and $\langle Z^{\ast},S^{\ast}\rangle=(\xi^{\ast})^{\top}S^{\ast}\xi^{\ast}=0$. Hence, $Z^{\ast}$ is an optimal solution. It remains to establish the uniqueness. To this end, suppose ${\widetilde{Z}}$ is another optimal solution. Then,

where $(a)$ holds because $\langle\mathbf{I},{\widetilde{Z}}\rangle=K$ and $\langle\mathbf{J},{\widetilde{Z}}\rangle=K^{2}$; $(b)$ holds because $\langle A,{\widetilde{Z}}\rangle=\langle A,Z^{\ast}\rangle$, $B^{*},{\widetilde{Z}}\geq 0$, and $\langle D^{*},{\widetilde{Z}}\rangle\leq\sum_{i\in C^{*}}d^{*}_{i}=\langle D^{*},Z^{*}\rangle$ since $d_{i}^{*}\geq 0$ and ${\widetilde{Z}}_{ii}\leq 1$ for all $i\in[n]$. Since ${\widetilde{Z}}\succeq 0$ and $S^{\ast}\succeq 0$ with $\lambda_{2}(S^{\ast})>0$, ${\widetilde{Z}}$ needs to be a multiple of $Z^{\ast}=\xi^{\ast}(\xi^{\ast})^{\top}$. Then ${\widetilde{Z}}=Z^{\ast}$ since $\mathsf{Tr}({\widetilde{Z}})=\mathsf{Tr}(Z^{\ast})=K$. ∎

Define $b^{\ast}_{i}\triangleq\lambda^{\ast}-\frac{1}{K}\sum_{j\in C^{\ast}}A_{ij}$ for $i\notin C^{\ast}$. Let $B^{*}\in{\mathcal{S}}^{n}$ be given by

It suffices to show that $(S^{\ast},D^{\ast},B^{\ast})$ satisfies the conditions in Lemma 4 with probability at least $1-n^{-\Omega(1)}.$

By definition, we have $d^{\ast}_{i}(Z^{\ast}_{ii}-1)=0$ and $B^{\ast}_{ij}Z^{\ast}_{ij}=0$ for all $i,j\in[n]$. Moreover, for all $i\in C^{\ast}$,

where the last equality holds because $B^{\ast}_{ij}=0$ if $(i,j)\in C^{\ast}\times C^{\ast}$; for all $i\notin C^{\ast}$,

where the last equality follows from our choice of $b^{\ast}_{i}$. Hence, $D^{\ast}\xi^{\ast}=A\xi^{\ast}+B^{\ast}\xi^{\ast}-\eta^{\ast}\xi^{\ast}-\lambda^{\ast}K\mathbf{1}$ and consequently $S^{\ast}\xi^{\ast}=0$.

We next show that $D^{\ast}\geq 0$, $B^{\ast}\geq 0$ with probability at least $1-n^{-\Omega(1)}.$ It follows from Theorem 5 that $\eta^{\ast}\leq c^{\prime}\sqrt{\log n}$ with probability at least $1-n^{-\Omega(1)}$ for some positive constant $c^{\prime}$ depending only on $a$. Furthermore, let $X_{i}\triangleq\sum_{j\in C^{\ast}}A_{ij}$. Then $X_{i}\sim{\rm Binom}(K-1,\frac{a\log n}{n})$ if $i\in C^{\ast}$ and ${\rm Binom}(K,\frac{b\log n}{n})$ otherwise. We divide the analysis into two separate cases. First consider the case $b=0$, then $X_{i}=0$ for all $i\notin C^{\ast}$. Since $\tau^{\ast}=0$ in this case, $\min_{i\notin C^{\ast}}b_{i}^{\ast}=0$ holds automatically. For any $i\in C^{\ast}$, applying Lemma 2 with $\tau=0$ yields

By definition, $f(a,b)=a-\tau^{\ast}\log\frac{{\rm e}a}{\tau^{\ast}}=b-\tau^{\ast}\log\frac{{\rm e}b}{\tau^{\ast}}$ in this case. Applying the union bound implies that with probability at least $1-n^{1-\rho f(a,b)+o(1)}$,

Since $\sqrt{\log n}=o(\frac{\log n}{\log\log n})$ and $\rho f(a,b)>1$ by the assumption (14), it follows that with probability at least $1-n^{-\Omega(1)},$ $\min_{i\in C^{\ast}}d_{i}^{\ast}\geq 0$ and $\min_{i\notin C^{\ast}}b_{i}^{\ast}\geq 0$.

It remains to verify $S^{\ast}\succeq 0$ with $\lambda_{2}(S^{\ast})>0$ with probability at least $\geq 1-n^{-\Omega(1)}$, i.e.,

It follows that for any $x\perp\sigma^{\ast}$ and $\|x\|=1$,

where $(a)$ holds because $B^{\ast}_{ij}=0$ for all $i,j\notin C^{\ast}$ and

To lower bound the worst-case probability of error, consider the Bayesian setting where the planted cluster $C^{\ast}$ is uniformly chosen among all $K$-subsets of $[n]$ with $K=\lfloor\rho n\rfloor$. If $a=b$, then the cluster is unidentifiable from the graph.

Next, we prove the theorem first for the case $a>b$. If $b=0$, then perfect recovery is possible if and only if the subgraph formed by the vertices in cluster, which is ${\mathcal{G}}(K,a\log n/n)$, contains no isolated vertex.To be more precise, if there is an isolated vertex in the cluster $C^{*}$, then the likelihood has at least $n-K$ maximizers, which, in turn, implies that the probability of exact recovery for any estimator is at most $\frac{1}{n-K}$. This occurs with high probability if $\rho a<1$ .

By symmetry, we can condition on $C^{*}$ being the first $K$ vertices. Let $T$ denote the set of first $\lfloor\frac{\rho n}{\log^{2}n}\rfloor$ vertices. Then

completing the proof in the case $a>b>0$.

completing the proof for the case $0<a<b$. ∎

Appendix A The sharpness of the condition for Theorem 5

Consider the case where $A$ is the adjacency matrix of ${\mathcal{G}}(n,p)$. We show that if $p=o(\frac{\log n}{n})$ and $p=n^{-1+o(1)}$, then

where $X_{i}{\stackrel{{\scriptstyle\text{i.i.d.}}}{{\sim}}}{\rm Binom}(n/2,p)$. Using the inequality $\binom{n}{k}\geq\left(\frac{n}{k}\right)^{k}$ for $k\geq 0$ with the convention that $0^{0}=0$,

Since $\log(1-x)\geq-2x$ for $x\in[0,1/2]$, it follows that

Plugging $k^{\ast}\triangleq\lfloor\frac{\log n}{\log\left(\log n/(np)\right)}\rfloor$ into (38), we get that

where the last inequality follows due to $np=o(k^{\ast})$ since $np=o(\log n)$ and $\log(\log n/(np))=o(\log n)$ since $np=n^{o(1)}$, By the independence of $\{X_{i},i\in[n/2]\}$, we have

where the last inequality follows in view of (40).

References