Unifying Graph Convolutional Neural Networks and Label Propagation
Authors: Hongwei Wang
Jure Leskovec
Venue:  (2020)
Keywords: graph convolutional neural networks
label propagation
node classification

Abstract: Label Propagation (LPA) and Graph Convolutional Neural Networks (GCN) are both message passing algorithms on graphs. Both solve the task of node classification but LPA propagates node label information across the edges of the graph, while GCN propagates and transforms node feature information. However, while conceptually similar, theoretical relation between LPA and GCN has not yet been investigated. Here we study the relationship between LPA and GCN in terms of two aspects: (1) feature/label smoothing where we analyze how the feature/label of one node are spread over its neighbors; And, (2) feature/label influence of how much the initial feature/label of one node influences the final feature/label of another node. Based on our theoretical analysis, we propose an end-to-end model that unifies GCN and LPA for node classification. In our unified model, edge weights are learnable, and the LPA serves as regularization to assist the GCN in learning proper edge weights that lead to improved classification performance. Our model can also be seen as learning attention weights based on node labels, which is more task-oriented than existing feature-based attention models. In a number of experiments on real-world graphs, our model shows superiority over state-of-the-art GCN-based methods in terms of node classification accuracy.


Under review as a conference paper at ICLR 2020
UNIFYING GRAPH CONVOLUTIONAL NEURAL NETWORKS AND LABEL PROPAGATION
Anonymous authors Paper under double-blind review
ABSTRACT
Label Propagation (LPA) and Graph Convolutional Neural Networks (GCN) are both message passing algorithms on graphs. Both solve the task of node classifi- cation but LPA propagates node label information across the edges of the graph, while GCN propagates and transforms node feature information. However, while conceptually similar, theoretical relation between LPA and GCN has not yet been investigated. Here we study the relationship between LPA and GCN in terms of two aspects: (1) feature/label smoothing where we analyze how the feature/label of one node spread over its neighbors; And, (2) feature/tabel influence of how much the initial feature/label of one node influences the final feature/label of an- other node. Based on our theoretical analysis, we propose an end-to-end model that unifies GCN and LPA for node classification. In our unified model, edge weights are learnable, and the LPA serves as regularization to assist the GCN in learning proper edge weights that lead to improved classification performance. Our model can also be seen as learning attention weights based on node labels, which is more task-oriented than existing feature-based attention models. In number of experiments on real-world graphs, our model shows superiority over sate-of-theeart GCN-based methods in terms of node classification accuracy.
INTRODUCTION
Consider the problem of node classification in graph, where the goal is to learn mapping M V ツー> C. from nodes V to labels L. Solution to this problem is widely applicable various scenarios, e.g., inferring income of users in a social network or classifying scientific articles in citation network. Different from generic machine learning problem where samples are independent from each other, nodes are connected by edges in the graph, which provide additional information and require more delicate modeling. To capture the graph information, researchers have mainly designed models the assumption that labels and features vary smoothly over the edges of the graph. In particular, on the label side L, node labels are propagated and aggregated along edges in the graph, which is known as Label Propagation Algorithm (LPA) (Zhu al., 2005; Zhou et al., 2004; Zhang & Lee, 2007; Wang & Zhang, 2008; Karasuyama & Mamitsuka, 2013; Gong et al., 2017: Liu et al., 2019a); On the node side V. node features are propagated along edges and transformed through neural network layers, which is known as Graph Convolutional Neural Networks (GCN) (Kipf & Welling, 2017: Hamilton et al., 2017: Li al., 2018; Xu et al., 2018; Liao et al., 2019; Xu al., 2019; Qu et al., 2019).
GCN and LPA are related in that they propagate features and labels on the two sides of the mapping M, respectively. However, the relationship between GCN and IPA has not yet been investigated. Specifically, what the theoretical relationship between GCN and IPA, and how can they be com- bined to develop more accurate model for node classification in graphs?
Here we study the theoretical relationship between GCN and LPA from two viewpoints: (I) Feature/label smoothing, where we show that the intuition behind GCN/LPA is smoothing fea- ture//lbels of nodes across the edges of the graph, i.e., one node's feature/label equals the weighted average of features/labels of its neighbors. We prove that if edge weights smooth the node features, they also smooth the node labels with guaranteed upper bound on the approximation error. And, (2) feature/label influence, where we quantify how much the initial feature/label of node v, influences

---

