When Does Label Propagation Fail? A View from a Network Generative Model

1 Introduction

On most networks, such as social networks, nodes are associated with labels such as gender, age, and locations of people [Mislove et al., 2010]. Since these node labels are missing in most cases [Backstrom et al., 2010], predicting these missing labels is meaningful for some applications [Chaudhari et al., 2014; Jacob et al., 2014; Sen et al., 2008]. For Internet advertising, for example, prediction of user demographics is beneficial for both users and companies so that suitable advertisements can be placed. We call this the node classification problem-we want to recover the missing node labels given the observed node labels and the network structure.

Label Propagation (LP) [Bengio et al., 2006] is a standard algorithm for solving the node classification problem. 1 Given a network and partially observed node labels, LP minimizes the cost function, which consists of two terms that prefer that: (1) predicted labels of connected nodes are the same, and (2) predicted labels and observed labels are the same for each labeled node (i.e., the nodes whose labels are observed). To solve this optimization problem, LP propagates the observed labels throughout the network along edges, which converges to the optimal solution [Bengio et al., 2006].

1 Throughout this paper, we consider LP as an algorithm to solve the node classification problem, although it can be applied to any type of data by constructing a network based on the similarity of data samples.

Although LP works reasonably well in most cases, we do not know exactly which kinds of data LP does and does not work well on. This is our main research question (RQ). We break down the details of this RQ into the following four questions:

• RQ1: What type of node label is suitable for LPassortative, disassortative, or others? We say labels are assortative when nodes with the same labels are densely connected (e.g., age in SNS), or disassortative when nodes with different labels tend to be connected (e.g., gender in SNS [Takac and Zabovsky, 2012]).
• RQ2: Should the density of intra-cluster edges be uniform or non-uniform? Some real networks have clusters with varying densities; for example, in SNSs, classmates form a densely connected cluster, whereas people in the same city form a sparsely connected cluster.
• RQ3: Should the label distribution (i.e., the number of occurrences of each label across the whole network) be uniform or non-uniform? The label distribution is not always uniform; people's genders are almost uniformly distributed, for example, whereas people's home locations are not.
• RQ4: Can observed labels be allowed to be incorrect? If so, with what probability? Observed labels could be incorrect because of, for example, typing errors.

Admittedly, some of these questions have already been addressed individually. For example, at an objective function level, it is clear that LP does not work at all with disassortative node labels. However, there has been no comprehensive study that answers the above RQs at a much deeper level.

Meanwhile, in the network science community, a very similar problem called the node clustering problem has been extensively studied. Although the objective of this problem is also the prediction of node labels, the difference is that the setting is unsupervised; i.e., all of the labels are assumed to be unobserved. To solve this problem, the Stochastic Blockmodel (SBM) is often used [Wang and Wong, 1987]. SBM is a generative model of a network that has a community structure. A remarkable property is that, in contrast to LP, SBM explicitly characterizes the generative process of a network by a few interpretable parameters, which means we can understand the underlying structures of a real network by estimating these parameters. The above RQs are therefore completely clarified on SBM.

Present work. Although the problem settings are different (semi-supervised and deterministic vs. unsupervised and probabilistic), LP and SBM share the same goal. This raises a natural question: Is there any theoretical connection between LP and SBM? More specifically, can we interpret LP also as a probabilistic network generative model like SBM? The short answer is yes, and we use this key fact to derive the answers to the above RQs.

We explain the main idea step by step as follows. First, we propose a semi-supervised network generative modelPartially Labeled SBM (PLSBM)-that extends SBM so that it accepts partial supervision. Second, to make the discussion rigorous, we also introduce a discretized version of LP (formally introduced in Section 5.1), which we call discrete LP (DLP). Finally, as our main result, we show that the solution of DLP is identical to the maximum a posteriori (MAP) estimate of PLSBM with restricted parameters. This result reveals the theoretical properties of DLP (and LP) and allows us to answer the RQs. We also perform experiments on synthetic networks. The results on the synthetic datasets support our theoretical results.

