RESEARCH
REPORT
N° 8974
Feb 2017
Project-Team Neo

ISRN INRIA/RR--8974--FR+ENG

Arun Kadavankandy, Konstantin Avrachenkov, Laura Cottatellucci
and Rajesh Sundaresan

ISSN 0249-6399

arXiv:1611.04847v3 [cs.LG] 6 Mar 2017

The Power of
Side-information in
Subgraph Detection

The Power of Side-information in Subgraph
Detection
Arun Kadavankandy, Konstantin Avrachenkov,
Laura Cottatellucci and Rajesh Sundaresan
Project-Team Neo
Research Report n° 8974 — Feb 2017 — 37 pages

Abstract:
In this work, we tackle the problem of hidden community detection. We consider
Belief Propagation (BP) applied to the problem of detecting a hidden Erdős-Rényi (ER) graph
embedded in a larger and sparser ER graph, in the presence of side-information. We derive two
related algorithms based on BP to perform subgraph detection in the presence of two kinds of sideinformation. The ﬁrst variant of side-information consists of a set of nodes, called cues, known
to be from the subgraph. The second variant of side-information consists of a set of nodes that
are cues with a given probability. It was shown in past works that BP without side-information
fails to detect the subgraph correctly when an eﬀective signal-to-noise ratio (SNR) parameter falls
below a threshold. In contrast, in the presence of non-trivial side-information, we show that the
BP algorithm achieves asymptotically zero error for any value of the SNR parameter. We validate
our results through simulations on synthetic datasets as well as on a few real world networks.
Key-words: Belief Propagation, Dense community detection, Cavity Method, Detectability,
Stochastic Block Model

RESEARCH CENTRE
SOPHIA ANTIPOLIS – MÉDITERRANÉE

2004 route des Lucioles - BP 93
06902 Sophia Antipolis Cedex

Le Pouvoir d’Information Supplementaire en Detection des
Sousgraphes
Résumé : Dans ce travail, nous nous attaquons au problème de la detection d’une communauté
cachée dans un grand graphe. Nous considérons Belief Propagation (BP) pour cela, et le modele
que nous utilisons est celui d’un petite graph Erdős-Rényi qui est place dans un plus grande
graphe, aussi Erdős-Rényi. Nous assumons qu’il y a des informations supplémentaires de deux
categories : la premiere où certains sommets qui appartiennent à la communauté concernée sont
connus, qui s’appellent des sommets indices (parfaites informations supplémentaires), et la deuxième où certains sommets sont donnés, mais qu’une partie d’eux ne sont correctes (informations
supplémentaires imparfaites). L’algorithme basé sur Belief propagation que nous présentons peut
fonctionner en presence de ces deux categories d’information supplémentaires, et en l’analysant
nous prouvons que meme une très peu de leur quantité enlève un seuil de « detectabilité » qui
existe dans Belief Propagation sans aucunes informations supplémentaires. Nous fournissons
aussi des résultats d’experiences conduites sur des graphes synthétiques et aussi deux graphes
reels.
Mots-clés : Belief Propagation, Graphes Aléatoires non-oriéntés, Detection de Commaunautes,
Stochastic Block Model, Methode de Cavite, Seuil de Detectabilite

The Power of Side-information in Subgraph Detection

1
1.1

3

Introduction
Problem Motivation

We consider the problem of hidden community detection in graphs in the presence of sideinformation. In various disciplines graphs have been used to model, in a parsimonious fashion,
relationships between heterogenous data. The presence of a dense hidden community in such
graphs is usually indicative of interesting phenomena in the associated real-world network.
An example application of dense subgraph detection in Signal Processing is the problem of
Correlation Mining [1]. Given a network of correlated signals, a graph is formed with nodes
representing signals, and weighted links representing pairwise correlations. The problem of detecting a group of closely correlated signals is then a dense subgraph detection problem on the
constructed graph [1]. Dense subgraph detection also ﬁnds application in real-world computer
and social networks; for e.g., in detecting fraudulent activity [2–4]. It can, in addition, be viewed
as a signal recovery problem on graphs [5, 6].
A majority of subgraph detection algorithms try to ﬁnd a subset of nodes that maximizes
some objective such as the average link density within the subset [7]. A good way to benchmark
the performance of various community detection algorithms is to validate them on generative
graph models with inherent community structure. In this work, we model the hidden community
as a small but well-connected Erdős-Rényi graph embedded within a larger but sparser ErdősRenyi graph. This model was used in [8] to capture terrorist transactions in a computer network.
It is a special case of the Stochastic Block Model (SBM), which has been widely used to assess
the performance of diﬀerent community detection algorithms [9].
The study of subgraph detection on generative models is interesting in itself from an algorithmic perspective. Recent works on hidden community detection and related problems demonstrate
the presence of sharp phase transitions in the range of parameter values between three regimes:
easy (detection achievable with relatively small computational costs), hard (computationally
taxing, but detectable), and impossible to detect [10–12]. We provide more details on these
phenomena while reviewing prior works in the next subsection. The novel aspect of this paper is
a theoretical study of the impact of side-information on this computational barrier. The form of
side-information we consider is the identity of special nodes called cues that are known to belong
to the subgraph, either deterministically or with some level of certainty. One often has access to
such prior knowledge in real-world applications [13–15].
By developing and analyzing the asymptotic performance of a local algorithm based on Belief Propagation (BP), we show that even a small amount of side-information can lead to the
disappearance of the computational barrier. BP is an eﬃcient way to perform approximate ML
detection on certain types of graphs using distributed and local message passing [16]. It belongs to the class of guilt-by-association schemes [17] and has been successfully applied to many
practical problems in graphs such as fraud detection [2] and data mining [18].

1.2

Previous works

Consider a graph with n nodes that contains a hidden community of size K. The edge probability
between any two nodes within the community is p and it is q otherwise, such that p > q. The
parameters p, q and K can in general be functions of n. This model, denoted by G(K, n, p, q),
was already considered in [19–21] in the context of anomaly detection.
A special case of the above model is the hidden clique model with p = 1 and q = 1/2.
The study of clique detection algorithms demonstrate the presence of phase transitions in the
subgraph size K between impossible, hard and easy regimes. If K ≤ 2(1 − ǫ) log2 (n), the
clique is impossible to detect; however, an exhaustive search detects the clique nodes when
RR n° 8974

K. Avrachenkov et al.

4

K ≥ 2(1 + ǫ) log2 (n). √
In contrast, the smallest clique size that can be detected in polynomial
time is believed to be c n [22] for somepc > 0, and the minimum clique-size that can be detected
in nearly-linear time is believed to be n/e [23].
The computational barriers for subgraph detection in a sparse graph without cues were studied
in [10, 11, 24]. In [11] the author investigated the performance of Maximum Likelihood (ML)
detection and BP, and analyzed the phase transition with respect to an eﬀective signal-to-noise
ratio (SNR) parameter λ deﬁned as
λ=

K 2 (p − q)2
.
(n − K)q

(1)

The larger the λ, the easier it is to detect the subgraph. Subgraph recovery was considered
under a parameter setting where K = κn, p = a/n and q = b/n, where κ, a and b are constants
independent of n. It was shown under this setting that, for any λ > 0, an exhaustive search can
detect the subgraph with success probability approaching one as κ → 0. However BP, which has
quasi-linear time complexity, achieves non-trivial success probability only when λ > 1/e in the
same regime. Further, for λ < 1/e, the success probability of the algorithm is bounded away
from one. This demonstrates the existence of a computational barrier for local algorithms.
In [24] the authors show that when K = o(n), i.e., when κ → 0, and p, q are such that
n
a = np = no(1) and p/q = O(1), ML detection succeeds when λ = Ω( K
n log( K )), i.e., detection
is possible even when the SNR parameter goes to zero so long as it does not go to zero too fast.
Under the same parameter setting, it was shown that BP succeeds in detecting the subgraph
with the fraction of misdetected nodes going to zero, only when λ > 1/e [10]. Therefore, λ = 1/e
represents a computational barrier for BP in the subgraph detection problem without sideinformation.
In the present work, we examine the impact of side-information on the above computational
barrier. To the best of our knowlege, ours is the ﬁrst theoretical study of the performance of
local algorithms for subgraph detection in the presence of side-information in G(K, n, p, q). In [25],
the authors compared, but only empirically, several guilt-by-association schemes for subgraph
detection with cues.
There exist many works on the eﬀect of side-information in the context of identifying multiple
communities [12, 26–28]. These works considered a diﬀerent variant of the SBM where nodes are
partitioned into two or more communities, with dense links inside communities and sparse links
across communities. The authors of [27] and [28] consider a BP algorithm to detect two equalsized communities. In [28], the side-information is such that all nodes indicate their community
information after passing it through a binary symmetric channel with error rate α. They show
that when α < 1/2, i.e., when there is non-trivial side-information, there is no computational
barrier and BP works all the way down to the detectability threshold called the Kesten-Stigum
threshold [29]. In [27], a vanishing fraction n−o(1) of nodes reveal their true communities. Again,
there is no computational barrier and BP works all the way down to the detectability threshold.
A fuller picture is available in [12], which considers asymmetric communities and asymmetric
connection probabilities within communities. In this setting, the authors of [12] demonstrate the
presence of all three regimes (easy to detect, hard to detect but possible via exhaustive search,
and impossible to detect) as a function of the size of the smallest community. In contrast, [28]
and [27] consider equal-sized communities with the same edge probability within each community.
In [12, 27, 28], the parameters are chosen such that node degrees alone are not informative.
Our work is diﬀerent from the above settings, in that we deal with a single community, and
the degrees can be informative in revealing node identities, i.e., the average degree of a node
within the subgraph Kp + (n − K)q is greater than nq, the average degree of a node outside
the subgraph. In this setting we show that the computational barrier disappears when sideInria

The Power of Side-information in Subgraph Detection

5

information is available. We emphasize that our results cannot be obtained as a special case of
the results in [12, 26–28].

1.3

Summary of Results

We consider subgraph detection in G(K, n, p, q) with two types of side-information:
1. A fraction α of subgraph nodes are revealed to the detector, which we call reliable cues.
This represents the case of perfect side-information.
2. A similar number of nodes are marked as cues, but they are unreliable, i.e., imperfect
side-information.
These two types of side-information are typical in semi-supervised clustering applications [13–15].
We use BP for subgraph detection to handle these two kinds of side-information. Our computations are local and distributed and require only neighbourhood information for each node in
addition to the graph parameters p, q and K.
We analyze the detection performance of our algorithm when p = a/n, q = b/n with a, b
ﬁxed and K = κn with κ ﬁxed, as in the regime of [11]. Under this setting, we derive recursive
equations for the distributions of BP messages in the limit as the graph size n tends to inﬁnity.
These recursions allow for numerical computation of the error rates for ﬁnite values of a, b and
κ.
Based on these recursions, we obtain closed form expressions for the distributions when
a, b → ∞. We then show that when there is non-trivial side-information, the expected fraction of
misclassiﬁed nodes goes to zero as κ → 0, for any positive value of the respective SNR parameter
λα or λ, for perfect or imperfect side-information, made explicit later. Thus the computational
barrier of λ = 1/e for BP without side-information disappears when there is side-information.
We validate our theoretical ﬁndings by simulations. To demonstrate the practical usefulness
of our algorithm we also apply it to subgraph detection on real-world datasets.
The algorithm for imperfect side-information with its numerical validation on synthetic
datasets was submitted for review to ISIT 2017 [30]. The rest of the material, such as the algorithm for perfect side-information, all the proofs and numerical results on real-world datasets, is
new in this journal version.

1.4

Organization

The rest of the paper is organized as follows. In Subsection 1.5 we delineate useful notation.
In Section 2 we describe the model and deﬁne the problem in detail. In Section 3, we present
our algorithm with perfect cues and explain the steps in its derivation. In Section 4 we derive
the asymptotic distribution of BP messages. In particular, in section 4.1, we prove our main
result on the asymptotic error rate of our algorithm. In Section 5 we present our algorithm with
imperfect side-information and provide a result on its asymptotic error rate. In Section 6 we
present results on our experiments on the synthetic graph as well as a few real-world graphs.
In Section 7, we conclude with some suggestions for future work. Some proofs are relegated to
supplementary material for lack of space.

1.5

Notation and Nomenclature

A graph node is denoted by a lower case letter such as i. The graph distance between two nodes
i and j is the length of the shortest sequence of edges to go from i to j. The neighbourhood of a
node i, denoted by δi is the set of one-hop neighbours of i, i.e., nodes that are at a graph distance
RR n° 8974

K. Avrachenkov et al.

6

of one. Similarly, we also work with t-hop neighbours of i, denoted as Gti , the set of nodes within
a distance of t from i. Note that G1i = δi. We use the following symbols to denote set operations:
C = A\B is the set of elements that belong to A and not B and ∆ denotes the set diﬀerence, i.e.,
A∆B = (A ∪ B)\(A ∩ B). Also |C| denotes the cardinality of the set C. The indicator function
for an event A is denoted by 1(A), i.e., 1(A) = 1 if A is true and 0 otherwise. The symbol ∼
denotes the distribution of a random variable (rv), for example X ∼ Poi(γ) means that X is a
Poisson distributed rv with mean γ. Also, N (µ, σ 2 ) denotes the Gaussian distribution with mean
D
µ and variance σ 2 . The symbol −→ denotes convergence in distribution.

2

Model and Problem Definition

Let G(K, n, p, q) be a random undirected graph with n nodes and a hidden community S such
that |S| = K. Let G = (V, E) be a realization of G(K, n, p, q). An edge between two nodes
appears independently of other edges such that P((i, j) ∈ E|i, j ∈ S) = p and P((i, j) ∈ E|i ∈
S, j 6∈ S) = P((i, j) ∈ E|i, j 6∈ S) = q. We assume that S is chosen uniformly from V among all
sets of size K. Additionally let p = a/n and q = b/n, where a and b are constants independent
of n. Such graphs, with average degree O(1), are called diluted graphs. We use a function
σ : V → {0, 1}n to denote community membership such that σi = 1 if i ∈ S and 0 otherwise.
Next we describe the model for selecting C, the set of cues. To indicate which nodes are cues,
we introduce a function c : V → {0, 1}n such that (s.t.) ci = 1 if i is a cued vertex and ci = 0
otherwise. The model for cues depends on the type of side-information: perfect or imperfect.
The side-information models are as follows:
1. Perfect side-information: In this case the cues are reliable, i.e., they all belong to the
subgraph. To construct C we sample nodes as follows
(
α if x = 1
P(ci = 1|σi = x) =
0 if x = 0,
for some α ∈ (0, 1). Under this model we have
X
nP(ci = 1) =
P(ci = 1|σi = 1)P(σi = 1)
i∈V

= αK.

(2)

2. Imperfect side-information: Under imperfect side-information, the cues are unreliable.
We generate C by sampling nodes from V as follows using a ﬁxed β ∈ (0, 1]. For any i ∈ V :
(
αβ
if x = 1,
(3)
P (ci = 1|σi = x) = αK(1−β)
if x = 0.
(n−K)
Under this model we have for any i ∈ V,
P(ci = 1) = P(σi = 1)P(ci = 1|σi = 1)
+ P(σi = 0)P(ci = 1|σi = 0)
K
(n − K) αK(1 − β)
αβ +
n
n
(n − K)
= αK/n;
=

Inria

The Power of Side-information in Subgraph Detection

7

hence it matches with (2) of the perfect side-information case. It is easy to verify that
under the above sampling
P (σi = 1|ci = 1) = β,
(4)
which provides us with the interpretation of |log(β/(1 − β))| as a reliability parameter for
cue information.
Given G, C our objective is to infer the labels {σi , i ∈ V \C}. The optimal detector that
minimizes the expected number of misclassiﬁed nodes is the per-node MAP detector given as [24]:


P(σi = 0)
σ̂i = 1 Ri > log
,
P(σi = 1)
where
Ri = log



P(G, C|σi = 1)
P(G, C|σi = 0)



is a log-likelihood ratio of the detection problem. Observe that this detector requires the observation of the whole graph. Our objective then is to compute Ri for each i using a local Belief
Propagation (BP) algorithm and identify some parameter ranges for which it is useful. Specifically, we want to show that a certain barrier that exists for BP when α = 0 disappears when
αβ > 0.

3

Belief Propagation Algorithm for Detection with Perfect
Side-information

In this section we present the BP algorithm, Algorithm 1, which performs detection in the
presence of perfect side-information. We provide here a brief overview of the algorithm. At step
t of Algorithm 1, each node u ∈ V \C updates its own log-likelihood ratio based on its t-hop
neighbourhood:


P(Gtu , Cut |σu = 1)
t
Ru := log
,
(5)
P(Gtu , Cut |σu = 0)

where Gtu is the set of t-hop neighbours of u and Cut is the set of cues in Gtu , i.e., Cut = Gtu ∩ C.
The beliefs are updated according to (8). The messages transmitted to u by the nodes i ∈ δu,
the immediate neighbourhood of u, are given by


P(Gti \u, Cit \u|σi = 1)
t
,
(6)
Ri→u := log
P(Gti \u, Cit \u|σi = 0)

where Gti \u and Cit \u are deﬁned as above, but excluding the contribution from node u. Node
t
i updates Ri→u
by acquiring messages from its neighbours, except u, and aggregating them
according to (7). If node u is isolated, i.e., δu = ∅, there are no updates for this node. It can be
checked that the total computation time for tf steps of BP is O(tf |E|).
The detailed derivation of the algorithm can be found in Appendix A. The derivation consists
of two steps. First we establish a coupling between Gtu , the t-hop neighbourhood of a node u
of the graph and a specially constructed Galton-Watson (G-W) tree1 Tut of depth t rooted on
t
u. This coupling ensures that for a carefully chosen t = tf the neighbourhood Guf of the node
is a tree with probability tending to one as n → ∞ (i.e., with high probability (w.h.p)). The
1 Detailed

RR n° 8974

in Appendix A

K. Avrachenkov et al.

8

Algorithm 1 BP with perfect side-information
1:
2:

log(n)
0
+ 1. Set t = 0.
Initialize: Set Ri→j
to 0, for all (i, j) ∈ E with i, j 6∈ C. Let tf < log(np)
For all directed pairs (i, u) ∈ E, such that i, u ∈
/ C:
 


t
X
X
p
exp(Rl→i
− υ)(p/q) + 1
t+1
Ri →u = −K(p−q)+
log
+
, (7)
log
t
q
exp(Rl→i
− υ) + 1
1
1
l∈Ci ,l6=u

3:
4:

n−K
).
where υ = log( K(1−α)
Increment t, if t < tf − 1 go back to 2, else go to 4
t
Compute Ruf for every u ∈ V \C as follows:

 

t
X
X
exp(Rl→u
− υ)(p/q) + 1
p
log
log
+
Rut+1 = −K(p − q) +
t
q
exp(Rl→u
− υ) + 1
1
1
l∈Cu

5:

l∈δi\Ci ,l6=u

(8)

l∈δu\Cu

The output set is the union of C and the K − |C| set of nodes in V \C with the largest values
t
of Ruf .

second step of the derivation involves deriving the recursions (7) and (8) to compute (6) and (5)
respectively, using the tree coupling.
The output of the algorithm is C along with the set of K − |C| nodes with the largest value
t
of log-likelihoods Ri f . In the following section we derive the asymptotic distributions of the
BP messages as the graph size tends to inﬁnity, so as to quantify the error performance of the
algorithm.

4

Asymptotic Error Analysis

t
In this section we analyze the distributions of BP messages Ri→u
given {σi = 1} and given {σi =
0} for i ∈ V \C. First, we derive a pair of recursive equations for the asymptotic distributions
t
of the messages Ri→u
given {σi = 0, ci = 0} and given {σi = 1, ci = 0} in the limit as n → ∞
in Lemma 1. In Proposition 1 we present the asymptotic distributions of the messages in the
large degree regime where a, b → ∞. This result will enable us to derive the error rates for
detecting the subgraph in the large degree regime (Theorem 1). Finally, we contrast this result
with Proposition 2 from [11], which details the limitation of local algorithms.
t
directly, we look at the log-likelihood ratios of the posterior probInstead of studying Ri→u
abilities of σi given as


t
t
eit = log P(σi = 1|Gi , Ci , ci = 0)
R
P(σi = 0|Gti , Cit , ci = 0)
t
et . By Bayes rule, R
et
and the associated messages R
i→u
i→u = Ri→u − υ, where




P(σi = 0|ci = 0)
n−K
υ = log
= log
.
P(σi = 1|ci = 0)
K(1 − α)

et
Let ξ0t , ξ1t be rvs with the same distribution as the messages R
i→u given {σi = 0, ci = 0} and
given {σi = 1, ci = 0}, respectively in the limit as n → ∞. Based on the tree coupling in Lemma
3 of Appendix A, it can be shown that these rvs satisfy the recursive distributional evolutionary
equations given in the following lemma.
Inria

The Power of Side-information in Subgraph Detection

9

Lemma 1. The random variables ξ0t and ξ1t satisfy the following recursive distributional equations
with initial conditions ξ00 = ξ10 = log (κ(1 − α)/(1 − κ)) .
(t+1) D

ξ0

=h+

L0c
X

log(ρ) +

(t+1) D

=h+

L1c
X
i=1

D

(t)

f (ξ0,i ) +

log(ρ) +

L10
X
i=1

L01
X

(t)

(9)

(t)

(10)

f (ξ1,i )

i=1

i=1

i=1

ξ1

L00
X

(t)

f (ξ0,i ) +

L11
X

f (ξ1,i ),

i=1

where = denotes equality in distribution, h = −κ(a − b) − υ, ρ := p/q = a/b, and the function f
is defined as


exp(x)ρ + 1
f (x) := log
.
(11)
exp(x) + 1

t
The rvs ξ0,i
, i = 1, 2, . . . are independent and identically distributed (iid) with the same distribut
t
tion as ξ0 . Similarly ξ1,i
, i = 1, 2, . . . are iid with the same distribution as ξ1t . Furthermore, L00 ∼
Poi((1 − κ)b), L01 ∼ Poi(κb(1 − α)), L10 ∼ Poi((1 − κ)b), L11 ∼ Poi(κa(1 − α)), L0c ∼ Poi(κbα)
and L1c ∼ Poi(κpα).

Proof. This follows from (7) and the tree coupling in Lemma 3 of Appendix A.

We deﬁne the eﬀective SNR for the detection problem in the presence of perfect sideinformation as:
K 2 (p − q)2 (1 − α)2
κ2 (a − b)2 (1 − α)2
λα =
=
,
(12)
(n − K)q
(1 − κ)b

where the factor (1 − α)2 arises from the fact that we are now trying to detect a smaller subgraph
of size K(1 − α).
We now present one of our main results, on the distribution of BP messages in the limit of
large degrees as a, b → ∞ such that λα is kept ﬁxed.
Proposition 1. In the regime where λα and κ are held fixed and a, b → ∞, we have


1−κ
1
D
ξ0t+1 −→ N − log
− µ(t+1) , µ(t+1)
κ(1 − α) 2


1−κ
1
D
ξ1t+1 −→ N − log
+ µ(t+1) , µ(t+1) .
κ(1 − α) 2

The variance µ(t) satisfies the following recursion with initial condition µ(0) = 0 :
µ

(t+1)

1−κ
+ λα E
= λα α
(1 − α)2 κ

(1 − κ)

κ(1 − α) + (1 − κ) exp(−µ(t) /2 −

where the expectation is taken w.r.t. Z ∼ N (0, 1).

p
µ(t) Z)

!

,

(13 )

Before providing a short sketch of the proof of the above proposition, we state a Lemma
from [10], which we need for our derivations.

Lemma 2. [10, Lemma 11] Let Sγ = X1 + X2 + . . . + XNγ , where Xi , for i = 1, 2, . . . Nγ , are
independent, identically distributed rv with mean µ, variance σ 2 and E(|Xi3 |) ≤ g 3 , and for some
γ > 0, Nγ is a Poi(γ) rv independent of Xi : i = 1, 2, . . . , Nγ . Then
!
CBE g 3
Sγ − γµ
supx P p
− Φ(x) ≤ p
,
γ(µ2 + σ 2 )
γ(µ2 + σ 2 )3
where CBE = 0.3041.
RR n° 8974

K. Avrachenkov et al.

10

We now provide a sketch of the proof of Proposition 1; the details can be found in Appendix B.

Sketch of Proof of Proposition 1. The proof proceeds primarily by applying the expectation and
variance operators to both sides of (9) and (10) and applying various reductions. First notice
that when a, b → ∞ and λ and κ are held constant, we have ρ → 1 as follows:
s
λα (1 − κ)
ρ = a/b = 1 +
.
(14)
(1 − α)2 κ2 b
Then using Taylor’s expansion of log(1 + x) we can expand the function f (x) in (11) up to second
order as follows:
f (x) = (ρ − 1)

1
ex 2
ex
− (ρ − 1)2 (
) + O(b−3/2 ).
x
1+e
2
1 + ex

(15)

We use these expansions to simplify the expressions for the means and variances of (9) and (10).
Then, by a change of measure, we express them in terms of functionals of a single rv, ξ1t . We
then use induction to show that the variance µ(t+1) satisﬁes the recursion (13) and use Lemma
2 to prove Gaussianity.
In the following subsection, we use Proposition 1 to derive the asymptotic error rates of the
detector in Algorithm 1.

4.1

Detection Performance

Let us use the symbol S to denote the subgraph nodes with the cued nodes removed, i.e.,
S = S\C. This is the set that we aim to detect. The output of Algorithm 1, Sb is the set of nodes
with the top K − |C| beliefs. We are interested in bounding the expected number of misclassiﬁed
b Let Sb be the output set of the algorithm excluding cues since the cues are
nodes E(|S∆S|).
b K − |C|. To characterize the performance of the
always correctly detected. Note that |S|= |S|=
detector, we need to choose a performance measure. In [11], a rescaled probability of success was
used to study the performance of a subgraph detector without cues, deﬁned as
b ∈ S) + P(i 6∈ S|i
b 6∈ S) − 1,
Psucc (b
σ ) = P(i ∈ S|i

(16)

b and the dependence of Psucc (b
where σ
bi = 1(i ∈ S),
σ ) on n is implicit. In our work, we study
the following error measure, which is the average fraction of misclassiﬁed nodes, also considered
in [10], which for the uncued case is deﬁned as
E :=

b
E(|S∆S|)
.
K

Observe that 0 ≤ E ≤ 2. In particular E = 2 if the algorithm misclassiﬁes all the subgraph nodes.
We now show that these two measures are roughly equivalent. For simplicity we consider the
case where there are no cues, but the extension to the cued case is straightforward. Since our
b K, the following is true for any
algorithm always outputs K nodes as the subgraph, i.e., |S|=
estimate σ
b of σ :
n
n
X
X
1(b
σi = 1, i 6∈ S),
(17)
1(b
σi = 0, i ∈ S) =
rn :=
i=1

i=1

Inria

The Power of Side-information in Subgraph Detection

11

i.e., the number of misclassiﬁed subgraph nodes is equal to the number of misclassiﬁed nodes
outside the subgraph. We can rewrite the error measure E in terms of rn , since
b
|S∆S|
2rn
=
.
K
K

(18)

Next notice that we can rewrite Psucc (b
σ ) as follows.
n

1X
(P(b
σi = 0|i ∈ S) + P(b
σi = 1|i 6∈ S))
Psucc (b
σ) = 1 −
n i=1

n 
X
P(b
σi = 0, i ∈ S) P(b
σi = 1, i 6∈ S)
(a)
=1−
+
K
n−K
i=1


nE(rn )
E(rn )
E(rn )
(b)
=1−
+
,
=1−
K
n−K
K(n − K)
where in step (a) we used Bayes rule with P(i ∈ S) =

K
n.

Since 1 ≤

n
n−K

1 − 2E(rn )/K ≤ Psucc (b
σ ) ≤ 1 − E(rn )/(K).

(19)

≤ 2, we get
(20)

b

S|)
→ 0.
Hence from (18) and (20), Psucc (b
σ ) → 1 if and only if E(|S∆
K
In the following proposition, we state and prove the main result concerning the asymptotic
error performance of Algorithm 1.

Theorem 1. For any λα > 0, α > 0,
b
E(|S∆S|)
lim lim
≤2
b→∞ n→∞ K(1 − α)

s

α (1−κ)
1 − κ − 18 αλ
κ(1−α)2 .
e
κ(1 − α)

(21)

Consequently,
b
E(|S∆S|)
= 0.
κ→0 b→∞ n→∞ K(1 − α)
lim lim lim

Proof. Let Sb0 be the MAP estimator given by

b
S0 = i : Rit > log

1−κ
κ(1 − α)



.

b
Since Sb is the set of nodes with the top K − |C| beliefs, we have either Sb ⊂ Sb0 or Sb0 ⊂ S.
Therefore,
b ≤ |S∆Sb0 |+|S∆
b Sb0 |
|S∆S|
= |S∆Sb0 |+|K − |C|−|Sb0 ||
= |S∆Sb0 |+||S|−|Sb0 ||
≤ 2|S∆Sb0 |,

(22)

where the last step follows because the set diﬀerence between two sets is lower bounded by the
b0 |)
S
diﬀerence of their sizes. If we can bound E(|S∆
K(1−α) by one-half the expression in (21) the result
of the Proposition follows. The proof of this upper bound uses Proposition 1 and is given in
Appendix C.
RR n° 8974

K. Avrachenkov et al.

12

Theorem 1 states that the detectability threshold does not exist for Belief Propagation with
cues.
This is in stark contrast to the performance of BP when there is no side-information. In that
case, as stated in the following theorem from [11], the performance of any local algorithm suﬀers
when the SNR parameter λ < 1/e. In the following LOC denotes the class of all local algorithms,
i.e., algorithms that take as input the local neighbourhood of a node.
Proposition 2. [11, Theorem 1] If λ < 1/e, then all local algorithms have success probability
uniformly bounded away from one; in particular,
sup

lim Psucc (T ) ≤

T ∈LOC n→∞

and therefore
sup

lim E(T ) ≥

T ∈LOC n→∞

5

e−1
,
4

5−e
> 1/2.
4

Imperfect Side Information

In this section, we develop a BP algorithm under the more realistic assumption of imperfect
side information, where the available cue information is not completely reliable. This is true of
humanly classﬁed data available for many semi-supervised learning problems.
Our BP algorithm can easily take into account imperfection in side information. Suppose
we know the parameters α and β deﬁned in (2) and (4) respectively, or their estimates thereof.
We remark that unlike Algorithm 1, which only has to detect the uncued subgraph nodes, our
algorithm needs to explore the whole graph, since we do not know a priori which cues are correct.
As before, for a node u, we wish to compute the following log-likelihood ratio in a distributed
manner:


P(Gtu , cu , Cut |σu = 1)
,
Rut = log
P(Gtu , cu , Cut |σu = 0)

where cu is the indicator variable of whether u is a cued node, and Cut is the cued information
of the t-hop neighbourhood of u, excluding u. Note that we can expand Rut as follows




P(Gtu , Cut |σu = 1, cu )
P(cu |σu = 1)
t
Ru = log
+ log
P(Gtu , Cut |σu = 0, cu )
P(cu |σu = 0)




t
t
P(cu |σu = 1)
P(Gu , Cu |σu = 1)
+ log
,
(23)
= log
P(Gtu , Cut |σu = 0)
P(cu |σu = 0)
where in the second step we dropped the conditioning w.r.t.
cu because
(Gtu , Cut ) is independent


P(cu |σu =1)
of the cue information of node u given σu . Let hu = log P(cu |σu =0) . Then it is easy to see from
(3) that
 

log β(1−κ) ,
if u ∈ C,

 (1−β)κ
hu =
(24)
(1−αβ)(1−κ)
log
,
otherwise.
(1−κ−ακ+ακβ)

The recursion for the ﬁrst term in (23) can be derived along the same lines as the derivation of
Algorithm 1 and is skipped. The ﬁnal BP recursions are given in Algorithm 2.
In order to analyze the error performance of this algorithm we derive the asymptotic distrit
butions of the messages Ru→i
, for {σu = 0} and {σu = 1}. Note that, since we now assume
Inria

The Power of Side-information in Subgraph Detection

13

Algorithm 2 BP with imperfect cues
1:
2:

log(n)
0
+ 1. Set t = 0.
Initialize: Set Ri→j
to 0, for all (i, j) ∈ E. Let tf < log(np)
For all directed pairs (i, u) ∈ E:


t
X
exp(Rl→i
− ν)(p/q) + 1
t+1
Ri →u = −K(p − q) + hi +
log
,
t
exp(Rl→i
− ν) + 1

(25)

l∈δi,l6=u

3:
4:

where ν = log( n−K
K ).
Increment t; if t < tf − 1 go back to 2, else go to 4
t
Compute Ruf for every u ∈ V as follows:


t
X
exp(Rl→u
− ν)(p/q) + 1
Rut+1 = −K(p − q) + hu +
log
t
exp(Rl→u
− ν) + 1

(26)

l∈δu

5:

t
Output Sb as K set of nodes in V with the largest values of Ruf .

that we do not know the exact classiﬁcation of any of the subgraph nodes, we need to detect K
nodes, and hence the eﬀective SNR parameter is deﬁned as
λ=

K 2 (p − q)2
.
(n − K)q

(27)

t
The following proposition presents the asymptotic distribution of the messages Ru→i
in the limit
of n → ∞ and in the large degree regime where a, b → ∞.

Proposition 3. Let n → ∞. In the regime where λ and κ are held fixed and a, b → ∞, the
t
message Ru→i
given {σu = j}, where j = {0, 1} converges in distribution to Γtj + hu where hu is
defined in (24). The rvs Γtj have the following distribution:
Γt0 ∼ N (−µ(t) /2, µ(t) ), and

Γt1 ∼ N (µ(t) /2, µ(t) ),

where µ(t) satisfies the following recursion with µ(0) = 0,
µ

(t+1)

2

= αβ λE
E

(1 − κ)/κ

(t) /2−

β + (1 − β)e(−µ

√

µ(t) Z)

(1 − κ)

!

+ (1 − αβ)2 λ

(t) /2−

κ(1 − αβ) + (1 − κ − ακ + ακβ)e(−µ

√

µ(t) Z)

!

(28 )

,

and the expectation is with respect to (w.r.t.) Z ∼ N (0, 1).
Proof. The proof proceeds by deriving the recursive distributional equations that the message
distributions satisfy in the limit n → ∞, and then applying the large degree limit of a, b → ∞
to these recursions.The details are in the supplementary material.
The above proposition immediately leads to the following result on the asymptotic error rate of
Algorithm 2.
RR n° 8974

K. Avrachenkov et al.

14

Theorem 2. For any λ > 0, α > 0, β > 0,
E(|Ŝ∆S|)
lim lim
b→∞ n→∞
K

p
≤ 2 α β(1 − β) +
r

λαβ 2 (1−κ)
1−κ
8κ
(1 − αβ)(
.
− α(1 − β)) e−
κ
Consequently,
b
E(|S∆S|)
= 0.
κ→0 b→∞ n→∞
K
lim lim lim

Proof. The proof essentially analyzes the properties of the recursion (28) and is similar to the
proof of Theorem 1. See supplementary material for details.

6

Numerical Experiments

In this section we provide numerical results to validate our theoretical ﬁndings on the synthetic
model as well as on two real-world datasets. We compare the performance of BP to another
seed-based community detection algorithm, the personalized PageRank, which is widely used for
local community detection [31].

6.1

Synthetic dataset

First we show that the limitation of local algorithms described in Proposition 2 is overcome by BP
when there is non-trivial side-information. Proposition 2 says that when λ < 1/e, E(T ) > 1/2
for any local algorithm T. We run our Algorithm 1, on a graph generated with α = 0.1, κ =
5 × 10−4 , b = 100 and n = 106 . For λ = 1/4 < 1/e, we get an average value of E = 0.228 < 1/2.
Thus it is clear that our algorithm overcomes the computational threshold of λ = 1/e.
Next, we study the performance of Algorithm 2 when there is noisy side-information with
β = 0.8. For λ = 1/3 < 1/e, we get an average error rate of 0.3916 < 1/2 clearly beating
the threshold of λ = 1/e. Thus we have demonstrated that both with perfect and imperfect
side-information, our algorithm overcomes the λ = 1/e barrier of local algorithms.
Next, we verify that increasing α improves the performance of our algorithm as expected. In
Figure 1, we plot the variation of E of Algorithm 1 as a function of α. Our parameter setting
is κ = 0.01, b = 100, and λ = 1/2 with n = 104 . In the ﬁgure, we also plot the error rate E
obtained by personalized PageRank under the same setting, with damping factor αpr = 0.9 [31].
The ﬁgure demonstrates that BP beneﬁts more as the amount of side-information is increased
than PageRank does.
Next, we compare the performance of BP algorithm without side-information given in [11]
to our algorithm with varying amounts of side-information. We choose the setting where n =
104 , b = 140 and κ = 0.033 for diﬀerent values of λ by varying p. In Figure 2 we plot the metric E
against λ for diﬀerent values of β, with α = 0.1. For β = 1 we use Algorithm 1. We can see that
even BP with noisy side-information performs better than standard BP with no side-information.
In addition, as expected increasing β improves the error performance.
Inria

The Power of Side-information in Subgraph Detection

15

Variation of error with respect to α
2

BP
Pagerank

1.8

1.6

1.4

E

1.2

1

0.8

0.6

0.4

0.2

0
0

0.05

0.1

0.15

0.2

0.25

0.3

α

Figure 1: Performance of BP Algo 1 as a function of α

Impact of Side-information on BP error performance
2

1.9

1.8

1.7

E

1.6

1.5

1.4

1.3

1.2

1.1
0.15

Random guessing
BP with no cues
α = 0.1, β = 0.3
α = 0.1, β = 0.5
α = 0.1, β = 0.7
α = 0.1, β = 0.9
α = 0.1, β = 1
0.2

0.25

0.3

0.35

0.4

0.45

0.5

0.55

0.6

λ

Figure 2: Comparison of BP for subgraph detection for diﬀerent amounts of side-information

RR n° 8974

K. Avrachenkov et al.

16

Class 0
BP
PageRank

#of cues = 1
0.7143
0.6327

#of cues = 2
0.7216
0.6392
Table 1: Reuters911 recall results

6.2

Real-world datasets

We consider two real-world networks: The USPS dataset and the Reuters-911 dataset. For these
two datasets we compare the performance of BP with personalized PageRank in terms of recall
rate R deﬁned as
|S ∩ Ŝ|
R=
,
|S|
where S is the true community and Ŝ is its estimate. This is a commonly used metric for
community detection applications [32]. We use αpr = 0.9 as the damping factor of PageRank.
We describe the datasets and the results obtained by our algorithms below.
6.2.1

USPS dataset

The USPS dataset contains 9296 scanned images of size 16 × 16, which can represented by a
feature vector of size 256 × 1 with values from -1 to +1 [33]. First, we construct a graph from
this dataset, where nodes represent scanned images, by adding a link between a node and its
three nearest neighbours, where the distance is deﬁned as the euclidean distance between the
images represented as feature vectors. The resulting graph is undirected with a minimum degree
of at least 3. This is an instance of the k nearest neighbour graph, with k = 3. On this graph
we run BP and PageRank separately for each of the 10 communities for α = 0.01 and α = 0.05
(Figure 3). It can be seen from Figure 3, that the performance of BP is strictly worse than that
of PageRank. This result points to the importance of having the correct initialization for the BP
parameters. Indeed, in our underlying model for BP, we assumed that there is only one dense
community in a sparse network, in which case, as demonstrated in Figure1, BP outperforms
PageRank by a big margin. However in the USPS graph, there are ten dense communities, and
therefore it deviates signiﬁcantly from our underlying model.
6.2.2

Reuters911 Dataset

In this subsection we consider a graph that is closer to our assumed model. We consider the
Reuters911 dataset also used in [34]. It is made up of words from all news released by Reuters
for 66 days since September 11, 2001. Table 5 in [34] shows a group of 99 collocated words in
this dataset. This subset represents the largest dense community to be detected in this dataset.
A graph of size n = 13332 is generated from this dataset by adding a link between two words
if they appear together in a sentence. The resulting graph is undirected and unweighted. We
compare BP and Pagerank on this dataset for one and two cues. The cues we use are the words
pentagon and 11. In Table 1 we show the recall values R of PageRank and BP, excluding cues.
Clearly, BP performs better.

7

Conclusions and Future Extensions

In this work we developed a local distributed BP algorithm that takes advantage of sideinformation to detect a dense subgraph embedded in a sparse graph. We obtained theoretical
Inria

The Power of Side-information in Subgraph Detection

17

BP vs PageRank for USPS dataset
1

0.9

R (Minus Cues)

0.8

0.7

BP with α = 0.01
BP with α = 0.05
PageRank with α = 0.01
PageRank with α = 0.05

0.6

0.5

0.4

0.3
1

2

3

4

5

6

7

8

9

10

Community index

Figure 3: Comparison of BP for subgraph detection for diﬀerent amounts of side-information
results based on density evolution on trees to show that it achieves zero asymptotic error regardless of the SNR parameter λ, unlike BP without cues, where there is a non-zero detectability
threshold. We then validated our theoretical results by simulating our algorithm on a synthetic
dataset and showing that, in the presence of both noise-less and noisy side-information, our BP
algorithm overcomes the error bound of local algorithms when λ < 1/e. We then applied our
algorithm to two real-world datasets: USPS and Reuters911 and compared its performance with
personalized PageRank. Our results indicate that the relative improvement in BP depends on
the closeness of the dataset to the underlying graph model used to derive BP. In the future, we
would like to do non-asymptotic analysis when a, b and κ are functions of n. Extension to dense
graphs would also be interesting, where traditional BP and tree coupling-based analysis will not
work owing to the presence of loops.

Acknowledgements
This work was partly funded by the French Government (National Research Agency, ANR)
through the “Investments for the Future” Program reference #ANR-11-LABX-0031-01 and IndoFrench CEFIPRA Collaboration Grant No.5100-IT1 “Monte Carlo and Learning Schemes for
Network Analytics.”

A

Description of G-W tree and derivation of Algorithm 1

We derive Algorithm 1 by establishing a coupling formulation between a t-hop neighbourhood
Gtu of node u and a Galton-Watson (G-W) tree rooted at u constructed as follows. Let Tut be
RR n° 8974

K. Avrachenkov et al.

18

a labelled Galton-Watson (G-W) tree of depth t rooted at node u constructed as follows (as
in [10]): The label τu at node u is chosen at random in the following way:
P(τu = 1) =

K
,
n

P(τu = 0) =

n−K
.
n

The number of children Nu of the root u is Poisson-distributed with mean d1 = Kp + (n − K)q if
τu = 1 and mean d0 = nq if τu = 0. Each child is also assigned a label. The number of children
i with label τi = 1 is Poisson distributed with mean Kp if τu = 1 and mean Kq if τi = 0.
The number of children with label τi = 0 is Poisson distributed with mean (n − K)q for both
τu = 0 and τu = 1. By the independent splitting property of Poisson random variables, this is
equivalent to assigning the label τi = 1 to each child i by sampling a Bernoulli random variable
with probability (w.p.) Kp/d1 if τu = 1 and Kq/d0 if τu = 0. Similarly τi = 0 w.p. (n − K)q/d1
and (n − K)q/d0 for τu = 0 and 1 respectively. Namely, if i is a child of u,
P(τi = 1|τu = 1) =

Kp
,
d1

P(τi = 1|τu = 0) =

Kq
.
d0

(29)

We then assign the cue indicator function e
c such that e
ci = 1 w.p. α if τi = 1 and e
ci = 0 if
e t , the set of cued neighbours. Now we
τi = 0. The process is repeated up to depth t giving us C
u
have the following coupling result between (Gtu , σ t , Cut ), the neighbourhood of u and the node
eut ), the depth-t tree Tut and its labels due to [10].
labels of that neighbourhood and (Tut , τ t , C

Lemma 3. [10, Lemma 15] For t such that (np)t = no(1) , there exists a coupling such that
eut ) with probability 1 − n−1+o(1) .
(Gtu , σ t , Cut ) = (Tut , τ t , C

We now derive the recursions for the likelihood ratios on the tree Tut . For large n with high
probability, by the coupling formulation, Rut also satisfy the same recursions. For notational
simplicity, from here onwards we represent the cue labels on the tree by c and the set of cued
neighbours by Cut , just as for the original graph. We use Λtu to denote the likelihood ratio of
node u computed on a tree deﬁned as below:
Λt+1
= log
u



P(Tut+1 , Cut+1 |τu = 1)
P(Tut+1 , Cut+1 |τu = 0)



.

By virtue of tree construction, if the node u has Nu children, the Nu subtrees rooted on these
children are jointly independent given τu . We use this fact to split Λt+1
in two parts.
u

Λt+1
u




P(Tut+1 , Cut+1 |τu = 1)
= log
P(Tut+1 , Cut+1 |τu = 0)


P(Nu |τu = 1)
+
= log
P(Nu |τu = 0)


X
P(Tit , ci , Cit |τu = 1)
log
,
P(Tit , ci , Cit |τu = 0)

(30)
(31)

i∈δu

by the independence property of subtress Tit rooted on i ∈ δu. Since by Lemma 3, the degrees
are Poisson,
u −d1
P(Nu |τu = 1) = dN
/Nu ! ,
1 e
Inria

The Power of Side-information in Subgraph Detection

19

and similarly for P(Nu |τu = 0). Therefore we have
log



P(Nu |τu = 1)
P(Nu |τu = 0)






d1
= Nu log
− (d1 − d0 )
d0
 
d1
= Nu log
− K(p − q).
d0

(32)

Next we look at the second term in (31). We analyze separately the case of ci = 1 and ci = 0
for i ∈ δu , i.e, the cued and uncued children are handled separately.
Case 1 ( ci = 1): We have


P(Tit , ci , Cit |τu = 1)
P(Tit , ci , Cit |τu = 0)


P(Tit , ci , Cit , τi = 1|τu = 1)
(a)
= log
P(Tit , ci , Cit , τi = 1|τu = 0)


P(Tit , ci , Cit |τi = 1)P(τi = 1|τu = 1)
= log
P(Tit , ci , Cit |τi = 1)P(τi = 1|τu = 0)


Kp/d1
(b)
,
= log
Kq/d0

log



(33)

where in step (a) we applied the fact that ci = 1 implies τi = 1, and in (b) we used (29).
Case 2 (ci = 0): Observe that P(ci = 0|τi = 1) = 1 − α and P(ci = 0|τi = 0) = 1. Note that
P(Tit , ci , Cit |τu = 1)
= P(Tit , Cit |τi = 1)P(ci |τi = 1)P(τi = 1|τu = 1)

P(Tit , Cit |τi = 0)P(ci |τi = 0)P(τi = 0|τu = 1)
Kp
= P(Tit , Cit |τi = 1)(1 − α)
d1
(n
−
K)q
+ P(Tit , Cit |τi = 0)
.
d1
+

(34)

Similarly, we can show
Kq
(1 − α)
d0
(n − K)q
P(Tit , Cit |τi = 0)
.
d0

P(Tit , ci , Cit |τu = 0) = P(Tit , Cit |τi = 1)
+
Let us deﬁne
Λti→u := log
RR n° 8974



P(Tit , Cit |τi = 1)
P(Tit , Cit |τi = 0)



,

(35)

K. Avrachenkov et al.

20

the message that i sends to u at step t. Using the above deﬁnition, (34), and (35) we get

log



=

=

P(Tit , ci , Cit |τu = 1)
P(Tit , ci , Cit |τu = 0)
t

log



eΛi→u Kq
d0 (1
 
d0
log
+ log
d1
t

!

(n−K)q
d1
− α) + (n−K)q
d0
!
Kp
Λti→u
e
(n−K)q (1 − α) + 1
.
t
K
(1 − α) + 1
eΛi→u (n−K)

eΛi→u Kp
d1 (1 − α) +

(36)

We then use the substitution ν := log((n−K)/K) in the above equation. Finally combining (32),
t
(33) and (36) and replacing Λtu with Rut and Λti→u with Ri→u
, we arrive at (8). The recursive
equation (7) can be derived in exactly the same way by looking at the children of i ∈ δu.

B

Proof of Proposition 1

Since the statistical properties of Rut and Λtu are the same in the n → ∞ limit, we analyze the
distribution of Λtu . Let us deﬁne the posterior likelihood for τu given by
e ti = log
Λ



P(τi = 1|Tit , Cit , ci = 0)
P(τi = 0|Tit , Cit , ci = 0)



.

Note that P(τi = 1|ci = 0) = κ(1 − α)/(1 − κα) and P(τi = 0|ci = 0) = (1 − κ)/(1 − κα) are the
prior probabilities of the uncued vertices. For convenience we use an overline for the symbols of
expectation E and probability P to denote conditioning w.r.t {ci = 0}.

By a slight abuse of notation, let ξ0t and ξ1t denote the rvs whose distributions are the same as
e t given {ci = 0, τi = 0} and {ci = 0, τi = 1} respectively in the limit n → ∞.
the distributions of Λ
i
We need a relationship between P0 and P1 , the probability measures of ξ0t and ξ1t respectively,
stated in the following lemma.
Lemma 4.
κ(1 − α)
dP0
(ξ) =
exp(−ξ).
dP1
1−κ
In other words for any integrable function g(·)
e t )|τu = 0] =
E[g(Λ
u

κ(1 − α)
e t )e−Λe tu |τu = 1].
E[g(Λ
u
1−κ

e tu ) = 1(Λ
e u ∈ A), A being some
Proof. Following the logic in [11], we show this result for g(Λ
measurable set. The result for general g then follows because any integrable function can be
Inria

The Power of Side-information in Subgraph Detection

21

obtained as the limit of a sequence of such rvs [35]. Let Y = (Tut , Cut ), the observed rv. Therefore
 


e tu ∈ A |τu = 0
E 1 Λ


e t ∈ A|τu = 0
= P Λ
u
=

=

e tu ∈ A, τu = 0)
P(Λ
P(τu = 0)


e tu ∈ A, τu = 0|Y )
EY P(Λ

= EY

"

P(τu = 0)

e tu ∈ A)P(τu = 0|Y )
1(Λ
P(τu = 0)
et

e t ∈ A)e−Λu P(τu = 1|Y )
1(Λ
u
P(τu = 0)

(a)

= EY
=
=

where in (a) we used the fact that
on the event {τu = 1}.

#

!

P(τu = 1)
e t ∈ A)e−Λe tu )
E1 (1(Λ
u
P(τu = 0)
κ(1 − α)
e t ∈ A)e−Λe tu ),
E1 (1(Λ
u
1−κ
P(τu =0|Y )
P(τu =1|Y )

e tu ), and E1 denotes expectation conditioned
= exp(−Λ

Proof. Since λα and κ are ﬁxed and b → ∞, from (12) we have
ρ := a/b = 1 +

s

λα (1 − κ)
= 1 + O(b−1/2 ).
(1 − α)2 κ2 b

(37)

Following [11], we prove the result by induction on t. First let us verify the result holds when
t = 0, for the initial condition that ξ00 = ξ10 = −υ. We only do this for ξ0t since the steps are
similar for ξ1t . Observe that


f (−υ) = log 



κ(1−α)ρ
(1−κ) + 1 
κ(1−α)
(1−κ) + 1



κ(1 − α)
= log 1 + (ρ − 1)
1 − κα
κ(1 − α) (ρ − 1)2 κ2 (1 − α)2
(a)
= (ρ − 1)
−
1 − κα
2
(1 − κα)2
+ O(b−3/2 ),

(38)

where (a) follows from (37), and Taylor’s expansion around ρ = 1. Similarly,
f 2 (−υ) = (ρ − 1)2
RR n° 8974

κ2 (1 − α)2
+ O(b−3/2 ),
(1 − κα)2

(39)

K. Avrachenkov et al.

22

log(ρ) = log(1 + (ρ − 1))
s
λα (1 − κ)
λα (1 − κ)
=
−
+ O(b−3/2 ),
2
2
(1 − α) κ b 2(1 − α)2 κ2 b
and
log2 (ρ) =

λα (1 − κ)
+ O(b−3/2 ).
(1 − α)2 κ2 b

(40)

(41)

Let us verify the induction result for t = 0. Using the recursion (9) with ξ00 = log κ(1−α)
1−κ = −υ,
we can express Eξ01 as
Eξ01 = −κb(ρ − 1) − υ + κbα log(ρ) + b(1 − κα)f (−υ).
Now using (38) and (40) we obtain
s
s
λ
b(1
−
κ)
λα (1 − κ)b
α
Eξ01 = −κ
− υ + κα
(1 − α)2 κ2
(1 − α)2 κ2

(42)

λα (1 − κ)α
2(1 − α)2 κ
s
λα (1 − κ)b
λα (1 − κ)
+
κ(1 − α) −
+ O(b−1/2 )
2
2
(1 − α) κ
2(1 − κα)
−

= −υ −

λα (1 − κ)
λα (1 − κ)
α−
+ O(b−1/2 ).
2(1 − α)2 κ
2(1 − κα)

(43)

We also obtain, using the formula for the variance of a Poisson random variable
Varξ01 = log2 (ρ)κbα + f 2 (−υ)(1 − κ)b + f 2 (−υ)κb(1 − α)
(1 − κ)λα
(a) λα α(1 − κ)
+
+ O(b−1/2 ),
=
(1 − α)2 κ
1 − κα

(44)

where in (a) we used (41) and (39). Comparing (43) and (44), after letting b → ∞ with µ(1) in
(13) using µ(0) = 0, we can verify the mean and variance recursions. Next we use Lemma 2 to
prove gaussianity. Note that we can express ξ01 − h as the Poisson sum of iid mixture random
variables as follows
L0
X
Xi ,
ξ01 − h =
i=1

where L0 ∼ Poi(b), and L(Xi ) = καL(log(ρ)) + (1 − κ)L(f (−υ)) + (κ(1 − α))L(f (−υ)), keeping
in mind the independent splitting property of Poissons, where L denotes the law of a rv2 . Next
we calculate E(|Xi |3 ). It is easy to show using (38) and (40) that
E(|Xi |3 ) = κα log3 (b) + (1 − κα)|f 3 (−υ)|= O(b−3/2 ).

(45)

Therefore the upper bound of Lemma 2 with λ = b becomes
C E(|Xi |3 )
O(b−3/2 )
pBE
= p
= O(b−1/2 ).
γ(µ2 + σ 2 )3
bΩ(b−3 )

√
Xi are iid with mean µ = κα log(ρ) + (1 − κα)f (−ν) = Ω(1/ b) and σ2 = Ω(1/b), both of which are
2
2
bounded (fixed b and as n → ∞). Also µ + σ = Ω(1/b).
2 Clearly

Inria

The Power of Side-information in Subgraph Detection

23

By Lemma 2, taking b → ∞ we obtain the convergence to Gaussian.
Having shown the induction hypothesis for t = 0, we now assume it holds for some t > 0. By
using (11), (15) and Lebesgue’s dominated convergence theorem [35, Theorem 16.4] we obtain
!
!
t
t
(ρ − 1)2
eξ1
e2ξ1
t
−
+ O(b−3/2 ),
Ef (ξ1 ) = (ρ − 1)E
(46)
E
t
t
2
1 + eξ1
(1 + eξ1 )2
and by using Lemma 4 in addition we obtain
Ef (ξ0t )

κ(1 − α)
E
= (ρ − 1)
1−κ



1
t
1 + eξ1



(ρ − 1)2 κ(1 − α)
E
−
2(1 − κ)

t

eξ1
t
(1 + eξ1 )2

!

+ O(b−3/2 ). (47)

PL
Now we take the expectation of both sides of (9) and (10). Using the fact that E i=1 Xi =
EXi EL if L ∼ Poi and Xi are independent and identically distributed (iid) rv, we obtain
 


p
κbα + E f (ξ0t ) (1 − κ)b + E f (ξ1t ) κb(1 − α)
E(ξ0t+1 ) = h + log
(48)
q
and

E(ξ1t+1 ) = h + log

 


p
κaα + E f (ξ0t ) (1 − κ)b + E f (ξ1t ) κa(1 − α).
q

(49)

We now substitute (47) and (46) in (48) to get:
E(ξ0t+1 )
=
+
−
+
−

h + κbα log(ρ)



κ(1 − α)
1
(1 − κ)b (ρ − 1)
E
t
1−κ
1 + eξ1
!

t
(ρ − 1)2 κ(1 − α)
eξ1
−3/2
E
+ O(b
)
t
2(1 − κ)
(1 + eξ1 )2
!

t
eξ1
κb(1 − α) (ρ − 1)E
t
1 + eξ1
!

t
e2ξ1
(ρ − 1)2
−3/2
E
+ O(b
) ,
t
2
(1 + eξ1 )2

which on simplifying and grouping like terms gives
λα (1 − κ)
E
E(ξ0t+1 ) = h + κbα log(ρ) + κ(a − b)(1 − α) −
2(1 − α)κ
Substituting h = −κ(a − b) − log
E(ξ0t+1 )

= − log

Using (40) we get
RR n° 8974



1−κ
κ(1 − α)





1−κ
κ(1−α)



t

eξ1
t
1 + eξ1

!

+ O(b−1/2 ).

, we get

λα (1 − κ)
− ακ(a − b) + κbα log(ρ) −
E
2κ(1 − α)

t

eξ1
t
1 + eξ1

!

+ O(b−1/2 ).

K. Avrachenkov et al.

24

−ακ(a − b) + κbα log(ρ)

κbα(log(ρ) − (ρ − 1))


λα (1 − κ)
−3/2
κbα − 2
+ O(b
)
2κ b(1 − α)2
λα α(1 − κ)
−
+ O(b−1/2 ).
2(1 − α)2 κ

=

=
=
Finally we obtain
E(ξ0t+1 )

= − log



1−κ
κ(1 − α)



λα α(1 − κ)
(1 − κ)
−
− λα
E
2(1 − α)2 κ
2(1 − α)κ

t

eξ1
t
1 + eξ1

!

+ O(b−1/2 ).

(50)

Using exactly the same simpliﬁcations we can get
E(ξ1t+1 ) = − log



1−κ
κ(1 − α)



αλα (1 − κ) λα (1 − κ)
+
+
E
2κ(1 − α)2
2κ(1 − α)

t

eξ1
t
1 + eξ1

!

+ O(b−1/2 ).

(51)

Our next goals are to compute var(ξ0t+1 ) and var(ξ1t+1 ). Towards this, observe that f 2 (x) =
 x 2
e
+ O(b−3/2 ). Therefore
(ρ − 1)2 1+e
x
!

t

E(f

2

(ξ0t ))

2

= (ρ − 1) E

e2ξ0
t
(1 + eξ0 )2

+ O(b−3/2 ),

and using Lemma 4 the above becomes
κ(1 − α)
E(f 2 (ξ0t )) = (ρ − 1)2
E
1−κ

t

eξ1
t
(1 + eξ1 )2

Similarly,

E f 2 (ξ1t ) = (ρ − 1)2 E

t

e2ξ1
t
(1 + eξ1 )2

!

!

+ O(b−3/2 ).

+ O(b−3/2 ).

(52)

(53)

P
2
Now we use the formula for the variance of Poisson sums Var L
i=1 Xi = E(Xi )E(L) to get
Var(ξ0t+1 ) = log2 (ρ)κbα + (1 − κ)bE(f 2 (ξ0t )) + κb(1 − α)E(f 2 (ξ1t ))

Var(ξ1t+1 ) = log2 (ρ)κaα + (1 − κ)bE(f 2 (ξ0t )) + κa(1 − α)E(f 2 (ξ1t )).
Substituting (52) and (53) into the above equations and letting b → ∞, we get
lim Var(ξ1t+1 ) = lim Var(ξ0t+1 ) = µ(t+1) ,

b→∞

where
µ(t+1) =

b→∞

λα α(1 − κ) λα (1 − κ)
+
E
κ(1 − α)2
κ(1 − α)



exp ξ1t
1 + exp(ξ1t )



.

(54)
Inria

The Power of Side-information in Subgraph Detection

Using µ(t+1) of (54) in (50) and (51) we get


(1 − κ)
t+1
−
E(ξ0 ) = − log
κ(1 − α)


(1 − κ)
E(ξ1t+1 ) = − log
+
κ(1 − α)

1 (t+1)
µ
+ O(b−1/2 )
2
1 (t+1)
µ
+ O(b−1/2 ).
2

25

(55)

Now we use the fact the induction assumption that ξ1t → N (E(ξ1t ), µ(t) ). Since the function
t
t
eξ1 /(1 + eξ1 ) is bounded, by Lebesgue’s dominated convergence theorem [35, Theorem 16.4] this
t
t
(t)
means E(1/(1 + e−ξ1 )) → E(1/(1 + e−N (E(ξ1 ),µ ) )) as b → ∞.We can write N (E(ξ1t ), µ(t) ) =
p
µ(t) Z + E(ξ1t ), where Z ∼ N (0, 1). Therefore we obtain




1
1

E
= E
√
t
(t)
(t)
(1−κ) − µ
1 + e−ξ1
1 + e− µ Z κ(1−α)
e 2
!
κ(1 − α)
.
=E
√ t µ(t)
κ(1 − α) + (1 − κ)e(− µ Z− 2 )
Substituting the above into (54) gives us the recursion for µ(t+1) given in (13).
Next we prove Gaussianity. Consider
ξ0t+1 − E(ξ0t+1 )
 
L00
X
p
t
(f (ξ0,i
) − E(f (ξ0t ))) +
(L0c − E(L0c )) +
= log
q
i=1
L01
X
i=1

t
(f (ξ1,i
) − E(f (ξ1t ))) + (L00 − E(L00 ))E(f (ξ0t )) +

(L01 − E(L01 ))E(f (ξ1t )).

(56)

t
t
Let us look at the second term. Let Xi = f (ξ0,i
) − Ef (ξ0,i
). Then it can be shown that
P
P
EL00
L00
2
EXi = O(1/b). Let D := i=1 Xi − i=1 Xi . In the second term the summation is taken up
Pδ
to i ≤ EL00 . Then E(D2 ) = | i=1 Xi |2 , where δ ≤ |L00 − EL00 |+1, where the extra 1 is because
√
EL00 may not be an integer. Therefore ED2 = EδE|X1 |2 ≤ (C/b)((1 − κ)b + 1)1/2 = O(1/ b).
Thus, we can replace the Poisson upper limits of the summations in the second and third terms
of (56) by their means, leading to

ξ0t+1 − E(ξ0t+1 ) = log

 
E(L01 )
E(L00 )
X
X
p
t
t
(f (ξ1,i
) − E(f (ξ1t )))
(f (ξ0,i
) − E(f (ξ0t ))) +
(L0c − E(L0c )) +
q
i=1
i=1

+ (L00 − E(L00 ))Ef (ξ0t ) + (L01 − E(L01 ))E(f (ξ1t )) + op (1),

(57)

where op (1) indicates a rv that goes to zero in probability in the limit. The combined variance
of all other terms approaches µ(t+1) , deﬁned in (13), as b → ∞ and it is ﬁnite for a ﬁxed t.
Now since we have an inﬁnite sum of independent rvs as a, b → ∞, with zero mean and ﬁnite
variance, from the standard CLT, we can conclude that the distribution tends to N (0, µt+1 ).
The argument for ξ1t+1 is identical.
RR n° 8974

K. Avrachenkov et al.

26

C

Finishing the proof of Theorem 1

Proof. We bound E(|S∆Sb0 |)/(K(1 − α)) as follows:


 Pn
E ( i=1 1σi 6=σbi )
E(|S∆Sb0 |)
= lim lim
b→∞ n→∞
b→∞ n→∞ K(1 − α)
K − Kα

(1 − κ)
≤ lim
P(ξ0t ≥ 0)+
b→∞ κ(1 − α)

P(ξ1t ≤ 0) ,
lim lim

(58)

since
E

n
X
i=1

1σi 6=σbi

!

=

n(P(ci = 0, σi = 0)P(Rit > υ|ci = 0, σi = 0) +
P(ci = 0, σi = 1)P(Rit < υ|ci = 0, σi = 1)),

(59)

t
and since Rit − Ri→u
= O(b−1/2 ). Indeed, given the b → ∞ limit in (58), the bound O(b−1/2 )
allows us to replace Rit in (59) by the distribution limit when n → ∞, which is ξ0t or ξ1t when
conditioned on {σi = 0} or {σi = 1} respectively, for an arbitrary i. We now analyze each term
in (58) separately. By Proposition 1 we have

lim

b→∞

P(ξ1t

1

p
µ(t)

≤ 0) = Q



(1 − κ)
µ(t)
− log
2
κ(1 − α)

!

where Q(·) denotes the standard Q function. Noticethat by (13) we have that µ(t) ≥ λα α(1 −
α (1−κ)
(t)
√
κ)/(κ(1 − α)2 ), since E κ(1−α)+(1−κ)1−κ
≤ λκ(1−α)
2 .
exp(−µ/2− µZ) ≥ 0. In addition, by (54), µ

Note that the lower bound on µ(t) is not useful when α = 0. Therefore by using the Chernoﬀ
2
bound for the Q function, Q(x) ≤ 12 e−x /2 , we get
1−κ
2
1 − 2µ1(t) ( µ(t)
2 −log( κ(1−α) ))
e
2
1−κ
2
1 − µ(t)
(1− (t)
log( κ(1−α)
) )2
µ
= e 8
2
1−κ
1 − µ(t) 12 log( κ(1−α)
)
≤ e 8 e
2s

lim P(ξ1t ≤ 0) ≤

b→∞

=

1
2

1 − κ − µ(t)
e 8 ,
κ(1 − α)

(60)

where we used the fact that (1 − x)2 ≥ 1 − 2x for any x > 0. By employing similar reductions,
we can show
s


1
1 − κ − µ(t)
(1 − κ)
t
P(ξ0 ≥ 0) ≤
e 8 .
lim
(61)
b→∞ κ(1 − α)
2 κ(1 − α)
Inria

The Power of Side-information in Subgraph Detection

27

Substituting (69) and (70) back in (58) and using the fact that µ(t) ≥ λα α(1 − κ)/(κ(1 − α)2 ),
we get
s
α α(1−κ)
E(|S∆Sb0 |)
1 − κ − λ8κ(1−α)
2
≤
e
lim lim
b→∞ n→∞ K(1 − α)
κ(1 − α)
Then using (22) we get the desired result in (21) .

References
[1] H. Firouzi, B. Rajaratnam, and A. O. Hero III, “Predictive correlation screening: Application to two-stage predictor design in high dimension.” in AISTATS, 2013, pp. 274–288.
[2] D. H. Chau, S. Pandit, and C. Faloutsos, “Detecting fraudulent personalities in networks of
online auctioneers,” in PKDD. Springer, 2006, pp. 103–114.
[3] A. Beutel, W. Xu, V. Guruswami, C. Palow, and C. Faloutsos, “Copycatch: stopping group
attacks by spotting lockstep behavior in social networks,” in Proceedings of the 22nd WWW.
ACM, 2013, pp. 119–130.
[4] S. T. Smith, E. K. Kao, K. D. Senne, G. Bernstein, and S. Philips, “Bayesian discovery of
threat networks,” IEEE Transactions on Signal Processing, vol. 62, no. 20, pp. 5324–5338,
2014.
[5] S. Chen, A. Sandryhaila, J. M. Moura, and J. Kovačević, “Signal recovery on graphs: Variation minimization,” IEEE Transactions on Signal Processing, vol. 63, no. 17, pp. 4609–4624,
2015.
[6] X. Wang, P. Liu, and Y. Gu, “Local-set-based graph signal reconstruction,” IEEE Transactions on Signal Processing, vol. 63, no. 9, pp. 2432–2444, 2015.
[7] V. E. Lee, N. Ruan, R. Jin, and C. Aggarwal, “A survey of algorithms for dense subgraph
discovery,” in Managing and Mining Graph Data. Springer, 2010, pp. 303–336.
[8] T. Miﬄin, C. Boner, G. Godfrey, and J. Skokan, “A random graph model for terrorist
transactions,” in 2004 IEEE Aerosp. Conf. Proc., vol. 5. IEEE, 2004, pp. 3258–3264.
[9] K. Rohe, S. Chatterjee, and B. Yu, “Spectral clustering and the high-dimensional stochastic
blockmodel,” Ann. Stat., pp. 1878–1915, 2011.
[10] B. Hajek, Y. Wu, and J. Xu, “Recovering a Hidden Community Beyond the Spectral Limit
in O(|E|log∗ |V |) Time,” arXiv Prepr. arXiv1510.02786, 2015.
[11] A. Montanari, “Finding one community in a sparse graph,” Journal of Statistical Physics,
vol. 161, no. 2, pp. 273–299, 2015.
[12] F. Caltagirone, M. Lelarge, and L. Miolane, “Recovering asymmetric communities in the
stochastic block model,” in Allerton 2016 54th Annual Allerton Conference on Communication, Control, and Computing, Monticello, United States, Sep. 2016.
[13] K. Avrachenkov, P. Gonçalves, A. Mishenin, and M. Sokol, “Generalized optimization framework for graph-based semi-supervised learning,” in Proceedings of the Twelfth SIAM International Conference on Data Mining, Anaheim, California, USA, April 26-28, 2012., 2012,
pp. 966–974.
RR n° 8974

28

K. Avrachenkov et al.

[14] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf, “Learning with local and
global consistency,” Advances in neural information processing systems, vol. 16, no. 16, pp.
321–328, 2004.
[15] X. Zhu, Z. Ghahramani, J. Laﬀerty et al., “Semi-supervised learning using gaussian ﬁelds
and harmonic functions,” in ICML, vol. 3, 2003, pp. 912–919.
[16] M. Mezard and A. Montanari, Information, physics, and computation.
Press, 2009.

Oxford University

[17] D. Koutra, T.-Y. Ke, U. Kang, D. H. P. Chau, H.-K. K. Pao, and C. Faloutsos, “Unifying
guilt-by-association approaches: Theorems and fast algorithms,” in Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2011, pp.
245–260.
[18] U. Kang, D. H. Chau, and C. Faloutsos, “Mining large graphs: Algorithms, inference, and
discoveries,” in 2011 IEEE 27th International Conference on Data Engineering. IEEE,
2011, pp. 243–254.
[19] T. Miﬄin, C. Boner, G. Godfrey, and J. Skokan, “A random graph model for terrorist
transactions,” in 2004 IEEE Aerosp. Conf. Proc. (IEEE Cat. No.04TH8720), vol. 5. IEEE,
2004, pp. 3258–3264.
[20] B. A. Miller, N. T. Bliss, and P. P. J. Wolfe, “Subgraph detection using eigenvector L1
norms,” in Adv. Neural Inf. Process. Syst. 23 24th Annu. Conf. Neural Inf. Process. Syst.
2010, NIPS 2010, 2010, pp. 1–9.
[21] A. Kadavankandy, L. Cottatellucci, and K. Avrachenkov, “Characterization of L1 -norm
statistic for Anomaly Detection in Erdös Rényi Graphs,” in CDC. IEEE, 2016.
[22] N. Alon, M. Krivelevich, and B. Sudakov, “Finding a large hidden clique in a random graph,”
Random Structures and Algorithms, vol. 13, no. 3-4, pp. 457–466, 1998.
p
[23] Y. Deshpande and A. Montanari, “Finding hidden cliques of size N/e in nearly linear
time,” Foundations of Computational Mathematics, vol. 15, no. 4, pp. 1069–1128, 2015.
[24] B. Hajek, Y. Wu, and J. Xu, “Information limits for recovering a hidden community,” in
Information Theory (ISIT), 2016 IEEE International Symposium on. IEEE, 2016, pp.
1894–1898.
[25] B. A. Miller, S. Kelley, R. S. Caceres, and S. T. Smith, “Residuals-based subgraph detection
with cue vertices,” in 2015 49th Asilomar Conference on Signals, Systems and Computers.
IEEE, 2015, pp. 1530–1534.
[26] A. E. Allahverdyan, G. Ver Steeg, and A. Galstyan, “Community detection with and without
prior information,” EPL (Europhysics Letters), vol. 90, no. 1, p. 18002, 2010.
[27] T. T. Cai, T. Liang, and A. Rakhlin, “Inference via message passing on partially labeled
stochastic block models,” arXiv preprint arXiv:1603.06923, 2016.
[28] E. Mossel and J. Xu, “Local Algorithms for Block Models with Side Information,” in ITCS
’16. New York, New York, USA: ACM Press, jan 2016, pp. 71–80.
Inria

The Power of Side-information in Subgraph Detection

29

[29] 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 preprint arXiv:1512.09080, 2015.
[30] A. Kadavankandy, K. Avrachenkov, L. Cottatellucci, and R. Sundaresan, “Belief propagation
for subgraph detection with imperfect side-information,” in Submitted to ISIT 2017. IEEE,
Awaiting review.
[31] R. Andersen and F. Chung, “Detecting sharp drops in PageRank and a simpliﬁed local
partitioning algorithm,” Theory Appl. Model. Comput., vol. 4484/2007, no. 3, pp. 1–12,
2007.
[32] J. Yang and J. Leskovec, “Deﬁning and evaluating network communities based on groundtruth,” Knowledge and Information Systems, vol. 42, no. 1, pp. 181–213, 2015.
[33] D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Schölkopf, “Learning with Local and
Global Consistency,” Adv. Neural Inform. Process. Syst., vol. 16, pp. 321–328, 2004.
[34] J. Chen and Y. Saad, “Dense subgraph extraction with application to community detection,”
IEEE Transactions on Knowledge and Data Engineering, vol. 24, no. 7, pp. 1216–1230, 2012.
[35] P. Billingsley, Probability and measure. John Wiley & Sons, 2008.
[36] N. Alon and J. H. Spencer, The probabilistic method. John Wiley & Sons, 2004.

RR n° 8974

K. Avrachenkov et al.

30

Supplementary Material
t
Proof of Proposition 3. We derive the conditional distributions of the messages Ru→i
for a ﬁnite
t given {σu = 0} and given {σu = 1}. In this limit the tree coupling of Lemma 3 holds with a
slightly modiﬁed construction of the tree to accomodate the diﬀerence in the generation of cued
nodes. It is similar to the tree coupling in Lemma 3, with the only diﬀerence being the generation
of cues. At any level of the tree, a node u is labelled a cue such that P(cu = 1|τu = 1) = αβ
and P(cu = 1|τu = 0) = κα(1 − β)/(1 − κ), so that the equalities in (2) and (4) hold, where cu
t
t
t
denotes the cue membership of node u on the tree. Let Fu→i
be such that Ru→i
= Fu→i
+ hu ,
t
for any two neighbouring nodes i and u. Then, it can be seen from (25) that Fu→i satisﬁes the
following recursion
X
t+1
Fu→i
= −κ(a − b) +
fisi (Flt + hl ),
(62)
l∈δu,l6=i

where fisi (x) := log



e(x−ν) ρ+1
e(x−ν) +1



. Let Ψt0 , Ψt1 be the rvs that have the conditional asymptotic

t
distribution of Fu→i
given {σu = 0} and {σu = 1} respectively in the limit n → ∞. Then, by
studying the recursion (62) on the tree we can conclude that Ψt0 , Ψt1 satisfy the following recursive
distributional equations

D

Ψt+1
= −κ(a − b) +
0
L
01n
X

L
01c
X

fisi (Ψt1i + Bc )+

i=0

fisi (Ψt1i + Bn ) +

fisi (Ψt0i + Bc )+

i=0

i=0

L
00n
X

L
00c
X

fisi (Ψt0i + Bn ),

(63)

i=0

D
=
Ψt+1
1

−κ(a − b) +

L
11n
X

L
11c
X
i=0

fisi (Ψt1i + Bn ) +

L
10c
X

fisi (Ψt0i + Bc )+

i=0

i=0

L
10n
X

fisi (Ψt1i + Bc )+

fisi (Ψt0i + Bn ),

(64)

i=0

D

where = represents equality in distribution, and the random sums are such that L01c ∼ Poi(κbαβ), L01n ∼
Poi(κb(1−αβ)), L00c ∼ Poi(κbα(1−β)), L00n ∼ Poi(b(1−κ−κα(1−β)), L11c ∼ Poi(κaαβ),
 L11n ∼

Poi(κa(1−αβ)), L10c ∼ Poi(κbα(1−β)), and L10n ∼ Poi(b(1−κ−κα(1−β))), Bc = log β(1−κ)
(1−β)κ ;


(1−αβ)(1−κ)
; and Ψt0,i and Ψt1,i are iid rvs with the same distribution as Ψt0 and
Bn = log (1−κ−ακ+ακβ)
Ψt1 respectively.

We now derive the asymptotic distributions q
Ψt+1
and Ψt+1
when a, b → ∞ such that λ =
0
1
2
pr
κ (a−b)
λ(1−κ)
= 1 + b , where r := λ(1−κ)
(1−κ)b and κ are ﬁxed. Observe that ρ = 1 +
κ2 b
κ2 . Notice
2

Inria

The Power of Side-information in Subgraph Detection

31

that if P0 ∼ L(Ψt0 ) and P1 = L(Ψt1 ), we have, since Ψ = log



dP1
dP0



, that

dP0
dP1 (Ψ)

= e−Ψ . Also



ex−ν
fisi (x) = log 1 + (ρ − 1)
1 + ex−ν
r  x−ν 
e
r
−
=
b 1 + ex−ν
 x−ν 2
1r
e
+ O(b−3/2 ),
2 b 1 + ex−ν
and
2
fisi
(x) =

r
b



ex−ν
1 + ex−ν

2

(65)
(66)
(67)

+ O(b−3/2 ).

(68)

Now we can reformulate the recursions in (63) and (64) as a Poisson sum as follows:
D

= −κ(a − b) +
Ψt+1
0
D
Ψt+1
=
1

−κ(a − b) +

L0
X

Xl

(69)

Yl ,

(70)

l=1

L1
X
l=1

where L0 = Poi(b), L1 = Poi(κa + (1 − κ)b) and Xl and Yl are mixture rvs with laws deﬁned as
follows:
L(Xl ) = ακ(1 − β)L(fisi (Ψt0 + Bc )) + (1 − κ)(1 − α(1 − β)e−ν )L(fisi (Ψt0 + Bn ))
+ ακβL(fisi (Ψt1 + Bc )) + κ(1 − αβ)L(fisi (Ψt1 + Bn )),
L(Yl ) =

(1 − κ)b(1 − α(1 − β)e−ν )
ακb(1 − β)
L(fisi (Ψt0 + Bc )) +
L(fisi (Ψt0 + Bn ))
κa + (1 − κ)b
κa + (1 − κ)b
κaαβ
κa(1 − αβ)
+
L(fisi (Ψt1 + Bc )) +
L(fisi (Ψt1 + Bn )).
κa + (1 − κ)b
κa + (1 − κ)b

κ(1−αβ)
β
) and Bn − ν = log( (1−κ−ακ(1−β))
). We can calculate
Observe that we have Bc − ν = log( 1−β
E(Xl ) as
!
r
r
t
r
r
r
eΨ1 +Bc −ν
E(Xl ) = ακβ
+ κ(1 − αβ)
− ακβ E
t
b
b
2b
1 + eΨ1 +Bc −ν
!
t
eΨ1 +Bn −ν
r
+ O(b−3/2 ),
− κ(1 − αβ) E
t
2b
1 + eΨ1 +Bn −ν

which gives,
E(Xl ) = κ

r

r
r
− ακβ E
b
2b

t

eΨ1 +Bc −ν
t
1 + eΨ1 +Bc −ν

!

r
− κ(1 − αβ) E
2b

t

eΨ1 +Bn −ν
t
1 + eΨ1 +Bn −ν

!

+ O(b−3/2 ).

Similarly
E(Xl2 )
RR n° 8974

r
= ακβ E
b

t

eΨ1 +Bc −ν
t
1 + eΨ1 +Bc −ν

!

rκ(1 − αβ)
E
+
b

t

eΨ1 +Bn −ν
t
1 + eΨ1 +Bn −ν

!

+ O(b−3/2 ),

K. Avrachenkov et al.

32

and
E(|Xl3 |)

t

e2(Ψ1 +Bc −ν)
t
(1 + eΨ1 +Bc −ν )2

r
= ακβ( )3/2 E
b

!

t

+

e2(Ψ1 +Bn −ν)
t
(1 + eΨ1 +Bn −ν )2

κ(1 − αβ)r3/2
E
b3/2

!

+O(b−2 ).

(71)

Similarly we can calculate the moments of Yl as follows:
!
r
t
ακbβ
r
1 + ρeΨ1 +Bc −ν
E(Yl ) =
E
t
κa + (1 − κ)b b
1 + eΨ1 +Bc −ν
t

t

t

t

eΨ1 +Bc −ν (1 + ρeΨ1 +Bc −ν )
rακβ
E
−
t
2(κa + (1 − κ)b)
(1 + eΨ1 +Bc −ν )2
!
r
t
1 + ρeΨ1 +Bn −ν
r
κb(1 − αβ)
E
+
t
κa + (1 − κ)b b
1 + eΨ1 +Bn −ν
rκ(1 − αβ)
E
−
2(κa + (1 − κb))

!

eΨ1 +Bn −ν (1 + ρeΨ1 +Bn −ν )
t
(1 + eΨ1 +Bn −ν )2

giving

!

+ O(b−3/2 ),

t

√
E(Yl ) = κ rb

1
rαβκ
eΨ1 +Bc −ν
+
E
t
κa + (1 − κ)b 2(κa + (1 − κ)b)
1 + eΨ1 +Bc −ν
!
t
rκ(1 − αβ)
eΨ1 +Bn −ν
+
+ O(b−3/2 ).
E
t
2(κa + (1 − κ)b)
1 + eΨ1 +Bn −ν

!

In addition,
E(Yl2 )

ακβr
=
E
κa + (1 − κ)b

t

eΨ1 +Bc −ν
t
1 + eΨ1 +Bc −ν

!

+ O(b−2 )

κr(1 − αβ)
+
E
κa + (1 − κ)b

t

eΨ1 +Bn −ν
t
1 + eΨ1 +Bn −ν

!

and
E(|Yl3 |)
=

ακβr3/2
E
(κa + (1 − κ)b)b1/2

κ(1 − αβ)r3/2
+
E
(κa + (1 − κ)b)b1/2

t

e2Ψ1 +2Bc −2ν
t
(1 + eΨ1 +Bc −ν )2
t

!

e2Ψ1 +2Bn −2ν
t
(1 + eΨ1 +2Bn −ν )2

!

+O(b−2 ).

(72)

Let us deﬁne µ(t) as
µ(t+1) = αβκrE



1
t

1 + e−Ψ1 −Bc +ν



+ κr(1 − αβ)E



1
t

1 + e−Ψ1 −Bn +ν



.

(73)
Inria

The Power of Side-information in Subgraph Detection

33

Finally we have
E(Ψt+1
0 ) = −κ(a − b) + bE(Xl )
ακβr
E
=−
2

t

eΨ1 +Bc −ν
t
1 + eΨ1 +Bc −ν
t

eΨ1 +Bn −ν
t
1 + eΨ1 +Bn −ν

κ(1 − αβ)r
E
−
2
=−

!

!

+ O(b−1/2 )

µt+1
+ O(b−1/2 ),
2

and
E(Ψt+1
1 ) = −κ(a − b) + (κa + (1 − κ)b)E(Yl )
!
t
eΨ1 +Bc −ν
ακβr
E
=
t
2
1 + eΨ1 +Bc −ν
!
t
κ(1 − αβ)r
eΨ1 +Bn −ν
+
E
+ O(b−1/2 )
t
2
1 + eΨ1 +Bn −ν
=

µ(t+1)
+ O(b−1/2 ).
2

In addition, for the variances of Ψt+1
and Ψt+1
we have
0
1
2
Var(Ψt+1
0 ) = bE(Xl )
t

= αβκrE

eΨ1 +Bc −ν
t
1 + eΨ1 +Bc −ν

!

t

+ κ(1 − αβ)rE

eΨ1 +Bn −ν
t
1 + eΨi +Bn −ν

!

+ O(b−1/2 )

= µ(t+1) + O(b−1/2 ),

(74)

and similarly
2
Var(Ψt+1
1 ) = (κa + (1 − κ)b)E(Yl )

=µ

(t+1)

+ O(b

−1/2

).

(75)
(76)

Now we need to show the Gaussianity of the messages Ψt0 and Ψt1 , which we show using Lemma
2. For (69) the upperbound in Lemma 2 becomes
C E(|Xi |3 )
CBE bE(|Xi |3 )
pBE
= p
2
2
3
γ(µ + σ )
(b(µ2 + σ 2 ))3
=

CBE bE(|Xi |3 )
3/2
Var(Ψt+1
0 )

(77)

Similarly for (70) we get
CBE E(|Yi |3 )
CBE (κa + (1 − κ)b)E(|Yi |3 )
p
=
.
3/2
Var(Ψt+1
γ(µ2 + σ 2 )3
1 )
RR n° 8974

(78)

K. Avrachenkov et al.

34

In Lemma 6 stated and proved below, we show that µ(t+1) ≥ αβ 2 λ 1−κ
κ . Therefore for any
κ < 1/2, we have
t+1
Var(Ψt+1
0 ) = Var(Ψ0 ) ≥

αβ 2 λ
+ O(b−1/2 ) = Θ(1),
2

under the assumptions of the proposition. In addition we have bE(|Xi |3 ) = O(b−1/2 ) and (κa +
(1 − κ)b)E(|Yi |3 ) = O(b−1/2 ) from (71) and (72). Thus the bounds given in (77) and (78) both
tend to zero as b → ∞.
(t)
(t)
Hence by Lemma 2, we obtain that Ψt1 → N ( µ2 , µ(t) ) and Ψt0 → N (− µ2 , µ(t) ) as b → ∞,
where from (73), µ(t) satisﬁes the following recursion with inital condition µ(0) = 0 :
!
!
(1 − κ)
(1 − κ)
(t+1)
+ (1 − αβ)λE
.
µ
= αβλE
√
√
µ(t)
µ(t)
(t)
(t)
κ + (1 − κ)e− µ Z− 2 −Bc
κ + (1 − κ)e− µ Z− 2 −Bn
(79)
t
Consequently, the distributions of the messages Ru→i
in the limit of n → ∞ converge to Γtj + hu ,
(t)

(t)

given {σu = j}, where Γt1 ∼ N ( µ2 , µ(t) ) and Γt0 ∼ N (− µ2 , µ(t) ), in the large degree limit
where b → ∞.

Proving the bound on µ(t)
Let F (µ) be deﬁned as
F (µ)
= αβ 2 λE



(1 − κ)/κ
√
β + (1 − β) exp(−µ/2 − µZ)



+

(1 − αβ)2 λ


(1 − κ)
√
E
.
κ(1 − αβ) + (1 − κ − ακ + ακβ)e(−µ/2− µZ )
Then µ(t) satisﬁes the recursion µ(t+1) = F (µ(t) ), by substituting for Bc and Bn in (79). Below
we show a lower bound on F (µ). For its proof we need the following Lemma from [36].
Lemma 5. [36, Theorem 6.2.1] If f, g : R → R are two non-decreasing functions, then E(f g) ≥
E(f )E(g).
Now we state our result on F (µ).
Lemma 6. For 0 < β < 1,
F (µ) ≥ αβ 2 λ
Proof. We show that
gβ = E



1−κ
.
κ

1
√
β + (1 − β) exp(−µ/2 − µZ)



√
d
is nonincreasing for 0 ≤ β ≤ 1 as shown below. Let X = exp(− µZ). Then dβ
(gβ ) =


exp(−µ/2)X−1
d
E (β+(1−β)e−µ/2 X)2 . Now we show dβ (gβ ) < 0 using Lemma 5. In Lemma 5, let f =
Inria

The Power of Side-information in Subgraph Detection

−1
. Clearly these
(β+(1−β)e−µ/2 X)2
√
µZ
−µ/2

exp(−µ/2)X and g =

E(f )E(g) = E(g), since E(f ) = Ee
E



35

are non-decreasing in X. Therefore E(f g) ≥

= 1. Therefore we have

e

−e−µ/2 X
(β + (1 − β)e−µ/2 X)2



≥E



−1
(β + (1 − β)e−µ/2 X)2



,

dg

hence dββ < 0 for all β. Therefore 1 = gβ (1) ≤ gβ (β) for β < 1. The result then follows by
substituting this lower bound in the deﬁnition of F (µ) and observing that the second term is
strictly non-negative.

Proof of Theorem 2
Proof. Notice that when we set β = 1 the recursion (28) becomes the same as (13). Also, when
β = 0 we can retrieve the recursion for standard BP without side-information, i.e., and from this
it can be gleaned that the asymptotic error rate is zero only if λ > 1/e.
Let us now consider 0 < β < 1. By Lemma 6, we have
αβ 2 λ
Hence µ(t) = Θ

1−κ
κ



1−κ
(1 − κ)
≤ µ(t) ≤ λ
.
κ
κ

. The asymptotic distributions of the messages are as follows:

Γt0,0
Γt0,1
Γt1,0
Γt1,1



(1 − αβ)(1 − κ)
∼ N (−µ /2, µ ) + log
(1 − κ − ακ + ακβ)


β(1 − κ)
(t)
(t)
∼ N (−µ /2, µ ) + log
κ(1 − β)


(1 − αβ)(1 − κ)
∼ N (µ(t) /2, µ(t) ) + log
(1 − κ − ακ + ακβ)


β(1 − κ)
∼ N (µ(t) /2, µ(t) ) + log
,
κ(1 − β)
(t)

(t)



t
where Γtj,k is the rv with the asymptotic distribution of the messages Ru→i
in the limit of n → ∞
and b → ∞, given {σu = j, cu = k}. We can now write the probability of error pβe of the per-node
MAP detector Sb0 as

pβe = pβe (i|σi = 0, ci = 0)P (σi = 0, ci = 0)+
pβe (i|σi = 0, ci = 1)P (σi = 0, ci = 1)
+ pβe (i|σi = 1, ci = 0)P (σi = 1, ci = 0)
+ pβe (i|σi = 1, ci = 1)P (σi = 1, ci = 1)
= P0,0 (Rit > ν)π0,0 + P0,1 (Rit > ν)π0,1
+ P1,0 (Rit < ν)π1,0 + P1,1 (Rit < ν)π1,1 ,

is the error rate of Algorithm 2, where pβe (i|σi = 0, ci = 0) denotes the probability that node i is
misclassiﬁed, given {σi = 0, ci = 0} and π0,1 = P(σi = 0, ci = 1) etc. Then the expected fraction
RR n° 8974

K. Avrachenkov et al.

36

of mislabelled nodes

E(|Ŝ0 ∆S|)
K

in the limit n → ∞, b → ∞ is

npβe
lim lim
b→∞ n→∞ K
 (t)
= Q

µ
2

(1 − αβ)


Q


µ(t)
2


β
+ log( (1−β)
)
 αβ +
p
µ(t)
− log




1−κ
κ



1− ακ(1−β)
1−κ
1−αβ

p
µ(t)

 


+



β
− log( 1−β
)
+
p
α(1 − β)Q 
µ(t)


 (t)
(1−αβ)κ
µ
2 − log (1−κ−ακ+ακβ)
1−κ
.
p
− α(1 − β))Q 
(
κ
µ(t)
µ(t)
2

We can show, by a calculation similar to the one followed in the proof of Theorem 1, that
npβe
lim lim
b→∞ n→∞ K

p
≤
α β(1 − β) +
r

λαβ 2 (1−κ)
1−κ
8κ
(1 − αβ)(
.
− α(1 − β)) e−
κ
Finally by a similar calculation to (22),
b
E(|S∆S|)
lim lim
n→∞
b→∞
K

p
≤ 2 α β(1 − β) +
r

λαβ 2 (1−κ)
1−κ
8κ
(1 − αβ)(
.
− α(1 − β)) e−
κ

Contents
1 Introduction
1.1 Problem Motivation . . . .
1.2 Previous works . . . . . . .
1.3 Summary of Results . . . .
1.4 Organization . . . . . . . .
1.5 Notation and Nomenclature

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

3
3
3
5
5
5
Inria

The Power of Side-information in Subgraph Detection

37

2 Model and Problem Definition

6

3 Belief Propagation Algorithm for Detection with Perfect Side-information

7

4 Asymptotic Error Analysis
4.1 Detection Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8
10

5 Imperfect Side Information

12

6 Numerical Experiments
6.1 Synthetic dataset . . . . . .
6.2 Real-world datasets . . . . .
6.2.1 USPS dataset . . . .
6.2.2 Reuters911 Dataset

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

14
14
16
16
16

7 Conclusions and Future Extensions

16

A Description of G-W tree and derivation of Algorithm 1

17

B Proof of Proposition 1

20

C Finishing the proof of Theorem 1

26

RR n° 8974

RESEARCH CENTRE
SOPHIA ANTIPOLIS – MÉDITERRANÉE

2004 route des Lucioles - BP 93
06902 Sophia Antipolis Cedex

Publisher
Inria
Domaine de Voluceau - Rocquencourt
BP 105 - 78153 Le Chesnay Cedex
inria.fr
ISSN 0249-6399