Under review as a conference paper at ICLR 2020
the output feature/label of node U, in GCN/LPA by studying the Jacobian/gradient of node v with respect to node Vo. and then we also prove their quantitative relationship.
Based on the above theoretical analysis, we propose unified model GCN-LPA for node classifi- cation. We show that the key to improving the performance of GCN is to enable nodes within the same class/label connect more strongly with each other by making edge weights/strengths train- able. Then we prove that increasing the strength of edges between the nodes of the same class is equivalent to increasing the accuracy of LPA'S predictions. Therefore, we can first learn the opti- mal edge weights by minimizing the loss of predictions in LPA, then plug the optimal edge weights into a GCN learn node representations and do final classification. In GCN-LPA, we further com- bine the two steps together and train the whole model in an end-to-end fashion, where the LPA part serves as regularization to assist the GCN part learning proper edge weights that benefit the separation of different classes. It is worth noticing that GCN-LPA can also be seen as learning at- tention weights for edges based on node label information, which requires less handcrafting and more task-oriented than existing work that learns attention weights based on node feature similarity (Veličković et al., 2018; Thekumparampil et al., 2018; Zhang et al., 2018; Liu et al., 2019b). Ex- periments five datasets indicate that our model outperforms state-of-the tfetth--rrt methods in terms of classification accuracy.
2 UNIFYING GCN AND LPA
In this section, we first formulate the node classification problem and briefly introduce LPA and GCN. We then prove their relationship from the viewpoints of smoothing and influence. Based on our theoretical analysis, we then propose a unified model GCN-LPA, and we also analyze the reason why our model performs better than GCN in node classification.
2.1 PROBLEM FORMULATION AND PRELIMINARIES
We begin by describing the problem of node classification on graphs and introducing notation. Con- sider graph G (V, A, X, Y), where V {u1.-... } is the set of nodes, e -R is the adjacency matrix (self-loops are included), X is the feature matrix of nodes and Y is labels of nodes. Gij (the ij-th entry of A) the weight of the edge connecting e and My. ((w) denotes the set of immediate neighbors of node v in graph g. Each node e; has feature vector which is the i-th row of X, while only the first m nodes have labels yı. Yn from label set (1, (1....,c).
The goal is to learn a mapping M: V + L and predict labels of unlabeled nodes.
Label Propagation Algorithm. I.AA assumes that two connected nodes are likely to have the same
label, and thus it propagates labels iteratively along the edges. Let (*()) = [v] , ,. Ur (k) E R'xe
be the soft label matrix in iteration > 0, in which the i-th row yi (R)T denotes the predicted label distribution for node By in iteration As When A = 0. the initial label matrix ( [v] (0) .3' (0)
consists of one-hot label indicator vectors y; for i 1. m (i.e., labeled nodes) or zero vectors otherwise (i.e., unlabeled nodes). Let D be the diagonal degree matrix for A with entries da = Σ, aij. Then LPA (Zhu et al., 2005) in iteration is formulated as the following two steps:
( D-1 1 ( (1+1) = yi (0) y:
y; Vi Vig m.
(2)
In Eq. (1), all nodes propagate their labels to their neighbors according to weights of edges. Then in Eq. (2), labels of all labeled nodes are reset to their initial values, because LPA wants to persist labels of nodes which are labeled so that unlabeled nodes do not overpower the labeled ones as the initial labels would otherwise fade away.
Graph Convolutional Neural Network. GCN is multi-layer feedforward neural network that propagates and transforms node features across the graph. The layer-wise propagation rule of GCN is (k+1) = o(D AD- & x ((()), where (K()) is trainable weight matrix in the k-th layer, a(.) is an activation function such as ReLU, and (*) [x{{]
(k) .... xx ( are the k-th layer node representations with ( X. To align with the above LPA, we use D-1 A the normalized adjacency matrix instead of the symmetric one D- 1 A proposed by Kipf & Welling (2017).
2

---

Under review as a conference paper at ICLR 2020
Therefore, the feature propagation scheme of GCN in layer & is:
( = Ax())
Notice similarity between Eqs. (1) and (3). Next shall study and uncover the relationship between the two equations.
2.2 FEATURE SMOOTHING AND LABEL SMOOTHING
The intuition behind both LPA and GCN is smoothing (Zhu et al., 2003; Li et al., 2018): In LPA, the final label of node is the weighted average of labels of its neighbors: yi (oc)
d:g ΣjeNio Aijli (oo);
in GCN, the final node representation is also the weighted average of representations of its neighbors we assume a is identity function and (+) are identity matrices: x!=) d.s ΣjeNo) )syx) (00)
Next we show the relationship between feature smoothing and label smoothing:
Theorem (Relationship between feature smoothing and label smoothing) Suppose that the latent ground-truth mapping M : x + from node features to node labels is differentiable and satisfies L-Lipschitz constraint, iee, [M(x1) - M(xx)] S L||x| - x2l12 for any x1 and X2 (L is constant). If the edge weights {aiz) approximately smooth over its immediate neighbors with error G, ie., X; dic EjENiO asyx; + Co then the edge weights {aiz} also approximately smooth ys over its immediate neighbors with the following approximation error: y/ dic EjEN()) ai5Uyl S Elleslle + of max - xxll2)). where olax) denotes a higher order infimitesiall than a.
Proof of Theorem is Appendix A. Theorem indicates that label smoothing is theoretically guaranteed by feature smoothing. Note that if we treat edge weights (aiz learnable, then feature smoothing (i.e., & - 0) can be directly achieved by keeping node features x; fixed while setting {a.j} appropriately, without resorting to feature propagation in a multi-layer GCN. Therefore, simple approach to exploit this thcorem would be learn {aiz} } by reconstructing node feature x; from its neighbors, then use the learned {a.}} } to reconstruct node labels y/ (Karasuyama & Mamitsuka, 2013). This is equivalent to first minimizing the difference between (0) and (L) by learning D- A in one-layer GCN where and (9) are identity, then plug the learned D-1 A in LPA and run for one iteration.
As shown in Theorem 1, the approximation error of labels is dominated by L|leel22- However, this error could be fairly large in practice because: (1) The number of immediate neighbors for a given node may be too small to reconstruct its features perfectly, especially in the case where node features are high-dimensional and sparse. For example, in a citation network where node features one-hot bag-of-words, vectors, the feature of one article never be precisely reconstructed if none of its neighboring articles contains the specific word that appears in this article. As result, |ealll will be non-neglib, This explains why it is beneficial apply LPA and GCN for multiple iterations/layers in order to include information from farther away neighbors. (2) The ground-truth mapping M may not be sufficiently smooth due to the complex structure of latent manifold and possible noise, which fails to satisfy L-Lipschitz constraint. In other words, the constant L will be extremely large.
2.3 FEATURE INFLUENCE AND LABEL INFLUENCE
To address the above concerns and extend our analysis, we next consider GCN and LPA with multi- ple layers/iterations, and do not impose any constraint the ground- -tuth mapping M.
Consider two nodes U, and 2, in a graph. Inspired by Koh & Liang (2017) and Xu et al. (2018), we study the relationship between GCN and IPA in terms of influence, i.e., how the output feature/label of va will change if the initial feature/label of Up is varied slightly. Technically, the feature/label influence is measured by the Jacobian/gradient of the output feature/label of v. with respect to the initial feature/label of up. Denote (8) as the k-th layer representation vector of v, in GCN, and x, as the initial feature vector of Ug. We quantify the feature influence of Us on H2 follows:
3

---

Under review as a conference paper at ICLR 2020
Definition 1 (Feature influence) The feature inftuence of node vs node va after layers of GCN the LI-norm of the expected Jacobian matrix (xa)) löx;; (Va, rb; k) = | [[xx
(k) /0xi] ll, The normalized feature influence is then defined as [ 0s; k) 1 (Va, ub; k)) Ewev I (Va, 0g k).
We also consider the label influence of node node Va in LPA (this implies that is unlabeled and Up is labeled). Since different label dimensions of y do not interact with each other LPA, we assume that all Yi and y." are scalars within [0, 1] (i.e., binary classification) for simplicity. Label influence is defined as follows:
Definition (Label influence) The label influence of labeled node v6 on unlabeled node va after iterations of LPA is the gradient of yo (k) with respect to yb: It(Va, vb;k) = Dya /0th.
The following theorem shows the relationship between feature influence and label influence:
Theorem (Relationship between feature influence and label influence) Assume the activation function used in GCN is ReLU. Denote va as unlabeled node, vo labeled node, and B as the fraction of unlabeled nodes. Then the label influence of up on va after k iterations of LPA equals, in expectation, to the cumulative normalized feature inftuence of us on vo after k layers of GCN:
B[ii(ua: Ub: = Σ j=1 (VI
(4)
Proof of Theorem 2 is in Appendix B. Intuitively, Theorem 2 shows that if vp has high label influence on Va. then the initial feature vector of v will also affect the output feature vector of e to a large extent. Theorem provides the theoretical guideline for designing our unified model in the next subsection.
2.4 THE UNIFIED MODEL
Before introducing the proposed model, first rethink the GCN method and what ideal node representation should be like. Since we aim to classify nodes, the perfect node representation would be such that nodes with the same label are embedded close together, which would give large separation between different classes. Intuitively, the key to achieve this goal is to enable nodes within the same class to connect more strongly with each other, so that they are pushed together by the GCN. We can therefore make edge strengths/weights trainable, then learn to increase the intra-class feature influence for each class i: Σn,, Fo........ 7 (Va, vb) by adjusting edge weights, However,
this requires operating on Jacobian matrices with the size of (()) d(K) (d(w) and d(K) are the dimensions of initial and output features, respectively), which is impractical if initial node features are high- dineeniiiinioonll. Fortunately, we can turn to optimizing the antra-class label influence instead, i.e., Ev. M.-y. =i..=. (va, 1b), according to Theorem 2. We further show that, by the following theorem, the intra-class label influence for given node va is proportional to the probability that vo classified correctly by LPA:
Theorem 3 (Relationship between label influence and LPA's prediction) Consider a given node Va and its label Yo- If we treat node Va as unlabeled, then the total label influence of nodes with label ya node va is proportional to the probability that node Ua is classified ya by LPA:
Ie Ubi k) xc Pr (gh. =ya).
(5)
where g/5e is the predicted label v. using a k-iteration LPA.
Proof of Theorem 3 is in Appendix C. Theorem indicates that, if edge weights {ayy} maximize the probability that e, is correctly classified by LPA, then they also maximize the intra-class label influence for node Ua- We therefore first learn the optimal edge weights A by minimizing the
4

---

Under review as a conference paper at ICLR 2020
loss of predicted labels by LPA:!
A arg min Lipa (A) = arg min
Σ
High yo),
(6)
A
A
where J is the cross-entropy loss, 1/tm and ya are the predicted label distribution of v using LPA and the true one-hot label of Va. respectively. a S. means Ca is labeled. The optimal A maximize the probability that each node is correctly labeled by LPA, thus also increasing the intra-class label influence (by Theorem 3) and intra-class feature influence (by Theorem 2). Then and the corresponding D to GCN to predict labels and learn optimal transformation matrices:
apply A'
( = A (K)
k 0 1--L,
W = arg min Lygen (W, A*) arg min W
Σ
J( :9a)
(8)
W
Vla Sm
where 8g (which is the a-th row of (()) is the predicted label distribution of Us using the GCN specified in Eq. (7).
In practice, it is generally better combine the above two steps together and train the whole model in an end-to-end fashion:
W A" = arg min Lgen (W, A) + XLipa (A),
W.A
where À is the balancing hyper-parameter. In this way. (Ap) serves as regularization term that assists the learning of edge weights A, since it is hard for the GCN to learn both W and A simultaneously due to overfitting. The proposed GCN-LPA approach can also be seen as learning the importance of edges that can be used to reconstruct node labels accurately by LPA, then transferring this knowledge from label space to feature space for the GCN. From this perspective, GCN-LPA also connects to Theorem except that the knowledge transfer is in the other direction.
It is also worth noticing how the optimal A" is configured. The principle here is that we do not mod- ify the basic structure of the original graph (i.e., not adding or removing edges) but only adjusting weights of existing edges. This is equivalent learning positive mask matrix M for the adjacency matrix A and taking the Hadamard product Mo. = A". Each element My can be set as either a free variable or a function the nodes at edge endpoints, for example, My = log (exp(x; Hx₃) + 1) where H is learnable kernel matrix for measuring feature similarity.
2.5 ANALYSIS OF GCN-LPA MODEL BEHAVIOR
In this subsection, we show benefits of our unified model compared with GCN by analyzing proper- ties of embeddings produced by the two models. We first analyze the update rule of GCN for node v;: (k) (())., where ä. = auj /dy is the normalized weight of edge (j. i). This formula can be decomposed into the following two steps: (1) In aggregation step, we calculate
x (l++1) a Σ (N())) ā.yx;
the aggregated representation h," (R) of all neighborhoods ((:x:): h
Eo,EN(r.) ) (k), (2) In
transformation step, the aggregated representation h (k) is mapped to a new space by a transforma- tion matrix and nonlinear function: (A++) a (b. (1) w())). We show by the following theorem that the aggregation step reduces the overall distance the embedding space between the nodes that connected in the graph:
Theorem 4 (Shrinking property in GCN) Let D(x) = = ăi |x, xx, 11 be distance met- ric between the embeddings x of nodes. Then we have (*) & ()x
'Here the optimal edge weights A' share the same topology the original graph G. meaning that we do add or remove edges from & hut only learning the weights of existing edges. See the end of this subsection for more discussion.
"Heee somewhat abuse the notations for simplicity, since in Theorem the two notations represent label category rather than label distribution. But the subtle difference can he easily distinguished based context.
5

---

Proof of Theorem 4 is in Appendix D. Theorem 4 indicates that the overall distance among con- nected nodes is reduced after taking one aggregation step, which implies that connected components in the graph "shrink" and nodes within each connected component get closer to each other in the embedding space. In an ideal case where edges only connect nodes with the same label, the aggre- gation step will push nodes within the same class together, which greatly benefits the transformation Under review as a conference paper at ICLR 2020
(a) Karate club network with noisy edges
(b) GCN the original network
(c) GCN-LPA the original network
(d) GCN the noisy network
(e) GCN-LPA the noisy network
Figure 1: Node embeddings of Zachary's 's karate club network trained on node classification task (red vs. blue). Node coordinates in (b)-(e) are the embedding coordinates. Notice that GCN does not produce linearly separable embeddings ((b) vs. (c)), while GCN-LPA performs much better even in the presence of noisy edges ((d) vs. (e)). Additional visualizations are included in Appendix
step that acts like a hyperplane (((k) for classification. However, two connected nodes may have different labels. These "noisy" edges will impede the formation of clusters and make the inter-class boundary less clear.
Fortunately, in GCN-LPA, edge weights are learned by minimizing the difference between ground- truth labels and labels reconstructed from multi-hop neighbors. This will force the model to increase weight/bandwidth of possible paths that connect nodes with the same label, so that labels can "flow" easily along these paths for the purpose of label reconstruction. In this way, GCN-LPA is able to identifyy potential intra-class edges and increase their weights to assist learning clustering structures.
To illustrate this, we apply two-layer untrained GCN with randomly initialized transformation matrices to the well-known Zachary's karate club network (Zachary, 1977) as shown in Figure la, which contains 34 nodes of classes and 78 unweighted edges (grey solid lines). We then increase the weights of intra-class edges by ten times to simulate GCN-LPA. We find that GCN works well on this network (Figure 1b), but GCN-LPA performs even better than GCN because the node em- beddings are completely linearly separable as shown in Figure Ic. To further justify our claim, we randomly add 20 "noisy" inter-class edges (grey dotted lines) to the original network, from which observe that GCN is misled by noise and mixes nodes of two classes together (Figure Id), but GCN- LPA still distinguishes the two clusters (Figure Ie) because is better at "denoising" undesirable edges based on the supervised signal of labels.
CONNECTION TO EXISTING WORK
Edge weights play a key role in graph-based based node classification as well as representation learning. In this section, we discuss three lines of related work that learn edge weights adaptively.
Locally linear embedding (LLE) (Roweis & Saul, 2000) and its variants (Zhang & Wang, 2007; Kong et al., 2012) learn edge weights by constructing linear dependency between node and its neighbors, then use the learned edge weights to embed high- nigh-dimensional nodes into low- dimensional space. Our work similar LLE in the aspect of transferring the knowledge of edge importance from one space to another, but the difference is that LLE is an unsupervised dimension reduction method that learns the graph structure based on local proximity only, while our work semi-supervised and explores high-order relationship among nodes.
Classical LPA (Zhu et al., 2005; Zhou et al., 2004) can only make use of node labels rather than node features. In contrast, adaptive LPA considers node features by making edge weights learnable. Typical techniques of learning edge weights include adopting kernel functions (Zhu et al., 2003; =xaa)² /a²) where d is dimensionality of features), Liu et al., 2019a) (e.g., dij Exp(-Eale (Wang & Zhang, 2008; Karasuyama & Mamitsuka, minimizing neighborhood reconstruction error
2013), using leave-one-out loss (Zhang & Lee, 2007), or imposing sparseness edge weights

---

Under review as a conference paper at ICLR 2020
(Hong et al., 2009). However, in these LPA variants, node features only used to assist learning the graph structure rather than explicitly mapped to node labels, which limits their capability in node classification. Another notable difference that adaptive LPA learns edge weights by introducing the regularizations above, while our work takes LPA itself as regularization to learn edge weights.
Our method is also conceptually connected to attention mechanisms graphs (Veličković al., 2018; Thekumparampil et al., 2018; Zhang et al., 2018; Liu et al., 2019b), in which an attention weight acj learned between node v; and Vj. For example, oij LeakyReLU(( [Wx:]] in GAT (Veličković et al., 2018), Oijj a cos W xi, W xxx in AGNN (Thekumparampil et al., 1018), ozy (Wix,) x, W2,, in GaAN (Zhang et al., 2018), and 0gj = a tanh Nonh(Wix + W2x,) GeniePath (Liu et al., 2019b). where a and W are trainable variables. A significant difference between these attention mechanisms and our work is that attention weights are learned based merely on feature similarity, while we propose that edge weights should be consistent with the distribution of labels on the graph, which requires less handcrafting of the attention function and is more task- oriented. Nevertheless, all the above formulas for calculating attentions can also be used our model as the implementation of edge weights.
x; />\::W>x [[Wx,))
EXPERIMENTS
We evaluate our model and present its performance on five datasets including citation networks and coauthor networks. We also study the dlyper-paaamete sensitivity and provide training time analysis.
4.1 DATASETS
We use the following five datasets in our experiments:
Citation networks: We consider three citation network datasets (Sen et al., 2008): Cora, Citeseer, and Pubmed. these datasets, nodes correspond documents, edges correspond to citation links, and each node has a sparse bag-of-wont feature vector as well as class label. Coauthor networks: We also use two co-authorship networks (Shchur et al., 2018), Coauthor-CS and Coauthor-Phy based on Microsoft Academic Graph from the KDD Cup 2016 challenge. Here nodes are authors and an edge indicates that two authors co-authored a paper. Node features represent paper keywords for each author's 's papers, and class labels indicate most active fields of study for each author.
Statistics of the five datasets are shown in Table 1. We also calculate the intra-class edge rate (the fraction of edges that connect two nodes within the same class), which is significantly higher than inter-class edge rate in all networks. The finding supports our claim in Section 2.5 that node classification benefits from intra-class edges in graph.
4.2 BASELINES
We compare against the following baselines in our experiments: Multi-layer Perceptron (MLP) and Logistic Regression (LR) are feature-based methods that do not consider the graph structure. Label Propagation (LPA) (Zhu et al., 2005), on the other hand, only consider the graph struc- ture and ignore node features. The rest of baselines are GCN-based methods: Graph Convolu- tional Network (GCN) (Kipf Welling, 2017) proposes a first-order approximation to spectral graph convolutions. Graph Attention Network (GAT) (Veličković et al., 2018) 8) propose an at- tention mechanism to treat neighbors differently in the aggregation step. Jumping Knowledge Networks (JK-Net) (Xu al., 2018) leverages different neighborhood ranges for each node to en-
Cora
Citeseer
Pubmed
Coauthor-CS
Coauthor-Phy
nodes
2,708
3,327
19.717
18,333
34,493
# edges
5,278
4,552
44,324
81,894
247,962
# fcatures
1,433
3,703
500
6,805
8,415
# classes
7
6
15
5
Intra-class edge rate
81.0%
73.6%
80.2%
80.8%
93.1% 1%
Table 1: Dataset statistics after removing self-loops and duplicate edges.
7

---

Under review as a conference paper at ICLR 2020
Method
Cora
Citeseer
Pubmed
Coauthor-CS
Coauthor-Phy
MLP
64.6 + 1.7
62.0
1.8
85.9 + 0.3
91.7
94.1 1.2
LR
77.3 + 1.8
71.2 = 1.8
86.0 0.6
91.1 0.6
93.8 + 1.1
LPA
85.3 0.9
70.0 1.7
82.6 0.6
91.3 0.2
94.9 + 0.4
GCN
88.2 1.210..0
77.3
1.5
87.2 0.4
93.6
96.2 +
GAT
87.7 + 0.3
76,2
+ 0.9
86.9 + 0.5
93.8 + 0.4
96.3 + 0.7
JK-Net
89.1 + 1.2
78.3
0.9
85.8 + 1.1
92.4 + 0.4
94.8 + 0,4
GraphSAGE
86.8 + 1.9
75.2
1.1
84.7
+ 1.6
92.6 1.6
94.5 + 1.1
GCN-LPA
88.5 + 1.5
78.7
= 0.6
87.8 0.6
94.8 =
96.9 + 0.2
Table 2: Mean and the 95% confidence intervals of test set accuracy for all methods and datasets.
Training time per epach (s)
Accuracy
Accuray
GOX lypet 1 lyees =
CON 1ye
nodes
Figure 2: Sensitivity to LPA
Figure Sensitivity to on Citeseer dataset.
Figure 4: Training time per epoch random graphs.
iterations Citeseer dataset.
able structure-aware representation. We use concat as the aggregator for JK-Net. Graph Sampling and Aggregation (GraphSAGE) (Hamilton al.. 2017) is mini-batch implementation of GCN that uses neighborhood sampling strategy and different aggregation schemes. We use mean as the aggregator for GraphSAGE.
4.3 EXPERIMENTAL SETUP
Our experiments focus the transductive setting where only know labels of part of nodes but have access to the entire graph as well as features of all nodes. The ratio training, validation, and test set set 6 training. We train our model for 200 epochs using Adam (Kingma & Ba, 2015) and report the test set accuracy when validation set accuracy is maximized. Each experiment is repeated three times and we report the mean and the 95% confidence interval. We initialize weights according to Glorot & Bengio (2010) and row-normalize input features. During training, we apply 1.2 regularization to the transformation matrices and use the dropout technique (Srivastava et al., 2014). The settings of all other parrmterraetters can be found in Appendix
2. The weight of each edge is treated as free variable during
4.4 RESULTS
The results of node classification are summarized in Table 2. Table 2 indicates that only using node features (MLP, LR) or graph structure (LPA) will lead to information loss and cannot fully exploit datasets in general. The results demonstrate that proposed GCN-LPA model surpasses state- of-the-art GCN/GNN baselines. We note that JK-Net is a strong baseline on Cora, but does not perform consistently well other datasets.
We investigate the influence of the number of LPA iterations and the training weight of LPA loss term À the performance of classification. The results Citeseer dataset plotted in Figures 2 and 3, respectively, where each line corresponds to given number of GCN layers in GCN-LPA. From Figure 2 we observe that the performance boosted first when the number of LPA iterations increases, then the accuracy stops increasing and decreases since large number of LPA itcrations will include more noisy nodes. Figure shows that training without the LPA loss term (i.e., 0) is more difficult than the case where A
5, which justifies our aforementioned claim that is
The experimental setting here is the same GCN (Kipf & Welling, 2017). But note that our method can he easily generalized inductive case if implemented in way similar to GraphSAGE (Hamilton et al., 2017).
8

---

Under review as a conference paper at ICLR 2020
Ratio of laheled nodes Accuracy
0%
20%
40%
600%
80%
100%
75.8 + 1.0
76.3 1 1.1
76.7
0.8
77.3 + 0.7
78.1 + 0.6
78.7 = 0.6
Table 3: Result of GCN-LPA on Citeseer dataset with differet ratio of labeled nodes in LPA.
hard for the GCN part to learn both transformation matrices W and edge weights A simultaneously without the assistance of LPA regularization.
To further show how much the LPA impacts the performance, we vary the ratio of labeled nodes LPA from 100% to 0% during training, and report the result of acuracy on Citeseer dataset in Table 3. From Table 3 we observe that the performance of GCN-LPA gets worse when the ratio of labeled nodes in LPA decreases. In addition, using more labeled nodes in LPA also helps improve the model stability. Note that ratio of 0% does not mean that GCN-LPA is equivalent to GCN (Kipf& & Welling, 2017) because the edge weights in GCN-LPA is still trainable, which increases the risk of overfitting the training data.
We study the training time GCN-LPA on random graphs. We use the one-hot identity vector feature and label for each node. The size of training set and validation is 100 and 200, respectively, while the rest is test set. The average number of neighbors for each node is set as 5, and the number of nodes is varied from one thousand to one million. We GCN-LPA and GCN for 100 epochs on a Microsoft Azure virtual machine with NVIDIA Tesla M60 GPU, 12 Intel Xeon CPUs (E5-2690 v3 (2.60GHz) and 128GB of RAM, using the same ayper-parameter setting as in Cora. The training time per epoch of GCN-LPA and GCN is presented in Figure 4. Our result shows that GCN- requires only 9.2% extra training time on average compared to GCN.
CONCLUSION AND FUTURE WORK
In this paper, we studied the theoretical relationship between two types of well-known graph-based models for node classification, label propagation algorithm and graph convolutional neural networks, from the perspectives of feature/label smoothing and feature/label influence. We then propose unified model GCN-LPA, which learns transformation matrices and edge weights simultaneously GCN with the assistance of I.PA regularizer. We also analyze why our unified model performs better than traditional GCN in node classification. Experiments on five datasets demonstrate that our model outperforms state-of-ther basclines, and it is also highly time-efficient with respect to the size of graph.
We point out two avenues of possible directions for future work. First, our proposed model focuses on transductive setting where all node features and the entire graph structure given. An interest- ing problem is whether it can be applied to inductive setting where we have no access to test nodes during training. Second, the question of how to generalize the idea of our model to GNNs with different aggregation functions (e.g., concatenation or max-pooling) is also promising direction.
REFERENCES
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the 13th International Conference Artificial Intelligence and Statistics, 2010.
Chen Gong, Dacheng Tao, Wei Liu, Liu Liu, and Jie Yang. Label propagation via teaching-to to- learn and learning-to-teach. IEEE Transactions Neural Networks and Learning Lystems, 28 (6), 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances Neural Information Processing Systems, 2017.
Cheng Hong, Zicheng Liu, and Jie Yang. Sparsity induced similarity measure for label propagation. In Proceedings of the 12th IEEE International Conference on Computer Vision. IEEE, 2009.
Masayuki Karasuyama and Hiroshi Mamitsuka. Samifold-basel similarity adaptation for label prop- agation. In Advances in Neural Information Processing Systems, 2013.

---

Under review as a conference paper at ICLR 2020
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In Proceedings of the 5th International Conference Learning Representations, 2017.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Deguang Kong, Chris Ding, Heng Huang, and Feiping Nie. An iterative locally linear embedding
algorithm. In Proceedings of the 29th International Coference International Conference Machine Learning. Omnipress, 2012.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In The 32nd AAAI Conference on Artificial Intelligence, 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Yanbin Liu, Juho Lee, Minscop Park. Sachoon Kim, Eunho Yang, Sung Ju Hwang, and Yi Yang. Learning to propagate labels: Transductive propagation network for few-shot learning. In Pro- ceedings of the 7th International Conference Learning Representations, 2019a.
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In The 33rd AAAI Conference on Artificial Intelligence, 2019b.
Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Sam T Roweis and Lawrence Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 290(5500), 2000.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rae Rad. Collective classification in network data. Al magazine, 29(3), 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In Neural Information Processing Systems Workshop Relational Representation Learning, 2018
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15(1), 2014.
Kiran K Thekumparampil. Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning. arXiv preprint arXiv: arXiv:/803.037355 2018
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua
Bengio. Graph attention networks. In Proceedings of the 6th International Conference on Learn ing Representations, 2018.
Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. IEEE Transac- tions on Knowledge and Data Engineering, 20(1), 2008
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, 2018
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, 2019.
Wayne W Zachary. An information flow model for conflict and fission in small groups Journal of anthropological research, 33(4), 1977.
10

---

Under review as a conference paper at ICLR 2020
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King. and Dit- Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXiv preprint arXiv:1803.07294, 2018.
Xinhua Zhang and Wee S Lee. Hyperparameter learning for graph based semi-supervised learning algorithms. In Advances in Neural Information Processing Systems, 2007.
Zhenyue Zhang and Jing Wang. Mile: Modified locally linear embedding using multiple weights. In Advances Neural Information Processing Systems, 2007.
Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learn- ing with local and global consistency. In Advances in Neural Information Processing Systems, 2004.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International Conference on Machine Learning, 2003.
Xiaojin Zhu, John Lafferty, and Ronald Rosenfeld. Semi-supervised learning with graphs. PhD thesis, Carnegie Mellon University, language technologies institute, school of, 2005.

---

Under review as a conference paper at ICLR 2020
APPENDIX
PROOF OF THEOREM
Proof. Denote ass atz du, as the normalized weight of edge (j. Is clear that Eje atj Given that M differentiable, we perform first-order Taylor expansion with Peano's form of remainder at x, for E)EN()) dzyUy:
Σ JEN(1)
ŪayUj = Σ Mxy)(xx))
JEN(O)
= Σ äij ( + 0M(x;)
(x, - -x;) + +ollx; xilla)
0x
JEN(1)
(10)
M(x)) + aM(x))
Σ āxy(x, -x,) + Σ
Tyo(lx - xx112)
0x
JEN(()
JEN(O)
OM(x;,
yı
0x
6
[1x| -x,112).
JEN(()
According to Cauchy-Schhie Schwarz inequality and L L-Lipschitz property, we have c
(.((x)))
a.M(x))
||G|/2
L|lc/l2-
(11)
0x
0x
Therefore, the approximation of ys is bounded by
Σ رزرزة
V1
JEN())
aM((x))
Σ
ā;jo(l|>; xil12)
8x
jEN(i)
(12)
OM(x;)
ā=)o(11z} xxl12) JEN(()
Σ
0x
L|lez|12 + o( max (||x; xx(12)).
JEN(s)
PROOF OF THEOREM
Before proving Theorem 2, first give two lemmas that demonstrate the exact form of feature influence and label influence defined this paper. The relationship between feature influence and label influence then be deduced from their exact forms.
Lemma 1 Assume that the nonlinear activation function in GCN is ReLU. Let Pa be path (u))), 1 1), ... _r00] of length k from node to node Ub, where (M) Ua 2(0)) and (( E (N( k....,.. Then we have
(v Ub; k) = Σ
II
0oti-11,000)
(13)
Pu sbikk
where 106 is the normalized weight of edge (v(0) (i(1))))
Proof.
See Xu et al. (2018) for the detailed proof.
The product tenm in Eq. (13) is the probability of given path Pg- Therefore, the right hand side in Eq. (13) is the sum over probabilities of all possible paths of length from Eú to Ug which the probability that random walk starting u, ends Us after taking & steps.
12

---

Under review as a conference paper at ICLR 2020
Va
Va
a
Vaa
V1
3/3
V1
3/
V1
V1
V3
4
V4
D4
V2
Vb
V2
Vb
1/2 Vb
1/2 Vb
(a) Iteration
(b) Iteration 2
(c) Iteration 3
(d) Paths from Wa
Figure 5: An illustrating example of label propagation in LPA. Suppose labels are propagated for three iterations, and no self-loop exists. Blue nodes are labeled while white nodes are unlabeled. (a) Va 's label propagates to v1 (yellow arrows). Note that the propagation of t label to by is cut off since vy is labeled thus absorbing va 's label. (b) Ua 's label that propagated to en further propagates to 02 and v (yellow arrows). Meanwhile, va label reset to its initial value then propagates from Va again (green arrows). (c) The propagating process in iteration 3. Purple arrows denote the propagation of v 's label starting from vo for the third time. (d) All possible paths of length no more than three from Vo to Up containing unlabeled nodes only. Note that there no path of length one from Va to
Lemma Let Up be path (u(0), (oli-1)..... w00 of length j from node Va to node vb, where أ(ار Va. (0)) tb. uli-1) ((((0) for = j..... ,,, and all nodes along the path are unlabeled except (0)) Then we have
[u Ubi k) ΣI
(n((=)),n(():
(14)
where ,069) the normalized weight of edge (v(0, ((i-))).
To intuitively understand this lemma, note that there are two differences between Lemma and Lemma 2: (1) In Lemma 1, (Va: 1g; 1g; sums over all paths from Va to Ub of length k, but in Lemma 2, Te(Wa, vs; k) sums over all paths from v. us of length no more than k. The is because in LPA, 44 's label reset its initial value after each iteration, which means that the label of us serves constant signal that begins propagating in the graph again and again after each iteration. (2) In Lemma 1 we consider all possible paths from U. to Up. but in Lemma 2, the paths are restricted to contain unlabeled nodes only. The reason here is the same above: Since the labels of labeled nodes are reset to their initial values after each iteration in LPA, the influence of 12 's label will be absorbed in labeled nodes, and the propagation of 2g 's label will be cut off at these nodes. Therefore, v% label can only flow to U, along the paths with unlabeled nodes only. See Figure 5 for an illustrating example showing the label propagation in LPA.
Proof. As mentioned above, a significant difference between LPA and GCN is that all laheled nodes are reset its original labels after each iteration in LPA. This implies that the initial label y,, of node Ur appears not only as y but also as every y for j = 1,... kk Therefore, the (k)
influence of yo on (1) is the cumulative influence of yb on yo for j 0, 1.... k---1
(1)
Li(Va, Ubi ubik) k) = OyA k-1
Oya (k)
(15)
By:
== Oyb
According to the updating rule of LPA, have
(k) i EesEN(EN))
dacy! (R-1)
Oy (k-1) Oaz
aya
ay
=
0
0yh
(1)
(16)
(v.)
(2) an
is decomposed into the weighted average of By (k-1)
In the above equation, the derivative where v. traverses all neighbors of va. For those us's that initially labeled, _ (k-1) is reset to
13

---

Under review as a conference paper at ICLR 2020
their initial labels in each iteration. Therefore, they always constant and independent of v/b meaning that their derivatives w.r.t. yb are zero. So we only need to consider the terms where Vg is an unlabeled node:
(6)
(5)
Öy
dy (k-1)
E
Oos (3)
(17)
0yb (3)
byb
where 2 > m means U2 is unlabeled. To intuitively understand Eq. (17), one can imagine that we perform random walk starting from node to for one step, where the "transition probability" is the edge weights å, and all nodes in this random walk are restricted to unlabeled nodes only. Note that
(k) further decompose every y²- (k-1) in Eq. (17) in the way similar to what do for yo in Eq. (16). So the expansion in Eq. (17) can be performed iteratively until the index & decreases to j.
This is equivalent performing all possible random walks for l: - j steps starting from Vas where all nodes but the last in the random walk are restricted to be unlabeled nodes:
ΣΣ Oy6 E
(k) Oya
II (ik--
d 1) 10,000
Oye
(18)
())
Oyb ()
where in the first summation term is the end node of a random walk, 2i in the second summa- tion term is an calabeleddnddes-oee path from Vo to of length k - j. and the product term is the
ayg
in Eq. (18). We know that ,y!") Byb GF
probability of a given path 2g Consider the last term
0y
for all * b and By
for z b, which means that only those random-walk paths that end exactly at 9b (i.e., the end node v, is exactly v²) count for the computation Eq. (18). Therefore, have
By
(k) Oy
Σ 4g
ā 1,,6), i=kj
II
(19)
0ub (3)
where Ug-)) is a path from va to ds of length k: j containing only unlabeled nodes except uh- Substituting the right hand term of Eq. (15) with Eq. (19), we obtain that
[V Ubi k) ΣΣ I
ΣΣΙ 1=
d 2000
(20)
j=0 Log i=k-j
Now Theorem can be proved by combining Lemma 1 and Lemma 2:
Proof. Suppose that whether node is labeled not is independent of each other for the given graph. Then we have
E (i( 0b1 A:)
=E
ΣΣΣ
Σ
Σ
II
2010))
E
14
i=j
Pr (Pg -b
is an cilabeled-nodes-onle path)
II
j=1 pa
(21)
dg3-1)
i=)
3 I (vas Db:
14

---

Under review as a conference paper at ICLR 2020
C PROOF OF THEOREM: 3
Proof. Denote the set of labels as L. Since different label dimensions in e do not interact with each other when running LPA, the value of the Yo yo-th dimension in y (denoted by y 2 [yo)) comes only from the nodes with initial label Ya. It is clear that
ya [ya]
E ΣEN
6,0 1,,00;
(22)
06:36 Ma 1=1 115145 b=j
which equals Emor v. 1u(ua Ubi k) according to Lemma 2. Therefore, we have
[ya]
Pr(ßa -oo)
(8) X Ma
[Wa]
Σ
Iv Ubi k)
(23)
Eiec ya
[1]
D PROOF OF THEOREM
In this proof we assume that the dimension of node representations is one, but note that the conclu- sion can be easily generalized to the case of mulli-dimennional representations since the function (xx) can be decomposed into the sum of one-dimensional cases. In the following of this proof, we
to denote node representations, but keep in mind that they are (R) and h (k) still use bold notations x,
scalars rather than vectors.
We give two lemmas before proving Theorem 4. The first one is about the gradient of D(x):
Lemma
h(a)
(1)
(D)x())
aD(x
(K) -x,x) EujeN((r) (x)(x) - (1)) )- = EmyeN(on Zzyx) h,
Proof.
x
0x!
It is interesting to see from Lemma 3 that the aggregation step in GCN is equivalent to running gradient descent for one step with a step size of one. However, this is not able guarantee that ((h(*) < (xx())) because the step size may be too large reduce the value of D.
The second lemma about the Hessian of Dxx):
Lemma 4 (x) 21, or equivalently, 21 D2D(x) is positive semidefinite matrix.
Proof.
We first calculate the Hessian of D(x) = Em,,,
ä:g
||: - x,113:
- ō11
ēin
221
0z2
02n
Dx)
D-D
(24)
-
1 ann
Therefore, 27 I+ D-1A. Since D-1A is Markov matrix (i.e., each entry is non- negative and the sum of each row is one), its eigenvalues are within the range [-1, 1], so the eigen- values of I + D ' A are within the range [0, 2]. Therefore, ++1 D-1 A is a positive semidefinite matrix, and we have V Dx) 27.
I
We can now prove Theorem 4:
Proof. Since D is quadratic function, we perform second-order Taylor expansion of around (k) and obtain the following inequality:
(()( = =D(x( + VD(x (+) ((k) (h - T x(())
-D(x(()) (x(x(() ( (1( (V2))()))TT=((VV(((()))))
(25)
()))(()) - ()) TV)((() + ()(
TVD(<()))V(((()))>)))))))))))>>) =D((x))
()) = D(x(+)).
15

