1

Side Information in the Binary Stochastic
Block Model: Exact Recovery
arXiv:1708.04972v1 [] 16 Aug 2017

Hussein Saad, Student Member, IEEE, Ahmed Abotabl , Student Member, IEEE
and Aria Nosratinia, Fellow, IEEE

Abstract
In the community detection problem, one may have access to additional observations (side information) about the label of each node. This paper studies the effect of the quality and quantity of
side information on the phase transition of exact recovery in the binary symmetric stochastic block
model (SBM) with n nodes. When the side information consists of the label observed through a binary
symmetric channel with crossover probability α, and when log( 1−α
α ) = O(log(n)), it is shown that side
information has a positive effect on phase transition; the new phase transition under this condition is
characterized. When α is constant or approaches zero sufficiently slowly, i.e., log( 1−α
α ) = o(log(n)),
it is shown that side information does not help exact recovery. When the side information consists of
the label observed through a binary erasure channel with parameter ǫ, and when log(ǫ) = O(log(n)), it
is shown that side information improves exact recovery and the new phase transition is characterized.
If log(ǫ) = o(log(n)), then it is shown that side information is not helpful. The results are then
generalized to an arbitrary side information of finite cardinality. Necessary and sufficient conditions are
derived for exact recovery that are tight, except for one special case under M -ary side information.
An efficient algorithm that incorporates the effect of side information is proposed that uses a partial
recovery algorithm combined with a local improvement procedure. Sufficient conditions are derived for
exact recovery under this efficient algorithm.

Index Terms
Community detection, Stochastic block model, Side information, Exact recovery.
The authors are with the Department of Electrical Engineering, University of Texas at Dallas, Richardson, TX 75083-0688
USA, E-mail: hussein.saad@utdallas.edu;ahmed.abotabl@utdallas.edu;aria@utdallas.edu.

August 17, 2017

DRAFT

2

I. I NTRODUCTION
The problem of learning or detecting community structures in random graphs has been studied
in statistics [1]–[5], computer science [6]–[10] and theoretical statistical physics [11], [12],
among others. The problem of detecting communities has many applications: finding like-minded
people in social networks [13], improving recommendation systems [14], detecting protein
complexes [15]. Among the different random graph models [16], [17], the stochastic block
model (SBM) is widely used in the context of community detection [18]. This extension of the
Erdos-Renyi model consists of n nodes that belong to two1 communities, each pair connected
with an edge with probability p if the pair belongs to the same community and with probability
q if they do not. The prior distribution of the node labels is identical and independent, and often
uniform (labels are equi-probable). The goal of community detection is to recover/detect the
labels upon observing the graph edges.
The graphical structure of inference problems can lead to well-characterized asymptotic results
(e.g. phase transitions) that can give insights on the performance of inference algorithms on
large data sets. But a purely graphical model for observations also unfortunately limits the
scope of the applicability of the model. For example, social networks such as Facebook and
Twitter have access to much information other than the graph edges. A citation network that
has the authors names, keywords, and abstracts of papers, and therefore may provide significant
additional information beyond the co-authoring relationships.
In statistics, the problem of community detection with additional information such as “annotation” [19], “attributes” [20], or “features” [21] has been broached, wherein for matching to real
(finite) data sets a parametric model is proposed that expresses the joint probability distribution
of the graphical and non-graphical (attribute/feature) observations conditioned on the true label
and a modeling parameter. These works concentrate on model-matching and inference using
graphical and non-graphical observations. This is unlike the present paper that is concerned
with phase transitions and thresholds, but they nevertheless show the interest of the broader
community in the issue of side-information in graph-based inference.
For reference, a few basic definitions are highlighted before continuing with the literature
survey. Correlated recovery refers to community detection that performs better than random
1

We consider the binary stochastic block model.

August 17, 2017

DRAFT

3

guessing [22]–[26]. Weak recovery refers to a vanishing fraction of misclassified labels [27]–
[29]. Exact recovery refers to recovering all communities with probability converging to one as
n → ∞ [18], [30], [31]. Phase transition refers to a threshold on the random graph parameters
such that on one side of the threshold no algorithm can achieve a certain form of recovery, and
on the other side some algorithm exists to achieve recovery. A sparse regime is in place when
the average degree of the graph is Ω(1), and a graph is dense if the average degree is Ω(log n).
The asymptotic behavior of belief propagation with side information has been studied in
binary community detection in the sparse regime. Mosel and Xu [32] considered side information
consisting of the label observed through a binary symmetric channel, showing that subject to
side information the belief propagation under certain condition has the same residual error as
the MAP estimator. They also showed weak recovery if the average degree grows with n. Cai
et. al [33] considered side information consisting of the label observed through a binary erasure
channel (BEC) with erasure probability ǫ → 1 as n → ∞, demonstrating regimes for correlated
recovery and weak recovery. Both [32], [33] present sufficient (but not necessary) conditions. Kadavankandy et al. [34] studies the single-community problem under side information consisting
of the labels observed through a binary asymmetric channel, where they showed weak recovery
in the sparse regime. Kanade et. al [35] showed that for symmetric communities, the phase
transition of correlated recovery is not affected if labels are observed through a BEC whose
erasure probability ǫ → 1 as n grows. The same side information was shown to be helpful
to correlated recovery of local algorithms. Caltagirone et. al [36] considered binary asymmetric
communities, showing that in the presence of side information mentioned above, local algorithms
achieve correlated recovery up to the phase transition threshold.
This paper studies the effect of side information on binary community detection, motivated and
directed by several observations. First, while the effect of side information on correlated recovery
and weak recovery has been studied, its effect on exact recovery has been unknown. Also, the
literature has concentrated on the effect of side information only on belief propagation, which
is not enough to determine phase transition. Second, only binary side information about binary
labels has been studied (or binary side information with erasures). The more general case where
side information has an arbitrary alphabet is motivated by many practical applications, but an Mary side information has not been thoroughly studied either in the context of belief propagation or
maximum likelihood. Finally, in many cases either necessary or sufficient conditions for recovery
August 17, 2017

DRAFT

4

is known, but not both.
In this paper, we study the effect of side information on exact recovery in the dense regime,
i.e., when p = a logn n and q = b logn n with constants a > b > 0. We investigate the question: when
and how much can side information affect the phase transition threshold of exact recovery?2
We study this question for the popular models of side information: (a) the labels are observed
through a binary symmetric channel with crossover probability α ∈ (0, 0.5), and (b) labels are
observed through a binary erasure channel with erasure probability ǫ ∈ (0, 1). We also generalize
the existing models to include arbitrary side information distributions on finite alphabets. For
exact recovery, necessary and sufficient conditions are derived that are tight. More specifically:
•

For side information observed through a binary erasure channel with erasure probability
ǫ ∈ (0, 1), we show that when log(ǫ) is constant independent of n, or, surprisingly, o(log(n)),
√
then side information does not help exact recovery and the phase transition is still ( a −
√ 2
b) > 2. When log(ǫ) is O(log(n)), then side information helps and the phase transition for
exact recovery changes. More precisely, we show that when log(ǫ) = −β log(n) for some
√ √
β > 0, then: ( a− b)2 +2β > 2 is necessary and sufficient for exact recovery. We provide
our sufficient conditions for two detection algorithms, namely, Maximum Likelihood and an
efficient algorithm which uses a partial recovery algorithm from the literature combined with
a local improvement procedure that combines both the graph and side information. Also,
during the proofs, we needed one lemma from [30], for which we provide an alternative
and more compact proof.

•

