Year: 2020

Abstract:
Massive labeled data have been used in training deep neural networks, thus label noise has become an important issue therein. Although learning with noisy labels has made great progress on image datasets in recent years, it has not yet been studied in connection with utilizing GNNs to classify graph nodes. In this paper, we propose a method, named LPM, to address the problem using Label Propagation (LP) and Meta learning. Different from previous methods designed for image datasets, our method is based on a special attribute (label smoothness) of graphstructured data, i.e., neighboring nodes in a graph tend to have the same label. A pseudo label is computed from the neighboring labels for each node in the training set using LP; meta learning is utilized to learn a proper aggregation of the original and pseudo label as the final label. Experimental results demonstrate that LPM outperforms state-of-the-art methods in graph node classification task with both synthetic and real-world label noise. Source code to reproduce all results will be released.

heading: 1 INTRODUCTION
text: Deep Neural Networks (DNNs) have achieved great success in various domains, but the necessity of collecting large amount of samples with high-quality labels is both expensive and time-consuming. To address this problem, cheaper alternatives have emerged. For example, the onerous labeling process can be completed on some crowdsourced system like Amazon Mechanical Turk 1. Besides, we can collect labeled samples from web with search engines and social media. However, all these methods are prone to produce noisy labels of low quality. As is shown in recent research (Zhang et al., 2016b), an intractable problem is that DNNs can easily overfit to noisy labels, which dramatically degrades the generalization performance. Therefore, it is necessary and urgent to design some valid methods for solving this problem.
Graph Neural Networks (GNNs) have aroused keen research interest in recent years, which resulted in rapid progress in graph-structured data analysis (Kipf & Welling, 2016; Velickovic et al., 2017; Xu et al., 2018; Hou et al., 2019; Wang & Leskovec, 2020). Graph node classification is the mostcommon issue in GNNs. However, almost all the previous works about label noise focus on image classification problem and handling noisy labels in the task of graph node classification with GNNs has not been studied yet. Fortunately, most edges in the graph-structured datasets are intra-class edges (Wang & Leskovec, 2020), indicating that a node’s label can be estimated by its neighbor nodes’ labels. In this paper, we utilize this special attribute of graph data to alleviate the damages caused by noisy labels. Moreover, meta learning paradigm serves as a useful tool for us to learn a proper aggregation between origin labels and pseudo labels as the final labels.
The key contributions of this paper are as follows:
• To the best of our knowledge, we are the first to focus on the label noise existing in utilizing GNNs to classify graph nodes, which may serve as a beginning for future research towards robust GNNs against label noise.
• We utilize meta-learning to learn how to aggregate origin labels and pseudo labels properly to get more credible supervision instead of learning to re-weight different samples.
1https://www.mturk.com/
We experimentally show that our LPM outperforms state-of-the-art algorithms in utilizing GNNs to classify graph nodes with both synthetic and real-world label noise.

heading: 2 RELATED WORK

heading: 2.1 GRAPH NEURAL NETWORKS
text: To start, we use G = (V, E ,X ) to denote a graph whose nodes set is V and edges set is E , and X ∈ Rn×d is the input feature matrix, where n denotes the number of nodes in the graph and d is the dimension of the input feature vector of each node. We use eu,v ∈ E to denote the edge that connects node u and v. For each node v ∈ V , its neighbor nodes set can be donated as Nv = {u : eu,v ∈ E}. For node classification task, the goal of GNNs is to learn optimal mapping function f(·) to predict the class label yv for node v. Generally speaking, GNNs follows a framework including aggregation and combination in each layer. Different GNNs have proposed different ways of aggregation and combination. In general, the k-th layer of a GNN reads
a(k)v = Aggregate (k)({h(k−1)u : u ∈ N (v)}), h(k)v = Combine(k)(h(k−1)v , a(k)v ), (1)
where h(k)v is the output for k-th layer of node v, h (0) v is the input vector of node v.

heading: 2.2 LABEL PROPAGATION
text: In Label Propagation (LP), node labels are propagated and aggregated along the edges in the graph (Zhou et al., 2004; Zhu et al., 2005; Wang & Zhang, 2007; Karasuyama & Mamitsuka, 2013). There are some works which were designed to improve the performance of label propagation. For example, Gong et al. (2016) proposed a novel iterative label propagation algorithm which explicitly optimizes the propagation quality by manipulating the propagation sequence to move from simple to difficult examples; Zhang et al. (2020) introduces a triple matrix recovery mechanism to remove noise from the estimated soft labels during propagation. Label propagation has been applied in semi-supervised image classification task. For example, Gong et al. (2017) used a weighted Knearest neighborhood graph to bridge the datapoints so that the label information can be propagated from the scarce labeled examples to unlabeled examples along the graph edges. Park et al. (2020) proposed a novel framwork to propagate the label information of the sampled data (reliable) to adjacent data along a similarity based graph. Compared to these methods, we utilize the intrinsic graph structure instead of handcrafted graph to propagate clean labels information, which is more reliable for graph-structured data. Besides, GNNs are utilized by us to extract features and classify nodes for graph-structured data.

heading: 2.3 META-LEARNING BASED METHODS AGAINST NOISY LABELS
text: Meta-learning aims to learn not only neural networks’ weights, but also itself, such as hand-designed parameters, optimizer and so on (Andrychowicz et al., 2016; Finn et al., 2017). Several works have utilized meta-learning paradigm to deal with label noise. For example, Li et al. (2019) has proposed to find noise-tolerant model parameters by keeping the consistency between the output of teacher and student networks, and Li et al. (2017b) trains the teacher networks with samples with clean labels and then transfer the knowledge to student networks so that the student can learn correctly even if the existence of mislabeled data. Besides, Ren et al. (2018); Jenni & Favaro (2018); Shu et al. (2019) utilize meta-learning paradigm to re-weight samples, i.e., weight samples with clean labels more and weight mislabeled samples less. The weighting factors are optimized by gradient decent or generated by a network to minimizes the loss on a small amount of samples with correct labels. In contrast, meta-learning paradigm is utilized in this paper to learn how to aggregate origin labels and pseudo labels properly. We can get more credible supervision by combining the original label information with the label information provided by LP properly.

