Curriculum Learning for Graph Neural Networks: A Multiview Competence-based Approach

Nidhi Vakil, Hadi Amiri

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.

Introduction

Standard training for Graph Neural Networks (GNNs) typically utilizes stochastic gradient descent, treating every training sample with equal importance regardless of the training stage. This approach ignores the potential benefits of Curriculum Learning (CL), a strategy inspired by human education where a learner starts with simple concepts and gradually progresses to more complex material. While CL has shown promise in machine learning, its application to GNNs has been limited by a reliance on single-dimensional difficulty metrics, such as training loss.

Graphs are inherently multidimensional structures. A node that appears "easy" to classify based on its local degree might be "hard" when considering its global centrality or the density of its neighborhood. To capture this complexity, we introduce Multiview Competence-based Curriculum Learning (MCCL), a framework that leverages diverse graph structural properties to guide the training process.

The MCCL Framework

MCCL optimizes GNN training through three integrated components: graph complexity formalisms, a competence function, and a dynamic scheduling scheme.

1. Graph Complexity Formalisms (The "Views")

Rather than relying on a single metric, MCCL incorporates 26 different structural indices derived from graph theory. These include local measures like Node Degree and Subgraph Density, as well as global measures like Katz Centrality and Eigenvector Centrality. By treating these indices as multiple "views" of difficulty, the framework can better characterize the nuanced complexity of graph data.

2. Model Competence

The model's readiness to learn is governed by a competence function $c(t)$. This function determines the fraction of the training dataset the model is allowed to "see" at any given iteration $t$. Typically, $c(t)$ starts small and increases monotonically until the model is training on the full dataset, ensuring the GNN is not overwhelmed by complex samples early in the process.

3. Dynamic Scheduling

The scheduler determines which difficulty view to prioritize at each stage of training. The authors propose two primary strategies:

  • Model-based Scheduling: The scheduler performs a forward pass to identify which complexity index currently correlates best with model performance (e.g., which index produces the most informative loss distribution).
  • Index-based Scheduling: A computationally lighter approach that uses the raw complexity scores of the indices to rank and select samples.

To avoid redundancy among the 26 indices, the framework employs K-means clustering on the rankings, ensuring the scheduler selects from a diverse subset of structural perspectives.

Experimental Evaluation

The effectiveness of MCCL was evaluated across two primary tasks using four diverse datasets:

  • Link Prediction: Evaluated on PGR (Gene Phenotype Relation) and GDPR (Gene, Disease, Phenotype Relation), which involve complex causal relations extracted from biomedical literature.
  • Node Classification: Evaluated on Cora (a standard citation network) and Ogbn-arxiv (a large-scale citation network from the Open Graph Benchmark).

Key Results

MCCL consistently outperformed standard GNN training and state-of-the-art curriculum learning baselines like CurGraph and SuperLoss. Notable improvements included:

  • A 6.7 point accuracy boost on the Cora dataset.
  • A 4.9 point boost on the large-scale Ogbn-arxiv dataset.
  • A 3.3 point F1 improvement on the complex GDPR link prediction task.

Discussion and Insights

The Shift from Local to Global

Analysis of the scheduler's behavior revealed a distinct pattern: early in training, the model benefits most from "local" structural information (e.g., node degree). As the model's competence grows, the scheduler naturally shifts its focus toward "global" indices (e.g., eigenvector centrality), suggesting that GNNs must master local neighborhoods before they can effectively process global graph topology.

The "Anti-Curriculum" Phenomenon

Interestingly, in certain node classification tasks, the researchers found that an "anti-curriculum" (starting with hard examples) was more effective. This suggests that for specific architectures or data distributions, early exposure to complex samples can help the model escape poor local minima, challenging the traditional "easy-to-hard" assumption of CL.

Efficiency and Scalability

Despite the added complexity of calculating structural indices, MCCL can be more efficient than standard training. Because the competence function limits the data processed in early iterations, the total number of forward and backward passes is often reduced. While calculating 26 indices for massive graphs presents a preprocessing overhead, the "Index-based" scheduling approach remains practical for real-world applications.

Conclusion

MCCL represents a significant step forward in curriculum learning for GNNs. By moving beyond single-view difficulty metrics and embracing the structural diversity of graphs, the framework provides a robust, model-agnostic method for improving GNN performance and training efficiency. Future work will explore the application of multiview curricula to tasks such as community detection and clustering.

Summary updated

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.
BibTeX
@inproceedings{vakil2023curriculum,
  author = {Nidhi Vakil and Hadi Amiri},
  title = {{Curriculum Learning for Graph Neural Networks: A Multiview Competence-based Approach}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2023},
  url = {https://openreview.net/forum?id=nthiK5UR9z},
}
Figure