Understanding the Success of Graph-based Semi-Supervised Learning using Partially Labelled Stochastic Block Model

1 Introduction

In several practical learning scenarios - e.g., e-commerce, genomics, image search, speech recognition and natural language processing - out of the large number of available instances, only a handful are typically labelled. The cost associated with labelling necessitates employing semi-supervised learning (SSL) in such cases. Graph-based SSL (G-SSL) is an influential approach to SSL that seeks to exploit homophily [McPherson et al., 2001]), in order to estimate the labels of the unlabelled instances. First introduced in [Zhu et al., 2003], and subseauently popularised in [Zhu, 2005], Label Propagation (LP), enjoyed widespread empirical success in G-SSL and sparked a series of extensions: [Talukdar and Crammer, 2009], [Chakrabarti et al., 2014], [Stretcu et al., 2019].

Sadly, theoretical understanding of the efficacy of these algorithms has been lacking. Till date, to the best of our knowledge, only [Yamaguchi and Hayashi, 2017] attempts to characterise the performance of LP, by proving equivalence with the problem of community recovery in PLSBM, an extension of the Stochastic Block Model (SBM) [Abbe et al., 2015] to the case of partially-labelled graphs. However, beyond equivalence, [Yamaguchi and Hayashi, 2017] does not quantify the efficacy in terms of well-understood notions of predictive performance, such as accuracy. We address this gap by noting an equivalence between the notion of accuracy and that of community recovery [Abbe and Sandon, 2015; Ke and Honorio, 2018]. Moreover, we characterise the conditions on graph structure, volume and quality of available labels that lead to upper- and lower-bounds on accuracy for LP.

∗Equal contribution

Our contributions are listed below (see Table 1 for a quick reference):

• We extend the notion of success and failure beyond equivalence ([Yamaguchi and Hayashi, 2017]) by connecting it to 100% accuracy, ≥ 100(1 - ϑ)% accuracy, and ≤ 100(1 - δ)% accuracy, respectively, for arbitrary ϑ, δ ∈ (0, 1). See §3.2 for details.
• We characterise the condition on graph structure, label volume and quality, that leads to ≤ 100(1 - δ)% accuracy by connecting it to the notion of failure of recovery ([Ke and Honorio, 2018]) (§4).
• We state similar necessary conditions that lead to 100% accuracy by connecting it to the notion of exact recovery ([Saad and Nosratinia, 2018]) (§5).
• We state a well-positioned conjecture on similar necessary conditions that lead to 100(1 - ϑ)% accuracy by connecting it to the notion of partial recovery ([Yun and Proutiere, 2014]), for the case of ϑ = s/n, where s = o(n) (§6).
• We extend the failure of recovery result obtained in [Ke and Honorio, 2018] to the case of partially-labelled SBM with K ≥ 2. See Theorem 2.
• We provide extensive experimental evidence support the theory (including the conjecture) on synthetic partiallylabelled graphs. See §7 for details.

Proofs and additional experimental evidences are available in the supplementary material 1 .

1 See following URL: http://bit.ly/PLSBM IJCAI20

[Saad and Nosratinia, 2018] 4

2 Background

We begin by recounting the equivalence theorem derived in [Yamaguchi and Hayashi, 2017].

Let (A,X) denote a partially-labelled graph on n nodes, [n], where the first nl nodes, [nl], carry a label in [K]. X ∈ {0, 1}n×K denotes the labels on nodes, when available. For nodes i ∈ [nl], Xi is the one-hot representation of the corresponding label xi ∈ [K], whereas for the unlabelled nodes, j ∈ [n] \ [nl], Xj = 0 (0 denotes the Kdimensional zero vector). A ∈ {0, 1}n×n denotes the adjacency matrix, where Ai,j = 1 indicates the presence of edge between nodes i and j (we assume that there are no selfloops: Ai,i = 0, ∀i ∈ [n]). Graph-based semi-supervised learning (G-SSL) attempts at recovering the label, ̂X, of the hitherto unlabelled nodes, [n] \ [nl].

2.1 Discrete Label Propagation

