Information Limits for Recovering a Hidden Community

Introduction

Many modern datasets can be represented as networks with vertices denoting the objects and edges (sometimes weighted or labeled) encoding their pairwise interactions. An interesting problem is to identify a group of vertices with atypical interactions. In social network analysis, this group can be interpreted as a community with higher edge connectivities than the rest of the network; in microarray experiments, this group may correspond to a set of differentially expressed genes. To study this problem, we investigate the following probabilistic model considered in .

Let $C^{*}$ be drawn uniformly at random from all subsets of $[n]$ of cardinality $K$. Given probability measures $P$ and $Q$ on a common measurable space, let $A$ be an $n\times n$ symmetric matrix with zero diagonal where for all $1\leq i<j\leq n$, $A_{ij}$ are mutually independent, and $A_{ij}\sim P$ if $i,j\in C^{*}$ and $A_{ij}\sim Q$ otherwise.

In this paper we assume that we only have access to pairwise information $A_{ij}$ for distinct indices $i$ and $j$ whose distribution is either $P$ or $Q$ depending on the community membership; no direct observation about the individual indices is available (hence the zero diagonal of $A$). Two choices of $P$ and $Q$ arising in many applications are the following:

Bernoulli case: $P={\rm Bern}(p)$ and $Q={\rm Bern}(q)$ with $p\neq q$. When $p>q$, this coincides with the planted dense subgraph model studied in , which is also a special case of the general stochastic block model with a single community. In this case, the data matrix $A$ corresponds to the adjacency matrix of a graph, where two vertices are connected with probability $p$ if both belong to the community $C^{\ast}$, and with probability $q$ otherwise. Since $p>q$, the subgraph induced by $C^{\ast}$ is likely to be denser than the rest of the graph.

Gaussian case: $P={\mathcal{N}}(\mu,1)$ and $Q={\mathcal{N}}(0,1)$ with $\mu\neq 0$. This corresponds to a symmetric version of the submatrix localization problem studied in .The previously studied submatrix localization model (also known as noisy biclustering) deals with submatrices whose row and column supports need not coincide and the noise matrix is asymmetric consisting of iid entries throughout. Here we focus on locating principal submatrices contaminated by a symmetric noise matrix. Additionally, we assume the diagonal does not carry any information. If instead we assume nonzero diagonal with $A_{ii}\sim{\mathcal{N}}(\mu,1)$ if $i\in C^{*}$ and $A_{ii}\sim{\mathcal{N}}(0,1)$ if $i\notin C^{*}$, the results in this paper carry over with minor modifications explained in Remark 11. When $\mu>0$, the entries of $A$ with row and column indices in $C^{\ast}$ have positive mean $\mu$ except those on the diagonal, while the rest of the entries have zero mean.

Given the data matrix $A$, the problem of interest is to accurately recover the underlying community $C^{\ast}$. The distributions $P$ and $Q$ as well as the community size $K$ depend on the matrix size $n$ in general. For simplicity we assume that these model parameters are known to the estimator. The only assumptions on the community size $K$ we impose are that $K/n$ is bounded away from one, and, to avoid triviality, that $K\geq 2$. Of particular interest is the case of $K=o(n),$ where the community size grows sublinearly.

We focus on the following two types of recovery guarantees.Exact and weak recovery are called strong consistency and weak consistency in , respectively. Let $\xi\in\{0,1\}^{n}$ denote the indicator of the community such that ${\rm supp}(\xi)=C^{*}$. Let $\widehat{\xi}=\widehat{\xi}(A)\in\{0,1\}^{n}$ be an estimator.

Estimator $\widehat{\xi}$ weakly recovers $\xi$ if, as $n\to\infty$, $d_{H}(\xi,\widehat{\xi})/K\to 0$ in probability, where $d_{H}$ denotes the Hamming distance.

Intuitively, for a fixed network size $n$, as the community size $K$ decreases, or the distributions $P$ and $Q$ get closer together, the recovery problem becomes harder. In this paper, we aim to address the following question: From an information-theoretic perspective, computational considerations aside, what are the fundamental limits of recovering the community? Specifically, we derive sharp necessary and sufficient conditions in terms of the model parameters under which the community can be exactly or weakly recovered. These results serve as benchmarks for evaluating practical algorithms and aid us in understanding the performance limits of polynomial-time algorithms.

In addition to establishing information limits with sharp constants for general $P$ and $Q$, we identify the following algorithmic connection between weak and exact recovery: If exact recovery is information-theoretically possible and there is an algorithm for weak recovery, then in linear additional time we can obtain exact recovery based on the weak recovery algorithm. This suggests that if the information limit of weak recovery can be obtained in polynomial time, then so can exact recovery; conversely, if there exists a computational barrier that separates the information limit and the performance of polynomial-time algorithms for exact recovery, then weak recovery also suffers from such a barrier. To establish the connection, we apply a two-step procedure: the first step uses an estimator capable of weak recovery, even in the presence of a slight mismatch between $|C^{\ast}|$ and $K$, such as the maximum likelihood estimator (see Lemma 4); the second step cleans up the residual errors through a local voting procedure for each index. In order to ensure the first and second step are independent, we use a method which we call successive withholding. The method of successive withholding is to randomly partition the set of indices into a finite number of subsets. One at a time, one subset is withheld to produce a reduced set of indices, and an estimation algorithm is run on the reduced set of indices. The estimate obtained from the reduced set of indices is used to classify the indices in the withheld subset. The idea is to gain independence: the outcome of estimation based on the reduced set of indices is independent of the data between the withheld indices and the reduced set of indices, and the withheld subset is sufficiently small so that we can still obtain sharp constants. This method is mentioned in , and variations of it have been used in , , and .

Previous work has determined the information limits for exact recovery up to universal constant factors for some choices of $P$ and $Q$. For the Bernoulli case, it is shown in that if $Kd(q\|p)-c\log K\to\infty$ and $Kd(p\|q)\geq c\log n$ for some large constant $c>0$, then exact recovery is achievable via the maximum likelihood estimator (MLE); conversely, if $Kd(q\|p)\leq c^{\prime}\log K$ and $Kd(p\|q)\leq c^{\prime}\log n$ for some small constant $c^{\prime}>0$, then exact recovery is impossible for any algorithms. Similarly, for the Gaussian case, it is proved in that if $K\mu^{2}\geq c\log n$, then exact recovery is achievable via the MLE; conversely, if $K\mu^{2}\leq c^{\prime}\log n$, exact recovery is impossible for any algorithms. To the best of our knowledge, there are only a few special cases where the information limits with sharp constants are known:

Bernoulli case with $p=1$ and $q=1/2$: It is widely known as the planted clique problem . If $K\geq 2(1+\epsilon)\log_{2}n$ for any $\epsilon>0$, exact recovery is achievable via the MLE; if $K\leq 2(1-\epsilon)\log_{2}n$, then exact recovery is impossible. Despite an extensive research effort polynomial-time algorithms are only known to achieve exact recovery for $K\geq c\sqrt{n}$ for any constant $c>0$ .

Bernoulli case with $p=a\log n/n$ and $q=b\log n/n$ for fixed $a,b$ and $K=\rho n$ for a fixed constant $0<\rho<1$. The recent work finds an explicit threshold $\rho^{*}(a,b)$, such that if $\rho>\rho^{*}(a,b)$, exact recovery is achievable in polynomial-time via semi-definite relaxations of the MLE with probability tending to one; if $\rho<\rho^{*}(a,b)$, any estimator fails to exactly recover the cluster with probability tending to one regardless of the computational costs. This conclusion is in sharp contrast to the computational barriers observed in the planted clique problem.

The paper of Butucea et al. gives sharp results for a Gaussian submatrix recovery problem similar to the one considered here – see Remark 7 for details.

While this paper focuses on information-theoretic limits, it complements other work investigating computationally efficient recovery procedures, such as convex relaxations , spectral methods , and message-passing algorithms . In particular, for both the Bernoulli and Gaussian cases:

if $K=\Theta(n)$, a linear-time degree-thresholding algorithm achieves the information limit of weak recovery (see [22, Appendix A] and [24, Appendix A]);

if $K=\omega(n/\log n)$, whenever information-theoretically possible, exact recovery can be achieved in polynomial time using semi-definite programming ;

if $K\geq\frac{n}{\log n}(1/(8e)+o(1))$ for Gaussian case and $K\geq\frac{n}{\log n}(\rho_{\sf BP}(a/b)+o(1))$ for Bernoulli case,Here $\rho_{\sf BP}(a/b)$ denotes a constant only depending on $a/b$. exact recovery can be attained in nearly linear time via message passing plus clean up whenever information-theoretically possible.

However, it is an open problem whether any polynomial time can achieve the respective information limit of weak recovery for $K=o(n)$, or exact recovery for $K\leq\frac{n}{\log n}(1/(8e)-\epsilon)$ in the Gaussian case and for $K\leq\frac{n}{\log n}(\rho_{\sf BP}(a/b)-\epsilon)$ in the Bernoulli case, for any fixed $\epsilon>0$.

The related work studies weak recovery in the sparse regime of $p=a/n$, $q=b/n$, and $K=\kappa n$. In the iterated limit where first $n\to\infty$, and then $\kappa\to 0$ and $a,b\to\infty$, with $\lambda=\frac{\kappa^{2}(a-b)^{2}}{(1-\kappa)b}$ fixed, it is shown that a local algorithm, namely local belief propagation, achieves weak recovery in linear time if $\lambda{\rm e}>1$ and conversely, if $\lambda{\rm e}<1$, no local algorithm can achieve weak recovery. Moreover, it is shown that for any $\lambda>0$, MLE achieves a recovery guarantee similar to weak recovery in Definition 3. In comparison, the sharp information limit for weak recovery identified in Corollary 1 below allows $p,q$ and $K$ to vary simultaneously with $n$ as $n\to\infty$.

Finally, we briefly compare the results of this paper to those of and on the planted bisection model (also known as the binary symmetric stochastic block model), where the vertices are partitioned into two equal-sized communities. First, a necessary and sufficient condition for weak recovery and a necessary and sufficient condition for exact recovery are obtained in . In this paper, sufficient and necessary conditions, (7) and (8) in Theorem 1, are presented separately. These conditions match up except right at the boundary; we do not determine whether recovery is possible exactly at the boundary. The result for exact recovery in is similar in that regard. Perhaps future work, based on techniques from , can provide a more refined analysis for the recovery problem at the boundary. Secondly, when recovery is information theoretically possible for the planted bisection problem, efficient algorithms are shown to exist in and . In contrast, for detecting or recovering a single community whose size is sublinear in the network size, there can be a significant gap between what is information theoretically possible and what can be achieved by existing efficient algorithms (see ). We turn instead to the MLE for proof of optimal achievability. Finally, this paper covers both the Gaussian and Bernoulli case (and other distributions) in a unified framework without assuming that the community size scales linearly with the network size.

Overview of Main Results

Let $\widehat{C}_{\rm ML}$ denote the maximum likelihood estimation (MLE) of $C^{*},$ given by:

Our results require mild regularity conditions on the size of the hidden community $K$ and on the pair of distributions, $P$ and $Q.$ Specifically, for $K$, it is assumed without further comment that

This assumption implies that $\frac{\log n}{\log(n-K)}\to 1$, so in several asymptotic results $\log n$ and $\log(n-K)$ are interchangeable; we give preference to $\log n$. Also, to avoid triviality, it is assumed throughout that $K\geq 2.$

In particular, $E_{P}$ and $E_{Q}$ are convex functions. Moreover, since $\psi_{Q}^{\prime}(0)=-D(Q\|P)$ and $\psi_{Q}^{\prime}(1)=D(P\|Q)$, we have $E_{Q}(-D(Q\|P))=E_{P}(D(P\|Q))=0$ and hence $E_{Q}(D(P\|Q))=D(P\|Q)$ and $E_{P}(-D(Q\|P))=D(Q\|P)$. Our regularity assumption on the pair $P$ and $Q$ is the following.

There exists a constant $C$ such that for all $n$,

