Title: GENERALIZED LABEL PROPAGATION METHODS FOR SEMI-SUPERVISED LEARNING

Abstract: The key challenge in semi-supervised learning is how to effectively leverage unlabeled data to improve learning performance. The classical label propagation method, despite its popularity, has limited modeling capability in that it only exploits graph information for making predictions. In this paper, we consider label propagation from a graph signal processing perspective and decompose it into three components: signal, filter, and classifier. By extending the three components, we propose a simple generalized label propagation (GLP) framework for semi-supervised learning. GLP naturally integrates graph and data feature information, and offers the flexibility of selecting appropriate filters and domainspecific classifiers for different applications. Interestingly, GLP also provides new insight into the popular graph convolutional network and elucidates its working mechanisms. Extensive experiments on three citation networks, one knowledge graph, and one image dataset demonstrate the efficiency and effectiveness of GLP.

1. INTRODUCTION:

The success of deep learning and neural networks comes at the cost of large amount of training data and long training time. Semi-supervised learning (Zhu, 2005; Chapelle et al., 2006) is interesting and important as it can leverage ample available unlabeled data to aid supervised learning, thus greatly saving the cost, trouble, and time for human labeling. Many researches have shown that when used properly, unlabeled data can significantly improve learning performance (Zhu & Goldberg, 2009; Kingma et al., 2014; Kipf & Welling, 2017) . The key challenge for semi-supervised learning is how to effectively leverage the information of unlabeled data, such as graph structures and data features.

Label propagation (Zhu et al., 2003; Zhou et al., 2004; Bengio et al., 2006) is arguably the most popular method for graph-based semi-supervised learning. As a simple and effective tool, it has been widely used in many scientific research fields and has found numerous industrial applications. Given a non-oriented graph G = (V, W, X) with n = |V| vertices, a nonnegative symmetric affinity matrix W ∈ R n×n + encoding edge weights, and a feature matrix X ∈ R n×m which contains an mdimensional feature vector of each vertex. For semi-supervised classification, only a small subset of vertices are labeled, and the goal is to predict the labels of other vertices. Denote by Y ∈ {0, 1} n×l the labeling matrix 1 with l being the number of classes. The objective of of label propagation (LP) is to find a prediction (embedding) matrix Z ∈ R n×l which agrees with Y while being smooth on the graph such that nearby vertices have similar embeddings:

EQUATION

where α is a balancing parameter, L = D -W is the graph Laplacian 2 and D is the degree matrix.

The term enforcing smoothness is called graph Laplacian regularization or Tikhonov regularization. Solving the quadratic regularization framework gives the prediction of LP.

As LP makes predictions only based on graph information (W ), its performance depends on whether the underlying graph structure can well represent the class information of data -vertices in the same 1 If the label of vertex vi is known, then Y (i, :) is a one-hot embedding of vi with yij = 1 if vi belongs to the j-th class and yij = 0 otherwise. If the label of vertex vi is not given, then Y (i, :) is a vector of all zeros.

2 Other variants such as the normalized Laplacian matrices are also applicable.

cluster tend to have same labels. For some applications such as social network analysis, data exhibits a natural graph structure. For some other applications such as image or text classification, data may come in a vector form, and a graph is usually constructed using data features. Nevertheless, in many cases, graphs only partially encode data information. Take document classification in a citation network as an example, the citation links between documents form a graph which represents their citation relation, and each document is represented as a bag-of-words feature vector which describes its content. To correctly classify a document, both the citation relations (W ) and the content information (X) need to be taken into account, as they contain different aspects of document information. However, in this case, LP can only exploit the graph information to make predictions without using any of the feature information, thus resulting in poor performance.

