Tag Entropy: A Structure-Agnostic Curriculum Learning Framework for Graph Neural Networks

Abstract

Curriculum Learning (CL) orders training samples from easy to hard, but its application to graphs remains limited: existing methods rely on architecture-specific signals such as training loss, or on hand-crafted structural heuristics that do not transfer across datasets. Standard Graph Neural Network (GNN) training sidesteps this entirely, sampling at random and ignoring substantial informational variation across graphs. While pre-defined, generalizable difficulty scores are well established for text and images, no analogue exists for graphs. We propose Tag Entropy, a static, model-agnostic scoring function that measures graph difficulty as the normalized Shannon entropy of node attribute distributions. The same formulation applies to graphs with single discrete tags and to those with high-dimensional categorical features, with the latter handled through a lossless tuple-to-integer compression that preserves joint atom states. Combined with a root-pacing schedule that gradually introduces higher-entropy graphs, the framework requires no pretraining and no domain expertise. Across PROTEINS, MUTAG, NCI1, and OGBG-MOLHIV with GCN, GAT, and GIN backbones, Tag Entropy is competitive with or exceeds twelve baselines. The largest gains appear on architectures most sensitive to ordering: on PROTEINS, GIN improves from 74.11% to 77.86%, and on MUTAG, GAT improves from 69.47% to 73.68%.