Relational Curriculum Learning for Graph Neural Networks
Authors: Zheng Zhang
Junxiang Wang
Liang Zhao
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph neural networks
Curriculum learning

Abstract: Graph neural networks have achieved great success in representing structured data and its downstream tasks such as node classification. The key idea is to recursively propagate and aggregate information along the edges of a given graph topology. 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 graph neural network models may lead to suboptimal learned representations because they usually consider every edge in a given graph topology equally. On the other hand, curriculum learning, 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 of representation learners by gradually proceeding from easy to more difficult samples during training. Unfortunately, most existing curriculum learning strategies are designed for i.i.d data samples and cannot be trivially generalized to handle structured data with dependencies. In order to address these issues, in this paper we propose a novel curriculum learning method for structured data to leverage the various underlying difficulties of data dependencies to improve the quality of learned representations on structured data. Specifically, we design a learning strategy that gradually incorporates edges in a given graph topology into training according to their difficulty from easy to hard, where the degree of difficulty is measured by a self-supervised learning paradigm. We demonstrate the strength of our proposed method in improving the generalization ability of learned representations through extensive experiments on nine synthetic datasets and seven real-world datasets with different commonly used graph neural network models as backbone models.

Under review as a conference paper at ICLR 2023
RELATIONAL CURRICULUM LEARNING FOR GRAPH NEURAL NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks have achieved great success in representing structured data and its downstream tasks such as node classification. The key idea is to recursively propagate and aggregate information along the edges of a given graph topology. 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 graph neural network models may lead to suboptimal learned representations because they usually consider every edge in a given graph topology equally. On the other hand, eurriculum learning, 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, most existing curriculum learning strategies are designed for independent data samples and cannot be trivially generalized to handle data with dependencies. In order to address these issues, in this paper we propose novel curriculum learn- ing method for structured data to leverage the various underlying difficulties of data dependencies to improve the quality of learned representations on structured data. Specifically,
design learning strategy that gradually incorporates edges in given graph topology into training according to their difficulty from easy hard, where the degree of difficulty is measured by self-supervised learning paradigm. 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 with different commonly used graph neural network models as backbone models.
INTRODUCTION
Learning powerful representations of data samples with dependencies has become a core paradigm for understanding the underlying network mechanisms and performing variety of downstream tasks such as social network analysis (Wasserman et al. 1994) and recommendation systems (Ying et al.] 2018 Fan al., 2019). As class of state-of-the-arr representation learning methods, graph neural networks (GNNs) have received increasing attention in recent years due to their powerful ability to jointly model data samples and their dependencies in an end-to-end fashion. Typically, GNNs treat data samples as nodes and their dependencies as edges, and then follow neighborhood ag- gregation scheme learn data sample representations by recursively transforming and aggregating information from their neighboring samples.
On the other hand, inspired by cognitive science studies (Elman 1993 Rohde Plaut 1999) that humans can benefit from the sequence of learning basic (casy) concepts first and ad advanced (bard) concepts later, curriculum learning (CL) (Bengio al. 2009; Kumar al., 2010) suggests training 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. Many previous studies have shown that this easy-to-hard learning strategy can effectively improve the generalization ability of the model (Bengio et al.] 2009 Tiang et al. 2018 Han et al., 2018 Gong et al., 2016; Shrivastava al. 2016 Weinshall et al. 2018). Furthermore, previous studies Jiang et al. 22188]
10188HHam Han et al. [2018) Gong et al. (2166) have shown that CL. strategies increase the robustness of the model against noisy training samples. An intuitive

---

Under review as a conference paper at ICLR 2023
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.
However, existing CL algorithms are typically designed for independent data samples (e.g. image) while designing effective CL strategy for data samples with dependencies has been largely under- explored. In dependent data, not only the difficulty of learning individual data samples can vary but also the difficulty of perceiving the dependencies between data samples. For example, in social networks, the connections between users with certain similar characteristics, such as geological loca- tion or interests, are usually considered as easy edges because their formation mechanisms are well expected. Some connections from unrelated users, such as advertisers or even bots, can usually be considered hard as they are not well expected or even noisy such that the likelihood of these connec- tions can positively contribute to the downstream task, e.g. community detection, is relatively low. Therefore, as the previous CL strategies indicated that an easy-to-hare learning sequence on data samples can improve the learning performance, an intuitive question whether similar strategy on data dependencies that iteratively involving 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 designing feasible principle to select edges by properly quantifying how well they are expected. Existing CL studies independent data often use supervised computable metrics (e.g. training loss) to quantify sample complexity, but how to quantify how well the dependencies between data samples expected which has supervision is challenging. (2) Difficulty in designing appropriate pace to gradually involve edges based on model status. Similar to the human learning process, the model should ideally retain a certain degree of freedom to adjust the curriculum according to its own learning status. It is extremely hard to design a general pacing policy suitable for different real-world scenarios. (3) Difficulty in ensuring convergence and numerical steady process for optimizing the model. Since GNN models work by propagating and aggregating message information over the edges, due to discrete changes in the number of propagating messages by CL. strategy, the learning process of incremental edges increases the difficulty of finding optimal parameters.
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 of representa- tion learners on data with dependencies. To address the first challenge, we propose self-supervised learning approach to select the most K casiest edges that are well expected by the model. Specifi- cally, we jointly learn the node-level prediction task and estimate how well the edges are expected by measuring the relation between learned node embeddings. Second, to design an appropriate learning pace for gradually involving more edges in training, we present the learning process as a concise op- timization model under the self-paced learning framework (Kumar et al. 2010), which lets the model gradually increase the number K of selected edges according to its own status. Third, to ensure con- vergence of optimizing the model, we propose a proximal optimization algorithm with theoretical convergence guarantee and an edge reweighting scheme to smooth the structure transition. Finally, we demonstrate the superior performance of RCL compared to state-of-the comparison methods through extensive experiments on both synthetic and real-world datasets.
RELATED WORK
Curriculum learning (CL). Bengio et al. (2009) first proposed the idea of CL in the context of machine learning, aiming to improve model performance by gradually including easy to hard samples in training the model. Self-paced learning (Kumar et al.] (010)) 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 (Jiang et al. 2015 2014 Zhou et al.) 2020) further proposed many supervised measurement metrics for determining curriculums, for ex- ample, the diversity of samples (Jiang et al. 2014) or the consistency of model predictions (Zhou) et al. 2020). Meanwhile, many empirical and theoretical studies were proposed explain why CL. could lead to generalization improvement from different perspectives. For example, studies such as MentorNet (Jiang et al. (018)) and Co-teaching (Han et al. [0018) 8) empirically found that utilizing CL strategy can achieve better generalization performance when the given training data are noisy.
Gong et al. (2016) provided theoretical explanations on the denoising mechanism that CL learners waste less time with the noisy samples they are considered harder samples.
2