In general, $\psi_{Q}^{\prime\prime}(\lambda)=\psi_{P}^{\prime\prime}(\lambda-1)=\mathsf{var}_{Q_{\lambda}}(L),$ where $Q_{\lambda}$ is the tilted distribution defined by $dQ_{\lambda}=\exp(\lambda L-\psi_{Q}(\lambda))dQ,$ so the point of Assumption 1 is to require these quantities for $\lambda\in$ be bounded by a constant times the divergences. Assumption 1 is the strongest condition imposed on $P$ and $Q$ in this paper; several of the results hold under weaker assumptions described in Section 3, which are also weaker than sub-Gaussianity of the LLR.

Assumption 1 is fulfilled in the following cases:

Bounded LLR: Lemma 1 in Section 3 shows that Assumption 1 holds if $L$ is bounded by a constant, which, in particular, holds in the Bernoulli case if both $\frac{p}{q}$ and $\frac{\bar{p}}{\bar{q}}$ are bounded away from zero and infinity.

Gaussian case: In the Gaussian case $P={\mathcal{N}}(\mu,1),Q={\mathcal{N}}(0,1)$, we have $L(x)=\mu(x-\frac{\mu}{2})$, $D(P\|Q)=D(Q\|P)=\mu^{2}/2$, $\psi_{Q}(\lambda)=\frac{(\lambda^{2}-\lambda)\mu^{2}}{2}$, $E_{Q}(\theta)=\frac{1}{8}(\mu+\frac{2\theta}{\mu})^{2}$ and $E_{P}(\theta)=E_{Q}(-\theta)$. In particular, $\psi^{\prime\prime}_{Q}(\lambda)\equiv\mu^{2}$ so Assumption 1 holds with $C=2$ regardless of how $\mu$ varies with $n$. More generally, for $P$ and $Q$ lying in the same exponential family, Appendix B provides a simple sufficient condition to verify Assumption 1.

2 Weak Recovery

The following theorem is our main result about weak recovery. It gives a sufficient condition and a matching necessary condition for weak recovery.

The assumption $K\geq 2,$ implies $K/2\leq K-1\leq K$, so the first parts of (7) and (8) would have the same meaning if $K$ were replaced by $K-1$. In the special case of bounded LLR, the factor $K-1$ in the second parts of (7) and (8) can be replaced by $K$. This is because if $\log\frac{dP}{dQ}$ is bounded, so is $D(P\|Q)$, and $KD(P\|Q)\to\infty$ implies $K\to\infty$ and hence also $(K-1)/K\to 1$.

Suppose the ratios $\log\frac{p}{q}$ and $\log\frac{\bar{p}}{\bar{q}}$ are bounded. If

then weak recovery is possible. If weak recovery is possible, then

Condition (10) is necessary even if $p/q\to\infty,$ but (9) alone is not sufficient without the assumption that $p/q$ is bounded. This can be seen by considering the extreme case where $K=n/2$, $p=1/n$, and $q={\rm e}^{-n}$. In this case, condition (9) is clearly satisfied; however, the subgraph induced by index in the cluster is an Erdős-Rényi random graph with edge probability $1/n$ which contains at least a constant fraction of isolated vertices with probability converging to one as $n\to\infty$. It is not possible to correctly determine whether the isolated vertices are in the cluster, hence the impossibility of weak recovery.

then weak recovery is possible. If weak recovery is possible, then

3 Exact Recovery

The following theorem states our main result about exact recovery. It gives a sufficient condition and a matching necessary condition for exact recovery. Since exact recovery implies weak recovery, conditions from Theorem 1 naturally enter.

Suppose Assumption 1 holds. If (7) and the following hold:

In the special case of linear community size, i.e., $K=\Theta(n)$, (13) and (14) can be simplified by replacing $E_{Q}\left(\frac{1}{K}\log\frac{n}{K}\right)$ by the Chernoff index between $P$ and $Q$ :

To see this, note that in the definition $E_{Q}(\theta)$ in (5) the supremum can be restricted to $\lambda\in$ and hence $E_{Q}(\theta)\leq E_{Q}(\theta+\delta)\leq E_{Q}(\theta)+\delta$ as long as $-D(Q\|P)\leq\theta\leq\theta+\delta\leq D(P\|Q)$. By (7), $\delta=\frac{1}{K}\log\frac{n}{K}\leq D(P\|Q)$ for all sufficiently large $n$. Hence, in the case of $K=\Theta(n)$, $C(P,Q)\leq E_{Q}\left(\frac{1}{K}\log\frac{n}{K}\right)\leq C(P,Q)+\Theta(\frac{1}{n}),$ proving the claim. The Chernoff index $C(P,Q)$ gives the optimal exponent for decay of sum of error probabilities for the binary hypothesis testing problem in the large-sample limit.

Suppose $\log\frac{p}{q}$ and $\log\frac{\bar{p}}{\bar{q}}$ are bounded. If (9) holds, and

then exact recovery is possible. If exact recovery is possible, then (10) holds, and

In the Bernoulli case, $E_{P}(\theta)=d(\alpha\|p)$ and $E_{Q}(\theta)=d(\alpha\|q)$, where $\alpha=(\theta+\log\frac{\bar{q}}{\bar{p}})/\log\frac{p\bar{q}}{q\bar{p}}.$ ∎

Consider the Bernoulli case in the regime

where $s\geq 1$ is fixed, $\rho\in(0,1)$ and $a>b>0$. Let $I(x,y)\triangleq x-y\log({\rm e}x/y)$ for $x,y>0$. Then the sharp recovery thresholds are determined by Corollaries 1 and 3 as follows: For any $\epsilon>0$,

For $s>1$, if $\rho I(b,a)\geq{\frac{(2+\epsilon)(s-1)\log\log n}{\log n}}$, then weak recovery is possible; if $\rho I(b,a)\leq{\frac{(2-\epsilon)(s-1)\log\log n}{\log n}}$, then weak recovery is impossible. For $s=1$, weak recovery is possible if and only if $\rho I(b,a)=\omega(\frac{1}{\log n})$.