heading: 3 METHODS

heading: 3.1 PRELIMINARIES
text: Given a graph data with n nodes and their labels D = {(x0, y0), (x1, y1), ..., (xn−1, yn−1)}, where xj is the j-th node and yj ∈ {0, 1}c is the label over c classes. Dtrain = {(x0, y0), (x1, y1), ..., (xs−1, ys−1)} are training nodes with noisy labels. Our goal is to enable the GNNs f(xj ;w) trained with noisy sets Dtrain can also generalize well on test nodes. w is the learnable parameters of GNNs. In our method, m nodes with true labels Dclean = {(xs, ys), (xs+1, ys+1), ..., (xs+m−1, ys+m−1)} in the graph are provided as the initial clean sets (m s). GCN (Kipf & Welling, 2016) and GAT (Velickovic et al., 2017) are utilized in our experiments to extract features and classify nodes. Our method includes two main parts: label propagation and label aggregation. We will go into details about these two parts in the following section 3.2 and section 3.3.

heading: 3.2 LABEL PROPAGATION
text: Label Propagation is based on the label smoothness that two connected nodes tend to have the same label. Therefore, the weighted average of neighbor nodes’ label of a node is similar to this node’s true label. An illustration of LP part in our method can be found in Figure. 1. The first step of LP is to construct an appropriate neighborhood graph. A common choice is k-nearest graph (Iscen et al., 2019; Liu et al., 2018) but there is an intrinsic graph structure (adjacency matrix A) in graph data, so our similarities matrix W with zero diagonal can be constructed with A, whose elements Wi,j are pairwise similarities between node i and node j:
Wi,j = Ai,j
d(hi, hj) + ε , (2)
where hi, hj are the feature vectors extracted by GNNs for node i and node j. d(·, ·) is a distance measure (e.g.,Euclidean distance). ε is an infinitesimal. Note that we can get W with time complexity O(| E |) instead of O(n2) because A is a sparse matrix whose edge lists are given. Then we can normalize the similarities matrix W :
S = D−1/2WD−1/2, (3)
where D is a diagonal matrix with (i,i)-value to be the sum of the i-th row of W . Let Y (k) = [y
(k) 1 , ..., y (k) n ]T ∈ Rn×c be the soft label matrix in LP iteration k and the i-th row y(k)i is the predicted label distribution for node i. When k = 0, the initial label matrix Y (0) = [y(0)1 , ..., y (0) n ]T
consists of one-hot label vectors for i = s, s+ 1, ..., s+m− 1(i.e., initial clean sets) or zero vectors otherwise. The LP (Zhu et al., 2005) in iteration k can be formulated as:
Y (k+1) = SY (k), (4)
y (k+1) i = y (0) i ,∀i ∈ [s, s+m− 1] (5)
In Eq. (4), every node’s label in the (k + 1)-th iteration equals the weighted average of its neighbor nodes’ labels in k-th iteration. In this way, the clean sets propagate labels to the noisy training nodes according to normalized edge weights. And then in Eq. (5), the labels of clean sets nodes are reset to their initial values. The reason is that we can take full advantage of the tiny minority of clean nodes and in case that the effect of clean sets fade away.
Co-teaching (Han et al., 2018) and Co-teaching plus (Yu et al., 2019) have been proposed to train DNNs robustly against label noise. There are two DNNs which select samples with small loss from noisy training sets to train each other. Our method is similar to theirs to some extent because LP is utilized by us to select true-labeled samples from Dtrain for training. However, instead of taking the nodes with small loss as true-labeled nodes, we select the nodes Dselect whose original labels are same with pseudo labels for training. Original labels ofDselect are credible and we also inject them to initial clean sets Dclean for better LP in next epoch. This is why our method can achieve better performance even if few true-labeled nodes are provided.
3.3 META-LEARNING BASED LABEL AGGREGATION
1. Fo w ar d no is y
2. Aggregation net forward
3. Ba ck w ar d no is y Training loss 6.Backw ard on backw
ard 4. Fo rw ar d cl ea n
5.Backw ard clean
Clean loss
Gradients descent
7.Aggregation net backward
In section 3.2, the selected training nodes (node 5,7 in Figure.1) have been utilized for training and LP but the left training nodes Dleft (node 6,8,9,10 in Figure.1) with abundant information haven’t been fully exploited. In this section, we mine the abundant and precious information from Dleft via meta learning. The computation process of label aggregation is shown in Figure. 2.
For ∀(xj , yj) ∈ Dleft, we can get two loss values: l1 = loss(ŷj , yj), (6) l2 = loss(ŷj , ỹj), (7)
where ŷj is the label predicted by GNNs for training node j and ỹj is the pseudo label predicted by LP for node j. We can also get final label yj for node j by aggregating original label yj and pseudo label ỹj :
yj = λjyj + (1− λj)ỹj , λj ∈ [0, 1] (8)
where λ is the aggregation coefficient. Some previous methods designed a weighting function mapping training loss to sample weights for noisy label problems (Kumar et al., 2010; Ren et al., 2018; Shu et al., 2019). Instead, we utilize a 3-layer multi-layer perceptron (MLP) as the aggregation network g(·; ·) to map loss values to aggregation coefficient λj :
λj = g(l1 ‖ l2; θ) = λj(θ;w), (9) Where l1 ‖ l2 is a 2-dimensional vector which is the concatenation of l1 and l2 and θ is the weights of aggregation network g. The rationality lies on a consensus that samples’ loss values are affiliated with the credibility of samples’ original labels (Kumar et al., 2010; Shu et al., 2019; Yu et al., 2019). The MLP or aggregation networks’ input layer are 2 neurons and its output layer is one neuron, which can be an approximator to almost any continuous functions. The activation function of the last layer is sigmoid function to ensure that output λj ∈ [0, 1]. We can get the training loss Ltrj for node j:
Ltrj (w, θ) = loss(ŷj(w), yj(θ)), (10)
Then we can backward on the GNNs:
ŵt(θt) = wt − α | Dleft | ∑
(xj ,yj)∈Dleft
∇wLtrj (w, θt)|wt , (11)
where α is the learning rate of GNNs. Then we can get the loss Lc on clean sets Dclean:
Lc(ŵt(θt)) = 1 | Dclean | ∑
(xi,yi)∈Dclean
loss(f(xi; ŵt(θt)), yi), (12)
Where f(xi; ŵt(θt)) is the output of GNNs. Then we can utilize Lc to update the weights of aggregation network:
θt+1 = θt − β∇θLc(ŵ(θ))|θt , (13) where β is the learning rate of aggregation network. Finally, GNNs’ weights can be updated:
wt+1 = wt − α | Dleft | ∑
(xj ,yj)∈Dleft
∇wLtrj (w, θt+1)|wt . (14)
To some extent, this part is similar to re-weight based methods (Ren et al., 2018; Shu et al., 2019). However, LPM has two significant advantages. Firstly, re-weight based methods can not remove the damages caused by incorrect labels because they assign every noisy training sample a positive weight while LPM potentially has the ability to take full advantage of noisy samples positively. Secondly, LPM can generate comparatively credible labels for other usages while re-weight or some other methods can not. Algorithm. 1 shows all the steps of our algorithm.