For side information observed through a binary symmetric channel with crossover proba) is o(log(n)), then side information
bility α ∈ (0, 0.5), we show that when c = log( 1−α
α
√
√
does not help exact recovery and the phase transition is still ( a − b)2 > 2. When
α is decreasing with n such that c = β log(n) for some β > 0, then: for graphs with
T (a−b)
2
T (a−b)
2

< β, β > 1 is necessary and sufficient for exact recovery and for graphs with

> β, η(a, b, β) > 2 is necessary and sufficient for exact recovery, where η(a, b, β) =
p
γ+β
+ Tβ log( γ−β
), where T = log( ab ), γ = β 2 + abT 2 . Unlike the partial noiseless
a+b+β− 2γ
T
side information, we provide the sufficient conditions only for the efficient algorithm3.

2

√
√
The exact recovery phase transition without side information is ( a − b)2 > 2 [30].

3

These results appear in the Allerton Conference on Communications, Control, and Computing 2017 [37].

August 17, 2017

DRAFT

5

•

We then generalize our results to M-ary side information with finite M. We provide necessary
and sufficient conditions and show that they are tight, expect for one special case, by
extending our efficient algorithm to M-ary side information. Surprisingly, we show that
if for at least one m ∈ {1, · · · , M} we have the log-likelihood ratio of this mth side
information to be o(log(n)), then side information does not help exact recovery and the
√
√
phase transition is still ( a − b)2 > 2. If for all m ∈ {1, · · · , M} we have the loglikelihood ratio of side information to be Ω(log(n)), then we need several conditions to be
satisfied which will be specified later in Section V.

To illustrate our results, we show in Figures 1, 2 the error exponent, for some values of a, b,
for the side information observed through a binary erasure and binary symmetric channels as a
function of β. From the figures, we can see that the value of β needed for recovery depends on
√
√
a, b. For the binary erasure channel, for any given a > b > 0 with ( a − b)2 < 2, the needed
√
√
value of β for recovery, i.e., critical β, is 1 − 12 ( a − b)2 + δ for any arbitrary small δ > 0.
√
√
For the binary symmetric channel, for any given a > b > 0 with ( a − b)2 < 2, the value
) > 2, then the critical
of β needed for recovery can be determined as follows: if η(a, b, T (a−b)
2

β is the value of β that makes η > 2, in that case it is less than one. On the other hand, if
η(a, b, T (a−b)
) < 2, then it is 1 + δ for arbitrary small δ > 0.
2
Remark 1: For weak recovery, it is easy to see that for α or ǫ → 0 as n → ∞ arbitrary slow,
side information could help to achieve recovery regardless of the observed graph. However, for
exact recovery, we still need a certain rate at which α or ǫ → 0 to make the side information
useful to the maximum likelihood detector. We will provide some intuition about why this is
the case in our analysis in the next few sections.
II. S YSTEM M ODEL
In this paper, we consider the binary symmetric stochastic block model with side information.
Let the labels of the two communities be 1 or −1. Our observations are generated as follows:
each node, out of n nodes, is assigned independently and uniformly at random to one of the
two communities. After the assignment of nodes, each two nodes are connected with an edge
if the two nodes belong to the same community and with
independently with probability a log(n)
n
, otherwise. Finally, for each node we observe a scalar side information. We
probability b log(n)
n
consider three models of side information.
August 17, 2017

DRAFT

6

1-0.5η(a,b,β) VS 1-β
1
a=5,b=1
a=4,b=1
a=3,b=1
a=2.5,b=1

0.5
0

Error exponent

Recovery region
-0.5
Critical β
-1
-1.5
-2
-2.5
-3
0

0.5

1

1.5

2

2.5

3

3.5

Quality of Side information (β)

Fig. 1.

Error exponent of the binary symmetric channel side information as a function of β.

√
√
1 − (0.5( a − b)2 + β)
1
0.5

Error exponent

0

Recovery region

−0.5
Critical β
−1
−1.5
−2
−2.5
−3

0

1

2

3

4

5

Quality of Side information (β)

Fig. 2.

Error exponent of binary erasure channel side information as a function of β.

August 17, 2017

DRAFT

7

First, for each node, we independently observe its true label with probability (1 − α) or the
negative of its true label with probability α, for α ∈ (0, 0.5). For the second model, for each
node, we independently observe its true label with probability 1 − ǫ or 0 with probability ǫ,
for ǫ ∈ (0, 1). For the third model, we consider M-ary side information, where for each node i
we independently observe yi ∈ {u1 , u2, · · · , um }. We denote P(yi = um |xi = ±1) = α±,m , and
PM
PM
α
=
+,m
m=1 α−,m = 1.
m=1

We denote the observed graph by G = (V, E), the vector of nodes’ true assignment by x∗ ,

and the vector of nodes’ side information by y. The goal is to recover the node assignment x∗
from the observation of (G, y).
Remark 2: In [30] where the graph is the only observation, exact recovery is defined up to
a global flip. This is due to the symmetry of the two communities and hence, recovering the
true vector x∗ or −x∗ would be considered a success. This is not generally true with side
information. For example, with side information observed through binary symmetric or binary
erasure channels, symmetry is broken and success is only considered when the true vector x∗
is recovered.
III. B INARY S YMMETRIC C HANNEL
In this section, we consider side information consisting of the true labels observed through a
binary symmetric channel with crossover probability α ∈ (0, 0.5). We provide tight necessary
and sufficient conditions for different cases of α. But before we proceed with the proofs we
need the following lemmas.
First, we present the ML rule for detecting the communities. It is known that without side
information, in the binary symmetric SBM, the ML will find two equally sized communities (of
size

n
2

each) that have the minimum number of edges between them, i.e., minimum cut [30].

So we need to determine the ML rule when it has side information. Denote the first and
second communities by A and B, respectively. We will use communities A (1) and B (−1)
interchangeably. Let the number of edges inside community A and B be E(A) and E(B),
respectively. Also, let the total number of edges in the observed graph be Et . Finally, let the
number of {i ∈ A : yi = 1} and {i ∈ B : yi = −1} be J+ (A) and J− (B), respectively. Then,
the log-likelihood function can be written as:

August 17, 2017

DRAFT

8

 (a)


log P(G, y|x) = log P(G|x) + log P(y|x)


n
n2
2( 22 )−E(A)−E(B)
−E
+E(A)+E(B)
E(A)+E(B) Et −E(A)−E(B)
t
(1 − q) 4
= log p
q
(1 − p)


J+ (A)+J− (B) n−J+ (A)−J− (B)
+ log (1 − α)
α
(b)



=R + T E(A) + E(B) (1 + o(1)) + c J+ (A) + J− (B)

(1)

where T = log( ab ), c = log( 1−α
), (a) holds because G, y are independent given x and (b)
α
holds by defining R to be a constant that contains all the terms that are independent of x and
approximating log( p(1−q)
) by (1 + o(1))T because (1 − p), (1 − q) both approach 1 as n → ∞.
q(1−p
Therefore, ML rule finds two equally sized communities that have the maximum the number of
edges inside the communities weighted by T plus the number of yi that matches the communities’
labels weighted by c.
Using this result, we will now get a sufficient and necessary conditions for the event that ML
fails to detect the communities. But we need the following definitions. Recall, we defined the
true communities as A (1) and B (−1). Moreover, we define the following events.

F = {ML fails}
FA = {∃i ∈ A : T (E[i, B] − E[i, A]) − cyi ≥ T }
FB = {∃j ∈ B : T (E[j, A] − E[j, B]) + cyj ≥ T }

(2)

where E[·, ·] denotes the number of edges between two sets of nodes. The following two lemmas
define lower and upper bounds of the probability of failure of ML.
Lemma 1: F will happen if both FA and FB happened.
Proof:
Define two new communities Â = A\{i} ∪ {j} and B̂ = B\{j} ∪ {i}. Hence, we need to


show that log P(G, y|Â, B̂) ≥ log P(G, y|A, B) , which implies the failure of ML.

Let Aij ∼ Bern(q) be a random variable representing the existence of the edge between nodes

i and j. Then, using (1):




log P(G, y|Â, B̂) =R + T E(Â) + E(B̂) + c J+ (Â) + J− (B̂)
August 17, 2017

DRAFT

9



=R + T E(A) + E(B) − E[i, A] + E[j, A] − E[j, B] + E[i, B] − 2Aij


+ c J+ (A) + J− (B) + J+(j) − J+(i) + J−(i) − J−(j)


=R + T E(A) + E(B) + c J+ (A) + J− (B) − 2T Aij


+ T E[j, A] − E[j, B] + cyj + T E[i, B] − E[i, A] − cyi

(a)


≥ log P(G, y|A, B) + 2T (1 − Aij )
(b)

≥ log P(G, y|A, B)



where (a) holds by the assumption that FA ∩ FB happened and (b) holds because (1 − Aij ) ≥ 0
and T ≥ 0. Hence, from the last inequality, we conclude that the ML will not coincide with the
true assignment A, B.
Lemma 2: Suppose that F happens. Then, there exists k and sets Aw ⊂ A and Bw ⊂ B with
|Aw | = |Bw | = k, for 1 ≤ k ≤

n
2

such that:





T E[Bw , A\Aw ]+E[Aw , B\Bw ]−E[Bw , B\Bw ]−E[Aw , A\Aw ] +2c J+ (Bw )−J+ (Aw ) ≥ 0
Proof: Let Â = A\{Aw } ∪ {Bw } and B̂ = B\{Bw } ∪ {Aw }. Since F happened, then:


log P(G, y|Â, B̂) ≥ log P(G, y|A, B) , and hence:


T E[A\{Aw }, A\{Aw }] + E[Bw , A\{Aw }] + E[B\{Bw }, B\{Bw }] + E[Aw , B\{Bw }] +


c J+ (A\{Aw }) + J+ (Bw ) + J− (B\{Bw }) + J− (Aw ) ≥


T E[A\{Aw }, A\{Aw }] + E[Aw , A\{Aw }] + E[B\{Bw }, B\{Bw }] + E[Bw , B\{Bw }] +


c J+ (A\{Aw }) + J+ (Aw ) + J− (B\{Bw }) + J− (Bw )

By canceling out similar terms, this concludes our proof.
Remark 3: In [30], due to symmetry, recovering the true assignment vector x∗ or −x∗ is

considered a success. Thus, the error event was defined for 1 ≤ k ≤ n4 . Here, since α < 0.5,
August 17, 2017

DRAFT

10

then side information will break symmetry, and hence, exchanging a subset of nodes of size k
is not the same as exchanging a subset of nodes of size

n
2

− k. Thus, we defined our error event

for 1 ≤ k ≤ n2 . That is true also for side information observed through a binary erasure channel.
A. Necessary Conditions

Let a > b > 0 and define c = log( 1−α
) and η(a, b, β) = a + b + β − 2γ
+ Tβ log( γ+β
), where
α
T
γ−β
p
T = log( ab ), γ = β 2 + abT 2 .
√
√
Theorem 1: For c = o(log(n)), if ( a − b)2 < 2, then ML fails in recovering the communities with probability bounded away from zero. On the other hand, for c = β log(n), for some
β > 0, for graphs with

T (a−b)
2

< β, if β < 1 then ML fails in recovering the communities with

probability bounded away from zero, and for graphs with

T (a−b)
2

> β, if η(a, b, β) < 2, then ML

fails in recovering the communities with probability bounded away from zero.
Remark 4: Note that under the assumption that the number of edges connected to nodes
i, j ∈ community A are independent, the proof would be much simpler. However, they are
dependent. To overcome this dependency, we break the event FA into several events. Such idea
was introduced in [30].
Proof:
Note that since x∗ is generated uniformly, then ML minimizes the probability of error over
all possible estimators. Hence, if the probability of failure of ML is bounded away from zero,
then every other estimator has probability of failure bounded away from zero. Let H be a subset
of A with |H| =

n
.
log3 (n)

We define the following events:


△i = i ∈ H : E[i, H] ≤

log(n)
log log(n)


log(n)
≤ T ∗ E[i, B]
FiH = i ∈ H : T ∗ E[i, A\H] + cyi + T + T
log log(n)

△ = ∀i ∈ H : △i is true

F H = ∪i∈H FiH
We will prove this part of the theorem via several lemmas.

August 17, 2017

DRAFT

11

Lemma 3: If P(FA ) ≥ 23 , then P(F ) ≥ 31 .
Proof:
If P(FA ) ≥ 23 , then by the symmetry of the graph and the side information, P(FB ) ≥

2
3

too.

Also, by Lemma 1 FA ∩ FB ⇒ F . Then, we have:
P(F ) ≥ P(FA ) + P(FB ) − 1 ≥
Lemma 4: IF P(F H ) ≥

9
10

and P(△) ≥

9
,
10

1
4
−1=
3
3

then P(F ) ≥ 31 .

Proof: It is easy to see that △ ∩ F H ⇒ FA . Hence,

P(FA ) ≥ P(F H ) + P(△) − 1 ≥

2
8
>
10
3

which together with Lemma 3 concludes the proof.

9
10

Based on the above Lemmas, our proof boils down to proving when P(F H ) ≥

9
10

and P(△) ≥

are true.
Lemma 5: P(△) ≥

9
10

for sufficiently large n.

Proof:
Let Wi ∼ Bern(p). Then, we have:

P(△ci )

=P

X
i−1

≤P

n
log3 (n)

log(n)
Wj +
Wj ≥
log(log(n))
j=1
j=i+1

n
3 (n)
 log
X

j=1

X

log(n)
Wj ≥
log(log(n))





− log(n)
(a)  1
log3 (n)  log(log(n))
≤
e a log(log(n))

where (a) holds from a multiplicative form of Chernoff bound, which states that for a sequence
P
of n i.i.d random variables Xi , P( ni=1 Xi ≥ tµ) ≤ ( et )−tµ , where µ = nE[X]. Thus, we get by
union bound:
August 17, 2017

DRAFT

12

n  1 log3 (n)  log(log(n))
P(△i ) ≥ 1 −
log3 (n) e a log(log(n))

− log(n)

log(n)−3 log(log(n))

= 1−e

e

log(n) log(ae)
log(n)
− log(log(n))
log(log(n))



3 log(log(n))−log(log(log(n)))



= 1 − e−2 log(n)+o(log(n))

Thus, for sufficiently large n, P(△) ≥
9
10

We will show when P(F H ) ≥

log3 (n)
n

9
.
10

is true in two steps. First we will show that if P(FiH ) >

9
. Then, we will show when
10
log3 (n)
9
log(10), then P(F H ) ≥ 10
.
n

log(10), then P(F H ) ≥

Lemma 6: If P(FiH ) >

P(FiH ) >

log3 (n)
n

log(10) is true.

Proof:

(a)

P(F H ) = P(∪i∈H FiH ) = 1 − P(∩i∈H (FiH )c )
 n
= 1 − 1 − P(FiH ) log3 (n)
where (a) holds because FiH are i.i.d random variables. So, for P(F H ) ≥

(1 − P(FiH ))

n
log 3 (n)

≤

1
.
10

9
10

to be true, we need

If P(FiH ) is not o(1), then clearly the inequality is true. On the other

hand, if P(FiH ) is o(1), then:

lim 1 − P(FiH )

n→∞



n
log3 (n)

= lim 1 − P(FiH )
n→∞

−n

= lim e log3 (n)

P(FiH )

(P(FiH ))( P(F1H ) )( log3n(n) )
i

n→∞

So clearly, if P(FiH ) >
P(F H ) ≥

9
.
10

August 17, 2017

log3 (n)
n

n

log(10), then (1 − P(FiH )) log3 (n) ≤

1
,
10

which implies that

DRAFT

13

log3 (n)
log(10) is true.
n
3
log
P(FiH ) > n(n) log(10) for

The final step is to show when P(FiH ) >
Lemma 12 in the Appendix shows that

Recall that c = log( 1−α
).
α
sufficiently large n if one

of the following is satisfied:
•

√
√
When c = o(log(n)): if ( a − b)2 < 2.

•

When c = β log(n), β > 0: for any a, b, β, if η(a, b, β) < 2.

•

When c = β log(n), β > 0: for a, b, β : β >

T (a−b)
,
2

if η(a, b, β) > 2 and β < 1.

B. Sufficient Conditions
In this section we provide an efficient algorithm that achieves exact recovery down to the
necessary conditions obtained in Section III-A. The algorithm is decomposed into two stages.
In the first stage we use the algorithm proposed in [24] on the graph alone. Such algorithm
is known to achieve weak recovery. Then, we modify its outcome using the graph and side
information. This idea was used before in [30], [31], but it is the first time to be used with side
information, to the best of our knowledge.
Note that based on Lemma 2, we can try to provide the sufficient conditions by bounding
P n2
n 2
(k)
2
Pn , where 1 ≤ k ≤ n2 and
the failure event of maximum likelihood as P(F ) ≤ k=1
k
P
Pk
(k)
n
Pn := P T m
i=1 (Zi − Wi ) + c
i=1 (Si − Ri ) ≥ 0 , m = 2k( 2 − k), Wi ∼ Bern(p),
Zi ∼ Bern(q), Si ∼ Bern(α) and Ri ∼ Bern(1 − α). However, it is difficult to deal with a

weighted sum of four independent Binomial random variables with different number of trials
and different probability of success. The algorithm we provide overcome this difficulty because
the second stage that exploits side information works on a node by node basis, and hence, deal
with the side information as a Bernoulli random variable instead of Binomial.
The algorithm starts by splitting the information in the observed graph into two parts. The
first part to be used by the partial recovery algorithm and the second part to be used for local
modification with the observed side information. In order to make the two steps independent, we
follow a similar idea as the one presented in [30]. First assume we have a complete graph on n
nodes. We split its edges into two random graphs each with n nodes. We call these graphs H1 and
H2 . More precisely, we generate H1 by keeping edges in the complete graph with probability
D
.
log(n)

H2 will be the complement of H1 . Then, we define G1 and G2 as sub-graphs of the

observed graph G as: G1 = G ∩ H1 and G2 = G ∩ H2 .
August 17, 2017

DRAFT

14

Next, we apply the partial recovery algorithm presented in [24] on G1 . Notice that G1 is a
graph obtained from a binary symmetric SBM with connectivity parameters ( Da
, Db
). Thus, the
n
n
′

′

′

partial recovery algorithm is guaranteed to return two communities A and B such that A ,
′

B coincide with the true community assignment A, B on at least (1 − δ(D))n nodes, with
δ(D) → 0 as D → ∞ [24].
The last step is the local modifications step. Now that we have G2 , the side information y,
′

′

′

A and B , we locally modify the community assignment as follows: for a node i ∈ A , we flip
′

its membership if the number of edges between i and B is greater than or equal the number of
′

edges between i and A plus
′

c
T

′

yi and for node j ∈ B , we flip its membership if the number of
′

edges between j and A is greater than or equal the number of edges between j and B minus
c
T

yi . If the the number of flips in each cluster is not the same, keep the clusters unchanged.
√ √
Theorem 2: For c = o(log(n)), if ( a− b)2 > 2, then, there exists large enough D such that,

with high probability, the algorithm described above will successfully recover the communities
from the observed graph and side information. On the other hand, for c = β log(n), for some
β > 0, then the algorithm described above will successfully recover the communities from the
observed graph and side information, if:


η(a, b, β) > 2, for
Proof:


β > 1,

for

a, b, β : β <

T (a−b)
2

a, b, β : β >

T (a−b)
2

Our goal here is to upper bound the error of misclassifing one node, then use a simple union
bound over all nodes. If we assume for now (to be changed later) that H2 is a complete graph,
then we have four different cases for which a node could be misclassified according to our
′

algorithm. Two cases could happen when the node i ∈ A and another two when the node
′

i ∈ B . The first two cases are displayed in Figures 3, 4. The remaining cases are similar.
Now under the assumption that H2 is complete, then the four cases for error can be written
as follows. Let Wi ∼ Bern(p), Zi ∼ Bern(q) and yi ∈ {1, −1} with probabilities (1 − α), α,
respectively. For simplicity, we will write δ instead of δ(D). Then, we have the following:


Pe = P node i is mislabeled
August 17, 2017

DRAFT

15

Yi= {1,-1} ~(1-α,α)

Fig. 3.

Yi= {1,-1} ~(α,1-α)

B

A

B

A

A

B

A

B

A’

B’

A’

B’

Correct node that will be flipped

=P

Fig. 4.

n
 (1−δ)
X2

n

Zi +

i=1

δ2
X
i=1

Incorrect node that will not be flipped

(1−δ) n2

Wi ≥

X

n

Wi +

i=1

δ2
X
i=1

c
Zi + y i
T



(3)

Recall, we assumed that H2 is a complete graph. However, using [Lemma 14 in [30]], it can
2D
) with high probability. Hence,
be shown that the degree of any node in H2 is at least n(1 − log(n)

we will loosely upper bound (3) be removing

2D
n
log(n)

from the first two terms on the right hand

side. Thus, we get:

Pe ≤ P

n
 (1−δ)
X2

i=1

2D
(1−δ) n2 − log(n)
n

n

Zi +

δ2
X
i=1

X

Wi ≥

2D
δn
− log(n)
n
2

X

Wi +

i=1

i=1

c
Zi + y i
T



(4)

Now Lemma 17 shows that if c = o(log(n)), then (4) can be upper bounded by (5) and if
c = β log(n), for some β > 0, then for a, b, β : β <
and for a, b, β : β >

T (a−b)
,
2

T (a−b)
,
2

(4) can be upper bounded by (6)

(4) can be upper bounded by (7).

1

√

Pe ≤ n− 2 (

√
a− b)2 +o(1)

+ n−(1+Ω(1))

1

Pe ≤ (2 − α)n− 2 η(a,b,β)+o(1) + n−(1+Ω(1))

1

Pe ≤ (1 − α)n− 2 η(a,b,β)+o(1) + n−β + n−(1+Ω(1))
August 17, 2017

(5)

(6)

(7)
DRAFT

16

Hence, using a union bound (we will do the analysis for (6) only, (5) and (7) follow similarly),
we get:

1

P(∃ a misclassified node) ≤ (2 − α)n1− 2 η(a,b,β)+o(1) + n−Ω(1)

(8)

which shows that if η(a, b, β) > 2, then the algorithm described above will successfully recover
the communities from the observed graph and side information with high probability. Note that
for (7), Lemma 15 shows that for all a and b, η > 2 if β > 1, and hence, for (7), β > 1 is
sufficient.

IV. B INARY E RASURE C HANNEL
In this section, we consider side information consisting of the true labels observed through a
binary erasure channel with parameter ǫ ∈ (0, 1). We provide necessary and sufficient conditions
that are tight for different cases for ǫ. Unlike Section III, we provide the sufficient conditions
for the Maximum Likelihood detector (known as information theoretic upper bound [30]), then
we propose an efficient algorithm that succeeds all the way down to the threshold. But as we
did in Section III, before we proceed with the proofs we need the following lemmas.
First, we present the ML rule for detecting the communities. Note that since here the side
information is either the true label or zero, thus, the maximum likelihood rule is the same as the
rule without side information. In other words, the maximum likelihood rule is to maximize the
number of edges inside the communities. However, the only difference is the feasible set. Instead
P
of having a feasible set of all possible vectors of length n ∈ {±1}n such that ni=1 xi = 0, the
P
new feasible set would be all vectors of length n ∈ {±1}n such that ni=1 xi = 0 and all these

vectors match the non erased bits in the observed side information y. The reason why this is
true, is because for any vector x that does not match the observed y, then P(y|x) = 0, and
hence, the maximum likelihood will never choose such vector.
Now based on the above observation, we will now get a sufficient and necessary conditions
for the event that ML fails to detect the communities. Recall that F denotes the event of failure
of maximum likelihood and E[·, ·] denotes the number of edges between two sets of nodes. We
define the following events
August 17, 2017

DRAFT

17

FA = {∃i ∈ A : (E[i, B] − E[i, A]) ≥ 1 and yi = 0}
FB = {∃j ∈ B : (E[j, A] − E[j, B]) ≥ 1 and yj = 0}

Lemma 7: F will happen if both FA and FB happened.
Proof:
Define two new communities Â = A\{i} ∪ {j} and B̂ = B\{j} ∪ {i}. Hence, we need to


show that log P(G, y|Â, B̂) ≥ log P(G, y|A, B) , which implies the failure of ML.

Let Aij ∼ Bern(q) be a random variable representing the existence of the edge between nodes

i and j. Then, using the maximum likelihood rule, we have:




log P(G, y|Â, B̂) =R + T E(Â) + E(B̂) + log P(y|A, B)


=R + T E(A) + E(B) + T E[j, A] − E[i, A] − E[j, B] + E[i, B] − 2Aij

+ log P(y|A, B)
(a)

(b)


≥ log P(G, y|A, B) + 2T (1 − Aij ) ≥ log P(G, y|A, B)

where (a) holds by the assumption that FA ∩ FB happened and (b) holds because (1 − Aij ) ≥
0. Hence, from the last inequality, we conclude that the ML will not coincide with the true
assignment A, B.
Lemma 8: Suppose that maximum likelihood fails. Then, there exists k and sets Aw ⊂ A and
Bw ⊂ B with |Aw | = |Bw | = k, for 1 ≤ k ≤

n
2

such that (9) is true and the side information

yi = 0∀i ∈ Aw , Bw .
E[Bw , A\Aw ] + E[Aw , B\Bw ] − E[Bw , B\Bw ] − E[Aw , A\Aw ] ≥ 0

(9)

Proof:
Let Â = A\{Aw } ∪ {Bw } and B̂ = B\{Bw } ∪ {Aw }. Since maximum likelihood is assumed


to have failed, then: log P(G, y|Â, B̂) ≥ log P(G, y|A, B) . First, note that any node to be

exchanged, has got to have erased side information, otherwise, it will never be exchanged. Also,
note that conditioned on the community assignments, G, y are independent, and since all the
August 17, 2017

DRAFT

18

feasible community assignment vectors, x, have the same P(y|x), therefore, we are only left
with P(G|x) which gives (9).

A. Necessary Conditions
√
√
Theorem 3: For log(ǫ) = o(log(n)), if ( a − b)2 < 2, then ML fails in recovering the communities with probability bounded away from zero. On the other hand, for log(ǫ) = −β log(n),
√
√
for some β > 0, if 12 ( a − b)2 + β < 1, then ML fails in recovering the communities with
probability bounded away from zero.
Proof:
We will need some definitions as in Section III-A. Some of these definitions are the same but
we include them here for completeness. Let H be a subset of A with |H| =

n
.
log3 (n)

We define

the following events:

log(n)
log log(n)


△i = i ∈ H : E[i, H] ≤


FiH = i ∈ H : yi = 0 and E[i, A\H] + 1 +

log(n)
≤ E[i, B]
log log(n)


△ = ∀i ∈ H : △i is true

F H = ∪i∈H FiH
We will prove this part of the theorem via several lemmas. Note that Lemmas 3, 4, 5, 6 extend
directly to our case here using the above definitions. To complete the proof, we need to show
log3 (n)
log(10) is true.
n
3
log
P(FiH ) > n(n) log(10) for

when P(FiH ) >

sufficiently large n if one of the following is satisfied:
√
When log(ǫ) = o(log(n)): if ( a − b)2 < 2.
√
√
When log(ǫ) = −β log(n), β > 0: for any a, b, β, if 12 ( a − b)2 + β < 1.

shows that
•
•

This is proven in Lemma 13 in the Appendix, which

August 17, 2017

√

DRAFT

19

B. Sufficient Conditions
Unlike Section III, we provide our sufficient conditions for two detectors, namely, Maximum
Likelihood and an efficient algorithm which uses a partial recovery algorithm from the literature
combined with a local improvement procedure.
1) Maximum Likelihood:

√ √
Theorem 4: For log(ǫ) = o(log(n)), if ( a− b)2 > 2, then the ML detector exactly recovers
the communities , with high probability. On the other hand, for log(ǫ) = −β log(n), for some
√
√
β > 0, if ( a − b)2 + 2β > 2, then the ML detector exactly recovers the communities , with
high probability.
Proof:
We will use Lemma 8, from which we can define the following event:

Pn(k)

:= P

m
X
i=1

where m =

2k( n2

(Zi − Wi ) ≥ 0



− k), Wi ∼ Bern(p) and Zi ∼ Bern(q).

Then, by a simple union bound we have:
n

P(F ) ≤

2
X

k=1

2k

ǫ

 n 2
2

k

Pn(k)

(10)

(k)

To bound Pn , we can use [Lemma 8 in [30]]. Lemma 16 in the Appendix shows an alternative
proof which is easier and more compact. Using Lemma 16, we have:

Pn(k) ≤ e−2m
Using the fact that
n
2
X

k=1

ǫ2k

 n 2
2

k

n
k



√
log(n) 1 √
( 2 ( a− b)2 )
n

(11)

)k , we can bound (10) as follows:
≤ ( ne
k
n

Pn(k) ≤ ǫn +

−1
2
X

ǫ2k ek



2 log(n)−2 log(2k)+2

k=1

1

k

e−4k( 2 − n )

n

≤ o(1) +

August 17, 2017

−1
2
X
k=1



k 2 log(n)−2 log(2k)+2

e

k
−4k( 12 − n
)

e

1 √
( a−
2

1 √
( a−
2

√ 
b)2 log(n)

√ 2
b) −

log(ǫ)
k
2 log(n)( 1
2−n)



log(n)

DRAFT

20
n

(a)

≤ o(1) +

−1
2
X

ek



2 log(n)−2 log(2k)+2

k=1

1

1 √
( a−
2

k

e−4k( 2 − n )

√

log(ǫ)
b)2 − log(n)



log(n)

(12)

where (a) holds because log(ǫ) < 0 and supk 2( 21 − nk ) = 1
Now, we divide our analysis into two cases.
•

when log(ǫ) = −β log(n), for some β > 0. In this case, we have:
n

o(1) +

−1
2
X
k=1

2k

ǫ

 n 2
2

k

n

Pn(k)

≤ o(1) +

−1
2
X



k 2 log(n)−2 log(2k)+2

e

k=1

k
−4k( 21 − n
)

e

1 √
( a−
2

√



b)2 +β log(n)

n

(a)

≤ o(1) + 2

4
X

k
)
k 2 log(n)−2 log(2k)+2) −4k( 12 − n

e

e

1 √
( a−
2

k=1


√ 2
b) +β log(n)

n

(b)

≤ o(1) + 2

4
X



k
k 2 log(n)−2 log(2k)+2−4( 12 − n
)(1+δ) log(n)

e

k=1
n

(c)

≤ o(1) + 2

4
X



k
k 2−2 log(2k)+4 n
log(n)−δ log(n)

e

k=1

n

(d)

≤ o(1) + 2n−δ

4
X

e−2k



k
log(n)
−1+log(2k)−2 n

k=1

(13)
where (a) holds because
increasing) for 1 ≤ k ≤

