# Mini-Batch Class Composition Bias in Link Prediction

arXiv: https://arxiv.org/abs/2604.25978 · HTML: https://mlsanity.com/paper/2604.25978/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 15 references that are in the map.
- First posted on arXiv 28 Apr 2026.

## Builds on (most cited first, 7 of 7)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [Neural Common Neighbor with Completion for Link Prediction](https://mlsanity.com/paper/2302.00890/) (2023)
- [Fully-inductive Node Classification on Arbitrary Graphs](https://mlsanity.com/paper/2405.20445/) (2024)
- [Quantifying the Alignment of Graph and Features in Deep Learning](https://mlsanity.com/paper/1905.12921/) (2019)

## Abstract (arXiv)

Prior work on node classification has shown that Graph Neural Networks (GNNs) can learn representations that transfer across graphs, when underlying graph properties are shared. For a fixed graph, one would then expect GNNs trained for link prediction to learn a representation consistent with that learnt for node classification. We show this intuition does not hold in the general case. Instead, we find popular link prediction models can learn a trivial mini-batch dependent heuristic, enabled by batch-normalisation layers, to solve the edge classification task. When correcting for this, we observe increased alignment of the network representation with node-class relevant features, suggesting the network has learnt a graph representation that better aligns with the underlying graph's properties. Our findings suggest that standard link prediction training may be leading us to overestimate link predictors' ability to learn a generalised representation of a graph that is consistent across tasks.