heading: 3.4 CONVERGENCE OF LPM
text: Here we show theoretically that the loss functions will converge to critical points under some mild conditions. The detailed proof of the following theorems will be provided in Appendix C.
Theorem 1 Suppose the loss function loss is L-Lipschitz smooth, and λ(·) is differential with a δbounded gradient, twice differential with its Hessian bounded byB with respect to θ. Let the learning rate αt = min{1, kT }, for some k > 0, such that k T < 1 and learning rate βt a monotone descent sequence, βt = min{ 1L , c√ T } for some c > 0, such that L ≤ c√ T and ∑∞ t=1 βt ≤ ∞, ∑∞ t=1 β 2 t ≤ ∞. Then the clean loss of Aggregation Net can achieve ‖∇θLc(ŵ(θt))‖22 ≤ in O(1/ 2) steps. More specifically,
min 0≤t≤T ‖∇θLc(ŵ(θt))‖22 ≤ O( C√ T ). (15)
Theorem 2 Under the conditions of Theorem 1, with the gradient of loss bounded by ρ, then
lim t→∞
‖∇wtLtr(wt, θt+1)‖22 = 0. (16)
Algorithm 1: LPM. Line 2-12: label propagation; Line 13-22: label aggregation. Data: D,Dtrain,Dclean, max epochs T , LP iterations K in every epoch,A,feature matrix X ,GNNs feature extractor f , Aggregation Network g, expanding clean set for LP Dc Result: Robust GNNs parameters wT
1 Dc = Dclean 2 for t = 0, 1, 2, ..., T − 1 do 3 for ∀v ∈ D do hv = f(xv;wt); 4 for (i, j) ∈ {1, 2, ..., n}2 do Wi,j = Ai,jd(hi,hj)+ε ; 5 for k = 0, 1, 2, ...,K − 1 do 6 Y (k+1) = D−1/2WD−1/2Y (k), y
(k+1) j = y (0) j (∀ node j ∈ Dc)
7 end 8 Dselect = Dleft = ∅; 9 for ∀ node i ∈ Dtrain do
10 if onehot(y(K)i ) = yi do Dselect = node {i} ∪ Dselect; 11 else do Dleft = node {i} ∪ Dleft; 12 end 13 Dc = Dc ∪ Dselect 14 wt ← one-step optimization of wt with the selected nodes Dselect ; 15 for ∀ node j ∈ Dleft do 16 ŷj = f(xj ;wt); 17 l1 = loss(ŷj , yj); l2 = loss(ŷj , ỹj); 18 λj = g(l1 ‖ l2; θt); 19 yj = λjyj + (1− λj)ỹj , λj ∈ [0, 1];Ltrj (w, θ) = loss(ŷj(w), yj(θ)); 20 end 21 ŵt(θt) = wt − α|Dleft| ∑ (xj ,yj)∈Dleft ∇wL tr j (w, θt)|wt ; 22 Lc(ŵt(θt)) = 1 |Dclean| ∑
(xi,yi)∈Dclean loss(f(xi; ŵt(θt)), yi); 23 θt+1 = θt − β∇θLc(ŵ(θ))|θt ; 24 wt+1 = wt − α|Dleft| ∑ (xj ,yj)∈Dleft ∇wL tr j (w; θt+1)|wt . 25 end

heading: 4 EXPERIMENTS

heading: 4.1 DATASETS AND IMPLEMENTATION DETAILS
text: We validate our method on six benchmark datasets, namely citation networks (Sen et al., 2008) including Cora, Citeseer and Pubmed. Coauthor-Phy dataset (Shchur et al., 2018) is also utilized in our experiments, but the results are shown in Appendix A due to the limited space. Summary of the graph datasets mentioned above are shown in Table. 1. The Clothing1M (Xiao et al., 2015) and Webvision (Li et al., 2017a) dataset are utilized to validate the effectiveness of our method in real-world label noise settings. We take a kNN graph (k = 5) as the graph structure so that GNNs can be applied in these two datasets, which follows previous work (Franceschi et al., 2019). More details about our preprocessing on Clothing1M and Webvision datasets can be seen in Appendix B.
The experiments are conducted with two types of label noise: uniform noise and flip noise following previous works (Zhang et al., 2016a; Shu et al., 2019). The former means that the label of each sample is independently changed to a random class with probability p, and the latter means that the label is independently flipped to a similar class with total probability p. The ratio of training, validation, and test nodes are set as 4:4:2. Only nearly 25 nodes with clean labels in the validation set are provided as the clean set in each dataset and we ensure that each class has the same number of samples. For example, we use 8 clean samples per label class for Pubmed. GCN (Kipf & Welling, 2016) serves as the base classification network model in our experiments and it is trained using Adam (Kingma & Ba, 2014) with an initial learning rate 0.01 and a weight decay 5× 10−4, except that the weight decay equals to 0 in Clothing1M and Coauthor-Phy datasets.
We compare LPM with multiple baselines using the same network architecture. These baselines are typical and some of them achieve state-of-the-arts performance on image datasets, which include:
Base model, referring to the GCN that directly trained on noisy training nodes; Meta-learning based methods L2RW (Ren et al., 2018), MW-Nets (Shu et al., 2019); Typical and effective method Co-teaching plus (Yu et al., 2019); Robust loss function against label noise GCE loss (Zhang & Sabuncu, 2018) and APL (Ma et al., 2020); The most recent method based on co-training JoCoR (Wei et al., 2020). For those baselines that don’t need clean sets (Base model, Co-teaching plus, GCE loss, JoCoR and APL), we finetune (denoted by FT in this paper) them on the initial clean sets after the model was trained on training sets for a fair comparison. More experimental details about LPM and all baselines are available in the Appendix B.