Assume $\rho,a,b$ are fixed constants. Let $\tau_{0}=(a-b)/\log(a/b)$. Then exact recovery is possible if $\rho I(b,\tau_{0})>1$; conversely, if $\rho I(b,\tau_{0})<1$, then exact recovery is impossible, generalizing the previous results of for linear community size ($s=1$). To see this, note that by definition, $\tau^{\ast}=(1+o(1))\tau_{0}\log^{s}n/n$, and thus $d(\tau^{\ast}\|q)=(1+o(1))I(b,\tau_{0})\log^{s}n/n$.

The recent work considered a generalized planted bisection model where $A_{ij}\sim P$ if $i,j$ are in the same community and $Q$ if otherwise. Their result applies to the following generalization of the Bernoulli distribution, where $P=(p_{0},\ldots,p_{m})$ and $Q=(q_{0},\ldots,q_{m})$ with $p_{i}=\frac{a_{i}\log n}{n},q_{i}=\frac{b_{i}\log n}{n},1\leq i\leq m$ for some $m\geq 1$ and positive constants $a_{i},b_{i},$ $1\leq i\leq m$. For this family of distribution the LLR is bounded and hence Theorem 2 gives the sharp condition for recovering a single hidden community. Specifically, note that \psi_{Q}(\lambda)=\big{(}\sum_{i=1}^{m}a_{i}^{\lambda}b_{i}^{\bar{\lambda}}-a_{i}\lambda-b_{i}\bar{\lambda}+o(1)\big{)}\frac{\log n}{n}. Thus for $K=\rho n$ with a fixed $\rho$, the sharp threshold of exact recovery is given by \rho\sup_{0<\lambda<1}\big{(}\sum_{i=1}^{m}a_{i}\lambda+b_{i}\bar{\lambda}-a_{i}^{\lambda}b_{i}^{\bar{\lambda}}\big{)}>1. For $m=1$ with $a_{1}=a$ and $b_{1}=b$, the optimal $\lambda$ is determined by $a^{\lambda}b^{\bar{\lambda}}=(a-b)/\log(a/b)=\tau_{0}$, and the sharp threshold of exact recovery simplifies to $\rho I(b,\tau_{0})>1$, recovering the result for the Bernoulli case given in Remark 4.

then exact recovery is possible. If exact recovery is possible, then (12) holds and

See Appendix C for a proof of Corollary 4.

where $s\geq 1$ and $\rho\in(0,1)$ are fixed constants. The critical signal strength that allows weak or exact recovery is determined by Corollaries 2 and 4 as follows: For any $\epsilon>0$,

For $s>1$, if $\mu_{0}>(2+\epsilon)\sqrt{\frac{(s-1)\log\log n}{\rho\log n}}$, then weak recovery is possible; conversely, if $\mu_{0}<(2-\epsilon)\sqrt{\frac{(s-1)\log\log n}{\rho\log n}}$, then weak recovery is impossible. For $s=1$, weak recovery is possible if and only if $\mu_{0}=\omega(\frac{1}{\sqrt{\log n}})$.

If $\mu_{0}>\sqrt{\frac{8+\epsilon}{\rho}}$, then exact recovery is possible; conversely, If $\mu_{0}<\sqrt{\frac{8-\epsilon}{\rho}}$, then exact recovery is impossible.

Butucea et al. considers the submatrix localization model with an $n\times m$ submatrix with an elevated mean in an $N\times M$ large Gaussian random matrix with independent entries, and gives sufficient conditions and necessary conditions, matching up to constant factors, for exact recovery, which are analogous to those of Corollary 4. Setting $(n,m,N,M)$ in [9, (2.3)] (sufficient condition for exact recovery of rectangular submatrix) equal to $(K,K,n,n)$ gives precisely the sufficient condition of Corollary 4 for exact recovery of a principal submatrix of size $K$ from symmetric noise. This coincidence can be understood as follows. The nonsymmetric observations of [9, (2.3)] in the case of parameters $(K,K,n,n)$ yield twice the available information as the symmetric observation matrix we consider (diagonal observations excluded) while the amount of information required to specify a $K\times K$ (not necessarily principal) submatrix of an $n\times n$ matrix is twice the information needed to specify a principal one. The proof techniques of are similar to ours, with the main difference being that we simultaneously investigate conditions for weak and exact recovery. Finally, the information limits of weak recovery for biclustering are established in [24, Section 4.1] based on modifications of the arguments in .

If $K\leq n^{1/9}$, (11) implies (19), and thus (11) alone is sufficient for exact recovery; if $K\geq n^{1/9}$, then (19) implies (11), and (19) alone is sufficient for exact recovery.

The reminder of the paper is organized as follows. Section 3 gives some preliminaries. Section 4 proves Theorem 1, pertaining to weak recovery, and Section 5 proves Theorem 2, pertaining to exact recovery. Additional results are introduced in Section 5, which highlight alternative sufficient and necessary conditions for exact recovery involving large deviation probabilities for sums of random variables, related to the voting procedure mentioned in the introduction.

On the Assumptions on P𝑃P and Q𝑄Q

This section presents some conditions sufficient for Assumption 1, and some implications of Assumption 1.

If $|L|\leq B$ for some positive constant $B$, then Assumption 1 holds with $C=2{\rm e}^{5B}$.

First, some background. Let $\phi(y)=e^{y}-1-y$, which is nonnegative, convex, with $\phi(0)=\phi^{\prime}(0)=0$ and $\phi^{\prime\prime}(y)=e^{y}$. Thus for $|y|\leq B$, $e^{-B}\leq\phi^{\prime\prime}(y)\leq e^{B}$ and hence $\frac{e^{-B}y^{2}}{2}\leq\phi(y)\leq\frac{e^{B}y^{2}}{2}$.

Now to the proof. We begin by noticing that for all $\lambda\in$,

In turn, using $y^{2}\leq 2e^{B}\phi(y)$ as shown above and recalling that $L=\log\frac{dP}{dQ}$, we have

Combining the last two displayed equations yields $\psi^{\prime\prime}_{Q}(\lambda)\leq 2{\rm e}^{3B}D(Q\|P)$ for $\lambda\in$. Abbreviate $\psi_{Q}$ by $\psi$. By a variation of the argument above, we have

