Curriculum Learning for Graph Neural Networks: Which Edges Should We
  Learn First
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.
Zheng Zhang, Junxiang Wang, Liang Zhao
# Curriculum Learning for Graph Neural Networks: Which Edges Should We Learn First

###### 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](https://github.com/rollingstonezz/Curriculum_learning_for_GNNs).

## 1 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-to-hard learning strategy can effectively improve the generalization ability of the model [2; 19; 15; 11; 35; 46], and some studies [19; 15; 11] have shown that CL strategies can also increase the robustness of the learned model against noisy training samples. An intuitive explanation is that in 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 on one sample impacts that of another, forming a graph structure that encompasses all samples connected by their dependencies. There are
many machine learning techniques for such graph-structured data, ranging from traditional models like conditional random field [36], graph kernels [37], to modern deep models like GNNs [29; 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-structured 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 robustness 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 a 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 **R**elational **C**urriculum **L**earning (**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 learning manner. Specifically, for each training iteration, we choose \(K\) easiest edges whose corresponding relations are most well-expected by the current model. Second, to design an 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 an alternative optimization algorithm with a theoretical convergence guarantee and an edge reweighting scheme to smooth the graph structure transition. Finally, we demonstrate the superior performance of RCL compared to state-of-the-art comparison methods through extensive experiments on both synthetic and real-world datasets.

## 2 Related Works

Curriculum Learning (CL).Bengio et al.[2] 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 [25] 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 according to its own training status. Following works [18; 17; 55] 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. [11] provided theoretical explanations on the denoising mechanism that CL learners waste less time 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 as [44; 5; 45; 28], simply treat
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 [5; 45; 28], which largely limit the generalizability of these methods.

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 [7; 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. Existing works [9; 4; 20; 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 [7; 56; 9] to preprocess graph structure such as singular value decomposition (SVD), or dynamically remove "redundant" edges according to the downstream task performance on 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 in which data samples are correlated with each other. Typically, the data samples are treated as nodes while their dependencies are treated as edges in the constructed graph. Formally, we denote a graph as \(G=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}=\{v_{1},v_{2},\ldots,v_{N}\}\) is a set of nodes that \(N=|\mathcal{V}|\) denotes the number of nodes in the graph and \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\) is the set of edges. We also let \(\mathbf{X}\in\mathbb{R}^{N\times b}\) denote the node attribute matrix and let \(\mathbf{A}\in\mathbb{R}^{N\times N}\) represent the adjacency matrix. Specifically, \(A_{ij}=1\) denotes that there is an edge connecting nodes \(v_{i}\) and \(v_{j}\in\mathcal{V}\), otherwise \(A_{ij}=0\). A GNN model \(f\) maps the node feature matrix \(\mathbf{X}\) associated with the adjacency matrix \(\mathbf{A}\) to the model predictions \(\hat{\mathbf{y}}=f(\mathbf{X},\mathbf{A})\), and get the loss \(L_{\mathrm{GNN}}=L(\hat{\mathbf{y}},\mathbf{y})\), where \(L\) is the objective function and \(\mathbf{y}\) is the ground-truth label of nodes. The loss on one node \(v_{i}\) is denoted as \(l_{i}=L(\hat{y_{i}},y_{i})\).

## 4 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 is extremely difficult due to several unique challenges: (1) Difficulty in designing a feasible principle to select

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 \(\mathbf{y}\) and reconstructs the input structure by a 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.
edges by properly quantifying their difficulties. (2) Difficulty in designing an appropriate pace of curriculum to gradually involve more edges in training based on model status. (3) Difficulty in ensuring convergence and a numerical steady process for optimizing the CL model.

In order to address the above challenges, we propose a novel CL method named **R**elational **C**urriculum **L**earning (**RCL**). The sequence, which gradually includes edges from easy to hard, is called _curriculum_ and learned in different grown-up stages of training. In order to address the first challenge, we propose a self-supervised module _Incremental Edge Selection (IES)_, which is shown in Figure 1(a), 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 a joint optimization framework to automatically increase the number of selected edges \(K\) given its own training status. The framework is elaborated in Figure 1(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 a theoretical convergence guarantee in Section 4.2 Algorithm 1 and an edge reweighting scheme to smooth the discrete edge incrementing process in Section 4.3.

### Incremental Edge Selection by Quantifying Difficulties of Sample Dependencies

Here we propose a novel way to 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 a 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 1(a), given the currently selected edges at 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 \(\mathbf{R}\), which is defined as the degree of mismatch between the original adjacency matrix \(\mathbf{A}\) and the reconstructed adjacency matrix \(\tilde{\mathbf{A}}^{(t)}\), can be considered a strong indicator for describing how well the edges are expected by the current model. Specifically, a smaller residual error indicates a higher probability of being a well-expected edge.

With the developed self-supervised 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 \(\mathbf{A}^{(t)}\) that will be fed into the GNN model \(f^{(t)}\), we introduce a learnable binary mask matrix \(\mathbf{S}\) with each element \(\mathbf{S}_{ij}\in\{0,1\}\). Thus, the training adjacency matrix at iteration \(t\) can be represented as \(\mathbf{A}^{(t)}=\mathbf{S}^{(t)}\odot\mathbf{A}\). To filter out the edges with \(K\) smallest residual error, we penalize the summarized residual errors over the selected edges, which can be represented as \(\sum_{i,j}\mathbf{S}_{ij}\mathbf{R}_{ij}\). Therefore, the learning objective can be presented as follows:

\[\begin{split}&\underset{\mathbf{w}}{\min}L_{\mathrm{GNN}}+\beta \sum_{i,j}\mathbf{S}_{ij}\mathbf{R}_{ij},\\ & s.t.\left\|\mathbf{S}\right\|_{1}\geq K,\end{split} \tag{1}\]

where the first term \(L_{\mathrm{GNN}}=L(f(\mathbf{X},\mathbf{A}^{(t)};\mathbf{w}),\mathbf{y})\) is the node-level predictive loss, e.g. cross-entropy loss for the node classification task. The second term \(\sum_{i,j}\mathbf{S}_{ij}\mathbf{R}_{ij}\) aims at penalizing the residual errors over the edges selected by the mask matrix \(\mathbf{S}\). \(\beta\) is a hyperparameter to tune the balance between terms. The constraint is to guarantee only the most \(K\) well-expected edges are selected.

More concretely, the value of a residual edge \(\tilde{\mathbf{A}}^{(t)}_{ij}\in[0,1]\) can be computed by a non-parametric kernel function \(\kappa(\mathbf{z}^{(t)}_{i},\mathbf{z}^{(t)}_{j})\), e.g. the inner product kernel. Then the residual error \(\mathbf{R}_{ij}\) between the input structure and the reconstructed structure can be defined as \(\left\|\tilde{\mathbf{A}}^{(t)}_{ij}-\mathbf{A}_{ij}\right\|\), where \(\left\|\cdot\right\|\) is commonly chosen to be the squared \(\ell_{2}\)-norm.

### 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 1 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
Equation 1 is difficult since \(\mathbf{S}\) is a binary matrix where each element \(\mathbf{S}_{ij}\in\{0,1\}\), optimizing \(\mathbf{S}\) would require solving a discrete constraint program at each iteration. To address this issue, we first relax the problem into continuous optimization so that each \(\mathbf{S}_{ij}\) can be allowed to take any value in the interval \([0,1]\). 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 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. Given this, we can incorporate the equality constraint as a Lagrange multiplier and rewrite the loss function as \(\mathcal{L}=L_{GNN}+\beta\sum_{i,j}\mathbf{S}_{ij}\mathbf{R}_{ij}-\lambda(|| \mathbf{S}||_{1}-K)\). Considering that \(K\) remains constant, the optimization of the loss function can be equivalently framed by substituting the given constraint with a regularization term denoted as \(g(\mathbf{S};\lambda)\). As such, the overall loss function can be reformulated as:

\[\min_{\mathbf{w},\mathbf{S}}L_{\mathrm{GNN}}+\beta\sum_{i,j}\mathbf{S}_{ij} \mathbf{R}_{ij}+g(\mathbf{S};\lambda), \tag{2}\]

where \(g(\mathbf{S};\lambda)=\lambda\left\|\mathbf{S}-\mathbf{A}\right\|\) and \(\left\|\cdot\right\|\) is commonly chosen to be the squared \(\ell_{2}\)-norm. Since the training adjacency matrix \(\mathbf{A}^{(t)}=\mathbf{S}^{(t)}\odot\mathbf{A}\), as \(\lambda\rightarrow\infty\), more edges in the input structure are included until the training adjacency matrix \(\mathbf{A}^{(t)}\) converges to the input adjacency matrix \(\mathbf{A}\). Specifically, the regularization term \(g(\mathbf{S};\lambda)\) controls the learning scheme by the _age parameter_\(\lambda\), where \(\lambda=\lambda(t)\) grows with the number of iterations. By monotonously increasing the value of \(\lambda\), the regularization term \(g(\mathbf{S};\lambda)\) will push the mask matrix gradually converge to the input adjacency matrix \(\mathbf{A}\), resulting in more edges automatically involved in the training structure.

**Optimization of learning objective.** In optimizing the objective function in Equation 2, we need to jointly optimize parameter \(\mathbf{w}\) for GNN model \(f\) and the mask matrix \(\mathbf{S}\). To tackle this, we introduce an EM-style optimization scheme (detailed in Algorithm 1) that iteratively updates both. The algorithm uses the node feature matrix \(\mathbf{X}\), the original adjacency matrix \(\mathbf{A}\), a step size \(\mu\) to control the age parameter \(\lambda\) increase rate, and a hyperparameter \(\gamma\) for regularization adjustments. Post initialization of \(\mathbf{w}\) and \(\mathbf{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 \(\lambda\) when the training matrix \(\mathbf{A}^{(t)}\) differs from input matrix \(\mathbf{A}\), incorporating more edges in the next iteration.

**Theorem 4.1**.: _We have the following convergence guarantees for Algorithm 1: \(\bullet\) Avoidance of Saddle Points. If the second derivatives of \(L(f(\mathbf{X},\mathbf{A}^{(t)};\mathbf{w}),\mathbf{y})\) and \(g(\mathbf{S};\lambda)\) are continuous, then for sufficiently large \(\gamma\), any bounded sequence \((\mathbf{w}^{(t)},\mathbf{S}^{(t)})\) generated by Algorithm 1 with random initializations will not converge to a strict saddle point of \(F\) almost surely. \(\bullet\) Second Order Convergence. If the second derivatives of \(L(f(\mathbf{X},\mathbf{A}^{(t)};\mathbf{w}),\mathbf{y})\) and \(g(\mathbf{S};\lambda)\) are continuous, and \(L(f(\mathbf{X},\mathbf{A}^{(t)};\mathbf{w}),\mathbf{y})\) and \(g(\mathbf{S};\lambda)\) satisfy the Kurdyka-Lojasiewicz (KL) property [41], then for sufficiently large \(\gamma\), any bounded sequence \((\mathbf{w}^{(t)},\mathbf{S}^{(t)})\) generated by Algorithm 1 with random initialization will almost surely converge to a second-order stationary point of \(F\)._

The detailed proof can be found in Appendix B.
### Smooth Structure Transition by Edge Reweighting

Note that in the Algorithm 1, the optimization process requires iteratively updating the parameters \(\mathbf{w}\) of the GNN model \(f\) and current adjacency matrix \(\mathbf{A}^{(t)}\), where \(\mathbf{A}^{(t)}\) varies discretely between iterations. However, GNN models mostly work in a message-passing 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 a novel edge reweighting scheme to (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 \(\bar{\mathbf{A}}^{(t)}\) to substitute \(\mathbf{A}^{(t)}\) for training the GNN model \(f\) in step 3 of Algorithm 1, where the mapping from \(\mathbf{A}^{(t)}\) to \(\bar{\mathbf{A}}^{(t)}\) can be represented as:

\[\bar{\mathbf{A}}^{(t)}_{ij}=\pi^{(t)}_{ij}\mathbf{A}^{(t)}_{ij}, \tag{3}\]

where \(\pi^{(t)}_{ij}\) is the weight imposed on edge \(e_{ij}\) at iteration \(t\). \(\pi^{(t)}_{ij}\) is calculated by considering the counted occurrences of edge \(e_{ij}\) until the iteration \(t\) and the confidence of the latent embedding for the connected pair of nodes \(v_{i}\) and \(v_{j}\):

\[\pi^{(t)}_{ij}=\psi(e_{ij})\rho(v_{i})\rho(v_{j}), \tag{4}\]

where \(\psi\) is a function that reflects the number of edge occurrences and \(\rho\) 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 to obtain a smooth transition of the training structure between iterations, we take the learned curriculum of selected edges into consideration. Formally, we model \(\psi\) by a smooth function of the edge selected occurrences compared to the model iteration occurrences before the current iteration:

\[\psi(e_{ij})=t(e_{ij})/t, \tag{5}\]

where \(t\) is the number of current iterations and \(t(e_{ij})\) represents the counting number of selecting edge \(e_{ij}\). 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 \(\tilde{A}\) is inferred from the latent embedding \(\mathbf{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 \(\rho\) 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, a larger training loss indicates a low confident latent node embedding. Mathematically, the weights \(\rho(v_{i})\) on node \(v_{i}\) can be represented as a distribution of their training loss:

\[\rho(v_{i})\sim e^{-l_{i}} \tag{6}\]

where \(l_{i}\) is the training loss on node \(v_{i}\). Therefore, a node with a larger training loss will result in a smaller value of \(\rho(v_{i})\), 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.
We verify the effectiveness of framework components through ablation studies in Section 5.4. Intuitive visualizations of the edge selection curriculum are shown in Section 5.5. In addition, we measure the the parameter sensitivity in Appendix A.2 and running time analysis in Appendix A.5 due to the space limit.

### 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; 1] to generate a set of synthetic datasets, where the formation probability of an edge is designed to reflect its likelihood to positively contribute to 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 \(1,2,\ldots,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 a higher chance to positively contribute to the node classification task because it 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.1.

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 [51] and ogbn-arxiv [16], two coauthor network datasets CS and Physics [34], 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 [10] and Open Graph Benchmark (OGB) [16], where basic statistics are reported in Table 2.

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-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.

\begin{table}
\begin{tabular}{c|c c c c c c c c c} \hline \hline Home ratio & **0.1** & **0.2** & **0.3** & **0.4** & **0.5** & **0.6** & **0.7** & **0.8** & **0.9** \\ \hline GCN & 50.84\(\pm\)1.03 & 56.50\(\pm\)0.50 & 65.17\(\pm\)0.48 & 77.94\(\pm\)0.54 & 87.15\(\pm\)0.44 & 93.27\(\pm\)0.24 & 97.48\(\pm\)0.25 & 99.10\(\pm\)0.17 & 92.93\(\pm\)0.03 \\ GNNSVD & 54.96\(\pm\)0.76 & 58.54\(\pm\)0.56 & 63.06\(\pm\)0.63 & 70.23\(\pm\)0.61 & 80.51\(\pm\)0.51 & 85.02\(\pm\)0.46 & 90.31\(\pm\)0.27 & 94.23\(\pm\)0.22 & 96.74\(\pm\)0.23 \\ PngGNN & 47.87\(\pm\)0.87 & 54.59\(\pm\)0.55 & 63.94\(\pm\)0.44 & 79.66\(\pm\)0.49 & 87.67\(\pm\)0.51 & 93.16\(\pm\)0.34 & 97.06\(\pm\)0.31 & 99.01\(\pm\)0.19 & **99.94\(\pm\)0.03** \\ NeuralSparse & 51.42\(\pm\)1.35 & 57.99\(\pm\)0.69 & 65.10\(\pm\)0.43 & 75.73\(\pm\)0.34 & 87.40\(\pm\)0.29 & 93.54\(\pm\)0.28 & 97.16\(\pm\)0.15 & 99.01\(\pm\)0.22 & 98.93\(\pm\)0.07 \\ PTDNet & 48.21\(\pm\)1.98 & 55.52\(\pm\)0.82 & 65.04\(\pm\)0.94 & 79.37\(\pm\)0.45 & 87.10\(\pm\)0.39 & 94.19\(\pm\)0.18 & 98.61\(\pm\)0.12 & 99.51\(\pm\)0.09 & 98.91\(\pm\)0.05 \\ CLNodes & 50.37\(\pm\)0.73 & 56.64\(\pm\)0.56 & 65.04\(\pm\)0.66 & 77.52\(\pm\)0.48 & 86.85\(\pm\)0.44 & 93.10\(\pm\)0.47 & 97.34\(\pm\)0.25 & 99.02\(\pm\)0.18 & 99.88\(\pm\)0.04 \\ RCL & **57.57\(\pm\)0.43** & **62.06\(\pm\)0.28** & **73.98\(\pm\)0.58** & **84.45\(\pm\)0.75** & **92.69\(\pm\)0.09** & **97.42\(\pm\)0.17** & **96.92\(\pm\)0.05** & **99.98\(\pm\)0.02** & 99.93\(\pm\)0.06 \\ \hline GIN & **48.33\(\pm\)1.39** & 53.35\(\pm\)0.19 & 54.09\(\pm\)0.19 & 75.75\(\pm\)1.10 & 83.51\(\pm\)0.19 & 90.57\(\pm\)0.36 & 97.32\(\pm\)0.18 & 99.95\(\pm\)0.10 & 99.91\(\pm\)0.02 \\ GNNSVD & 43.21\(\pm\)1.60 & 45.68\(\pm\)1.66 & 54.90\(\pm\)1.68 & 62.89\(\pm\)0.79 & 79.76\(\pm\)0.52 & 85.63\(\pm\)0.44 & 93.65\(\pm\)0.39 & 97.24\(\pm\)0.17 & 98.94\(\pm\)0.17 \\ PngGNN & 45.76\(\pm\)1.64 & 29.50\(\pm\)1.67 & 14.07\(\pm\)0.76 & 79.65\(\pm\)0.43 & 87.83\(\pm\)0.17 & 89.96\(\pm\)0.55 & 98.40\(\pm\)0.48 & 95.10\(\pm\)0.12 & 99.78\(\pm\)0.05 \\ NeuralSparse & 50.23\(\pm\)2.05 & 54.12\(\pm\)1.52 & 62.81\(\pm\)0.75 & 76.98\(\pm\)1.17 & 85.14\(\pm\)0.94 & 92.57\(\pm\)0.44 & 98.02\(\pm\)0.20 & 99.61\(\pm\)0.12 & 99.91\(\pm\)0.05 \\ PTDNet & 53.23\(\pm\)2.76 & 56.12\(\pm\)2.03 & 65.81\(\pm\)1.38 & 77.81\(\pm\)1.02 & 86.14\(\pm\)0.45 & 93.21\(\pm\)0.74 & 97.08\(\pm\)0.41 & 97.51\(\pm\)0.18 & **99.91\(\pm\)0.03** \\ CLNodes & 43.56\(\pm\)1.42 & 51.10\(\pm\)1.15 & 62.38\(\pm\)0.78 & 75.83\(\pm\)1.07 & 87.66\(\pm\)0.90 & 94.25\(\pm\)0.44 & 98.06\(\pm\)0.26 & **99.06\(\pm\)0.09** & **99.92\(\pm\)0.03** \\ RCL & **57.63\(\pm\)0.66** & **62.08\(\pm\)1.17** & **71.02\(\pm\)0.61** & **86.01\(\pm\)0.69** & **88.62\(\pm\)0.43** & **94.88\(\pm\)0.36** & 98.19\(\pm\)0.19 & 99.92\(\pm\)0.08 & 99.99\(\pm\)0.04 \\ \hline GraphSAGE & 62.57\(\pm\)0.55 & 63.73\(\pm\)0.43 & 76.17\(\pm\)0.44 & 78.08\(\pm\)0.54 & 75.88\(\pm\)0.51 & 91.42\(\pm\)0.37 & 95.26\(\pm\)0.33 & 97.78\(\pm\)0.16 & 95.20\(\pm\)0.13 \\ GNNSVD & 64.42\(\pm\)0.20 & 66.71\(\pm\)0.39 & 67.12\(\pm\)0.58 & 68.87\(\pm\)0.50 & 77.70\(\pm\)0.65 & 82.86\(\pm\)0.50 & 87.81\(\pm\)0.71 & 91.61\(\pm\)0.55 & 95.01\(\pm\)0.50 \\ PngGNN
Initializing graph structure by a pre-trained model.It is worth noting that the model needs an initial training graph structure \(\mathbf{A}^{(0)}\) in the initial stage of training. An intuitive way is that we can initialize the model to work in a 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 \(\mathbf{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 1 to obtain the initial training structure \(\mathbf{A}^{(0)}\) but the latent node embedding is extracted from the pre-trained model \(f^{*}\).

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 in particular data splits. Test results are according to the best validation results. General training hyperparameters (such as learning rate or the number of training epochs) are equal for all models.

### 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 or most competitive performance to all the comparison methods over three backbone GNN architectures. Specifically, RCL outperforms the second best method on average by 4.17%, 2.60%, and 1.06% on GCN, GIN, and GraphSAGE backbones, respectively. More importantly, the proposed RCL method performs significantly better than the second best model when the _homo_ of generated graphs is low (\(\leq 0.5\)), on average by 6.55% on GCN, 4.17% on GIN, and 2.93% on GraphSAGE backbones. These demonstrate that our proposed RCL method significantly improves the model'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 baseline models on average by 1.86%, 2.83%, and 1.62% over GCN, GIN, and GraphSAGE, 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 a significance \(p<0.001\), in 8 out of 43 cases with a significance \(p<0.01\), and in 5

\begin{table}
\begin{tabular}{c|c c c c c c c c c} \hline \hline  & **Cara** & **Citeseer** & **Pubmed** & **CS** & **Pivages** & **Photo** & **Computers** & **aph-arxiv** & **gbng-petrains** \\ \hline \# nodes & 2,708 & 3,327 & 19,717 & 18,333 & 34,933 & 7,650 & 13,752 & 169,343 & 132,534 \\ \# edges & 10,556 & 9,104 & 88,648 & 16,3788 & 405,924 & 238,162 & 49,722 & 1,166,423 & 39,561,525 \\ \# features & 1,433 & 3,703 & 500 & 6,805 & 8,415 & 745 & 767 & 100 & 8 \\ \hline GCN & 85.741\(\pm\)0.42 & 78.93\(\pm\)0.32 & 87.91\(\pm\)0.09 & 93.03\(\pm\)0.32 & 96.55\(\pm\)0.15 & 93.25\(\pm\)0.70 & 88.99\(\pm\)0.40 & 71.74\(\pm\)0.29 & 72.51\(\pm\)0.35 \\ GNNSP & 83.24\(\pm\)10.3 & 78.40\(\pm\)0.87 & 88.81\(\pm\)0.38 & 93.79\(\pm\)0.11 & 96.11\(\pm\)0.13 & 96.83\(\pm\)0.73 & 86.49\(\pm\)0.77 & 67.44\(\pm\)0.51 & 66.92\(\pm\)0.64 \\ PnGNN & 85.66\(\pm\)0.10 & 74.78\(\pm\)0.55 & 87.22\(\pm\)0.33 & 94.04\(\pm\)0.19 & 95.55\(\pm\)0.26 & 92.07\(\pm\)0.67 & 87.22\(\pm\)0.59 & (OOM) & (OM) \\ NeuralSParse & 85.95\(\pm\)0.86 & 74.24\(\pm\)0.48 & 86.33\(\pm\)0.40 & 93.21\(\pm\)0.47 & 95.66\(\pm\)0.30 & 90.57\(\pm\)0.89 & 86.22\(\pm\)0.83 & (OOM) & (OM) \\ PIDNet & 83.84\(\pm\)0.95 & 75.44\(\pm\)0.42 & 88.79\(\pm\)0.08 & 93.04\(\pm\)0.43 & 95.60\(\pm\)0.89 & 89.82\(\pm\)0.87 & 87.52\(\pm\)0.70 & (OMOM) & (OMOM) \\ CLNode & 85.67\(\pm\)0.33 & 78.90\(\pm\)0.57 & 89.50\(\pm\)0.28 & 93.83\(\pm\)0.24 & 95.76\(\pm\)0.16 & 93.19\(\pm\)0.83 & 89.28\(\pm\)0.38 & 70.95\(\pm\)0.18 & 71.40\(\pm\)0.32 \\ RCL & **87.15\(\pm\)0.35** & **74.97\(\pm\)0.35** & **89.97\(\pm\)0.12** & **94.66\(\pm\)0.30** & **97.02\(\pm\)0.33** & **97.02\(\pm\)0.32** & **73.04\(\pm\)0.33** & **73.05\(\pm\)0.36** & **73.19\(\pm\)0.36** \\ \hline GIN & 84.43\(\pm\)0.65 & 74.87\(\pm\)0.87 & 85.72\(\pm\)0.20 & 91.48\(\pm\)0.36 & 95.62\(\pm\)0.30 & 93.02\(\pm\)0.91 & 89.94\(\pm\)1.38 & 69.26\(\pm\)0.34 & 74.51\(\pm\)0.32 \\ GNNSP & 82.23\(\pm\)0.65 & 72.11\(\pm\)0.70 & 83.81\(\pm\)0.15 & 91.40\(\pm\)0.87 & 95.30\(\pm\)0.29 & 94.91\(\pm\)1.11 & 86.26\(\pm\)0.26 & 67.79\(\pm\)0.41 & 76.65\(\pm\)0.43 \\ PnGNN & 85.02\(\pm\)0.61 & **78.12\(\pm\)0.82** & 87.73\(\pm\)0.51 & 97.82\(\pm\)0.51 & (OOM) & (OM) & 92.23\(\pm\)0.67 & 85.41\(\pm\)0.48 & (OMOM) & (OM) \\ NeuralSParse & 84.92\(\pm\)0.58 & 75.48\(\pm\)0.47 & 86.11\(\pm\)0.49 & 89.66\(\pm\)0.82 & 95.05\(\pm\)0.57 & 93.28\(\pm\)0.83 & 87.22\(\pm\)0.54 & (OOM) & (OM) \\ PIDNet & 83.02\(\pm\)0.11 & 75.00\(\pm\)0.74 & 88.80\(\pm\)0.92 & 91.91\(\pm\)0.21 & 95.57\(\pm\)0.40 & 90.70\(\pm\)0.76 & 87.08\(\pm\)0.65 & (OMOM) & (OM) \\ CLNode & 83.52\(\pm\)0.77 & 75.82\(\pm\)0.05 & 88.69\(\pm\)0.61 & 91.71\(\pm\)0.41 & 95.75\(\pm\)0.46 & 92.78\(\pm\)0.90 & 85.93\(\pm\)1.53 & 70.58\(\pm\)0.17 & 73.97\(\pm\)0.31 \\ RCL & **86.41\(\pm\)0.39** & 76.00\(\pm\)0.18 & **89.71\(\pm\)0.29** & **93.92\(\pm\)0.27** & **96.76\(\pm\)0.17** & **93.83\(\pm\)0.51** & **89.76\(\pm\)0.19** & **73.25\(\pm\)0.18** & **73.78\(\pm\)0.12** \\ \hline GraphSAGE & 86.20\(\pm\)0.27 & 77.27\(\pm\)0.25 & 88.50\(\pm\)0.62 & 94.21\(\pm\)0.18 & 93.26\(\pm\)0.14 & 93.28\(\pm\)0.51 & 88.62\(\pm\)0.21 & 71.19\(\
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.

### 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 \(M\) 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 2, we can observe that RCL shows strong robustness 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.13%, 3.47% on Citeseer dataset, with GCN and GIN backbone models, respectively.

### Ablation Study

To investigate the effectiveness of our proposed model with some simpler heuristics, we deploy a series of ablation analysis. We first train the model with node classification task purely and select the top K expected edges as suggested by the reviewer. Specifically, we follow previous works [43; 45] using two classical selection pacing functions as follows:

\[\mathrm{Linear}\colon K_{\mathrm{linear}}(t)=\frac{t}{T}|E|;\ \ \mathrm{Root} \colon K_{\mathrm{root}}(t)=\sqrt{\frac{t}{T}}|E|,\]

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-linear and Random-root with the above two mentioned pacing functions, respectively.

In order to further investigate the impact of the proposed components of RCL. We also first consider variants of removing the edge smoothing components mentioned in Section 4.3. Specifically, we

Figure 2: Node classification accuracy (\(\%\)) on Cora and Citeseer under random structure attack. The attack edge ratio is computed versus the original number of edges, where \(100\%\) means that the number of inserted edges is equal to the number of original edges.

\begin{table}
\begin{tabular}{c|c c c c c} \hline \hline  & **Synthetic** & **Synthetic2** & **Citeseer** & **CS** & **Computers** \\ \hline Full & **73.98\(\pm\)0.55** & **97.42\(\pm\)0.17** & **79.79\(\pm\)0.55** & **94.66\(\pm\)0.22** & **90.23\(\pm\)0.23** \\ Curriculum-linear & 70.93\(\pm\)0.54 & 95.19\(\pm\)0.19 & 79.04\(\pm\)0.38 & 94.14\(\pm\)0.26 & 89.28\(\pm\)0.21 \\ Curriculum-root & 70.13\(\pm\)0.72 & 95.50\(\pm\)0.18 & 78.72\(\pm\)0.54 & 94.74\(\pm\)0.34 & 89.27\(\pm\)0.15 \\ Random-linear & 58.76\(\pm\)0.46 & 98.70\(\pm\)0.17 & 77.43\(\pm\)0.49 & 29.76\(\pm\)0.14 & 88.76\(\pm\)0.18 \\ Random-root & 61.04\(\pm\)0.20 & 91.04\(\pm\)0.09 & 76.81\(\pm\)0.35 & 92.92\(\pm\)0.15 & 88.81\(\pm\)0.28 \\ w/o edge appearance & 70.70\(\pm\)0.43 & 95.77\(\pm\)0.16 & 77.77\(\pm\)0.65 & 43.99\(\pm\)0.21 & 89.56\(\pm\)0.30 \\ w/o node confidence & 72.38\(\pm\)0.41 & 69.86\(\pm\)0.17 & 78.72\(\pm\)0.72 & 94.34\(\pm\)0.13 & 90.03\(\pm\)0.62 \\ w/o pre-trained model & 72.56\(\pm\)0.69 & 93.89\(\pm\)0.14 & 78.28\(\pm\)0.77 & 94.50\(\pm\)0.14 & 89.00\(\pm\)0.55 \\ \hline \hline \end{tabular}
\end{table}
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.
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 a pre-trained model to initialize model, which is mentioned in 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-linear 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-linear and Random-root on all datasets drops by 3.86% on average compared to the variants Curriculum-linear and Curriculum-root. Such behavior demonstrates the effectiveness of our proposed edge difficulty quantification module by showing that randomly involving edges into training cannot benefit model performance. (iii) 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.

### 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 to 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 a novel CL method to improve the generalization ability and robustness of GNN models on learning representations of data samples with dependencies. The proposed method **R**elational **C**urriculum **L**earning (**RCL**) effectively addresses the unique challenges in designing CL strategy for handling dependencies. First, a self-supervised learning module is developed to 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 is 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.

Figure 3: Visualization of edge selection process during training.
## 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: 10827.002.120.04). The authors acknowledge Emory Computer Science department for providing computational resources and technical support that have contributed to the experimental results reported within this paper.