To summarize, the key contributions of this paper are highlighted as follows.

• We propose PLSBM, which is the key to connecting the LP and network generative models.
• We prove that the solution of DLP is identical to the MAP estimate of a special case of PLSBM where some parameters are restricted. This means that we identify the data generative process behind DLP.
• Using the above result, we show the settings in which LP does and does not work well, by answering RQ1-RQ4.

We emphasize that our interdisciplinary findings between LP and SBM are not only theoretically interesting, but also have several potential impacts, including the following:

• The connection between LP and SBM allows us to interchange the findings from the so far different two communities, AI / machine learning and network science. This enables a deeper analysis of the theoretical properties of both models.
• Now we have a guideline for using LP-we can safely choose whether or not to use LP on a target dataset on the basis of the answers to our four RQs.

2 RelatedWork

Label Propagation. There are many algorithms related to LP; Harmonic Function [Zhu et al., 2003], Local and Global Consistency [Zhou et al., 2004], Adsorption [Baluja et al., 2008], and Modified Adsorption [Talukdar and Crammer, 2009] are the most commonly used algorithms that search for the fixed point state where as many connected nodes as possible have the same class labels. Whereas these algorithms are designed for assortative labels, OMNI-Prop [Yamaguchi et al., 2015] is an LP-like algorithm that is applicable to both assortative and disassortative labels.

There are few studies exploring LP from a theoretical perspective. In his doctoral thesis [Zhu et al., 2005], Zhu analyzed LP from several perspectives, for example, interpreting LP as a series of random walks or an electric network, and exploring connections between LP and Gaussian processes. A recent study [Kyng et al., 2015] also theoretically investigated related but not identical problem of graph regression, proposing a fast algorithm to solve it. To the best of our knowledge, our study is the first to address the network generative model behind LP.

Stochastic Blockmodel. SBM is one of the most basic network generative models; it takes an unattributed network and outputs the clustering of nodes. This basic model has been extensively studied from a variety of perspectives such as phase transition [Zhang et al., 2014], degree distribution [Karrer and Newman, 2011], and cluster size [Zhang et al., 2016]. However, to the best of our knowledge, there has been no study bridging the gap between LP and SBM to share the findings from both research communities. In this paper, to bridge this gap, we propose a network generative model that is designed to be as simple as possible, in contrast to other relatively complex models [Newman and Clauset, 2015; Chang and Blei, 2010; Nallapati et al., 2008; Cho et al., 2016; Kim and Leskovec, 2012; Pfeiffer III et al., 2014]. Our model is viewed as performing classification when it is provided some degree of supervision, and it is viewed as performing clustering when it is not provided any supervision. Hence, in the rest of this paper, we discuss in detail both the node classification problem and the node clustering problem, which are defined in the next section.

3 Settings

Let G = (X, Y ) be an attributed graph with N nodes, M edges, and K distinct labels. X is the N × N adjacency matrix where xij = 1 if node i and j are connected, and xij = 0 otherwise. Y is the N × K partially observed label assignment matrix where yik = 1 if node i has label k, and yik′ = 0 for k′ ̸= k. There are two types of nodes, namely, labeled nodes V L = {1, . . . ,NL}, and unlabeled nodes V U = {NL + 1, . . . ,N}. Each labeled node is explicitly assigned its label, whereas labels of unlabeled nodes are unknown. That is, for each labeled node 1 ≤ i ≤ NL, yi is a 1-of-K vector, whereas for each unlabeled node NL + 1 ≤ i ≤ N, yi is a 0 vector.

Using the above notation, we formally define the K-class node classification problem, which LP solves, and the Kcluster node clustering problem, which SBM solves, as follows:

Problem 1 (K-class node classification).

• Given: an adjacencymatrixX and a partially observed label assignment matrix Y ,
• Find: the label of each unlabeled node i ∈ V U .