---

Under review as a conference paper at ICLR 2020
1-layer
2-layer
3-layer
4-layer
(a) GCN on the original network
1-layer
2-layer
3-aayer
4-layer
(b) GCN-LPA on the original network
1-layer
layer
3-bayer
4-laycr
(c) GCN on the noisy network
1-layer
2 2-layer
3-layor
4-layer
(d) GCN-LPA on the noisy network
Figure 6: Visualization of GCN and GCN-LPA with layers on karate club network.
MORE VISUALIZATION RESULTS ON KARATE CLUB NETWORK
Figure 6 illustrates more visualization of GCN and GCN-LPA on karate club network. In each subfigure, we vary the number layers from to 4 to examine how the learned representations evolve. The initial node features are one-hot identity vectors, and the dimension of hidden layers and output layer is 2. The transformation matrices are uniformly initialized within range [-1, 1]. We sigmoid function the nonlinear activation function. Comparing the four figures in each row, we conclude that the aggregation step and transformation step GCN and GCN-LPA do benefit the separation of different classes. Comparing Figure 6a and 6с (or Figure 6b and 6d), conclude that more inter-class edges will make the separation harder for GCN (or GCN-LPA). Comparing Figure 6a and 6b (or Figure 6с and 6d), we conclude that GCN-LPA more noise-resistant than GCN, therefore, GCN-LPA can better differentiate classes and identify clustering substructures.
HYPER-PARAMETER SETTINGS
The detailed hyper-parameter settings for all datasets are listed Table 4. In GCN-LPA. we use the same dimension for all hidden layers. Note that the number of GCN layers and the number of LPA iterations can actually be different since GCN and LPA are implemented as two independent Cora, and perform fine-tuning
modules. We grid search to determine hyper-parament
16

