Arun Kadavankandy

Konstantin Avrachenkov

Laura Cottatellucci

Rajesh Sundaresan

The Power of Side-information in Subgraph Detection

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 side-information. The first 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 a so-called effective 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 a suitably defined phase-transition parameter. We validate our results on synthetic datasets and a few real world networks.

I. INTRODUCTION

1) 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 application of dense subgraph detection in Signal Processing is the problem of Correlation Mining [START_REF] Firouzi | Predictive correlation screening: Application to two-stage predictor design in high dimension[END_REF]. Consider a network with nodes representing correlated 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 [START_REF] Firouzi | Predictive correlation screening: Application to two-stage predictor design in high dimension[END_REF]. Dense subgraph detection also finds application in realworld computer and social networks; for e.g., in detecting fraudulent activity [START_REF] Beutel | Copycatch: stopping group attacks by spotting lockstep behavior in social networks[END_REF], [START_REF] Chau | Detecting fraudulent personalities in networks of online auctioneers[END_REF], [START_REF] Smith | Bayesian discovery of threat networks[END_REF]. It can also be viewed as a signal recovery problem on graphs [START_REF] Chen | Signal recovery on graphs: Variation minimization[END_REF], [START_REF] Wang | Local-set-based graph signal reconstruction[END_REF].

A majority of subgraph detection algorithms try to find a subset of nodes that maximizes some objective such as the average link density within the subset [START_REF] Lee | A survey of algorithms for dense subgraph discovery[END_REF]. A good way to benchmark the performance of various community detection algorithms is to validate them on generative graph models A.

Kadavankandy is with CentraleSupélec, Paris(email:arun.kadavankandy@supelec.fr) K. Avrachenkov is with Inria, Sophia Antipolis, France(email:konstantin.avratchenkov@inria.fr).

L. Cottatellucci was with Department of Communication Systems, EU-RECOM, Sophia-Antipolis, France. She is with Institute of Digital Communications, Friedrich-Alexander Universität, Erlangen-Nürnberg, Germany, (email:laura.cottatellucci@fau.de).

R. Sundaresan is with Indian Institute of Science, Bangalore, India(email:rajeshs@iisc.ac.in).

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ős-Renyi graph. This model was used in [START_REF] Mifflin | A random graph model for terrorist transactions[END_REF] to capture terrorist transactions in a computer network. It is a special case of the Stochastic Block Model (SBM), widely used to assess the performance of different community detection algorithms [START_REF] Rohe | Spectral clustering and the highdimensional stochastic blockmodel[END_REF].

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 [START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF], [START_REF] Hajek | Recovering a Hidden Community Beyond the Spectral Limit in O(|E|log * |V |) Time[END_REF], [START_REF] Montanari | Finding one community in a sparse graph[END_REF]. 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 [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF], [START_REF] Zhou | Learning with local and global consistency[END_REF], [START_REF] Zhu | Semi-supervised learning using gaussian fields and harmonic functions[END_REF].

In this paper we focus on local distributed algorithms that are essential for graph clustering application when the graph is distributed over a computer cluster or a cloud. Furthermore, in graph applications involving extremely large sizes as is the typical case in Big Data problems, the full graph is not available to the algorithm, and one is often interested in a local solution or in a local low-conductance cut in graph clustering terminology. Such considerations have been pursued in the works [START_REF] Andersen | Detecting sharp drops in PageRank and a simplified local partitioning algorithm[END_REF], [START_REF] Gleich | Seeded pagerank solution paths[END_REF] and references therein.

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 efficient way to perform approximate Maximum Likelihood (ML) detection on certain types of graphs using distributed and local message passing [START_REF] Mezard | Information, physics, and computation[END_REF]. It belongs to the class of guiltby-association schemes [START_REF] Koutra | Unifying guilt-by-association approaches: Theorems and fast algorithms[END_REF] and has been successfully applied to many practical problems in graphs such as fraud detection [START_REF] Chau | Detecting fraudulent personalities in networks of online auctioneers[END_REF] and data mining [START_REF] Kang | Mining large graphs: Algorithms, inference, and discoveries[END_REF].

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 [START_REF] Kadavankandy | Characterization of L 1 -norm statistic for Anomaly Detection in Erdös Rényi Graphs[END_REF], [START_REF] Mifflin | A random graph model for terrorist transactions[END_REF], [START_REF] Miller | Subgraph detection using eigenvector l1 norms[END_REF] 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 -) log 2 (n), the clique is impossible to detect; however, an exhaustive search detects the clique nodes when K ≥ 2(1 + ) log 2 (n). In contrast, the smallest clique size that can be detected in polynomial time is believed to be c √ n [START_REF] Alon | Finding a large hidden clique in a random graph[END_REF] for some c > 0, and the minimum clique-size that can be detected in nearly-linear time is believed to be n/e [START_REF] Deshpande | Finding hidden cliques of size N/e in nearly linear time[END_REF].