Definition 1 (DLP [Yamaguchi and Hayashi, 2017]). DLP estimates the true labels of the nodes, ̂ XDLP ∈ {0, 1}n×K , as a solution to the following (combinatorial) optimisation problem:

A relaxation, Y ∈ [0, 1]n×K , and a subsequent rounding leads to the original Label Propagation algorithm [Zhu, 2005]. It is worth noting that the solution to LP, ̂ XLP ∈ {0, 1}n×K , is a worse optimiser of Equation 1 than ̂ XDLP because of the intermediate relaxation and rounding.

2.2 Partially-Labelled Stochastic BlockModel

Definition 2 (PLSBM [Yamaguchi and Hayashi, 2017]). PLSBM(n, nl, α, K, Q) posits a generative model over the family of partially-labelled graphs, (A,X), defined as follows:

1. Each node i ∈ [n] is assigned a label, xi ∈ [K], (corresponding to its community membership) with uniform probability 1/K, yielding a set of balanced communities in expectation 2 .

2 PLSBM is typically defined with xi ∼Mult(· | γ), i.i.d. However, the restricted notion with γ = 1/K1 suffices for the present work.

4

4

2� (m-ary SBM)

1. The entries of the adjacency matrix, A, are generated i.i.d., with Pr(Ai,j = 1 | xi, xj) = Qxi,xj , where Q ∈ (0, 1)K×K is a symmetric matrix. In other words, Ai,j | X ∼ Bern(·|Qxi,xj ), i.i.d..
2. For the nodes in [nl], (potentially noisy) labels, x′ ∈ [K], are revealed i.i.d. as follows: Pr(x′i = xi) = 1-α and Pr(x′i = j) = α K-1 , ∀j ̸= xi. The rest of the nodes, indexed {nl +1, · · · , n} remain unlabelled.

In §4, §5, §6, we use another equivalent formulation of PLSBM ([Saad and Nosratinia, 2018]), PLSBM(n, ϵl, α,K,Q), with the following modification: instead of revealing the label of the nodes in [nl], we reveal labels (with or without noise, as before) for each node in [n] with probability ϵl. With ϵl = nl n , in expectation, labels for nl nodes are revealed under PLSBM(n, ϵl, α, K, Q).

Given (A,X′ ) ∼ PLSBM(n, nl, α,K,Q), we let ̂ XMAP = arg maxX Pr(X|A, X′ ; ϵl, α, Q) denote the MAP estimate of the (latent) membership vector X (obtained through an inference procedure such as variational EM [Yamaguchi and Hayashi, 2017]). Similarly, we let ̂ XMLE = arg maxX Pr(X,A,X′ ; ϵl, α,Q) denote the corresponding MLE estimate. Following [Abbe et al., 2015], we note that ̂ XMAP = ̂ XMLE, when γ = 1/K1.

2.3 Equivalence of DLP and PLSBM

The following result builds a bridge between the two seemingly disparate disciplines of graph-based semi-supervised learning and graph generative models:

Theorem 1 ([Yamaguchi and Hayashi, 2017]). Given a realisation (A,X′ ) ∼ PLSBM(n, nl, α,K, µI + ν(11T - I)), and number of nodes in each cluster, nk, ∀k ∈ [K], ̂ XDLP (λ) = ̂ XMAP (α, µ, ν), if the following conditions hold:

1. If λ > 0, then µ > ν; else if λ < 0, then µ < ν; else if λ = 0, then µ = ν; and

Discussion. It is not hard to see that Theorem 1 holds for PLSBM(n, ϵl, α,K,Q) as well, since the log-likelihood is identical to that of PLSBM(n, nl, α,K,Q), barring a constant. This extension of Theorem 1, with ̂ XMAP substituted with ̂ XMLE, will be used in the subsequent sections (§4, §5, §6).

In what follows, we strengthen Theorem 1 by further connecting the notion of recovery in the context of community detection (see §3.1) to that of accuracy in the graph-based semi-supervised learning (see §3.2). §3.3 provides an outline of the theoretical results we have obtained.

3 Preparation