heading: 4.2 RESULTS
text: Table. 2 shows the results on Cora and Citeseer with different levels of uniform noise ranging from 0% to 80%. Every experiment are repeated 5 times with different random seeds. Finally, we report the best test accuracy across all epochs averaged over 5 repetitions for each experiment. As can be seen in Table. 2, our method gets the best performance across all the datasets and all noise rates, except the second for 0% uniform noise rate. Our method performs even better when the labels are corrupted at high rate. Table. 3 shows the performance on Cora, Citeseer and Pubmed with different levels of flip noise ranging from 0% to 40%. It can be seen that our method also outperforms state-of-the-arts methods under flip noise across different noise rate, except that the second for 0% flip noise rate. Our method outperforms the corresponding second best method by a large margin when the noise rate is 0.4. As can be seen in Table. 4, our method can also perform better than other baselines in datasets with real-world label noise. We also experiment with Graph Attention Networks (Velickovic et al., 2017) as the feature extractor and classifier, the results shown in Appendix A demonstrate that our method can also perform well with other GNNs.
Table 4: Comparison with baselines in test accuracy (%) on Clothing1M and Webvision. Mean accuracy (± std) over 5 repetitions are reported. The best is highlighted in bold.
Methods Basemodel GCN+FT L2RW MW-Nets GCEloss+FT JoCoR+FT Ours Clothing1M 35.83±0.03 38.05±0.13 53.5±0.08 54.15±0.23 56.9±0.08 56.3±0.12 57.35±0.11 Webvision 32.43±0.05 34.58±0.08 50.12±0.16 52.42±0.25 53.45±0.13 54.12±0.22 55.43±0.17
Figure 3: Comparsion of the true-labeled samples rate in Dtrain and Dselect in various datasets.

heading: 4.3 ANALYSIS OF THE NECESSITY AND EFFECTIVENESS OF DIFFERENT PARTS
text: We design five experiments to validate the necessity and effectiveness of different components of our algorithm. Firstly, we compare the ratio of truelabeled nodes in Dselect with Dtrain in the last epoch to validate the effectiveness of LP. Figure. 3 shows the ratio of true-labeled nodes in Dselect in the last epoch and Dtrain under uniform noise on various datasets. It can be found that nearly all the nodes selected by LP are true-labeled even if most training nodes are mislabeled, which demonstrates the great ability of LP to select true-labeled nodes from noisy training nodes. Secondly, we remove the label aggregation in LPM to validate its necessity and the result shows that the performance of our method become much worse without label aggregation. It is necessary to mine the potential information from the left noisy training nodes after LP selection. Besides, we validate the effectiveness by replacing the learned aggregation coefficients λ with random
numbers between 0 and 1. It is obvious that the aggregation coefficients λ optimized by meta learning outperform random λ. Also, we assign the percentage of clean nodes of each label class as λ (tuned) for comparison. These validate the effectiveness of the meta-learning based label aggregation. The results of above two experiments are shown in Table. 5. We denote the average of λ of clean nodes and noisy nodes in Dleft as λclean and λnoise respectively, ∆λ = λclean − λnoise. We plot the variation of ∆λ during training stage in Figure. 4. It can be observed that λclean > λnoise across the training stage and the margin between λclean and λnoise grows larger with the training process, which suggests that λ optimized by our method is valid.

heading: 4.4 IMPACT OF FINETUNING AND NOISE RATE
text: We would like to investigate how our baselines can perform without finetuning. As can be seen in Figure. 5, the performance of the baselines will degenerate relatively significantly without finetuning across different noise rate. This illustrates that some baselines (without finetuning) that are designed for image datasets may perform relatively poor on graph-structured data and this motivates our work which trains GNNs robustly utilizing the structure information of graph data. Besides, We can also observe that our method only drops nearly 9% when the flip noise rate increased from 0% to 40%, whereas the baseline has dropped nearly 20% - 30%, which illustrates that our method is more robust, especially at high noise rate. At 0% noise, our method only slightly underperforms reweights besed methods. This is reasonable because the original labels are all correct but our method will inevitably perturb a few clean labels while the re-weights based methods will not.

heading: 4.5 SIZE OF THE CLEAN SET
text: We try to strike a balance and understand when finetuning will be effective. As can be seen in Figure. 6, our method can also perform better even if the size of clean set is extremely small. The overall test accuracy does not grow much when the size of clean set is large enough. Besides, the test accuracy of baselines with fintuning will increase significantly when the size of clean set grows larger. This suggests that finetuning will be valid when the size of clean set grows larger because GNNs can achieve good performance with relatively less samples (Kipf & Welling, 2016; Veličković et al., 2017). From this perspective, our method can also serve as complementary for finetuning based methods when the size of clean set is large enough.

heading: 5 CONCLUSION AND FUTURE WORK
text: In this work, we proposed a robust framwork for GNNs against label noise. This is the first method that specially designed for label noise problem existing in utilizing GNNs to classify graph nodes and it outperforms state-of-the-arts methods in graph-structured data, which may serve as the beginning for future research towards robust GNNs against label noise. As a future work, we may design an inductive robust method. Besides, better methods that don’t need clean sets are also the goals of us.