The computational barriers for subgraph detection in a sparse graph without cues were studied in [START_REF] Hajek | Recovering a Hidden Community Beyond the Spectral Limit in O(|E|log * |V |) Time[END_REF], [START_REF]Information limits for recovering a hidden community[END_REF], [START_REF] Montanari | Finding one community in a sparse graph[END_REF]. In [START_REF] Montanari | Finding one community in a sparse graph[END_REF] the author investigated the performance of ML detection and BP, and analyzed the phase transition with respect to an effective signal-to-noise ratio (SNR) parameter λ defined 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 [START_REF]Information limits for recovering a hidden community[END_REF] the authors show that when K = o(n), i.e., when κ → 0, and p, q are such that a = np = n o (1) and p/q = O(1), ML detection succeeds when λ = Ω( K n log( n 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 [START_REF] Hajek | Recovering a Hidden Community Beyond the Spectral Limit in O(|E|log * |V |) Time[END_REF]. Therefore, λ = 1/e represents a computational barrier for BP in the subgraph detection problem without side-information.

In the present work, we examine the impact of sideinformation on the above computational barrier. To the best of our knowlege, ours is the first theoretical study of the performance of local algorithms for subgraph detection in the presence of side-information in G(K, n, p, q). In [START_REF] Miller | Residuals-based subgraph detection with cue vertices[END_REF], the authors compared, but only empirically, several guilt-byassociation schemes for subgraph detection with cues.

There exist many works on the effect of side-information in the context of identifying multiple communities [START_REF] Allahverdyan | Community detection with and without prior information[END_REF], [START_REF] Cai | Inference via message passing on partially labeled stochastic block models[END_REF], [START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF], [START_REF] Mossel | Local Algorithms for Block Models with Side Information[END_REF]. These works considered a different 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 [START_REF] Cai | Inference via message passing on partially labeled stochastic block models[END_REF] and [START_REF] Mossel | Local Algorithms for Block Models with Side Information[END_REF] consider a BP algorithm to detect two equal-sized communities. In [START_REF] Mossel | Local Algorithms for Block Models with Side Information[END_REF], 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 [START_REF] Abbe | Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic bp, and the information-computation gap[END_REF]. In [START_REF] Cai | Inference via message passing on partially labeled stochastic block models[END_REF], 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 [START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF], which considers asymmetric communities and asymmetric connection probabilities within communities. In this setting, the authors of [START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF] 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, [START_REF] Mossel | Local Algorithms for Block Models with Side Information[END_REF] and [START_REF] Cai | Inference via message passing on partially labeled stochastic block models[END_REF] consider equal-sized communities with the same edge probability within each community.

In [START_REF] Cai | Inference via message passing on partially labeled stochastic block models[END_REF], [START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF], [START_REF] Mossel | Local Algorithms for Block Models with Side Information[END_REF], the parameters are chosen such that node degrees alone are not informative. Our work is different 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. In this setting we show that the computational barrier disappears when side-information is available. Additionally, our results cannot be obtained as a special case of the results in [START_REF] Allahverdyan | Community detection with and without prior information[END_REF], [START_REF] Cai | Inference via message passing on partially labeled stochastic block models[END_REF], [START_REF] Caltagirone | Recovering asymmetric communities in the stochastic block model[END_REF], [START_REF] Mossel | Local Algorithms for Block Models with Side Information[END_REF].

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 semisupervised clustering applications [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF], [START_REF] Zhou | Learning with local and global consistency[END_REF], [START_REF] Zhu | Semi-supervised learning using gaussian fields and harmonic functions[END_REF].

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 fixed and K = κn with κ fixed, as in the regime of [START_REF] Montanari | Finding one community in a sparse graph[END_REF]. We derive recursive equations for the distributions of BP messages in the limit as the graph size n tends to infinity. These recursions allow for numerical computation of the error rates for finite 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 misclassified nodes goes to zero as κ → 0, for any positive value of the phase transition 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 findings 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 presented at ISIT 2017 [START_REF] Kadavankandy | Belief propagation for subgraph detection with imperfect sideinformation[END_REF]. 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.

4) Organization:

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

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 of one. Similarly, we also work with t-hop neighbours of i, denoted as G t i , the set of nodes within a distance of t from i. Note that G 1 i = δ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 symmetric difference, 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 µ and variance σ 2 . The symbol D -→ denotes convergence in distribution.

II. 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 ∈ S) = P((i, j) ∈ E|i, j ∈ 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 c i = 1 if i is a cued vertex and c i = 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

P(c i = 1|σ i = x) = α if x = 1 0 if x = 0,
for some α ∈ (0, 1). Under this model we have

nP(c i = 1) = i∈V P(c i = 1|σ i = 1)P(σ i = 1) = αK. (2)
2) Imperfect side-information: Under imperfect sideinformation, the cues are unreliable. We generate C by sampling nodes from V as follows using a fixed β ∈ (0, 1]. For any i ∈ V :

P (c i = 1|σ i = x) = αβ if x = 1, αK(1-β) (n-K) if x = 0. (3)
Under this model we have for any i ∈ V,

P(c i = 1) = P(σ i = 1)P(c i = 1|σ i = 1) + P(σ i = 0)P(c i = 1|σ i = 0) = K n αβ + (n -K) n αK(1 -β) (n -K) = αK/n;
hence it matches with (2) of the perfect side-information case. It is easy to verify that under the above sampling

