Curriculum Learning for Graph Neural Networks: Which Edges Should We Learn First
Authors: Zheng Zhang
Junxiang Wang
Liang Zhao
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph neural networks
Curriculum learning
Graph structure learning
TL;DR: We propose a novel curriculum learning method to gradually involve edges in the training of graph neural networks.

Abstract: Graph Neural Networks (GNNs) have achieved great success in representing data with dependencies by recursively propagating and aggregating messages along the edges. However, edges in real-world graphs often have varying degrees of difficulty, and some edges may even be noisy to the downstream tasks. Therefore, existing GNNs may lead to suboptimal learned representations because they usually treat every edge in the graph equally. On the other hand, Curriculum Learning (CL), which mimics the human learning principle of learning data samples in a meaningful order, has been shown to be effective in improving the generalization ability and robustness of representation learners by gradually proceeding from easy to more difficult samples during training. Unfortunately, existing CL strategies are designed for independent data samples and cannot trivially generalize to handle data dependencies. To address these issues, we propose a novel CL strategy to gradually incorporate more edges into training according to their difficulty from easy to hard, where the degree of difficulty is measured by how well the edges are expected given the model training status. We demonstrate the strength of our proposed method in improving the generalization ability and robustness of learned representations through extensive experiments on nine synthetic datasets and nine real-world datasets. The code for our proposed method is available at https://github.com/rollingstonezz/Curriculum_learning_for_GNNs