so that $\psi^{\prime\prime}(\lambda)\leq 2{\rm e}^{5B}D(Q\|P)$ for $\lambda\in$. Let $\widetilde{\psi}$ denote the version of $\psi$ that would be obtained if the roles of $P$ and $Q$ were swapped. Then $\widetilde{\psi}^{\prime\prime}(\lambda)\leq 2{\rm e}^{5B}D(P\|Q)$ for $\lambda\in$. Since $\psi$ and $\widetilde{\psi}$ are related by reflection about $\lambda=1/2$: $\psi(\lambda)\equiv\widetilde{\psi}(1-\lambda)$, we have $\psi^{\prime\prime}(\lambda)\leq 2{\rm e}^{5B}D(P\|Q)$ for $\lambda\in$, completing the proof. ∎

As shown in the proofs, Theorem 1 (weak recovery), and the sufficiency part of Theorem 2 (exact recovery) hold under assumptions somewhat weaker than Assumption 1; only the necessity part of Theorem 2 relies on Assumption 1. To clarify this subtlety, we introduce two successively weaker assumptions. We also provide a lemma showing that any of the assumptions imply the equivalence $D(P\|Q)\asymp D(Q\|P)\asymp C(P,Q)$.

Assumption 1 implies Assumption 2 which implies Assumption 3, with the same constant $C$ throughout. Any of these assumptions implies that:

and hence also that $D(P\|Q)\asymp D(Q\|P)\asymp C(P,Q)$.

Assumption 1 $\Rightarrow$ Assumption 2: Condition (21) is implied by Assumption 1 because $\psi_{P}(0)=0,$ and $\psi_{P}^{\prime}(0)=D(P\|Q)$, so by the integral form of Taylor’s theorem, $\psi_{P}(\lambda)-D(P\|Q)\lambda$ is $\lambda^{2}/2$ times a weighted average of $\psi_{P}^{\prime\prime}$ over the interval $[\lambda,0]$ for $\lambda\in$. Similarly, (22) is implied by Assumption 1 because $\psi_{Q}(\lambda)+D(Q\|P)\lambda$ is a weighted average of $\psi_{Q}^{\prime\prime}$ over the interval with endpoints and $\lambda,$ for $\lambda\in$.

Assumption 2 $\Rightarrow$ Assumption 3: Since $\psi_{P}(-1)=\psi_{Q}(1)=0,$ either (21) or (22) imply that $C\geq 2,$ which is achieved in the Gaussian case. Condition (21) implies

where the supremum is attained at $\lambda=\frac{-\eta}{C}$ which belongs to $$by the fact$C\geq 2$. So (21) implies (23). The proof that (22) implies (24) is similar.

Assumption 3 $\Rightarrow$ (25): Taking $\eta=1$ in (23) and (24) we get $C(P,Q)\geq\frac{1}{2C}\max\{D(P\|Q),D(Q\|P)\}$. In the other direction, $D(P\|Q)=E_{Q}(D(P\|Q))\geq E_{Q}(0)=C(P,Q)$ and, similarly, $D(Q\|P)\geq C(P,Q)$. ∎

Recall the Chernoff upper bounds (3) and (4) on the probability of large deviations, which hold non-asymptotically for any sample size $n$ and any pair $P$ and $Q$. To prove the necessary condition for exact recovery, we need a lower bound with matching exponent. Such a result is well-known for fixed distributions. Indeed, the sharp asymptotics of large deviation is given by the Bahadur-Rao theorem (see, e.g., [17, Theorem 3.7.4]); however, this result is not applicable in the hidden community problem because both $P$ and $Q$ can vary with $n$. The following lemma provides a non-asymptotic information-theoretic lower bound (cf. [36, Theorem 11.1] and [15, Eq. (5.21), p. 167]):

If $-D(Q\|P)\leq\gamma<\gamma+\delta\leq D(P\|Q)$, then

The left inequality in (26) is the Chernoff bound (3); it remains to prove the right inequality. Let $E_{n}=\left\{\sum_{k=1}^{n}L_{k}>n\gamma\right\}$. For any $Q^{\prime}$, the data processing inequality of KL divergence gives

Using the lower bound for the binary divergence $d(p\|q)=-h(p)+p\log\frac{1}{q}+(1-p)\log\frac{1}{1-q}\geq-\log 2+p\log\frac{1}{q}$ yields

If Assumption 1 holds and $-D(Q\|P)\leq\gamma<\gamma+\delta\leq D(P\|Q)$:

Weak Recovery for General P/Q𝑃𝑄P/Q Model

Theorem 1 is proved in Section 4.1. Section 4.2 provides a modification of the sufficiency part of Theorem 1 giving a sufficient condition for weak recovery with random cluster size; it is used in Section 5 to prove sufficient conditions for exact recovery.

The sufficiency proof only uses (23) while the necessity proof only uses (24). The sufficiency proof is based on analyzing the MLE via a delicate application of union bound and large deviation upper bounds (3) and (4). For the necessary part, the proof for the first condition in (8) uses a genie argument and the theory of binary hypothesis testing, while the proof of the second condition in (8) is based on mutual information and rate-distortion function.

By the assumption (7), we have $(K-1)D(P\|Q)(1-\eta)\geq 2\log\frac{n}{K}$ for some $\eta\in(0,1)$. Choose $\theta=(1-\eta)D(P\|Q)$. By the assumption (23), we have

Using the fact that $E_{P}(\theta)=E_{Q}(\theta)-\theta$, we have

Therefore, in view of $\epsilon=1/\sqrt{KD(P\|Q)}$, it follows that $E\triangleq\min\{E_{1},E_{2}\}=\Omega(KD(P\|Q))=\Omega(\epsilon^{-2})$. Hence, in view of (28),

Necessity

Given $i,j\in[n]$, let $\xi_{\backslash i,j}$ denote $\{\xi_{k}\colon k\neq i,j\}$. Consider the following binary hypothesis testing problem for determining $\xi_{i}$. If $\xi_{i}=0$, a node $J$ is randomly and uniformly chosen from $\{j\colon\xi_{j}=1\}$, and we observe $(A,J,\xi_{\backslash i,J})$; if $\xi_{i}=1$, a node $J$ is randomly and uniformly chosen from $\{j\colon\xi_{j}=0\}$, and we observe $(A,J,\xi_{\backslash i,J})$. Note that