heading: A APPENDIX : ADDITIONAL EXPERIMENT RESULTS
text: We also take Graph Attention Networks (GAT) as the feature extractor and classifier and the results shown in Table. A.6 validate that our method can also perform well with various GNNs. Besides, LPM can also perform better than other baselines in larger graph dataset Coauthor-Phy, the results can be seen in Table. A.7. We also demonstrate confusion matrices of Basemodel and LPM in Figure. A.4, which visually show that our method can improve the robustness against label noise of GNNs by a large margin.

heading: B APPENDIX : ADDITIONAL DETAILS OF OUR EXPERIMENTS
text: Original Clothing1M and Webvision datasets are all large-scale datasets with real-world label noise. We randomly choose 5000 images in 10 classes from original datasets and every image serves as a node in the graph, a kNN graph (k=5) is treated as the graph structure so that GNNs can be applied in Clothing1M datasets. This setting is similar to some previous works which also aim to apply GNNs in datasets without graph structure. ResNet-50 with ImageNet pretrained weights is utilized by us to extract feature vectors for all the images. Table. A.8 shows the different hyper-parameters in LPM experiments for different datasets. In all the experiments, 25 true-labeled nodes are utilized as the initial clean sets or as the samples for
finetuning and the total epoch of all the experiments is 300. In Co-teaching plus experiment, the initial epoch is 270, the forget rate is 0.1 and 5 epochs for linear drop rate ,the exponent of the forget rate is 1. For MW-Nets, the dimension of the meta net’s middle layer is 100 and the learning rate is 5 × 10−3. q for GCEloss is 0.1. The combination of Normalized Focal Loss and Mean Absolute Error is utilized in APL experiments, the weight of Normalized Focal Loss is 0.1 and the weight of Mean Absolute Error is 10. For JoCoR experiments, the epochs for linear drop rate is 5 and the exponent of the forget rate is 2. The balance coefficient between conventional supervised learning loss and contrastive loss is 0.01. The learning rate and weight decay of Graph Attention Networks are 0.01 and 5 × 10−4. The dimension of hidden layer of GAT is 16 and the number of head attentions is 8. The alpha of the leaky relu is 0.2 and the dropout rate is 0.5. Throughout this work we implemented gradient based meta-learning algorithms in PyTorch using the Higher library (Grefenstette et al., 2019).

