Mini-Batch Class Composition Bias in Link Prediction

A new paper by Kieran Maguire and Srinandan Dasmahapatra, accepted at the GCLR 2026 workshop (co-located with AAAI 2026), exposes a critical flaw in how Graph Neural Networks (GNNs) are trained for link prediction. The researchers show that popular link prediction models do not learn a generalized representation of graph structure as previously assumed. Instead, these models exploit a trivial heuristic based on mini-batch class composition, enabled by batch-normalization layers, to solve the edge classification task. This shortcut allows models to achieve high performance on standard benchmarks without truly understanding the underlying graph properties, meaning their reported accuracy may be artificially inflated.

The implications are significant for the machine learning community. By correcting for this mini-batch class composition bias, the authors observed increased alignment of network representations with node-class relevant features, suggesting the model learns a graph representation that better reflects the actual graph's properties. This finding challenges the prevailing intuition that GNNs trained for link prediction and node classification learn consistent representations. The work indicates that current training regimes may lead researchers to overestimate link predictors' ability to generalize across tasks and graphs. For practitioners building recommendation systems, drug discovery pipelines, or social network analysis tools, this means performance metrics from standard link prediction training should be viewed with caution until the bias is addressed.