n
4

n
2

k



=

and

n
4

n
2
n
−k
2



and the range of m is the same (only decreasing not
√ √
≤ k ≤ n2 −1, (b) holds by assuming that 21 ( a− b)2 +β >

1 + δ for δ > 0 and (c), (d) hold because 1 ≤ k ≤ n4 .
Now notice that for sufficiently large n, 1 ≤ k ≤
log(2k) −

n
4

we have

2k
1
log(n) ≥ log(2k)
n
3

Hence for sufficiently large n,
n

P(F ) ≤ 2n−δ

4
X

k=1

which, together with the observation that
of the second case of the theorem.
August 17, 2017

2

e− 3 k(log(2k)−3) + o(1)

P n4

k=1

2

e− 3 k(log(2k)−3) is O(1) concludes the proof

DRAFT

21

•

when log(ǫ) = o(log(n)). In this case, we have:
n

o(1) +

−1
2
X
k=1

2k

ǫ

 n 2
2

k

n

Pn(k)

≤ o(1) +

−1
2
X



k 2 log(n)−2 log(2k)+2

e

k=1

k
−4k( 12 − n
)

e

1 √
( a−
2

√



b)2 +o(1) log(n)

(a)

≤ Cn−δ + o(1)

(14)

√ √
where (a) holds as the same analysis done in the first case, just assume that 12 ( a − b)2 >
√
√
1 + δ for δ > 0 instead of 12 ( a − b)2 + β > 1 + δ. This concludes the proof of the first
case of the theorem.

2) Efficient Algorithm: In this section we provide an efficient algorithm that achieves exact
recovery down to the necessary conditions obtained in Section IV-A. The algorithm is decomposed into two stages. In the first stage we use the algorithm proposed in [24] on the graph
alone. Such algorithm is known to achieve partial recovery. Then, we modify its outcome using
the graph and side information. The first stage of the algorithm is the same as Section III-B.
The second stage, the local modification is however different.
′

′

After the first stage, we have G2 , the side information y, A and B . We locally modify the
community assignment as follows: for any node i, we flip its membership if yi 6= 0 and does
′

′

not match the assignment node i got from A and B , or if yi = 0 and the number of edges
between i and the opposite community is greater than or equal the number of of edges between
i and its own community. If the the number of flips in each cluster is not the same, keep the
clusters unchanged.

√
√
Theorem 5: If log(ǫ) = o(log(n)), then if ( a − b)2 > 2, then, there exists large enough

D such that, with high probability, the algorithm described above will successfully recover the
communities from the observed graph and side information. On the other hand, if log(ǫ) =
−β log(n), for some β > 0, then the algorithm described above will successfully recover the
√
√
communities from the observed graph and side information, if ( a − b)2 + 2β > 2.
Proof:
Recall we defined Pe = P(node i to be misclassified). Following the same analysis as in the
proof of Lemma 2, we get:

August 17, 2017

DRAFT

22

Pe ≤ ǫP

n
 (1−δ)
X2

i=1

2D
(1−δ) n2 − log(n)
n

n

Zi +

δ2
X
i=1

Wi ≥

X

2D
δn
− log(n)
n
2

X

Wi +

i=1

i=1

Zi



(15)

Now using Lemma 17 with c = 0 instead of c = o(log(n)), then (4) can be upper bounded
as:

√

1

Pe ≤ ǫn− 2 (

√
a− b)2

+ n−(1+Ω(1))

(16)

Following the analysis in Section IV-A, we divide the analysis into two cases:
•

When log(ǫ) = −β log(n), for some β > 0. In this case, we have:
1

√

Pe ≤ n− 2 (
•

√
a− b)2 −β

+ n−(1+Ω(1))

(17)

When log(ǫ) = o(log(n)). In this case, we have:

1

√

Pe ≤ n− 2 (

√
a− b)2 +o(1)

+ n−(1+Ω(1))

(18)

Finally, using a union bound (we will do the analysis only for (17), (18) follows similarly),
we get:

1

√

P(∃ a misclassified node) ≤ n1−( 2 (

√
a− b)2 +β)

+ n−Ω(1)

(19)

√
√
which shows that if 12 ( a − b)2 + β > 1, then the algorithm described above will successfully
recover the communities from the observed graph and side information.
V. M- ARY S IDE I NFORMATION
In this section, we generalize our results to M-ary side information with finite M. More
precisely, for each node i we independently observe yi ∈ {u1 , u2, · · · , um}. We denote P(yi =
um |xi = 1) = α+,m and P(yi = um |xi = −1) = α−,m , for α+,m > 0, α−,m > 0 and
PM
PM
α+,m
m=1 α+,m =
m=1 α−,m = 1. Moreover, we define hm = log( α−,m ). We provide necessary

conditions for exact recovery for different cases for hm and propose an efficient algorithm that
succeeds all the way down to the threshold. We emphasize that we studied the binary symmetric
August 17, 2017

DRAFT

23

and binary erasure models before the M-ary side information because their proofs are easier
to follow and also for one case (that was proved to be sufficient and necessary for the binary
symmetric model) we only prove that it is sufficient for the M-ary case but we could not prove its
necessity. The proofs in this section are similar to the proof of the Theorems in Sections III, IV.
Thus, we only provide proof sketches below.
Let T = log( ab ) and recall that F denotes the event of failure of maximum likelihood and
E[·, ·] denotes the number of edges between two sets of nodes. Moreover, for a node i, we define
hi = hm , if yi = um . Then, we define the following events

FA = {∃i ∈ A : T (E[i, B] − E[i, A]) − hi ≥ T }
FB = {∃j ∈ B : T (E[j, A] − E[j, B]) + hj ≥ T }

Lemma 9: F will happen if both FA and FB happened.
Proof:
Define two new communities Â = A\{i} ∪ {j} and B̂ = B\{j} ∪ {i}. Hence, we need to


show that log P(G, y|Â, B̂) ≥ log P(G, y|A, B) , which implies the failure of ML. Let the

number of {i ∈ A : yi = um } and {i ∈ B : yi = um } be Jum (A) and Jum (B), respectively.
Using the maximum likelihood rule, we have:




log P(G, y|Â, B̂) = log P(G|Â, B̂) + log P(y|Â, B̂)


=R + T E(A) + E(B) − E[i, A] + E[j, A] − E[j, B] + E[i, B] − 2Aij +
M
X

m=1

Jum (A) log(α+,m ) + Jum (B) log(α−,m ) +

M
X

m=1

(Jum (j) − Jum (i))hm



= log P(G, y|A, B) + T − E[i, A] + E[j, A] − E[j, B] + E[i, B] − 2Aij
+ hj − hi

(a)

(b)


≥ log P(G, y|A, B) + 2T (1 − Aij ) ≥ log P(G, y|A, B)

where R is a constant representing all terms that are independent of x, (a) holds by the
assumption that FA ∩ FB happened and (b) holds because (1 − Aij ) ≥ 0. Hence, from the
August 17, 2017

DRAFT

24

last inequality, we conclude that the ML will not coincide with the true assignment A, B.
√
√
Theorem 6: If for at least one m, α+,m 6= α−,m and hm = o(log(n)), then ( a − b)2 > 2
is necessary and sufficient for exact recovery. On the other hand, if for at least one m, we have
one of the following conditions:



α+,m = α−,m = −β log(n), β > 0



, log(αsgn(β1 ),m ) = o(log(n))
hm = β1 log(n), |β1 | < T (a−b)
2




′
′
h = β log(n), |β | < T (a−b) , log(α
m
2
2
sgn(β2 ),m ) = −β2 log(n), β2 > 0
2


√ 2
√
′
then minm ( a − b) + 2β, η(a, b, |β1|), η(a, b, |β2|) + 2β2 > 2 is necessary and sufficient
for exact recovery, where η is defined in section III-A.
A. Necessary Conditions
In this section we provide necessary conditions for exact recovery in the binary symmetric
SBM with M-ary side information.
Proof: [Proof of converse part of Theorem 6]
Note that unlike Sections III, IV, the side information might not be symmetric. Hence, we
need to define the events of Section III-A for both communities A and B. Let H1 and H2 be
subsets of A and B, respectively, with |H1 | = |H2 | =

△1i = i ∈ H1 : E[i, H1 ] ≤