heading: C APPENDIX : CONVERGENCE OF LPM
text: Our proof of the convergence of LPM mainly follow some previous works (Ren et al., 2018; Shu et al., 2019) that utilize meta-learning to reweight noisy training samples. As is illustrated in some previous works (Zhou et al., 2004; Zhu et al., 2005), LPA will converge to a fixed point. Namely, Dselect and Dleft will converge to fixed sets. In our proof, the final | Dleft | and final | Dclean | are denoted with n and m for easier illustration. Loss function loss is denoted by l in this proof. Here we first rewrite the forward and backward equations as follows:
ŷj = f(xj ;wt) = yj(w)|wt (17) λj = g(l(yj , ŷj) ‖ l(ỹj , ŷj); θt) = λj(θ;wt)|θt (18)
Ltr(wt; θt) = 1
n n∑ j=1 l(λjyj + (1− λj)ỹj , ŷj) (19)
ŵt(θt) = wt − α∇wLc(w; θt)|wt (20)
ŷi = f(xi; ŵt) = yi(ŵ;xi)|ŵt (21)
Lc(ŵ)|ŵt = 1
m m∑ i=1 Lci (ŵ)|ŵt = 1 m m∑ i=1 Lci (ŵt(θ))|θt = 1 m m∑ i=1 l(yi, ŷi) (22)
θt+1 = θt − β∇θLc(ŵ(θ))|θt (23) wt+1 = wt − α∇wLtr(w; θt+1)|wt (24)
(xj , yj) is node from the final left training set Dleft; (xi, yi) is node from the final clean set Dclean; f is the GCN for classification with its weights w; g is the Aggregation Net whose input are the nodes from clean set with its weights θ; Lc is the loss on clean sets. Ltr is the final training loss. l(y, ŷ) is the loss (such as Cross Entropy) which satisfies linearity given by
l(λy1 + (1− λ)y2, ŷ) = λl(y1, ŷ) + (1− λ)l(y2, ŷ).
Derivation of the equation of updating the weights in Aggregation Net
1
m m∑ i=1 ∇θLci (ŵ(θ))|θt = 1 m m∑ i=1 ∂Lci (ŵ) ∂ŵ |ŵt n∑ j=1 ∂ŵt(θ) ∂λj |θt ∂λj(θ;wt) ∂θ |θt . (25)
According to Equation (20)
ŵt(θ)|θt = wt − α∇wt 1
n n∑ j=1 l(λjyj + (1− λj)ỹj , ŷj)
∂ŵt(θ)
∂λj |θt = −
α n ∇wt ∂l(λjyj + (1− λj)ỹj , ŷj) ∂λj |θt
∂ŵt(θ)
∂λj |θt = −
α n ∇wt ∂[λj l(yj , ŷj) + (1− λj)l(ỹj , ŷj)] ∂λj |θt
∂ŵt(θ)
∂λj |θt = −
α n ∇wt(l(yj , ŷj)− l(ỹj , ŷj))|θt
∂ŵt(θ)
∂λj |θt = −
α
n ∂(l(yj , ŷj)− l(ỹj , ŷj)) ∂wt |wt
Therefore, Equation (25) can be written as
1
m m∑ i=1 ∇θLci (ŵ(θ))|θt
=− α mn m∑ i=1 ∂Lci (ŵ) ∂ŵ |ŵt n∑ j=1 ∂(l(yj , ŷj)− l(ỹj , ŷj)) ∂wt |wt ∂λj(θ;wt) ∂θ |θt
=− α n n∑ j=1 ( 1 m m∑ i=1 ∂Lci (ŵ) ∂ŵ |Tŵt ∂(l(yj , ŷj)− l(ỹj , ŷj)) ∂wt |wt) ∂λj(θ;wt) ∂θ |θt
=− α n n∑ j=1 ( 1 m m∑ i=1 Gij) ∂λj(θ;wt) ∂θ |θt ,
where Gij = ∂Lci (ŵ) ∂ŵ | T ŵt ∂(l(yj ,ŷj)−l(ỹj ,ŷj)) ∂wt |wt .
Lemma 1. Suppose the loss function l is L-Lipschitz smooth, and λ(·) is differential with a δ-bounded gradient, twice differential with its Hessian bounded by B with respcet to θ, and the loss function l(·, ·) have ρ-bounded gradients with respect to the parameter w. Then the gradient of w with respect to Lci (ŵ) is Lipschitz continuous.
Proof. The supposition is equivalent to the following inequalities,
‖∇ŵLc(ŵ)|w1 −∇ŵLc(ŵ)|w2‖ ≤ L‖w1 − w2‖, (26)
for any w1, w2;
‖∇θλ(θ;wt)‖ ≤ ρ; (27) ‖∇2θ2λ(θ;wt)‖ ≤ B; (28)
‖∇wl(yi, ŷi((ŵt(w);xi)))‖ ≤ δ. (29)
The gradient of θ with respect to loss on clean set reads
∇θLci (ŵ(θ))|θt
=− α n n∑ j=1 ∂Lci (ŵ) ∂ŵ |Tŵt ∂(l(yj , ŷj)− l(ỹj , ŷj)) ∂wt |wt ∂λj(θ;wt) ∂θ |θt
=− α n n∑ j=1 Gij ∂λj(θ;wt) ∂θ |θt
Taking the gradient of θ in both sides of the equation, we have
∇2θ2Lci (ŵ(θ))|θt = − α
n n∑ j=1 ( ∂Gij ∂θ |θt ∂λj(θ;wt) ∂θ |θt + (Gij) ∂2λj(θ;wt) ∂θ2 |θt).
For the first term in summation,
‖∂Gij ∂θ |θt ∂λj(θ;wt) ∂θ |θt‖
≤δ‖ ∂ ∂ŵ ( ∂Lci (ŵ) ∂θ |Tθt)| T ŵt ∂(l(yj , ŷj)− l(ỹj , ŷj)) ∂wt |wt‖
=δ‖ ∂ ∂ŵ (−α n n∑ k=1 ∂Lci (ŵ) ∂ŵ |Tŵt ∂(l(yk, ŷk)− l(ỹk, ŷk)) ∂wt |wt ∂λj(θ;wt) ∂θ |θt)|Tŵt ∂(l(yj , ŷj)− l(ỹj , ŷj)) ∂wt |wt‖
=δ‖(−α n n∑ k=1 ∂2Lci (ŵ) ∂ŵ2 |Tŵt ∂(l(yk, ŷk)− l(ỹk, ŷk)) ∂wt |wt ∂λk(θ;wt) ∂θ |θt)|Tŵt ∂(l(yj , ŷj)− l(ỹj , ŷj)) ∂wt |wt‖
≤δα‖∂ 2Lci (ŵ)
∂ŵ2 |ŵt‖‖ ∂(l(yk, ŷk)− l(ỹk, ŷk)) ∂wt |wt‖‖ ∂λk(θ;wt) ∂θ |θt)|ŵt‖‖ ∂(l(yj , ŷj)− l(ỹj , ŷj)) ∂wt |wt‖
≤4αLρ2δ2.
And for the second term,
‖(Gij) ∂2λj(θ;wt)
∂θ2 |θt‖ = ‖
∂Lci (ŵ)
∂ŵ |Tŵt ∂(l(yj , ŷj)− l(ỹj , ŷj)) ∂wt |wt ∂2λj(θ;wt) ∂θ2 |θt‖ ≤2Bρ2.
Therefore,
‖∇2θ2Lci (ŵ(θ))|θt‖ ≤ 4α2Lρ2δ2 + 2αρ2B. (30)
Let Lv = 4α2Lρ2δ2 + 2αρ2B ,Based on Lagrange mean value theorem, we have
‖∇θLc(ŵt(θ1))−∇θLc(ŵt(θ2))‖ ≤ Lv‖θ1 − θ2‖,
for all θ1, θ2.
Theorem 1. Suppose the loss function l is L-Lipschitz smooth, and λ(·) is differential with a δbounded gradient, twice differential with its Hessian bounded byB with respect to θ. Let the learning rate αt = min{1, kT }, for some k > 0, such that k T < 1 and learning rate βt a monotone descent sequence, βt = min{ 1L , c√ T } for some c > 0, such that L ≤ c√ T and ∑∞ t=1 βt ≤ ∞, ∑∞ t=1 β 2 t ≤ ∞. Then the loss of Aggregation Net can achieve ‖∇θLc(ŵ(θt))‖22 ≤ in O(1/ 2)steps. More specifically,
min 0≤t≤T ‖∇θLc(ŵ(θt))‖22 ≤ O( C√ T ). (31)
Proof. The iteration for updating the parameter θ reads
θt+1 = θt − β∇θLc(ŵt(θ))|θt .
In two successive iteration, observe that
Lc(ŵt+1(θt+1))− Lc(ŵt(θt)) =[Lc(ŵt+1(θt+1))− Lc(ŵt(θt+1))] + [Lc(ŵt(θt+1))− Lc(ŵt(θt))]. (32)
For the first term, given that loss function on clean set is Lipschitz smooth, we have
Lc(ŵt+1(θt+1))− Lc(ŵt(θt+1))
≤ < ∇Lc(ŵt(θt+1)), ŵt+1(θt+1)− ŵt(θt+1) > + L
2 ‖ŵt+1(θt+1)− ŵt(θt+1)‖22.
According to Equation (20) and (23),
ŵt+1(θt+1)− ŵt(θt+1) = − αt n n∑ j=1 [λj∇wl(yj , ŷj) + (1− λj)∇wl(ỹj , ŷj)]|wt+1 ,
and thus,
‖Lc(ŵt+1(θt+1))− Lc(ŵt(θt+1))‖ ≤ αtρ2 + L
2 α2tρ 2,
since the first gradient of loss function is bounded by ρ. By the Lipschitz continuity of Lc(ŵt(θ)) according to Lemma 1., it can be obtained that
Lc(ŵt(θt+1))− Lc(ŵt(θt))
≤〈∇θtLc(ŵt(θt)), θt+1 − θt〉+ L
2 ‖θt+1 − θt‖22
= 〈∇θtLc(ŵt(θt)),−βt∇θtLc(ŵt(θt))〉+ Lβ2t
2 ‖∇θtLc(ŵt(θt))‖22
=− (βt − Lβ2t
2 )‖∇θtLc(ŵt(θt))‖22.
Therefore, the Equation (32) satisfies
Lc(ŵt+1(θt+1))− Lc(ŵt(θt)) ≤ αtρ2 + L
2 α2tρ
2 − (βt − Lβ2t
2 )‖∇θtLc(ŵt(θt))‖22
(βt − Lβ2t
2 )‖22∇θtLc(ŵt(θt))‖22 ≤ αtρ2 +
L 2 α2tρ 2 − Lc(ŵt+1(θt+1)) + Lc(ŵt(θt)).
Summing up above inequalities from 1 to T , we have
T∑ t=1 (βt − Lβ2t 2 )‖∇θtLc(ŵt(θt))‖22 ≤Lc(ŵ1(θ1)) + T∑ t=1 (αtρ 2 + L 2 α2tρ 2)
T∑ t=1 (βt − Lβ2t 2 ) min t ‖∇θtLc(ŵt(θt))‖22 ≤Lc(ŵ1(θ1)) + T∑ t=1 (αtρ 2 + L 2 α2tρ 2).
Furthermore,
min t ‖∇θtLc(ŵt(θt))‖22 ≤
Lc(ŵ1(θ1)) + ∑T t=1(αtρ 2 + L2 α 2 tρ
2)∑T t=1(βt − Lβ2t 2 )
≤ 2Lc(ŵ1(θ1)) +
∑T t=1(2αtρ
2 + Lα2tρ 2)∑T
t=1(2βt − Lβ2t )
≤ 2Lc(ŵ1(θ1)) +
∑T t=1(2αtρ
2 + Lα2tρ 2)∑T
t=1(βt)
≤2L c(ŵ1(θ1)) + α1ρ 2T (2 + L)
Tβt
= 2Lc(ŵ1(θ1)
T
1 βt + α1ρ
2(2 + L)
βt
≤2L c(ŵ1(θ1)
T max{L,
√ T
k }+ min{1, k T }max{L,
√ T
k }ρ2(2 + L)
≤2L c(ŵ1(θ1)
c √ T
+ kρ2(2 + L)
c √ T
= O( 1 T ).
It holds for ∑T t=1(βt) ≤ ∑T t=1(2βt − Lβ2t ). In conclusion, it proves that the algorithm can always achieve min0≤t≤T ‖∇θLc(ŵ(θt))‖22 ≤ O( 1√T ) in T steps.
Lemma 2. Let (an)1≤n, (bn)1≤n be two non-negative real sequences such that the series ∑∞ ii an
diverges, the series ∑∞ ii anbn converges, and there exists K > 0 such that ‖bn+1 − bn‖ ≤ Kan. Then the seqences (bn)1≤n converges to 0. Proof. See the proof of Lemma A.5 in [Stochastic majorization-minimization algorithms for ].
Theorem 2. Suppose the loss function l is L-Lipschitz smooth and have ρ-bounded gradients with respect to training data and clean set, and λ(·) is differential with a δ-bounded gradient twice differential with its Hessian bounded by B with respect to θ. Let the learning rate αt = min{1, kT }, for some k > 0, such that kT < 1 and learning rate βt a monotone descent sequence, βt = min{ 1 L , c√ T } for some c > 0, such that L ≤ c√ T and ∑∞ t=1 βt ≤ ∞, ∑∞ t=1 β 2 t ≤ ∞. Then
lim t→∞
‖∇wtLtr(wt; θt+1)‖22 = 0.
Proof. It is obvious that at satisfy ∑∞ t=0 at =∞, ∑∞ t=0 at ≤ ∞. In Eq. 18, 19, 20, and the linearity of L, we rewrite the update of w as
wt+1 = wt − αt∇Ltr(wt; θt+1)
= wt − αt n n∑ j=1 λj(θt+1;wt)∇wt l(yj , ŷj(wt)) + (1− λj(θt+1;wt))∇wt l(ỹj , ŷj(wt)).
First, we have the difference of the loss function on training set between two iterations,
Ltr(wt+1; θt+2)− Ltr(wt; θt+1) =[Ltr(wt+1; θt+2)− Ltr(wt+1; θt+1)] + [Ltr(wt+1; θt+1)− Ltr(wt; θt+1)]. (33)
For the first term in Eq.33, by the L-Lipschitz-smooth and ρ−bounded gradients of λ with respect to training and clean set,
Ltr(wt+1; θt+2)− Ltr(wt+1; θt+1)
= 1
n n∑ j=1 (λj(θt+2;wt+1)− λj(θt+1;wt+1))l(yj , ŷ(wt+1)) + (λj(θt+1;wt+1)− λj(θt+2;wt+1))l(ỹj , ŷj(wt+1))
≤ 1 n n∑ j=1 ( 〈 ∂λj(θ;wt+1) ∂θ |θt+1 , θt+2 − θt+1 〉 + δ 2 ‖θt+2 − θt+1‖22)(l(yj , ŷ(wt+1)) + l(yj , ŷ(wt+1)))
= 1
n n∑ j=1 ( 〈 ∂λj(θ;wt+1) ∂θ |θt+1 ,−βt∇θtL(ŵt(θt)) 〉 + δβ2t 2 ‖∇θtL(ŵt(θt))‖22)(l(yj , ŷ(wt+1)) + l(yj , ŷ(wt+1))).
For the second term in Eq. 33,
Ltr(wt+1; θt+1)− Ltr(wt; θt+1) ≤ 〈 ∇wtLtr(wt; θt+1), wt+1 − wt 〉 + L
2 ‖wt+1 − wt‖22
=− (αt − La2t
2 )‖∇wtLtr(wt; θt+1)‖22.
Therefore, we have
Ltr(wt+1; θt+2)− Ltr(wt; θt+1)
≤ 1 n n∑ j=1 ( 〈 ∂λj(θ;wt+1) ∂θ |θt+1 ,−βt∇θtLc(ŵt(θt)) 〉
+ δβ2t 2 ‖∇θtL(ŵt(θt))‖22)(l(yj , ŷ(wt+1)) + l(yj , ŷ(wt+1))) −(αt − Lα2t
2 )‖∇wtLtr(wt; θt+1)‖22.
Summing up the inequalities in both sides from t = 1 to∞, we have
lim t→∞
‖Ltr(wt+1; θt+2)− Ltr(w1; θ2)‖
≤ ∞∑ t=1 −βt n n∑ j=1 [‖∂λj(θ;wt+1) ∂θ |θt+1‖2‖∇θtLc(ŵt(θt))‖2(‖l(yj , ŷ(wt+1))‖2 + ‖l(yj , ŷ(wt+1))‖2)
+ ∞∑ t=1 δβ2t 2 n∑ j=1 ‖∇θtLc(ŵt(θt))‖22](‖l(yj , ŷ(wt+1))‖2 + ‖l(yj , ŷ(wt+1))‖2)
− ∞∑ t=1 (αt − Lα2t 2 )‖∇wtLtr(wt; θt+1)‖22.
Rearrange the terms of the inequality, we obtain ∞∑ t=1 αt‖∇wtLtr(wt; θt+1)‖22
+ ∞∑ t=1 βt n n∑ j=1 ‖∂λj(θ;wt+1) ∂θ |θt+1‖2‖∇θtLc(ŵt(θt))‖2(‖l(yj , ŷ(wt+1))‖2 + ‖l(yj , ŷ(wt+1))‖2)
≤Lα 2 t
2 ‖∇wtLtr(wt; θt+1)‖22
+ ∞∑ t=1 δβ2t 2 n∑ j=1 ‖∇θtLc(ŵt(θt))‖22](‖l(yj , ŷ(wt+1))‖2 + ‖l(yj , ŷ(wt+1))‖2)
− lim t→∞ ‖Ltr(wt+1; θt+2)‖2 + ‖Ltr(w1; θ2)‖2
≤ ∞∑ t=1 Lαt 2 ρ2 + ‖Ltr(w1; θ2)‖2 + ∞∑ t=1 δβ2t 2 (2Mρ2)− lim t→∞ ‖Ltr(wt+1; θt+2)‖2
≤∞. The inequality next to last holds since our loss function is bounded by M , and the last one holds for∑∞ t=1 α 2 t and ∑∞ t=1 β 2 t are finite.
In addition, since ∞∑ t=1 βt n n∑ j=1 ‖∂λj(θ;wt+1) ∂θ |θt+1‖2‖∇θtLc(ŵt(θt))‖2(‖l(yj , ŷ(wt+1))‖2 + ‖l(yj , ŷ(wt+1))‖2)
≤2Mρδ ∞∑ t=1 βt ≤ ∞,
we can obtain that ∞∑ t=1 αt‖∇wtLtr(wt; θt+1)‖22 ≤ ∞. (34)
In the other hand, based on the inequality: (‖a‖+ ‖b‖)(‖a‖ − ‖b‖) ≤ ‖a+ b‖‖a− b‖,
we have |‖∇Ltr(wt+1; θt+2)‖22 − ‖∇Ltr(wt; θt+1)‖22|
=(‖∇Ltr(wt+1; θt+2)‖2 + ‖∇Ltr(wt; θt+1)‖2)(‖∇Ltr(wt+1; θt+2)‖2 − ‖∇Ltr(wt; θt+1)‖2) ≤‖∇Ltr(wt+1; θt+2) +∇Ltr(wt; θt+1)‖2‖‖2‖∇Ltr(wt+1; θt+2)−∇Ltr(wt; θt+1)‖2 ≤(‖∇Ltr(wt+1; θt+2)‖2 + ‖∇Ltr(wt; θt+1)‖2)‖∇Ltr(wt+1; θt+2)−∇Ltr(wt; θt+1)‖2) ≤2Lρ‖(wt+1, θt+2)− (wt, θt+1)‖2 ≤2Lραtβt‖(∇Ltr(wt, θt+1),∇Lc(wt, θt+1))‖2 ≤2 √ 2Lρ2β1αt
=Cαt.
For Eq. 34 which reads ∞∑ t=1 αt‖∇wtLtr(wt; θt+1)‖22 ≤ ∞,
since ∑∞ t=0 αt = ∞, and there exists K = C > 0, such that |‖∇Ltr(wt+1; θt+2)‖22 − ‖∇Ltr(wt; θt+1)‖22| ≤ Cαt, by Lemma 2., we can conclude that lim t→∞ ‖∇wtLtr(wt; θt+1)‖22 = 0,
which indicates that the gradient of loss on training set of our algorithm will finally achieve to zero, and thus the iteration of w enables training loss to converge.

Review summaries:
The paper proposes a robust training algorithm for graph neural networks against label noise. The authors assume the labeled nodes are divided into two parts, clean part without noise and train part with some noise. The proposed method contains two parts. Firstly, it leverages label propagation (LP) trained on the clean nodes to assign pseudo labels on train nodes with noisy labels. Secondly, the authors design a learnable weight \lambda to learn the label for those noisy nodes where LP does not agree with the original labels. The final graph neural network is trained with clean nodes, high confidence train nodes, and uncertain train nodes with learned labels. The authors conduct experiments on four graph datasets with manual injected noise and one real-world noisy dataset to validate the proposed method.