P (σ i = 1|c i = 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 minimizing the expected number of misclassified nodes is the per-node MAP detector given as [START_REF]Information limits for recovering a hidden community[END_REF]:

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

R i = 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 R i for each i using a local 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.

III. 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 sideinformation. In order to avoid erroneous likelihood computations, the number of steps t f of the BP algorithm must be small enough not to encounter loops. By Lemma 3, this can be ensured with high probability if t f < log(n) log(np) + 1. We provide here a brief overview of the algorithm. At step t of Algorithm 1, each node u ∈ V \C updates its own loglikelihood ratio based on its t-hop neighbourhood:

R t u := log P(G t u , C t u |σ u = 1) P(G t u , C t u |σ u = 0) , (5)
where G t u is the set of t-hop neighbours of u and C t u is the set of cues in G t u , i.e., C t u = G t u ∩ C. The beliefs are updated according to [START_REF] Cai | Inference via message passing on partially labeled stochastic block models[END_REF]. The messages transmitted to u by the nodes i ∈ δu, the immediate neighbourhood of u, are given by

R t i→u := log P(G t i \u, C t i \u|σ i = 1) P(G t i \u, C t i \u|σ i = 0) , (6)
where G t i \u and C t i \u are defined as above, but excluding the contribution from node u. Node i updates R t i→u by acquiring messages from its neighbours, except u, and aggregating them according to [START_REF] Billingsley | Probability and measure[END_REF]. 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 t f steps of BP is O(t f |E|).

Algorithm 1 BP with perfect side-information

1: Initialize: Set R 0 i→j to 0, for all (i, j) ∈ E with i, j ∈ C. Let t f < log(n) log(np) + 1. Set t = 0. 2: For all directed pairs (i, u) ∈ E, such that i, u / ∈ C: R t+1 i →u = -K(p -q) + l∈C 1 i ,l =u log p q + l∈δi\C 1 i ,l =u log exp(R t l→i -υ)(p/q) + 1 exp(R t l→i -υ) + 1 , (7)
where υ = log( n-K K(1-α) ).

R t+1 u = -K(p -q) + l∈C 1 u log p q + l∈δu\C 1 u log exp(R t l→u -υ)(p/q) + 1 exp(R t l→u -υ) + 1 5:
The output set is the union of C and the K -|C| set of nodes in V \C with the largest values of R

t f u .
The detailed derivation of the algorithm can be found in Appendix A. The derivation consists of two steps. First we establish a coupling between G t u , the t-hop neighbourhood of a node u of the graph and a specially constructed Galton-Watson (G-W) tree 1 T t u of depth t rooted on u. This coupling ensures that for a carefully chosen t = t f the neighbourhood G t f u of the node is a tree with probability tending to one as n → ∞ (i.e., with high probability (w.h.p)). The second step of the derivation involves deriving the recursions [START_REF] Billingsley | Probability and measure[END_REF] and [START_REF] Cai | Inference via message passing on partially labeled stochastic block models[END_REF] 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 of log-likelihoods R t f i . In the following section we derive the asymptotic distributions of the BP messages as the graph size tends to infinity, so as to quantify the error performance of the algorithm. 1 Detailed in Appendix A IV. ASYMPTOTIC ERROR ANALYSIS In this section we analyze the distributions of BP messages R t i→u given {σ i = 1} and given {σ i = 0} for i ∈ V \C. First, we derive a pair of recursive equations for the asymptotic distributions of the messages R t i→u given {σ i = 0, c i = 0} and given {σ i = 1, c i = 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 [START_REF] Montanari | Finding one community in a sparse graph[END_REF], which details the limitation of local algorithms.

Instead of studying R t i→u directly, we look at the loglikelihood ratios of the posterior probabilities of σ i given as

R t i = log P(σ i = 1|G t i , C t i , c i = 0) P(σ i = 0|G t i , C t i , c i = 0) and the associated messages R t i→u . By Bayes rule, R t i→u = R t i→u -υ, where υ = log P(σ i = 0|c i = 0) P(σ i = 1|c i = 0) = log n -K K(1 -α) .
It is worthwhile to note that our analysis of BP recursions proceeds in two steps. In the first step, we keep the parameters b, a constant and we take the limit where the graph size n goes to infinity. This helps us to apply the tree coupling result in Lemma 3 and establish a set of recursive distributional equations, the exact solutions to which will provide us with the limiting distribution of BP messages in the limit n → ∞. This result is given in Lemma 1. However, for finite degrees, this set of equations is difficult to solve and does not give any insight into the performance of our algorithm, although it can be solved by iterative methods. Therefore, in Proposition 1, we derive the limiting form of the distributions in the limit b → ∞. Letting b → ∞ facilitates the analysis by letting us use the CLT in Lemma 2 to arrive at a closed form expression of the distributions, which can in turn be used to show an error bound for BP given in Theorem 1.

Let ξ t 0 , ξ t 1 be rvs with the same distribution as the messages R t i→u given {σ i = 0, c i = 0} and given {σ i = 1, c i = 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.

Lemma 1 The random variables ξ t 0 and ξ t 1 satisfy the following recursive distributional equations with initial conditions

ξ 0 0 = ξ 0 1 = log (κ(1 -α)/(1 -κ)) . ξ (t+1) 0 D = h + L0c i=1 log(ρ) + L00 i=1 f (ξ (t) 0,i ) + L01 i=1 f (ξ (t) 1,i ) (9)
ξ (t+1) 1 D = h + L1c i=1 log(ρ) + L10 i=1 f (ξ (t) 0,i ) + L11 i=1 f (ξ (t) 1,i ), (10)
where D = denotes equality in distribution, h = -κ(a -b) -υ, ρ := p/q = a/b, and the function f is defined as

f (x) := log exp(x)ρ + 1 exp(x) + 1 . ( 11
)
The rvs ξ t 0,i , i = 1, 2, . . . are independent and identically distributed (iid) with the same distribution as ξ t 0 . Similarly ξ t 1,i , i = 1, 2, . . . are iid with the same distribution as

ξ t 1 . Fur- thermore, L 00 ∼ Poi((1 -κ)b), L 01 ∼ Poi(κb(1 -α)), L 10 ∼ Poi((1 -κ)b), L 11 ∼ Poi(κa(1 -α)), L 0c ∼ Poi(κbα) and L 1c ∼ Poi(κpα).
Proof: This follows from [START_REF] Billingsley | Probability and measure[END_REF] and the tree coupling in Lemma 3 of Appendix A.

We define a phase transition parameter for the detection problem in the presence of perfect side-information as:

λ α = K 2 (p -q) 2 (1 -α) 2 (n -K)q = κ 2 (a -b) 2 (1 -α) 2 (1 -κ)b , (12)
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 fixed.

Proposition 1 In the regime where λ α and κ are held fixed and a, b → ∞, we have

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

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

µ (t+1) = λ α α 1 -κ (1 -α) 2 κ + λ α E (1 -κ) κ(1 -α) + (1 -κ) exp(-µ (t) /2 -µ (t) Z) , (13)
where the expectation is taken w.r.t. Z ∼ N (0, 1).

Before providing a short sketch of the proof of the above proposition, we state a CLT for Poisson sums from [START_REF] Hajek | Recovering a Hidden Community Beyond the Spectral Limit in O(|E|log * |V |) Time[END_REF].

Lemma 2 [17, Lemma 11] Let S γ = X 1 + X 2 + . . . + X Nγ , where X i , for i = 1, 2, . . . N γ , are independent, identically distributed rv with mean µ, variance σ 2 and E(|X 3 i |) ≤ g 3 , and for some γ > 0, N γ is a Poi(γ) rv independent of X i : i = 1, 2, . . . , N γ . Then

sup x P S γ -γµ γ(µ 2 + σ 2 ) -Φ(x) ≤ C BE g 3 γ(µ 2 + σ 2 ) 3 ,
where Φ(x) = P(Z ≤ x), with Z ∼ N (0, 1) and C BE = 0.3041.

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:

ρ = a/b = 1 + λ α (1 -κ) (1 -α) 2 κ 2 b . (14)
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) e x 1 + e x - 1 2 (ρ -1) 2 ( e x 1 + e x ) 2 + O(b -3/2 ). (15)
We use these expansions to simplify the expressions for the means and variances of ( 9) and [START_REF] Chau | Detecting fraudulent personalities in networks of online auctioneers[END_REF]. Then, by a change of measure, we express them in terms of functionals of a single rv, ξ t 1 . We then use induction to show that the variance µ (t+1) satisfies the recursion [START_REF] Chen | Signal recovery on graphs: Variation minimization[END_REF] 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.

A. 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, S is the set of nodes with the top K -|C| beliefs. We are interested in bounding the expected number of misclassified nodes E(|S∆ S|). Let S be the output set of the algorithm excluding cues since the cues are always correctly detected. Note that |S|= | S|= K -|C|.

To characterize the performance of the detector, we need to choose a performance measure. In [START_REF] Montanari | Finding one community in a sparse graph[END_REF], a rescaled probability of success was used to study the performance of a subgraph detector without cues, defined as

P succ ( σ) = P(i ∈ S|i ∈ S) + P(i ∈ S|i ∈ S) -1, (16)
where σ i = 1(i ∈ S), and the dependence of P succ ( σ) on n is implicit. In our work, we study the following error measure, which is the average fraction of misclassified nodes, also considered in [START_REF] Hajek | Recovering a Hidden Community Beyond the Spectral Limit in O(|E|log * |V |) Time[END_REF], which for the uncued case is defined as

E := E(|S∆ S|) K .
Observe that 0 ≤ E ≤ 2.

In particular E = 2 if the algorithm misclassifies 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 algorithm always outputs K nodes as the subgraph, i.e., | S|= K, the following is true for any estimate σ of σ :

r n := n i=1 1( σ i = 0, i ∈ S) = n i=1 1( σ i = 1, i ∈ S), (17)
i.e., the number of misclassified subgraph nodes is equal to the number of misclassified nodes outside the subgraph. We can rewrite the error measure E in terms of r n , since

|S∆ S| K = 2r n K . ( 18
)
Next notice that we can rewrite P succ ( σ) as follows.

P succ ( σ) = 1 - 1 n n i=1 (P( σ i = 0|i ∈ S) + P( σ i = 1|i ∈ S)) (a) = 1 - n i=1 P( σ i = 0, i ∈ S) K + P( σ i = 1, i ∈ S) n -K (b) = 1 - E(r n ) K + E(r n ) n -K = 1 - nE(r n ) K(n -K) , (19)
where in step (a) we used Bayes rule with

P(i ∈ S) = K n . Since 1 ≤ n n-K ≤ 2, we get 1 -2E(r n )/K ≤ P succ ( σ) ≤ 1 -E(r n )/(K). (20)
Hence from ( 18) and ( 20), P succ ( σ) → 1 if and only if

E(|S∆ S|) K
→ 0. 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, lim b→∞ lim n→∞ E(|S∆ S|) K(1 -α) ≤ 2 1 -κ κ(1 -α) e -1 8 αλα(1-κ) κ(1-α) 2 . (21)
Consequently,

lim κ→0 lim b→∞ lim n→∞ E(|S∆ S|) K(1 -α) = 0.
Proof: Let S 0 be the MAP estimator given by

S 0 = i : R t i > log 1 -κ κ(1 -α) . ( 22
)
Since S is the set of nodes with the top K -|C| beliefs, we have either S ⊂ S 0 or S 0 ⊂ S. Therefore,

|S∆ S| ≤ |S∆ S 0 |+| S∆ S 0 | = |S∆ S 0 |+|K -|C|-| S 0 || = |S∆ S 0 |+||S|-| S 0 || ≤ 2|S∆ S 0 |, (23)
where the last step follows because the symmetric difference between two sets is lower bounded by the difference of their sizes. If we can bound E(|S∆ S0|) K(1-α) by one-half the expression in [START_REF] Kanade | Global and local information in clustering labeled block models[END_REF] the result of the Proposition follows. The proof of this upper bound uses Proposition 1 and is given in Appendix C. Theorem 1 states that the detectability threshold does not exist for BP with cues.

Note that Algorithm 1 is local until the last step of picking K -|C| nodes with the largest values of R t f i , which requires a fusion node to implement. However, as can be observed from ( 22) and ( 23), the statement about the error performance remains true even for a local version of this algorithm where each node independently employs a suitable thresholding of the final belief R t f i . In conclusion, a local algorithm consisting of BP followed by thresholding of the beliefs is sufficient to get close to the maximum-likelihood algorithm's performance. 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 [START_REF] Montanari | Finding one community in a sparse graph[END_REF], the performance of any local algorithm suffers when the parameter λ < 1/e. Thus, there is a discontinuity in the performance of BP in the sense that when α > 0, a sharp threshold that exists in the absence of side-information disappears.

In the following LOC denotes the class of all local algorithms, i.e., algorithms that take as input the local neighbourhood of a node.

V. 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 classfied data available for many semisupervised learning problems.

Our BP algorithm can easily take into account imperfection in side information. Suppose we know the parameters α and β defined 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:

R t u = log P(G t u , c u , C t u |σ u = 1) P(G t u , c u , C t u |σ u = 0)
, where c u is the indicator variable of whether u is a cued node, and C t u is the cued information of the t-hop neighbourhood of u, excluding u. Note that we can expand R t u as follows

R t u = log P(G t u , C t u |σ u = 1, c u ) P(G t u , C t u |σ u = 0, c u ) + log P(c u |σ u = 1) P(c u |σ u = 0) = log P(G t u , C t u |σ u = 1) P(G t u , C t u |σ u = 0) + log P(c u |σ u = 1) P(c u |σ u = 0) , ( 24
)
where in the second step we dropped the conditioning w.r.t. c u because (G t u , C t u ) is independent of the cue information of node u given σ u . Let h u = log P(cu|σu=1) P(cu|σu=0) . Then it is easy to see from (3) that

h u =    log β(1-κ) (1-β)κ , if u ∈ C, log (1-αβ)(1-κ) (1-κ-ακ+ακβ) , otherwise. ( 25
)
Algorithm 2 BP with imperfect cues 1: Initialize: Set R 0 i→j to 0, for all (i, j) ∈ E. Let t f < log(n) log(np) + 1. Set t = 0. 2: For all directed pairs (i, u) ∈ E:

R t+1 i →u = -K(p -q) + h i + l∈δi,l =u log exp(R t l→i -ν)(p/q) + 1 exp(R t l→i -ν) + 1 , (26)
where ν = log( n-K K ).

R t+1 u = -K(p -q) + h u + l∈δu log exp(R t l→u -ν)(p/q) + 1 exp(R t l→u -ν) + 1 5: Output S as K set of nodes in V with the largest values of R t f u .
The recursion for the first term in ( 24) can be derived along the same lines as the derivation of Algorithm 1 and is skipped.

The final BP recursions are given in Algorithm 2.

In order to analyze the error performance of this algorithm we derive the asymptotic distributions of the messages R t u→i , for {σ u = 0} and {σ u = 1}. Note that, since we now assume that we do not know the exact classification of any of the subgraph nodes, we need to detect K nodes, and hence the phase transition parameter is defined as

λ = K 2 (p -q) 2 (n -K)q . ( 28
)
The following proposition presents the asymptotic distribution of the messages R t u→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 message R t u→i given {σ u = j}, where j = {0, 1} converges in distribution to Γ t j +h u where h u is defined in [START_REF] Mezard | Information, physics, and computation[END_REF]. The rvs Γ t j have the following distribution:

Γ t 0 ∼ N (-µ (t) /2, µ (t) ), and Γ t 1 ∼ N (µ (t) /2, µ (t) ),
where µ (t) satisfies the following recursion with µ (0) = 0,

µ (t+1) = αβ 2 λE (1 -κ)/κ β + (1 -β)e (-µ (t) /2- √ µ (t) Z) + (1 -αβ) 2 λ E (1 -κ) κ(1 -αβ) + (1 -κ -ακ + ακβ)e (-µ (t) /2- √ µ (t) Z) , (29)
and the expectation is w.r.t. (with respect to) 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.

Theorem 2 For any λ > 0, α > 0, β > 0,

lim b→∞ lim n→∞ E(| Ŝ∆S|) K ≤ 2 α β(1 -β) + (1 -αβ)( 1 -κ κ -α(1 -β)) e -λαβ 2 (1-κ) 8κ
.

Consequently,

lim κ→0 lim b→∞ lim n→∞ E(|S∆ S|) K = 0.
Proof: The proof essentially analyzes the properties of the recursion [START_REF] Montanari | Finding one community in a sparse graph[END_REF] and is similar to the proof of Theorem 1. See supplementary material for details. Note on number of steps for asymptotic weak recovery: It is worthwhile to note that, while running BP for t f number of steps, where t f is defined in Algorithms 1 and 2 leads to improved error performance, in order to get asymptotic weak recovery, it is sufficient to run BP for one step. This follows because the error bounds we derived in Theorems 1 and 2 rely on a lower bound on the asymptotic mean of the messages µ (t) , which is valid for any t > 0, specifically for t = 1.

VI. NUMERICAL EXPERIMENTS

In this section we provide numerical results to validate our theoretical findings 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 [START_REF] Andersen | Detecting sharp drops in PageRank and a simplified local partitioning algorithm[END_REF].

A. Synthetic dataset

First we show that the limitation of local algorithms described in Proposition 2 is overcome by BP when there is nontrivial 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 = 10 6 . 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 In the figure, we also plot the error rate E obtained by personalized PageRank under the same setting, with damping factor α pr = 0.9 [START_REF] Andersen | Detecting sharp drops in PageRank and a simplified local partitioning algorithm[END_REF]. The figure demonstrates that BP benefits 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 [START_REF] Montanari | Finding one community in a sparse graph[END_REF] to our algorithm with varying amounts of side-information. We choose the setting where n = 10 4 , b = 140 and κ = 0.033 for different values of λ by varying p. In Figure 2 we plot the metric E against λ for different values of β, with α = 0.1. For β = 1 we use Algorithm 1. We can see that even BP with noisy sideinformation performs better than standard BP with no sideinformation. In addition, as expected increasing β improves the error performance.

Finally, we note that as observed in the previous section, in terms of asymptotic error performance in the presence of side-information, even BP run for a single step achieves asymptotically zero error. In order to assess the performance of BP when run for more than one step, we simulated a case where n = 10 4 ,κ = 0.01, b = 100 and λ = 1/2 with α = .05 and β = 1. In Figure 3, we plot the error E for up to 3 steps of BP. Clearly, the performance of BP for only one step is quite unsatisfactory. This finding makes a case for running BP for more than one step. In the future, we hope to correctly characterize the error improvement when BP is run for more than one step.

B. 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 defined as

R = |S ∩ Ŝ| |S| ,
where S is the true community and Ŝ is its estimate. This is a commonly used metric for community detection applications [START_REF] Yang | Defining and evaluating network communities based on ground-truth[END_REF]. We use α pr = 0.9 as the damping factor of PageRank. We 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 [START_REF] Zhou | Learning with local and global consistency[END_REF]. 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 defined 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 4). It can be seen from Figure 4, 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 Community index 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 [START_REF] Chen | Dense subgraph extraction with application to community detection[END_REF]. It is made up of words from all news released by Reuters for 66 days since September 11, 2001. Table 5 in [START_REF] Chen | Dense subgraph extraction with application to community detection[END_REF] shows a group of 99 collocated words in this dataset.This subset represents the largest dense community to be detected in this dataset with an average degree of 520 while the average degree of nodes outside this subgraph is 18.48. 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, with node degrees 432 and 43 respectively. In Figures 5,6, we provide for illustrative purposes, the histogram of the degrees inside the subgraph and outside the subgraph respectively. In Table I

VII. CONCLUSIONS AND FUTURE EXTENSIONS

In this work we developed a local distributed BP algorithm that takes advantage of side-information to detect a dense subgraph embedded in a sparse graph. We obtained theoretical results based on density evolution on trees to show that it achieves zero asymptotic error regardless of the 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.

An intuition why the side information we consider is so effective is that it provides global knowledge of the subgraph location, in addition to the local information available to the BP algorithm. Our results are also in line with the similar drastic improvements brought about by side-information in local community detection in other models as reported in [START_REF] Kanade | Global and local information in clustering labeled block models[END_REF], [START_REF] Zhang | Phase transitions in semisupervised clustering of sparse networks[END_REF].

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.

It is also important to note that the BP algorithm overcomes the 1/e barrier because the fraction of cued nodes α is strictly positive. This naturally leads one to a question for the future on whether there is a critical rate for α → 0 above which local algorithms with cued nodes continue to perform as well as maximum-likelihood detection.

Finally, we would like to note that the simple SBM graph used in this paper is not often a good fit for graphs encountered in practice. There exist several modifications of the SBM in the literature such as the degree-corrected SBM [START_REF] Qin | Regularized spectral clustering under the degree-corrected stochastic blockmodel[END_REF] and the Random Intersection Model [START_REF] Chen | Phase transitions in spectral community detection[END_REF]. Generative models like SBM provide a good analytical platform for studying the impact of side-information on community detection algorithms, and can lead to the study of more realistic models in the future.

i∈δu log P(T t i , c i , C t i |τ u = 1) P(T t i , c i , C t i |τ u = 0) , (32)
by the independence property of subtress T t i rooted on i ∈ δu. Since by Lemma 3, the degrees are Poisson,

P(N u |τ u = 1) = d Nu 1 e -d1 /N u ! ,
and similarly for P(N u |τ u = 0). Therefore we have log P(N u |τ u = 1)

P(N u |τ u = 0) = N u log d 1 d 0 -(d 1 -d 0 ) = N u log d 1 d 0 -K(p -q). ( 33
)
Next we look at the second term in [START_REF] Rohe | Spectral clustering and the highdimensional stochastic blockmodel[END_REF]. We analyze separately the case of c i = 1 and c i = 0 for i ∈ δ u , i.e, the cued and uncued children are handled separately. Case 1 ( c i = 1): We have

log P(T t i , c i , C t i |τ u = 1) P(T t i , c i , C t i |τ u = 0) (a) = log P(T t i , c i , C t i , τ i = 1|τ u = 1) P(T t i , c i , C t i , τ i = 1|τ u = 0) = log P(T t i , c i , C t i |τ i = 1)P(τ i = 1|τ u = 1) P(T t i , c i , C t i |τ i = 1)P(τ i = 1|τ u = 0) (b) = log Kp/d 1 Kq/d 0 , (34)
where in step (a) we applied the fact that c i = 1 implies τ i = 1, and in (b) we used (30). Case 2 (c i = 0): Observe that P(c i = 0|τ i = 1) = 1 -α and P(c i = 0|τ i = 0) = 1. Note that

P(T t i , c i , C t i |τ u = 1) = P(T t i , C t i |τ i = 1)P(c i |τ i = 1)P(τ i = 1|τ u = 1) + P(T t i , C t i |τ i = 0)P(c i |τ i = 0)P(τ i = 0|τ u = 1) = P(T t i , C t i |τ i = 1)(1 -α) Kp d 1 + P(T t i , C t i |τ i = 0) (n -K)q d 1 . (35)
Similarly, we can show

P(T t i , c i , C t i |τ u = 0) = P(T t i , C t i |τ i = 1) Kq d 0 (1 -α) + P(T t i , C t i |τ i = 0) (n -K)q d 0 . (36)
Let us define

Λ t i→u := log P(T t i , C t i |τ i = 1) P(T t i , C t i |τ i = 0)
, the message that i sends to u at step t. Using the above definition, [START_REF] Yang | Defining and evaluating network communities based on ground-truth[END_REF], and (36) we get

log P(T t i , c i , C t i |τ u = 1) P(T t i , c i , C t i |τ u = 0) = log e Λ t i→u Kp d1 (1 -α) + (n-K)q d1 e Λ t i→u Kq d0 (1 -α) + (n-K)q d0 = log d 0 d 1 + log e Λ t i→u Kp (n-K)q (1 -α) + 1 e Λ t i→u K (n-K) (1 -α) + 1 . (37)
We then use the substitution ν := log((n -K)/K) in the above equation. Finally combining [START_REF] Smith | Bayesian discovery of threat networks[END_REF], [START_REF] Wang | Local-set-based graph signal reconstruction[END_REF] and [START_REF] Zhou | Learning with local and global consistency[END_REF] and replacing Λ t u with R t u and Λ t i→u with R t i→u , we arrive at [START_REF] Cai | Inference via message passing on partially labeled stochastic block models[END_REF]. The recursive equation ( 7) can be derived in exactly the same way by looking at the children of i ∈ δu.

log(ρ) = log(1 + (ρ -1)) = λ α (1 -κ) (1 -α) 2 κ 2 b - λ α (1 -κ) 2(1 -α) 2 κ 2 b + O(b -3/2 ), (41)
and

log 2 (ρ) = λ α (1 -κ) (1 -α) 2 κ 2 b + O(b -3/2 ). (42)
Let us verify the induction result for t = 0. Using the recursion (9) with ξ 0 0 = log κ(1-α) 1-κ = -υ, we can express Eξ 1 0 as

Eξ 1 0 = -κb(ρ -1) -υ + κbα log(ρ) + b(1 -κα)f (-υ).
Now using (39) and (41) we obtain

Eξ 1 0 = -κ λ α b(1 -κ) (1 -α) 2 κ 2 -υ + κα λ α (1 -κ)b (1 -α) 2 κ 2 (43) - λ α (1 -κ)α 2(1 -α) 2 κ + λ α (1 -κ)b (1 -α) 2 κ 2 κ(1 -α) - λ α (1 -κ) 2(1 -κα) + O(b -1/2 ) = -υ - λ α (1 -κ) 2(1 -α) 2 κ α - λ α (1 -κ) 2(1 -κα) + O(b -1/2 ). ( 44
)
We also obtain, using the formula for the variance of a Poisson random variable

Varξ 1 0 = log 2 (ρ)κbα + f 2 (-υ)(1 -κ)b + f 2 (-υ)κb(1 -α) (a) = λ α α(1 -κ) (1 -α) 2 κ + (1 -κ)λ α 1 -κα + O(b -1/2 ), (45)
where in (a) we used (42) and (40). Comparing (44) and (45), 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 ξ 1 0 -h as the Poisson sum of iid mixture random variables as follows By Lemma 2, taking b → ∞ we obtain the convergence to Gaussian.

ξ 1 0 -h = L0 i=1 X i , where
Having shown the induction hypothesis for t = 0, we now assume it holds for some t > 0. By using [START_REF] Chen | Dense subgraph extraction with application to community detection[END_REF], (15) and

Now we take the expectation of both sides of ( 9) and [START_REF] Chau | Detecting fraudulent personalities in networks of online auctioneers[END_REF]. Using the fact that E L i=1 X i = EX i EL if L ∼ Poi and X i are independent and identically distributed (iid) rv, we obtain 1 σi = σi = n(P(c i = 0, σ i = 0)P(R t i > υ|c i = 0, σ i = 0) + P(c i = 0, σ i = 1)P(R t i < υ|c i = 0, σ i = 1)),

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

By Proposition 1 we have

lim b→∞ P(ξ t 1 ≤ 0) = Q 1 µ (t) µ (t) 2 -log (1 -κ) κ(1 -α)
where Q(•) denotes the standard Q function. Notice that by [START_REF] Chen | Signal recovery on graphs: Variation minimization[END_REF] we have that µ (t) ≥ λ α α(1 -κ)/(κ(1 -α) 2 ), since ≥ 0. In addition, by (55), µ (t) ≤ λα(1-κ) κ(1-α) 2 . Note that the lower bound on µ (t) is not useful when α = 0. Therefore by using the Chernoff bound for the Q function, Q(x) ≤ 1 2 e -x 2 /2 , we get

lim b→∞ P(ξ t 1 ≤ 0) ≤ 1 2 e -1 2µ (t) ( µ (t) 2 -log( 1-κ κ(1-α) )) 2 = 1 2 e -µ (t) 8 (1-2 µ (t) log( 1-κ κ(1-α) )) 2 ≤ 1 2 e -µ (t) 8 e 1 2 log( 1-κ κ(1-α) ) = 1 2 1 -κ κ(1 -α) e -µ (t) 8 , (61)
where we used the fact that (1 -x) 2 ≥ 1 -2x for any x > 0.

By employing similar reductions, we can show Then using [START_REF] Koutra | Unifying guilt-by-association approaches: Theorems and fast algorithms[END_REF] we get the desired result in [START_REF] Kanade | Global and local information in clustering labeled block models[END_REF] .

Proposition 2 [ 29 ,

 229 Theorem 1] If λ < 1/e, then all local algorithms have success probability uniformly bounded away from one; in particular,

Fig. 1 :

 1 Fig. 1: Performance of BP Algo 1 as a function of α

2 1 Fig. 2 :Fig. 3 :

 123 Fig. 2: Comparison of BP for subgraph detection for different amounts of side-information

Fig. 4 :Fig. 5 :

 45 Fig. 4: Comparison of BP for subgraph detection for different amounts of side-information

Fig. 6 :

 6 Fig. 6: Histogram of the degrees of the nodes outside the target subgraph in the Reuters graph Class 0 #of cues = 1 #of cues = 2 BP 0.7143 0.7216 PageRank 0.6327 0.6392

  L 0 ∼ Poi(b), and L(X i ) = καL(log(ρ))+ (1κ)L(f (-υ)) + (κ(1 -α))L(f (-υ)), keeping in mind the independent splitting property of Poissons, where L denotes the law of a rv3 . Next we calculate E(|X i | 3 ). It is easy to show using (39) and (41) that(46) E(|X i | 3 ) = κα log 3 (b) + (1 -κα)|f 3 (-υ)|= O(b -3/2 ).Therefore the upper bound of Lemma 2 with λ = b becomesC BE E(|X i | 3 ) γ(µ 2 + σ 2 ) 3 = O(b -3/2 ) bΩ(b -3 ) = O(b -1/2 ).

3

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

e ξ t 1 1 + e ξ t 1 - (ρ - 1 ) 2 2 E e 2ξ t 1 ( 1 + e ξ t 1 ) 2 +e ξ t 1 -E e ξ t 1 ( 1 + e ξ t 1 ) 2 +

 1112111211112 O(b -3/2 ), and by using Lemma 4 in addition we obtainEf (ξ t 0 ) = (ρ -1) (ρ -1) 2 κ(1 -α) 2(1 -κ) O(b -3/2 ).

1 + e ξ t 1 -ξ t 1 ( 1 + e ξ t 1 ) 2 +ξ t 1 1 + e ξ t 1 - (ρ - 1 ) 2 2 E e 2ξ t 1 ( 1 + e ξ t 1 ) 2 +E e ξ t 1 1 + e ξ t 1 +ξ t 1 1 + e ξ t 1 +

 111112111211121111 (49) E(ξ t+1 0 ) = h + logp q κbα + E f (ξ t 0 ) (1 -κ)b + E f (ξ t 1 ) κb(1 -α) and (50) E(ξ t+1 1 ) = h + log p q κaα + E f (ξ t 0 ) (1 -κ)b + E f (ξ t 1 ) κa(1 -α). We now substitute (48) and (47) in (49) to get:E(ξ t+1 0 ) = h + κbα log(ρ) + (1 -κ)b (ρ -1) κ(1 -α) 1 -κ E 1 (ρ -1) 2 κ(1 -α) 2(1 -κ) E e O(b -3/2 ) + κb(1 -α) (ρ -1)E e O(b -3/2 ) ,which on simplifying and grouping like terms givesE(ξ t+1 0 ) = h + κbα log(ρ) + κ(a -b)(1 -α) -λ α (1 -κ) 2(1 -α)κ O(b -1/2 ). Substituting h = -κ(a -b) -log 1-κ κ(1-α) , we get E(ξ t+1 0 ) = -log 1 -κ κ(1 -α) -ακ(a -b) + κbα log(ρ) -λ α (1 -κ) 2κ(1 -α) E e O(b -1/2 ).Using (41) we get as a, b → ∞, with zero mean and finite variance, from the standard CLT, we can conclude that the distribution tends to N (0, µ t+1 ). The argument for ξ t+1 1 is identical.APPENDIX C FINISHING THE PROOF OF THEOREM 1Proof: We bound E(|S∆ S 0 |)/(K(1 -α)) as follows:

  α)+(1-κ) exp(-µ/2-√ µZ)

  ) and (62) back in (59) and using the fact that µ(t) ≥ λ α α(1 -κ)/(κ(1 -α) 2 ), we get lim b→∞ lim n→∞ E(|S∆ S 0 |) K(1 -α) ≤ 1 -κ κ(1 -α) e -λα α(1-κ)8κ(1-α) 2 .

  3: Increment t; if t < t f -1 go back to 2, else go to 4 4: Compute R

	t f u for every u ∈ V as follows:
	(27)

  we show the recall values R of PageRank and BP, excluding cues. Clearly, BP performs better.

