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

Training Graph Neural Networks (GNNs) is typically a "sink or swim" affair where the model is exposed to all data simultaneously, regardless of structural complexity. This paper introduces MCCL (Multiview Competence-based Curriculum Learning), a framework that strategically schedules training examples by evaluating "difficulty" through 26 different lenses of graph theory. By starting with simpler structures and gradually increasing complexity as the model's competence grows, MCCL achieves significant performance gains in link prediction and node classification while reducing overall training time.

Methods and Framework

The core of the MCCL framework consists of three main components designed to mimic human education patterns:

  1. Graph Complexity Formalisms: Rather than relying on a single metric, the authors use 26 different indices from graph theory to measure difficulty. These range from local metrics, such as Node Degree, to global metrics like Katz Centrality or Eigenvector Centrality.
  2. Model Competence: A mathematical function $c(t)$ calculates the fraction of the training data the model is "ready" to handle at any given iteration $t$. This fraction grows from a small seed (e.g., 1%) to 100% as training progresses.
  3. The Scheduler: This component acts as the "teacher," deciding which difficulty view to prioritize at each step. It can operate in a model-based mode (choosing indices based on loss) or an index-based mode (using raw complexity scores).
Figure 1: A low-complexity subgraph (G1) representing the "easy" examples prioritized during the early stages of the curriculum.

Key Results and Insights

MCCL was evaluated on four real-world datasets, including PGR and GDPR (link prediction) and Cora and Ogbn-arxiv (node classification). The framework consistently outperformed state-of-the-art curriculum learning baselines:

  • Performance Gains: MCCL achieved a 3.3 point F1 increase on GDPR and a 6.7 point accuracy jump on the Cora citation network.
  • The "Local-to-Global" Shift: A fascinating finding was that the model naturally prioritizes different information types over time. Early in training, the scheduler favors indices that operate locally (like node degree). As competence grows, it shifts toward global indices (like centrality).
  • Efficiency: Because the model only processes a fraction of the data in early stages, MCCL reduces total training time compared to standard GNN training paradigms.

Conclusion

MCCL advances GNN training by incorporating a fine-grained spectrum of graph difficulty criteria. While calculating 26 indices can be computationally expensive for massive graphs, the resulting improvements in accuracy and training efficiency suggest that multiview curriculum learning is a powerful tool for complex graph-based tasks. Future work will explore these curricula in graph-level classification and unsupervised learning contexts.

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