We begin with a brief refresher of the relevant definitions from the literature ([Abbe and Sandon, 2015] and [Saad and Nosratinia, 2018]) on the recovery of communities.

3.1 Recovery of Communities in PLSBM

Exact Recovery

The correct community memberships for all the nodes must be inferred with probability tending to 1 as n → ∞ in order to attain exact recovery. In other words, limn→∞Pr(X = ̂X) = 1, where the probability is defined by the generative model of PLSBM(n, ϵl, α, K, Q).

[Saad and Nosratinia, 2018] furnishes exact recovery results under a more general generative model of partiallylabelled graphs (m-ary side information) for K = 2, which we adapt in §5 to the case of PLSBM.

Partial Recovery

The correct community membership for at least s nodes must be inferred with probability tending to 1 as n → ∞ in order to attain partial recovery. In other words, limn→∞Pr(ℓ0-1 (X, ̂X) ≤ s/n) = 1, where ℓ0-1 (X, ̂X) = 1n ∑i∈[n] 1{xi̸=ˆxi} is the usual 0-1 loss counting the fraction of errors. To the best of our knowledge, no result exists for the partially-labelled graphs that we study. [Yun and Proutiere, 2014] furnishes a partial recovery result for the SBM with K = 2, when s = o(n). We dwell upon this topic in §6, where we put forth a well-reasoned conjecture based on this result.

Failure of Recovery

The correct community membership of at least 100(1 - δ)% of the nodes (in expectation) must be incorrectly inferred in order to attain failure of recovery, for any given δ ∈ [0, 1]. In other words, for every node Pr( ̂ xi ̸= xi) ≥ δ. [Ke and Honorio, 2018] studies failure of recovery from an informationtheoretic perspective and derives algorithm-agnostic results for SBMwith K = 2. In §4, we refine the result for partiallylabelled graphs (PLSBM) and extend it to the case of K ≥ 2. We refer the interested reader to [Abbe, 2017] for a comprehensive survey on this topic, in addition to the above works.

3.2 Success and Failure of G-SSL

We now connect the notion of accuracy in the G-SSL parlance to that of recovery in community detection, and lend precise definitions to the notions of its success and failure:

Total success. It is easy to see that exact recovery leads to 100% accuracy - this is the strongest possible notion of success for G-SSL. Note that this guarantee on accuracy only holds with probability tending to 1 as n → ∞.

Partial success. Since partial recovery places an upperbound on the 0-1 loss, ℓ0-1 (X, ̂X) ≤ s/n, it leads to a lowerbound, 100(1 - sn )%, accuracy. Note that this guarantee on accuracy only holds with probability tending to 1 as n → ∞.

Failure. Failure to recover, guaranteeing Pr( ̂ xi ̸= xi) ≥ δ, ∀i ∈ [n], puts a lower-bound on the 0-1 loss, ℓ0-1 (X, ̂X) ≥ δ in expectation. Therefore, it translates to an upper-bound of 100(1 - δ)% on accuracy. Note that this guarantee holds in expectation, irrespective of the value of n.

3.3 Outline of the Theoretical Results

In what follows, we connect the three notions of recovery (§3.1) to the corresponding notions of accuracy (§3.2). §4 employs information-theoretic tools deployed in [Ke and Honorio, 2018] to prove an algorithm-agnostic nonasymptotic upper-bound on accuracy; however, it extends the result presented therein to the case of PLSBM, and to the case of K ≥ 2 communities. §5 adapts the result presented in [Saad and Nosratinia, 2018] to the case of PLSBM. §6 puts forth a well-reasoned conjecture that proposes to extend the result presented in [Yun and Proutiere, 2014] to the case of PLSBM. At a high level, all the three results state one structural constraint (involving Q) for each regime of the volume and quality of labels (governed by ϵl and α, respectively) that is either necessary for recovery (or, in some cases, sufficient as well). The corresponding guarantee on accuracy of LP is then made by invoking Theorem 1.