To go beyond the limit of LP and jointly model graph and feature information, a common approach is to train a supervised learner to classify data features while regularizing the classifier using graph information. Manifold regularization (Belkin et al., 2006) trains a support vector machine with a graph Laplacian regularizer. Deep semi-supervised embedding (Weston et al., 2008) and Planetoid (Yang et al., 2016) train a neural network with an embedding-based regularizer. The recently proposed graph convolutional neural networks (Kipf & Welling, 2017) adopts a different approach by integrating graph and feature information in each of its convolutional layer, which is coupled with a projection layer for classification.

In this paper, we extends the modeling capability of LP in the context of graph signal processing. Casted in the spectral domain, LP can be interpreted as low-pass graph filtering (Ekambaram et al., 2013; Girault et al., 2014) . The rest of the paper is organized as follows. Section 2 interprets LP in the context of graph signal processing. Section 3 presents the proposed GLP framework. Section 4 revisits GCN under GLP. Section 5 discusses the design of graph filters for GLP. Section 6 presents experimental results. Section 7 discusses related works. Finally, section 8 concludes the paper.

2. A SPECTRAL VIEW OF LABEL PROPAGATION:

In this section, we provide a spectral view of LP in the context of graph signal processing.

2.1. GRAPH SIGNALS AND FILTERS:

In graph signal processing (Shuman et al., 2013) , the eigenvectors and eigenvalues of the graph Laplacian play the role of Fourier basis and frequencies in parallel with classical harmonic analysis. The graph Laplacian matrix can be eigen-decomposed as: L = ΦΛΦ -1 , where Λ = diag(λ 1 , • • • , λ n ) are the eigenvalues in an increasing order, i.e., 0 = λ 1 ≤ • • • ≤ λ n , and Φ = (φ 1 , • • • , φ n ) are the associated orthogonal eigenvectors. Note that the row normalized graph Laplacian L r = D -1 L and the symmetrically normalized graph Laplacian L s = D -1 2 LD -1 2 have similar eigen-decomposition. The eigenvalues (λ i ) 1≤i≤n are interpreted as frequencies and the associated eigenvectors (φ i ) 1≤i≤n are interpreted as Fourier basis.

A graph signal is a real-valued function f : V → R defined on the vertex set of a graph. Denote by f = (f (v 1 ), • • • , f (v n )) a graph signal in a vector form. Consider (φ i ) 1≤i≤n as basis functions. Any graph signal f can be decomposed into a linear combination of the basis functions:

EQUATION

where c = (c 1 , • • • , c n ) and c i is the coefficient of φ i . The magnitude of the coefficient |c i | represents the strength of the basis function φ i presented in the signal f .

A graph filter is defined as a matrix G ∈ R n×n . G is linear shift-invariant (Sandryhaila & Moura, 2013) , if and only if there exists an function

p(•) : R → R, satisfying G = Φp(Λ)Φ -1 , where p(Λ) = diag(p(λ 1 ), • • • , p(λ n )). The real-valued function p(•) is called the frequency response function of G.

It is well known that the basis functions associated with lower frequencies (smaller eigenvalues) are smoother (Zhu & Goldberg, 2009) , as the smoothness of φ i can be measured by λ i :

EQUATION

This indicates that a smooth signal f should contain more low-frequency components than highfrequency components. To produce a smooth signal, the graph filter G should be able to preserve the low-frequency components in f while filtering out the high-frequency components. By Eq. ( 2), we have

EQUATION

In the filtered signal f , the coefficient c i of the basis function φ i is scaled by p(λ i ). To preserve the low-frequency components and remove the high-frequency components, p(λ i ) should amplify c i when λ i is small and suppress c i when λ i is large. Simply put, p(•) should behave like a low-pass filter in classical harmonic analysis.

2.2. THREE COMPONENTS OF LABEL PROPAGATION:

The prediction (embedding) matrix of LP can be obtained by taking the derivative of the unconstrained quadratic optimization problem in Eq. ( 1) and setting it to zero:

EQUATION

With the prediction matrix Z, each unlabeled vertex v i is usually classified by simply comparing the elements in Z(i, :). In some methods, a normalization scheme may be applied on the columns of Z first before the comparison (Zhu et al., 2003) .