---

Under review as a conference paper at ICLR 2023
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 samples with dependencies. Few existing attempts, such as Wang et al. (202I): Chu et al.] (221 Wei et al. (2022); Li et al. (2022), simply treat nodes or graphs as independent samples and then apply CI. strategies of independent
data, which ignore the fundamental and unique dependency information that carried by the topolog-
ical structure in data, thus can not well handle the correlation between data samples. Furthermore, these models are mostly based on heuristic-based sample selection strategies (Chu al., [2021] Wei
et al. 2022 Li et al. 2022), which largely limit the generalizability of their proposed methods.
Graph structure learning. Another stream of existing studies that related to our work is graph
structure learning. Recent studies have shown that GNN models are vulnerable to adversarial attacks on graph structure (Dai et al., 2018, Züigner et al. 22018: Jin et al. 2021 Wu et al. 2019). 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 (Entezari al. 2020 Chen al.) 2020 Jin et al. 2020; Zheng et al. 2020) Luo et al. (02T) 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 (Dai et al.] 2018 Zügner et at. at 2018 Entezari et al., 2020) 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 (Chen et al.] 2020. Jin al., 2020 Luo et al.) (02T). However, modifying the graph topology will inevitably lose potential 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 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 graph as G = EV.E), where V {ei, U2...., UN a set of nodes that N |V| denotes the number of nodes in the graph and & C V x is is the set of edges. We also let X E RR denote the node attribute matrix and A E RNNNN represents the adjacency matrix. Specifically, the attribute of node vi can be expressed as a b dimensional vector r, R¹. A.j = 1 denotes there is an edge connecting nodes U, and B2 V. otherwise Ar, O. A GNN model f maps node feature matrix X associated with the adjacency matrix A to the model predictions ý = fXX, A), and get the loss LGNN L(ý.y y), where L is the objective function and y is the ground-truth label of nodes. The loss on one node U3 is denoted as 4, = L(e y:).
Curriculum Learning In order to leverage the information carried by the various difficulties of data samples into the training process, Curriculum Learning (CI.) (Bengio et al.) 2009 Kumar et al,, 2010), which is inspired by the cognitive process of human learning principles that learning concepts in meaningful order (Elman) 1993), is a popular training strategy that can improve the generaliza- tion ability of representation learners. Specifically, instead of randomly presenting all training sam- ples to the model as in traditional machine learning algorithms, CL learners start with easy samples and gradually include harder ones during the training process, where the difficulty of samples can be measured by a predetermined policy or a supervised computable metric (e.g. training loss).
METHODOLOGY
As previous CL strategies 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 strategy for handling data with dependencies, which is extremely difficult due to several unique challenges: (I) Difficulty in designing feasible principle to select 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 numerical steady process for optimizing the model.
In order to address the above challenges, we propose a novel CL method named Relational Curriculum Learning (RCL). The sequences, which gradually include edges from easy to hard, are called curriculums and learned in different grown-up stages of training. In order to address the first challenge, we propose joint learning module Incremental Edge Selection (IES), which as shown in Figure Ma). to select edges that are mostly expected by the current model in a self-supervised manner. Specifiically, we jointly learn the node-level prediction task and quantify the difficulty of
3

---