TABLE I :

 I Reuters911 recall results

Under the assumptions of Lemma

we can construct a Poisson tree identical to the t-hop neighbourhood of a given node. In addition, it can be concluded from the Lemma that all the subtrees of this tree are nonoverlapping and hence independent.

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 Indo-French CEFIPRA Collaboration Grant No.5100-IT1 "Monte Carlo and Learning Schemes for Network Analytics." We would like to thank Bruce Hajek for very useful comments that helped to improve this paper.

APPENDIX 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 G t u of node u and a Galton-Watson (G-W) tree rooted at u constructed as follows. Let T t u be a labelled Galton-Watson (G-W) tree of depth t rooted at node u constructed as follows (as in [START_REF] Hajek | Recovering a Hidden Community Beyond the Spectral Limit in O(|E|log * |V |) Time[END_REF]): The label τ u at node u is chosen at random in the following way:

The number of children N u of the root u is Poisson-distributed with mean d 1 = Kp + (n -K)q if τ u = 1 and mean d 0 = 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/d 1 if τ u = 1 and Kq/d 0 if τ u = 0. Similarly τ i = 0 w.p. (n-K)q/d 1 and (n-K)q/d 0 for τ u = 0 and 1 respectively. Namely, if i is a child of u,

We then assign the cue indicator function c such that c i = 1 w.p. α if τ i = 1 and c i = 0 if τ i = 0. The process is repeated up to depth t giving us C t u , the set of cued neighbours. Now we have the following coupling result between (G t u , σ t , C t u ), the neighbourhood of u and the node labels of that neighbourhood and (T t u , τ t , C t u ), the depth-t tree T t u and its labels due to [START_REF] Hajek | Recovering a Hidden Community Beyond the Spectral Limit in O(|E|log * |V |) Time[END_REF].