Casted in the context of graph signal processing, LP can be decomposed into three components: signal, filter, and classifier. By Eq. ( 5), the input signal matrix of LP is the labeling matrix Y , where it has l channels and each column Y (:, i) can be considered as a graph signal. In Y (:, i), only the labeled vertices in class i have value 1 and others 0.

The graph filter used in LP is

(I + αL) -1 = [Φ(I + αΛ)Φ -1 ] -1 = Φ(I + αΛ) -1 Φ -1 ,

with frequency response function

EQUATION

)

Note that this also holds for the normalized graph Laplacians. As shown in Fig. 1 (a), the frequency response function of LP is low-pass. For any α > 0, p(λ i ) is near 1 when λ i is close to 0 and p(λ i ) decreases and approaches 0 as λ i increases. Applying the filter on signal Y (:, i), it will produce a smooth signal Z(:, i) in which vertices of the same class have similar values and vertices in class i have larger values than others under the cluster assumption. The balancing parameter α controls the degree of the graph Laplacian regularization. When α increases, the filter becomes more low-pass (Fig. 1 (a)) and will produce smoother embeddings.

Finally, LP applies a nonparametric classifier on the embeddings to classify the unlabeled vertices, i.e., the label of an unlabeled vertex v i is given by y i = arg max j Z(i, j). 

k = 1 k = 2 k = 3 k = 4 (b) RNM: (1 -λ) k 0.0 0.5 1.0 1.5 2.0 1.0 0.5 0.0 0.5 1.0 k = 1 k = 2 k = 3 k = 4 (c) RW: (1 -1 2 λ) k 0.0 0.5 1.0 1.5 2.0 1.0 0.5 0.0 0.5 1.0 RNM, k = 2 RW, k = 2 RW, k = 4

3. GENERALIZED LABEL PROPAGATION METHODS:

We propose a generalized label propagation (GLP) framework by naturally generalizing the three components of LP for semi-supervised classification:

• Signal: Use the feature matrix X instead of the labeling matrix Y as input signal.

• Filter: The filter G can be any low-pass, linear, shift-invariant filter.

• Classifier: The classifier can be any classifer trained on the embeddings of labeled vertices.

GLP consists of two steps. First, a low-pass, linear, shift-invariant graph filter G is applied on the feature matrix X to obtain a smooth feature matrix X ∈ R n×m :

EQUATION

The next step is to train a supervised classifier (e.g., multilayer perceptron, convolutional neural networks, support vector machines, etc.) with the filtered features of labeled data, and then apply the classifier on the filtered features of unlabeled data to predict their labels.

GLP naturally combines graph and feature information in Eq. ( 7), and allows taking advantage of a powerful supervised classifier. The rationale behind GLP is to learn representative feature vectors of each class for easing the downstream classification task. After filtered by G, vertices in the same class are expected to have more similar and representative features, which makes it much easier to train a good classifier with very few samples.

Consider an extreme case that each class is a connected component of the graph. In this case, we can learn perfect features by an extremely low-pass filter G, whose spectrum p(•) is unit impulse function, i.e., p(0) = 1 and p(λ) = 0 if λ = 0. We can compute G = Φp(Λ)Φ -1 in the spatial domain. In particular, G ij = 1 l k if v i and v j are of the same class, otherwise G ij = 0, where l k is the number of labeled samples in class k. After filtered by G, vertices in the same class will have an identical feature vector which is its class mean. Then any classifier that can correctly classify the labeled data will achieve 100% accuracy on the unlabeled data, and only one labeled example per class is needed to train the classifier.

4. REVISIT GRAPH CONVOLUTIONAL NETWORKS:

In this section, we show that the graph convolutional networks (GCN) (Kipf & Welling, 2017) for semi-supervised classification can be interpreted under the GLP framework, which explains its implicit design features including the number of layers, the choice of the normalized graph Laplacian, and the renormalization trick on the convolutional filter.

Graph Convolutional Networks. The GCN model contains three steps. First, a renormalization trick is applied on the adjacency matrix W by adding an self-loop to each vertex, which results in a new adjacency matrix W = W + I with the degree matrix D = D + I. After that, symmetrically normalize W and get Ws = D-1 2 W D-1 2 . Second, define the propagation rule

EQUATION

where H (t) is the matrix of activations in the t-th layer and H (0) = X, Θ (t) is the trainable weight matrix in layer t, and σ is the activation function, e.g., ReLU(•) = max(0, •). The graph convolution is defined by multiplying the input of each layer with the renormalized adjacency matrix Ws from the left, i.e., Ws H (t) . The convoluted features are then fed into a projection matrix Θ (t) . Third, stack two layers up and apply a softmax function on the output features to produce a prediction matrix:

EQUATION

and train the model using the cross-entropy loss over the labeled instances.

4.1. LINK TO GENERALIZED LABEL PROPAGATION METHODS:

The graph convolution in each layer of the GCN model actually performs feature smoothing with a low-pass filter Ws = I -Ls , where Ls is the symmetrically normalized graph Laplacian of the graph with extra self-loops. Suppose that Ls can be eigen-decomposed as Ls = Φ ΛΦ -1 , then we have I -Ls = Φ(I -Λ)Φ -1 . The frequency response function of the filter is

EQUATION

Clearly, as shown in Fig. 1 (b), this function is linear and low-pass on the interval [0, 1], but not on [1, 2], as it amplifies the eigenvalues near 2.

Interestingly, by removing the activation function ReLU in Eq. ( 9), we can see that GCN is a special case of GLP, where the input signal is X, the filter is W 2 s , and the classifier is a two-layer multi-layer perceptron (MLP).

Why the Normalized Graph Laplacian. Note that the eigenvalues of the normalized Laplacians L s and L r all fall into interval [0, 2] (Chung, 1997), while the unnormalized Laplacian L has eigenvalues in [0, +∞]. If using the unnormalized graph Laplacian, the response function in Eq. (10) will amplify eigenvalues in [2, +∞], which will introduce noise and undermine performance.

Why Two Convolutional Layers. In Eq. ( 9), the GCN model stacks two convolutional layers. Without the activation function, the feature matrix is actually filtered by I -Ls twice, which is equivalent to be filtered by (I -Ls ) 2 with response function (1 -λ) 2 . As we can see from Fig. 1(b),  (1 -λ) 2 is more low-pass than (1 -λ) by suppressing the eigenvalues in the mid-range of [0, 2] harder, which explains why GCNs with two convolutional layers perform better than those with only one.

Why the Renormalization Trick. The effect of the renormalization trick is illustrated in Fig. 2 , where the response functions on the eigenvalues of L s and Ls on the Cora citation network are plotted. We can see that by adding a self-loop to each vertex, the range of eigenvalues shrink from [0, 2] to [0, 1.5], thus avoiding amplifying eigenvalues near 2 and reducing noise. This explains why the renormalization trick works.

5. FILTER DESIGN AND COMPUTATION:

In this section, we discuss the design and computation of low-pass graph filters for GLP.

Auto-Regressive. The Auto-Regressive (AR) filter is the one used in LP:

EQUATION

)

Actually p ar is an auto-regressive filter of order one (Tremblay et al., 2018) . We have shown p ar is low-pass in section 2.2. However, the computation of p ar involves matrix inversion, which is also computationally expensive with complexity O(n 3 ). Fortunately, we can circumvent this problem by approximating p ar using its polynomial expansion:

EQUATION

We can then compute X = p ar (L)X iteratively with

X (0) = O, • • • , X (i+1) = X + α 1 + α W X (i) ,

and let X = 1 1+α X (k) . Empirically, we find that k = 4α is enough to get a good approximation. Hence, the computational complexity is reduced to O(nmα

+ N mα) (note that X is of size n × m),

where N is the number of nonzero entries in L, and N n 2 when the graph is sparse.

Renormalization. The renormalization (RNM) filter is an exponential function of the renormalized adjacency filter used in GCN:

EQUATION

)

We have shown in section 4.1 that although the response function p rnm (λ) = (1 -λ) k is not lowpass, the renormalization trick shrinks the range of eigenvalues of L and makes p rnm resemble a low-pass filter. The exponent parameter k controls the low-pass effect of p rnm . When k = 0, p rnm is all-pass. When k increases, p rnm becomes more low-pass. Note that for a sparse graph, (I -L) is a sparse matrix. Hence, the fastest way to compute X = p rnm ( L)X is to left multiply X by (I -L) repeatedly for k times, which has the computational complexity O(N mk).

Random Walk. We also propose to design a random walk (RW) filter:

EQUATION

)

We call p rw the random walk filter because I+D -1 W 2 is a stochastic matrix of a lazy random walk which at each step returns to the current state with probability 1 2 , and

I+D -1 W 2 k

is the k-step transition probability matrix. Similarly, we can derive the response function of p rw as

EQUATION

)

Note that L r has the same eigenvalues with L s , with range [0, 2]. Unlike the RNM, p rw is a typical low-pass filter on [0, 2], as shown in Fig. 1(c ). We can also see in Fig. 1(d ) that the curves of (1-λ) 2 and (1 -1 2 λ) 4 are very close, implying that to have the same level of low-pass effect, k in p rw should be set twice as large as in p rnm . This may be explained by the fact that the two functions (1 -λ) k and (1 -1 2 λ) 2k have the same derivative k at λ = 0. On the computation side, RW has the same complexity O(N mk) as RNM.

An important issue of filter design for GLP is how to control the strength of filters by setting parameters such as α and k. Intuitively, when labeled data is scarce, it would be desirable for the filtered features of each instance to be closer to its class mean and be more representative of its own class. Hence, in this case, α and k should be set large to produce smoother features. However, oversmoothing usually results in inaccurate class boundaries. Therefore, when the amount of labeled data is reasonably large, α and k should be set relatively small to preserve feature diversity in order to learn more accurate class boundaries.

6. EXPERIMENTS:

Datasets In this section, we test GLP on three citation networks -Cora, CiteSeer and PubMed (Sen et al., 2008) , one knowledge graph -NELL (Carlson et al., 2010) , and one handwritten digit image dataset -MNIST (LeCun et al., 1998) . Dataset discriptions are provided in Appendix A. Baselines On citation networks and NELL, we compare GLP against GCN (Kipf & Welling, 2017), LP (Wu et al., 2012) , multi-layer perceptron (MLP), Planetoid (Yang et al., 2016) , DeepWalk (Perozzi et al., 2014) , manifold regularization (ManiReg) (Belkin et al., 2006) , semi-supervised embedding (SemiEmb) (Weston et al., 2008) , and iterative classification algorithm (ICA) (Sen et al., 2008) . On MNIST, we compare GLP against GCN, LP, MLP, and convolutional neural networks (CNN).

Experimental Setup We test GLP with RNM, RW and AR filters (section 5) on all the datasets. We use MLP as the classifier for GLP on citation networks and NELL, and use CNN as the classifier on MNIST. Guided by our analysis in section 5, the filter parameters k and α should be set large with small label rate and set small with large label rate. We use fixed parameters k = 10 for RNM, k = 20 for RW, and α = 20 for AR when label rate is less than or equal to 2%, and set them to 5, 10, 10 respectively otherwise. We follow Kipf & Welling (2017) to set the parameters of MLP, including learning rate, dropout, and weight decay. To make sure GLP works in practice and for more fair comparison with baselines, we do not use a validation set for classifier model selection as in Kipf & Welling (2017), instead we select the classifier with the highest training accuracy in 200 steps. Results of GLP and GCN on all the datasets are reported without using a validation set, except that on NELL, we also report the results with validation (on the right of "/"). More implementation details are provided in Appendix B due to space limitations.

Performance of GLP The results are summarized in Tables 1 and 2 , where the top 3 classification accuracies are highlighted in bold. Overall, GLP performs the best on all the datasets. On citation networks, with 20 labels per class, GLP performs comparably with GCN and outperforms other baselines by a considerable margin. With 4 labels per class, GLP significantly outperforms all baselines including GCN. On NELL, GLP wtih RW and RNM filters consistently outperforms the best baseline Planetoid for each setting, and outperforms other baselines including GCN by a large margin. Note that GLP achieves this performance without using any additional validation set. The performance of GLP (and GCN) will be further boosted with validation, as shown on the right of "/". On MNIST, GLP consistently outperforms all baselines for every setting.

The running times of GLP and some other baselines are also reported in Tables 1 and 2 . GLP runs much faster than GCN on most datasets, except for NELL, on which the running times of GLP with two filters are similar with GCN. More discussions about running times are included in Appendix E.

Results Analysis Compared with LP and DeepWalk which only use graph information, the large performance gains of GLP clearly comes from leveraging both graph and feature information. Compared with purely supervised MLP and CNN which are trained on raw features, the performance gains of GLP come from the unsupervised feature filtering. Fig. 3 visualizes the raw and filtered features (by RNM filter) of Cora projected by t-SNE (Van der Maaten & Hinton, 2008) . The filtered features exhibit a much more compact cluster structure, thus making classification much easier. In Appendix C, we show that feature filtering improves the accuracy of various classifiers significantly.

Compared with GCN and other baselines which use both graph and feature information, the performance gains of GLP come in two folds. First, GLP allows using stronger filters to extract higher level data representations to improve performance when label rate is low, which can be easily achieved by increasing the filter parameters k and α, as shown in Fig. 3 . But this cannot be easily achieved in GCN. As each convolutional layer of GCN is coupled with a projection layer, to increase smoothness one needs to stack many layers, and a deep GCN is difficult to train. Second, GLP allows adopting domain-specific classifiers such as CNN to deal with vision tasks. As shown in Table 2 , the performance of CNN trained on raw features of labeled data is very competitive and grows fast.

Due to space limitations, we include the stability analysis of GLP in Appendix D.

7. RELATED WORKS:

Many graph-based semi-supervised learning methods adopt a common assumption that nearby vertices are likely to have same labels. One idea is to learn smooth low-dimensional embedding of data points by using Markov random walks (Szummer & Jaakkola, 2002) , Laplacian eigenmaps (Belkin & Niyogi, 2004) , spectral kernels (Chapelle et al., 2003; Zhang & Ando, 2006) , and context-based methods (Perozzi et al., 2014) . Another idea hinges on graph partition, where the cuts should agree with the labeled data and be placed in low density regions (Blum & Chawla, 2001; Zhu et al., 2003; Joachims, 2003; Blum et al., 2004) . Perhaps the most popular idea is to formulate a quadratic regularization framework to explicitly enforce the consistency with the labeled data and the cluster assumption, which is known as label propagation (Zhou et al., 2004; Chapelle & Zien, 2005; Bengio et al., 2006; Kveton et al., 2010) .

To leverage more data information to improve predictions, a variety of methods proposed to jointly model data feature and graph information. Zhou et al. (2004) proposed to combine label propagation with external classifiers by attaching a "dongle" vertex to each unlabeled vertex. Iterative classification algorithm (Sen et al., 2008) iteratively classifies an unlabeled vertex using its neighbors' labels and features. Manifold regularization (Belkin et al., 2006) , deep semi-supervised embedding (Weston et al., 2008) , and Planetoid (Yang et al., 2016) regularize a supervised classifier with a Laplacian regularizer or an embedding-based regularizer. Graph convolutional networks (Kipf & Welling, 2017) combine graph and feature information in convolutional layers, which is actually doing Laplacian smoothing on data features (Li et al., 2018) . Follow-up works include graph attention networks (Velikovi et al., 2018) , attention-based graph neural network (Thekumparampil et al., 2018) , and graph partition neural networks (Liao et al., 2018) .

The idea of feature smoothing has been widely used in computer graphics community for fairing 3D surface (Taubin, 1995b; a; Desbrun et al., 1999) . Hein & Maier (2007) proposed manifold denoising which uses feature smoothing as a preprocessing step for running a label propagation algorithm, i.e, the denoised features are used to construct a better graph for LP. This method is still "onedimensional", as it cannot use the preexisting graph information in data such as citation networks.

In contrast, the proposed GLP and the GCN frameworks are "two-dimensional".

8. CONCLUSION:

In this paper, we have proposed a simple, flexible, and efficient framework GLP for semi-supervised learning, and demonstrated its effectiveness theoretically and empirically. GLP offers new insights into existing methods and opens up possible avenues for new methods. An important direction for future research is the design and selection of graph filters for GLP in different application scenarios.

Other directions include making GLP readily applicable to inductive problems, developing faster algorithms for GLP, and applying GLP to solve large-scale real-world problems. 

:

https://github.com/tkipf/ica

Figures and Tables:

Figure 1: Response functions of AR, RNM, and RW filters, and their comparison.

Figure 2: Effect of the renormalization trick. Left two figures plot points (λ i , p(λ i )). Right two figures plot points ( λi , p( λi )).

Figure 3: Visualization of raw and filtered features of Cora.

Classification Accuracy and running time on citation networks and NELL.

Table content: <table><tr><td>Label Rate</td><td/><td colspan="2">20 labels per class</td><td/><td colspan="2">4 labels per class</td><td>10%</td><td>1%</td><td>0.1%</td></tr><tr><td/><td>Cora</td><td colspan="3">CiteSeer PubMed Cora</td><td colspan="2">CiteSeer PubMed</td><td/><td>NELL</td><td/></tr><tr><td>ManiReg</td><td>59.5</td><td>60.1</td><td>70.7</td><td>-</td><td>-</td><td>-</td><td>63.4</td><td>41.3</td><td>21.8</td></tr><tr><td>SemiEmb</td><td>59.0</td><td>59.6</td><td>71.7</td><td>-</td><td>-</td><td>-</td><td>65.4</td><td>43.8</td><td>26.7</td></tr><tr><td>DeepWalk</td><td>67.2</td><td>43.2</td><td>65.3</td><td>-</td><td>-</td><td>-</td><td>79.5</td><td>72.5</td><td>58.1</td></tr><tr><td>ICA</td><td>75.1</td><td>69.1</td><td>73.9</td><td>62.2</td><td>49.6</td><td>57.4</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Planetoid</td><td>75.7</td><td>64.7</td><td>77.2</td><td>43.2</td><td>47.8</td><td>64.0</td><td>84.5</td><td>75.7</td><td>61.9</td></tr><tr><td>MLP</td><td colspan="7">56.7 (0.5s) 55.9 (0.6s) 69.1 (0.5s) 37.8 (0.5s) 39.6 (0.6s) 57.6 (0.5s) 63.7 (9.4s)</td><td>41.3 (4.9s)</td><td>21.5 (7.1s)</td></tr><tr><td>LP</td><td colspan="7">67.8 (0.4s) 43.9 (0.3s) 66.4 (1.2s) 60.9 (0.1s) 40.0 (0.2s) 62.6 (4.3s) 71.4</td><td>44.8</td><td>26.5</td></tr><tr><td>GCN</td><td colspan="9">79.5 (1.5s) 68.7 (2.3s) 77.2 (16s) 64.0 (1.8s) 56.4 (2.5s) 66.7 (17s) 81.6 / 82.1 (39s) 62.9 / 67.7 (33s) 39.1 / 58.2 (40s)</td></tr><tr><td colspan="10">GLP (RNM, MLP) 79.1 (0.5s) 67.6 (0.6s) 77.2 (0.5s) 68.4 (0.5s) 57.5 (0.6s) 67.2 (0.6s) 85.2 / 85.9 (49s) 77.4 / 78.8 (22s) 64.5 / 68.1 (26s)</td></tr><tr><td colspan="10">GLP (RW, MLP) 79.1 (0.5s) 67.7 (0.6s) 77.0 (0.5s) 68.5 (0.5s) 57.6 (0.6s) 67.2 (0.6s) 85.3 / 86.6 (87s) 77.4 / 79.5 (35s) 64.9 / 70.5 (39s)</td></tr><tr><td colspan="10">GLP (AR, MLP) 80.3 (0.5s) 68.3 (0.7s) 78.3 (0.5s) 69.4 (0.7s) 58.3 (0.9s) 68.7 (0.8s) 84.2 / 84.0 (487s) 63.9 / 66.1 (375s) 59.9 / 62.9 (637s)</td></tr></table>