Under review as a conference paper at ICLR 2023
(4)
Incremental Edge Selection (IES)
Residual graph
Refined structure
Latent embedding
Decoder
n.
y +
(b)
IES
IES
IES
Trainin process T
Figure I: The overall framework of RCL. (a) The Incremental Edge Selection module first extracts the latent node embedding by GNN model given the current training structure, then jointly learn the node prediction label and reconstruct the input structure. A small residual eπrоr on an edge indi- cates the corresponding dependency is well expected and thus can be added the refined structure for the next iteration. (b) The iterative learning process of RCL. Model starts with an empty struc- ture and gradually includes more edges until the training structure converges to the input structure.
edges by their residual error in reconstructing the input structure, then K most expected edges are selected for next iteration, where the details are elaborated in section 4. To address the second challenge, which is design an appropriate pace for gradually including more edges, we present self-paced learning framework in section 1.2 as shown in Figure Ib), to automatically increase the number of selected edges K in training given its own training status. Finally, to ensure convergence of optimization, wc propose proximal optimization algorithm with theoretical convergence guar- antee in section 4.2 algorithm [ numerical issue of discretely incrementing the training structure between iterations in section
and we further introduce an edge reweighting scheme to address the
4.1 INCREMENTAL EDGE SELECTION BY QUANTIFYING TOPOLOGY COMPLEXITIES
As mentioned above, we need novel way to select edges by first quantifying their difficulty levels. However, as existing works on independent data typically use supervised training loss of samples to quantify their difficulty level, there exists no supervised metrics on edges. In order to address this issue, we propose a method to quantify the difficulty edges by measuring how well the edges are expected from the learned embeddings of their connected nodes. Specifically, the node embedding of the GNN model, which is learned by transforming and aggregating nodes and their neighbors' features through message-passing fashion, can be considered a high-level semantic representation of data samples and their dependencies. To measure how well the dependencies between data samples expected, we restore the node embeddings the original graph structure, which is called the reconstruction of the original graph structure. The residual graph, which is defined as the degree of mismatch between the input adjacency matrix and the reconstructed adjacency matrix À (+), can be considered strong indicator for describing how well the edges are expected by the current model. Specifically, smaller residual errors indicate a higher probability of being a well-expected edge. In particular, as shown in figure Ma] that at iteration 6, we learn the node-level prediction )((t) and extract the latent node embedding (t) from the current GNN model f(t), Then the latent embedding is restored to the original graph structure to reconstruct the input adjacency matrix. The residual graph R is defined as the degree of mismatch between the input adjacency matrix A and the reconstructed adjacency matrix A (t)
With the developed self-supervised method measure how well edges expected, here we formu- late the key learning paradigm of selecting the top K well-expected edges from the input structure. Specifically, to obtain the training adjacency matrix A (f) that will be fed into the GNN model f(), introduce a learnable binary mask matrix S with each clement S.y {0, 1}. Thus, the training adjacency matrix at iteration f can be represented A (*) (()) o 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 Σ,, Rij. Therefore, the learning objective can be presented as follows:
minLGNN + 3 > S,y
w
s.t. |||| 2 K,
4

---

Under review as a conference paper at ICLR 2023
where the first term LGNN- L(f(X, ww))) y) is the node-level predictive loss, e.g. cross- entropy loss for node classification, the second term Σij S.yR.y aims at penalizing the residual errors on the edges selected by the mask matrix that is a hyperparameter to tune the balance between terms. The constraint is guarantee only the most K well-expected edges are selected.
1] can be computed by a non-parametric kernel function x(2? (9) 2 ). e.g. the inner product kernel. Then the residual error Ruy between
Mathematically, the value of a residual edge A (t) 1/
E
[0.
the input structure and the reconstructed structure can be defined as || - -Au] where ||-I| is commonly chosen to be the squared m--nomm. A smaller residual error of edge Ai denotes that this edge is well-expected, which will be added to the training structure A (t) at an early stage of training.
4.2 SELE-PACED LEARNING OF THE INCREMENTAL STRUCTURE
In order to dynamically include more edges into training, intuitive way is to iteratively increase the value of K in equation D to allow more edges to be selected. However, directly solving equa- tion D is difficult since S is binary matrix where each element S.j E {0. 1}, optimizing S would require solving a discrete constraint program at each iteration. Besides, it is difficult to determine an appropriate value of K according to the training status of the model. In order to solve this issue, we first relax the problem into continuous optimization so that each S. can be allowed to take any value in the interval 1]. Then we treat the constraint as Lagrange multiplier and solve an equiv- alent problem by substituting the constraint to regularization term g(S; A), thus, our overall loss function can be written as:
min LONN B SS, + g(S: W.S
(2)
where ((S: = S|| All and ||-|| is commonly chosen to be the squared fn-norm. Since the training adjacency matrix (+) s(f) as À + oo, more edges in the input topology are included until the training adjacency matrix A (1) converges to the input adjacency matrix A. Specifically, the regularization term g(S A) controls the learning scheme by the age parameter X, where À A(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 approach the input adjacency matrix A, resulting in more edges involved in the training structure.
Optimization of learning objective. It is worth noting that optimizing our objective function in equation requires jointly optimizing parameter w of GNN model f and the mask matrix S. In order to address this problem, we propose a proximal alternating optimization schema to iteratively update w and S in sequence. The full algorithm is presented in Algorithm [ As we can see, our algorithm takes the input of node feature matrix X and original adjacency matrix A, stepsize μ to control the increasing pace of age parameter X, and a hyperparameter y to tune the proximal terms. After initializing the parameters w and S, it alternates between two updating steps until it finally converges: (1) Step 3 first learns the optimal parameter of GNN model f with the current training adjacency matrix; (2) Step 4&5 extracts the latent node embedding by fixing the GNN model parameter and build the reconstructed adjacency matrix by the kernel function; (3) Step 6 learns the optimal mask matrix S with the reconstructed adjacency matrix and regularization term; (4) Step 7 refines the training adjacency matrix with respect to the updated mask matrix; (5) The age parameter À is increased when the training adjacency matrix A (*) is still different from the input adjacency matrix A. thus more edges will be included in the next iteration of the training.
Theorem 1.
We have the following convergence guarantees for Algorithm D
[Avoidance of Saddle Points] If the second derivatives of L(f(X, A (9) w).y) and g(; X) are con- tinuous, then for sufficiently large "Is any bounded sequence (W(!), S(D) generated by Algorithn with random initializations will not converge to a strict suddle point of F almost surely.
[Second Order Convergence] If the second derivatives of L(f A (4) ww), y) and g(; are con-
tinuous, and ((f(X, ()); w) y) and g(S; >) satisfy the Srrdyka-Lojasiewice (KL) property (Wang) el al. 2022), then for sufficiently large ",, any bounded sequence (w(0), {())) generated by Algorithm 7 with random initialization will almost surely converge second-order stationary point of F.
We prove this theorem by Theorem 10 and Corollary 3 from mathematical proof can be found in Appendix B
Li et al. 2019 and the complete
5

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Proximal Alternating Minimization Algorithm for Equation 2
Input Node features X, adjacency matrix A, stepsize a and hyperparameter y Output The model parameter w of GNN model f.
1: Initialize w("), S X
2: while Not Converged do
3: w(1) = arg min L[f(X, (L-(X, +)) Stj A A.s
+
w(t
w
4: Given (()), extract latent nodes embedding (1)) from GNN model
5: Calculate reconstructed structure A (f)
x(2) 3
(1) (t) for all pairs of i
6: S(O)) = arg ming 3 Eii Sis A
A + gg(( + 2 s S S
7: Compute A = (t) o A
8:
if' A o A then increase A by stepsize
9:
end while
10:
return w
4.3
SMOOTH TRAINING STRUCTURE BY EDGE REWEIGHTING
Note that in the algorithm I the optimization process requires iteratively updating the parameters w of the GNN model f with respect to the training adjacency matrix A (*), where the training adja- cency matrix A (1) varies discretely due to the inherent discrete nature of graph topology. However, since state-of-the- representations along edges by recursively aggregating and transforming information from neigh- boring nodes, discretely modifying the number of edges will result in a great drift of the optimal model parameters between iterations. Therefore, the numerical issue caused by discrete changes in the training structure can increase the difficulty of finding optimal parameters and sometimes even hurt the generalization ability of the model. Besides the numerical problem caused by discretely increasing the number of edges, another problem raised by the CL strategy in Section 4.1 is the trustworthiness of the estimated edge difficulty. Recall that the estimated difficulty is inferred from the residual error on the edges, where the reconstructed structure built based on the learned latent node embedding. 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 also compromise the quality of the designed curriculum by CL strategy.
GNN models mostly work in mnesagge-pssing fashion, which computes node
To address both issues, we adopt an edge reweighting scheme to (1) smooth the transition of the training structure between iterations, and (2) reduce the influence of edges that connect nodes with relatively low confidence latent embeddings. Formally, we use a smoothed version of structure A (t) to substitute A (4) for training the GNN model ff in step 5 of algorithm ! where the mapping from A (1) to (t) can be represented as:
(3) where 3(0 is the weight imposed to edge Eay at iteration f, and calculated by considering the counted occurrences of edge eij until the iteration and the confidence of the latent embedding for the connected pair of nodes v; and Uy:
= 300
ij:
8 b/ - ((s
where ei is a function that reflects the number of edge occurrences and p is a function reflect the degree of confidence for the latent node embedding. The details of these two functions are as follow. Smooth the transition of the training structure between iterations. In order obtain smooth transition of the training structure between iterations, we take the learned curriculum on selected edges by the CL strategy into consideration. Formally, we model &e by smooth function of the edge selected times compared to the model iteration times before the current iteration:
(5) where / is the number of current iterations and ((eú)) represents the counting number of selecting edge egy. Therefore, we transform the original discretely changing training structure into a smoothly changing one by taking the historical edge selection curriculum into consideration.
(eer)) = t(exs)/t,
Reduce the influence of nodes with low confidence latent embeddings. As introduced in algorithm| line 6, the estimated structure Á is inferred from the latent embedding Z that is extracted from the trained GNN model f. Such estimated latent embedding may possibly shift from the true underlying embedding, which results in the inaccurately reconstructed structure around the node.

---

Under review as a conference paper at ICLR 2023
In order to alleviate this issue, similar to previous CL strategies inferring the complexity of data samples by their supervised training loss, we model the function P by the training loss on nodes, which indicates the confidence of their latent embedding. Specifically, larger training loss indicates a low confident latent node embedding. Mathematically, the weights p((;) on node n can be represented distribution of their training loss:
p(vs)) ~e
where 1, is the training loss on node et. Therefore, a node with a larger training loss will result in smaller value of p(v;), which reduces the weight of the edges connected that node.
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 [.2) We further present the robustmess test on our CL method against topological structure adversarial attack in Section 5.3] Intuitive visualizations of the edge selection curriculum are shown in Section [5.4] In addition, we verify the effectiveness of all components of the method through ablation studies and measure the parameter sensitivity of our proposed method in Appendix A.2 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 structure, we follow previous studies (Karimi et al. 2018 Abu-El El-Ha et al. 2019) to generate set of synthetic datasets, where the formation probability of edge is designed to reflect its likelihood to positively contribute to the node classification job, which indicates its difficulty level. Specifically, the nodes in each generated graph are divided into 10 equally sized node classes 1, .... 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 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. Therefore, the probability of forming an edge in the synthetic graph can reflect the likelihood that this edge can contribute to the prediction. Specifically, edges with a higher formation probability, e.g. connecting nodes with close labels, meaning that there is a higher chance that this connection will positively contribute to the prediction. We vary the value of homo from 0.1, 0.2. ... ..,.......9.. 0.9 to generate nine graphs in total. More details and a visualization illustrating 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 (Yang et al.] (016)) and ogbn-arxiv Hu et al. (2020), two coauthor network datasets CS and Physics (Shchur al. (0188). two Amazon co-purchase network datasets Photo and Computers (Shchur et al.112018), and one protein interation network (Hu et al. (2020). We follow the data splits from Chen et al. (2018) 8) on citation networks and use a 5-Told cross-validation
Homo ratio
GUN
50.82:102
06,0050.30
65. 17:07
0154-0554
87
15:0.4
93.7200.4
97 08.225
99.1010.11 17
99.932003
GNNSVD
04.9610.76
15.056
63. 0.60
20.23-0.61
80.5110.41
85.02.0.46
90.3120.27
94. 94.2310.22
96.74220223
ProGNN
47.8710.87
51.5910.55
65.39_0.44
76.56
0.49
57.5610.51
93 13..0
97 00.3311..1
99.0410.199 19
99.9410.03
NeuralSpanse
51.42:1.35
$7,9910.9
03:
033
87.40
94.54
97.16.00155
99.0110.22
03
PTDNet
4.99
58.52+282
6382-094
79-37-0.55
98
00.01
00.0
CL Nodes
50.37+0.73
56.64+056
048
M035-40.44
10:447
57 02.2255
990224018 18
99.88+0044
RCL.
$7.57=0.44
02.06:+0.28
03598=0.55
84.54 0.75
92.69:0.099
97.42=0.17
99.62:0.05
99.89-10.02
90.93-0006
GIN
48.33+1.89
$3.62+1.30
77.55-1.10
50.5700.66
97.82-0.18
99
GNNSVD
43.21+1.60
45.60+166
5490-1.16
29-
79.76+40.52
45.63+00.44
93.65+00.9
97.22+0017 17
00
ProGNN
45.76::1.40
12.96:1001
64.12-100
7695=087
85.13-0.71
09556
96. 06.5440..8
99.51+0.12
09.78
NeuralSparse
50.234.2.0
14.12+1552
62.81
1.19
85. 05.144
92.5710.44
98 98.0210.20
99.6110.12
99 91 0.005
PTDNNet
53.2312.76
26.121203
63.81
1.02
86 140.65
93.2110.74
97 97.0810.111
99.5110.18
10.03
CLNodes
45.3611.442
31,1011.15
62.53-088
87.76.0.90
94
98.3010.26
99.000009
RCI.
57.63+0.66
6..0-11.17
71.92-0611
0.61
90.66
19-0.19
99.52-0.00
89
GraphSage
62.5110.55
61.3310611
71.620044
0.4
85.110311
914210.31
95 95.2610033
97.7810.16
WU.5200.13
GNNSVD
64422:080
65.71:1039
02.12-055
68 0.5
77.011065
82 00
87.8110.71
91.61110.55
90.01:10.50
PootNN
58.574209
66.75+091
12.14-064
27-444444
95.21+0.30
97.51+0023
99.50+-0.11
NeuralSpanse
61,20+0.77
66.61+0666
30.60=0799
09.650445
19+099
51.3140.54
86+0.3
97.16+0022
99.55+0011
PTDNNet
65.72+1.08
69.25+0.92
72. 0.77
79.66 0.5
86.54-0.56
91.79+0.53
96, 10:00888
97.98-+0.12 13
99.78-00.8
CoNosss
69.4120.66
70.8310.58
05.51=0336
82 05-433
87.06:00.56
91 0.141
95.9120.38
98. 98.33110266
99. 99.57.0.14
RCL
68.0310.37
71,3910.11
76.99.0.99
0.576_0.55
88.2410.30
93.3410.56
97.66110,52
98.86100.28
99.6110.00
Table 1: Node classification accuracy on synthetic datasets (%). The best-performing method on each backbone GNN model is highlighted in bold, while the second-best method underlined. In situations where RCL's performance is not strictly 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.
7

---

Under review as a conference paper at ICLR 2023
Cora
Clteseer
Pahmed
CS
Plysies
Photo
Computers
ogbu-arxiv
ogbn-proicins
modes
2,708
3,527
19.317
18,335
34,893
7,600
13,752
109,343
132,534
* alpes
10,556
9,104
88,648
163,768 -
405,934
238,162
491,722
1,166,243
39,561, 252
featunes
1,435
3,700
500
6805
8,415
745
767
100
GCN
45.741042
78
GNNSVD
13.2411.03
74.80.1087
13.7910.11
96.111011
89
86. 06779
00.9210005
PioGNN
6566+061
74. 14.78+055
87.22-0.35
19
06 7540
2207-067
8R 08:72-0:99
SpuralSpame
76. 24:10400 48
86
95 50.5613330
0.99709900
88 88.82.0..3
PIINNe
77.52:1022 42
N7 07.89-0.08
00
90.56
88:922087
87.52200:70
78. 57
89 0..50-0.22
95
95 76+0 16
03.99-083
89 11.22-0.85 38
2095--.18
71 40+0:32
RCL
57.1510.44
79.79
0.55
89.79.0.1
10.66.0.33
97.02 0.233
94.41
90.23
0.23
74.0800333
15.19.00.66
CIN
51431005
74.77
20
85.72:0.40
48100.3
95 05.0210000
93.02:000 019
86
06.04:11
1.58
89:6100.4
GNNSVD
72.11:2070
08.31
95.3010029
3.111
N2
02.06:2222
2.26
67.7940.41
70.0
PNoGNN
45.0240.44
7M.12
02.23-0067
1488
Spore
519210.58
95.05 50
93.28
PTDNat
83.02:1001
75.00
08.04:0.29
000000076
87
0.65
CLNode
53.5230.77
75.82.0038
86, 86.92.0.011
95 75.25.00 46
92.78
85.93 1.53
739710.31
RCI.
86.64-0..99
77.60+0 18
89.17-0.29
96.75-0-177
03.88-0.51
89.76-0.199
72.55HLIS
78776+0.22
GraphSuge
56.2210.27
71.271023
88 88.50100:16
04221011
96, 26 20.3
93
88.62 0:21
713910027
77.6500:00
GNNSVD
83 33.11:0.82
73.19:0.49 49
88 88.42-0.38
03
95.9611011 12
09.31=0:51
81 1611.15
698220034
ProGNN
86.25110.22
74,45.1083
88.52.0.45
90.8910.69
89 09.44
NeuralSparse
54.00-00.22
76.32+0055
89,02-0.39
50
9667600.0 30
90-76=1006
30.37
PTDNee
86.03.0.600
76.07.10.58
86.78.00:5
95.32.10311
92,9611087
CLMode
56.00130.64
72.23:0.54
88.7620..57
1220...
9688740455
93.9020.42
89 57.5720.62
71.5410.20
484044-41
RCI.
86.90-0.399
79.95+0.18
90.14-0.43
05.05-0.23
96.88-0.19
95.06-0.52
90.47-0.38
7A.3+-U14
70.9
Table Node classification results on real-world datasets (%). The hest-performing method on each
backbone is highlighted in bold and second-best is underlined. (-) denotes an out-of-memory issue.
setting on coauthor and Amazon co-purchase networks. All data are from Pytorch-geometric li- brary (Fey& & Lenssen 2019) and basic statistics are reported in Table 2
Comparison methods. We incorporate three commonly used GNN models, including GCN (Kipf & / GraphSAGE (Hamilton et al. (017), and GIN (Xu et al.) (018)) 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 methods in the experi- ments: (1) We incorporate four graph structure learning methods GNNSVD (Entezari et al. 2020),
ProGNN (Jin et al., 2020), NeuralSparse (Zheng et al. 2020), and PTDNet (Luo et al. (021): 1); (2) We further compare with a curriculum learning method CLNode (Wei et al.] (022) which gradually select nodes in the order of the difficulties defined by heuristic-based strategy. More details about the comparison methods and model implementation details can be found in Appendix A.
5.2 EFFECTIVENESS ANALYSIS ON SYNTHETIC AND REAL-WORLD DATASETS.
Table [ 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. 4.17%, 2.60%, and 1. 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 (S 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 's capability of learning an effective representation to downstream tasks especially when the complexities 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 6 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 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 out of 43 cases with a significance < 0.05. Such statistical significance results can demonstrate that our proposed method can consistently perform better than the bascline models in all datasets.
5.3 ROBUSTNESS ANALYSIS AGAINST ADVERSARIAL TOPOLOGICAL STRUCTURE ATTCK
To further examine the robustness of the RCL method on extracting powerful representation from complex data samples, we follow previous works (Jin et al. 2020 Luo et al., (02T) to randomly inject fake edges into real-world graphs. This adversarial attack can be viewed adding random
8

---

Under review as a conference paper at ICLR 2023
noise to the topological structure of graphs. Specifically, 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. 3.47% on Citeseer dataset, with GCN and GIN backbone models, respectively. Citesear,
Cora, GCN
Cora,
Citesear, GCN
0.83
2./5
Accuracy
0.72
2.70
0.72
0.55
2.45
6.78
2.00
0.62
0.55
0.55
20
32 Attack edge (16)
20
60 20120
30 20 12 Attack edge (9)
Attack edge (%)
edge
-
basic
+ GNNSVD
PreGNN
+
NeuratSparse
PTDNet
+
CLNode
+
RCL
Figure 2: Node classification accuracy (%) on 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.
5.4
VISUALIZATION OF LEARNED EDGE SELECTION CURRICULUM
Besides the effectiveness of the RCL method on downstream classification results, it is also inter- esting to verify whether the learned edge selection curriculum satisfies the rule from easy to hard. Since real-world datasets do not have ground -ruth labels of difficulty on edges, we conduct exper- iments on synthetic datasets, where the difficulty of each edge can be indicated by its formation probability. Specifically, we classify edges into three 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 S We can observe that RCL can effectively select most the easy edges the beginning of training, then more easy edges and mostly medium edges gradually included during training, and most hard edges are left unselected until the end stage of training. Such model behavior is consistent with the idea of designing 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, regardless of the backbone model choice.
GCN
GIN
GraphSage
1.0
1.0
1.0
Easy
Easy
Easy
0.8
Medium
0.8
Medium
0.8
Medium
Hard
Hard
Hard
Ratio
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
50
100
150
50
100
150
50
100
150
Epechs
Epochs
Epochs
Figure 3: Visualization of edge selection on the synthetic dataset.
6 CONCLUSION
This paper focuses on developing a novel CL strategy to improve the generalization ability of GNN models on data samples with dependencies. The proposed method Relational Curriculum Learning (RCL) effectively addresses the unique challenges in designing CL. strategy for handling depen- dencies. First, a self-supervised learning module is developed to select appropriate edges that are expected by the model. Then optimization model is presented to iteratively increment the training structure 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 nu- merical 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.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learn- ing. pp. 21-29. PMLR, 2019.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pp. 41-48, 2009,
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural net- works: Better and robust node embeddings. Advances in neural information processing systems, 13:19314-19326, 2020.
Guanyi Chu, Xiao Wang, Chuan Shi, and Xunqiang Jiang. Cuco: Graph representation with cur- riculum contrastive learning. In IJCAI, pp. 2300-2306 2306, 2021.
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, pp. 1115-1124. PMLR, 2018.
Jeffrey L Elman. Learning and development in neural networks: The importance of starting small. Cognition, 48(1):71-99, 1993.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 169-177, 2020.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Erie Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint 1rXiv:1903.02444 2019.
Tieliang Gong, Qian Zhao, Deyu Meng, and Zongben Xu. Why curriculum learning & self-paced learning work in big/noisy data: A theoretical perspective. Big Data & Information Analytics, (1):111, 2016.
Guy Hacohen and Daphna Weinshall. On the power of curriculum learning in training deep net- works. In International Conference on Machine Learning, pp. 2535-2544. PMLR, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Bo Han, Quanming 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.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0066 2020.
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.
Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander G Hauptmann. Self-paced eur- riculum learning. In Twenty-ninth AAAI conference on artificial intelligence, 2015.
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. International conference machine learning, pp. 2304-2313. PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2023
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 A ACM SIGKDD international conference on knowledge discovery & data mining, pp. 66,74, 2020.
Wei Jin, Yaxing Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Ad- versarial attacks and defenses on graphs. ACM SIGKDD Explorations Newsletter, 22(2))19-34, 2021.
Fariba Karimi, Mathieu Génois, Claudia Wagner, Philipp Singer, and Markus Strohmaier. Ho- mophily influences ranking of minorities in social networks. Scientific reports, 8(1):1-12, 2018.
Thomas N. Kipf and Max Welling, Semi-Supervised Classification with Graph Convolutional Net- works. In Proceedings of the 5th International Conference Learning Representations, 2017.
M Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. Advances in neural information processing systems, 23, 2010.
Qiuwei Li, Zhihui Zhu, and Gongguo Tang. Alternating minimizations converge to second-order optimal solutions. In International Conference Machine Learning, pp. 3943.. PMLR, 2019.
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.02559, 2022.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM international conference on web search and data mining, pp. 779-787, 2021.
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, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
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.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arv: /8/ 1.05868, 2018
Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region-base based object detectors with online hard example mining. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 761-769, 2016.
Junxiang Wang, Hongyi Li, and Liang Zhao Accelerated gradient-free neural network training by multi-convex alternating optimization. Neurocomputing, 487:130-144 2022.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Curgraph: Curriculum learning for graph classification. Proceedings of the Web Conference 2021, pp. 1238-1248, 2021.
Stanley Wasserman, Katherine Faust, et al. Social network analysis: Methods and applications. 1994.
Xiaowen Wei, Weiwei Liu, Yibing Zhan, Du Bo, and Wenbin Hu. Clnode: Curriculum learning for node classification. arXiv preprint arXiv:2206.07258, 2022.
Daphna Weinshall, Gad Cohen, and Dan Amir. Curriculum learning by transfer learning: Theory and experiments with deep networks. In International Conference Machine Learning, pp- 5238-52 0246.224.115 PMLR, 2018.
Richard Lee Wheeden and Antoni Zygmund. Measure and integral, volume 26. Dekker New York, 1977.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversar- ial examples for graph data: deep insights into attack and defense. In Proceedings of the 28th International Joint Conference Artificial Intelligence, pp. 48 188664823, 2019.

---

Under review as a conference paper at ICLR 2023
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Rex Ying. Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974- 983, 2018.
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 Machine Learning, pp. 11458-1 1468. PMLR, 2020.
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.
Daniel Zügner,, Amir Akharnejad, 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, pp. 2847-2856, 2018.
12

---

Under review as a conference paper at ICLR 2023
A ADDITIONAL EXPERIMENTAL SETTINGS AND RESULTS
A.I ADDITIONAL EXPERIMENTAL SETTINGS
Synthetic datasets To evaluate the effectiveness of our proposed method on datasets with ground- truth difficulty labels on structure, we first follow previous studies (Karimi ct al. 2018 Abu-El-Hann
al. 2019 to generate set of synthetic datasets, where the difficulty of edges in generated graphs are indicated by their formation probability. Specifically, graph is with 5,000 nodes, which are divided into 10 equally sized node classes ......., 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 For example, 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 formed between nodes with different labels (different colors in Figure 4. the probability of forming an edge is inversely proportional to the distances between their labels. Mathematically, the probability of forming an edge between node u and node v fol- lows Pu-ve e-los where the distances between labels |c,, c.l 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 higher formation probability, e-g- connecting nodes with the same label or close labels, meaning that there is a 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 a 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.2, 0.9 to generate nine graphs in total. Similar to previous works (Karimi et al. 2018 Abu-El Hajja et al. 2019), we randomly partition each synthetic graph into equal-sized train, validation, and test node splits.
shown in Figure + each generated
Figure 4: Visualization of synthetic datasets. Each color represents class of nodes. Node attributes are sampled from overlapping multi-Gaussian Gaussian distributions, where the attributes of nodes with close labels are likely to have short distances. Homogeneous 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 node denotes the edge difficulty, since edges between nodes with close classes are more likely to positively contribute to the prediction under the homogeneous assumption.
Initializing graph structure by a pre-trained model. It worth noting that the model needs an initial training graph structure A (9) in the initial stage of training. An intuitive way is that can initialize the model to work in a purely data-driven scenario that starts only with isolated nodes where no edges exist. However, instructive initial structure can greatly reduce the search cost
13

---

Under review as a conference paper at ICLR 2023
and computational burden. Inspired by many previous CL works (Weinshall et al. 2018 Hacohen & Weinshall, 2019 Jiang et al. 2018 Zhou et al.] 2020) that incorporate prior knowledge of a pre- trained model into designing curriculum for the current model, we initialize the training structure (9) by 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 A (o) but the latent node embedding 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 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 the number of training epochs) are equal for all models. For the pre-trained model to initialize the training structure, utilize the same model as the backbone model utilized by our method. For example, if we use GCN as the backbone model for RCL, the pre- traitre 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 (Paszke al. 2019).
The following describes the details of our comparison models.
Graph Neural Networks (GNNs). We first introduce three baseline GNN models follows.
(i) GCN. Graph Convolutional Networks (GCN) (Kipf & Welling 2017) is a commonly used GNN, which introduces first-order approximation architecture of the Chebyshev spectral convolution operator;
2018 is variant of GNN, which has (ii) GIN. Graph Isomorphism Networks (GIN) (Xu et al.
provably powerful discriminating power among the class of T-order GNNs;
(iii) GraphSage. GraphSage Hamilton al. (207)) is GNN method that computes the hidden representation of the root node by aggregating the hidden node representations hierarchically from bottom 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 (Entezari et al. 2020) first apply singular value decomposition (SVD) on the graph adjacency matrix obtain low-rank graph structure and apply GNN the obtained low-rank structure;
(ii) ProGNN. ProGNN (Tin et al. 2020 method defend against graph adversarial attacks by obtaining a sparse and low-rank graph structure from the input structure;
(iii) NeuralSparse. NeuralSparse (Zheng et 2020) is method to learn robust graph representa- tions by iteratively sampling k-neighbor subgraphs for each node and sparsing the graph according the performance on the node classification;
(iv) PTDNet. PTDNet (Luo et al.) [2021) learns sparsified graph by pruning task iusk-itreeevant edges, where sparsity is 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 (Wei et al. 2022) regards nodes as data samples and gradually incorporates more nodes into training according their difficulty. They apply a heuristic- hhesistic-based strategy to mea- sure 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: {le-2, -,, le-3);
Number of GNN layers: {2):
Dimension of hidden state: (64];
Age parameter : (1, denotes the training structure will converge to the input structure the final iteration).
2, 3, 4, 5,5) (A larger value indicates faster pacing for adding edges, where
14

---

Under review as a conference paper at ICLR 2023
A.2 ADDITIONAL EXPERIMENTS
Synthetic1
Synthetic2
Citeseer
Computers
Full
+3.58
97.4240.17
7..79=0.53
94.66=0.22
90.23+0.23
w/o edge appearance
70.20++0.43
95.77+0.16
77.77+0.65
94.39+0.21
89.56++.30
w/u node confidence
72.3811041
96.86.0.117
78.72.1.72
94.34.10.13
90.03-10.62
w/o pre-trained model
72.56+00.69
93.89+4..14
78.28=0.77
94.50=0.144
89.80=00.55
Table 3:
Ablation study. Here "Full" represents the original method without removing any compo- nent. The best-performing method on each dataset is highlighted in bold.
Ablation study Here we investigate the impact of the proposed components of RCL. We first con- sider variants of removing the structural smoothing components mentioned in Section 4.3 Specif- ically, we consider two variants w/o edge appearance and w/o node confidence, which remove the smoothing function of the edge appearance ratio and the component reflect the degree of confi- dence for the latent node embedding in RCL. respectively. In addition to examining the effective- ness components structural smoothing, we further consider variant w/o pre-trained model that avoids using pre-trained model, which is mentioned in Appendix A.I 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 (homophity coefficient= 0.3, 0.6) and three real-world datasets Table 3 where we can observe a significant performance drop consis- tently for all variants. The results validate that all structural smoothing and initialization components can benefit the performance RCL on the downstream tasks.
Parameter sensitivity analysis Recall that RCL learns curriculum to gradually add edges in a given input graph structure to 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 conduct experiments to explore the impact 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, À = 1 means that the training structure will probably not converge the input structure until the last iteration, and X will converge to 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, classification results are steady that the average standard deviation is 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 completed.
means that the training structure
Synthetic1
Synthetic2
Cora
Citeseer
74
93.0
80.0
87.5
Acciracy
73-
79.0
86.5
78.5
91.5
2
3
Figure 5: Parameter sensitivity analysis on four datasets. Here larger value of À means the training structure will converge to the original structure at earlier training stage.
B MATHEMATICAL PROOF
Theorem 1. We have the following convergence guarantees for Algorithm I
[Avoidance of Saddle Points] If the second derivatives of L(f(X, A (4), w).y) and (S; X) are con- tinuous, then for sufficiently large 7, any bounded sequence (w()), s(()) generated by Algorithn
15

---

Under review as a conference paper at ICLR 2023
with random initializations will not converge strict saddle point of F almost surely.
[Second Order Convergence] If the second derivatives of I(J(X, (0; w),y) and g(S; A) are continuous, and L(f(X, A ( w y) and g X) satisfy the Kurdyka-Lojasievinn (KL) property (Wang et al. 2022). then for sufficiently large 7 any bounded sequence (w(+), S()) generated by Algorithm 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 3 from Li et al. (2019).
[Avoidance of Saddle Points] Because the sequence (w(*), S()) is bounded, and the second derivatives of L and g continuous, then they are bounded. In other words, max{ L( A (0;; (()) r)ll (ss(t) 2UDl} s p, where p
have
0 is a constant. Simi- Anl
1
larly, it is easy to check that the second derivative of the term Σnj Sig
is bounded, q. where
is constant and À function of w. Therefore, it means that the objective is bi-smooth, i.e. m Fll |]] V S In other words, F satisfies Assumption 4 from Li et al. (2019). Moreover, the second derivative of F is continuous. For any 7 p + q. any bounded sequence (w(*), (()) generated by Algorithm will not converge to striet saddle of F almost surely by Theorem 10 from Li et (2019).
i... max{
7 En,
Siy
A
A.
E. Sis A Aus
[Second Order Convergence From the above proof of avoidance of saddle points, we know that F satisfies Assumption 4 from Li et al. 2019). Moreover, because I. and g satisfy the KL property,
A.j satisfies the KL property, we conclude that F satisfy the KL property well. From the proof above, also know that the second derivative of F is continuous. Because continuous differentiability implies Lipschitz continuity Wheeden & Zygmund| (1977). infers that the first derivative of F is Lipschitz continuous. As result, F satisfies Assumption
and the term Σi, S.j A
from Li et al. (2019). Because I' satisfies Assumptions I and 4, then for any y > p any bounded
sequence (w("), (()) generated by Algorithm will almost surely converges to second-order sta- tionary point of F by Corollary from Li et al. 2019).
While the convergence of Algorithm entails the second-order optimality conditions of and g, some commonly used f such as the GNN with sigmoid or tanh activations and some commonly used y such as the squared &a norm satisfy the KL property, and Algorithm[]is guaranteed to avoid a strict saddle point and converges to second-order stationary point.
16


Reviews:
[{"review_id": "wMyCCMeUMg", "reviewer": "Reviewer_yJ3m", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper targets the problem that the edges in a graph may have different levels of difficulty to learn and proposes a curriculum learning-based model to gradually incorporate edges during learning according to their difficulties. The difficulty level is obtained by self-supervised learning. Experiments are conducted on 9 synthetic datasets (with 9 different homophily coefficients) and 7 real-world datasets.", "summary_of_the_review": "Overall, this paper has a novel idea, but the proposed model is not totally clear. Besides, misusing the concepts like i.d.d. makes the paper not rigorous enough.", "strength_and_weaknesses": "\nStrengths:\n\n1. The paper is overall easy to understand. The motivation and the background knowledge of the curriculum learning are clearly introduced.\n\n2. The idea to achieve better learning performance on graphs by investigating the difficulty of the edges is novel.\n\n3. In experiments, both synthetic datasets and real-world datasets are used. The synthetic datasets have controllable properties (i.e. homophily coefficient).\n\n\nWeakness:\n\n1. The main idea is pretty intuitive. The difficulty level of the edges is only intuitively proposed without concrete examples. Therefore, it is unclear what exactly the difficulty levels mean. Moreover, the noise seems to be one component of the difficulty, is there any other concrete factors determining the difficulty?  \n\n2. i.d.d data is not correctly used. What the authors want to express through i.d.d data should be 'independent data', in which the data have no connections. While i.d.d. data refers to different samples drawn independently from identical distributions.\n\n3. In experiments, it is unclear why the difficulty of the edges can correspond to the formation probability.\n\n4. The datasets are rather small. \n\n5. The proposed method is not consistently better than the baselines in all datasets. Besides, is there any experiment that can demonstrate that it is indeed the curriculum learning part that improves the performance, instead of other factors like model complexity?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h_9MbmEoyJ", "reviewer": "Reviewer_fwhF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates curriculum learning for graph neural networks (GNNs), aiming at selecting the most important edges in a graph for GNN training. The authors formalize the task as an optimization problem, which has a node-level predictive loss and a structural-penalty loss. A proximal algorithm is proposed for optimization. Experimental results on multiple datasets are encouraging.", "summary_of_the_review": "See the comments above.", "strength_and_weaknesses": "Strengths:\n1. The problem of learning graph structures for GNN is important.\n2. The proposed method uses the node representations learned by GNNs to measure the likelihood of each edge, which is quite intuitive.\n3. Some improvements are observed in the experiment.\n\nWeaknesses:\n1. The writing of the paper can be further improved.\n2. The improvements over existing methods are not significant.\n\nDetailed comments:\n\n1. The writing of the paper can be further improved.\nThe abstract of the paper says that a curriculum learning method is proposed, where edges are given to GNNs according to their difficulty from easy to hard, and the difficulty is measured by a self-supervised learning paradigm. However, in the model section, these claims are not well explained. The edge difficulty and self-supervised learning paradigm are not mentioned. Although readers can roughly get the idea that the edge difficulty is measured by the inner product between corresponding node embeddings, I feel like the abstract and model sections are written by different authors, making it not easy to follow.\n\n2. Many ideas of the paper are not new\nThe overall loss function of the proposed method is given by Eq. (3) of Algorithm 1. There are three parts, where the first part is a supervised loss, the second part is a graph reconstruction loss, and the third one is a regularization term. The first two terms are widely studied in the graph machine learning literature for GNN training and structure learning. Given these existing works, I feel like this paper does not bring new ideas. Although the authors introduce their method from a perspective of curriculum learning and some smoothing strategies are proposed in Sec. 4.3, I think the contribution is not so significant as the underlying ideas are not so different from existing methods.\n\n3. The improvements over existing methods are not very significant.\nThe results on real-world datasets are presented in Tab. 2, where the improvements over existing methods are not so significant, and the results on different datasets all have very high standard deviation. To better convince readers, I think it is helpful to consider some larger datasets for evaluation, where the standard deviation over different runs can be smaller.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QtXXhhNk0we", "reviewer": "Reviewer_f5Ws", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a method for iterative construction of graph structure in GNN settings. The key is to make use of the homophily -- similar nodes tend to connect. The optimization procedures encourage more edges to be added along the training process. This results in a better optimized GNNs -- boosting up accuracy performance and improved robustness against structural noise.", "summary_of_the_review": "An useful attention to the literature of graph structure learning in GNNs. I'd like to see when the homophily assumption breaks and how the method will be adjusted.", "strength_and_weaknesses": "Strength\n======\n- The paper studies an interesting problem -- optimizing the parameter and graph structure jointly.\n- The proposed solution is sensible and is shown empirically to improve performance and robustness.\n\nWeaknesses\n==========\n- Posing the forward edge selection as curriculum learning is somewhat confusing. It is better to emphasize on the joint optimization aspects.\n- Again, adding terms like self-paced, self-supervised learning are also confusing.\n- Although homophily is a well-known properties of real-world graphs, it would be interesting to see if this assumption breaks, e.g., redesigning the kernel for graph reconstruction.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject