Unifying Graph Convolutional Neural Networks and Label Propagation
Authors: Hongwei Wang
Jure Leskovec
Venue:  (2021)
Keywords: graph convolutional neural networks
label propagation
semi-supervised 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, it is unclear how LPA and GCN can be combined under a unified framework to improve node classification. Here we study the relationship between LPA and GCN in terms of feature/label influence, in which we characterize how much the initial feature/label of one node influences the final feature/label of another node in GCN/LPA. Based on our theoretical analysis, we propose an end-to-end model that combines GCN and LPA. 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 the weights for edges based on node labels, which is more task-oriented than existing feature-based attention models and topology-based diffusion models. In a number of experiments on real-world graphs, our model shows superiority over state-of-the-art graph neural networks in terms of node classification accuracy.

Under review as a conference paper at ICLR 2021
UNIFYING GRAPH CONVOLUTIONAL NEURAL NET- WORKS 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, it is unclear how LPA and GCN can be combined under unified framework to improve node classification. Here we study the relationship between LPA and GCN in terms of feature/label influence, in which we char- acterize how much the initial feature/label of one node influences the final fea- ture/label of another node in GCN/LPA. Based on our theoretical analysis, we propose end-to-end model that combines GCN and LPA. In our unified model, edge weights are learnable, and the I.PA 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 the weights for edges based on node labels, which is more task-oriented than existing feature-based attention models and topology-basee graphs, model shows superiority over state-of-the-a graph neural networks in terms of node classification accuracy.
diffusion models. In a number experiments on real-world
INTRODUCTION
Consider the problem of node classification in graph, where the goal is to learn mapping M V + C from node set V to label set L. Solution to this problem is widely applicable to various scenarios, e.g., inferring income of users citation network. Different from a 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 on the assumption that labels/features are correlated over the edges of the graph. In particular, the label side L. node labels are propagated and aggregated along edges in the graph, which is known as Label Propagation Algorithm (LPA) (Zhu et 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 Graph Convolutional Neural Networks (GCN) (Kipf & Welling, 2017; Hamilton et al., 2017: Li et al., 2018; Xu et al., 2018; Liao et al., 2019; Xu al., 2019b; Qu et al., 2019).
social network or classifying scientific articles in
GCN and LPA are related in that they propagate features and labels on the two sides of the mapping M, respectively. Prior work Li et al. (2019) has shown the relationship between GCN and LPA in terms of low-pass graph filtering. However, it is unclear how the discovered relationship benefits node classification. Specifically, can GCN and LPA be combined to develop a more accurate model for node classification in graphs?
Here we study the theoretical relationship between GCN and LPA from the viewpoint of fea- ture/label influence, where we quantify how much the initial fcature/label of node Up influences
'There are methods in statistical relational learning Rossi et al. (2012) also using feature propaga- tion/diffusion techniques. In this work, we focus on GCN, but the analysis and the proposed model can be casily generalized to other feature diffusion methods.

---

Under review as a conference paper at ICLR 2021
the output feature/label of node Ue in GCN/LPA by studying the Jacobian//radiene of node vs with respect to node Va- We also prove the quantitative relationship between feature influence and label influence, i..,, the label influence of 2 on va equals the cumulative discounted feature influence of th on ea in expectation (Theorem 1).
Based on the theoretical analysis, we propose unified model GCN-LPA for node classification. We show that the key to improving the performance of GCN is to enable nodes of the same class connect more strongly with each other by making edge weights/strengths trainable. 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 (Theorem 2). Therefore, we can first learn the optimal edge weights by minimizing the loss of predictions in LPA, then plug the optimal edge weights into a GCN to learn node representations. In GCN-LPA, we further combine the above two steps together and train the whole model in 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 node classes. is worth noticing that GCN-LPA can also be seen learning the weights for edges based on node label information, which requires less handcrafting and is more task-oriented than existing attention models that learn edge weights based on node feature similarity (Veličković et al., 2018; The kumparampii et al.. 2018; Zhang et al., 2018; Liu et al., 2019b) or diffusion models that learn adjacency matrix based graph topology (Klicpera al., 201 90; Xu et al., 2019;; Abu-El-Haija et al., 2019; Klicpera et al., 2019b).
We conduct extensive experiments on five datasets, and the results indicate that our model outper- forms state-of-the-art graph neural networks in terms of classification accuracy. The experimental results also show that combining GCN and LPA together is able learn more informative edge weights thereby leading to better performance.
OUR APPROACH
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 feature influence and label influence. Based on the theoretical finding, we propose unified model GCN-LPA, and analyze why our model is theoretically superior to vanilla GCN.
2.1 PROBLEM FORMULATION AND PRELIMINARIES
where V {ur,... v..) is the set of nodes, A E R the adjacency matrix, X is the feature matrix of nodes and Y is labels of nodes. Usy (the ij-th entry of A) is the weight of the edge connecting e and Vy. .N(v) denotes the set of first-order neighbors of node in graph G. Each node i has feature vector x; which is the i-th row of X, while only the first mn nodes (m < n) have labels y1. Mm from a label set L = (1,...,, The goal is to learn mapping M V - L and predict labels of unlabeled nodes.
Consider graph 9 = (V,
Label Propagation Algorithm. LPA (Zhu et al., 2005) assumes that two connected nodes are likely to have the same label, and thus it propagates labels iteratively along the edges. Let y (b)
..... .... yo / E _R be the soft label matrix in iteration & > O, in which the i-th row y; (R)T denotes the predicted label distribution for node v; in iteration k. When k = 0, the initial label (0) for i = 1, ..... m
matrix (()) |y (0) ... ... 1/ ! consists of one-hot label indicator vectors y;
(i.e.. labeled nodes) or zero vectors otherwise (i.c., unlabeled nodes). Then LPA in iteration k is formulated as the following two steps:
y(+1)) = Ā (k), y (k+1) = y/ (0)
Vi < m.
(2)
In the above equations, Á is the normalized adjacency matrix, which can be the random walk tran- sition matrix A,w: = D-1 A or the symmetric transition matrix Asym = D- AD- where /) is the diagonal degree matrix for A with entries d, = Σ, dij. Without loss of generosity, we use À = Aym in this work. In Eq. (1), all nodes propagate labels to their neighbors according to nor- malized edge weights. Then in Eq. (2), labels of all labeled nodes are reset to their initial values,
2

---

Under review as a conference paper at ICLR 2021
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 Networks. GCN Kipf & Welling (2017) is multi-layer feedfor- ward neural network that propagates and transforms node features across the graph. The feature propagation scheme of GCN in layer is:
x(++1) = (Ax(*)
(3)
where W(k) trainable weight matrix in the k-th layer, a(.) is an activation function, and ((k [x] .... xT are the k-th layer node representations with X X. By setting the dimension of the last layer to the number of classes c, the last layer can be seen as (unnormalized)
label distribution predicted for a given node. The whole model can thus be optimized by minimizing the discrepancy between predicted node label distributions and ground-trume labels Y.
2.2 FEATURE INFLUENCE AND LABEL INFLUENCE
Consider two nodes v and 1y in a graph. Inspired by Koh & Liang (2017) and Xu al. (2018), we study the relationship between GCN and LPA in terms of influence, i.e., how the output feature/label of Ue will change if the initial feature/label of vs is varied slightly. Technically, the feature/label influence is measured by the Jacobian/gradient of the output feature/label of va with respect to the initial feature/label of ug- Denote x!1) as the k-th layer representation vector of va in GCN, and X² as the initial feature vector of Ub. We quantify the feature influence of Ub on Ua as follows:
Definition 1 (Feature influence) The feature inftuence of node Us on node after k layers of GCN
the LI-norm of the expected Jacobian matrix 0xa (K) /0x,; [v Ub; k) [0x (k) /0xo] 11.. The normalized feature influence is then defined as [ tb; k) = y (Va, Ub; k)/ Em,ey 1 (Vas 07; k).
We also consider the label influence of node on 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 in LPA,
we assume that all ys and (-) are scalars within [0, 1] (i.c., this is binary classification task) for simplicity. Label influence defined as follows:
Definition (Label influence) The label influence of labeled node vs on unlabeled node va after
iterations of LPA is the gradient of yo
(K) with respect to yb: Ir(Ua, k) = Oya /0yb-
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 an unlabeled node, vs as labeled node, and B as the fraction of unlabeled nodes. Then the label influence of ub on after k iterations of LPA equals, in expectation, to the cunulative normalized feature inftuence of Us on v, after is layers of GCN:
B[I Ub: k)] = Σ B
Proof of Theorem is in Appendix A. Intuitively, Theorem shows that if en has high label influence on US. then the initial feature vector of t will also affect the output feature vector of c, greatly. Theorem provides the theoretical guideline for designing our unified model in the next subsection.
2.3 THE UNIFIED MODEL.
Before introducing the proposed model, we rethink the GCN method and see what an ideal set of node representations should be like. Since we aim to classify nodes, the perfect node representation would be such that nodes with the same label are embedded closely together, which would give a large separation between different classes. Intuitively, the key 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 GCN (more discussion is presented in Section 2.4). We therefore make edge strengths/weights
3

---

Under review as a conference paper at ICLR 2021
trainable, then learn to increase the intra-class f influence: Eisc Ee, =. (v Vb) (C is the label set), by adjusting edge weights. However, this requires operating on Jacobian ma- trices with the size of d(0) x d) (d(o) and d' are the dimensions of input and output in GCN, respectively), which is impractical if initial node features are nigh-dimensional. Fortunately, we can turn to optimizing the intra-class label influence instead, i.e., LiEc Ln misii m.....i.. Ii(U,, ub), according to Theorem/ 1. Note that Eiec 2n..,b =1, =i (1 06) = = vo Lomm= 4e vt). We further show, by the following theorem, that the term Em Ii(va, Ub) (the total intra-class label influence on given node v,) is proportional to the probability that v, is classified correctly by LPA:
Theorem 2 (Relationship between label influence and LPA's prediction) Consider a given node Un and its label yo- If we treat node Va as unlabeled, then the total label influence of nodes with label ya on node va is proportional to the probability that node va is classified as ya by LPA:
Li(Vas Ubi k) x Pr (g = ya), ya),
(5)
where ih is the predicted label of Uo using a k-iteration IPA.
Proof of Theorem 2 is in Appendix B. Theorem indicates that, if edge weights {aiy} maximize the probability that va is correctly classified by LPA, then they also maximize the intra-class label influence on node Un- We can therefore first learn the optimal edge weights A by minimizing the loss of predicted labels by LPA:?
A" arg min Lipa (A) = arg min
Σ Vig Sm
J( yo).
(6)
m
where J is the cross-entropy loss, 1/th and la are the predicted label distribution of va using LPA and the true one-hot label of Ua. respectively. a < m means to labeled. The optimal A maximizes the probability that each node is correctly labeled by LPA, thus also maximizes the intra-class label influence (according to Theorem 2) and intra-class feature influence (according to Theorem 1). Since A increases the connection strength within each class, it is expected to improve the performance of GCN compared with the original adjacency matrix A. Therefore, we can plug A' into GCN to predict labels:
X
x("" A = 0, 1K
We use igem the a-th row of ((K), to denote the predicted label distribution of v, using the GCN specified in Eq. (7). Then the optimal transformation matrices in the GCN can be learned by minimizing the loss of predicted labels by GCN:
W = arg min Lyen (W,A*) = arg min
Σ Um
Joa (a))
(8)
W
m
is more elegant (and empirically better) to combine the above two steps together into a multi- objective optimization problem, and train the whole model in end-to-end fashion:
W A" = arg min T.gen (W, A) + XTipa (A),
W.A
where À is the balancing paper-parameter. In this way, Lipa (A) serves as a regularization term that assists the learning of edge weights A, since is hard for 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 GCN.
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.c., not adding or removing edges) but only adjusting weights of existing edges. This is equivalent to learning positive mask matrix M for the adjacency matrix A and taking the Hadamard product M o A = A Each element Mij can be set as either a free variable or a function of the two nodes, for example, M,j = log (exp(x; Hx,) + +1) where H is a learnable kernel matrix for measuring feature similarity.
Here the optimal edge weights A share the same topology as the original graph G. i.e. we do not add or remove edges from G but only learning the weights of existing edges. See the end of this subsection for more discussion.
4

---

Under review as a conference paper at ICLR 2021
2.4 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
oy: (1==1)
E (v))N((s) ū (+)(((()) W(k)), where üij = auz/ /ds is the normalized weight of edge (i, i). This formula can decomposed into the following two steps: (1) In aggregation step, we cal- culate the aggregated representation h;
(k) of all neighborhoods ((;): h." - -n 0 (k)
(2) In transformation step, the aggregated representation in!h) is mapped to new space by a transfor- mation matrix and nonlinear function: x; (k+1) o (h. that the aggregation step reduces the overall distance the embedding space between the nodes that are connected in the graph:
(8) w(()). We show by the following theorem
Theorem (Shrinking property in GCN) Let D(x) = Em م |x x, be a distance met- ric over node embeddings x. Then we have ((h(k)) S D(x(()).
Proof of Theorem 3 is in Appendix C. Theo- rem 3 indicates that the overall distance among connected nodes is reduced after taking one ag- gregation 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 ideal case where edges only connect nodes with the same label, the aggregation step will push nodes within the same class together, which greatly benefits the transformation step that acts like using hyperplane (k) for classification. However, two connected nodes may have dif- ferent labels. These "noisy" edges will impede the formation of clusters and make the inter- class boundary less clear.
(a) A graph with two classes of nodes
(b) Potential intra-class edges (bold links)
A graph with two classes of nodes, while white nodes are unlabeled (Figure Ia). To classify nodes, our model will increase the con- necting strength among nodes within the same class, thereby increasing their fcature/label influ- ence on each other. this way, our model is able identify potential intra-class edges (bold links in Figure 1b) and strengthen their weights.
Figure 1:
Fortunately, in GCN-LPA, edge weights are learned by minimizing the difference between ground-truth labels and labels reconstructed from local neighbors. This will force the model to increase the 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 identify potential intra-class edges and increase their weights to assist learning clustering structures see Figure for an illustrating example).
To empirically justify our claim, 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 2a, which contains 34 nodes of 2 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 this network (Figure 2b), but GCN-LPA performs even better than GCN because the node embeddings are completely linearly separable as shown in Figure 2c. To further justify our claim, we randomly add 20 "noisy" inter-class edges (grey dotted lines) the original network. from which we observe that GCN is misled by noise and mixes nodes of two classes together (Figure 2d), but GCN-LPA still distinguishes the two clusters (Figure 2c) because it is better at "denoising" undesirable edges based on the supervised signal of labels.
3 CONNECTION TO EXISTING WORK
Edge weights play a key role in graph- machine learning algorithms. In this section, we discuss three lines of related work that learn edge weights adaptively.
5

---

Under review as a conference paper at ICLR 2021
(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
Node embeddings of Zachary's karate club network trained on node classification task (red vs. blue). Figure 2a visualizes the graph. Node coordinates in Figure 2b-2e are the embedding coordinates. Notice that GCN does not produce linearly separable embeddings (Figure 2b vs. Figure 2c), while GCN-LPA performs much better even in the presence of noisy edges (Figure 2d vs. Figure 2e). Additional visualizations are included in Appendix D.
Figure 2:
Locally Linear Embedding. Locally linear embedding (LLE) (Roweis & Saul, 2000) and its vari- ants (Zhang & Wang, 2007; Kong et al., 2012) learn edge weights by constructing a linear de- pendency between node and its neighbors, then use the learned edge weights embed high- dimensional nodes into a low-dimensional space. Our work is similar to LLE in the aspect of trans- ferring 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 prox- imity only, while our work is semi-supervised and explores high-order relationship among nodes.
Label Propagation Algorithm. Classical LPA (Zhu et al., 2005; Zhou et al., 2004) can only make use of node labels rather than node features. 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; Liu et al., 2019a) (e.g., dij = exp(- - xza)² /o²) where d is dimensionality of features), minimizing neighborhood reconstruction error (Wang & Zhang, 2008; Karasuyama & Mamitsuka, 2013), using leave-one-out loss (Zhang & Lee, 2007), or imposing sparseness
edge weights (Hong et al., 2009). However, in these LPA variants, node features are 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 is that adaptive LPA learns edge weights by introducing the regularizations above, while our work takes LPA itself as regularization to learn edge weights.
Attention and Diffusion on Graphs. Our method is also conceptually connected to attention mech- anism on graphs, in which an attention weight oiy is learned between node v, and Uy. For example, aij = Leaky [W xxx [ll,,))) in GAT (Veličković al., 2018), aij in AGNN (Thekumparampiil et al., 2018), oij = (Wix;) W2x, in GaAN (Zhang et al., 2018), and oıj a tanh(W x, + W2x,) in GeniePath (Liu et al., 2019b), where a and W are trainable variables. Our method is also similar to liffusion-basee methods (Klicpera et al., 2019a; Xu et al., 2019a; Abu-El-Haija et al., 2019; Klicpera et al., 2019b; Jiang al., 2019; Yang al., 2019). Graph diffusion uses extended neighborhoods for aggregation in GNNs, which can be seen as learning a new adjacency matrix for given graph. significant difference between attention/diifusion mech- anisms and our work is that attention/diifusion is learned based on feature similarity/graphh topology, while we propose that edge weights should be consistent with the distribution of labels on the graph, which requires less handcrafting of the attention/difflsionn function and is more task-oriented.
cos cos(Wx, x, Wx,)
EXPERIMENTS
4.1 EXPERIMENT SETUP
Datasets. We use the following five datasets in our experiments. Cora, Citeseer, and Pubmed (Sen et al., 2008) are citation networks, where nodes correspond to documents, edges correspond to citation links, and each node has a sparse bag-of-worde feature vector as well as a class label. We also use two co-authorship networks (Shchur et al., 2018), Coauthor-CS and Coauthor-Phy, where nodes are authors and an edge indicates that two authors co-authored a paper. Node features represent paper keywords for each author's papers, and class labels indicate most active fields of

---

Under review as a conference paper at ICLR 2021
Method
Cora
Citeseer
Pubmed
Coauthor-CS
Coauthor-Phy
LR
57.1
2.3
61.0 = 2.2
3.11
86,4 0.9
86.7
LPA
74.4 + 2.6
67.8 = 2.1
7
73.6 3.9
86.6 2.0
GCN
81.4 + 1.3
71.9 = 1.9
91.1 0.5
92.4
GAT
80.7 1.3
71.4
76.7
90.5 0.6
92.2 0.9
JK-Net
81.3 +
1.4
70.2
1.3
77.6
90.3 0.4
91.0 0.7
GIN
74.5 + 1.5
60.7
= 1.3
73.4
+ 1.2
84.1 = 1.9
87.3 + 1.7
GDC
83.2 1
0.9
0.9
72.2
1 1.4
77.8
0.8
91.4 1.0
92.0 1 0.7
GCN+LPA
78.4
18.40.007
0.7
69.8
1 1.4
74.1
0.9
84.5 1.0
89.7 0.8
GCN-LPA
83.0 - 1.4
72.6
= 0.9
78.4 1.5
91.9 0.9
93.4 1.6
Table 1: Mean and the 95% confidence intervals of test accuracy for all methods and datasets.
Training time spoch (c)
GON-LPA
sccurary
03
DCV
00V 1pos
501 lave =
100C
Figure 3: Sensitivity to the number of LPA iterations Citeseer dataset.
Figure 4: Sensitivity to (weight of LPA loss) Cite- seer dataset.
Figure 5: Training time per epoch on random graphs.
study for each author. Statistics of the five datasets are shown in Appendix E. We also calculate the intra-class edge rate (the fraction of edges that connect two nodes within the same class), which significantly higher than inter-class edge rate in all networks. The finding supports our claim in Section 2.4 that node classification benefits from intra-class edges in a graph.
Baselines. We compare against the following baselines in our experiments. Logistic Regression (LR) is feature-based based methods that do not consider the graph structure. Label Propagation (LPA) (Zhu et al., 2005), on the other hand, only consider the graph structure and ignore node features. We also compare with several GNNs: Graph Convolutional Network (GCN) (Kipf & Welling, 2017), Graph Attention Network (GAT), Jumping Knowledge Network (JK-Net) (Xu et al., 2018), Graph Isomorphism Network (GIN) (Xu et. 2019b), and Graph Diffusion Convolution (GDC) (Klicpera al., 2019b) (with GCN as the base model). In addition, propose another baseline GCN+LPA, which simply adds predictions of GCN and LPA together.
Experimental Setup. Our experiments focus on the transductive setting where we only know labels of part nodes but have access to the entire graph as well as features of nodes.3 3 We randomly sample 20 nodes per class training set, 50 nodes per class validation set, and the remaining nodes as test set. The weight of each edge is treated as a free variable during training. We train model for 200 epochs using Adam (Kingma & Ba, 2015) and report the test accuracy when validation set accuracy is maximized. Each experiment repeated five 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 L2 regularization to the transformation matrices and use the dropout technique (Srivastava al., 2014). The settings of all other hyper- parameters can be found in Appendix F.
4.2 RESULTS
Comparison with Baselines. The results of node classification are summarized in Table 1. Table indicates that only using node features (LR) or graph structure (LPA) will lead information loss and cannot fully exploit datasets. The results demonstrate that our proposed GCN-LPA model surpasses state-of-the-art GNN baselines. We notice that GDC a strong baseline on Cora, but
*Our method can be easily generalized to inductive setting if implemented using minibatch training like GraphSAGE (Hamilton al., 2017).

---

setting Under review as a conference paper at ICLR 2021
Labeled node rate
5%
10%
20%
50%
80%
LPA
67.9 2.1
68.1 1.3
70.5 + 1.5
72.5 1 1.2
76,4 1.1
GCN
72.1 + 1.9
72.5 + 1.8
74.3
+ 0.9
76.8 + 0.6
80.2 - 1.5
GCN-LPA
72.7 + 1.2
73.2 = 1.1
75.4 1.5
78.2 1.3
82.3 + 0.9
Table 2: Accuracy of LPA, GCN, and GCN-LPA on Citeseer with different labeled node rate.
does not perform consistently well on other datasets. In addition, GCN+L.PA does not perform well, since it utilizes the prediction of LPA directly, making its performance limited by LPA.
Efficacy of LPA Regularization. We investigate the influence of the number of LPA iterations and the training weight of LPA loss term À the performance of classification. The results on Citeseer dataset are plotted in Figures 3 and 4, respectively, where each line corresponds to a given number of GCN layers in GCN-LPA. From Figure we observe that the performance is boosted at first when the number of LPA iterations increases, then the accuracy stops increasing and decreases since a large number of LPA iterations will include more noisy nodes. Figure 4 shows that training without the LPA loss term (i.e., À = 0) is more difficult than the case where À = 1 ~ 5, which justifies our aforementioned claim that it is hard for the GCN part to learn both transformation matrices W and edge weights A simultancously without the assistance of LPA regularization.
Influence of Labeled Node Rate. To study the influence of labeled node rate on the performance of our model, we vary the ratio of labeled node rate on Citeseer from 5% to 80% while keeping the validation and test set fixed, and report the result in Table 2. From Table we observe that GCN-LPA outperforms GCN and IPA consistently, and the improvement achieved by GCN-LPA increases when labeled node rate is larger (from 0.6% to 2. 2.1% compared with GCN). This because GCN-LPA requires node labels to calculate edge weights. Therefore, larger labeled node rate will provide more information for identifying noisy edges.
Visualization of Learned Edge Weights. To intuitively understand what our model learns about edge weights. we split nodes in Coauthor- CS dataset into 15 groups according their labels, and calculate the average weights of edges connecting every pair of node groups as well the average weights of edges within every group. The results are shown in Figure 6, where darker color indicates higher average weights of edges. It is clear that values along the diagonal (intra-class edges weights) are significantly larger than off-diagonal values (inter-class edge weights) in general, which demonstrates that GCN-LPA is able to identify the importance of edges and distinguish inter-class and intra- class edges. The visualization results are similar for other datasets.
10
Figure 6: Visualization of learned edge weights in Coauthor- CS dataset.
Time Complexity. We study the training time of GCN-LPA on random graphs. We use the one-hot identity vector as feature and 0 as label for each node. The size of training set and validation set 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 run 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 as in Cora. The training time per epoch of GCN-LPA and GCN is presented in Figure 5. Our result shows that GCN-LPA requires only 9.2% extra training time on average compared GCN.
CONCLUSION
We studies the theoretical relationship between two types of well-known graph-based algorithms for node classification, label propagation algorithm and graph convolutional neural networks, from the perspectives of feature/label influence. We then propose unified model GCN-LPA, which learns transformation matrices and edge weights simultaneously in GCN with the assistance of LPA regularizer. We also analyze why our unified model performs better than traditional GCN in terms of node classification. Experiments on five datasets demonstrate that our model outperforms state- of-the-art baselines, and it is also highly time-efficient with respect the size of graph.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 36th International Con- ference on Machine Learning, pp. 21-29, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, 2010.
Chen Gong, Dacheng Tao, Wei Liu, Liu Liu, and Jie Yang. Label propagation via teaching-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 in 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.
Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph learning-come convolutioalll networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 11313-11320, 2019.
Masayuki Karasuyama and Hiroshi Mamitsuka. Manifold- basteddddbaddddddd similarity adaptation for label prop- agation. In Advances in Neural Information Processing Systems, 2013.
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 Sth International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Proceedings of the 7th International Conference on Learning Representations, 2019a.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In Advances in Neural Information Processing Systems, pp. 13354-13366, 2019b.
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 on International Conference on 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.
Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi- suuervised learning via graph filtering. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9582-9591, 2019.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanezosnet: Multi-scale deep graph convolutional networks. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Yanbin Liu, Juho Lee, Minseop 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.

---

Under review as a conference paper at ICLR 2021
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.
Ryan A Rossi, Luke K McDowell, David William Aha, and Jennifer Neville, Transforming graph data for statistical relational learning. Journal of Artificial Intelligence Research, 45:363-441, 2012.
Sam T Roweis and Lawrence K 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-Rai -add Collective classification in network data. Al magazine, 29(3), 2008.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In Neural Information Processing Systems Workshop on 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 Jourmal 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:1803.037.3. 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro 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
Binghing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional networks using heat kernel for semi-supervised learning. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 1928-1934. AAAI Press, 2019a.
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 Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, 2019b.
Liang Yang, Zesheng Kang, Xiaochun Cao, Di Jin, Bo Yang, and Yuanfang Guo. Topology opti- mization based graph convolutional network. In IJCAI, pp. 4054-4061, 2019.
Wayne W Zachary. An information flow model for conflict and fission in small groups Journal of anthropological research, 33(4), 1977.
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 arX1v:1803.07294, 2018.
Xinhua Zhang and Wee S Lee. Hyperparameter learning for graph based sumi-super 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 in Neural Information Processing Systems, 2007.
10

---

Under review as a conference paper at ICLR 2021
Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learn- ing with local and global consistency. Advances 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, school of language technologies institute, 2005.

---

Under review as a conference paper at ICLR 2021
APPENDIX
A PROOF OF THEOREM
Before proving Theorem 1, we first give two lemmas that demonstrate the exact form of feature influence and label influence defined in this paper. The relationship between feature influence and label influence can then be deduced from their exact forms.
Lemma Assume that the nonlineur activation function in GCN ReLU. Let PR be path (v)(k), v((-1),, ,... _vO' of length from node Va to node Vb. where e(k) = Va vil)) = Ub. and w)l-11 1) E (N(( h ...... 1. Then we have
1 Ub: k)
-EII dyee 11,0000
(10)
Pg-bi=k i=
where 1165) is the normalized weight of edge (vl1) (((-1)))
Proof. See Xu et al. (2018) for the detailed proof.
The product term in Eq. (10) the probability of a given path Pg- Therefore, the right hand side in Eq. (10) is the sum over probabilities of all possible paths of length k from Uo to Ug which is the probability that a random walk starting Ua ends at 1s after taking steps.
Lemma 2 Let Ug be path (u(0), w(i-1),.... [.0) of length from node node uh. where أوا Va. v0)) ob, wli-1) E ((v(0) for -.. 1, and all nodes along the path are unlabeled except (0)) Then we have
k
Li Ubi k) = ΣΣ (n(1-1),nt))
(11)
where dy6 11,60 is the normalized weight of edge (v((), 1(1-))).
To intuitively understand this lemma, note that there two differences between Lemma 1 and Lemma 2: (1) In Lemma 1, (Va; U9; k); sums over all paths from va to eb of length k; but in Lemma 2, Te(Va, vs; k) sums over all paths from v. to th of length no more than k. The is because in LPA, Ub 's label reset its initial value after each iteration, which means that the label of us serves as a constant signal that begins propagating in the graph again and again after each iteration. (2) In Lemma I we consider all possible paths from v, to vG, but in Lemma 2, the paths are restricted to contain unlabeled nodes only. The reason here is the same as above: Since the labels of labeled nodes are reset to their initial values after each iteration in LPA, the influence of to 's label will be absorbed in labeled nodes, and the propagation of Vb 's label will be cut off at these nodes. Therefore, vy," 's label can only flow to v, along the paths with unlabeled nodes only. See Figure for an illustrating example showing the label propagation in LPA.
Proof. As mentioned above, a significant difference between LPA and GCN is that all labeled nodes are reset to its original labels after each iteration in LPA. This implies that the initial label
ys of node 2s appears not only as y/
(5) for j = ... A Therefore, the influence of yo on yo is the cumulative influence of ()) (k)
(0) but also as every yb
(k)
yo for j 0. ,k-1 1:
Oyla
k-
Oya (k)
Ii(Va, Ub; k)
(12)
Byh
1=0 Ouo
According to the updating rule of LPA, we have
Oya
0 E
EeyEN(e.)
CazVz
(k-1)
Oy: 1k-1)
Oaz
(13)
0yb
( 0yy (5)
01b
(1)
(r.))
12

---

Under review as a conference paper at ICLR 2021
Va
Va
V1
V
V'
x
V/3
V/
Pi
V1
V1
P4
V4
1/4
1/ 1/b
Vb
V/2 Db
V/ Vp
(d) Paths from Va to
(a) Iteration
(b) Iteration 2
(c) Iteration 3
1/b
Figure 7: 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) Ua 's label propagates to U1 (yellow arrows). Note that the propagation of 02 label to it is cut off since vy is labeled thus absorbing va 's label. (b) va 's label that propagated to #1 further propagates to U2 and (yellow arrows). Mcanwhile, % 's label is reset to its initial value then propagates from Va again (green arrows). (c) Label propagation in iteration Purple arrows denote the propagation of 's label starting from ta for the third time. (d) All possible paths of length no more than three from Va to 2/ containing unlabeled nodes only. Note that there is no path of length one from va to Ub.
In the above equation, the derivative (g(h) is decomposed into the weighted average of By th ay.
0yh
where E2 traverses all neighbors of Va. For those v, 's that are initially labeled, y (k-1) is reset to
their initial labels in each iteration. Therefore, they are always constant and independent of y/ meaning that their derivatives w.r.t. yb are zero. So only need consider the terms where v. is an unlabeled node:
Öy:
(k)
Oy 1k-1)
E
Oos
(14)
Oy (1)
Ou
where 2 > m means v, is unlabeled. To intuitively understand Eq. (14), one can imagine that we perform random walk starting from node vn for one step, where the "transition probability" the edge weights a, and all nodes in this random walk are restricted to unlabeled nodes only. Note that we can further decompose every y/ (k-1) in Eq. (14) in the way similar to what we do for yo*) in Eq. (13). So the expansion in Eq. (14) can be performed iteratively until the index & decreases to j.
This is equivalent performing all possible random walks for -- j steps starting from ea, where all nodes but the last in the random walk are restricted to be unlabeled nodes:
(N) aya ay.
Σ EVU
II (=k-)
1)(1-)) .019)
(15)
())
where u, in the first summation term is the end node of random walk, 24- in the second summa- tion term is unlabeled-nodes-onn path from U. to of length k - j. and the product term is the
(y
By 135 in Eq. (15). We know that an By.
probability of given path 24 Consider the last term
for all z # b and (2)
for = = b, which means that only those random-walk paths that end exactly at Us (i.c., the end node v, is exactly vt) count for the computation in Eq. (15). Therefore, have
ty! (K)
Σ
II ap1t-1),000
(16)
where Ug is a path from to U9 of length h containing only unlabeled nodes except Substituting the right hand term of Eq. (12) with Eq. (16), we obtain that
Tu(ua bb; k)
ΣΣ
II
Σ j=1
deit 10,000)
(17)
5= 12
u
i=
13

---

to denote node representations, but keep in mind that they are Under review as a conference paper at ICLR 2021
Now Theorem can be proved by combining Lemma 1 and Lemma 2:
Proof. Suppose that whether a node is labeled or not is independent of each other for the given graph. Then we have
(li 06; kb;
=E
dest 2000
I 2
a
1,0-11,008
Leg
j=1
Pr (P an unlabeledd-nods--nnly path)
II doit 1,06)
(18)
1=1
pe
3d
1)
3 ((Va: Ub:j). Σ
pa-s
im
j=1
B PROOF OF THEOREM? 2
Proof. Denote the set of labels L. Since different label dimensions in ya do not interact with each other when running LPA, the value of the yo-th dimension in y!? (denoted by yá (-) (ya)) comes only from the nodes with initial label Yu- It is clear that
ya [al
E 0B
ΣIΙ a 10001,,00
(19)
U5 46 1=
which equals E Ee..goy. [u(Ve Ub: k) according Lemma Therefore, we have
Pr(όa = yo) = ya
[aal
x ya
(k) yal = Σ
4( Ubi k)
(20)
Eiec Va
[1]
06:366
C PROOF OF THEOREM 3
In this proof sion can be easily generalized to the case multi-dimensional representations since the function
that the dimension of node representations is one, but note that the conclu-
D(x) can be decomposed into the sum of one-dimensional cases. In the following of this proof,
still use bold notations x (k) and h (k) scalars rather than vectors.
We give two lemmas before proving Theorem 3. The first one is about the gradient of D(x):
Lemma
x
(k)
(N)
8x!*
Proof.
(k)
(k)
(8) - (k)) (x)) = EeyeN(es) x (1) EvjeN(a)) (x
h
ax
interesting to see from Lemma that the aggregation step GCN is equivalent to running gradient descent for one step with step size of one. However, this is not able to guarantee that (+) (x)( because the step size may be too large to reduce the value of D.
The second lemma about the Hessian of Dxx):
Lemma 4 (x) A 27, or equivalently, 21 D2D(x) is positive semidefinite matrix.
14

---

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 on Under review as a conference paper at ICLR 2021
Proof.
We first calculate the Hessian of D(x)
5 E,,,, dsyl[x; x211ă
1
Oin
021
d22
U2n
D²D(x)
-- -I-D-A.
(21)
0n1
2n2
1 ann
Therefore, 2/ - = D- Since D 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-1 A are within the range [0, 2]. Therefore, I+ D-1 1A is positive semidefinite matrix, and we have Dx) 2/.
= =
We can now prove Theorem 3:
Proof. Since D is a quadratic function, we perform second-order Taylor expansion of around ((k) and obtain the following inequality:
()h( =D(x( VD( (h (x)) + - - -=)"== -x(1)
x()))
= ()) VD(x TVDxX( + [xx(())) ( (<>(x/)>)))))
(22)
(1)x V TVD(x() ()(x(()) VD(x TVD()
-D(x(A))
D MORE VISUALIZATION RESULTS ON KARATE CLUB NETWORK
Figure 8 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 use sigmoid function as 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 8a and 8c (or Figure 8b and 8d), conclude that more inter-class edges will make the separation harder for GCN (or GCN-LPA). Comparing Figure 8a and Sb (or Figure 8c and 8d), we conclude that GCN-LPA more noise-resistant than GCN, therefore, GCN-LPA can better differentiate classes and identify clustering substructures.
E DATASETS DETAILS
The statistics all datasets are shown Table 3.
Cora
Citeseer
Pubmed
Coauthor-CS
Coauthor-Phy
# nodes
2,708
3,327
19,717
18,333
34,493
# edges features
5,278
4,552
44.324
81,894
247,962
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%
Laheled node
5.2%
3.6%
0.3%
1.6%
0.3%
Table 3: Statistics for all datasets.
F HYPER-PARAMETER SETTINGS
modules. We use grid search to determine hyper-paramette
15

---

Under review as a conference paper at ICLR 2021
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-layer
4-layer
(d) GCN-LPA on the noisy network
Figure Visualization of GCN and GCN-LPA with
layers on karate club network.
Cora
Citeseer
Pubmed
Coauthor-CS
Coauthor-Phy
Dimension of hidden layers
32
16
32
32
32
GCN layers
2
# LPA iterations
L2 weight
x 10
5 x 10
2 x 10
x 10
x 10-4
LPA weight (A)
10
Dropout rate
0.2
0.2
0.2
Learning rate
0.05
0.05
Table 4: Hyper-parameter settings for all datasets.
other datasets, i.e., varying one hyper-parameter per time to see if the performance can be further improved. The search spaces for papammerrrseters follows:
Dimension of hidden layers: {8, 16, 32):
# GCN layers:
(1,2,3, 4, 5)6;;;
# LPA iterations: (1,2,3,4,5,6,
I.2 weight: (10-7,2x x 10-7, 10-6,2 10-6,5 10-6 10-50 x 10-5,5
10-5,10-4 10-4, x 10-1,5 10-1,10-3);
LPA weight (A): 1,,
16

---

Under review as a conference paper at ICLR 2021
Dropout rate:
Learning rate: (0.01,0.02, 0.05, 0.2,
17


Reviews:
[{"review_id": "vU3hkNqDkf", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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 aims to combine the label propagation and graph convolutional network with the modeling of their latent relationships. In the developed model, the node label is utilized to infer the edge weights between different nodes. From the evaluation results in Section 4, the performance improvement between the proposed method GCN-LPA and GDC is marginal, which can hardly demonstrate the advantage of the unified model (with GCN and LPA) over the graph diffusion network (without the restriction of information aggregation over neighboring nodes).\n\nFurthermore, this work generates another baseline with the combination of prediction GCN and LPA methods. From the evaluation results, this baseline performs much worse than GCN and GAT, which may indicate that the predict combination involves some noise. It is better to conduct further experiments to show the effectiveness of the proposed GCN and LPA integration mechanism over simplified combination.\n\nA minor note would be the lack of detailed hyperparameter tuning strategies of compared baselines. Different parameter settings may offer different performances; thus, it would be better to report how to perform the parameter tuning over various compared methods (such as GAT, GCN and GDC), to achieve good model performance and ensure a fair performance comparison.\n\nThe proposed method incorporates the label propagation to calculate edge weights, which share similar paradigm for learning node correlations with graph attention network and its extensions. In addition to the performance gap between the GCN-LPA and GAT, more clarifications about the model difference could be added, to have a better understanding of the new combined GCN and LPA framework.\n\nIt would be better to show the performance as the training/test ratio varies. It will be interesting to see is more data helpful to capture graph structural information better.\n\nIn the experiments, only model scalability comparison between the new GCN-LPA method and GCN, is studied. Is the GCN-LPA more efficient than other baselines, and which component of the new framework is more computationally expensive?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "F4K3sTuzGnt", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "##########################################################################\nSummary:\n \nThe manuscript proposes a unified model which combines label propagation algorithm (LPA) and graph convolution network (GCN). The main idea is to optimize edge weights (after making edge weights trainable) by maximizing the intra-class feature influence. Introducing the theorems on the relationship between feature and label influence, and LPA’s prediction, the authors propose the unified objective function (a summation of the GCN loss and LPA loss) which combines both methods.   \n##########################################################################\nReasons for score: \n \nOverall, I vote for accepting. The manuscript is overall well written, and the motivation of the proposed method is well explained by the proposed theorems. The logic leading to the objective function sounds reasonable and interesting. However, the manuscript still seems to need some clarifications. \n \n##########################################################################Pros: \n \n1.\tThe manuscript provides a new theoretical viewpoint to combine LPA and GNN.\n2.\tThe proposed method outperforms the baselines, including some state-of-the-art Methods. \n \n##########################################################################\nCons: \n \n1. The method is a transductive method (test data points should are present during training) although the authors briefly mentioned the possibility of extension to inductive learning. I think that additional specialized effort is needed to extend label propagation in inductive setting. I think this is one of main weakness of the model.\n2. Regarding the term regularization term for the LPA loss. This is generally referring to a penalty term on a penalty on the model complexity. I think that it is more appropriate if the authors introduced the proposed objective function as a simple implementation of multi-objective optimization.   \n  \n#########################################################################\nQuestions:\nIn the experimental results. “In addition, we propose another baseline GCN+LPA, with simply adds predictions of”: It is not clear how to combine the prediction solutions from both methods (adding predictions in different scales?). \n\nFor Figure 5. What is the sparseness of edges in the random graphs? GCN-LPA has additional many parameters (the size is equal to the number of non-zero edges in the graph) compared to GCN. I expected that the time complexity of GCN-LPA would be way larger than that of GCN. Is this experimental setting close to real prediction problems?  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "F0yHwmUw57", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 combines the label propagation algorithm (LPA) and graph convolutional neural networks (GCNs) and proposes a unified model with learnable edge weights utilizing both feature and label influence.\nThe theoretical analysis of the correlation between LPA and GCN is interesting. Based on the theoretic analysis they show that the key to improving the performance of GCN is to enable nodes of the same class to connect more strongly, thus they propose to use LPA to reweight the edges and then use the new edge weights for GCN. However, their final model jointly learns edge weights with both LPA and GCN, which is acceptable but might reduce the connection to the theory. \nMoreover, my main concerns are about the experiments. \n(1)\tSome of the baselines do not match the results reported in the original paper (e.g. GAT has much better performance than the numbers reported in Table 1); and the improvement of accuracy is actually marginal on most datasets. It will be better if the authors can analyze in which condition or on what types of datasets GCN-LPA works better. \n(2)\tI would like to see an ablation study which removes the LPA loss (\\lambda L_{lpa}(A)) or replaces it with l2 regularization in Equation (9). Since the main idea of this paper is to reweight the edges with LPA, it is necessary to show the effect of the LPA regularization term. Reweighting the edges using only GCN is a very natural ablation model.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "DgYW1qQxhgO", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 addresses the problem that edges in a graph could be noisy, containing erroneous edges. With the assumption of GCN that ‘labels/features are correlated over the edges of the graph’, it is desired that weights of inter-class edges are large, and those of intra-class edges are small. Hence, these noisy edges could impair GCN’s performance.\n\nAddressing this problem, this work propose to optimize the given adjacency matrix based on the performance of Label Propagation(LPA) on it. LPA also assume the ‘homophily’ property of graphs, hence adapting adjacency matrix on it can encourage larger weights being given to trajectories linking two same-class nodes. This step is expected to be beneficial for the performance of GCN.\n\nThis paper has following strong points:\n1.\tProposed GCN-LPA can learn to optimize the edges and perform node classification in an end-to-end manner, without causing much more training time cost;\n2.\tThe writing is clear and easy to understand. The motivation, theory part is presented step by step, with complete proofs of those theorem;\n3.\tExperiments show that the proposed model is better at splitting embedding of nodes from different classes, and achieve improvement in node classification performance.\nFollowing are the weak points:\n1.\tThe idea that LPA can help GCN is not convincing. These two methods have similar assumption over the data, as also shown in the relation between label influence weight and feature influence weight in Theorem 1. Hence, why the authors claim on Page4, after Eq(9), that only updating edges with GCN will cause overfitting? Would not they be the same?\n2.\tThe experiment is not very complete. Implemented GCN-LPA optimizes edges with gradient from both LPA and GCN tasks. The idea that LPA contains complementary information for GCN is not well justified. I would suggest that using LPA to obtain the updated edges and then fix them, before sending them to the GCN model.\n3.\tBesides, there are some other papers also seeking to adapt edges for the training of GCN, which are not mentioned. For example, \n[Jiang, Bo, et al. \"Semi-supervised learning with graph learning-convolutional networks.\" Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019.]\n[Yang, Liang, et al. \"Topology Optimization based Graph Convolutional Network.\" IJCAI. 2019.]\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three of the reviewers are significantly concerned about this submission while R3 was positive during review. During discussion, R3 also agreed that there are concerns not only on experimental designs and results but also the proposed model. Thus a reject is recommended.
Decision: Reject