Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
Authors: Yunsheng Shi
Zhengjie Huang
shikun feng
Hui Zhong
Wenjin Wang
Yu Sun
Venue:  (2021)
Keywords: Unified Message Passing Model
Graph Neural Network
Label Propagation Algorithm
Semi-Supervised Classification.

Abstract: Graph neural network (GNN) and label propagation algorithm (LPA) are both message passing algorithms, which have achieved superior performance in semi-supervised classification. GNN performs \emph{feature propagation} by a neural network to make predictions, while LPA uses \emph{label propagation} across graph adjacency matrix to get results. However, there is still no good way to combine these two kinds of algorithms. In this paper, we proposed a new {\bf Uni}fied {\bf M}essage {\bf P}assaging Model (UniMP) that can incorporate \emph{feature propagation} and \emph{label propagation} with a shared message passing network, providing a better performance in semi-supervised classification. First, we adopt a Graph Transformer jointly label embedding to propagate both the feature and label information. Second, to train UniMP without overfitting in self-loop label information, we propose a masked label prediction strategy, in which some percentage of training labels are simply masked at random, and then predicted. UniMP conceptually unifies feature propagation and label propagation and be empirically powerful. It obtains new state-of-the-art semi-supervised classification results in Open Graph Benchmark (OGB). 

Under review as a conference paper at ICLR 2021
MASKED LABEL PREDICTION: UNIFIED MESSAGE PASSING MODEL FOR SEMI- SEMI-SUPERVISED CLASSIFICA- TION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural network (GNN) and label propagation algorithm (LPA) are both message passing algorithms, which have achieved superior performance semi- supervised classification. GNN performs feature propagation by a neural network to make predictions, while LPA uses label propagation across graph adjacency matrix to get results. However, there is still no good way to combine these two kinds of algorithms. In this paper, we proposed new Unified Message Passaging Model (UniMP) that can incorporate feature propagation and label propagation with shared message passing network, providing a better performance in semi- supervised classification. First, we adopt Graph Transformer jointly label em- bedding to propagate both the feature and label information. Second, to train UniMP without overfitting in self-loop label information, we propose a masked label prediction strategy, in which some percentage of training labels are sim- ply masked at random, and then predicted. UniMP conceptually unifies feature propagation and label propagation and be empirically powerful. It obtains new state-of-the-art semi-supervised classification results in Open Graph Benchmark (OGB).
INTRODUCTION
There are various scenarios in the world, e.g., recommending related news and products, discovering new drugs, predicting social relations, which can be described as graph structures. Many methods have been proposed to optimize these graph-based problems and achieved significant success in many related domains such predicting the properties of nodes (Yang et al. 20066] Kipf & Welling. 2016), links (Grover & Leskovec 2016 Battaglia et al., 2018). and graphs (Duvenaud et al. 2015 Niepert et al. 2016 Bojchevski al. 2018).
In the task of semi-supervised node classification, we are required to learn with labeled examples and then make predictions for those unlabeled ones. To better classify the nodes" labels in the graph, based on the Laplacian smoothing assumption (Li al., 20188 Xu et al.) 20185), the message passing models were proposed aggregate the information from its connected neighbors in the graph, acquiring enough facts to produce a more robust prediction for unlabeled nodes. Generally, there are two kinds of practical methods to implement message passing model, the Graph Neural
Networks (GNNs) (Kipf & Welling 2016 Hamilton et al. 2017 Xu et al., 2018b Liao et al. 2019
Xu al.) 2018a| Qu al.
2019) and the Label Propagation Algorithms (LPAs) [Zuu 2005 Zhu
et al.
2003
Zhang & Lee 2007 Wang & Zhang 2007 Karasuyama & Mamitsuka 2013 Gong
let al.
2016 Liu al. 2019). GNNs combine graph structures by propagating and aggregating
nodes features through several neural layers, which get predictions from feature propagation. While
LPAs make predictions for unlabeled instances by label propagation iteratively.
Since GNN and LPA are based on the same assumption, making semi-supervised classifications by information propagation, there is an intuition that incorporating them together for boosting perfor- mance. Some superior studies have proposed their graph models based on it. For example, APPNP (Klicpera et al. 2019) and TPN (Liu et al., 2019) integrate GNN and LPA by concatenating them together, and GCN-LPA (Wang & Leskovec 2019 uses I.AA regularize their GCN model. How-

---

Under review as a conference paper at ICLR 2021
ever, shown in Tabel aforementioned methods still can not incorporate GNN and LPA within message passing model, propagating feature and label in both training and prediction procedure.
Table 1: Comparision between message passing models
Training Feature Label Feature
Prediction
Label
LPA
GCN APPNP
GCN-LPA
UniMP (Ours)
To unify the feature and label propagation, there are mainly two issues needed to be addressed:
Aggregating feature and label information. Since node feature is represented by embeddings. while node label is a one-hot vector. They are not in the same vector space. In addition, there different between their message passing ways. GNNs
propagate the information by diverse neural structures likes GraphSAGE (Hamilton et al. 2017). GCN (Kipf & Welling (016) and GAT Veličkovié et al. 2017). But LPAs only pass the label message by graph adjacency matrix.
Supervised training. Supervised training a model with feature and label propagation will overfit in self-loop label information inevitably, which makes the label leakage in training time and causes poor performance in prediction.
In this work, inspired by several advantages developments (Vaswani et al. 2017 Wang al. 2018 Devlin et al. 2018) in Natural Language Processing (NLP), we propose a new Unified Message Passing model (UniMP) with masked label prediction that can settle the aforementioned issues. UniMP is multi-layer Graph Transformer, jointly using label embedding to transform nodes labels into the same vector space as nodes features. propagates nodes features like the previous attention based GNNs (Veličković et al. [017]] /Zhang et al. 2018). Meanwhile, its multi-head attentions are used as the transition matrix for propagating labels vectors. Therefore, each node can aggregate both features and labels information from its neighbors. To supervised training UniMP without overfitting in self-loop label information, we draw lessons from masked word prediction in BERT (Devlin et al.) 2018) and propose masked label prediction strategy, which randomly masks some training instances' label embedding vectors and then predicts them. This training method perfectly simulates the procedure of transducing labels information from labeled to unlabeled examples in the graph.
We conduct experiments three semi-supervised classification datasets in the Open Graph Bench- mark (OGB), where our new methods achieve novel state-of-the-art results in all tasks, gaining 82.56% ACC in ogbn-products, 86.42% ROC-AUC in ogbn-proteins and 73.11% ACC in ogbn- arxiv. We also conduct the ablation studies for the models with different inputs to prove the effec- tiveness of unified method. In addition, we make the most thorough analysis of how the label propagation boosts our model's performance.
2
METHOD
We first introduce our notation about graph. We denote graph as G (V, E), where V denotes the nodes in the graph with [V] and denotes edges with |E| = m. The nodes are described by the feature matrix X E RR=x/, which usually are dense vectors with f dimension, and the target class matrix Y Baxe with the number of classes c. The adjacency matrix = [4s.p] Raax used describe graph G, and the diagonal degree matrix is denoted by D diag(d1, d2...., dn)) where d, = Σ, azy is the degree of node A normalized adjacency matrix is defined as D or
D- 1 AD 1, and we adopt the first definition in this paper.
2.1 FEATURE PROPAGATION AND LABEL PROPAGATION
In semi-supervised node classification, based on the Laplacian smoothing assumption, the GNN transforms and propagates nodes features X across the graph by several layers, including linear layers and nonlinear activation to build the approximation of the mapping: X Y. The feature
2

---

Under review as a conference paper at ICLR 2021
X
Attention
Multi
Matirul
Scale
A
Dit--hroctctt
Edges
Linarr
LiveEa
Linear
Neighbors
Predictions
P(Yv-u X, Y,
Partael by Diswnved shaee
Tranc aatoooominn
Graphh
LeyerNomm
Rolly
Transforma
Graph
LayerNamm
Didpux
Figure I: The architecture of our UniMP.
propagation scheme GNN layer is:
H(+1) = Y foue
where the a is activation function, W(() is the trainable weight in the (-th layer, and the H is the (-th layer representations of nodes. H/ (0) is equal node input features Finally, foat output layer is applied on the final representation to make prediction for Y.
As for LPA, it also assumes the labels between connected nodes are smoothing and propagates the labels iteratively across the graph. Given an initial label matrix yr()), which consists of one-hot label indicator vectors 7 for the labeled nodes or zeros vectors for the unlabeled. A simple iteration equation of LPA formulated following:
g((+)) D (1
(2)
Labels are propagated from each other nodes through a normalized adjacency matrix D- A.
2.2 UNIFIED MESSAGE PASSING MODEL
we employ Graph Transformer, jointly using label embedding construct our unified message passing model for combining the aforementioned feature and label propagation together.
As shown in Figure D
Graph Transformer. Since Transformer (Vaswani et al. 2017) has been proved being powerful
NLP., we employ its vanilla multi-head attention into graph learning with taking into account the
case of edge features. Specifically, given nodes features (!)) {h Io .... (11)) }, we calculate
(1)
multi-heal attention for each edge from j to as following:
2 A + Deg (8)
20) w-((), w + (())) (1)
Ca.ij = W Wa,elij + bac
33)
(1) (9 o,t + Cc,úr)
(1)
O
EvEN(y (ga. ((ll) Cc,tu)
3

---

Under review as a conference paper at ICLR 2021
is exponential scale dot-product function and d is the hidden size of each where k) exp( k
va
head. For the c-th head attention, we firstly transform the source feature h, and distant feature h/) into query vector 9c RR'and key vector k!) Rd respectively using different trainable parameters W w
(1)
c.k. baggr ( The provided edge features esj will be encoded and added into
key vector as additional information for each layer.
After getting the graph multi-head attention, we make a message aggregation from the distant j to the source
(1) W (1) +
b
Ee By
Σ
Jass (vad ecalD
JEN(6)
(4)
(1) w0 h (
8 sigmoid ( ( (1) : 1h DDD
h [(+1) ReL.U[LayerNorm(11 ) -(0
where the || is the concatenation operation for C' head attention. Comparing with the Equation 1 multi-head attention matrix replaces the original normalized adjacency matrix as transition matrix for message passing. The distant feature h is transformed to Ver E R for weighted sum. In addition, inspired by (Li et al. 2019; Chen et al. 2020) to prevent oversmoothing, we propose a gated residual connections between layers by E Rd and 8 E R!.
Specially, similar to GAT, if we apply the Graph Transformer on the output layer, we will employ averaging for multi-head output as following:
1 = -
(
-0
(5)
c=1
JEN(
(1-)) (1-
)
+ 5
Label Embedding and Propagation. We propose to embed the partially observed labels informa- tion into the same space as nodes features: Ý Raxe + Y. E R=xf, which consist of the label embedding vector for labeled nodes and zeros vectors for the unlabeled. And then, we combine the label propagation into Graph Transformer by simply adding the nodes features and labels features together as propagation features (H = X + Y.) RR We can prove that by mapping partially- labeled Ý and nodes features X into the both label propagation and feature propagation within a shared message passing framework. Let's take Y, = YW, and A to be normalized adjacency matrix D A or the attention matrix from our Graph Transformer like Equation
space and adding them up, our model is unifying
3 Then we can find that:
(0) X +YW.
(6)
((++)) = ((((1 (0l1--9000 3)A" BT) (T)HH
where can be the gated function like Equation 4 or a pre-defined apper-parameters like APPNP Klicpera et al. 2019). For simplification, we let function as identity function, then we can get:
H = ((1 3) + (1) + (W))
w()
= ((1 ((1 3) + 3/''XW' ((1 3) 31YYW.WW
where W wWW ... (())) Then we can find that our model can be approximately de- composed into feature propagation ((1 A) 31) XW and label propagation ((1 A* + B.....WW.
3 MASKED LABBL PREDICTION
Previous works on GNNs seldom consider using the partially observed labels Ý both training and inference stages. They only take those labels information as ground truth target supervised train
4

---

Under review as a conference paper at ICLR 2021
their model's parameters f with given X and A:
arg max log Po (Y log pe (0,
(8)
9
where V. represents the partial nodes with labels. However, our UniMP model propagates nodes features and labels to make prediction: p(y]X, A). Simply using above objective for our model will make the label leakage in the training stage, causing poor performance inference. Learning from BERT, which masks input words and makes prediction for them to pretrain their model (masked word prediction), we propose masked label prediction strategy to train our model. During training, at each step, we corrupt the y into by randomly masking a portion node labels to zeros and keep the others remain, which is controlled by hyper-parameter called label_rate. Let those masked labels be Y, our objective function is to predict Y with given X, Y and A:
arg max log Pe P0 (YX,Y, A)
Σ Po (T
where V represents those nodes with masked labels. In this way, we can train our model without the leakage of self-loop labels information. And during inference, we will employ all Y as input labels to predict the remaining unlabeled nodes.
4 EXPERIMENTS
We propose a Unified Message Passing Model (UniMP) for semi-supervised node classification, which incorporates the feature and label propagation jointly by Graph Transformer and employ masked label prediction strategy to optimize it. We conduct the experiments on the Node Property Prediction of Open Graph Benchmark (OGBN), which includes several various challenging and large-scale datasets for semi-supervised classification, splitted in the procedure that closely matches the woal-world application Hu et al. (2020). To verified our models effectiivnesss we compare our model with others arxiv three OGBN datasets. We also provide more experiments and comprehensive studies to show our motivation more intuitively, and how LPA improves our model to achieve better results.
models (SOTAs) in ogbn-products, ogbn-proteins and ogbn-
4.1 DATASETS AND EXPERIMENTAL SETTINGS
Table 2: Dataset statistics of OGB node property prediction
Name ogbn-products
Node
Edges
Tasks
Split Rate
Split Type
Task Type
Metric
1444, 029
61, 859, 140
1
88,2)888
Sales rank
Multi-class class
Accuracy
ogbn-proteins
132, 534
39, 561, 252
112
65 66116)19
Species
Binary class
ROC-AUC
ogbn-arxiv 169,343
166, 243
1
(8)088114
Time
Multi-class class
Accuracy
Datasets. Most of the frequently-used graph datasets are extremely small compared to graphs found in real applications. And the performance of GNNs these datasets is often unstable due several issues including their small-scale nature, non-negligible duplication or leakage rates, unrealistic data splits (Dwivedi et al. 2020 Hu al. 2020). Consequently, we conduct our experiments on the recently released datasets of Open Graph Benchmark (OGB) (Hu et al.) 2020), which overcome the main drawbacks of commonly used datasets and thus are much more realistic and challenging. OGB datasets cover variety of real-world applications and span several important domains ranging from social and information networks to biological networks, molecular graphs, and knowledge graphs. They also span a variety of predictions tasks at the level of nodes, graphs, and links/edges. As shown in table 2 in this work, we performed our experiments on the three OGBN datasets with different sizes and tasks for getting credible result, including ogbn-products about 47 products categories classification with given d00-dimensional nodes features wowoo-grooetiee proteins about 1 112 kinds of proteins function prediction with given 8 3-dimensional edges features and ogbn-arxiv about 40- class topics classification with given 128 dimension nodes features. More details about these datasets provided in Appendix A
5

---

Under review as a conference paper at ICLR 2021
Implementation Details. As mentioned above, these datasets are different from each other in sizes or tasks. So we evaluate our model on them with different sampling methods like previous studies (Li et al. 2020), getting credible comparison results. In aogn-pprodue dataset, we use Neighbor- Sampling with size = 10 for each layer to sample the subgraph during training and use full-batch for inference. In ogbn-proteins dataset, we use Random Partition split the dense graph into subgraph to train and test our model. The number of partitions is 9 for training and for test. As for small-size ogbn-arxiv dataset, we just apply full batch for both training and test. We set the hyper-parameter of our model for each dataset in Table 3 and the label_rate rate means the percentage of labels we preserve during applying masked label prediction strategy. We use Adam optimizer with Ir = 0.001 to train our model. Specially, we set weight decay to 0.0005 for our model in small-size ogbn-arxiv dataset to prevent overfitting. More details about the tuned syper-parameten are provided in Appendix B
Table 3: The hyper-paramerterr setting of our model
ogbn-products NeighborSampling
ogbn-proteins Random Partition
ogbn-arxiv
sampling method num layers hidden size
Full-batch
3
3
128
64
128
nua_heads dropout
4
4
2
0.3
0.1
0.3
0.001
0.001
0.001
weight_decay
*
0.0005
label rate
0.625
0.5
0.625
4.2 COMPARISON WITH SOTAS
Baseline and other comparative SOTAs provided by OGB leaderboard. Some of the including results are conducted officially by authors from original papers, while the others are re-implemented by communities. And all these results are guaranteed to be reproducible with open source codes. Following the requirement of OGB, we run our experimental results for each dataset 10 times and report the mean and standard deviation. As shown in Tabel Tabel and Tabel our unified model outperform all other comparative models in three OGBN datasets. Since most of the compared mod- els only consider optimizing their models for the features propagation, these results demonstrate that incorporating label propagation into GNN models can bring significant improvements. Specifically, we gain 82.56% ACC in prodduss, 86.425 ROC-AUC in ogbn-proteins which achieves about 0.6-1.6% absolute improvements compared to the newly SOTA methods like DeeperGCN (Li al.) 2020). In ogbn-arxiv, our method gains 73.1 1 % ACC, achieve 0.37% absolute improvements com- pared to GCNII (Chen et al. 2020). whose parameters are four times larger than ours.
Table 4: Results for oron-products
Model
Test Accuracy
Validation Accuracy
Params
GCN-Clusted (Chiang el al. 2019
0.7897 1 0.0036
0.9212 1 0.0009 0.8985 1 0.0022
206, 895
GAT-Cluster
0.7923 1 0.0078
1, 5.40 848
GAA-NeighborSSampinn
0.7945 = 0.0059
7,1, 574
GraphSAINT (Zeng et al.
2019
0.8027 = 0.0026
331, 661
DeeperGCN (Li el al 2020)
0,8090 = 0.0020
0.9238 + 0.0009
253, 743
UniMP
0.8256 + 0.0031
0.9308 + 0.0017
1, 1,47,, 605
Table 5: Results for ogbn-proteins
Model
Test ROC-AUC
Validation ROC-AUC
Params
GaAN (Zhang et al.
2018
0.7803 0.0073
Ge (Lu et al. 2020b)
0.7825 1 0.0035
316, 754
MWE-DGCN
0.8436 1 0.0065
0.8973 + 0.0057
538, 544
DeepGCN (Li et al.
2019)
0.8496 + 0.0028
0.8921 + 0.0011
2,374, 456
DeeperGCN (Li ct 2020
0.8580 + 0.0017
0.9106 + 0.0016
2,374, 568
UniMP
0.8642 1 0.0008
0.9175 0.0007
1,909,
104 104

---

Under review as a conference paper at ICLR 2021
Table Results for ogbn-arxiv
Model
Test Accuracy
Validation Accuracy
Params
DeeperGCN (Li et al
2020)
0.7192 = 0.0016
0.7262 = 0.0014
1, 1,471, 506
GaAN (hhagg
2018)
0.7197 + 0.0024
1,471,500
DAGNN ( (L
202(1a)
0.7209 0.0025
1, 7,744
JKtet (uu et al. (0188)
0.7219 + 0.0021
0.7335 = 0.0007
331, 661
GCNII (Chen el al.
2020
0.7274 + 0.0016
2, 148, 648
UniMP
0.7311 = 0.0021
0.7450 0.0005
473, 489
4.3 ABLATION STUDIES ON GRAPH TRANSFORMER AND MASKED LABEL PREDICTION
In this section, we will conduct extensive studies to identify the improvements from different com- ponents of our unified model. To get fair comparison, we re-implement classical GNN methods like GCN and GAT. following the same sampling methods and model setting shown in Table The hidden size of GCN is head num hidden size since it doesn't have head attention. We also change different inputs for our models to study the effectiveness of feature and label propagation.
As shown in Tabel 7 it's surprising that only Y and A. GNNs still work well in all three datasets, outperforming those MLP model only given X. This implies that one's label relies heavily on its neighborhood instead of itself feature. For models with X and A as inputs like most GNNs do, they are more likely to remember the labels of training set through approximations, which is inaccurate. It's waste of information in semi-supervised classification when prediction without incorporating the annotated label Y information from training sets, which are preciser than the model's 's approximations for training data. In addition, with different input settings, our improved Graph Transformer outperform GAT, GCN in most
Table 7: Ablation studies on models with different inputs.
Datasets
Inputs
Model
ogbn-products Test ACC
ogbn-proteins Test ROC-AUC
ogbn-arxiv
Test ACC
X
MLP
0.6106 = 0.0008
0.7204 + 0.0048
0.5765 + 0.0012
GCN
0.7851 = 0.0011
0.8265 0.0008
0.7218 1 0.0014
X, A
GAT
0.8002 + 0.0063
0.8376 0.0007
0.7246 1 0.0013
Transformer
0.8137 = 0.0047
0.8347 + 0.0014
0.7292 + 0.0010
GCN
0.7832 + 0.0013
0.8083 0.0021
0.7018 1 0.0009
A, Y
GAT
0.7751 1 0.0054
0.8247 0.0033
0.7055 + 0.0012
Transformer
0.7987 = 0.0104
0.8160 0.0007
0.7090 - 0.0007
GCN
0.7987 1 0.0104
0.8247 1 0.0032
0.7264 1 0.0003
X.
GAT
0.8193 1 0.0017
0.8556 0.0009
0.7278 + 0.0009
Transformer
0. 0.8269 = 0.0009
0.8560 0.0003
0. 0.7332 + 0.0014
In oghn-proteins, nodes features are not provided initially. We average the edge features as their nodes features and drop the edge features for fair comparison in this experiment. which is slightly different from Table X is the nodes features. is the graph adjacent matrix and Y is the observed labels. We run these models three times and report their means and stds.
4.4 EXPLORING HOW LABEL PROPAGATION AFFECTS UNIMP
orloardee
4:00
Test Accennyy
0.2
Valla
Vilid
4220
Tie
Labe
(95) Draining
Hote Tasting Phese
Num Noghloes
(a) Training with differ- (b) Training with differ- (c) Testing with different (d) Test accuracy with ent label rate.
ent proportion of data. proportion of labels. different neighbors.
Figure 2: Exploration of how label coverage affects label propagation.

---

Under review as a conference paper at ICLR 2021
One of our motivations for using label propagation is that labels carry additional informative feature which cannot be replaced by the model's approximation. However, the relation between the coverage of labeled data and the impact of label propagation for model still be uncertain. Therefore, we conduct more experiments in ogbn-arxiv to investigate their relationship in several different scenarios:
In Figure 2a we train UniMP using X, Y. A as inputs. We tune the training label rate which is the nyper-parameter of masked label prediction task and display the validation and test accuracy. Our model achieves better performance when label rate is about 0.625.
Figure 2b describes the correlation between the proportion of training data and the ef- fectiveness of label propagation. We fix the label rate with 0.625. The only change is the training data proportion. It's a common sense that with the increase of training data, the performance is gradually improving. And the model with label propagation can have greater benefits from increasing labeled data proportion.
In the training stage, our model always masks part of the training label and tries to recover them. But in the inference stage, our model utilizes all training labels for predictions, which is slightly inconsistent with the one in training. Figure we fix our trained models and perform label propagation with different label rate in inference. It's found that when lower the label rate during prediction, UniMP might have worse performance (less than 0.70) than the baseline (about 0.72). However, when the label rate climbs up, the performance can boost up to 0.73.
In Figure 2d calculate accuracy for unlabeled nodes with different number of neigh- bors. The experimental result shows that nodes with more neighbors have higher accuracy. And the model with label propagation can always have improvements even with different numbers of training neighbors.
GAT
GAT
fraesformer
GAT
GAT
GAT
GAT
Transformer
Trins former
2,465
2.47
2,475
2
2.49
2
Test Accurecy
Margin Similazity Between Neighbors
Figure 3: Correlation between accuracy and margin similarity between neighbors.
Wang & Leskovee (2019) have theoretically proved that using the LPA for GCN during training can enable nodes within the same class/label connect more strongly. increasing the accuracy (ACC) of model's prediction. Our model can be seen as an upgraded version of them, using LPA both training and testing time. Therefore, try experimentally prove the above idea based model. We use the Margin Similarity Function to reflect the connection tightness the nodes with same class (the higher scores, the stronger connection they are, and more details in Appendix (C) We conduct the experiments on ogbn-arxiv. And as shown Figure 3 the ACC of models' prediction proportional Margin Similarity. Unifying feature and label propagation their connection, improving their ACC. Moreover, our Graph Transformer outperforms GAT in both connection tightness and ACC with different inputs.
further strengthen
CONCLUSION
We first propose a unified message passing model, UniMP, which jointly performs feature propaga- tion and label propagation within a Graph Transformer to make the semi-supervised classification. Furthermore, we propose a masked label prediction method to supervised training model, pre- venting it from overfitting in self-loop label information. Experimental results show that UniMP outperforms the previous ogbn-prue proteins and ogbn-arxiv by large margin, and ablation studies demonstrate the effectiveness of unifying feature propagation and label propagation.
models three main OGBN datasets: ogbn-products,
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzun Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1rxxiv:8006.1222 2018.
Alcksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. Netgan: Gen- erating graphs via random walks. arXiv preprint arXiv: 808.0080/ 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks, arXiv preprint 1.Xiv:2007702133: 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular 2015.
fingerprints. In Advances in neural information processing systems, pp.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint wrXiv:2003.00982 2020.
Chen Gong, Dacheng Tao, Wei Liu, Liu Liu, and Jie Yang. Label propagation via teaching-to- learn and learning-to-teach. IEEE transactions on neural networks and learning systems, 28(6); 1452-1465, 2016.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00683 2020.
Masayuki Karasuyama and Hiroshi Mamitsuka. Manifold- similarity adaptation for label prop- agation. Advances in neural information processing systems, pp. 1547-1555, 2013.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 12X.011609.00207,000 2016.
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Gunnemann. Predict then propagate:
Graph neural networks meet personalized pagerank. arXiv: Learning, 2019.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? Proceedings of the IEEE International Conference on Computer Vision, pp. 9267-9276, 2019.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need train deeper gens. arXiv preprint arXiv:2006.0772 2020.
Qimai I.,, Zhichao Han, and Xiaoming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. Neural Computation, pp. 3548- 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. arXiv preprint arXiv: arXiv: /9011014444 2019.

---

Under review as a conference paper at ICLR 2021
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 2020a.
Yanbin Liu, Juho Lee, Minseop Park, Saehoon Kim, Eunho Yang, Sung Ju Hwang, and Yi Yang- Learning to propagate labels: Transductive propagation network for few-shot learning. arXiv: Learning. 2019.
Ziqi Liu, Zhengwei Wu, Zhiqiang Zhang, Jun Zhou, Shuang Yang. Le Song. and Yuan Qi. Bandit samplers for training graph neural networks. arXiv preprint arXiv:2006. 05800, 2020b.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net-
works for graphs. In International conference on machine learning, pp. 2014-2023, 2016.
Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. arXiv preprint arXiv:1905.06211. 2019.
Yifan Sun, Changmao Cheng, Yuhan Zhang, Chi Zhang, Liang Zheng, Zhongdao Wang, and Yichen Wei. Circle loss: A unified perspective of pair similarity optimization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6398-6407, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: /0903, 2017.
Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. IEEE Transac- tions on Knowledge and Data Engineering, 20(1):55-611 2007.
Guoyin Wang, Chunyuan Li, Wenlin Wang, Yizhe Zhang, Dinghan Shen, Xinyuan Zhang, Ricardo Henao, and Lawrence Carin. Joint embedding of words and labels for text classification. arXiv preprint arXiv: 2018.
Hongwei Wang and Jure Leskovee. Unifying graph convolutional neural networks and label propa- gation. arXiv: Learning, 2019.
Kuansan Wang. Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396 413, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint 11X.v:1810.00826. 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning graphs with jumping knowledge networks. arXiv preprint //X1v:1806.03536, 2018b
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- 2019.
saint: Graph sampling based inductive learning method. arXiv preprint
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
1033::1803.07294, 2018
Xinhua Zhang and Wee S Lee. Hyperparameter learning for graph based sumi-supe learning algorithms. In Advances in neural information processing systems, pp. 1585-1592, 2007.
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 (ICMI-03), pp. 912-919, 2003.
10

---

Under review as a conference paper at ICLR 2021
Xiaojin Jerry Zhu. Semi-supervised learning literature survey. Technical report, University of Macconii-MMadioon Madison Department of Computer Sciences, 2005.
Wisconsin-
A DATASETS DETAILS
ogbn-products. As shown in Table ogb-products is undirected and unweighted graph. repre- senting an Amazon product co- purcchaasing network. The goal this task is to predict the category of product in multi-class classification setup, where the 47 top-level categories labels. To match the real-world application, it conducts a splitting on the dataset based on sales ranking, where the top 10% for training, next top 2% for validation, and the rest for testing.
used for target
ogbn-proteins. As shown in Table ogbn-proteins dataset an undirected, weighted, and typed (according species) graph. Nodes represent proteins, and edges indicate different types of bi- ologically meaningful associations between proteins, c.g., physical interactions, co-expression or homology. The task is to predict the presence of protein functions in a multi-label binary classifica- tion setup, where there are 1 12 kinds of labels to predict in total. The performance is measured by the average of ROC-AUC scores across the 112 tasks. conducts the splitting by species.
ogbn-arxiv. As shown in Table 2 ogbn-arxiv dataset is a directed graph, representing the citation network between all Computer Science (CS) arXiv papers indexed by MAG (Wang et al.) 2020). The task is to predict the 40 subject areas of arXiv CS papers, e.g., As. cs.LG, and cs.OS, which are manually determined by the paper's authors and arXiv moderators. This dataset were splitted by time.
B HYPER-PARAMETERS TUNED ON UNIMP MODEL
There are the hyper-parameter parameters we tuned our unified model for comparison with other SOTA results, where the asterisks denote the typer-parameters we eventually selected.
Table 8: The tuned hyperparamerters of our model
ogbn-prdouct NeighborSampling
ogbn-proteins
ogbn-arxiv
sampling.methen method
Random Partition
Full-batch
num_layers
[3,, 4]
[3. 5, 7*, 9]
[3+, 4]
hidden size
[128*, 256]
[32, 64 128]
128*, 256]
num heads
[4*,2]
[6, 4 2]
[2 I]
dropout
[0.3*]
[0, 0.1 0.3]
[0.1, 0.3*]
[0.01, 0.001*]
[0.01, 0.001*]
[0.1, 0.001
weight decay
[0, 0.0005
[0.125, 0.25, 0.375, 0.5, 0.625*, 0.75, 0.875]
label rate
[
[0.375, 0.5*, 0.625)
C MARGIN SIMILARITY FUNCTION
Given an attention weight aiy from GAT or Graph Transformer, which can represent the connec- tion tightness between source node i and distance node j, employ the Circle Loss (Sun al.) 2020) and make slight change on it to build our Margin Similarity Function (MSF), measuring the connection tightness between the neighbors nodes with same labels. For each center node and its neighbors j, k E (i), we take the mcasurement task as pair similarity problem in which the center node's 's neighbors with same label are positive samples and the others are negative samples, calculating their connection tightness as following:
N
MSF =
log 1+
Σ
(10)
N
KEN
11


Reviews:
[{"review_id": "ZyChtxDdnz6", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 presents a novel unified model that jointly harnesses the power of graph convolutional networks and label propagation algorithms based on the unified message passing framework. The UniMP first employs graph Transformer networks to jointly propagate both feature and label information. Then, to avoid label leakage, a masked label prediction strategy is employed.\n\nPros:\n* The presented method shows strong empirical performance on the open graph benchmark dataset.\n* The whole framework is simple and the idea is easy to follow.\n\nCons:\n* What is the label leakage problem? It is not clear to me (1) why label will be leaked during the joint learning process and (2) what the outcome does label leakage bring.\n* The writing of this paper is poor. The authors are suggested to polish their paper. Please see minor comments below.\n* Although the proposed UniMP achieves state-of-the-art performance, the experiments are not convincing enough.\n  * Experimental results are not consistent, c.f. Table 4~6 and Table 7. It seems that the standalone Transformer even surpasses UniMP on ogbn-products and ogbn-arxiv.\n  * It seems that the hyper-parameter specifications vary greatly across the three datasets. To me the residual connection is helpful when stacking many layers (Li et al., 2019; Chen et al., 2020), while in this paper the number of layers is relatively low. A sensitivity analysis on the network depth is necessary to demonstrate the impact of the residual connection.\n  * When compared with GAT, the main differences are (1) different implementations of self-attention mechanisms and (2) whether to adopt gated residual connections. However, no ablation studies are provided to demonstrate the impact of these two independent components. Especially, as shown in Table 7 and Figure 3, given $X$,$A$,$\\hat{Y}$, transformer outperforms GAT. The authors are expected to elaborate on which component (self-attention implementation or gated residual connection) brings the improvement.\n\nMinor comments:\n* Abstract: we adopt a Graph Transformer jointly [using] label embedding?\n* Abstract: UniMP ... and be empirical powerful -> is empirical powerful\n* Page 2: there are different -> they are different\n* Mathematical notations are severely abused; for example, hidden_size should be represented by $f$, and how $\\hat{Y}_e$ is transformed from $\\hat{Y}$ is not clear.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "X9Gxe-xTdT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 proposed a novel unified massage passing strategy for semi-supervised graph learning scenario. It combines the advantages of the GNN and label propagation algorithms.\n\nIn the model, the label information is projected into the feature space, then merged/added with the node feature for the GNN feature aggregation module. By this way, the label information could be more effectively utilized in the semi-supervised scenario. In addition, a masked label prediction strategy is proposed to reduce the negative influence of the label leakage problem. The extensive experimental results demonstrate the effectiveness of the proposed model.\n\nPros:\n\nThis paper proposed a novel framework to more effectively and explicitly utilize the label information by GNN in semi-supervised scenario, and the experiments illustrate its effectiveness in general benchmark datasets.\n\nCons:\n\nThe insight/motivation of this method is not very significant. Compared with other methods such as APPNP,  TPN and GCN-LPA, the major differences is another effective/unified network structure to merge feature and label information together. Compared with GCN-LPA, the improvements in the insight/motivation aspect is not very significant. This paper shows empirical discussion compared with GCN-LPA, while it could be better to show some insight/theoretical discussion/analysis.\n\nThe improvements compared with other baselines are not significant. If more parameters/weights are deployed in other baselines, could the performance be better? Please discuss this point.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6N7lC1yr6l", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "Summary:\n\nThe paper proposes a new Graph Transformer (UniMP) based model with the motive of combining two powerful semi-supervised node classification techniques, GNN and LPA. Proposed Graph Transformer unifies feature and label propagation in conjunction to provide a better performance in semi-supervised node property classification task. UniMP also benefits from a masked label prediction strategy which is inspired by [Devlin et al.](https://arxiv.org/abs/1810.04805)\nProposed method is able to achieve SOTA performance on several datasets from Open Graph Benchmark. \n\n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nPros:\n\n+ The method proposed for unifying feature and label propagation is simple yet sufficiently novel.\n\n+ This paper is able to support all the claims with rigorous experimentation. The experimentation is done using Open Graph Benchmark datasets and the proposed method achieves SOTA on all the datasets used.\n    \n+ The paper is very well written and is easy to understand. I personally like the simple yet effective nature of the method.\n\n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nQuestions: \n\n- How do you map label information to feature information space? Is it a linear model? Did you explore any other embedding approaches before deciding on a linear model?\n\n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n    \nOverall, I vote for accepting the paper. This paper provides a novel method to unify GNN and LPA algorithms in order to take advantage of feature as well as label information. Proposed method is well supported by rigorous experimentation on various datasets and ablation studies on various inputs. \n\n------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n    \nMinor Comments/Typos:\n    \n- Section 1: In addition, there are **different** between → In addition, there are **differences** between\n    \n- Section 4: To **verified** our model → To **verify** our model\n    \n- Section 4.2: Some of the **including** results → Some of the **included** results\n    \n- Section 4.3: instead of **itself** **feature** → instead of **it's features**\n    \n- Section 4.4: model still **be** uncertain → model still **remains** uncertain", "extra_scores": {}, "extra_text": {}}, {"review_id": "2IAElEmekRi", "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": "The authors proposed a unified message passing model to make a graph neural network to be able to incorporate both label propagation and feature propagation. Compared to previous work, the proposed model can also make use of partial label information in both training and inference stages. Experiments on three OGBN datasets show that the proposed methods achieve promising performance.\n\nPros:\n\n    The motivation of the paper is very clearly stated in the text and the experiments successfully show that by incorporate label propagation and feature propagation, the performance can be improved.\n\n    The partial label information is included in both training and inference stages.\n\nCons:\n\n    In the literature review, one very important work [A], which is very closely related to the proposed model is ignored. In [A], a unified model for neural message passing is already established, and the proposed model seems to be a special case of the neural message passing module in [A]. The authors should compare their model to the one in [A] and clearly state the difference between the proposed model and the one [A], and should justify why should not use [A] directly.\n\n[A] Gilmer, Justin, et al. \"Neural Message Passing for Quantum Chemistry.\" ICML. 2017.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a semi-supervised graph classification technique that unifies feature and label propagation techniques. The resulting algorithm is a simple extension that attains strong performance. Reviewers were divided on this submission. Some reviewers felt the proposed algorithm did not constitute a sufficient technical contribution given that it was a simple combination of existing techniques. I tend to agree with other reviewers that the simplicity is a benefit. However, despite the methods simplicity there was significant confusion about the details of the method and multiple reviewers flagged that the paper was difficult to read and understand. It further could benefit from additional discussion and some clarification/cleanup of the experimental results. Finally, multiple reviewers asked for better situating of the proposed method with respect to prior work. Given these concerns, I do not think the paper is ready for publication. I would recommend the reviewers do a thorough re-write of the paper to address these concerns and consider resubmitting.
Decision: Reject