Hence, we have $(K-1)D(P\|Q)\to\infty$, which implies $KD(P\|Q)\to\infty$.

Combining the last two displays, we get that $\liminf_{n\to\infty}\frac{(K-1)D(P\|Q)}{\log(n/K)}\geq 2$.

2 A Sufficient Condition For Weak Recovery With Random Cluster Size

Theorem 1 invokes the assumption that $|C^{*}|\equiv K$ and $K$ is known. In the proof of exact recovery, as we will see, we need to deal with the case where $|C^{*}|$ is random and unknown. For that reason, the following lemma gives a sufficient condition for weak recovery with a random cluster size. We shall continue to use $\widehat{C}_{\rm ML}$ to denote the estimator defined by (2), although in this context it is not actually the MLE because $|C^{*}|$ need not be $K$. That is, there is a (slight) mismatch between the problem the estimator was designed for and the problem it is applied to.

Assume that $K\to\infty,$ $\limsup K/n<1,$ and there exists a universal constant $C>0$ such that (23) holds. Furthermore, suppose that

where $\epsilon=1/\sqrt{\min\{\log K,KD(P\|Q)\}}$.

Therefore, $m/m^{\prime}\to 1,$ and, moreover,

By the assumption (7), we have $KD(P\|Q)(1-\eta)\geq 2\log\frac{n}{K}$ for some $\eta\in(0,1)$. Choose $\theta=(1-\eta)D(P\|Q)$. By (23), we have that $E_{P}(\theta)\geq c\eta^{2}KD(P\|Q)$ and $E_{P}(m\theta/m^{\prime})\geq(1+o(1))c\eta^{2}KD(P\|Q)$. Thus,

Using the fact that $E_{P}(\theta)=E_{Q}(\theta)-\theta$, we get that

Exact Recovery for General P/Q𝑃𝑄P/Q Model

The sufficiency and necessity halves of Theorem 2 are proved in Sections 5.1 and 5.2, respectively.

This section proves the sufficiency part of Theorem 2. The proof is based on a two-step procedure for exact recovery, described as Algorithm 1. The first main step of the algorithm (approximate recovery) uses an estimator capable of weak recovery, even with a slight mismatch between $|C^{*}|$ and $K$, such as provided by the ML estimator (see Lemma 4). The second main step cleans up the residual errors through a local voting procedure for each index. In order to make sure the first and second step are independent of each other, we use the method of successive withholding.

This method of proof highlights $\eqref{eq:voting-suff}$ as the sufficient condition for when the local voting procedure succeeds. In fact, it permits us to prove an intermediate result, Theorem 3 below, which can be used to show that weak recovery plus cleanup in linear additional time can be applied to yield exact recovery no matter how the weak recovery step is achieved. In particular, and give conditions for message passing algorithms to achieve weak recovery in (near linear) polynomial time, and they invoke Theorem 3 to note that, if (13) holds, exact recovery can be achieved with the addition of the linear time cleanup step.

The following theorem gives sufficient conditions under which the two-step procedure achieves exact recovery, assuming the first step provides weak recovery.

Suppose $\widetilde{C}$ is produced by Algorithm 1 using estimators for weak recovery $\widehat{C}_{k}$ such that,

The proof of Theorem 3 is given after the following lemma.

Suppose Assumption 1 holds (or the weaker condition (22) holds) and (13) holds. Let $\{X_{i}\}$ denote a sequence of i.i.d. copies of $\log\frac{{\rm d}P}{{\rm d}Q}$ under measure $P$. Let $\{Y_{i}\}$ denote another sequence of i.i.d copies of $\log\frac{{\rm d}P}{{\rm d}Q}$ under measure $Q$, which is independent of $\{X_{i}\}$. Then for $\delta$ sufficiently small and $\gamma=\frac{1}{K}\log\frac{n}{K},$The $o$ in $o(1/K)$ is understood to hold as $n\to\infty.$ Thus, if $K$ is bounded, $o(1/K)$ means $o(1)$ as $n\to\infty.$

By the assumption (13), there exists $\epsilon>0$ sufficiently small such that $KE_{Q}(\gamma)\geq(1+\epsilon)\log n$ for all sufficiently large $n$. We restrict attention to such $n$. First of all,

Then (33) holds as long as $\delta<\frac{\epsilon}{1+\epsilon}$. To show (32), for any $t>0$, the Chernoff bound yields

Since $E_{P}(\gamma)=\sup_{-1\leq\lambda\leq 0}\lambda\gamma-\psi_{P}(\lambda)$, choose $t\in$ so that $\psi_{P}(-t)+\gamma t=-E_{P}(\gamma)=-E_{Q}(\gamma)+\gamma$. Since $\lambda\mapsto\psi_{Q}(\lambda)$ is convex with $\psi_{Q}(0)=\psi_{Q}(1)=0,$ it follows that

where the last inequality follows from (22) with $\lambda=-1$. Note that (24) is implied by (22). It follows from (24) that $E_{Q}(\gamma)\geq E_{Q}(0)\geq\frac{1}{2C}D(Q\|P)$. Together with (34), it yields that $\psi_{Q}(-t)\leq C(C+2)E_{Q}(\gamma)$. Let $C^{\prime}=C(C+2)$. Combining the above gives

where the last inequality follows from the assumption that $KE_{P}(\gamma)=\log K-\log n+KE_{Q}(\gamma)\geq\log K+\epsilon\log n$. Therefore, as long as $(1-(C^{\prime}+2)\delta)(1+\epsilon/2)>1$ and $\delta(1+C^{\prime})\leq(\epsilon/3)/(1+\epsilon/2)$,

Note that the conditions of Lemma 5 are satisfied, so that (32) and (33) hold.

Given $(C_{k}^{*},\widehat{C}_{k})$, each of the random variables $r_{i}\in S_{k}$ for $i\in[n]$ is conditionally the sum of independent random variables, each with either the distribution of $X_{1}$ or the distribution of $Y_{1}$ described in Lemma 5. Furthermore, on the event, ${\cal E}_{k}=\{|\widehat{C}_{k}\triangle C_{k}^{*}|\leq\delta K\},$

