Do Graph Neural Networks Follow Power Laws?

Abstract

Learning curves describe how model performance changes as more labeled data becomes available and can help estimate whether collecting additional labels is worthwhile. However, it remains unclear which mathematical functions best represent and extrapolate learning curves for graph neural networks. This study compares power-law and exponential models for learning curves generated by a graph neural network on node-classification datasets with different graph characteristics. The models are evaluated separately on how well they describe observed performance and how accurately they predict performance at larger, unseen labeling budgets. The results show that neither model family is universally preferable. Exponential models provide better descriptive fit on some datasets, while power-law models provide better descriptive fit on others. In the extrapolation experiments, power-law models often give more accurate predictions at larger labeled-node budgets, although the preferred model still depends on the dataset and fitting range. These findings indicate that descriptive fit and extrapolation accuracy should be treated as separate objectives. Overall, power-law behaviour appears to be a useful modelling assumption for some GNN learning curves, especially for extrapolation, but it should not be assumed to hold universally.