Curriculum Learning for Graph Neural Networks: Which Edges Should We Learn First
Zheng Zhang! Junxiang Wang Liang Zhao Emmrr University, Atlanta, GA NEC Labs America, Princeton, NJ {zheng. zhang, liang. Gemory. edu {junxiang. wang Ga Cmmmmmiiiiimammmmmmmmmmmmmm.mmmm emory. .ed
Abstract
Graph Neural Networks (GNNs) have achieved great success in representing data with dependencies by recursively propagating and aggregating messages along the edges. However, edges in real-world graphs often have varying degrees difficulty, and some edges may even be noisy to the downstream tasks. Therefore, existing GNNs may lead to suboptimal learned representations because they usually treat every edge in the graph equally. On the other hand, Curriculum Learning (CL), which mimics the human learning principle of learning data samples in a meaningful order, has been shown be effective in improving the generalization ability and robustness of representation learners by gradually proceeding from easy more difficult samples during training. Unfortunately, existing CL strategies are designed for independent data samples and cannot trivially generalize to handle data dependencies. To address these issues, we propose a novel CL strategy gradually incorporate more edges into training according to their difficulty from easy to hard, where the degree of difficulty is measured by how well the edges are expected given the model training status. We demonstrate the strength of our proposed method in improving the generalization ability and robustness of learned representations through extensive experiments on nine synthetic datasets and nine real-world datasets. The code for our proposed method is available at https //github. com/ rollingstonezz/uurrr wttp//urrrruuuuuu.cmmo waatlmeeeeannnneneeee Sor_ffor_GNos
Introduction
Inspired by cognitive science studies [8 33 that humans can benefit from the sequence of learning basic (easy) concepts first and advanced (hard) concepts later, curriculum learning (CL) 2 suggests training a machine learning model with easy data samples first and then gradually introducing more hard samples into the model according to a designed pace, where the difficulty of samples can usually be measured by their training loss (25). Many previous studies have shown that this easy- easy-to-hard learning strategy can effectively improve the generalization ability of the model 2 19 [5] [1 35 46).
and some studies [19
15 III have shown that CL strategies can also increase the robustness of the learned model against noisy training samples. An intuitive explanation is that CL settings noisy data samples correspond to harder samples, and CL learner spends less time with the harder (noisy) samples to achieve better generalization performance and robustness.
Although CL strategies have achieved great success in many fields such as computer vision and natural language processing, existing methods are designed for independent data (such as images) while designing effective CL. methods for data with dependencies has been largely underexplored. For example, in a citation network, two researchers with highly related research topics (e.g. machine learning and data mining) are more likely to collaborate with each other, while the reason behind a collaboration of two researchers with less related research topics (e.g. computer architecture and social science) might be more difficult to understand. Prediction one sample impacts that of another, forming graph structure that encompasses all samples connected by their dependencies. There are
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

many machine learning techniques for such graph-structured data, ranging from traditional models like conditional random field [6)., graph kernels [37], to modern deep models like GNNs (2 30 52
38
49
12
53 42 However, traditional CL strategies are not designed to handle the curriculum of
the dependencies between nodes in graph data, which are insufficient. Handling graph-structuree
data require not only considering the difficulty in individual samples, but also the difficulty of their dependencies to determine how to gradually composite correlated samples for learning.
As previous CL strategies indicated that an easy-to-hard learning sequence on data samples can improve the generalization and robustmess performance, an intuitive question is whether a similar strategy on data dependencies that iteratively involves easy-to-hard edges in learning can also benefit. Unfortunately, there exists no trivial way to directly generalize existing CL strategies on independent data to handle data dependencies due to several unique challenges: (1) Difficulty in quantifying edge selection criteria. Existing CL. studies on independent data often use supervised computable metrics (e.g. training loss) to quantify sample difficulty, but how to quantify the difficulties of understanding the dependencies between data samples which has no supervision is challenging.
(2) Difficulty in designing an appropriate curriculum to gradually involve edges. Similar to the human learning process, the model should ideally retain a certain degree of freedom to adjust the pacing of including edges according to its own learning status. As existing CL methods for graph data typically use fixed pacing function to involve samples. they can not provide this flexibility. Designing an adaptive pacing function for handling graph data is difficult since it requires joint optimization of both supervised learning tasks on nodes and the number of chosen edges. (3) Difficulty in ensuring convergence and numerical steady process for CL in graphs. Discrete changes in the number of edges can cause drift in the optimal model parameters between training iterations. How to guarantee a numerically stable learning process for CL on edges is challenging.
In order to address the aforementioned challenges, in this paper, we propose a novel CL algorithm named Relational Curriculum Learning (RCL) to improve the generalization ability and robustness of representation learners on data with dependencies. To address the first challenge, we propose an approach to select the edges by quantifying their corresponding difficulties in a self-supervised learn- ing manner. Specifically, for each training iteration, we choose K easiest edges whose corresponding relations are most well-expecter by the current model. Second, to design appropriate learning pace for gradually involving more edges in training, we present the learning process as a concise optimization model, which automatically lets the model gradually increase the number K to involve more edges in training according to its own status. Third, to ensure convergence of optimizing the model, we propose alternative optimization algorithm with theoretical convergence guarantee and an edge reweighting scheme to smooth the graph structure transition. Finally, we demonstrate the superior performance of RCL compared to tffe-of-the-ane comparison methods through extensive experiments on both synthetic and real-world datasets.
2 Related Works
Curriculum Learning (CL). Bengio et al. pioneered the concept of Curriculum Learning (CL) within the machine learning domain, aiming to improve model performance by gradually including easy to hard samples in training the model. Self-paced learning 2.5 measures the difficulty of samples by their training loss, which addressed the issue in previous works that difficulties of samples are generated by prior heuristic rules. Therefore, the model can adjust the curriculum of samples further proposed many supervised measurement metrics for determining curriculums, for example, the diversity of samples [17 or the consistency of model predictions [55] Meanwhile, many empirical and theoretical studies were proposed to explain why CL could lead to generalization improvement from different perspectives. For example, studies such as MentorNet [19] and Co-teaching (15) empirically found that utilizing CL strategy can achieve better generalization performance when the given training data is noisy. [TI] provided theoretical explanations on the denoising mechanism that CL learners waste less time
according to its own training status. Following works [88 17 55
with the noisy samples as they are considered harder samples. Some studies (2 35 46 13 24 also realized that CL can help accelerate the optimization process of non-convex objectives and improve the speed of convergence in the early stages of training.
Despite great success, most of the existing designed CL strategies are for independent data such as images, and there is little work on generalizing CL strategies to handle samples with dependencies.
Few existing attempts on graph-structured data [26] 21 28 such 44] 5 45 28), simply treat

---

(a)
Incremental Edge Selection (IES)
Residual graph
Refined structure
Latent embedding
GNN
Decoder
d
Top K
expected
y + y
(b)
IES
IES
IES
Training process T
Figure 1: The overall framework of RCL. (a) The Incremental Edge Selection module first extracts the latent node embedding by the GNN model given the current training structure, then jointly learns the node prediction label y and reconstructs the imput structure by decoder. A small residual error on an edge indicates the corresponding dependency is well expected and thus can be added to the refined structure for the next iteration. (b) The iterative learning process of RCL. The model starts with an empty structure and gradually includes more edges until the training structure converges to the input structure.
nodes as independent samples and then apply CL strategies on independent data, which ignore the fundamental and unique dependency information carried by the structure in data, and thus can not well handle the correlation between data samples. Furthermore, these models are mostly based on heuristic-based sample selection strategies these methods.
28 which largely limit the generalizability of
Graph structure learning. Another stream of existing studies that are related to our work is graph structure learning. Recent studies have shown that GNN models are vulnerable to adversarial attacks on graph structure 48). In order to address this issue, studies in graph structure learning usually aim to jointly learn an optimized graph structure and corresponding graph representations.
54 31 typically consider the hypothesis that the intrinsic graph structure should be sparse or low rank from the original input graph by pruning "irrelevant" edges. Thus, they typically use pre-deterministic methods
Existing works [9 4 20,
(56 9 to preprocess graph structure such singular value decomposition (SVD), or dynamically remove "redundant" edges according to the downstream task performance the current sparsified structure [4] 20, 31] However, modifying the graph topology will inevitably lose potentially useful information lying in the removed edges. More importantly, the modified graph structure is usually optimized for maximizing the performance on the training set, which can easily lead to overfitting issues.
3 Preliminaries
Graph neural networks (GNNs) are a class of methods that have shown promising progress in representing structured data which data samples correlated with each other. Typically, the data samples are treated as nodes while their dependencies are treated as edges in the constructed graph. Formally,
denote graph G (V,E), where V {ei, u2,..... UN is that N = [V] denotes the number of nodes in the graph and E C V is the set of edges. We also let X E R-Nx6 denote the node attribute matrix and let E NRN represent matrix. Specifically, Ay denotes that there is edge connecting nodes u, and U/ V, otherwise Ag = A GNN model ff maps the node feature matrix X associated with the adjacency matrix A to the model predictions fXX, A). and get the loss LGNN L(ý, y). where L is the objective function and y is the ground-truth label of nodes. The loss on one node 2 denoted as 4 L(gee v.).
of nodes
adjacency
Methodology
As previous CL methods have shown that an easy-to-hard learning sequence of independent data samples can improve the generalization ability and robustness of the representation learner, the goal of this paper is to develop an effective CL method on data with dependencies, which extremely difficult due several unique challenges: (1) Difficulty in designing feasible principle to select

---

edges by properly quantifying their difficulties. (2) Difficulty in designing appropriate pace of curriculum to gradually involve more edges in training based on model status. (3) Difficulty in ensuring convergence and numerical steady process for optimizing the CL model.
In order to address the above challenges, propose novel CL method named Relational Curriculum Learning (RCL). The sequence, which gradually includes edges from easy to hard, is called curricu- lum and learned in different grown-up stages of training. In order address the first challenge, we propose a self-supervised module Incremental Edge Selection (IES), which is shown in Figure aa), to select the K easiest edges at each training iteration that are mostly expected by the current model. The details are elaborated in Section 4.1 To address the second challenge, we present joint optimization framework to automatically increase the number of selected edges K given its own training status. The framework is elaborated in Figure[T[b and details can be found in Section 4.2 Finally, to ensure convergence of optimization and steady the numerical process, we propose an EM-style alternative optimization algorithm with theoretical convergence guarantee in Section 4.2 Algorithm and an edge reweighting scheme to smooth the discrete edge incrementing process Section
4.1 Incremental Edge Selection by Quantifying Difficulties of Sample Dependencies
Here we propose novel way select edges by first quantifying their difficulty levels. Existing works on independent data typically use supervised metrics such as training loss of samples to quantify their difficulty level, but there exists no supervised metrics on edges. To address this issue, we propose self-supervised module Incremental Edge Selection (IES). We first quantify the difficulty of edges by measuring how well the edges are expected from the currently learned embeddings of their connected nodes. Then the most well-expected edges are selected as the easiest edges for the next iteration of training. As shown in Figure I [)), given the currently selected edges iteration t. we first feed them to the GNN model to extract the latent node embeddings. Then we restore the latent node embeddings to the original graph structure through a decoder, which is called the reconstruction of the original graph structure. The residual graph R. which is defined as the degree of mismatch between the original adjacency matrix A and the reconstructed adjacency matrix A (*), can be considered a strong indicator for describing how well the edges are expected by the current model. Specifically, a smaller residual error indicates higher probability of being a well-expected edge.
With the developed sulf-super method to measure the difficulties of edges, here we formulate the key learning paradigm of selecting the top K easiest edges. To obtain the training adjacency matrix A (4) that will be fed into the GNN model f(1), we introduce a learnable binary mask matrix S with each element Siy E (0, 1). Thus, the training adjacency matrix at iteration t can be represented as (1) (*) A. To filter out the edges with K smallest residual error, penalize the summarized residual errors over the selected edges, which can be represented as Σij R.g. Therefore, the learning objective can be presented as follows:
minL + +33 +8>S, S.
2
s.t. |||| 2
where the first term LGNN L(J(X, A (0); w). is the node-level predictive loss, e.g. cross-entropy loss for the node classification task. The second term Σx, R.j aims at penalizing the residual errors over the edges selected by the mask matrix S. 8 is a hyperparameter to tune the balance between terms. The constraint is guarantee only the most K well-expected edges are selected.
More concretely, the value of a residual edge A (t) E [0, 1] can be computed by non-parametric kernel function x(z," (A) ((t).. e.g. the inner product kernel. Then the residual error R.j between
the input structure and the reconstructed structure can be defined as | A where || is commonly chosen to be the squared noomm
4.2 Automatically Control the Pace of Increasing Edges
In order to dynamically include more edges into training, an intuitive way is to iteratively increase the value of K in Equation to allow more edges to be selected. However, it is difficult to determine an appropriate value of K with respect to the training status of the model. Besides, directly solving

---

Algorithm Alternating Minimization Algorithm for Optimizing Equation 2
Input: Node features X. adjacency matrix stepsize y and hyperparameter 7 Output: Parameters w of GNN model f
I: Initialize w()), 8(9), A
2: while Not converged de
3: w(t) any ming [X A ww) + Sis A Ass +
|w w(t
4: Given w("), extract latent nodes embedding Z from GNN model f
5: Calculate reconstructed structure A. x(x) (9, xx)") for all pairs of i.
6: $09 arg ming / 2in Siy |A, A! ((: + |s S
7: Compute A ( A
8: A of then
9: Increase X by stepsize j
10: end
11: end while
10, optimizing S Equation 1 is difficult since S is a binary matrix where each element S E {0, 1), would require solving discrete constraint program at each iteration. To address this issue, we first relax the problem into continuous optimization so that each S,j can be allowed to take any value in the interval [0, 1]. Note that the inequality ||S||| 2 K in Eqn. D equivalent to the equality |||||| = K. This is because the second term in the Ioss function would always encourage fewer selected edges by the mask matrix S, as all values in the residual error matrix R and mask matrix S are nonnegative. Given this, we can incorporate the equality constraint as Lagrange multiplier and rewrite the loss function as L LGNN + 3 Ei, Sty - A([|S]I1 - K). Considering that K remains constant, the optimization of the loss function can be equivalently framed by substituting the given constraint with regularization term denoted g(;; A). As such, the overall loss function can be reformulated as:
min LGNN + B ESS + (S: W,S
1.j
where (S; A|S A| and ||-|| commonly chosen to be the squared fz-norm. Since the training adjacency matrix A (0) S @ A, as - co, more edges in the input structure are included until the training adjacency matrix A (1) converges to the input adjacency matrix A. Specifically, the regularization term g(; X) controls the learning scheme by the age parameter X, where À = X(t) grows with the number of iterations. By monotonously increasing the value of X, the regularization term g(S A) will push the mask matrix gradually converge to the imput adjacency matrix A, resulting in more edges automatically involved in the training structure.
Optimization of learning objective. optimizing the objective function Equation 2 we need to jointly optimize parameter w for GNN model I and the mask matrix S. To tackle this, we introduce an EM-style optimization scheme (detailed in Algorithm 1) that itcratively updates both. The algorithm uses the node feature matrix X, the original adjacency matrix A, a step size μ to control the age parameter À increase rate, and a hyperparameter y for regularization adjustments. Post initialization of w and S, it alternates between: optimizing GNN model f (Step 3), extracting latent node embeddings and reconstructing the adjacency matrix (Steps 4 & 5), refining the mask matrix using the reconstructed matrix and regularization, and results in more edges are gradually involved (Step 6), updating the training adjacency matrix (Step 7), and incrementing À when the training matrix A (t) differs from input matrix A, incorporating more edges in the next iteration.
Theorem 4.1. We have the following convergence guarantees for Algorithm 1:
Avoidance of Saddle Points. If the second derivatives of L(f(X, A 19; w))w),y) and g(S; X) are continuous, then for sufficiently large 7, any bounded sequence (w("), s(t) generated by Algorithm
1 with random initializations will not converge to a strict saddle point of F almost surely.
Second Order Convergence. If the second derivatives of T.[[(X, A A w) and g(S; X) are continuous, and L(f(X, A (6) y) and g(S; X) satisfy the Saadykka-ojjsiewiizz (KL) property [4] then for sufficiently large % any bounded sequence (w(t), s(+)) generated by Algorithm with random initialization will almost surely converge to recond-order stationary point of F.
The detailed proof can be found in Appendix B
5

---

4.3 Smooth Structure Transition by Edge Reweighting
Note that in the Algorithm 1, the optimization process requires iteratively updating the parameters of the GNN model f and current adjaceney matrix A A where A (t) varies discretely between iterations. However, GNN models mostly work in a messsae-passingg fashion, which computes node representations by iteratively aggregating information along edges from neighboring nodes, Discretely modifying the number of edges will result in a great drift of the optimal model parameters between iterations. In Appendix Figure. we demonstrate that a shift in the optimal parameters of the GNN results in a spike in the training loss. Therefore, it can increase the difficulty of finding optimal parameters and even hurt the generalization ability of the model in some cases. Besides the numerical problem caused by discretely increasing the number of edges, another issue raised by the CL strategy in Section 4.1 is the trustworthiness of the estimated edge difficulty, which is inferred by the residual error on the edges. Although the residual error can reflect how well edges are expected in the ideal case, the quality of the learned latent node embeddings may affect the validity of this metric and compromise the quality of the designed curriculum by the CL. strategy.
To address both issues, we propose novel edge reweighting scheme (1) smooth the transition of the training structure between iterations, and (2) reduce the weight of edges that connect nodes with low-confidence latent embeddings. Formally, we use a smoothed version of structure A (+) to substitute A (t) for training the GNN model f in step 3 of Algorithm 1, where the mapping from A (t) to A (f) can be represented as:
A
A 35
(1)) is the weight imposed on edge eij at iteration L. TH is calculated by considering the where ii counted occurrences of edge ety until the iteration t. and the confidence of the latent embedding for the connected pair of nodes ey and uy:
(t)
(4)
where vp is a function that reflects the number of edge occurrences and is a function to reflect the degree of confidence for the learned latent node embedding. The details of these two functions are described as follow.
Smooth the transition of the training structure between iterations. In order obtain a smooth transition of the training structure between iterations, we take the learned curriculum of selected edges into consideration. Formally, we model v by smooth function of the edge selected occurrences compared to the model iteration occurrences before the current iteration:
(ee) t(egg)/,,
where l is the number of current iterations and t(e;)) represents the counting number of selecting edge Eij. Therefore, we transform the original discretely changing training structure into a smoothly changing one by taking the historical edge selection curriculum into consideration.
Reduce the influence of nodes with low confidence latent embeddings. As introduced in our Algorithm 1 line 6, the estimated structure Á is inferred from the latent embedding Z. which is extracted from the trained GNN model f. Such estimated latent embedding may possibly differ from the true underlying embedding, which results in the inaccurately reconstructed structure around the node. In order to alleviate this issue, we model the function p by the training loss on nodes, which indicates the confidence of their learned latent embeddings. This idea is similar to previous CL strategies on inferring the difficulty of data samples by their supervised training loss. Specifically, larger training loss indicates a low confident latent node embedding. Mathematically, the weights p(v:) on node can be represented as distribution of their training loss:
p(v))
(6)
where 4 is the training loss on node v. Therefore, a node with a larger training loss will result in a smaller value of p(u;). which reduces the weight of its connecting edges.
5 Experiments
In this section, the experimental settings are introduced first in Section 5.1 then the performance of the proposed method on both synthetic and real-world datasets are presented in Section 5.2 We further present the robustness test on our CL method against topological structure noise in Section 5.3

---

Table 1: Node classification accuracy synthetic datasets (%). The best- persfrerforming method on each backbone GNN model is highlighted in bold, while the second-best method is underlined. In situations where RCL's performance is not strietly the best among all methods, we can see that almost
all methods can achieve a near-perfect performance and RCL is still close to the best methods.
Homo radlo
0.1
0.2
0.3
0.4
0.6
0,7
0.8
0.9
GCN
50.84:1:033
56.50=0.50
65.1740.48
07.94
87.15200.44
93.27.00.4
97,48=0.25
99.10
99.93:1.003
GNNSVD
54.96:0.76
58.45-0.56
63.06:0.63
70.23:00611
80.51:00.41
85.02:00.6
90.31=0.27
94.23
96. 96.74:20.23
ProtiNN
47.87+0877
54.59-0.55
65.39+0.44
76.96-0.49
87.76+0.51
94.1640334
97 6.-00.3
99.04+0.19
99.94-0003
NeuralSparse
51.42+1.33
57.99-
65.10-043
75.37-0:34
87.40+0.29
93.54+0.28
97. 07.16-0.15
99.01+0.22
99,83-+0.07
PTDNet
48.21=1998
55.52-2822
65.82:0.54
79.37=0045
89 19.17:00.39
94,19:20188
98.61=0.122
99.51=00.09
99.1:=0005
CLNodes
50.3740.73
0,564-0.56
65.0110.66
17.52:0.48
86.8510.44
93.10.1.47
97.34.0.25
99,0210.118
99.88.10.04
57.57+0.43
62.06 0.28
73,98 0.55
04.54-0.75
97.42--0.17
99.62-0.05
0.05
GIN
48,3311.99
53.221139
64.0810.99
17
85.3110.75
90.5710.56
97.82
19.3910.11
95.1110.02
GNNSVD
43.21++.60
1..68-1.6
54.9+ 1.16
08.29-0079
79.76+0.52
85.63++044
03.65-0.39
97. 97.22-00117
98.94+00.17
ProGNN
45.76+1.40
52.96=1.01
64.12:1107 07
069
13+0071
89 59
06.54
99.51 01
99.78:20.00
NeuralSparse
50.2342.05
1,512-1.52
62.8110.775
16198_1.17
05.1440..4
92.5740.44
98.02-0.20
99.61
99.91
PTDNet
53.23442766
56.12-2.03
65.81+1.38
77.81=1022
86.
93.2140.74 04.0
97 0.44
08
99.91 +0.03
CLNodes
45.36+11.42
11.10=1.155
62.53+0 88
76+00.90
9.90
94.25-+044
98.30=0.26
09.60=00009
99.92:00.03
RCL
57.63:10.66
1.17
0.602:0.61
0.66
83.62:0.43
94.810.36
18
99 0.
99.89110.04
GraphSAGE
62.5710:35
07.33-0.644
71.061074
80 0.
914421037
05.26-00.3
99.52:10.33 10
GNNSVD
64.42+00.80
65.71-0.39
67.12+0.58
68 07
70-00-0.65
82 02.86+0.50
87.81-0.71
60.50.55
95.01 +0.50
ProGINN
58,5742.09
66.75=00.1
0.
01
86
077
22.10:00.99
05.21=0.30
97.5 97.51=00.23
99.50.20.11
NeuralSpurse
61.70:10.77
66.65=0.66
70.6010.79
09.65
84.1910.91
91.3110544
94. 0.55
99.55 0..16.10.23
PTDNet
65.72+11.08
72.60-00.7 09.25-0.92
79 05.65-0.45
86.56+0
91.29++0.33
10-0..8
97.98+001 19.98.00.1
CLNodes
69.41:00.66
70.83-0.58
75.51=0.36 36
82 43
87.08:0.556
91.58:0441
95.91
9R. 55++0 26
99.57=00.11 14
RCL
68.03-10.37
0.53
76,99.10.99
03.76.00.55
88.2410.30
93.3410.56
97,66-0.52
08.86.10.28
99.64.10.88
We verify the effectiveness of framework components through ablation studies in Section55.4 Intuitive visualizations of the edge selection curriculum are shown in Scction In addition, measure the parameter sensitivity in Appendix (A. and running time analysis in Appendix due to the space limit.
5.1 Experimental Settings
Synthetic datasets. To evaluate the effectiveness of our proposed method on datasets with ground- truth difficulty labels on edges, we follow previous studies [22 [ to generate set of synthetic datasets, where the formation probability of an edge is designed to reflect its likelihood to positively contribute the node classification job, which indicates its ground-truth difficulty level. Specifically, the nodes in a generated graph are divided into 10 equally sized node classes 2,.,..., 10, and the node features are sampled from overlapping multi- Gaussian distributions. Each generated graph is associated with a homophily coefficient (homo) which indicates the probability of a node forming an edge to another node with the same label. For the rest edges that are formed between nodes with different labels, the probability of forming an edge is inversely proportional to the distances between their labels. Nodes with close classes are more likely to be connected since the formation probability decreases with the distance of the node label, and connections from nodes with close classes can increase the likelihood of accurately classifying a node due to the homophily property of the designed node classification task. Therefore, an edge with a high formation probability indicates higher chance to positively contribute to the node classification task because connects a node with a close class, and thus can be considered an easy edge. We vary the value of homo to generate nine graphs in total. More details and visualization about the synthetic dataset can be found in Appendix/A..
Real-world datasets. To further evaluate the performance of our proposed method in real- world scenarios, nine benchmark real-world attributed network datasets, including four citation network datasets Cora, Citeseer, Pubmed [5T) and ogbn-arxiv [16], two coauthor network datasets CS and
Physics 3 two Amazon co-purchase network datasets Photo and Computers 34), and one protein interation network ogbn-proteins [16] We follow the data splits from 3 on citation networks and use a 5-fold cross-validation setting on coauthor and Amazon co-purchase networks. All datasets are publicly available from Pytorch-geometric library where basic statistics are reported in Table
[00 and Open Graph Benchmark (OGB) [16).
Comparison methods. We incorporate three commonly used GNN models, including GCN 23 GraphSAGE [14], and GIN [50], as the baseline model and also the backbone model for RCL. In addition to evaluating our proposed method against the baseline GNNs, we further leverage two categories of state-of-the-as art comparison methods in the experiments: (1) We incorporate four graph structure learning methods GNNSVD 9. ProGNN (20), NeuralSparse 54 and PTDNet 31: (2)
We further compare with a curriculum learning method named CLNode
45 which gradually select
nodes in the order of the difficulties defined by a heuristic-based strategy. More details about the comparison methods can be found in Appendix A.1
7

---

Table 2: Node classification results real-world datasets (%). The best-performing method on each backbone is highlighted in bold and second-best is underlined. (OOM) shorts for out-of-memory.
Cora
Clesser
Pubmed
CS
Plysics
Photo
Compulers
ogbn-arxiv
ogbn-proieens
nodes
2,70s
3.327
19.717
18,333
34,493
13,752
169,343
132.534
At edges
10,556
9,104
88,648
163,78
495,924
238.162
491,722
1,166.243
39,561,252
* lealures
1,433
3,703
500
6,805
8,415
745
767
100
OCN
05.74
87.91
55.0010
0..25
29
GNNSVD
83.24221.03
74.8020.87
88.81
93.79
96.1110.133
0..6340.73
06.4910.77
67.4410.51
66.92-0.61
ProGNN
85.66:20.61
7..75
87.22-0.33
94.04 19
96.75 06.75
92.07=00.67
88.72-0.59
(0OM)
(OOM)
NeuralSpurse
05.95
76.2440.48
86.83-0.40
92.31
95. 35.5610.30 30
90.57.0.90
88.62.0.83
(00M)
(00M)
PTDNNer
83:84=0.5
93
06.56+00.09
88.92+00.7
87.52=0070
(OOM)
(00M)
CLNode
85.67=0.33
78 99-99-015 57
89 50 0.28
93.
0.20
95. 76:20 16
03.39-083
89 89.28-00.W
10
71.40=0.32
RCI.
87.15-0..44
79.79+1.55
N9.79
0.12
94.66 0.32
97.02+0.23
94.41 0.76
90.3
74,88+0.33
75.19 0.26
GIN
05.6210.30
2610.3
74.1
GNNSVD
82.23:10.65
72. 12..1
88.31 0.15
01.40
95 05.30....29
89.49.1.111
22.56.2.26
67.7910.41
00.65
POGNN
85.02=0.41
78.12+0.90
87.82 0.51
(00M)
(O0M)
92.23-00.7
83.54+1 18
(OOM)
(OOM)
NeuralSparse
04.92:0.58
0..87
86.11=0.49
89 0.82
95 05:05:0:57
03
87.2240.54
(O0M)
(00M)
PTTNNer
83.02=1001
75 00:000077744
88.0
01
95 57-00-40 40
00
(OOM)
(OOM)
CL.Node
83.52=0.77
75.8 08
86.92-00 0.61
91.21+04
95.75-0446
92.78+0.90
85 93+
10:58+0.177
73:97-0.11
RCL
0..64
77. 60:00000000 18
19.17-0.22
0.27
96.75:0.7
93.88
091
72.55:00155
7..76:0.22
GraphSAGE
58.50 0.16
91 11
191010277
07.6
GNNSVD
83.11=0882
73. 49:
88.42-0.. 38
03
95 95.96+0.11
00.31
81 46
02:004334
7182-0039
ProGNN
86.23:.0.42
14.4
88.52-0.45
(0OM)
(OOM)
00.89
89 $9.3410.54
(OOM)
(OOM)
NeuralSpurse
84.00-0.52
56.32+0.55
39
93 89-0
96 07677+0220 20
90.78-1.06 1.06
37-37-
(OOM)
(00M)
PTDNett
58.78
03.78:0.43
95. 3240333
02.96=00.87
89
(OOM)
(00M)
CL.Node
06.60-0164
77:23++0.54
88. 76 0.57
94. 13+00.44
96.87 96877+045
93.90=0.42
N9577-0.62
71 54+00000
78.40=041
RCI.
86.90- 0.39
78.95-0.118
90.14 0143
95.05-0.233
96.88
00.56
73.13-0114
79,89- 0.35
Initializing graph structure by a pre-trained model. It is worth noting that the model needs an initial training graph structure A (0) in the initial stage of training. An intuitive way is that we can initialize the model to work in purely data-driven scenario that starts only with isolated nodes where no edges exist. However, an instructive initial structure can greatly reduce the search cost and computational burden. Inspired by many previous CL works 46 13 19 [55] that incorporate prior knowledge of a pre-trained model into designing curriculum for the current model, we initialize the training structure A (0) by a pre-trained vanilla GNN model f". Specifically, we follow the same steps from line 4 to line 7 in the algorithm node embedding is extracted from the pre-trained model f"
obtain the initial training structure A (0) but the latent
Implementation details. We use the baseline model (GCN, GIN, GraphSAGE) as the backbone model for both our RCL method and all comparison methods. For a fair comparison, we require all models follow the same GNN architecture with two convolution layers. For each split, we run each model 10 times reduce the variance in particular data splits. Test results are according the best validation results. General training hyperparameters (such as learning rate or the number of training epochs) are equal for all models.
5.2 Effectiveness Results
Table 1 presents the node classification results of the synthetic datasets. We report the average accuracy and standard deviation for each model against the homo of generated graphs. From the table, we observe that our proposed method RCL consistently achieves the best most competitive performance to all the comparison methods over three backbone GNN architectures. Specifically, RCL outperforms the second best method on average by 4. 4.17% 2.60%, and 1.06% on GCN, GIN, and GraphS AGE backbones, respectively. More importantly, the proposed RCL method performs significantly better than the second best model when the homo of generated graphs is low (< 0.5), on average by 6.55% on GCN, 4. 1.17 on GIN, and 2.93% on GraphSAGE backbones. These demonstrate that our proposed RCL method significantly improves the model's 's capability of learning an effective representation to downstream tasks especially when the edge difficulties vary largely in the data.
We report the experimental results of the real-world datasets in Table 2 The results demonstrate the strength of our proposed method by consistently achieving the best results in all 9 datasets by GCN backbone architecture, all 9 datasets by GraphSAGE backbone architecture, and 8 out of 9 datasets by GIN backbone architecture. Specifically, our proposed method improved the performance of bascline models on average by 1.86%, 2.83%, and 1.62% over GCN, GIN, and GraphS and outperformed the second best models model on average by 1.37%, 2.49% and 1.22% over the three backbone models, respectively. The results demonstrate that the proposed RCL method consistently improves the performance of GNN models in real-world scenarios.
Our experimental results are statically sound. In 43 out of 48 tasks our method outperforms the second-best performing model with strong statistical significance. Specifically, we have in 30 out of 43 cases with significance p 0.001, in 8 out of 43 cases with significance p < 0.01, and in 5
8

---

Figure 2: Node classification accuracy (%) Cora and Citeseer under random structure attack. The attack edge ratio computed versus the original number of edges, where 100% means that the number of inserted edges is equal to the number of original edges.
Cora,
Citsseer GCN
Citeseer, GIN
0.00
0.85
0.75
Acciracy
0.80
0.70
0.73
0.75
0.65
0.60
0.70
0.56
0.53
00 Attack edge (%)
60 Attack edge (%)
Attack edge (%)
Attack edge (%)
-6-
basic
- GNNSVD
ProGNN
Noural Sparse
PTDNet
CLNode
-
RCL
Table 3: Ablation study. Here "Full" represents the original method without removing any component. The best-performing method on each dataset is highlighted in bold.
Syntheticl
Synthetic2
Citeseer
CS
Computers
Full
73.98=0.55
97.42:0.17
79.79=00.55
94.66=0.22
90.23:0.233
Curriculum- lineer
70.93-0.554
95.19+0.19 19
79.0440.38
94.14-0.26
89.28-+0.21
Curriculum root
70.13.1.772
95.5010.18
78.27.0..4
94.47.0.34
89.27.10.15
Random-lines
58.76-0046
89:78+0.11
77.43+0.49
92.76-0.14 14
88.76++0.18
Random rool w/o edge appearance
61.04.10.20
91.0410.09
76.81
92.92.1.115
88.81
70.70:1.:43
95.7710.16
77.77:0.65
94.3920.21
89.56:10.30
w/o node confidence
72.38=00441
96.86+0.17
78.72=0.72
94.34=0.13
90.03=0062
w/o pre-trained model
72.56=00.99
93.89+0.14
78.28-+0.77
94.50=0. 14
89 80-+0.55
out of 43 cases with a significance p < 0.05. Such statistical significance results can demonstrate that our proposed method can consistently perform better than the baseline models in both scenarios.
5.3 Robustness Analysis Against Topological Noise
To further examine the robustness of the RCL method on extracting powerful representation from correlated data samples, we follow previous works [20 31 to randomly inject fake edges into real-world graphs. This adversarial attack can be viewed as adding random noise to the topological structure of graphs. Specifically, we randomly connect M pairs of previously unlinked nodes in the real-world datasets, where the value of A varies from 10% to 100% of the original edges. We then train RCL and all the comparison methods on the attacked graph and evaluate the node classification performance. The results are shown in Figure[] we can observe that RCL shows strong robustmess to adversarial structural attacks by consistently outperforming all compared methods on all datasets. Especially, when the proportion of added noisy edges is large (> 50%), the improvement becomes more significant. For instance, under the extremely noisy ratio at 100%, RCL outperforms the second best model by 4.43% and 2.83% on Cora dataset, and by 6. 1,1%% 3.4 3.47% on Citeseer dataset, with GCN and GIN backbone models, respectively.
5.4 Ablation Study
To investigate the effectiveness of our proposed model with some simpler heuristics, we deploy a series of abalation analysis. We first train the model with node classification task purely and select the top expected edges as suggested by the reviewer. Specifically, we follow previous works [43] 45 using two classical selection pacing functions follows:
t Kinear (t) = - EE Root: Kroot - --V
Linear:
where t is the number of current iterations and T is the number of total iterations, and |E| is the number of total edges. We name these two variants Curriculum-linear and Curriculum-root, respectively. In addition, we also remove the edge difficulty measurement module and use random selection instead. Specifically, we gradually incorporate more edges into training in random order to verify the effectiveness of the learned curriculum. We name two variants as Random- -inear and Random-root with the above mentioned pacing functions, respectively.
In order to further investigate the impact of the proposed components of RCI.. We also first consider variants of removing the edge smoothing components mentioned in Section 4.3 Specifically,

---

GCN
GIN
GraphSage
1.0
1.0
1.
Easy
Easy
Easy
0.8
Medium
0.8
Medium
0.8
Medium
Herd
Hard
Hard
Raãio
0.6
0.6
0.6
0.2
0.2
0.2
0.0
0.0
0.0
50
:00
150
50
100
150
50
100
150
Epachs
Epochs
Epochs
Figure 3: Visualization of edge selection process during training,
consider two variants w/o EC and w/o NC, which remove the smoothing function of the edge occurrence ratio and the component to reflect the degree of confidence for the latent node embedding in RCL, respectively. In addition to examining the effectiveness of edge smoothing components, we further consider a variant w/o pre-trained model that avoids using pre-trained model to initialize model, which is mentioned Section 5.1 to initialize the training structure by a pre-trained model and instead starts with inferred structure from isolated nodes with no connections.
We present the results of two synthetic datasets (homophily coefficient= 0.3, 0.6) and three real-world datasets in Table 3 We summarize our findings from the above table as below: (i) Our full model consistently outperforms the two variants Curriculum-lnnes and Curriculum-root by an average of 1.59% on all datasets, suggesting that our pacing module can benefit model training. It is worth noting that these two variants also outperform the baseline vanilla GNN model Vanilla by an average of 1.92%, which supports the assumption that even a simple curriculum learning strategy can still improve model performance. (ii) We observe that the performance of the two variants Random-line and Random-root on all datasets drops by 3.86% average compared to the variants Curriculum- linear and Curriculum-rrot. Such behavior demonstrates the effectiveness difficulty quantification module by showing that randomly involving edges into training cannot benefit model performance. (ii) We can observe a significant performance drop consistently for all variants that remove the structural smoothing techniques and initialization components. The results validate that all structural smoothing and initialization components can benefit the performance of RCL on the downstream tasks.
our proposed edge
5.5 Visualization of Learned Edge Selection Curriculum
Besides the effectiveness and robustness of the RCL method on downstream classification results, it is also interesting to verify whether the learned edge selection curriculum satisfies the rule from easy to hard. Since real-world datasets do not have ground-truth labels of difficulty on edges, we conduct visualization experiments on synthetic datasets, where the difficulty of each edge can be indicated by its formation probability. Specifically, we classify edges into three balanced categories according their difficulty: easy, medium, and hard. Here, we define all homogenous edges that connect nodes with the same class as easy, edges connecting nodes with adjacent classes as medium, and the remaining edges connecting nodes with far away classes as hard. We report the proportion of edges selected for each category during training in Figure 3 We can observe that RCL can effectively select most of the easy edges at the early stage of training, then more easy edges and most medium edges are gradually included during training, and most hard edges are left unselected until the end stage of training. Such edge selection behavior is highly consistent with the core idea of designing a curriculum for edge selection, which verifies that our proposed method can effectively design curriculums to select edges according to their difficulty from easy to hard.
6 Conclusion
This paper focuses on developing novel CL method to improve the generalization ability and robustness of GNN models on learning representations of data samples with dependencies. The proposed method Relational Curriculum Learning (RCL) effectively addresses the unique challenges in designing CL strategy for handling dependencies. First, a self-supervised learning module is developed select appropriate edges that are expected by the model. Then an optimization model is presented to iteratively increment the edges according to the model training status and a theoretical guarantee of the convergence on the optimization algorithm given. Finally, an edge reweighting scheme is proposed to steady the numerical process by smoothing the training structure transition. Extensive experiments on synthetic and real-world datasets demonstrate the strength of RCL. in improving the generalization ability and robustness.
10

---

Acknowledgement
This work was supported by the National Science Foundation (NSF) Grant No. 1755850, No. 1841520, No. 2007716, No. 2007976, No. 1942594, No. 1907805, a Jeffress Memorial Trust Award, Amazon Research Award, NVIDIA GPU Grant, and Design Knowledge Company (subcontract number: (0827.002.) (0..000...100))... 120.04). The authors acknowledge Emory Computer Science department for providing computational resources and technical support that have contributed the experimental results reported within this paper.
References
[1] Sami Abu-EI-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 international conference on machine learning, pages 21-29. PMLR, 2019.
[2] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41 41-48,
2009.
[3] Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. International Conference on Learning Representations, 2018.
[4] Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in neural information processing systems, 33:19314-19322 2020.
[5] Guanyi Chu, Xiao Wang, Chuan Shi, and Xunqiang Jiang. Cuco: Graph representation with curriculum contrastive learning. In IJCAI, pages 2300-2306, 2021.
[6] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 13:13,, 2020.
[7] Hanjun Dai. Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song, Adversarial attack on graph structured data. In International conference on machine learning. pages 1115 1124. PMLR, 2018
[8] Jeffrey L Elman. Learning and development in neural networks: The importance of starting small. Cognition, 48(1):71-99, 1993.
(9] Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks graphs. In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 169-177, 2020.
[10] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 022428, 2019.
[11) Tieliang Gong, Qian Zhao, Deyu Meng, and Zongben Xu. Why curriculum learning & self- paced learning work in big/noisy data: theoretical perspective. Big Data Information Analytics, 1(1):111 2016.
[12] Xiaojie Guo, Shiyu Wang, and Liang Zhao Graph neural networks: Graph transformation. Graph Neural Networks: Foundations, Frontiers, and Applications, pages 251-275, 2022.
[13] Guy Hacohen and Daphna Weinshall. On the power of curriculum learning in training deep networks. In International Conference on Machine Learning, pages 2535-2544. PMLR, 2019.
[14] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[15] Bo Han, Quamming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. Advances in neural information processing systems, 31, 2018
11

---

[16] 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 preprini arXiv:2005.00687. 2020.
[17] Lu Jiang, Deyu Meng, Shoou-I Yu, Zhenzhong Lan, Shiguang Shan, and Alexander Hauptmann. Self-paced learning with diversity. Advances in neural information processing systems, 27, 2014.
[18] Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander G Hauptmann. Self Self-paced curriculum learning. In Twenty-ninth AAAI conference on artificial intelligence, 2015.
[19] Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data-driven curriculum for very deep neural networks on corrupted labels. In International conference on machine learning, pages 2304-2313. PMLR, 2018.
[20] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 66-74, 2020.
[21] Wei Ju, Zheng Fang, Yiyang Gu, Zequn Liu, Qingqing Long, Ziyue Qiao, Yifang Qin, Jianhao Shen, Fang Sun, Zhiping Xiao, al. A comprehensive survey on deep graph representation learning. arXiv preprint arXiv:2304.05055 2023.
[22] Fariba Karimi, Mathieu Génois, Claudia Wagner, Philipp Singer, and Markus Strohmaier. Homophily influences ranking of minorities in social networks. Scientific reports, 8(1):1-12, 2018.
[23] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations, 2017.
[24] Yajing Kong, Liu Liu, Jun Wang, and Dacheng Tao. Adaptive curriculum learning. In Pro- ceedings of the IEEE/CVF International Conference on Computer Vision, pages 5067-5076, 2021.
[25] M Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. Advances neural information processing systems, 23, 2010.
[26] Haoyang Li, Xin Wang, and Wenwu Zhu. Curriculum graph machine learning: A survey. arXiv preprint arXiv:2302.08 02926, 2023.
[27] Qiuwei Li, Zhihui Zhu, and Gongguo Tang. Alternating minimizations converge to second-order optimal solutions. In International Conference on Machine Learning, pages 3935-3944 PMLR, 2019.
[28] Xiaohe Li, Lijie Wen, Yawen Deng, Fuli Feng, Xuming Hu, Lei Wang, and Zide Fan. Graph neural network with curriculum learning for imbalanced node classification. arXiv preprint arXiv:2202.02529, 2022.
[29] Chen Ling, Junji Jiang, Junxiang Wang, and Zhao Liang. Source localization of graph diffusion via variational autoencoders for graph inverse problems. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pages 1010-1020, 2022.
[30] Chen Ling, Junji Jiang, Junxiang Wang, My T Thai, Renhao Xue, James Song, Meikang Qiu, and Liang Zhao. Deep graph representation learning and optimization for influence maximization. In International Conference on Machine Learning, pages 21350-21361. PMLR, 2023.
[31] Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingehao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM international conference on web search and data mining, pages 779-787, 2021.
12

---

[32] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga. et al. Pytorch: An imperative style, nigh-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[33] Douglas LT Rohde and David C Plaut. Language acquisition in the absence of explicit negative evidence: How important is starting small? Cognition, 72(1):67-109, 1999.
[34] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:/811.05868 2018.
[35] Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick, Training region-based object detectors with online hard example mining. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 761-769, 2016.
[36] Charles Sutton, Andrew McCallum, et al. An introduction to conditional random fields. Foundations and Trends in Machine Learning, 4(4):267-373, 2012.
[37] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201-1242, 2010.
[38] Junxiang Wang. Junji Jiang, and Liang Zhao. An invertible graph diffusion neural network for source localization. In Proceedings of the ACM Web Conference 2022, pages 1058-1069, 2022.
[39] Junxiang Wang, Hongyi Li, Zheng Chai, Yongchao Wang. Yue Cheng, and Liang Zhao. Toward quantized model parallelism for graph-augmented mips based on gradient- free admm framework. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[40] Junxiang Wang, Hongyi Li, and Liang Zhao. Accelerated gradient-fre free neural network training by multi-convex alternating optimization. Neurocomputing, 487: 133-13,, 2022.
[41] Junxiang Wang, Fuxun Yu, Xiang Chen, and Liang Zhao. Admm for efficient deep learning with global convergence. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 111-119, 2019.
[42] Shiyu Wang. Xiaojie Guo, and Liang Zhao. Deep generative model for periodic graphs. Advances in Neural Information Processing Systems, 35, 2022.
[43] Xin Wang, Yudong Chen, and Wenwu Zhu. A survey on curriculum learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, (49):4555-4574 2021.
[44] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Curgraph: Curriculum learning for graph classification. In Proceedings of the Web Conference 2021, pages 1238-1248, 2021.
[45] Xiaowen Wei, Weiwei Liu, Yibing Zhan, Du Bo, and Wenbin Hu, Clnode: Curriculum learning for node classification. arXiv preprint arXiv:2206.077 07258, 2022.
[46] Daphna Weinshall, Gad Cohen, and Dan Amir. Curriculum learning by transfer learning: Theory and experiments with deep networks. In International Conference on Machine Learning, pages 5238 5246. PMLR, 2018
[47] Richard Lee Wheeden and Antoni Zygmund. Measure and integral, volume 26. Dekker New York, 1977.
[48] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Ad- versarial examples for graph data: deep insights into attack and defense. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 4816-4823, 2019.
[49] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, (2(1):4-244 2020.
[50] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
13

---

[51] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi- sumi-supe learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[52] Zheng Zhang and Liang Zhao. Representation learning on spatial networks. Advances in Neural Information Processing Systems, 34:2303-223 2318, 2021.
[53] Zheng Zhang and Liang Zhao. Unsupervised deep subgraph anomaly detection. In 2022 IEEE International Conference Data Mining (ICDM), pages 753-762. IEEE, 2022.
[54] Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni. Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pages 1458-11468. PMLR, 2020.
[55] Tianyi Zhou, Shengjie Wang, and Jeff Bilmes. Robust curriculum learning: from clean label de- tection to noisy label self-correction. In International Conference on Learning Representations, 2020.
[56] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference knowledge discovery & data mining, pages 2847-2856, 2018.
14

---

A Additional Experimental Settings and Results
A.1 Additional Experimental Settings
Figure 4: Visualization of synthetic datasets. Each color represents class of nodes. Node attributes are sampled from overlapping labels are likely to have short distances. Homogemeous edges represent edges that connect nodes of the same class (with the same color). The probability of connecting two nodes of different classes decreases with the distance between the center points of their class distribution. Therefore, the formation probability of a node denotes the edge difficulty, since edges between nodes with close classes are more likely positively contribute the prediction under the homogeneous assumption.
distributions, where the attributes of nodes with close
Synthetic datasets. To evaluate the effectiveness of our proposed method on datasets with ground- truth difficulty labels on structure, first follow previous studies 22 [ to generate set of synthetic datasets, where the difficulty of edges in generated graphs are indicated by their formation probability. Specifically, as shown in Figure each generated graph is with 5,000 nodes, which are divided into 10 equally sized node classes 1, 2,, 2..... 10. The node features are sampled from overlapping multi- Gaussian distributions. Each generated graph is associated with a homophily coefficient (homo) which indicates the likelihood of a node forming a connection to another node with the same label (same color in Figure 4 For example, a generated graph with homo 0.5 will have on average half of the edges formed between nodes with the same label. For the rest edges that are formed between nodes with different labels (different colors in Figure 4. the probability of forming an edge inversely proportional to the distances between their labels. Mathematically. the probability of forming an edge between node and node follows Pu-ro e llc -co, where the distances between labels Icu Col means shortest distance of two classes on a circle. Therefore, the probability of forming an edge in the synthetic graph can reflect how well this edge is expected. Specifically, edges with a higher formation probability, e.g. connecting nodes with the same label or close labels, meaning that there is higher chance that this connection will positively contribute to the prediction (less chance to be a noisy edge). Conversely, edges with lower formation probability, e.g., connecting nodes with faraway labels, mean that there is higher chance that this connection will negatively contribute to the prediction (higher chance to be a noisy edge). We vary the value of homo from 0.1, ... 0.9 generate nine graphs in total. Similar to previous works [22 []] we randomly partition each synthetic graph into equal-sized train, validation, and test node splits.
Implementation Details. We use the baseline model (GCN, GIN, GraphSage) as the backbone model for both our RCL method and all comparison methods. For a fair comparison, we require all models follow the same GNN architecture with two convolution layers. For each split, we run each model 10 times to reduce the variance particular data splits. Test results are according to the best validation results. General training hyperparameters (such as learning rate the number of training
15

---

epochs) are equal for all models. For the pre- rre-trained model to initialize the training structure, we utilize the same model the backbone model utilized by our method. For example, if we use GCN as the backbone model for RCI., the pre-trained model to initialize is also GCN. All experiments are conducted on a 64-bit machine with four NVIDIA Quadro RTX 8000 GPUs. The proposed method implemented with Pytorch deep learning framework (22
The following describes the details of our comparison models.
Graph Neural Networks (GNNs). We first introduce three baseline GNN models as follows.
(i) GCN. Graph Convolutional Networks (GCN) 22 is a commonly used GNN, which introduces first-order approximation architecture of the Chebyshev spectral convolution operator;
(ii) GIN. Graph Isomorphism Networks (GIN) 50 is variant of GNN, which has provably powerful discriminating power among the class of 1-order GNNs;
(iii) GraphSage. GraphSage [4] is a GNN method that computes the hidden representation of the
root node by aggregating the hidden node representations hierarchically from bottom to top.
Graph structure learning. We then introduce four state-of-the-art methods for jointly learning the optimal graph structure and downstream tasks.
(i) GNNSVD. GNNSVD 9 first apply singular value decomposition (SVD) the graph adjacency matrix to obtain low-rank graph structure and apply GNN on the obtained low-rank structure;
(ii) ProGNN. ProGNN (20 is method to defend against graph adversarial attacks by obtaining sparse and low-rank graph structure from the input structure;
(iii) NeuralSparse. NeuralSparse (54) is method to learn robust graph representations by iteratively sampling k-neighbor subgraphs for each node and sparsing the graph according the performance on the node classification;
(iv) PTDNee. PTDNet [31] learns sparsified graph by pruning task-irrelevan edges, where sparsity controlled by regulating the number of edges.
Curriculum learning on graph data. We introduce recent curriculum learning work on node classification as follows.
(i) CLNode. CLNode 45 regards nodes as data samples and gradually incorporates more nodes into training according their difficulty. They apply heuristic-based strategy measure the difficulty of nodes, where the nodes that connect neighboring nodes with different classes are considered difficult.
Searching space for hyperparameters.
Number of epochs trained: (150, 500];
Learning rate for model: {1c-2, 5e 5e-3, 1c-3);
Number of GNN layers: {2);
Dimension of hidden state: (64);
Age parameter X : 2, 3, 4, 5) (A larger value indicates faster pacing for adding edges, where
denotes the training structure will converge to the input structure the final iteration).
A.2 Additional Effectiveness Experiments on Heterophilic Datasets
Dataset
Edge homo ratio
GCN
GCN-RCL
GIN
GIN-RCL
Texas
0.11
0.5645
0.6006
0.5885
0.6156
Cornell
0.30
0.4084
0.5045
0.4234
0.4925
Wisconsin
0.21
0.4923
0.5294
0.5141
0.5599
Actor
0.22
0,2868
0.3186
0.2678
0.3006
Squirrel
0.22
0,2743
0.2999
0.2347
0.2519
Chameleon
0.23
0.3625
0.4385
0.3233
0.4033
Table 4: Node classfication results for six real-world heterophilic datasets, where the best performance of each model category one dataset is highlighted.
16

---

In order to further verify the effectiveness of our proposed strategy on heterophilic graph datasets, we have included new experiments on six real-world heterophilic datasets, As shown in Table 4 our method consistently improve performance of backbone GNN models on these heterophilic datasets. Secifically, RCL. outperforms the second best method on average by 5.04%, and 4.55% on GCN and GIN backhones, respectively. The results can demonstrate our method is not limited to homophily graphs.
Although the inner product decoder utilized in experiments might imply an underlying homophily assumption, our method can still benefit from leveraging the edge curriculum present within the input datasets. A reasonable explanation is that standard GNN models are usually struggled with the heterophily edges, while our methodology designs a curriculum allowing more focus on homophily edges, which potentially leads to the observed performance boost.
A.3
Additional Effectiveness Experiments on PNA Backbone Model.
Dutasct
PNA
PNA-RCL
PNA-linear
PNA-root
GCN
GCN-RCL
GCN-lineur
GCN-root
Synthetic-0.3
0.6982
0.7667
0,7463
0.7445
0.6517
0.7398
0.6641
0.6533
Synthetic-0.5
0.8742
0,9016
0,8476
0.8704
0.8715
0,9269
0.8494
0.8854
Synthetic-0.7
Cora 0.9658
0,9821
0,9514
0.9766
0,9748
0.9962
0,9712
0,9796
0.8521
0,8145
0.8254
0.8574
0.8715
0.8327
0.8553
Citeseer
0.7478
0.7652
0.7482
0.7505
0.7893
0.7979
0.7723
0.7814
Computers 0.8989
0.9096
0,8866
0.89755
0.8809
0.9023
0.8713
0.8985
ogbn-urxiv 0.7175
0.7441
0.6980
0.7242
0.7174
0.7408
0.7288
0.7359
Table 5: Node classfication results for our method and traditional CL methods using PNA and GCN
as backbone. Here '-RCL' denotes our method, while '-linear' and '-root' denotes two traditional CL methods with different pacing functions.
In Table 5 new experiments that adopt modern GNN architecture PNA model [6] have been added. From the table we can observe that our proposed method improves the performance PNA backbone by 2.54% on average. which further verified the effectiveness of our method under different choices of backbone GNN model.
In addition, Table 5 we further include two traditional CL methods for independent data as additional baselines, following classical works 25 We employed the supervised training loss of pretrained GNN model as the difficulty metric, and selected two well-established pacing functions for curriculum design: linear and root pacing, defined follows:
Linear: Kiinear (t) -
IV] -
Root: Kroot V
L
where t the number of current iterations and is the number of total iterations, and [V] is the number of nodes.
We utilized GCN and PNA as backbone architectures, identified by the suffixes '-lierrr' and "-rott.. Across all datasets, the results consistently demonstrate that our proposed method outperforms traditional CL approaches.
A.4 Additional Robustness Experiments on PNA Backbone Model.
We present further robustness test against random noisy edges by using the PNA backbone model. The results are shown Table which further proves that our curriculum learning approach improves the robustness against edge noise with the advanced PNA model the backbone.
A.5 Time Complexity Analysis
Here we consider GCN as the backbone. First, the time complexity of T-layer GCN is ( b))) where b is the number of node attributes. Second, the time complexity of mcasuring the
17

---

Datasct
Method
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
Cora
PNA
0,8310
0.7911
0.7621
0.7402
0.7331
0.7210
0.6894
0.7042
0.6792
0.6617
Cora
PNA-RCL
0.8521
0.8315
0,8162
0.7969
0.7992
0.7951
0.7571
0.7642
0.7457
0.7371
Citescer
PNA
0.7478
0.7195
0.7184
0.6934
0.6952
0.6920
0.6852
0.6552
0.6481
0.6327
Citeseer
PNA-RCL
0.7652
0.7422
0.7222
0.7254
0.7041
0.7012
0.6953
0.6921
0.6884
0.6794
Table 6: of number of added random edges to the original edges.
Further robustness test using PNA as backbone model. Here the percentage denotes the ratio
Synthetic
Citeseer
Computers
ogbn-arxiv
ogbn-proteins
Vanilla
7.32s
3,90
16.88s
55.22s
1438.21s
GNNSVD
11.49s
3.82s
35,96s
135.72s
2632.42s
CLNode
6.29s
3.96s
17.02s
58.53s
1545.53s
ProGNN
220.25s
72.42s
1953.23s
(-)
NeuralSparse
310.02s
88.91s
6553,34s
(-)
(-)
PTDNet 153.43s
48.42s
2942.02s
(-)
(-)
Ours
4.07s
2.42s
14.62s
71.49s
2239.05s
Table 7: Running time of our method and comparison methods. Here (-) denotes out-of- error and Vanilla denotes the standard GNN model.
difficulty levels of edges by reconstruction O(EE)) where is the number latent embedding dimensions. Third, the time complexity of selecting the edges to add is O((E)) Therefore, the total time complexity of our algorithm is (Lb + d) + L|V (2)
In addition, we compare the total running time of our method and all comparison methods in the Table We can observe that the running time of our proposed method is comparable that of standard GNN models in all datasets. Notably, our method is even faster than standard GNN models in some datasets. One possible reason is that at the beginning of training, the graphs in our model have much fewer edges than those in standard GNN models. Therefore, the computational cost of the GNN model is also reduced.
A.6 Parameter Sensitivity Analysis
Recall that RCL learns a curriculum to gradually add edges in given input graph structure the training process until all edges are included. An interesting question is how the speed of adding edges will affect the performance of the model. Here we conduct experiments of age parameter À which controls the speed of adding edges to the model performance. Here larger value of means that the training structure will converge the input structure earlier. For example. À = means that the training structure will probably not converge to the input structure until the last iteration, and 5 means that the training structure will converge the input structure around half of the iterations are complete, and then the model will be trained with the full input structure for the remaining iterations. We present the results on two synthetic datasets (homophily coefficient= 0.3, 0.6) and two real-world datasets in Figure 5 As can be seen from the figure, the classification results are steady that the average standard deviation only 0.41 %. It is also worth noting that the peak values for all datasets consistently appear around À 3, which indicates that the best performance is when the training structure converges to the full input structure around two-thirds of the iterations are completed.
explore the impact
Synthetic1
Synthetic2
88.0
Accorssy
92.5
79.5
22
92.0
87.0
79.0
21
78.5
86.0
Figure 5: Parameter sensitivity analysis on four datasets. Here a larger value of À means the training structure will converge to the original structure at an earlier training stage.
18

---

A.7
Visualization of Importance on Smoothing Component
2.0
Ours
w/o smoothing
1.5
Training loss
1.0
0.5
0.0
0
20
40
60
80
100
120
140
# Epochs
Figure 6: The comparison between our full model and the version without smoothing technique on the training loss trend.
Our experimental results demonstrated the importance of applying our smoothing component in stablizing the optimization process of training. 6 shows that without the smoothing technique, the training loss spiked that reflects the GNN parameter shifts, which was caused by the number of edges discretely changed. However, after adding the smoothing technique, the training loss can smoothly converge, hence, the smoothing technique plays an important role in stabilizing the training process.
B Mathematical Proof
Theorem 1.
We have the following convergence guarantees for Algorithm 1:
Avoidance of Saddle Points If the second derivatives of L(J(X, A (8); w),y) and g(;; A) are continuous, then for sufficiently large y, any bounded sequence (w(t), (w((),(())) generated by Algorithm strict saddle point of F almost surely.
1 with random initializations will not converge
Second Order Convergence If the second derivatives of L(f(X, A (t); w).y) and g(S; A) are continuous, and L(f(X, A (9; w), and g(S; A) satisfy the Lojasswi (KL) property 40, then for sufficiently large y, any bounded sequence (v(())(())) generated by Algorithm I with random initialization will almost surely converges to a second-order stationary point of F.
Proof. We prove this theorem by Theorem 10 and Corollary from 27
[Avoidance of Saddle Points] Because the sequence (y(())S() is bounded, and the second derivatives of L and are continuous, then they are bounded. In other words, we have max V L(f(X, A (0); (()). (
([V >)Dl} I p. where p > 0 is a constant. Simi-
larly, it easy to check that the second derivative of the term Σi, S.g
A A.j is bounded,
i... maxt
V2 Eig
S.j
A
Ais
V
En, Siz A
} S g. where >> 0 is Ani
constant and A is function of Therefore, it means that the objective F is bi-smooth, i.c. F F $ + q. In other words, F satisfies Assumption from [27]. Moreover, the second derivative of F is continuous. For any 7 generated by Algorithm will not converge striet saddle of almost surely by Theorem 10 from
max{ V |.
g, any bounded sequence (w()), (())
27
[Second Order Convergence] From the above proof of avoidance of saddle points, we know that F satisfies Assumption 4 from 27 Moreover, because L and g satisfy the KL property, and the term
Σ,, Sij A
Aij
satisfies the KL property, we conclude that F satisfy the KL property as
19

---

well. From the proof above, we also know that the second derivative of F is continuous. Because continuous differentiability implies Lipschitz continuity 47). it infers that the first derivative of F is Lipschitz continuous. As result, F satisfies Assumption from [27] Because F satisfies Assumptions and 4, then for any > + q, any bounded sequence (w(t), generated by Algorithm I will almost surely converges second-order stationary point of F F' Corollary from
27
While the convergence of Algorithm entails the second-order optimality conditions of f and g. some commonly used f such as the GNN with sigmoid or tanh activations and some commonly used g such as the squared l norm satisfy the KL property [39 40), and Algorithm guaranteed to avoid a strict saddle point and converges second-order stationary point.
20


Reviews:
[{"review_id": "2IcCMbMce4", "reviewer": "Reviewer_u5nt", "summary": "This paper proposes a curriculum learning (CL) method for graph neural networks on the node classification task. Existing CL strategies are mostly designed for indepedent data samples, and cannot trivially generalize to graphs that contain data dependencies. The proposed solution, termed as Relational Curriculum Learning (RCL), learns to select edges from easy to hard in each iteration. The overall idea is to formulate curriculum learning as an optimization problem w.r.t. a discrete mask over the edges. Since it is hard to optimize the discrete mask, the authors relax the goal and alternatively optimize the GNN parameters and the edge mask in an EM fashion. Tricks like edge reweighting are applied to stablize the change in the edge mask. Experiments on synthetic datasets and 9 real-world datasets verify the effectiveness of RCL, though the improvement on real-world datasets are marginal given that RCL requires a pre-trained vanilla GNN model for initialization.", "questions": "- Q1: Line 12-15: How does the proposed model handle the data dependency issue? It is not explicitly mentioned.\n- Q2: Line 30-42: Can you describe the basic idea of traditional CL strategies and why they are insufficient for graphs? Can you describe how the dependencies in graphs impose a challenge for traditional CL methods?\n- Q3: Line 51-57: Why is it difficult to design an appropriate curriculum to gradually involve edges? Does the difficulty for convergence only hold for your method or any CL methods in general?\n- Q4: Line 65-66: You introduced the optimization model as a solution to an appropriate learning pace. How does the optimization model result in autoamtically increasing the number K to involve more edges? Some logic or description is missing here.\n- Q5: Line 163: Does $\\odot$ mean element-wise multiplication here?\n- Q6: Line 170: The constraint, plus the residual errors, guarantee that only the most K well-expected edges are selected, right?\n- Q7: Line 171-172: Please cite VGAE[1] for this dot-product style link prediction design.\n- Q8: Algorithm 1 Line 6: Is the argmin taken over continuous S space or binary S space? I presume it’s continuous space here.\n- Q9: Line 197-198: What do you mean by “the proximal terms” here?\n- Q10: How do you guarantee that the number of edges grow monotonically during the curriculum learning?\n- Q11: Why is the performance on Cora, Citeseer, PubMed higher than literature? Did you use a split other than the original split in the GCN paper? The authors should clarify that.\n- Typos:\n    - Title: Graph Neural Network → Graph Neural Networks\n    - Line 11: cannot be trivially generalized to → cannot trivially generalize to\n    - Line 195: You may add a reference link to Algorithm 1.\n    - Line 200: extracts → extract\n    - Line 219: recursively → iteratively\n    - Table 2: GraphSage → GraphSAGE\n    - Sec. 5.3: attck → attack\n\n[1] Kipf and Welling. Variational Graph Auto-Encoders. NIPS 2016 workshop.", "limitations": "The authors don’t discuss the limitations and societal impacts in the paper. I would suggest the authors adding one paragraph to discuss that. For example, some limitations could be that RCL requires a longer training time since it needs to first train a vanilla GNN model and then finetune it with curriculum learning.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- S1: This paper proposes a curriculum learning method tailored to the need of node representation learning. Unlike classical CL methods that learn to select easy samples, RCL uses all node labels but learns to select easy edges for GNN propagation.\n- S2: This paper conducts experiments on both synthetic datasets and real-world datasets. It achieves consistent improvement on 3 backbone GNN models and 9 real-world datasets, though the improvement is marginal.", "weaknesses": "- W1: This paper is badly written and not very easy to follow. The title is not precise considering the proposed model. I would suggest changing it to “Edge Curriculum Learning for Node Classification with Graph Neural Networks”, as the model only applies to homogeneous graphs rather than multi-relational graphs. The 2nd paragraph in the intro doesn’t have a good undelying logic. For example, why traditional CL strategies are insufficient is not clarified. The challenges claimed in the 3rd paragraph are also very weak. To my understanding, the first challenge might be a real one for classical CL methods, but the other two challenges seem to be fabricated for the proposed model, not general to CL methods. The first 2 paragraphs of Sec. 4 just repeat two paragraphs from the introduction.\n- W2: There are some math and concept errors in the core statement of the proposed model. Eqn. 2 is not a faithful usage of Lagrange multiplier (or KKT conditions since the constraint is an inequality), since the number of edges K is missing there and the adjacency matrix A is introduced from nowhere. The alternative optimization in Algorithm 1 and Line 192-205 is not proximal optimization. Proximal gradient is the method that optimizes a continuous surrogate with gradient and projects the solution back to a discrete space. Here you are just alterate the optimization of the GNN model and the continuous mask, which is more like the EM algorithm.\n- W3: The proposed RCL model lacks a clear high-level idea that can educate the community, nor an excellent performance that can make this model an off-the-shelf tool. Given that RCL requires a pretrained GNN model and new hyperparameters, needs a relatively complicated process for optmization, and only achieves slightly better results on real-world datasets, I doubt its signficance to the community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed assessment and valuable suggestions.\n\nR1: The term `Relational' in our title is intended to emphasize our research on integrating inter-node relationships into Curriculum Learning (CL) strategies for GNN models.\n\n`why traditional CL strategies are insufficient is not clarified'\n\nWe have elaborated why traditional CL strategies are insufficient in lines 40-42. Traditional CL strategies can only deal with independent data samples like images, which neglects relationships and structures in dependent data. Please refer to the second point in the global reply for extended comparison experiments with traditional CL methods, providing further empirical evidence.\n\n`...challenges seem to be fabricated for the proposed model, not general to CL methods'\n\nThe challenges are not fabricated solely for the proposed model but indeed are general to CL methods on handling graph edges. \n\n(1) Formulating a progressive, edge-inclusive curriculum is a fundamental challenge for all CL methods. Our ablation studies (refer to Appendix Table 4) reinforce this point by showing that various previous involving functions struggle with performance. The results reveal the importance of an appropriate curriculum on selecting edges. \n\n(2) The drift of optimal GNN parameters, discussed in lines 55-57, is a universal challenge arises from the necessity to modify the number of edges, which is not unique to our method. For example, graph structure learning models.\n\n\nR2: `Eqn. 2 is not a faithful usage of Lagrange multiplier...'\n\nWe acknowledge the need for more clarity regarding the use of the Lagrange multiplier method in Eqn. 2. \nWe note that the inequality $||\\mathbf{S}||_1 \\geq K$ in Eqn. 1 is equivalent to the equality $||\\mathbf{S}||_1 = K$. This is because the second term $\\beta \\sum\\_{i,j} \\mathbf{S}\\_{{ij}} \\mathbf{R}\\_{{ij}}$ in the loss function would always encourage fewer selected edges by the mask matrix $\\mathbf{S}$, as all values in the residual error matrix $\\mathbf{R}$ and mask matrix $\\mathbf{S}$ are nonnegative. This aligns with our motivation discussed on line 163 of the paper, `To filter out the edges with $K$ smallest residual error'.\n\nGiven this, we can incorporate the equality constraint as a Lagrange multiplier and rewrite the loss function as \n\n$\\mathcal{L}= L_{{GNN}} + \\beta \\sum\\_{i,j} \\mathbf{S}\\_{{ij}} \\mathbf{R}\\_{{ij}} - \\lambda (||\\mathbf{S}||_1 - K)$. \n\nAs $K$ is a constant value, minimizing the loss function is equivalent to minimizing the Eqn. 2 in our paper:\n    $\\min\\limits\\_{\\mathbf{w}, \\mathbf{S}}   L\\_{{GNN}} + \\beta \\sum\\_{i,j} \\mathbf{S}\\_{ij} \\mathbf{R}\\_{ij} + \\lambda || \\mathbf{S} - \\mathbf{A} ||,$\n\nwhere $\\mathbf{A}$ is the input adjancency matrix. \n\n\n`...is not proximal optimization.'\n\nWe acknowledge that this is a misusage of terminology. `EM-style alternative optimization' is more appropriate in describing our method.\n\nIt is worth noting that the functionality of our proposed method should remain valid, despite this misuse of terminology. \n\n\nR3. \n1. Our method does not strictly require a pretrained GNN model. Refer to global reply point 4 for details.\n\n2. Our proposed RCL methodology consistently enhances the performance of GNN models across a variety of GNN backbones with statistical soundness p>0.01 in 38 out of 48 tasks.\n\n3. Addressing the high-level idea, the RCL model introduces a novel perspective on handling data dependencies with curriculum learning, which can stimulate further research in both curriculum learning and graph representation learning areas.\n\n\n(Belows are replies to questions)\n\nA1. In the lines 109-110, we described treating data samples as nodes and their dependencies as edges. We then devised a CL strategy that leverages the inherent difficulty level of the edges to enhance the performance of the GNN model.\n\n\nA2. As we discussed in lines 48-50 and 122-124, traditional CL strategies usually use supervised computable metrics (e.g. training loss) to first quantify sample difficulty, and then gradually incorporate edges from easy to hard during the training process. However, quantifying the difficulty level of edges where no supervision is available is challenging, since supervised tasks typically associated with nodes.\n\n\nA3. See reply in R1 above.\n\n\nA4. We elaborated in Section 4.2 (lines 185-191). The regularization term $g(\\mathbf{S};\\lambda) = \\lambda ||\\mathbf{S}-\\mathbf{A}||$ in Eqn. 2 allows control over edge incrementation through parameter $\\lambda$, which increases with the number of training epochs. As $\\lambda$ grows, the term $g(\\mathbf{S};\\lambda)$ push the mask matrix $\\mathbf{S}$ to gradually approach the input adjacency matrix $\\mathbf{A}$, thus progressively involving more edges in training. \n\n\nA5. Yes, it means element-wise multiplication.\n\nA6. Yes, as we mentioned above in response to `W2', only the most $K$ well-expected edges will be selected. \n\nA7. We will add the citation in our later revision.\n\nA8. Yes, it is continuous space in Algorithm 1 Line 6.\n\nA9. We refer to the last term of Algorithm 1 Line 3 and Line 6.\n\nA10. As we illustrated in response A4, the discrepancy penalty between the mask matrix $\\mathbf{S}$ and the input adjacency matrix intensifies as $\\lambda$ increases. This ensures a progressive increase in edge involvement during learning, continuing until the number of selected edges equals the total input edges.\n\nA11. In line 285, we have clarified that we follow the data splits from previous study on these three datasets, which is a commonly used split (adopted by Pytorch-geometric library, refer to 'full' split).\n\nWe commit to correcting all the typographical errors and will include a paragraph discussing the limitations of our work in our subsequent revision.\n\n"}, {"review_id": "HeaMivbUyY", "reviewer": "Reviewer_TBej", "summary": "Summary\nThis work explores continual learning on data that is not independent, but has dependencies, such as graph edges. Three issues are raised when transferring continual learning techniques to learning on graphs: 1. there is no simple way to evaluate how easy/hard an edge is; 2. the curriculum should include a gradual way of involving more edges during training based on model performance; 3. as the GNN will observe different topologies, trainability issues might arise. The solutions consist of 1) using a self-supervised module to select K easiest edges, 2) proposing a new objective using the Lagrangian multiplier and 3) having a smooth transition between structures across iterations by having edge reweighing depend on edge selection occurrences. The continual learning scheme proposed is applied to standard GNNs such as GCN, GIN, GraphSAGE, showing improvements for most of them on synthetic and real-world node classification datasets. \n", "questions": "Please see the weaknesses section.", "limitations": "The authors only briefly mentioned limitations of the proposed approach, I encourage them to include a paragraph discussing them.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I find that the paper is above the acceptance bar in its current form. In particular, the area is of interest to the graph community, the proposed approach is sensible, the writing is clear and all experiments were successful in the sense that the continual modifications to the adjacency improve the final performance over having the same GNN model use the given graph as input. The visualisation of the learnt edge curriculum also provides interesting insights.\n", "weaknesses": "My understanding is that, based on the fact that edges are selected based on similarity in embedding space, the proposed approach might struggle with heterophilic graphs. While I appreciate the synthetic experiments that emphasise the good performance at different levels of homophily, I would encourage the authors to also consider real-world heterophilic datasets, such as those proposed in [1] or [2]. \n\n[1] - Lim, Derek, et al. \"Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods.\" Advances in Neural Information Processing Systems 34 (2021): 20887-20902.\n[2]. - Platonov, Oleg, et al. \"A critical look at the evaluation of GNNs under heterophily: are we really making progress?.\" arXiv preprint arXiv:2302.11640 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your valuable comments and acknowledgement of our work.\n\nQ1. `My understanding is that, based on the fact that edges are selected based on similarity in embedding space, the proposed approach might struggle with heterophilic graphs. While I appreciate the synthetic experiments that emphasise the good performance at different levels of homophily, I would encourage the authors to also consider real-world heterophilic datasets, such as those proposed in [1] or [2].'\n\nA1. Thank you for your suggestion and we have expanded the experiments on six real-world heterophilic datasets. The results are presented in global reply point 1 (see PDF Table 1), which indicate consistent improvements using our method over baseline GNN models on these heterophilic datasets. It is worth noting that the improvements in these datasets are even more significant than the homophily datasets used in our datasets. Specifically, RCL outperforms the second best method on average by 5.04\\%, and 4.55\\%, on GCN and GIN backbones, respectively.\n\nAlthough the inner product decoder we utilized might imply an underlying homophily assumption, our method appears to still benefit from leveraging the edge curriculum present within the input datasets. A reasonable explanation is that standard GNN models are usually struggled with the heterophily edges, while our methodology designs a curriculum allowing more focus on homophily edges, which potentially leads to the observed performance boost.\n\nIn addition, we will include a paragraph to discuss the limitations of our work in future revisions."}, {"review_id": "yhGQQOmecr", "reviewer": "Reviewer_f4A7", "summary": "This study addresses the challenge of varying learning difficulties among edges in a graph and proposes a curriculum learning approach that gradually incorporates more difficult edges. Experimental results on synthetic and real-world datasets demonstrate the effectiveness of the proposed method in improving accuracy and robustness.", "questions": "Could the inconsistent significance of the performance improvement in Table 2 be attributed to the edge selection method's limitations on these datasets? It appears that RCL performs better on large-scale datasets. Is there a specific reason for this observation?", "limitations": "None", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe research addresses an interesting and important problem of learning diverse difficulties among graph edges and understanding graph structures.\n2.\tThe proposed method, which employs a self-supervised approach to measure edge difficulties, is novel. The motivation behind the curriculum learning method is well-founded.\n3.\tSignificant accuracy improvements are observed on synthetic datasets across various settings. Figure 2 provides clear evidence of the method's effectiveness in enhancing robustness against noisy edges.\n", "weaknesses": "1.\tThe improvements on real-world datasets are not substantial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments. \n\nW1. `The improvements on real-world datasets are not substantial.'\n\nA1: We would like to highlight, in line 323-330 and line 331-335, that our model: (1) Tops performance in 26 out of 27 tasks across nine real-world datasets, signifying its effectiveness; (2) Shows consistent improvement over three different GNN backbone models, affirming its generalizability; (3) Produces statistically sound results, outperforming the second-best model in 43 out of 48 tasks with a significance of $p<0.05$, and in 38 out of these 43 cases, with a significance of $p<0.01$.\n\nQ1. `Could the inconsistent significance of the performance improvement in Table 2 be attributed to the edge selection method's limitations on these datasets? It appears that RCL performs better on large-scale datasets. Is there a specific reason for this observation?'\n\nA1. As we mentioned above, our model can consistently improve the performance of backbone GNN by leveraging the designed curriculum. Although there still exists difference on the performance improvements level on different datasets, it is extremely difficult to understand the reason behind it due to the lack of ground truth difficulty level of edges. \n\nHowever, a plausible explanation for the seemingly smaller absolute improvement on certain datasets (such as CS, Physics, and Photo) is that the underlying models for these datasets already yield a notably high prediction accuracy (exceeding 90\\%). Consequently, there is less room for significant improvement.\nIn contrast, for large-scale datasets, the base models tend to exhibit lower performance (around 70\\%), thus providing more opportunities for our model to enhance their performance. \n"}, {"review_id": "31mpK7xiQL", "reviewer": "Reviewer_tVbH", "summary": "The paper presents a curriculum learning strategy that works in the node classification setting. The key property in the node classification setting is that edges are not necessarily independent. The paper proposes a way to perform curriculum learning for this task, including the edges from easy to hard based on the distance of node embeddings (a model is trained on a subset of edges, then the easiest k edges are selected for the next round). The suggested method outperforms a number of GNNs in the area of graph structure learning which try to jointly learn the graph structure (removing noisy edges) and node embeddings. In particular, the suggested method is explicitly robust to random noise.", "questions": "- would it be possible to add experiments based on PNA? (or another modern backbone) \n\n- would it be possible to add the other CL methods in the experiments? Even though they assume some independence which is typically not present?\n\n- can an edge be included in iteration $t$ and not included in iteration $t+1$? Or are edges only added? (making this explicit in the paper would be very helpful to understand the edge selection better)\n\n- How is the number of initial edges determined?\n\n- Why is there no supervised loss on edges? (line 148) In Link prediction, one leaves out some percentage of the edges and tries to correctly predict them. This is clearly supervised. Why is such a scheme not applicable in this setting? (Or rather: its pretty close to the proposed strategy, would it make sense to add it?)\n\n- Does Eq1 in combination with fractional edge weights mean that an edge weight of K is added in each iteration?", "limitations": "none.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- a bottom-up curriculum strategy for node classification\n- fully neuronal, not much of a heuristic (only the way the number of edges to add in the next round is some kind of a heuristic)\n- The improvement in terms of robustness against noise is quite strong\n- General improvement in terms of classification accuracies is nice (although modern and strong GNNs are missing both as comparison and backbone)\n- adding the confidence of individual embeddings into the helps the model focussing on edges that are indeed \"easy\"", "weaknesses": "My major concern about the paper is that the experiments only use very basic algorithms (GCN, GIN, and GraphSAGE) as backbones for the proposed method. While I hope that the results carry over to modern GNNs, it would make sense to actually test that explicitly. My suggestion is to use PNA here as it is still a \"standard\" MPGNN without too fancy additions.\n\nThe second major criticism are the baseline methods used in the experiments. I believe that the task that is to be solved is still \"just\" node classification and thus all kinds of GNNs could serve as baseline, not only those that also try to remove noise. This holds for both the normal experiments as well as the experiment on robustness against noise (there is nothing adversarial about adding random edges). In addition, I believe that existing CL methods are worth comparing to, even if they assume an independence that definitely does not hold - the benefit of RCL should be even more pronounced for that case (and I would like to see that).\n\nFurther unsorted points I noted about the paper:\n* the fairness criterion does not really feel \"fair\" to me - optimizing each method's hyperparameters individually would be preferred\n * it is unclear how the decoder is trained\n * Algorithm 1, Line 6 is very hard to read\n * I did not quite get how the number of edges in $A^0$ is determined\n* It would be nice to note in the introduction that for graph learning (in contrast to node classification) the independence criterion of other CL methods holds. Just for the node classification task it is not applicable.\n* It could be clearer what the difference to existing CL methods for node classification is - those are just mentioned to all perform \"independent\" CL even though targeting node classification\n* 48: in how far is training unsupervised here? As far as I understood the model, the CL process is unsupervised but the overall training still needs supervision.\n* 133: was the numerically stable process really a challenge in practice?\n* To me the ablation study in the appendix was more interesting than Table 1. I believe that table 2 suffices to show the effectiveness of the method.\n* Section 5.3: this is robustness against noise. There is no adversary here that selects the edges. It does not make the experiment less important. Here, an additional baseline using standard (modern) GNNs would be highly appreciated.\n* The \"adjacency\" of classes sounded odd. Are the classes in the synthetic data really ordered and comparable? (i.e. 1 and 10 are further apart than 3 and 4)\n* How strong/important is the given theorem? Is it surprising? Please add one more sentence about it other than that the proof is in the appendix. Is the convergence really that challenging?\n \nWriting:\n* please make sure that all figures are indeed vector graphics\n* related work: please name the authors when using a paper as subject in a sentence\n* The paragraph on initializing (the) graph structure by a pre-trained model exists both in the paper and the appendix.\n* 134ff: this paragraph does not really add a lot of new information, nearly all of that was said before.\n* Tables 1 and 2 should both have a very first column that indicates that the three blocks are the three backbones. (I would rotate the column by 90 degrees then it should still fit)\n* Table 2: maybe exchange (-) by OOM to make clear what the problem was. Also specify that the available GPU memory was 48GB. \n* Eq1: w is undefined and not used.\n* I believe that mentioning the general speed of the method (with a pointer to the table in the appendix) would be benefitial.\n\nTypos:\nquite a number of \"the\" is missing, some appear in the wrong place.\n* 82: are -> is\n* 91: information that carried by the structure in data, thus -> information carried by the structure in the data, and thus\n* Fig1 caption learn -> learns\n* 103: potential -> potentially\n* 112: represents -> represent (adding a second \"let\" would also be nice)\n* 113: denotes there -> denotes that there\n* 114: maps node feature matrix -> maps the node feature matrix\n* 143: with theoretical -> with a theoretical\n* 168 for node -> for the node\n* 178: of K respect to -> of K with respect to\n* Algo1, Input: a stepsize -> stepsize\n* Algo1, Output: parameter w of GNN -> parameters w of the GNN\n* 192ff: please use some tool like grammarly here, I marked 7 places in this paragraph\n* 218: remove \"mostly\" (essentially only graph transformers do not only rely on message passing)\n* 217: training -> intermediate\n* 233: imposed to -> imposed on\n* 248: shift -> differ\n* 253: low confident -> low confidence\n* 336: attck -> attack (but rather exchange the heading to Robustness analysis against structural noise - that would be a much more accurate heading in my opinion)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed comments and insightful suggestions.\n\nmajor 1. We present the results of PNA on synthetic and real-world datasets in global reply point 2 (Table 2 in PDF), which illustrate that our curriculum learning approach consistently improves the performance of PNA backbone by 2.54\\% on average. \n\nmajor 2. \n\nNew experiments. We used both GCN and PNA as backbone models for additional baselines, denoted by suffixes -linear' and -root'. The results are shown in global reply point 2 (Table 2 in PDF). The results consistently highlight that our proposed approach surpasses these conventional CL techniques across all datasets. Besides, it is also worth noting that these traditional CL methods can still enhance performance in most datasets (synthetic, Computers, and ogbn-arxiv), espcially with the Root pacing function.\n\nChoice of baselines. It is critical to note that our choice of baseline models is primarily guided by the attributes of our proposed CL strategy.\n\nFirst, our contribution is not a specific GNN model, but a general curriculum learning strategy that can improve the performance and robustness of all GNN models that follow a message passing mechanism. Our experimental results substantiate this claim, demonstrating that our CL strategy consistently improves performance across various GNN backbone models.\n\nSecond, a unique aspect of our CL strategy is its dynamic alteration of the number of edges, placing it related to the domain of graph structure learning. Accordingly, we compared our method with four state-of-the-art graph structure learning methods. \n\n\n\n\np1. We use validation set or cross-validation for fair comparison over all expriments. We require all models to follow the same key model architecture hyperparameters such as the number of graph convolution layers. We require all models to follow the same hyperparameter search space, which is indiciated in our Appendix lines 562-568.\n\n\np2. As indicated in lines 171-172, our framework utilizes a non-parametric kernel function, e.g. the inner product kernel, as the decoder component. This ensures that there is no need for additional parameter training.\n\n\np3. Algorithm 1, Line 6 describes the optimization step on the mask matrix $\\mathbf{S}$, which results in more edges are gradually involved.\n\n\n\np4. As described in line 297-305, we used a pretrained vanilla GNN model to help initialize the edges. Specifically, we use the pretrained model to extract the latent embeddings and our optimization model subsequently selects the `easiest' edges to form the initial edge set. The number of these selected edges is determined by our optimization model and parameter $\\lambda$.\n\n\np5. While we discussed the scenarios that motivated our method, to extend curriculum learning to handle data dependencies, we will ensure that we provide more clarity in the later revisions.\n\n\np6. As we introduced in lines 87-93, existing CL methods for node classification generally treat nodes as independent samples during the learning process, thus can not well handle the correlation between data samples. These methods typically use heuristic metrics such as the node degree or loss as the indicator for designing the curriculum, which does not adequately address the dependencies between nodes.\n\np7. The primary goal of our model remains supervised learning for the node classification task. The term `unsupervised' pertains to the curriculum designing process on the edges. Given that there are no readily computable supervised metrics on edges, we employ self-supervised task for the formulation of the curriculum on the edges.\n\n\np8. Yes. In ablation studies Appendix Table 4 we have compared our full method with the version without smoothing technique, which can demonstrate the effectiveness of our smoothing techniques. \n\nSpecifically, without edge smoothing, the training loss spiked when the number of edges discretely changed, which was caused by shifts in the optimal GNN parameters.\n\np9. The lack of groundtruth difficulty levels for edges in real-world datasets motivated us to conducting extensive experiments on synthetic datasets, as represented in Table 1. Therefore, we constructed synthetic datasets with known ground-truth difficulty values. This design enables us to verify the capabilities of designed curriculum.\n\n\np10. We present further robustness test against noise using PNA model in global reply point 3 (Table 3 in PDF).\nThe results reveal that our curriculum learning approach remains robust against edge noise with the advanced PNA model as the backbone. Besides, we will change the title of this section into `Robustness analysis against topological noise' to better describe the experiments.\n\np11. The classes in synthetic data are arranged in a circular order, which is visualized in Appendix Figure 4. This implies that classes 1 and 10 are equally separated with 3 and 4.\n\np12. The theorem is important as it offers a robust theoretical basis for our approach's ability to handle the optimization challenges. As we mentioned above in p8, the discretely change of edges will result in the the spike of training loss, which is challenging for stable of the optimization process.\n\nq1. See major 1.\n\nq2. See major 2.\n\nq3. Is is very unlikely but possible an edge be included in iteration $t$ and not included in iteration $t+1$, which also verified the importance of adopting edge smoothing technique in ensuring the training stability.\n\nq4. See p4.\n\nq5. Our method operates in this manner, and we term it a self-supervised task, as the supervised learning focuses on node classification.\n\nq6. Our method can automatically determine the number of edges to be involved in each iteration, and it does not has to be a fixed constant. "}, {"review_id": "Yl4Y2CJsLc", "reviewer": "Reviewer_4bWL", "summary": "This paper proposes a novel curriculum learning method that progressively includes edges into training based on their difficulty level, starting from easy to hard. The difficulty level is determined by the expected model performance in predicting the edges.", "questions": "Please address the aforementioned weakness.", "limitations": "No specific concern.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) Graph representation learning is a very fundamental problem for graph-related problems, and designing curriculum learning strategy from edge perspective is a very interesting topic.\n\n(2) The paper is well-organized and easy to be understood.\n\n(3) Extensive experiments analysis is informative for the readers.", "weaknesses": "(1) Since the initial node embedding heavily relies on the quality of the encoder and the effectiveness of reconstruction loss, it is advantageous to initialize the training process using a pre-trained GNN encoder. Since the evaluation of edge difficulty in the paper is based on the difference between the reconstruction matrix and the ground-truth matrix, which leads to significant shift in the early stages of training from scratch. It is highly recommended to incorporate a pre-trained GNN encoder as an initialization step, which would be more reasonable.\n\n(2) Since the main training strategy in the paper is curriculum learning, it is suggested to compare the impact of different pace functions on performance.\n\n(3) As existing research suggests that curriculum learning is effective for noisy data, it would be valuable to validate the proposed method's effectiveness on different types and proportions of label rates.\n\n(4) The paper lacks some recent literature on the latest advancements for graph neural networks or curriculum learning.\n1. Curriculum Graph Machine Learning: A Survey. 2023\n2. A Comprehensive Survey on Deep Graph Representation Learning. 2023\n3. Graph Neural Network with Curriculum Learning for Imbalanced Node Classification. 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments.\n\nQ1. 'Since the initial node embedding heavily relies on the quality of the encoder and the effectiveness of reconstruction loss, it is advantageous to initialize the training process using a pre-trained GNN encoder...'\n\nA1. Your suggestion aligns with the approach we have implemented in our experiments. As described in lines 297-305, a section titled 'Initializing graph structure by a pre-trained model' details our use of a pre-trained GNN to initialize edge difficulty measurement.\n\nAdditionally, our ablation studies in Appendix Table 4 showed the performance difference when no pre-trained GNN model is employed. The results validate the beneficial impact of a pre-trained GNN on improving model performance by providing initial structure.\n\nQ2. 'Since the main training strategy in the paper is curriculum learning, it is suggested to compare the impact of different pace functions on performance.'\n\nA2. We indeed compared the impact of different pace functions on performance. In Appendix Table 4, we contrast our method with two commonly utilized pacing functions—linear and root. The results demonstrate that our designed pacing function can outperform these two competitive alternatives.\n\nQ3. 'As existing research suggests that curriculum learning is effective for noisy data, it would be valuable to validate the proposed method's effectiveness on different types and proportions of label rates.'\n\nA3. In Section 5.3 (refer to Figure 2), we conducted robustness tests against noisy edges, reflecting our primary focus on designing an appropriate curriculum on edges. \n\nWe introduced noise into the graph by randomly incorporating noisy edges, ranging from 10\\% to 100\\% of the original edges. The findings reveal that our RCL model effectively alleviates the performance drop, reducing it by over 50\\%. This demonstrates the robustness of our proposed curriculum learning technique when dealing with noisy scenarios.\n\n\nQ4. 'The paper lacks some recent literature on the latest advancements for graph neural networks or curriculum learning.'\n\nA4. We will include the recently related literature in our later revision."}]

Author rebuttal:
We sincerely thank all the reviewers for your efforts in providing critiques and suggestions to our work. We summarize the newly expanded experiments and frequent questions as below:

1. We have included new experiments on six real-world heterophilic datasets. As shown in PDF Table 1, our method consistently improve performance of backbone GNN models on these heterophilic datasets. Secifically, RCL outperforms the backbone GNN on average by 5.04\%, and 4.55\%, on GCN and GIN backbones, respectively. The results can demonstrate our method is not limited to homophily graphs.

2. In PDF Table 2, new experiments that adopt modern GNN architecture - PNA model [1] have been added. From the table we can observe that our proposed method improves the performance of PNA backbone by 2.54\% on average, which further verified the effectiveness of our method under different choices of backbone GNN model.

In addition, in Table 2 we further include two traditional CL methods for independent data as additional baselines, following classical works [2,3]. We employed the supervised training loss of a pretrained GNN model as the difficulty metric, and selected two well-established pacing functions for curriculum design: linear and root pacing, defined as follows:

$$\mathrm{Linear\colon } K_{\mathrm{linear}}(t) = \frac{t}{T}|V|;$$
$$\mathrm{Root\colon } K_{\mathrm{root}}(t) = \sqrt{\frac{t}{T}}|V|,$$
where $t$ is the number of current iterations and $T$ is the number of total iterations, and $|V|$ is the number of nodes. 

We utilized GCN and PNA as backbone architectures, identified by the suffixes '-linear' and '-root'. Across all datasets, the results consistently demonstrate that our proposed method outperforms traditional CL approaches.

[1] Corso, Gabriele, et al. "Principal neighbourhood aggregation for graph nets." Advances in Neural Information Processing Systems 33 (2020): 13260-13271.

[2] Bengio, Yoshua, et al. "Curriculum learning." Proceedings of the 26th annual international conference on machine learning. 2009.

[3] Kumar, M., Benjamin Packer, and Daphne Koller. "Self-paced learning for latent variable models." Advances in neural information processing systems 23 (2010).


3. We present further robustness test against random noisy edges by using the PNA backbone model. The results are shown in PDF Table 3, which further proves that our curriculum learning approach improves the robustness against edge noise with the advanced PNA model as the backbone.

4. We would like to clarify that while utilizing a pre-trained GNN model can help initialize the edges set, because its capacity to provide meaningful node embeddings to guide designing curriculum. However, the pre-trained model is not a necessity by our method. Our technique can operate effectively without such a setting. Our ablation studies in Appendix Table 4 can confirm that even without the pre-trained model to initialize, the method can still establish meaningful curriculum for numerous datasets.




Meta-review: This work makes a novel contribution to curriculum learning design, in a way that incrementally processes edges fed into a graph machine learning system. The idea is highly interesting and likely to be industrially impactful.

That being said, I find that there are definitely things that the authors could have executed better about this work and the rebuttal; for example, the clarity of work was somewhat lacking, and the heterophilic benchmarks chosen should have followed the advice of Reviewer TBej to make them more trustworthy. I really hope that the authors will find some time to follow this advice when revising their paper one more time. Further, concerns were raised about the significance of the provided experimental results.

In spite of the questionable improvements on certain datasets, one must however acknowledge the sheer scale of the experimentation the authors have done, and I also find that the paper has made a good chunk of convincing results. Further, while maybe the paper in its submitted form is not sufficient for NeurIPS acceptance, given the results provided during the rebuttal and the changes the authors promise to make, I do see a relatively minor amount of effort necessary to push it over the bar.

As such, I will recommend acceptance of the paper.
Decision: Accept (poster)