If $K$ is bounded, exact recovery is the same as weak recovery, so the sufficiency part of Theorem 2 follows from the sufficiency part of Theorem 1 in that case. So assume for the remainder of the proof that $K\to\infty.$

Since (7) holds and $K\to\infty$, it follows that

where $\epsilon=1/\sqrt{\min\{\log K,KD(P\|Q)\}}$. Since $\delta$ is a fixed constant, by the union bound over all $1\leq k\leq 1/\delta$, we have that

Since $\epsilon\to 0$, the desired (31) holds. ∎

2 The Necessary Condition

The following lemma gives a necessary condition for exact recovery under the general $P/Q$ model expressed in terms of probabilities for certain large deviations. Later in the section the lemma is combined with the large deviations lower bound of Lemma 3 to establish the necessary conditions in Theorem 2. This method parallels the method used in the previous section for establishing the sufficient condition in Theorem 2.

where $\sigma^{2}=K_{o}\mathsf{var}_{P}\left(L_{1}\right)$ and $\mathsf{var}_{P}(L_{1})$ denotes the variance of $L_{1}$ under measure $P$.

Let $i_{0}$ denote the random index such that $i_{0}=\arg\min_{i\in C^{*}}e(i,C^{*})$. Let $F$ denote the event that

and $\theta_{n}^{{}^{\prime\prime}}$ to be

and $\theta^{\prime}_{n},\theta^{{}^{\prime\prime}}_{n}$ are deterministic, it follows that $\theta^{\prime}_{n}>\theta^{\prime\prime}_{n}$ for sufficiently large $n$. Set $\theta_{n}=(\theta^{\prime}_{n}+\theta^{{}^{\prime\prime}}_{n})/2$. Thus $\theta_{n}<\theta^{\prime}_{n}$ and by the definition of $\theta^{\prime}_{n}$, (38) holds. Similarly, we have that $\theta_{n}>\theta^{{}^{\prime\prime}}_{n}$ and by the definition of $\theta^{{}^{\prime\prime}}_{n}$, (39) holds.

For all $i\in C^{\ast}$, $e(i,C^{\ast})$ has the same distribution as $\sum_{i=1}^{K-1}L_{i}$ under measure $P$, but they are not independent. Let $T$ be the set of the first $K_{o}$ indices in $C^{\ast}$, i.e., $T=[K_{o}]$, where $K_{o}=o(K)$ and $K_{o}\to\infty$. Let $\sigma^{2}=K_{o}\mathsf{var}_{P}(L_{1})$, where $\mathsf{var}_{P}(L_{1})$ denotes the variance of $L_{1}$ under measure $P$, and let $T^{\prime}=\{i\in T:e(i,T)\leq(K_{o}-1)D(P\|Q)+6\sigma\}$. SinceIn case $T^{\prime}=\emptyset$ we adopt the convention that the minimum of an empty set of numbers is $+\infty$.

The set $T^{\prime}$ is independent of $(e(i,C^{*}\backslash T):i\in T)$ and each of those variables has the same distribution as $\sum_{j=1}^{K-K_{o}}L_{j}$ under measure $P$. Thus,

Since the joint condition (8) is necessary for weak recovery, and hence also for exact recovery, it suffices to prove (14) under the assumption that (8) holds, i.e.,

for any fixed constant $\epsilon_{0}\in(0,1)$ and all sufficiently large $n$. It follows that

Thus if $K=O(1)$, then (42) implies (14). Hence, we assume $K\to\infty$ in the following without loss of generality.

For the sake of argument by contradiction, suppose that (14) does not hold. Then, by going to a subsequence, we can assume that

where $\gamma=\frac{1}{K}\log\frac{n}{K}$. It follows from (42) that $\gamma\leq\frac{1}{2-\epsilon_{0}}D(P||Q)$.

We shall apply Lemma 6 to argue a contradiction. As a witness to the nonexistence of $\theta_{n}$ satisfying (38) and (39) we show that if $\theta_{n}=\gamma$ then neither (38) nor (39) holds. By Lemma 2, $D(P\|Q)\asymp D(Q\|P)$. Since $0\leq\gamma\leq\frac{1}{2-\epsilon_{0}}D(P||Q)$, choosing $\delta>0$ to be a sufficiently small constant ensures that both $\gamma$ and $\gamma+\delta D(Q||P)$ lie in $[-D(Q||P),D(P||Q)]$. Then Assumption 1 and Corollary 5 yield:

By the properties of $E_{Q}$ discussed in Remark 3,

so, in view of (43), if $\delta$ is sufficiently small,

for all sufficiently large $n$. Also, recall that $D(P\|Q)\asymp D(Q\|P)$ and hence (42) implies that $KD(Q\|P)\to\infty$. Therefore,

for all sufficiently large $n$. Thus, (39) does not hold for $\theta_{n}\equiv\gamma$.

Turning to (38) (with $\theta_{n}=\gamma$), we let $K_{o}=K/\log K$ and

where $\sigma=\mathsf{var}_{P}[L]$. Note that $\mathsf{var}_{P}[L]=\psi_{Q}^{\prime\prime}(1)\leq CD(P\|Q)$ by Assumption 1 and recall that from (42) we have $\gamma\leq\frac{1}{2-\epsilon_{0}}D(P\|Q)$. Furthermore, since $K\to\infty$ and $KD(P\|Q)\to\infty$ by (42), we conclude that $\delta^{\prime}=o(1)$.

Since $D(P\|Q)\asymp D(Q\|P)$ and $0\leq\gamma\leq\frac{1}{2-\epsilon_{0}}D(P\|Q)$, choosing $\delta$ to be a sufficiently small constant ensures that both $\gamma-\delta^{\prime}D(P\|Q)$ and $\gamma-(\delta^{\prime}+\delta)D(P\|Q)$ lie in $[-D(Q\|P),D(P\|Q)]$. Hence, applying Corollary 5 yields

Moreover, in view of the fact that $E_{P}(\cdot)$ is decreasing and (23),

Let $C^{\prime}=\frac{(1-\epsilon_{0})^{2}}{2(2-\epsilon_{0})^{2}C}$. Therefore, similar to the properties of $E_{Q}$ discussed in Remark 3,

Since $E_{P}(\gamma)=E_{Q}(\gamma)-\gamma,$ by (43), there exist some $\epsilon>0$ such that

Thus by choosing $\delta$ sufficiently small and in view of $\delta^{\prime}=o(1)$,

for some $\epsilon^{\prime}>0$. Recall that $KD(P\|Q)\to\infty$, it readily follows from (45) that

Thus, with $\theta_{n}=\gamma$, neither (38) nor (39) holds for all sufficiently large $n$. Therefore, there does not exist a sequence $\theta_{n}$ such that both (38) and (39) hold for all sufficiently large $n$, contradicting the conclusion of Lemma 6. ∎

Appendix A Equivalence of Weak Recovery in Expectation and in Probability

where $\mathbf{0}$ denotes the all-zero vector. Since $|\xi|=K$, by the triangle inequality, we have

Appendix B Assumption 1 for exponential families of distributions

There is a simple sufficient condition for Assumption 1 to hold in case $P$ and $Q$ are from the same exponential family of distributions (including Bernoulli, Gaussian, etc). Consider a canonical exponential family with the following pdf (with respect to some dominating measure):For simplicity we assume $T$ and $\theta$ are scaler valued. Vector values would give $p_{\theta}(x)=h(x)\exp(\left\langle\theta,T(x)\right\rangle-A(\theta))$ and the condition (47), with $A^{\prime\prime}(\theta)$ replaced by $(\theta_{1}-\theta_{0})^{\top}H(\theta)(\theta_{1}-\theta_{0}),$ where $H$ is the Hessian of $A,$ and $I$ and $J$ becoming line segments, is still sufficient for Assumption 1.

By Taylor’s theorem, $D(P\|Q)$ is $\frac{(\theta_{0}-\theta_{1})^{2}}{2}$ times a weighted average of $A^{\prime\prime}$ over $I$:

Similarly, $D(Q\|P)$ is a weighted average of $A^{\prime\prime}$ over $I$. Therefore, a sufficient condition for Assumption 1 is

Gaussian: $\theta=\mu$, $A(\theta)=\theta^{2}/2$ and $A^{\prime\prime}(\theta)=1$. So (1) holds in the Gaussian case with no extra assumption.

Bernoulli: $\theta=\log\frac{p}{\bar{p}}$, $A(\theta)=\log(1+e^{\theta})$ and $A^{\prime\prime}(\theta)=\frac{e^{\theta}}{(1+e^{\theta})^{2}}=p(1-p)$. We shall show that if $p,q$ vary such that $p,q\in(0,1)$ with $p\neq q$, then (47) is equivalent to boundedness of the LLR. By symmetry between 0 and 1 we can assume without loss of generality that $0<q<p<1$. First, if $p\leq 1/2$ the LHS of (47) is $\frac{p\bar{p}}{q\bar{q}}\asymp\frac{p}{q}$ and if $p\in[1/2,1-\epsilon]$ for some fixed $\epsilon>0$ then the LHS of (47) has size $\Theta(1/q)=\Theta(p/q)$. So the claim is true if $p$ is bounded away from one. If $p\to 1$ and $q\not\to 1$ then both the LHS of (47) and the LLR are unbounded, so the claim is again true. It remains to check the case $p,q\to 1$. The denominator of the LHS of (47) is $p\bar{p}\asymp\bar{p}$. The maximum in the numerator is taken over the interval $[\theta_{-1},\theta_{1}],$ where $\theta_{-1}=\theta_{0}-[\theta_{1}-\theta_{0}]=\log\left(\frac{q^{2}\bar{p}}{\bar{q}^{2}p}\right)$. If $\theta_{-1}\leq 0$ (i.e. $\theta_{0}\leq\theta_{1}/2$) then the numerator of the LHS of (47) is $1/4$, so (47) fails to hold, and also, $\frac{\bar{p}}{\bar{q}}=O(\sqrt{\bar{p}})$ so the LLR is unbounded. It thus remains to consider the case $\theta_{1}/2\leq\theta_{0}\leq\theta_{1}$ with $\theta_{1}\to\infty$. The numerator of the LHS of (47) is $r\bar{r}$ where $r$ is determined by $\theta_{-1}=\log\frac{r}{\bar{r}},$ or, equivalently, $\frac{r}{\bar{r}}=\frac{q^{2}\bar{p}}{\bar{q}^{2}p}$. Hence $\bar{r}\asymp\frac{(\bar{q})^{2}}{\bar{p}}$. The LHS of (47) is $\frac{r\bar{r}}{p\bar{p}}\asymp\frac{\bar{r}}{\bar{p}}\asymp\left(\frac{\bar{q}}{\bar{p}}\right)^{2}$ while the maximum absolute value of the LLR is $\Theta(\log\frac{\bar{q}}{\bar{p}})$. Hence, again, (47) holds if and only if the LLR is bounded. The claim is proved.

Appendix C Proof of Corollary 4

In the Gaussian case, $E_{Q}(\theta)=\frac{1}{8}(\mu+\frac{2\theta}{\mu})^{2}$. Throughout this proof, let $\theta=\frac{1}{K}\log\frac{n}{K}$ and let $f$ be the function defined by $f(\mu)=E_{Q}(\theta)=\frac{1}{8}(\mu+\frac{2\theta}{\mu})^{2}.$ Consider the equation $f(\mu)=\frac{\log n}{K}.$ It yields a quadratic equation in $\mu^{2}$: $\mu^{4}-\frac{4\log n+4\log K}{K}\mu^{2}+\frac{4\log^{2}(n/K)}{K^{2}}=0$ which has two solutions namely $\mu_{\pm}^{2}=\frac{2}{K}\left(\sqrt{\log n}\pm\sqrt{\log K}\right)^{2}$. Without loss of generality, we take $\mu_{+}>0$ and $\mu_{-}>0$; the case of $\mu_{+}<0$ and $\mu_{-}<0$ follows analogously. In summary, the expressions inside the $\liminf$ in both (13) and (19) are one if $\mu$ is replaced by $\mu_{+}.$