---

Under review as a conference paper at ICLR 2020
Cora
Citeseer
Pubmed
Coauthor-CS
Coauthor-Phy
Dimension of hidden layers
32
16
32
32
32
# GCN layers
5
2
2
2
2
# LPA iterations
5
5
2
3
1.2 weight
10-4
x
10
x
10-4
1
10
1
10
I.PA weight (A)
10
2
1
Dropout rate
0.2
0
0
0.2
0.2
Learning rate
0.05
0.2
0.1
0.1
0.05
Table 4: Hyper--araaeeter settings for all datasets.
other datasets, i.e., varying one hyper-parameter per time see if the performance be further are as follows:
improved. The search spaces for
Dimension of hidden layers: {8, 16,36); 32):
# GCN layers:
(1,2, 6,
# LPA iterations: (1,2,3,4,5,6,7888,9)
1.2 weight:
(10-1,2x 10-1,5 10-7 10-9, 10-6, x 10-6 10-0, 2,, 10-5,5 x
10-5,10-4 10-
LPA weight (A): 10,
Dropout rate: (0,001,022.0330004,..33
Learning rate: (001,0002,000,,01,,,20.000
17


Reviews:
[{"review_id": "ryxzFyxAFr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a unified model which combines label propagation algorithm (LPA) and graph convolutional networks (GCNs) for node classification. The motivation of this combination is supported by two analysis on the feature/label smoothing and feature/label influence. The proposed GCN-LPA framework utilizeds LPA to adjust the edge weight A* through the label information. Then, this edge weight A* is used to transfer the knowledge from label information to feature information for enhancing the representation learning in GCN. An end-to-end  solution is proposed by treating the LPA process as regularization. Overall, the idea of unifying GCNs and LAP in an end-to-end fashion is interesting. \n\nOne major concern is that from the experiment, it is unclear how much the LPA impacts the node classification. It will be more convincing if the performance comparison under different percentage of labeled samples (during LPA) is provided. \n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "rkgeaF11cr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper connects graph convolutional networks with label propagation. There are a numbder of issues that need to be solved before possible publication.\nThe theoretical part (secion 2) is hard to follow. For example, the authors introduce in 2.1 a mapping M from vertices to labels. Then in Theorem 1, this mapping M indeed maps features of the vertices to labels. But then waht is the meaning of a L2 norms between features? At this point, I had a look in the experiment section to see what features are considered in practice. In section 4.1, it is written for the citation networks: 'each node has a sparse bag-of-words feature vector' or in the coauthor networks: 'Node features represent paper keywords for each author's paper'. How do you relate these claims to your theoretical analysis? Things get even worse in section 2.3, where derivatives with respect to initial feature vector are taken. How do you take a derivative with respect to a bag of words?\nEquation (5) is not clear at all, we need to read the end of this section to understand that A^* is constrained to have the same support as the adjacency graph and computed as a function of the node features. The authors shuold also define clearly y_hat in (5).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SygJVJ60YH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed an unified model for Label Propagation (LPA) and Graph Convolutional Neural Networks (GCN). It is shown how it is possible to infer the relationship between LPA and GCN in terms of label or feature smoothing (how label/feature does propagate over the neighbors) and label or feature influence over the other nodes. The results are given in terms of two theorems (whose proofs are in an appendix) which essentially state that the total label influence of nodes with a particular label “l” on a specific node is proportional to the probability that node is labelled as “l” by LPA. In practice, LPA acts as a regularizer to learn transformation matrices and edge weights simultaneously in GCN. By means of a simple joint loss (eq.8), the regularized training show that transductive learning with the joint model surpasses GCN/GNN baselines. \nWhile the proof of the first theorem is reasonable and seems correct (Taylor+ Schwarz inequality + L-Lip), the second left me a little puzzled, in particular wrt eq 16 and 17. Is it possible to add a graphical explanation or idea of the proof? Why “y” has to be reset at each iteration?\nUnfortunately, the improvement brought by the framework is marginal, even if it seems general. \nThe other limitation is that we have transductive training, but the authors are well aware about this.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors attempt to unify graph convolutional networks and label propagation and propose a model that unifies them. The reviewers liked the idea but felt that more extensive experiments are needed. The impact of labels needs to be specially studied more in-depth.
Decision: Reject