We refer the reader to Table 1 for a summary of the results presented in the remainder of this work, and a highlight of our contributions both w.r.t. the literature on the success/failure of G-SSL ([Yamaguchi and Hayashi, 2017]) in the top two rows (shaded in gray ), as well as the literature on community detection ([Ke and Honorio, 2018], [Saad and Nosratinia, 2018], [Yun and Proutiere, 2014]) that we adapt in the bottom two rows (below the rule). Inside the bracket, we provide a pointer to the corresponding section, as well as highlight the difference with the corresponding paper that we adapt (marked with 2 � in the same column).

4 Failure of Recovery &Up to 100(1 - δ)% Accuracy

In this section, we aim to provide a sufficient condition for the failure of recovery and, thus, furnish an upper-bound on the accuracy. We choose to prove algorithm-agnostic and nonasymptotic bounds and resort to information-theoretic techniques employed in [Ke and Honorio, 2018]. Note that their proof applies to SBM with no side-information and is limited to the K = 2 setting -- two limitations that we alleviate in this work. Note that we do not consider bounds specific to any inference technique such as MLE ([Saad and Nosratinia, 2018] and [Abbe et al., 2015]) or those that are asymptotic ([Abbe and Sandon, 2015]). We state the theorem below:

Theorem 2. Given (A,X′ ) ∼ PLSBM(n, ϵl, α,K,Q), where Q is a weakly assortative matrix as defined by mink (Qk,k - maxk′ Qk,k′ ) ≥ 0, every algorithm fails to estimate the true membership, X, with Pr( ̂X ̸= X) ≥ δ, for any given δ ∈ [0, 1] if:

Where Bern(·|p) is the Bernoulli distribution with parameter p ∈ [0, 1] (and support in {0, 1}) and DBern max (Q) = maxi,j∈[K] KL(Bern(Qi,i)||Bern(Qi,j ))

Sketch of Proof. We make use of Fano's inequality, Pr( ̂X ̸= X) ≥ 1 - I(A,X′ ;X)+log 2 K logn , to lower-bound Pr( ̂X ̸= X). Next, we upper-bound the mutual information, I(A,X′ ;X), relying on a combination of independence/additivity, uniform bounding.

Discussion. Theorem 2 characterises the parameter space of PLSBM(n, ϵl, α,K,Q) that leads to a failure of inference by furnishing a structural constraint (involving Q) for a regime of labelling defined by the volume (ϵl) and quality (α) of labels. Note that α(K - 1) + 1 α(K-1) increases with decrease in α (signifying gradual increase in the quality of the labels). Hence with increasing ϵl > 0 (signifying a gradual transition in the volume of labels from rare to abundant), the product term ϵl(α(K - 1) + 1 α(K-1) ) increases, thus reducing the RHS and destroying the inequality unless DBern max (Q) is very low. In other words, abundance of high-quality (low noise) labels helps community recovery, as expected.

Discussion. (A,X′ ) ∼ PLSBM(n, ϵl, α, 2, a logn n I + b log n n (11T -I)), and theweak assortativity constraint, a ≥ b, allows us to simplify and bound the term DBern max (Q) in Equation 2 using the inequality, log x ≤ x - 1, to yield:

Note that in the limit n → ∞, the RHS tends to 0, whereas the LHS tends to (a-b)2 b . Therefore, the only way to guarantee failure is a = b, which turns the intra- and inter-community connectivity identical making the communities completely indistinguishable.

Discussion. Demanding a pronounced failure will require us to set 1-δ low, so that the accuracy upper-bound is tightened. This will lower the RHS and demand an increasing degree of indistinguishability (by lowering DBern max (Q)) for failure of recovery.

Discussion. This information theoretic result holds regardless of the algorithm employed for exact recovery, one of which is the MLE algorithm which has been shown by [Yamaguchi and Hayashi, 2017] to be the same as LP [Bengio et al., 2006] since the MAP objective functions are equivalent. This means that, under the condition presented in Theorem 2, LP will misclassify any given node on the graphs generated by PLSBM with high probability, and therefore should not be applied at all.