Note that in the K-class node classification problem, we assume that at least one label assignment for each class is provided.

Problem 2 (K-cluster node clustering).

• Given: an adjacency matrix X and the number of clusters K,
• Find: the cluster assignment for each node i ∈ V L ∪ V U .

3.1 LP: Label Propagation

Given an attributed graph G, the objective of LP is to predict the label of each unlabeled node i ∈ V U . Let fik ∈ [0, 1] be the value that represents how likely it is that node i has label k. The objective function of LP to be minimized is defined as follows: 2

where λ ≥ 0 is the trade-off parameter, and ‖ · ‖2 denotes the ℓ2 -norm. The first term prefers that the predicted labels are the same as the observed labels, whereas the second term prefers that connected nodes have the same predicted labels. Note that since yi is a 0 vector for unlabeled node i, the first term works as a regularization term for unlabeled nodes so that fi moves toward 0. By setting the derivative of Q equal to zero, we have the closed-form solution of F as follows:

where L = D -W is the graph Laplacian, and D is the diagonal degree matrix with dii = ∑Nj=1 xij .

After ˆF is obtained, node labels are predicted by discretizing ˆF as follows:

Definition 1 (Solution of LP).

2 This objective function is the same as [Zhou et al., 2004] except for the square root degree normalization [Zhou et al., 2004].

3.2 SBM: Stochastic Blockmodel

SBM takes an adjacency matrix X and a user parameter K as input, and outputs K clusters of nodes. SBM has two parameters γ and Π, which have to be estimated fromX. γ is a Kdimensional vector for which ∑Kk=1 γk = 1, and γk ∈ [0, 1], which represents the fraction of the number of nodes in cluster k. Π is the K × K symmetric matrix whose element πkl ∈ [0, 1] represents the probability that a node in cluster k and a node in cluster l are linked by an edge.

The key idea of SBM is stochastic equivalence, which means that nodes in the same cluster have stochastically the same connection patterns (i.e., nodes in cluster k are all assigned πkl for all l). SBM produces clusters composed of stochastically equivalent nodes, which means that the resulting clusters are not always densely connected.

Generative Model

Let Mult denote the multinomial distribution and let Bern denote the Bernoulli distribution. Also, let zi be the 1-ofK indicator vector where zik = 1 indicates that node i is predicted to belong to cluster k. The generative process of SBM is then written as follows:

• For each node i = 1, . . . ,N
• Generate zi ∼Mult(·|γ)
• For each node pair (i, j)
• Generate xij ∼ Bern(·|zTi Πzj)

In the generative process, zi is generated for each node by the multinomial distribution with parameter γ. Then, xij is generated for each node pair by the Bernoulli distribution with parameter zTi Πzj, which equals πkl if zik = 1 and zjl = 1. The graphical model of SBM is shown in Fig. 1(a).

Based on this generative process, the log-likelihood of SBM is written as:

Inference

We follow [Daudin et al., 2008] who developed the variational EM (VEM) algorithm for estimating the SBM parameters.

In the E-step, we update the posterior distribution q(Z) as follows:

where qi = q(zi) for brevity, and ai = ln(11T - Π) ∑j̸=i qj; 1 denotes the vector with appropriate dimensions where all elements are 1.

In the M-step, we then update the parameters Π and γ as follows:

The iterative update of q, Π, and γ is guaranteed to converge, which achieves the local maxima of the marginal loglikelihood [Daudin et al., 2008].

4 PLSBM: Partially Labeled SBM

SBM is an unsupervised model; i.e., its estimate of the cluster structure is based solely on the network structure X. However, when the partially observed labels Y are given, we should use them because it will make clustering more accurate. This motivates us to introduce PLSBM.

4.1 Generative Model