n
.
log3 (n)

We define the following events:

log(n)
log log(n)


log(n)
≤ T E[i, B]
FiH1 = i ∈ H1 : T E[i, A\H1 ] + hi + T + T
log log(n)

△1 = ∀i ∈ H1 : △1i is true

F H1 = ∪i∈H1 FiH1

△2i = i ∈ H2 : E[i, H2 ] ≤

log(n)
log log(n)


log(n)
≤ T E[i, A]
FiH2 = i ∈ H2 : T E[i, B\H2 ] − hi + T + T
log log(n)

△2 = ∀i ∈ H2 : △2i is true

August 17, 2017

DRAFT

25

F H2 =



∪i∈H2 FiH2

Note that hi is distributed according to α+,m and α−,m if node i ∈ A, B, respectively. We will
prove this part of the theorem via several lemmas. Note that Lemmas 3, 4, 5, 6 extend directly
to our case here using the above definitions for both communities A and B. To complete the
proof, we need to show show when P(FiH1 ) >

log3 (n)
n

log(10) and P(FiH2 ) >

log3 (n)
n

log(10) are

true.
Lemma 10: Both P(FiH1 ) and P(FiH2 ) are greater than

log3 (n)
n

log(10) for sufficiently large n

if one of the following is true:

√ 2
√


For
m
:
α
=
6
α
,
h
=
o(log(n)),
if
(
a
−
b) < 2

+,m
−,m
m




√

For m : log(α+,m ) = log(α−,m ) = −β log(n), β > 0, if (√a − b)2 + 2β < 2



For m : hm = β log(n), |β| < T (a−b)
, log(αsgn,m ) = o(log(n)), if η(a, b, |β|) < 2


2




For m : hm = β log(n), |β| < T (a−b) , log(αsgn,m ) = −β ′ log(n), β ′ > 0, if η(a, b, |β|) + 2β ′ < 2
2
Proof: ]
Let Wi ∼ Bern(p), Zi ∼ Bern(q) and define l =

n
2

and Γ(t) = log(EX [etx ]) for a random

variable X. Then, we have the following:

P(FiH1 )

=P

n
X
2

i=1

M
X

≥

n
− 3n
2
log (n)

(Zi ) −

≥

i=1

hi
log(n)
(Wi ) ≥
+1+
T
log log(n)

n
2

α+,m P

m=1

(a)

X

M
X

X

log(n)
hm
+1+
[Zi − Wi ] ≥
T
log log(n)
i=1

−l t∗m am −Γ(t∗m )+|t∗m |δ

α+,m e

m=1







(1 − o(1))
(20)

2

where (a) holds by defining δ =

log 3 (n)
,
l

am = 1l ( hTm +1+ loglog(n)
)+δ, t∗m = arg supt∈R am t−Γ(t)
log(n)

and by using Lemma 14 in the Appendix. Similarly, we have:
n

X
2
log(n)
hm
H2
+1+
[Zi − Wi ] ≥ −
P(Fi ) ≥
α−,m P
T
log log(n)
m=1
i=1

M
X

August 17, 2017

DRAFT

26

≥

M
X

m=1

−l t∗m am −Γ(t∗m )+|t∗m |δ

α−,m e



(1 − o(1))
(21)

log(n)
)
log log(n)

where am = 1l (− hTm + 1 +

+ δ.

Without loss of generality, we will focus on m = 1. Following similar analysis as before we
have the following cases:
•

If h1 = o(log(n)) and α+,1 6= α−,1 , then t∗1 = 21 T for both (20), (21). Hence, by substituting
in (20), (21), we have:
P(FiH1 )

√ √
−0.5( a− b)2 +o(1)

≥n

+

M
X

α+,m e

M
X

α−,m e−l

−l t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(22)

t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(23)

m=2
√

P(FiH2 ) ≥ n−0.5(
√

√
a− b)2 +o(1)

+

m=2

√

Thus, it is clear that if ( a− b)2 ≤ 2−ε for some 0 < ε < 2, then P(FiH1 ) and P(FiH2 )are
ε

both greater than n−1+ 2 >
•

log3 (n)
n

log(10) for sufficiently large n.

If h1 = 0 and log(α+,1 ) = log(α−,1 ) = −β log(n), β > 0, then t∗1 = 21 T for both (20), (21).
Hence, by substituting in (20), (21), we have:
P(FiH1 )

P(FiH2 )

√ √
−0.5( a− b)2 −β+o(1)

≥n

+

M
X

−l t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(24)

−l t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(25)

α+,m e

m=2

√ √
−0.5( a− b)2 −β+o(1)

≥n

+

M
X

m=2

α−,m e

√
√
Thus, it is clear that if ( a − b)2 + 2β ≤ 2 − ε for some 0 < ε < 2, then P(FiH1 ) and
ε

P(FiH2 )are both greater than n−1+ 2 >

•

log3 (n)
n

log(10) for sufficiently large n.

If h1 = β log(n), for 0 < β < T a−b
, then t∗1 = log( γ+β
) for (20) and t∗1 = T1 log( γ−β
)
2
bT
bT
p
for (21), where γ = β 2 + abT 2 . Hence, by substituting in (20), (21), we have:
P(FiH1 ) ≥ e− log(n)

August 17, 2017

0.5η(a,b,β)−



log(α+,1 )
+o(1)
log(n)

+

M
X

m=2

α+,m e−l

t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1)) (26)

DRAFT

27

P(FiH2 )

− log(n) 0.5η(a,b,β)−β−

≥e



log(α−,1 )
+o(1)
log(n)

+

m=2

Then, if log(α+,1 ) = o(log(n)), this implies that
P(FiH1 )

P(FiH2 )

−0.5η(a,b,β)+o(1)

≥n

M
X

+

M
X

−l t∗m am −Γ(t∗m )+|t∗m |δ

α−,m e

≥n

M
X

+

m=2

(1 − o(1))
(27)

log(α−,1 )
log(n)

= −β + o(1). Hence we have:

−l t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(28)

−l t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(29)

α+,m e

m=2

−0.5η(a,b,β)+o(1)



α−,m e

Thus, it is clear that if η(a, b, β) ≤ 2 − ε for some 0 < ε < 2, then P(FiH1 ) and P(FiH2 )are
ε

both greater than n−1+ 2 >

log3 (n)
n

log(10) for sufficiently large n.
′

On the other hand, if log(α+,1 ) = −β log(n)), this implies that
′′

′′

log(α−,1 )
log(n)

′

′′

= −β , for some

β > 0 and β = β − β . Hence we have:
P(FiH1 )

P(FiH2 )

′

−0.5η(a,b,β)−β +o(1)

≥n

+

M
X

−l t∗m am −Γ(t∗m )+|t∗m |δ

α+,m e

m=2

′′

−0.5η(a,b,β)+β−β +o(1)

≥n

+

M
X

m=2
′

−0.5η(a,b,β)−β +o(1)

=n

+

M
X

m=2



(1 − o(1))

−l t∗m am −Γ(t∗m )+|t∗m |δ

α−,m e

−l t∗m am −Γ(t∗m )+|t∗m |δ

α−,m e





(30)

(1 − o(1))

(1 − o(1))

Thus, it is clear that if η(a, b, β) + 2β ≤ 2 − ε for some 0 < ε < 2, then P(FiH1 ) and
′

ε

P(FiH2 )are both greater than n−1+ 2 >

•

log3 (n)
n

log(10) for sufficiently large n.

< β < 0, then following the same analysis as the last point, we
If h1 = β log(n), for T b−a
2
get the following:
if log(α−,1 ) = o(log(n)), this implies that
P(FiH1 ) ≥ n−0.5η(a,b,|β|)+o(1) +
P(FiH2 )

August 17, 2017

−0.5η(a,b,|β|)+o(1)

≥n

+

log(α+,1 )
log(n)

M
X

= −β + o(1). Hence we have:
t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(31)

−l t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(32)

α+,m e−l

m=2
M
X

m=2

α−,m e

DRAFT

28

Thus, it is clear that if η(a, b, |β|) ≤ 2 − ε for some 0 < ε < 2, then P(FiH1 ) and P(FiH2 )are
ε

both greater than n−1+ 2 >

log3 (n)
n

log(10) for sufficiently large n.
′′

On the other hand, if log(α−,1 ) = −β log(n)), this implies that
′

′′

log(α+,1 )
log(n)

′

′

= −β , for some

β > 0 and β = β − β . Hence we have:
P(FiH1 )

P(FiH2 )

′′

−0.5η(a,b,|β|)−β +o(1)

≥n

−l t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(33)

−l t∗m am −Γ(t∗m )+|t∗m |δ



(1 − o(1))

(34)

α+,m e

m=2

′′

−0.5η(a,b,|β|)−β +o(1)

≥n

+

M
X

+

M
X

m=2

α−,m e

Thus, it is clear that if η(a, b, |β|) + 2β ≤ 2 − ε for some 0 < ε < 2, then P(FiH1 ) and
′′

ε

P(FiH2 )are both greater than n−1+ 2 >

log3 (n)
n

log(10) for sufficiently large n.

B. Sufficient Conditions
In this section we prove the achievable part of Theorem 6 by providing an efficient algorithm
that achieves exact recovery down to the optimal information theoretic threshold. The algorithm
is decomposed into two stages. The first stage of the algorithm is the same as Section III-B.
The second stage, the local modification is however different.
′

′

After the first stage, we have G2 , the side information y, A and B . We locally modify the
′

community assignment as follows: if a node i ∈ A , we flip its membership if the number of of
′

′

edges between i and B is greater than or equal the number of of edges between i and A plus
hi
T

′

′

and for node j ∈ B , we flip its membership if the number of of edges between j and A is
′

greater than or equal the number of of edges between j and B minus

hi
.
T

If the the number of

flips in each cluster is not the same, keep the clusters unchanged.
Lemma 11: There exists large enough D such that, with high probability, the algorithm
described above will successfully recover the communities from the observed graph and side
information if the following are satisfied simultaneously:

August 17, 2017

DRAFT

29


√
√


( a − b)2 > 2, for any m : α+,m 6= α−,m and hm = o(log(n))





√

(√a − b)2 + 2β > 2, for any m : log(α+,m ) = log(α−,m ) = −β log(n), β > 0



, log(αsgn(β),m ) = o(log(n))
η(a, b, |β|) > 2, for any m : hm = β log(n), |β| < T (a−b)


2




η(a, b, |β|) + 2β ′ > 2 for any m : hm = β log(n), |β| < T (a−b) , log(αsgn(β),m ) = −β ′ log(n), β ′ > 0
2
Proof:
Recall we defined Pe = P(node i to be misclassified). Following the same analysis as in the
proof of Lemma 2, we get:
n

n

δ2
 (1−δ)
M
X2
X
1X
α+,m P
Zi +
Wi ≥
Pe ≤
2 m=1
i=1
i=1
(1−δ) n
2

δn
2

 X
M
X
1X
α−,m P
Zi +
Wi ≥
2 m=1
i=1
i=1

2D
n
(1−δ) n2 − log(n)

X

2D
δn
− log(n)
n
2

i=1

X

2D
n
(1−δ) n2 − log(n)

2D
δn
− log(n)
n
2

X

Wi +

i=1

Wi +

i=1

X
i=1


hm
Zi +
+
T
hm
Zi −
T

(35)



Using a similar lemma as Lemma 17, we can show that for any term of the M terms above:
1

•

√

if hm = o(log(n)) and α+,m 6= α−,m , then this term can be upper bounded by n− 2 (

√
a− b)2 +o(1)

n−(1+Ω(1)) .

•

if hm = 0 and log(α+,m ) = log(α−,m ) = −β log(n), β > 0, then this term can be upper
1

√