Classification accuracy and running time on MNIST.

Table content: <table/>

CNN structure. × 5 × 32 with BN 28 × 28 × 32 Max-pooling 2 × 2 with BN 14 × 14 × 32 Conv. 3 × 3 × 64 with BN 14 × 14 × 64 Conv. 3 × 3 × 64 with BN 14 × 14 × 64 Max-pooling 2 × 2 with BN 7 × 7 × 64 Conv. 3 × 3 × 128 with BN 7 × 7 × 128 Conv. 1 × 1 × 10 with BN 7 × 7 × 10 Drop out 0.5 FC 490 × 10 with BN 10 ICA 2 implemented by Kipf and Planetoid implemented by Yang with their choices of parameters. Results of LP on NELL are also taken from Yang et al. (2016). All other results are reported by us.

Table content: <table><tr><td>Layer Structure</td><td>Output Size</td></tr><tr><td>Conv. 5</td><td/></tr></table>

Peer review (iclr2019):
 In classical Label Propagation (LP)-based semi-supervised learning, only the given graph structure and labelled data are taken account (e.g. in citation networks). However, this can be limiting as feature representations for data vertices (given by the matrix X) are not fully exploited. The proposed approach proposes to break this limitation. The authors consider LP from a signal processing perspective by showing that it behaves as a low pass filter: It amplifies contributions of small eigenvalues (of the graph Laplacian) and attenuate contributions of large eigenvalues leading to smoother signal. Such insight is exploited by replacing the input signal Y by X: Which has the result of smoothing features in X such as data points of the same class would have similar features. Then, a classifier is trained on the labelled data points using the filtered features. This classifier is finally used for classifying unlabelled data points. The authors reveal a connection between the proposed approach (GLP) and graph convolutional neural networks (GCN) by showing that the former is a special case of the first, which gives a natural and intuitive explanation to the inner workings of GCNS. Finally, experiments on 5 datasets have been conducted showing that the proposed approach consistently outperforms recent and classical semi-supervised approaches by a large margin, especially when the number of data points is very small. This paper is well motivated and written. However, the novelty is limited as similar ideas have been undertaken by [Hein and Maier 2007] although in different contexts. Although a discussion about [Hein and Maier 2007] has been provided in the related work section, it is not enough to faithfully compare both approaches. The authors should give proper credit to [Hein and Maier 2007] for the original ideas of smoothing the signal X and provide throughput qualitative and quantitative comparisons with [Hein and Maier 2007]: As stated by the authors, this approach is perhaps not directly applicable to citation networks. However, it is applicable to MNIST, and a comparison in this context is necessary. Also, it would be interesting to qualitatively compare the denoising ability of both approaches by showing some example images (on MNIST as provided by [Hein and Maier 2007]). In addition, I think this paper would benefit from: • Providing comparisons with recently proposed Gan-based semi-supervised approaches (e.g. Salimans et.al 2016) • Giving more details about hyper-parameter selection (alpha and k).