Now we consider that, in addition to X, Y is also generated by the model. Since the given observed labels are possibly incorrect, we introduce an additional parameter α ∈ [0, 1] that represents the probability of the correctness of the observed labels. Let B be the K × K matrix where bkk = α for all k, and bkl = 1-α K-1 for k ̸= l. The generative process of PLSBM is written as follows:

• For each node i = 1, . . . ,N
• Generate zi ∼Mult(·|γ)
• For each labeled node i = 1, . . . ,NL
• Generate yi ∼Mult(·|Bzi)
• For each node pair (i, j)
• Generate xij ∼ Bern(·|zTi Πzj)

Note that the only difference between SBM and PLSBM is that PLSBM generates Y (see Fig. 1).

The log-likelihood of PLSBM is written as:

ln P (X, Y , Z|Π, α, γ) = ln P (X, Z|Π, γ) + ln P (Y |Z, α),

where P (X, Z|Π, γ) is the same as in SBM, and P (Y |Z, α) is the likelihood of generating partially observed labels Y .

4.2 Inference

Inspired by [Daudin et al., 2008], we derive the VEM algorithm of PLSBM. Details of the derivation are omitted since it is not very different from [Daudin et al., 2008].

In the E-step, we update the posterior distribution q(Z) as follows:

The difference from SBM (Eqn. (4)) is the effect of Y . If it is observed that node i has label k (i.e., yik = 1), the second term on the right-hand side is lnbk, where the k-th element is larger than the other elements when α > 1/K. This means that node i is supervised toward being predicted as label k.

In the M-step, we then update the parameters Π, γ, and α as follows:

The updating equations for Π and γ are the same as those for SBM.

4.3 SBMas a Special Case of PLSBM

We prove that SBM is a special case of PLSBM when we ignore observed labels Y .

Proposition 2. If α = 1/K, the difference between the likelihood functions of SBM and PLSBM is constant.

Proposition 2 indicates that, when the given labels are assumed to be completely random, the log-likelihoods of SBM and PLSBM are equivalent, and any estimation method (e.g., maximum likelihood, MAP, or other Bayesian inference method) results in the same estimators of the parameters. Proof is omitted since it is obvious.

5 Theory

5.1 DLP: Discrete Label Propagation

Recall that LP solves the continuous optimization problem for F and then discretizes it to predict node labels (Definition 1). This approach is advantageous in terms of computational efficiency. As shown in Eqn. (2), LP is essentially a problem of inverting (I + λL), which is efficiently solved by calculating the Neumann series [Harville, 1998]. The post hoc discretization is not satisfactory, however, in terms of the principle of optimization. Indeed, the discretized solution (Def. 1) is not the minimizer of Eqn. (1) under the 1-of-K constraint. Moreover, there is no explicit objective function for which the discretized solution (Def. 1) is the minimizer. Motivated by this, we reformulate the LP problem as a discrete optimization problem that we call DLP.

The input and the output of DLP are the same as those for LP. The objective function of DLP is the same as that of LP (Eqn. (1)) except that λ can be negative. 3 This is because even if λ < 0, the solution of DLP does not diverge because of the constraint that the zi's are 1-of-K vectors. The solution of DLP is defined as follows:

Definition 3 (Solution of DLP).

where ℧ is the entire space consisting of N 1-of-K vectors.

Since the solution of LP (3) is an approximated solution of the objective function of DLP (8), the achievable minimum of LP with post hoc discretization is always worse than or equal to the minimum for DLP.

Proposition 4. For any X, Y , and λ,

5.2 DLP as a Special Case of PLSBM

First we define the MAP estimate of PLSBM as follows:

Definition 5 (MAP estimate of PLSBM).

3 If λ < 0 in LP, the second term of Eqn. (1) can be made arbitrarily small by increasing some of the Fs, and the solution can diverge to infinity.

Now, we show the sufficient conditions for the equivalence between the MAP estimate of PLSBM and the solution of DLP.

Theorem 6. Let ˆZDLP (λ) be the set of solutions of DLP with λ ∈ R. Let us introduce two variables µ, ν ∈ [0, 1] and let ˆZPLSBM(µ, ν, α) be the set of MAP estimates of Z with the subclass of PLSBM where

• Condition 1. γk = 1/K for all k,
• Condition 2. Π = µI + ν(11T - I), and
• Condition 3. the number of nodes assigned to cluster k is specified in advance for all k.

Then, ˆZDLP (λ) = ˆZPLSBM(µ, ν, α) if the following conditions are satisfied:

• Condition 4. if λ > 0, then µ > ν; else if λ < 0, then µ < ν; else if λ = 0, then µ = ν; and

Proof sketch. The log-likelihood of PLSBM satisfying Conditions 1 and 2 is rewritten as follows:

where C is some constant.

Denoting by nk = ∑i zik the number of nodes assigned to cluster k we can write: ∑Ni=1 ∑Nj=1 zTi zj = ∑Kk=1 n2k . Since this term becomes constant under Condition 3, according to Eqn. (9) we can again rewrite the log-likelihood as follows:

where C ′ is some constant. In addition, we can rewrite Eqn. (1) as follows:

where C ′′ is some constant. To show the equivalence of the maximizers, Eqns. (10) and (11) need to be equal up to a positive scale c′ > 0. This requires, by comparing the first and second terms in Eqns. (10) and (11), we need to have ln α(K-1) 1-α = c′ and ln µ(1-ν) ν(1-µ) = c′λ. Substituting the former into the latter, we obtain Condition 5. In addition, because c′ is positive, 1λ ln µ(1-ν) ν(1-µ) must be positive, which yields Condition 4.

According to Conditions 4 and 5, λ (the LP parameter) is related to Π and α (the PLSBM parameters). It is interesting to note that the label correctness probability α and the edge probability Π in PLSBM are controlled by just one parameter λ in DLP.

5.3 Answers to Our RQs

Having proved Theorem 6, we are now in a position to answer our four RQs.

• (RQ1) Assortativity and disassortativity. Condition 4 implies that positive λ leads to µ > ν. This indicates that since LP requires λ > 0, it works only on networks with assortative labels where the diagonal value µ of Π is larger than the off-diagonal value ν of Π.
• (RQ2) Uniform or non-uniform cluster density. Condition 2 implies that DLP assumes the uniform cluster density. Therefore, DLP may not work well on networks that have clusters with different densities, i.e., those for which the diagonal elements of Π are not the same.
• (RQ3) Uniform or non-uniform label distribution. Condition 1 implies that DLP assumes the uniform label distribution. This means that DLP may not work well for cases in which the ratio of labels in each class is non-uniform.
• (RQ4) Label correctness probability. Condition 5 implies a large odds ratio ( µ 1-µ )/( ν 1-ν ), which indicates strong assortativity, leads to large α. This means that, when LP deals with a network having strong assortativity, it requires α to be large. However, there could be labels with strong assortativity but small α (observed labels that are incorrect with high probability.) Therefore, DLP may not handle the case where there are many label noises but strong assortativity.

Although we interpret DLP as a special case of PLSBM in Theorem 6, there is still a gap between DLP and LP, namely, that LP involves a continuous relaxation. Furthermore, for PLSBM, Theorem 6 only shows the equivalence of its MAP estimate, not the solution given by the VEM algorithm. This gap will be shown to be sufficiently small, however, in the next section.

6 Experiments

6.1 Settings

We use PLSBM to generate the synthetic datasets (i.e., X and Y ) with varying parameters. We also vary the ratio of the training nodes (NL/N) from 0.1 to 0.9 by steps of 0.2. For each setting, we generate 20 networks with N = 1, 000 nodes and report the mean accuracy and the standard deviation. Note that although using the LFR benchmark [Lancichinetti et al., 2008] would be interesting, it is better to use PLSBM to generate the data to investigate the properties of LP. We compare SBM, PLSBM, and LP. SBM and PLSBM learn all the parameters from the data, whereas LP determines its parameter by 5-fold cross validation.

We use the standard classification accuracy for our evaluation metric, which is defined as the ratio of the number of correctly classified test nodes against all test nodes. For evaluating SBM and PLSBM, which essentially perform clustering, we take the best match between correct labels and the results of cluster numbers.

Reproducibility. Our code to reproduce the experiments is available at https://goo.gl/VWggEy.

6.2 Results

We perform experiments on four scenarios each of which corresponds to one of our four RQs.

(RQ1) Assortativity and disassortativity. We compare the results on assortative and disassortative labels with K = 2. For the network with assortative labels, we use Π(a) = ( 0.15 0.1 0.1 0.15 ), whereas for the network with disassortative labels, we useΠ(d) = ( 0.1 0.15 0.15 0.1 ). The other parameters are set to γ = (0.5, 0.5) and α = 0.99. The results (Figs. 2(a) and 2(f)) show that LP does not work on the disassortative labels.

(RQ2) Uniform or non-uniform cluster density. We compare the results on networks with uniform and non-uniform cluster densities with K = 3. For the uniform case, we use Π whose diagonal elements are all 0.2, and for the non-uniform case, we use Π whose diagonal elements are Π11 = 0.2, Π22 = 0.15, and Π33 = 0.1. Off-diagonal elements of Π in both settings are all 0.05 (so generated labels are assortative). The other parameters are set to uniform γ and α = 0.99. The results (Figs. 2(b) and 2(g)) show that the accuracy of LP is lower than that of SBM and PLSBM when the cluster density is non-uniform, indicating that LP does not work well on networks with a non-uniform cluster density.

(RQ3) Uniform or non-uniform label distribution. We compare the results on K = 3 networks with uniform (γ = (1/3, 1/3, 1/3)) and non-uniform (γ = (1/2, 1/4, 1/4)) label distributions. We use α = 0.99, and Π where Πkl = 0.15 if k = l and Πkl = 0.1 if k ̸= l. The results (Figs. 2(c) and 2(h)) show that LP does not work in the non-uniform setting even when the 90% of nodes are used as training nodes.

(RQ4) Label correctness probability. We compare the results on networks with high (α = 0.9) and low (α = 0.6) label correctness probabilities. The other parameters are set to K = 2, uniform γ, and Π = Π(a) . Figs. 2(d) and 2(i) show that, whereas SBM and PLSBM achieve almost 100% accuracy in both cases, LP shows lower accuracy when α = 0.6, meaning that LP does not adapt to varying α when Π is fixed.

7 Discussion

As shown in Figs. 2(a) and 2(f), on the dense networks, PLSBM achieves almost 100% accuracy. More surprisingly, SBM achieves almost the same high performance even though it does not use any observed labels. On the other hand, as shown in Figs. 2(e) and 2(j), SBM and PLSBM do not work well when we use 0.1 · Π(a) and 0.1 · Π(d) . This behavior is explained by the notion of detectability [Saade et al., 2014]. That is, without any supervision, SBM can recover true labels perfectly if the given network satisfies |cin - cout| ≥ K√c, where K = 2, cin and cout are the diagonal and off-diagonal parts of Πmultiplied by N, respectively, and c is the average degree. Whereas Π in the dense setting has the detectability property, Π in the sparse setting does not, which is also confirmed from the results.

In contrast, LP does not perfectly classify the nodes even on the dense networks, indicating that LP does not leverage the detectability. This can be explained by the weak expressive power of LP compared to PLSBM. As shown in Theorem 6, LP can handle only the subclass of networks that PLSBM generates because of some fixed parameters.

Acknowledgements

This research was partially supported by the program "Research and Development on Real World Big Data Integration and Analysis" of RIKEN, Japan, and by a project commissioned by the New Energy and Industrial Technology Development Organization (NEDO).