Curriculum Learning for Graph Neural Networks: A Multiview
  Competence-based Approach
A curriculum is a planned sequence of learning materials and an effective one
can make learning efficient and effective for both humans and machines. Recent
studies developed effective data-driven curriculum learning approaches for
training graph neural networks in language applications. However, existing
curriculum learning approaches often employ a single criterion of difficulty in
their training paradigms. In this paper, we propose a new perspective on
curriculum learning by introducing a novel approach that builds on graph
complexity formalisms (as difficulty criteria) and model competence during
training. The model consists of a scheduling scheme which derives effective
curricula by accounting for different views of sample difficulty and model
competence during training. The proposed solution advances existing research in
curriculum learning for graph neural networks with the ability to incorporate a
fine-grained spectrum of graph difficulty criteria in their training paradigms.
Experimental results on real-world link prediction and node classification
tasks illustrate the effectiveness of the proposed approach.
Nidhi Vakil, Hadi Amiri
# Curriculum Learning for Graph Neural Networks: A Multiview Competence-based Approach

###### Abstract

A curriculum is a planned sequence of learning materials and an effective one can make learning efficient and effective for both humans and machines. Recent studies developed effective data-driven curriculum learning approaches for training graph neural networks in language applications. However, existing curriculum learning approaches often employ a single criterion of difficulty in their training paradigms. In this paper, we propose a new perspective on curriculum learning by introducing a novel approach that builds on graph complexity formalisms (as difficulty criteria) and model competence during training. The model consists of a scheduling scheme which derives effective curricula by accounting for different views of sample difficulty and model competence during training. The proposed solution advances existing research in curriculum learning for graph neural networks with the ability to incorporate a fine-grained spectrum of graph difficulty criteria in their training paradigms. Experimental results on real-world link prediction and node classification tasks illustrate the effectiveness of the proposed approach.1