bounded by n− 2 (
•

√
a− b)2 −β+o(1)

+ n−(1+Ω(1)) .

and log(αsgn(β),m ) = o(log(n)), then this term can be upper
if hm = β log(n), |β| < T (a−b)
2
1

bounded by n− 2 η(a,b,|β|)+o(1) + n−(1+Ω(1)) .

•

if hm = β log(n), |β| < T (a−b)
and log(αsgn(β),m ) = −β log(n), β > 0, then this term can
2
′

1

be upper bounded by n− 2 η(a,b,|β|)−β

•

′

+o(1)

′

+ n−(1+Ω(1)) .

< |β| and log(α−sgn(β),m ) = −β log(n), β > 0, then this term
if hm = β log(n), T (a−b)
2
′

′

′

can be upper bounded by n−β + n−(1+Ω(1)) .

Combining all the above with a simple union bound over all nodes concludes the proof. Note
′

that the last case, which implies that β > 1 is also a needed condition for recovery, was not
included in Theorem 6 as we only show that it is sufficient but we could not show that it is
necessary for the M-ary case. However, we believe it is also necessary as shown, as a special
case, in Lemma 12.

August 17, 2017

DRAFT

+

30

VI. C ONCLUSION

AND

O PEN P ROBLEMS

In this paper, the binary symmetric stochastic block model is studied with side information.
We addressed the problem of the effect of side information on the phase transition threshold
for exact recovery. We first considered two popular models of side information, namely: side
information observed through binary symmetric or binary erasure channels. We showed that, for
both cases, side information does not always help. In fact even when the quality or quantity
of side information improves as n → ∞, we showed that for side information to help exact
recovery, we need a certain rate by which the quality or quantity improves. We also, provided
an efficient algorithm which succeeds all the way down to the thresholds, for both cases, using a
partial recovery algorithm combined with a local improvement procedure. Finally, we generalized
our results to M-ary side information with finite M.
A PPENDIX I
) and η(a, b, β) = a + b + β − 2 Tγ +
Lemma 12: Recall that c = log( 1−α
α
p
T = log( ab ), γ = β 2 + abT 2 . Also, recall from Section III-A that
P(FiH )

=P

n
X
2

i=1

n
− 3n
2
log (n)

Zi −

X
i=1

log(n)
Wi − cyi ≥ T + T
log log(n)

β
T

log( γ+β
), where
γ−β



where Wi ∼ T ∗ Bern(p), Zi ∼ T ∗ Bern(q) and yi ∈ {±1} ∼ {(1 − α), α}.
For sufficiently large n, P(FiH ) >

log3 (n)
n

log(10), if one of the following is satisfied:


√ 2
√


a
−
b) < 2
For
c
=
o(log(n)),
if
(



For c = β log(n), β > 0, for any a, b, β




For c = β log(n), β > 0, for a, b, β : β >
Proof:
Define l =

n
2

P(FiH )

T (a−b)
2

if η(a, b, β) > 2 and β < 1

and Γ(t) = log(EX [etx ]) for a random variable X. Then, we have the following:

=P

n
X
2

i=1
n
2

≥P
August 17, 2017

if η(a, b, β) < 2

X

n
− 3n
2
log (n)

Zi −

X
i=1

log(n)
Wi − cyi ≥ T + T
log log(n)

log(n)
[Zi − Wi ] ≥ cyi + T + T
log log(n)
i=1




DRAFT

31
n

 X
log(n)
1 2
1
)
=(1 − α)P
[Zi − Wi ] ≥ (c + T + T
l i=1
l
log log(n)
n

 X
log(n)
1 2
1
)
+ αP
[Zi − Wi ] ≥ (−c + T + T
l i=1
l
log log(n)


(a)
−l t∗2 a2 −Γ(t∗2 )+|t∗2 |δ
−l t∗1 a1 −Γ(t∗1 )+|t∗1 |δ
(1 − o(1))
(1 − o(1)) + αe
≥(1 − α)e
2

where (a) holds by defining δ =

log 3 (n)
,
l

(36)

a1 = 1l (c + T + T loglog(n)
) + δ, a2 = 1l (−c + T +
log(n)

) + δ, t∗1 = arg supt∈R ta1 − Γ(t), t∗2 = arg supt∈R ta2 − Γ(t) and by using Lemma 14.
T loglog(n)
log(n)

Now, we calculate t∗1 and t∗2 . First, we simplify the function inside the supremum. Note that

both supremums are very similar, so we will do the analysis for one of them, and the second
should follow similarity.

a 
a
ta1 − Γ(t) = ta1 − log 1 − q(1 − ( )t ) − log 1 − p(1 − ( )−t )
b
b
Now, it is easy to check that the right hand side is concave in t ∈ R. Hence, taking the
derivative with respect to t, we get:
p( ab )−t
q( ab )t
+
=
a1 −
1 − q(1 − ( ab )t ) 1 − p(1 − ( ab )−t )


a( ab )−t
b( ab )t
2c
2T
2T
2
log(n)
=0
+
+
+
+
−
n
log(n) log(n) log log(n) log 13 (n) 1 − q(1 − ( ab )t ) 1 − p(1 − ( ab )−t )
(37)
Now, we divide our analysis into two cases:
•

Case one: c is o(log(n)). In that case, the first four terms in (37) is o(1). This suggests that
t∗ = 12 . Hence, by substituting back in (37), we get:
r
r
a 
b 
1
)) − log 1 − p(1 − (
)
ta1 − Γ(t) = a1 − log 1 − q(1 − (
2
b
a
q
pa
b
p(1
−
(
))
(a) 1
q(1 − ( b ))
a
q
pa +
≤ a1 +
2
1 − q(1 − ( b )) 1 − p(1 − ( b ))
a

q

p


a(1 − ( ab ))
b(1 − ( ab ))
log(n)
q
p
=
+ o(1)
+
n
1 − q(1 − ( ab )) 1 − p(1 − ( b ))
a
August 17, 2017

DRAFT

32



√ 2
log(n) √
=
( a − b) + o(1)
n

(b)

(38)

p
−x
where (a) holds because log(1 − x) ≥ 1−x
and (b) holds because both (1 − q(1 − ( ab )))
p
and (1 − q(1 − ( ab ))) → 1 as n → ∞. Hence, substituting in one of the supremums
of (36), we have:

e−l

t∗1 a1 −Γ(t∗1 )+|t∗1 |δ



1 √
( a−
2

(1 − o(1)) ≥ e− log(n)

√



b)2 +o(1)

(1 − o(1))

Finally, following the same steps for the second supremum and substituting in (36), we
have:
√

P(FiH ) ≥ (1 − α)n−0.5(
√

= n−0.5(

√
a− b)2 +o(1)

√

+ αn−0.5(

√
a− b)2 +o(1)

√
a− b)2 +o(1)

√
√
ε
Thus, if ( a − b)2 ≤ 2 − ε for some 0 < ε < 2, then P(FiH ) ≥ n−1+ 2 >

log3 (n)
n

log(10)

for sufficiently large n. This proves the first case of Lemma 12.
•

1
,
nβ

β > 0. In this case c = β log(n) + o(1). Hence, substituting in (37),
p
γ−β
1
∗
)
and
t
=
log(
),
where
γ
=
β 2 + abT 2 . Hence,
this suggests that t∗1 = T1 log( γ+β
2
bT
T
bT
Case two: α =

by substituting back in (37) and following the same ideas as in (38), we get:


a ∗
a ∗
log(n)
2βt∗ + b(1 − ( )t ) + a(1 − ( )−t ) + o(1)
n
b
b

γ+β
γ+β
abT
log(n) 2β
log(
)+a+b−
−
+ o(1)
=
n
T
bT
T
γ+β

log(n)
2γ
β
γ+β
=
a+b+β−
+ log(
) + o(1)
n
T
T
γ−β
log(n)
(η(a, b, β) + o(1))
=
n

ta1 − Γ(t) ≤

(39)

Hence, substituting in one of the supremums of (36), we have:

−l t∗1 a1 −Γ(t∗1 )+|t∗1 |δ

e



−

(1 − o(1)) ≥ e

log(n)
2



η(a,b,β)+o(1)

(1 − o(1))

Finally, following the same steps for the second supremum and substituting in (36), we
have:
August 17, 2017

DRAFT

33

P(FiH ) ≥ (1 − α)n−0.5η(a,b,β)+o(1) + αn−0.5η(a,b,β)+β+o(1)
= n−0.5η(a,b,β)+o(1) (2 − α)
ǫ

Thus, if η(a, b, β) ≤ 2 − ε for some 0 < ε < 2, then P(FiH ) ≥ n−1+ 2 >

log3 (n)
n

log(10) for

sufficiently large n. This proves the second case of Lemma 12.

For the last case of Lemma 12, we begin as in (36) but take a different approach:

P(FiH )

≥P

n
X
2

log(n)
[Zi − Wi ] ≥ cyi + T + T
log log(n)
i=1

=(1 − α)(1 − P
+ α(1 − P

n
X
2


log(n)
)
[Zi − Wi ] ≤ c + T + T
log log(n)
i=1

n
X
2

(a)


log(n)
) )
[Zi − Wi ] ≤ (−c + T + T
log log(n)
i=1


Pn
log(n)
−t( 2 [Z −W ])

≥1 − (1 − α)e−n supt>0
−n supt>0

− αe



−t
n

−t
n

1
log E(e
c+T +T log log(n) − n



log(n)
1
log E(e−t(
−c+T +T log
−n
log(n)

i

i=1

Pn
2 [Z −W ])
i )
i=1 i



i

)

(40)

where (a) holds by Chernoff bound. Note that unlike the previous cases, here the supremum
is only on t > 0. Again, we will now focus on calculating one of the supremums in (40).
By direct computation of the logarithmic term we get:
 P n2
 (a) n 
p −t 
n
p t 
log 1 − q(1 −
) +
log 1 − p(1 −
)
log E e−t i=1 [Zi−Wj ] =
2
q
2
q
(b)
n
p −t
n
p t
≤−
q(1 −
)−
p(1 −
)
2
q
2
q

where (a) follows from the fact that Wi , Zi are independent random variables ∀i, and (b)
holds because log(1 − x) ≤ −x. Substituting in one of the supremums:

August 17, 2017

DRAFT

34



Pn

−t
log(n)
1
2
sup
c+T +T
− log E(e−t( i=1 [Zi −Wi ]) )
log log(n)
n
t>0 n
log(n)
a
1
a 
≥
sup −t(β + o(1)) + a + b − b( )−t − a( )t
n t>0
2
b
b

(41)

Again, by concavity of the last equation in t, we calculate the first derivative to get:

−β −

aT a t bT a −t
( ) +
( ) =0
2 b
2 b

(42)

Hence, following the same analysis as before, we can show that t∗ for the first and second
supremums can be calculated as:

1
T

log( γ−β
) and
aT

1
T
T (b−a)
2

t to be greater than zero. Thus, we need β <

log( γ+β
), respectively. Since we need
aT
for the first supremum, which can not

be true, since β is positive and b < a. Hence, by the concavity of the function and the fact
that it approaches −∞ as t → ∞, the optimal t for the first supremum is t∗1 = 0. On the
other hand, for the second supremum, we need β >
Thus, assuming β >

T (a−b)
,
2

T (a−b)
2

for t to be positive.

substituting in (40), we get:

1

P(FiH ) ≥ 1 − (1 − α)e0 − αn− 2 η(a,b,β)+β
(a)

1

= n−β − n− 2 η(a,b,β)

where (b) holds by using the fact that α = n−β . Hence, if β ≤ 1 − ε1 and 12 η ≥ 1 + ε2 ,
then P(FiH ) ≥ n−1 (nε1 − n−ε2 ) >

log3 (n)
n

log(10) for sufficiently large n. This proves the

third and last case of Lemma 12.

Lemma 13: Recall from Section IV-A that

P(FiH )

= ǫP

n
X
2

i=1

n
− 3n
2
log (n)

Zi −

X
i=1

log(n)
Wi ≥ 1 +
log log(n)



where Wi ∼ Bern(p), Zi ∼ Bern(q) and ǫ ∈ (0, 1).
For sufficiently large n, P(FiH ) >

August 17, 2017

log3 (n)
n

log(10), if one of the following is satisfied:

DRAFT

35

√
√
if ( a − b)2 < 2
√

For log(ǫ) = −β log(n), β > 0, if (√a − b)2 + 2β < 2


For log(ǫ) = o(log(n)),

Proof:
Define l =

n
2

and let Γ(t) = log(EX [etx ]) for a random variable X. Then, we have the

following:

P(FiH )

= ǫP

n
X
2

i=1

n
− 3n
2
log (n)

(Zi ) −

X
i=1

log(n)
(Wi ) ≥ 1 +
log log(n)

n
X
2

log(n)
[Zi − Wi ] ≥ 1 +
≥ ǫP
log log(n)
i=1

(a)
∗
∗
∗
≥ ǫe−l t a−Γ(t1 )+|t1 |δ (1 − o(1))

−l t∗ a−Γ(t∗1 )+|t∗1 |δ +log(ǫ)
=e
(1 − o(1))
2

where (a) holds by defining δ =

log 3 (n)
,
l

a = 1l (1 +

log(n)
)
log log(n)





(43)

+ δ, t∗1 = arg supt∈R at − Γ(t) and

by using Lemma 14 in the Appendix.
Now, we calculate t∗ . First, we simplify the function inside the supremum.


ta − Γ(t) = ta − log 1 − q(1 − et ) − log 1 − p(1 − e−t )

(44)

By concavity of the above function in t and by taking the derivative with respect to t and
equating to zero, we get:
pe−t
qet
+
=
1 − q(1 − et ) 1 − p(1 − e−t )


log(n)
2
2
2
ae−t
bet
=0
+
+
+
−
n
log(n) log log(n) log 13 (n) 1 − q(1 − et ) 1 − p(1 − e−t )

a−

(45)

Now, since the first three terms in (45) is o(1). Thus, this suggests that t∗ = 12 T and T =
log( ab ). Hence, by substituting back in (44), we get:
1
ta − Γ(t) = aT − log 1 − q(1 − (
2
August 17, 2017

r

a 
)) − log 1 − p(1 − (
b

r

b 
)
a
DRAFT

36

q

b
))
q(1 − ( b ))
1
a
q
pa +
≤ aT +
2
1 − q(1 − ( b )) 1 − p(1 − ( b ))
a

p(1 − (

pa

(a)

√

log(n) √
( a − b)2 + o(1)
n

=

where (a) holds because log(1 − x) ≥

−x
.
1−x

(46)
Hence, substituting in the supremum of (43), we

have:
−l t∗ a−Γ(t∗ )+|t∗ |δ

e



− log(n)

(1 − o(1)) ≥ e

1 √
( a−
2


√ 2
b) +o(1)

(1 − o(1))

(47)

Finally, substituting in (43), we have:
√

P(FiH ) ≥ ǫn−0.5(

√
a− b)2 +o(1)

(48)

√
√
Thus, if log(ǫ) = o(log(n)), then, it is clear that if ( a − b)2 ≤ 2 − ε for some 0 < ε < 2,
ε

then P(FiH ) ≥ n−1+ 2 >

log3 (n)
n

log(10) for sufficiently large n. This proves the first case of

Lemma 13.
√

√
On the other hand, if log(ǫ) = −β log(n), for some β > 0, then, it is clear that if ( a −
ε

b)2 + 2β ≤ 2 − ε for some 0 < ε < 2, then P(FiH ) ≥ n−1+ 2 >

log3 (n)
n

log(10) for sufficiently

large n. This proves the second and last case of Lemma 13.
Lemma 14: Let X1 , · · · , Xn be a sequence of i.i.d random variables. Define Γ(t) = log(E[etX ]).
Then, for any a, ǫ ∈ R:
n

1X
P
Xi ≥ a − ǫ ≥ e−n
n i=1

t∗ a−Γ(t∗ )+|t∗ |ǫ


2 
σX̂
1− 2
nǫ

where t∗ = arg supt∈R ta − Γ(t), X̂ is a random variable with the same alphabet as X but
∗

distributed according to

et x P(x)
EX [et∗ x ]

2
are the mean and variance of X̂, respectively.
and µX̂ , σX̂

Proof:
n
n


1X
1X
Xi ≥ a − ǫ ≥ P a − ǫ ≤
Xi ≤ a + ǫ
P
n i=1
n i=1
Z
=
P(x1 ) · · · P(xn )dx1 · · · dxn
P
1
a−ǫ≤ n

August 17, 2017

n
i=1

Xi ≤a+ǫ

DRAFT

37
Pn

Pn

(EX [et i=1 xi ])(et i=1 xi )
P
Pn
P(x1 ) · · · P(xn )dx1 · · · dxn
=
t n
i=1 xi ])(et
i=1 xi )
1 Pn
(E
[e
X
X
≤a+ǫ
a−ǫ≤ n
i=1 i

Z
n  txi
Y
(b)
e P(xi )
−n(ta−Γ(t)+|t|ǫ)
dxi
≥e
tx ]
1 Pn
E
[e
X
a−ǫ≤ n
X
≤a+ǫ
i
i=1
i=1


n
X
1
(c) −n(ta−Γ(t)+|t|ǫ)
=e
PX̂n a − ǫ ≤
X̂i ≤ a + ǫ
n i=1


2
(d)
+ (nµX̂ − na)2
nσX̂
−n(ta−Γ(t)+|t|ǫ)
(49)
1−
≥e
n2 ǫ2
(a)

Z

where (a) holds for any t ∈ R such that the expectation holds, (b) holds because a − ǫ ≤
Pn
etx P(x)
1
X̂
≤
a
+
ǫ,
(c)
holds
because
defines a probability distribution [38] on a new
i
i=1
n
EX [etx ]

random variable X̂ with the same alphabet as X, and (d) holds by Chebyshev’s inequality and
2
to be the mean and variance of X̂, respectively.
defining µX̂ , σX̂

Now, choose t = t∗ = arg supt∈R ta − Γ(t). Since this function is concave in t ∈ R [38], then
by setting the first derivative to zero, we have a =
we can show that µX̂ =

[xetx ]

EX
E[etx ]

∗

EX [xet x ]
.
E[et∗ x ]

Also, by direct computation of µX̂ ,

. This means that at t = t∗ , we have µX̂ = a. Thus, substituting

back in (49), we get:

 X
n
σ2 
1
∗
∗
∗
Xi ≥ a − ǫ ≥ e−n(t a−Γ(t )+|t |ǫ) 1 − X̂2
P
n i=1
nǫ
2

Now, in our model ǫ =

log 3 (n)
n

and X = Z − W , where Z ∼ T*Bern(q) and W ∼ T*Bern(p),

2
is in the order of
where T = log( ab ). Hence, we can easily show that σX̂

log(n)
,
n

and hence, we

have:
 X

n

1
P
Xi ≥ a − ǫ ≥ e−n(ta−Γ(t)+|t|ǫ) 1 − o(1)
n i=1
which concludes our proof.

p

Lemma 15: Define η(a, b, β) = a + b + β − 2 Tγ +

β
T

log( γ+β
), where T = log( ab ), γ =
γ−β

β 2 + abT 2 and a, b, β > 0 with a > b. Then, β > 1 implies η > 2.
Proof:
Let a + b − β − 2 Tγ +

August 17, 2017

β
T

log( γ+β
) = ψ(a, b, β). Then, from the definition of η, we have:
γ−β

DRAFT

38

η(a, b, β) − 2β = ψ(a, b, β)

(50)
∗

∗

+β
Note that ψ(a, b, β) is convex in β. Hence, at the optimal β ∗ , we can show that log( γγ ∗ −β
∗) = T.

Using this fact and by substituting in (50), we have:

η(a, b, β) − 2β ≥ a + b − 2
Now by the definition of γ, we have γ + β =
a
b

=

abT 2
,
(γ ∗ −β ∗ )2

abT 2
γ−β

γ∗
T

and using the fact that

(51)
γ ∗ +β ∗
γ ∗ −β ∗

= ab , we have

which implies that γ ∗ = bT + β ∗ . Hence, by substituting in (51), we get:
β∗
η(a, b, β) − 2β ≥ a − b − 2
T

Also, we can show that at β ∗ , γ ∗ = β ∗ ( a+b
). This implies that β ∗ =
a−b

(52)
T (a−b)
.
2

Substituting

in (52), we get: η(a, b, β) − 2β ≥ 0, which implies that η > 2 when β > 1.
(k)

Lemma 16: Define Pn := P
Zi ∼ Bern(q). Then,

Pm

i=1 (Zi


− Wi ) ≥ 0 , where m = 2k( n2 − k), Wi ∼ Bern(p),

Pn(k) ≤ e−2m

√
log(n) 1 √
( 2 ( a− b)2 )
n

Proof:

Pn(k)

=P

X
m
i=1

(Zi − Wi ) ≥ 0

(a)

1

≤ e−m supt>0 − m log(E[e

(b)

≤ e−m

(c)

log(n)
n

≤ e−2m

t



Pm
i=1 (Zi −Wi ) ])

supt>0 a+b−bet −ae−t

√
log(n) 1 √
( 2 ( a− b)2 )
n

(53)

where (a) holds by Chernoff bound, (b) holds because Zi and Wi are both i.i.d ∀i and (c) holds
by evaluating the supremum to get t∗ = 21 T and using the fact that log(1 − x) ≤ −x.

August 17, 2017

DRAFT

39

Lemma 17: Let Wi ∼ Bern(p), Zi ∼ Bern(q), yi ∈ {1, −1} with probabilities (1 − α), α,
2D
Pδ n2 − log(n)
P(1−δ) n
Pδ n2
P(1−δ) n − 2D n
n
Zi + Tc yi ).
respectively. Define Pe = P( i=1 2 Zi + i=1
Wi ≥ i=1 2 log(n) Wi + i=1

Then,


√ √

− 21 ( a− b)2 +o(1)

If
c
=
o(log(n)),
P
≤
n
+ n−(1+Ω(1))
e



1
, Pe ≤ (2 − α)n− 2 η(a,b,β)+o(1) + n−(1+Ω(1))
If c = β log(n) : 0 < β < T (a−b)
2




1
If c = β log(n) : β > T (a−b) ,
Pe ≤ (1 − α)n− 2 η(a,b,β)+o(1) + n−β + n−(1+Ω(1))
2
Proof:
By upper bounding Pe , we get:

Pe ≤P
≤P
≤P
(a)

≤P
P

n
 (1−δ)
X2

Zi +

i=1

n
X
2

i=1

X

Wi ≥

i=1

2D
(1−δ) n2 − log(n)
n

n

i=1

δ2
X

n
2

n
2

2D
δn+ log(n)
n

i=1

X

X

X

Zi +

i=1

Zi −

Wi ≥
Wi +

i=1

X
i=1

i=1

c
Wi + yi
T

c
Wi + yi
T

c
Wi ≥ yi
T







n
X
2


c
(Zi − Wi ) ≥ yi − ψδ log(n) +
T
i=1

2D
n
 δn+X
log(n)

i=1

=(1 − α)P
αP

P

2D
(1−δ) n
− log(n)
n
2

n

δ2
X

Wi ≥ ψδ log(n)



n
X
2


c
(Zi − Wi ) ≥ − ψδ log(n) +
T
i=1

n
X
2


c
(Zi − Wi ) ≥ − − ψδ log(n) +
T
i=1

2D
n
 δn+X
log(n)

i=1

Wi ≥ ψδ log(n)

where (a) holds by defining ψ = √ 1
δ

log( δ1 )



(54)

.

Now we bound the second term. A multiplicative Chernoff bound that states that for a sequence
P
of n i.i.d random variables Xi : P( ni=1 ≥ tµ) ≤ ( et )−tµ , where µ = nE[X]. Applying this bound
August 17, 2017

DRAFT

40

to the second term with µ = a(δ log(n) + 2D) and t =

P

2D
n
 δn+X
log(n)

i=1

Wi ≥ ψδ log(n)



ψδ log(n)
,
a(δ log(n)+2D)

we get:

−ψδ log(n)
ψδ log(n)
≤
ae(δ log(n) + 2D)

− √log(n)
ψ
log( 1 )
δ
=
2D
ae(1 + δ log(n) )


log(1+ 2D )
log log( 1 )
log(δ)+ 1
1+log(a)
δ log(n)
2
δ
√ 1
log(n) √
+ √
+
log( 1 )
log( 1 )
log( )
δ
δ
δ
=e


√ 1
log(1+ 2D )
δ log(n)


(a)

−

=n

log( δ )

1−

log( 1 )
δ

+o(1)

(55)

where (a) holds because δ → 0 as D → ∞. Note that we can find D large enough such that
2D
log(1+ δ log(n)
)

log( δ1 )

< 1. Hence, we get:

P

2D
n
 δn+X
log(n)

i=1

Wi ≥ ψδ log(n)



≤ n−(1+Ω(1))

(56)

Now for the first term in (54), we use Chernoff bound as follows:
n
X
2

n

X

2
c
c
(Zi − Wi ) ≥ − ψδ log(n) + αP
(Zi − Wi ) ≥ − − ψδ log(n)
(1 − α)P
T
T
i=1
i=1


2t
2t
−n
supt1 >0 n1 Tc −ψδ log(n) −log(E[et1 Z−t1 W ])
−n
supt2 >0 n2 − Tc −ψδ log(n) −log(E[et2 Z−t2 W ])
2
2
≤ (1 − α)e
+ αe

(a)

≤ (1 − α)e−

log(n)
2

c
supt1 >0 2t( T log(n)
−ψδ)+a+b−bet1 −ae−t1

+ αe−

log(n)
2

c
supt2 >0 2t2 (− T log(n)
−ψδ)+a+b−bet2 −ae−t2

(57)
where (a) holds because log(1 − x) ≤ −x. Now, we calculate t∗1 and t∗2 .
Note that ψδ → 0 as D → ∞. Hence, we will replace ψδ by o(1) for sufficiently large D.
Now we divide our analysis into three cases:
•

If c = o(log(n)), this suggests that t∗1 = t∗2 = 21 T . Hence, substituting in (57), we get:

(1 − α)P

August 17, 2017

n

X

2
c
c
(Zi − Wi ) ≥ − ψδ log(n) + αP
(Zi − Wi ) ≥ − − ψδ log(n)
T
T
i=1
i=1

n
X
2

DRAFT

41

1

√

≤ n− 2 (
•

√
a− b)2 +o(1)

(58)

, then we can show that that t∗1 = log( γ+β
) and
If c = β log(n), for 0 < β < T (a−b)
2
bT
p
t∗2 = log( γ−β
), where γ = β 2 + abT 2 . Hence, substituting in (57), we get:
bT
(1 − α)P

n
X
2

n

X

2
c
c
(Zi − Wi ) ≥ − ψδ log(n) + αP
(Zi − Wi ) ≥ − − ψδ log(n)
T
T
i=1
i=1
1

≤ (2 − α)n− 2 η(a,b,β)+o(1)
•

If c = β log(n), for β >

(59)
T (a−b)
,
2

then we can show that that t∗1 = log( γ+β
) and t∗2 = 0.
bT

Hence, substituting in (57), we get:

(1 − α)P

n

X

2
c
c
(Zi − Wi ) ≥ − ψδ log(n) + αP
(Zi − Wi ) ≥ − − ψδ log(n)
T
T
i=1
i=1

n
X
2
1

≤ (1 − α)n− 2 η(a,b,β)+o(1) + n−β

(60)

Using the last three displayed equations and (56) and substituting in (54) concludes the proof
of the lemma.

R EFERENCES
[1] P. Holland, K. Laskey, and S. Leinhardt, “Stochastic blockmodels: First steps,” Social Networks, vol. 5, no. 2, pp. 109–137,
June 1983.
[2] A. Zhang and H. Zhou, “Minimax rates of community detection in stochastic block models,” arXiv:1507.05313, Nov.
2015.
[3] P. J. Bickel and A. Chen, “A nonparametric view of network models and newmangirvan and other modularities,” Proceedings
of the National Academy of Sciences, vol. 106, no. 50, pp. 21 068–21 073, 2009.
[4] T. T. Cai and X. Li, “Robust and computationally feasible community detection in the presence of arbitrary outlier nodes,”
arXiv:1404.6000v4, June 2015.
[5] T. A. B. Snijders and K. Nowicki, “Estimation and prediction for stochastic blockmodels for graphs with latent block
structure,” Journal of Classification, vol. 14, pp. 75–100, 1997.
[6] S. Jafar, “Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of
clusters and submatrices,” ICML, In proceedings of, Feb. 2014.
[7] A. Coja-oghlan, “Graph partitioning via adaptive spectral techniques,” Comb. Probab. Comput., vol. 19, no. 2, pp. 227–284,
Mar. 2010.

August 17, 2017

DRAFT

42

[8] A. Coja-Oghlan, “A spectral heuristic for bisecting random graphs,” in Proceedings of the Sixteenth Annual ACM-SIAM
Symposium on Discrete Algorithms, ser. SODA ’05.

Philadelphia, PA, USA: Society for Industrial and Applied

Mathematics, 2005, pp. 850–859. [Online]. Available: http://dl.acm.org/citation.cfm?id=1070432.1070552
[9] X. L. T. Tony Cai, “A tensor approach to learning mixed membership community models,” arXiv:1302.2684v4, Oct. 2013.
[10] Y. Chen, S. Sanghavi, and H. Xu, “Improved graph clustering,” IEEE Trans. Inf. Theory, vol. 60, no. 10, pp. 6440–6455,
Oct 2014.
[11] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, “Asymptotic analysis of the stochastic block model for modular
networks and its algorithmic applications,” Phys. Rev. E, vol. 84, p. 066106, Dec. 2011.
[12] P. Zhang, K. F., ReichardtJ., and Z. L., “Comparative study for inference of hidden classes in stochastic block models,”
arXiv:1207.2328v2, July 2012.
[13] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proceedings of the National
Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, 2002.
[14] J. Xu, R. Wu, K. Zhu, B. Hajek, R. Srikant, and L. Ying, “Jointly clustering rows and columns of binary matrices:
Algorithms and trade-offs,” arXiv:1310.0512, Feb. 2014.
[15] J. Chen and B. Yuan, “Detecting functional modules in the yeast proteinprotein interaction network,” Bioinformatics,
vol. 22, no. 18, pp. 2283–2290, Sept. 2006.
[16] A. Lancichinetti and S. Fortunato, “Community detection algorithms: A comparative analysis,” Phys. Rev. E, vol. 80, p.
056117, Nov. 2009.
[17] S. Fortunato, “Community detection in graphs,” arXiv:0906.0612v2, Jan. 2010.
[18] E. Abbe, A. Bandeira, and G. Hall, “Community detection in general stochastic block models: fundamental limits and
efficient recovery algorithms,” arXiv:1503.00609, Mar. 2015.
[19] M. Newman and A. Clauset, “Structure and inference in annotated networks,” arXiv:1507.04001v1, 2015.
[20] J. Yang, J. McAuley, and J. Leskovec, “Community detection in networks with node attributes,” in IEEE International
Conference on Data Mining, Dec. 2013, pp. 1151–1156.
[21] Y. Zhang, E. Levina, and J. Zhu, “Community detection in networks with node features,” arXiv:1509.01173v1, 2015.
[22] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, “Inference and phase transitions in the detection
of modules in sparse networks,” Phys. Rev. Lett., vol. 107, p. 065701, Aug 2011. [Online]. Available:
https://link.aps.org/doi/10.1103/PhysRevLett.107.065701
[23] E. Mossel, J. Neeman, and A. Sly, “Reconstruction and estimation in the planted partition model,” Probability Theory and
Related Fields, vol. 162, no. 3, pp. 431–461, 2014.
[24] L. Massoulie, “Community detection thresholds and the weak ramanujan property,” arXiv:1311.3085v1, Nov. 2013.
[25] E. Mossel, J. Neeman, and A. Sly, “A proof of the block model threshold conjecture,” arXiv:1311.4115v4, Aug 2015.
[26] E. Abbe and C. Sandon, “Detection in the stochastic block model with multiple clusters: proof of the achievability
conjectures, acyclic bp, and the information-computation gap,” arXiv:1512.09080v4, Sep 2016.
[27] S. Yun and A. Proutiere, “Community detection via random and adaptive sampling,” arXiv:1402.3072v2, feb 2014.
[28] E. Mossel and J. Xu, “Density evolution in the degree-correlated stochastic block model,” in 29th Annual Conference
on Learning Theory, ser. Proceedings of Machine Learning Research, V. Feldman, A. Rakhlin, and O. Shamir, Eds.,
vol. 49. Columbia University, New York, New York, USA: PMLR, 23–26 Jun 2016, pp. 1319–1356. [Online]. Available:
http://proceedings.mlr.press/v49/mossel16.html

August 17, 2017

DRAFT

43

[29] H. Saad, A. Abotabl, and A. Nosratinia, “Exit analysis for belief propagation in degree-correlated stochastic block models,”
in IEEE International Symposium on Information Theory (ISIT), July 2016, pp. 775–779.
[30] E. Abbe, A. Bandeira, and G. Hall, “Exact recovery in the stochastic block model,” IEEE Trans. Inf. Theory, vol. 62,
no. 1, pp. 471–487, Jan. 2016.
[31] M. Elchanan, J. Neeman, and S. Allan, “Consistency thresholds for the planted bisection model,” arXiv:1407.1591v4, Mar.
2016.
[32] E. Mossel and J. Xu, “Local algorithms for block models with side information,” in ACM Conference on Innovations
in Theoretical Computer Science, ser. ITCS ’16.

New York, NY, USA: ACM, 2016, pp. 71–80. [Online]. Available:

http://doi.acm.org/10.1145/2840728.2840749
[33] T. Tony Cai, T. Liang, and A. Rakhlin, “Inference via message passing on partially labeled stochastic block models,”
arXiv:1603.06923v1, Mar. 2016.
[34] A. Kadavankandy, K. Avrachenkov, L. Cottatellucci, and R. Sundaresan, “The power of side-information in subgraph
detection,” arXiv:1611.04847v3, Mar. 2017.
[35] V. Kanade, E. Mossel, and T. Schramm, “Global and local information in clustering labeled block models,”
arXiv:1404.6325v4, July 2014.
[36] F. Caltagirone, M. Lelarge, and L. Miolane, “Recovering asymmetric communities in the stochastic block model,”
arXiv:1610.03680v2, Mar. 2017.
[37] H. Saad, A. Abotabl, and A. Nosratinia, “Exact recovery in the binary stochastic block model with binary side information,”
in Allerton Conference on Communications, Control, and Computing, Oct 2017.
[38] A. Dembo and O. Zeitouni, Large deviations techniques and applications. Berlin; New York: Springer-Verlag Inc, 2010.

August 17, 2017

DRAFT