Corollary 1 (Up to 100(1 - δ)% accuracy of LP). By Theorem 2, if the volume and the quality of labels (governed by ϵl and α, respectively) fail to balance the structural separation (governed by DBern max (Q)), every algorithm would fail to infer ̂X effectively (since Pr( ̂X ̸= X) ≥ 1 - δ). Therefore, MLE will not succeed, as well: i.e. Pr(̂ XMLE ̸= X) ≥ 1 - δ. By Theorem 1 and its extension, ̂ XDLP = ̂ XMLE for PLSBM(n, nl, α, K, µI + ν(11T - I)) with given community sizes, {nk | k ∈ [K]}, for an appropriate choice of λ. Together, it guarantees that in expectation, the labels inferred by LP will have atmost 100(1 - δ)% accuracy.

Corollary 1 strengthens the precision of Theorem 1 considerably by lending a precise notion to the term failure, rather than capturing it by a far weaker notion of ̂ XDLP ̸= ̂ XMLE ([Yamaguchi and Hayashi, 2017]).

5 Exact Recovery & 100%Accuracy

We now characterise the regime in which LP attains 100% accuracy on partially-labelled networks generated from symmetric PLSBM with K = 2. To this end, we adapt the result on exact recovery ([Saad and Nosratinia, 2018]) for a more general model of partial labelling, m-ary side-information, to the case of symmetric PLSBM.

We commence by formally defining the restricted PLSBM setting i.e., PLSBM with two symmetric clusters.

Definition 3 (Symmetric PLSBM with K = 2). Symmetric PLSBM is PLSBM(n, ϵl, α, 2, a log n n I + b logn n (11T - I)), where each of the two clusters are of size n/2.

Definition 4 (m-ary SBM). Instead of just 2 symbols, as in the case with symmetric PLSBM with K = 2, m-ary sideinformation encodes x′i with an alphabet of size m: [m]. The crossover, Pr(x′i | xi) = Mxi,x′i , is governed by a stochastic matrix (each row sums to 1), M ∈ R2×m.

It is easy to see that symmetric PLSBM with K = 2 can be equivalently viewed as an m-ary side-information with m = 3, where the alphabet is {-1,+1, 0}. This enables us to formulate the following theorem:

Theorem 3. Given (A,X′ ) sampled from a symmetric PLSBM, if MLE exactly recovers the true membership X, then:

1. η(a, b, |β1|) + 2β2 > 2, with 0 < |β1| < T (a-b) 2 and β2 ≥ 0, if (ϵl, α) ∈ R3(ϵl, α; β1, β2),

Before we provide a sketch of the proof, we need to define the regimes, R1(ϵl, α), R2(ϵl, α; β) and R3(ϵl, α; β1, β2), of label volume and quality precisely. Intuitively, a low value of ϵl (equivalently, a low value of log 1 1-ϵl , since ϵl ∈ [0, 1]) signifies rarity in labels. Similarly, a too high (α ≈ 1) or a too low (α ≈ 0) value of α would be informative - since it would either favour the incorrect label always, or would favour the correct label. Since log α 1-α attains its maximum at α = 1/2, this term captures the lack of information. Since Theorem 3 is inherently asymptotic, we need to bound these quantities as n grows: e.g. between log 1 1-ϵl = o(logn) and log 1 1-ϵl = θ(logn), the former indicates a rare regime, whereas the latter signifies (relative) abundance. We operationalise these intuitions as follows:

1. R1(ϵl, α): Either log(1-ϵl) ∈ o(log n), or, {log ϵl(1α), log ϵlα, log α (1-α) } ⊂ o(log n).
2. R2(ϵl, α; β): Either log(1 - ϵl) ∈ -β logn+ o(logn), or, log α (1-α) ∈ o(log n) and {log ϵl(1 - α), log ϵlα} ⊂ -β log n + o(log n).
3. R3(ϵl, α; β1, β2): log (1-α) α ∈ β1 logn+o(logn), and, if β1 > 0 then log ϵl(1 - α) ∈ -β2 log n + o(log n) or if β1 < 0 then log ϵlα ∈ -β2 log n + o(log n)

Sketch of Proof. In the case of symmetric PLSBM with K = 2, the symbol y ∈ [m] is informative 3 if f y 1 = log M+1,y M-1,y is O(logn), and is non-informative if f y 1 = o(logn). By Theorem 5 of [Saad and Nosratinia, 2018], this translates to the corresponding condition on log (1-α) α . Similarly, the symbol y is rare if f y 2 = logM+1,y or f y 3 = logM-1,y is O(logn) (o(logn) leads to the abundance). By Theorem 5 of [Saad and Nosratinia, 2018], this translates to the corresponding conditions on log(1 - ϵl), log ϵl(1 - α), log ϵlα.

Corollary 2 (100%accuracy of LP). By Theorem3, if ̂ XMLE exactly recovers the true labels X, the necessary conditions on the symmetric PLSBM parameters must hold and align with the three regimes, R1(ϵl, α), R2(ϵl, α; β) and R3(ϵl, α; β1, β2). By Theorem 1 and its extension, ̂ XDLP = ̂ XMLE for symmetric PLSBM, since n1 = n2 = n2 , for an appropriate choice of λ for each of the three regimes (e.g., λ = ω(log n) when (ϵl, α) ∈ R1(ϵl, α)). Therefore, if ̂ XDLP recovers the true labels X with 100% accuracy, the symmetric PLSBM parameters have to lie in one of the three regimes 4 .

Corollary 2 strengthens Theorem 1 by precisely defining the notion of success beyond ̂ XDLP = ̂ XMLE as found in [Yamaguchi and Hayashi, 2017]. §6 further generalises the notion of success.

3 Our usage of the terms informative and rare follows [Saad and Nosratinia, 2018]

4 Note that this is not sufficient. However, the experimental evidence presented in Figure 1 supports the characterisation.

6 Partial Recovery & at Least 100(1 - s/n)% Accuracy

In this section, we present a well-reasoned conjecture for the partial recovery of PLSBM, based on the results on partial recovery of SBM, without partial labelling, presented in [Yun and Proutiere, 2014]. Figure 1 furnishes experimental evidences in its support. We formulate the following corollary based on Theorem 1 of [Yun and Proutiere, 2014]:

Corollary 3. For a symmetric SBM(n, 2, pI+q(11T -I)) with p = a log n n and q = b logn n , where a > b, the number of nodes with wrongly inferred community memberships under a certain spectral algorithm does not exceed s (s = o(n)) with high probability in the asymptotic sense, if:

After scaling both sides with logn log n/s , taking liminfn→∞ we recover the necessary condition, (√a - √b)2 > 2, of Theorem 3, barring the scaling factor on the LHS (and the strict inequality):

This, further, tempts us to extend this observation to the case of a symmetric PLSBM with K = 2 in all the three regimes of Theorem 3, as well as to the MLE estimator (instead of the spectral algorithm that Corollary 3 relies upon), and put forth the following conjecture (see Figure 1 for the experimental evidence in its favour):

Conjecture 1. Given (A,X′ ) sampled from a symmetric PLSBM, if ̂ XMLE makes at most s (s = o(n)) mistakes, asymptotically, and with high probability, then:

1. liminfn→∞ logn log n/s (√a - √b)2 ≥ 2, if (ϵl, α) ∈ R1(ϵl , α),

Corollary 4 (At least 100(1 - s/n)% accuracy of LP). Modulo Conjecture 1, if ̂ XMLE recovers X barring at most s (s = o(n); e.g. s = √n) mistakes with high probability as n → ∞, then the necessary conditions on the symmetric PLSBM parameters must hold and align with the three regimes, R1(ϵl, α), R2(ϵl, α; β) and R3(ϵl, α; β1, β2). By Theorem 1 and its extension, ̂ XDLP = ̂ XMLE for symmetric PLSBM, since n1 = n2 = n2 , for an appropriate choice of λ for each of the three regimes. Therefore, if̂ XDLP recovers the true labels X with 100(1-s/n)% accuracy, the symmetric PLSBM parameters have to lie in one of the three regimes 5 .

Conjecture 1 helps us relax the definition of success presented in §5, and helps us bolster Theorem 1 with a precise and widely applicable definition of success beyond ̂ XDLP = ̂ XMLE as presented in [Yamaguchi and Hayashi, 2017].

7 Empirical Results

We consider synthetic graphs generated by a symmetric 2cluster PLSBM for the three regimes of Theorem 3 with an assortativity matrix Q = [ p q q p ], where p = a logn n and q = b logn n , with a > b. We define a modified assortativity coefficient (MAC) as (√a - √b)2 , (√a - √b)2 + 2β, η(a, b, |β1|) + 2β2 for the regimes, R1(ϵl, α), R2(ϵl, α; β) and R3(ϵl, α; β1, β2), respectively. From Theorem 3 we see that as we vary the MAC in each regime from 0 to 2, we expect the accuracy of LP to rise gradually from 50% (or less) to 100%, with the intermediate values governed by Conjecture 1. The results shown in Figure 1 demonstrate that this is indeed the case, where in addition to LP [Zhu, 2005], we consider two other algorithms adapted for exact and partial recovery of PLSBM, for comparison: a) Alg1 - exact recovery algorithm proposed in [Saad and Nosratinia, 2018] which employs a weak recovery algorithm ([Massouli´e, 2014]) with a label flipping procedure to achieve exact recovery; b) Alg2 - it is similar to Alg1, but with the Spectral Partition algorithm ([Yun and Proutiere, 2014]) swapped with [Massouli´e, 2014] instead.

For generating these graphs, we set n = 107 , b = 1, and varied a accordingly to get the desired values of the MAC. For regime R1, we set the number of partially labeled nodes, nl = log n and for regimes R2 and R3, we set nl = √n. For the regime R2, the label corruption probability, α was set to 0.1, whereas for the regime R3 it was set to 10-5 .

7.1 Observations

We mark the regimes of failure (acc. ≤ 100(1-δ)%, δ = 0.5) and success (acc. = 100%) as predicted by the theory in Figure 1 in light red and light green, respectively. As per Theorem 3, the success regime is the entire region where the MAC is > 2. From Corollary 1, in the asymptotic case as n → ∞

5 Note that this is not sufficient. However, the experimental evidence presented in Figure 1 supports the characterisation.

the failure regime becomes infinitesimally small. Since the value of n is large (= 107 ), the failure regime becomes quite narrow and Figure 1 shows that accuracy of our algorithms drops below 50% even outside it. This illustrates the fact that Corollary 1 only gives us a regime of guaranteed failure and does not imply that failure will not occur outside the regime. However this is probably due to the imperfection of the existing algorithms. Hence we can reasonably expect that as GSSL algorithms get more sophisticated, the empirical point of failure will get pushed further and further towards the theoretical failure regime.

Following Conjecture 1, the values of the MAC for different lower bounds of guaranteed accuracy are obtained by simply scaling by a factor of logn log(n/s) . That is, for an accuracy guarantee of 100(1 - s/n)%, the MAC must be above 2 log(n/s) logn . We delineate a few such values of the MAC as black (dotted) vertical lines on the graphs and find them to be quite accurate lower bounds of accuracy of LP, thus furnishing empirical evidence in its favour. We also observe that 99% accuracy is achieved long before the theoretical success regime of exact recovery (acc. = 100%), which highlights the importance of the partial recovery result. Since we get almost identical graphs for the three cases of Theorem 3, these results corroborate the theory presented in the paper in the realm of a symmetric 2-cluster PLSBM.

8 Conclusion

In this paper we have imparted new meaning and formalisation to the notions of success and failure of LP by relating its accuracy to the notions of recovery in community detection. The novel theoretical results presented characterise the efficacy of LP based on graph structure, label volume and quality. Experiments on synthetic datasets generated from PLSBM confirmed the theory, as well as furnished insights on the regimes that the theory does not apply to. However, analysis of a broader family of G-SSL algorithms on real-world graphs remains an interesting open problem.

Acknowledgements

This work has been supported by the following projects:

1. Project "AI/ML Techniques for Online Shopping" sponsored by Flipkart Internet Private Limited.
2. Project "Learning Representations from Network Data" sponsored by Intel Corporation.