Footnote 1: Code, data splits and guidelines are available at [https://clu.cs.uml.edu/tools.html](https://clu.cs.uml.edu/tools.html).

## 1 Introduction

Graph Neural Networks (GNNs) are generally trained using stochastic gradient descent (SGD), where the standard approach is to iteratively use the _entire_ training data to optimize model's objective until convergence. Curriculum learning techniques improve this training process by scheduling examples for training, e.g., by gradually learning from easier examples before training with harder ones. Such curricula can be predefined by humans Bengio and LeCun (2007); Bengio et al. (2009) or dynamically derived from data during training Jiang et al. (2018); Castells et al. (2020).

Curriculum learning for graph neural networks is an emerging area of research. Recently, Chu et al. (2021) employed a traditional curriculum learning approach introduced in Bengio et al. (2009) to improve negative sampling for graph classification. Wang et al. (2021) proposed to estimate the difficulty of graph entities-nodes, edges or subgraphs-based on the intra- and inter-class distributions of their embeddings in supervised settings, and developed a smooth-step function to gradually introduce harder examples to GNNs during training. Vakil and Amiri (2022) developed a loss-based curriculum learning approach that dynamically adjusts the difficulty boundaries of training samples based on their sample-level loss trajectories obtained from recent training dynamics of GNN models.

To the best of our knowledge, existing curriculum learning approaches often employ a _single_ criterion of difficulty in their curriculum learning framework, e.g., prediction loss Wu et al. (2021), consistency in prediction loss Xu et al. (2020), moving average of loss Zhou et al. (2020) or transformations of loss Vakil and Amiri (2022). We address this gap by developing a new curriculum learning approach for GNNs titled **M**ultiview **C**ompetence-based **C**urriculum **L**earning (MCCL) that builds on the complexity formalisms of graph data. By leveraging rich graph structures, graph complexity formalisms and model _competence_ (learning progress), we will design robust curricula for training GNNs. Table 1 shows three subgraphs ranked differently according to different graph complexity indices. If complexity is measured by _node degree_, then G1 and G2 are less complex than G3 because target nodes in these subgraphs have an overall smaller node degrees. However, if complexity is measured by _closeness centrality_2, then G2 is more complex than G3 because the target nodes are less central in G2 than those in G3. It is evident that complexity indices (views) can vary significantly in their difficulty estimates of graph data.

Footnote 2: Closeness centrality Sabidussi (1966) is smaller for central nodes–those that are closer to other nodes in the graph.
The objective of this work is improve the training process of GNNs by strategically and dynamically (during training) prioritizing key complexity indices, aiming to guide the model toward better minima within its parameter space. Graph complexity is a well-established area of research and our review of relevant literature suggests that there exist various techniques that employ structural properties of nodes, edges and subgraphs to quantify complexity of graph data (Kim and Wilhelm, 2008; Vishwanathan et al., 2010; Newman, 2018; Kriege et al., 2020). We build on these indices to design our curriculum learning framework which treats each complexity index as a view of difficulty. Our approach consists of a novel data scheduling scheme which derives effective curricula based on given views of sample difficulty and model competence during training. Specifically, given a downstream GNN model, our data scheduler gradually selects training examples from a graph complexity view based on competency of the GNN model during training. The model updates its competency and the scheduler determines the next best view for training the model. As model competency gradually increases, the scheduler allows using more signals from different views.

The contributions of this paper are as follows:

* A new curriculum learning approach that effectively leverages complexity formalisms of graph data, taking into account multiview difficulty of training data samples and model's learning progress, and
* Key insights into important complexity indices for effective training of graph neural networks for NLP applications.

We conduct extensive experiments on real world datasets for link prediction and node classification tasks in text graph datasets. Our approach results in 3.3 and 1.8 absolute points improvements in F1-score over the state-of-the-art model on link prediction datasets and 6.7 and 4.9 absolute points improvement on the node classification dataset. The results show that the contribution of complexity indices in training depends on factors such as training stage and model behavior. When the scheduling criterion relies solely on complexity indices, the scheduler tends to initially focus on indices that operate locally around nodes, and later shifts to those that operate globally at graph level. Extending schedulers based on model dynamics (e.g., loss) results in both local and global indices being used throughout the training. These findings provide insights into the type of complexity information that GNNs learn at different stages of their training.

\begin{table}
\begin{tabular}{l l l l l} \hline \hline
## 2 Competence-based Multiview Curricula

We present a competence-based multiview curriculum learning framework for training GNNs. At every training iteration, the framework selects a sub-set of training examples based on the best complexity index (view) and model's competence at that iteration. Algorithm 1 describes the overall approach. We first introduce our complexity indices and then present the model.

### Graph Complexity Formalisms

Various graph complexity indices were introduced in graph theory (Kashima et al., 2003; Borgwardt and Kriegel, 2005; Vishwanathan et al., 2010; Kriege et al., 2020; Newman, 2018). We consider 26 of such indices which represent criteria of difficulty in our curriculum learning framework.3 In what follows, we describe a few representative complexity indices and refer the reader to Appendix A for a full description of all indices.

Footnote 3: Our list of complexity indices may not be exhaustive. However, our framework and implementation allows adding any number of additional indices.

Since GNNs train through neural message passing at subgraph level (Gilmer et al., 2017; Hamilton et al., 2017), we compute complexity indices with respect to the \(k\)-hop neighbors (subgraph) of target nodes. For tasks involving two nodes (e.g., relation extraction), we sum the scores computed for the node pairs. We use Networkx (Hagberg et al., 2008) to compute the indices:

* **Degree:** The number of immediate neighbors of a node in a graph.
* **Average neighbor degree:** Average degree of the neighbors of a node: \[\frac{1}{|\mathcal{N}_{i}|}\sum_{j\in\mathcal{N}_{i}}k_{j},\] where \(\mathcal{N}_{i}\) is the set of neighbors of node \(i\) and \(k_{j}\) is the degree of node \(j\).
* **Katz centrality:** The centrality of a node computed based on the centrality of its neighbors. Katz centrality computes the relative influence of a node within a network by measuring the number of immediate neighbors and number of walks between node pairs. It is computed as follows: \[x_{i}=\alpha\sum_{j}\mathbf{A}_{ij}x_{j}+\beta,\] where \(x_{i}\) is the Katz centrality of node \(i\), \(\mathbf{A}\) is the adjacency matrix of Graph \(G\) with eigenvalues \(\lambda\). The parameter \(\beta\) controls the initial centrality and \(\alpha<\) 1 / \(\lambda_{max}\).
* **Resource allocation index:** For nodes \(i\) and \(j\) in a subgraph, the resource allocation index is defined as follows: \[\sum_{k\in(\mathcal{N}_{i}\bigcap\mathcal{N}_{j})}\frac{1}{|\mathcal{N}_{k}|},\] which quantifies the closeness of target nodes based on their shared neighbors.
* **Subgraph density:** The density of an undirected subgraph is computed as follows: \[\frac{e}{v(v-1)},\] where \(e\) is the number of edges and \(v\) is the number of nodes in the subgraph.
* **Local bridge:** A local bridge is an edge that is not part of a triangle in the subgraph. We take the number of local bridges in a subgraph as a complexity index.
* **Subgraph connectivity:** Is measured by the _minimum_ number of nodes that must be removed to disconnect the subgraph.
* **Eigenvector centrality:** Eigenvector centrality computes the centrality for a node based on the centrality of its neighbors. The eigenvector centrality for node i is \(Ax\) = \(\lambda x\). where \(A\) is the adjacency matrix of the graph \(G\) with eigenvalue \(\lambda\).

We note that our approach does not depend on any specific index. However, we recommend considering indices that are computationally inexpensive for applicability to large graphs. The complexity scores of each index are normalized into [0, 1] range using L2 norm.

### Model Competency

We define model competence at each training iteration \(t\) as the fraction of training data that can be used by the model at time \(t\); we refer to this fraction by \(c(t)\). Our curriculum learning framework employs difficulty indices to select \(c(t)\) fraction of examples to train its downstream model (a GNN). We employ the following function (Platanios et al., 2019) to quantify competence:

\[c(t)=\min\left(1,\sqrt[p]{t\left(\frac{1-c_{0}^{p}}{T}\right)+c_{0}^{p}}\right), \tag{1}\]
where \(t\) is the training iteration, \(p\) controls the sharpness of the curriculum so that more time is spent on the examples added later in the training, \(T\) is the maximum curriculum length (number of iterations), and \(c_{0}\) is the initial value of the competence. \(c(t)\) gradually increases to achieve the maximum value of 1, which covers the entire training dataset. We set \(p=2\) and \(c_{0}=0.01\) as suggested in (Platanios et al., 2019).

### Prioritizing Important Difficulty Indices

Difficulty indices vary significantly in their difficulty estimates, owing to the complicated topology and indistinct patterns in graph data. Our framework strategically prioritizes key difficulty indices while training a GNN model. Specifically, the framework employs two mechanisms (see line 7 in Algorithm 1) to determine which index (i.e., top \(c(t)\) portion of training data ranked by the difficulty scores obtained from the index) should be used for training the downstream GNN model at iteration \(t\): (i) model-based and (ii) index-based approaches:

Model-based:This approach performs a forward pass on the selected portion of training data and calculates the average loss of the GNN on these examples. The index with the maximum (or minimum, depending on the curriculum) average loss will be selected at iteration \(t\) and it's top \(c(t)\) examples will be used for training the downstream GNN. Minimum average loss prioritizes easier examples over harder ones for training. On the other hand, maximum average loss prioritizes harder examples (as in an anti-curriculum setting).

Index-based:This approach uses the actual difficulty scores obtained from indices. The index with minimum (or maximum) average difficulty score across its top \(c(t)\) portion of training samples will be selected for training and calculating the error (see lines 9-14 in Algorithm 1). We note that the index-based approach is computationally inexpensive compared to the model-based approach, and results in comparable performance, see results in experiments (Tables 4)

```
input : D: Training data of size \(n\) L: Difficulty indices M: GNN Model O: easy-to-hard vs. hard-to-easy transition output : Trained model M*
1 Compute complexity scores for each index \(i\) in L and store the results in L\({}_{i}\)\(\mathrm{L}_{i}\gets sort(\mathrm{L}_{i})\)# in ascending or descending order. for\(t\gets 0\) to Tdo\(c(t)\leftarrow\) competence from Eq (1)foreach index in Ldo\(l_{i}\leftarrow\) top (\(c(t)\times n\)) examples from L\({}_{i}\)\(e_{i}\leftarrow\) average loss or complexity of \(l_{i}\)
2 end forifO = easy-to-hardthen
3\(j=\arg\min_{i}e_{i}\)
4else
5\(j=\arg\max_{i}e_{i}\)
6 end for Train M with \(l_{j}\) samples
7
8 end for
```

**Algorithm 1**Multiview Competence-based Curriculum Learning (MCCL).

### Base Graph Neural Network Model

Our approach is model agnostic and can be applied to any GNN. We use the graph-text neural network (GTNN) model4 from (Vakil and Amiri, 2022) as the base model because it is designed for text-graph data. The model integrates textual information with graph structure and directly uses text embeddings at prediction layer to avoid information loss in the iterative process of training GNNs. We use this model as a base model to compare our and baseline curriculum learning approaches on graph data.

Footnote 4: [https://github.com/CLU-UML/gtnn](https://github.com/CLU-UML/gtnn)

## 3 Experimental Results

### Datasets

Gene Phenotype Relation (PGR) (Sousa et al., 2019): PGR is created from PubMed articles and contains sentences describing causal relations between genes and phenotypes (symptoms); see Table 1 for examples of this dataset.

Gene, Disease, Phenotype Relation (GDPR) (Vakil and Amiri, 2022): GDPR contains different types of relations among genes, diseases and phenotypes, and long texts describing them.

Cora(McCallum et al., 2000): Cora is a relatively small citation network, in which nodes are scientific papers and edges are citations among them. Each paper is categorized into one of the seven subject categories and is provided with a textual feature word vector obtained from the content of the paper.

Ogbn-arxiv(Hu et al., 2020): This Open Graph Benchmark dataset is a citation network between papers in the Computer Science domain. Each node in the graph is a paper and an edge represents
a citation from one paper to another. Also, each paper contains 128 dimension embedding vector obtained by taking the average of the words present in the title and the abstract.

Table 2 shows the statistics of the above datasets. We use PGR and GDPR for link prediction and Cora and Ogbn-Arxiv for node classification.

### Baselines

**CurGraph** (Wang et al., 2021) is a curriculum learning framework for graphs that computes difficulty scores based on the intra- and inter-class distributions of embeddings and develops a smooth-step function to gradually include harder samples in training. We report the results of our implementation of this approach.

**SuperLoss** (SL) (Castells et al., 2020) is a generic curriculum learning approach that dynamically learns a curriculum from model behavior. It uses a fixed difficulty threshold at batch level, determined by the exponential moving average of all sample losses, and assigns higher weights to easier samples than harder ones.

**Trend-SL** (Vakil and Amiri, 2022) is a curriculum learning approach which extends (Castells et al., 2020) by incorporating sample-level loss trends to better discriminate easier from harder samples and schedule them for training.

### Settings

We consider 1-hop neighbors for PGR and GDPR and 2-hop neighbors for Cora and Ogbn-Arxiv to create subgraphs for computing complexity indices, see Section 2.1, and training the GTNN model, see Section 2.4. We train all models for a maximum number of \(100\) iterations for PGR and GDPR, and \(500\) iterations for Cora and Ogbn-Arxiv with model checkpoint determined by validation data for all models. We conduct all experiments using Ubuntu 18.04 on a single 40GB A100 Nvidia GPU.

We consider 26 complexity indices listed in Appendix A. Since some of the indices are highly co-related, we use k-means to group them based on the Pearson co-relations between their ranking of training samples. We categorize indices into 10 clusters through grid search, which effectively prevents any redundancy in the index space. We randomly select an index from each cluster to be used by our curriculum learning framework. Indices that are used by the framework are labeled by asterisks in Appendix A.

We report F1 score (on positive class) for PGR and GDPR datasets, and Accuracy score for Cora and Ogbn-Arxiv datasets. In addition, we use t-test for significance testing and asterisk mark (*) to indicate significant difference at \(\rho=0.01\).

### Main Results

Table 3 shows the performance of the proposed MCCL method against other curriculum learning approaches. The results shows that applying curricula to the base model (GTNN) further improves its performance by 3.3 and 1.8 absolute points in F1 on GDPR and PGR datasets respectively, indicating the importance of curriculum learning for training GNNs. The corresponding improvement on Cora and Ogbn-Arxiv datasets are 6.7 and 4.9 absolute points in accuracy.

In addition, MCCL outperforms other curriculum learning approaches. Furthermore, as MCCL increasingly introduces more training instances at each iteration, it shows an overall faster training time compared to the other curriculum learning models, which iterate through all training examples at every iteration. See Section 4.4 for detail analysis on time complexity of different models.

\begin{table}
\begin{tabular}{l c c c c} \hline \hline  & **GDPR** & **PGR** & **Cora** & **Ogbn-Arxiv** \\ \hline
**Nodes** & 18.3K & 20.4K & 2.7K & 169K \\
**Edges** & 365K & 605K & 5.4K & 1.1M \\ \hline
**Train** & 30.1K & 2.6K & 2.1K & 90K \\
**Test** & 3.7K & 155 & 271 & 49K \\
**Val** & 3.7K & – & 271 & 30K \\ \hline \hline \end{tabular}
\end{table}
Table 2: Dataset statistics.

\begin{table}
\begin{tabular}{l c c c c} \hline \hline  & \multicolumn{2}{c}{**Link Prediction**} & \multicolumn{2}{c}{**Node Classification**} \\ \hline \hline  & **GDPR** & **PGR** & **Cora** & **Ogbn-Arxiv** \\
**Model** & **F1** & **F1** & **Acc** & **Acc** \\ \hline
**GTNN** & 82.4 & 93.4 & 91.5 & 71.6 \\ \hline
**CurGraph** & 81.0 & 80.3 & 88.6 & 68.7 \\
**SL** & 84.1 & 94.5 & 90.4 & 71.8 \\
**Trend-SL** & 84.6 & 94.5 & 90.4 & 71.5 \\
**MCCL** & **85.7*** & **95.2*** & **98.2*** & **76.5*** \\ \hline \hline \end{tabular}
\end{table}
Table 3: Performance of curriculum models on **GDPR** and **PGR** datasets for link prediction, and **Cora** and **Ogbn-Arxiv** for node classification. The base model for all curriculum learning approaches is GTNN, which has a high score of F1 and Accuracy on the datasets using standard training. MCCL performs best compared to the other curricula methods. Asterisk marks (*) indicate significantly better performance compared to all other competing models.
## 4 Multiview Curricula Introspection

We perform several ablation studies on the MCCL model, investigating genuine complexity indices compared to random ordering, multiview curricula versus anti-curricula, the impact of complexity indices in training, and the model's time complexity.

### Model Prioritizes Genuine Complexity Indices over Random Ordering

In curriculum learning, effective training depends on the scheduler, which determines the set of examples and their order for training at each iteration. Hence, the performance of the model largely depends on the scheduling criteria used for training. To determine if our model can indeed prioritize better indices, we added a _fake_ index named "Random" index to the list of our complexity indices. Training examples were randomly ordered in the Random index. We re-ran our model and checked whether it selects the Random index for training at any iteration. On Cora and Ogbn-Arxiv datasets, model selects the Random index at 17.6% and 12.8% of its training iterations. On PGR, the model never selects the Random index, and on GDPR, model selects the Random index at 8% of its training iterations. Specifically, toward the end of training at iterations [39, 46, 58, 71, 76, 83, 91, 93] with the best F1-score of 85.5% obtained at iteration 76. The fact that the model do not often select the Random index at many iterations is effectively inline with the core principle of curriculum learning-learning materials should be gradually learned in a properly-planned order. This sanity check indicates that the model prioritizes genuine complexity indices over random ordering.

### Multiview Curricula vs. Anti-Curricula

We study the effect of different criteria in MCCL framework through ablation analysis on (a): the order by which training examples are sorted with respect to their complexity scores for each index (descending versus ascending, see line 2 in Algorithm 1), (b): the mechanism by which our framework prioritizes indices (model-based versus index-based, see line 7 in Algorithm 1 and Section 2.3), and (c): the type of learning transition in our framework (easy-to-hard versus hard-to-easy transition, see lines 9-13 in Algorithm 1).

Table 4 shows the result of this ablation analysis averaged over the PGR and GDPR datasets for link prediction, and Cora and Ogbn-Arxiv datasets for node classification respectively. The corresponding results for each dataset is reported in Appendix B. Overall, the ascending order results in the best average F1 score for link prediction while descending order performs better for node classification. In addition, in model-based training, hard-to-easy (max) transition order is more effective than easy-to-hard (min) transition order across both tasks. This is perhaps because harder examples are superior at helping the model find better local minima at the early stages of training. We also observe that easy-to-hard (min) transition for index-based training results in higher average F1-score than hard-to-easy (max) transition of the model-based training. This is because, in case of index-based ordering, the difficulty scores (which are obtained from indices) may provide a more accurate estimation of easiness to the model than hardness, i.e. easy examples are likely easy for the model in both ordering but this may not be true for hard examples.

\begin{table}
\begin{tabular}{l l l l} \hline \hline \multicolumn{4}{c}{**Link Prediction**} \\ \hline \hline
**Model** & \begin{tabular}{c} **Index** \\ **Order** \\ \end{tabular} & 
\begin{tabular}{c} **Transition** \\ **Order** \\ \end{tabular} & **Avg F1** \\ \hline
**GTNN** & – & – & 87.9 \\ \hline \multirow{3}{*}{**MCCL: Model-based**} & desc & max & 89.4 \\  & desc & min & 89.3 \\  & asc & max & **89.9** \\  & asc & min & 88.7 \\ \hline \multirow{3}{*}{**MCCL: Index-based**} & desc & max & 90.1 \\  & desc & min & 89.2 \\ \cline{1-1}  & asc & max & 89.3 \\ \cline{1-1}  & asc & min & **90.4** \\ \hline \hline \end{tabular}
\end{table}
Table 4: Ablation analysis on the order by which training examples are sorted for complexity indices (ascending versus descending in the Index Order column, see line 2 in Algorithm 1), the training mechanism (model- versus index-based in the Model column, see line 7 in Algorithm 1) and the type of learning transition (easy-to-hard (Min error) versus hard-to-easy (Max error) in the Transition Order column, see lines 9–13 in Algorithm 1).
### Index Contributions to Training

To study the contributions of different complexity indices in the training process, we divide training iterations into three phases and create the histograms that show the number of times that each index is chosen at different stages of training: (i) Initial, (ii) Middle, and (iii) End phases of the training.

Figures 1 shows the results for different indices chosen by the best-performing MCCL model5 for both index-based (where the criterion for selecting samples is merely based on their difficulty scores obtained from indices) and model-based (where the criterion for selecting samples is based on instantaneous loss) approaches across our four datasets. Our key observation was that MCCL mainly focused on indices that operate locally around nodes (such as density- or degree-based indices) at early stages of training and then focused on indices that operate globally at graph level (such as centrality-based indices) at later stages of training for both index-based and model-based training mechanisms. Additionally, we observed greater diversity in the sets of prioritized indices in case of the model-based training mechanism, which indicates MCCL encourages learning from diverse views of difficulty during training. This is mainly because the model-based training mechanism in MCCL allows the GNN to directly contribute in scheduling indices through its loss dynamics during training.

Footnote 5: According to the results in Tables 6 and 7 in Appendix B.

In addition, we note that on the Cora dataset the model merely focused on degree-based metrics throughout its training in case of index-based training and, used a smaller set of fundamentally-different indices in case of model-based training. On the Ogbn-Arxiv dataset, the model focuses only on the eigenvector centrality index throughout its training in case of index-based training and focuses on connectivity and centrality indices in the model-based training. Further analysis on this model behavior is the subject of our future work.

Overall, density, degree indices including degree and degree assortativity coefficient, and centrality indices including closeness centrality, group degree centrality and eigenvector centrality indices are often prioritized by the model across different mechanisms and datasets.

### MCCL Has the Lowest Time Complexity

Let \(n\) be the number of training examples and \(e\) be the maximum number of iterations for training a neural network. The total of number of forward and backward passes required to train GTNN, SL, Trend-SL is \(2\times n\times e\). In contrast, MCCL trains from only a fraction of training examples at each iteration and do not need to "see" all the training examples at each iteration. If model-based mechanism is used to prioritize important indices for training, the total number of forward and backward passes of MCCL is \(3\times\sum_{i}(n\times\frac{i}{e})\), which amounts to \(1.5\times n\times(e-1)\); note that model-based approach requires \(\sum_{i}(n\times\frac{i}{e})=\frac{n\times(e-1)}{2}\) additional forward passes to select the best index. In case of the index-based training mechanism, no additional forward pass is required, resulting in a total of \(2\times\sum_{i}(n\times\frac{i}{e})\) passes, which amounts to \(n\times(e-1)\) passes. In either case, MCCL has lower time complexity than other baselines. The turnaround time of our model ranges from 10 minutes to 2.5 hours, depending on the size of the input dataset.

## 5 Related Work

Curriculum learning (Bengio et al., 2009) aims to improve the generalizability of a model by gradually training it with easy examples followed by hard ones. Castells et al. (2020) introduced a generic loss function called SuperLoss (SL) which can be added on top of any target-task loss function to dynamically weight the training samples according to their difficulty for the model using a batch-wise threshold. Zhou et al. (2020) proposed dynamic instance hardness to determine the difficulty of an instance with running average of the hardness metric over training history.

Curriculum learning has been investigated in NLP (Elman, 1993; Sachan and Xing, 2016; Settles and Meeder, 2016; Amiri et al., 2017; Platanios et al., 2019; Amiri, 2019; Zhang et al., 2019; Lalor and Yu, 2020; Xu et al., 2020; Chu et al., 2021; Liu et al., 2021; Kreutzer et al., 2021; Agrawal and Carpuat, 2022; Maharana and Bansal, 2022). Specifically, Settles and Meeder (2016); Amiri et al. (2017) proposed spaced repetition-based curricula based on psycholinguistic theory where the training data is scheduled by increasing intervals of time between consecutive reviews of previously learned data samples. Zhang et al. (2019) investigated curriculum learning for domain adaptation in neural machine translation, where samples were grouped and ranked based on their similarity score such that more similar samples are seen earlier and more frequently during training. Platanios
Figure 1: Histogram of the different indices chosen by the best-performing MCCL model for both index-based (where samples are selected for training merely based on their difficulty scores obtained from indices) and model-based (where samples are selected based on instantaneous loss of the model) approaches across three datasets at the beginning, middle and end of training; see best models in Table 6, Appendix B. Dominance of a metric depends on the internal structure of the graph, underlying task, stage of training, and model behavior during training. (a): on GDPR, model mainly focuses on density- and degree-based indices (which operate locally around nodes) at the beginning and centrality-based indices (which operate globally at graph level) at later stages of index-based training (left three plots). In case of model-based training (right three plots), both degree- and centrality-based indices were selected throughout the training. (b): On PGR, we observed the same pattern except that locality indices such as number of local bridges were prioritized in case of model-based training. (c): On Cora, the model merely focuses on the degree-based metrics throughout its index-based training, and focuses on a mix of different indices at early stages of its model-based training and closeness centrality at the end of training. (d): On Ogbn-Arxiv, the model only focuses on eigenvector centrality metric throughout its index-based training and focuses on the local bridge and degree assortativity indices in the initial phase of the model-based training. In the middle and final phases, model-based training mainly focuses on degree based indices.
et al. (2019) proposed an approach to use competency function using rarity of words or length of a sentence for neural machine translation and inspired Liu et al. (2021) to define a curriculum based on multi-modal (text and image) data to choose which modality should be used for training. The model uses sample perplexity at batch level to select the modality for training. Linguistic features such as word rarity or length of sentence in Platanios et al. (2019) and sample perplexity in Liu et al. (2021) were used as measures of difficulty. Xu et al. (2020) designed a curriculum learning approach for NLP tasks using cross-view of training data to identify easy and hard examples and rearrange the examples during training. Other works of curriculum learning in NLP focused on machine translation and language understanding. Agrawal and Carpuat (2022) developed a framework to train non-autoregressive sequence-to-sequence model to edit text where a curriculum is designed to first perform easy-to-learn edits followed by increasing difficulty of training samples. Maharana and Bansal (2022) designed several curriculum learning approaches using teacher-student model where the teacher model calculates the difficulty of each training example using question-answering probability, variability, and out-of-distribution measures.

Curriculum learning for graph data is an emerging area of research. Chu et al. (2021) explored curriculum learning approach in the self-supervision settings where the difficulty measure evaluates the difficulty of negative samples which is calculated based in the embeddings's similarity between positive and negative examples. Wang et al. (2021) proposed a curriculum based subgraph classification approach, CurGraph, which first obtains graph-level embeddings via unsupervised GNN method and then uses neural density estimator to model embedding distributions. The difficulty scores of graphs are calculated by a predefined difficulty measure based on the inter- and intra-class distribution of sub-graph embeddings. In Vakil and Amiri (2022), we extended the SuperLoss approach developed in Castells et al. (2020) by introducing a curriculum learning framework that dynamically adjusts the difficulty of samples during training with respect to the loss trajectory. We demonstrated the effectiveness of incorporating this strategy in graph curriculum learning settings. Previous work in graph curriculum learning has employed a single criterion of difficulty in their curriculum learning framework. Our work uses multiple criteria for curriculum learning on graphs. We encourage readers to see Li et al. (2023) for a survey on graphs curriculum learning approaches.

Finally, in terms of datasets, Sousa et al. (2019) developed the PGR dataset, which we used in our experiments. They developed a transformer model to identify the relation between biomedical entities, genes and phenotypes, from scientific PubMed articles. For relation classification authors considered a pair of entities and the context from the corresponding sentence in which both entities occur.

## 6 Conclusion and Future work

We present a novel curriculum learning approach for training graph neural networks. Our approach combines well-established graph complexity indices (views) obtained from graph theory and demonstrates the effectiveness of learning from diverse difficulty views for the tasks of link prediction and node classification. Our approach improves over the state-of-the-art techniques for curriculum learning on graphs across several datasets. Ablation studies show that the model prioritizes genuine complexity indices over to random ordering, and effectively uses and learn multiview complexity indices in both curricula and anti-curricula settings, and has lower time complexity that competing models. In future, we will extend our approach to other graph processing tasks, focusing on NLP applications such as clustering and community detection, and investigate the effect of graph complexity indices in such tasks.

### Limitation

Calculating complexity indices for large-scale graphs can be computationally expensive and time consuming. Some of the complexity indices show longer turnaround time when computed for denser areas in the graphs. In addition, as we mentioned in the paper, although we made sure our framework and implementation allows adding any number of additional indices in a modular way, there might be other effective complexity indices that are not included in this investigation. Furthermore, it should be noted that the model has been exclusively tested on graphs where nodes contain textual content, which may limit its application to more general graph types. Finally, the model has not been applied to other graph-based tasks such as clustering and graph-level classification.