Lemma 3 [17, Lemma 15] For t such that (np) t = n o (1) , there exists a coupling such that (G t u , σ t , C t u ) = (T t u , τ t , C t u ) with probability 1-n -1+o (1) , where equality of graphs means that the GW tree T t u is identical in topology to G t u with node labels τ t and cues C t u identical to σ t and Ct u , respectively.

We now derive the recursions for the likelihood ratios on the tree T t u . For large n with high probability, by the coupling formulation, R t u 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 C t u , just as for the original graph. We use Λ t u to denote the likelihood ratio of node u computed on a tree defined as below:

.

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

Since the statistical properties of R t u and Λ t u are the same in the n → ∞ limit, we analyze the distribution of Λ t u . Let us define the posterior likelihood for τ u given by

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 {c i = 0}. By a slight abuse of notation, let ξ t 0 and ξ t 1 denote the rvs whose distributions are the same as the distributions of Λ t i given {c i = 0, τ i = 0} and {c i = 0, τ i = 1} respectively in the limit n → ∞. We need a relationship between P 0 and P 1 , the probability measures of ξ t 0 and ξ t 1 respectively, stated in the following lemma.

In other words for any integrable function g(•)

Proof: Following the logic in [START_REF] Montanari | Finding one community in a sparse graph[END_REF], we show this result for g( Λ t u ) = 1( Λ u ∈ A), A being some measurable set. The result for general g then follows because any integrable function can be obtained as the limit of a sequence of such rvs [START_REF] Billingsley | Probability and measure[END_REF]. Let Y = (T t u , C t u ), the observed rv. Therefore

where in (a) we used the fact that P(τu=0|Y ) P(τu=1|Y ) = exp(-Λ t u ), and E 1 denotes expectation conditioned on the event {τ u = 1}.

Proof: Since λ α and κ are fixed and b → ∞, from [START_REF] Chen | Phase transitions in spectral community detection[END_REF] we have

Following [START_REF] Montanari | Finding one community in a sparse graph[END_REF], we prove the result by induction on t. First let us verify the result holds when t = 0, for the initial condition that ξ 0 0 = ξ 0 1 = -υ. We only do this for ξ t 0 since the steps are similar for ξ t 1 . Observe that

where (a) follows from [START_REF] Zhu | Semi-supervised learning using gaussian fields and harmonic functions[END_REF], and Taylor's expansion around ρ = 1. Similarly,

-ακ(a -b)

Finally we obtain (51)

Using exactly the same simplifications we can get (52)

Our next goals are to compute var(ξ t+1 0 ) and var(ξ t+1 1 ). Towards this, observe that

and using Lemma 4 the above becomes

Now we use the formula for the variance of Poisson sums Var

.

Using µ (t+1) of ( 55) in ( 51) and ( 52) we get

Now we use the fact the induction assumption that ξ t 1 → N (E(ξ t 1 ), µ (t) ). Since the function e ξ t 1 /(1 + e ξ t 1 ) is bounded, by Lebesgue's dominated convergence theorem [START_REF] Billingsley | Probability and measure[END_REF]Theorem 16.4]

, where Z ∼ N (0, 1). Therefore we obtain

.

Substituting the above into (55) gives us the recursion for µ (t+1) given in [START_REF] Chen | Signal recovery on graphs: Variation minimization[END_REF].

Next we prove Gaussianity. Consider

Let us look at the second term. Let X i = f (ξ t 0,i )-Ef (ξ t 0,i ). Then it can be shown that

where δ ≤ |L 00 -EL 00 |+1, where the extra 1 is because EL 00 may not be an integer. Therefore

. Thus, we can replace the Poisson upper limits of the summations in the second and third terms of (57) by their means, leading to

where o p (1) indicates a rv that goes to zero in probability in the limit. The combined variance of all other terms approaches µ (t+1) , defined in [START_REF] Chen | Signal recovery on graphs: Variation minimization[END_REF], as b → ∞ and it is finite for a fixed t. Now since we have an infinite sum of independent rvs