Study Reveals Mini-Batch Class Composition Bias in Link Prediction

Graph Neural Networks Face Hidden Bias Challenge in Link Prediction

A latest preprint paper (arXiv:2604.25978) has revealed a surprising finding: in link prediction tasks for Graph Neural Networks (GNNs), the popular mini-batch training strategy introduces systematic class composition bias, which can severely compromise the quality of learned node representations.

Previous research has demonstrated that GNNs can learn transferable representations across graphs in node classification tasks, provided the underlying graphs share common structural properties. Following this intuition, GNNs trained for link prediction on the same fixed graph should learn representations consistent with those from node classification. However, the researchers found that this intuition does not hold in general.

Core Finding: Mini-Batch Sampling Induces Representation Bias

The paper's core contribution lies in uncovering a previously overlooked issue — Mini-Batch Class Composition Bias. During link prediction training, models must distinguish between "positive samples" (existing edges) and "negative samples" (non-existing edges). Due to the inherent characteristics of mini-batch sampling strategies, the class composition ratio of positive and negative samples within each batch is not uniformly distributed. This non-uniformity causes GNNs to learn node representations that deviate from expectations during optimization.

Specifically, popular link prediction models trained with mini-batches systematically alter the local graph structure "seen" by the model through neighborhood sampling and edge sampling within batches. This means that the objective function being optimized has an implicit bias compared to the ideal objective over the full graph — a bias that does not manifest in the same way during node classification tasks.

Technical Analysis: Why Intuition Fails

From a technical perspective, although both node classification and link prediction rely on GNNs to generate node embeddings, their training signals differ fundamentally. In node classification, the supervisory signal acts directly on individual nodes, and mini-batch sampling primarily affects computational efficiency rather than optimization direction. However, in link prediction, the supervisory signal acts on node pairs, and negative sampling strategies along with batch construction methods directly influence the model's understanding of the core question: "which node pairs should be similar or dissimilar."

When the class distribution of negative samples in a mini-batch does not match the true distribution of the full graph, the model may over-discriminate certain node pairs while under-discriminating others. This bias accumulates throughout training, ultimately causing the learned representations to diverge significantly from the optimal representations based on full-graph information.

The researchers validated this theoretical analysis through experiments, demonstrating that across multiple benchmark datasets, different mini-batch construction strategies indeed produce node representations of varying quality, with some strategies yielding representation quality far below expectations.

Implications and Outlook for the GNN Community

This research carries significant practical implications for the graph learning community. Currently, a large volume of link prediction work directly adopts standard mini-batch training pipelines with little attention to the potential impact of batch construction strategies on model representations. The paper's findings remind researchers and engineers to more carefully consider the following aspects when designing link prediction systems:

• Negative sampling strategy selection: Different negative sampling approaches alter the class composition within batches, thereby affecting the final representations
• Batch size configuration: Smaller batches may amplify the effects of composition bias
• Evaluation methodology improvement: New evaluation metrics capable of detecting such biases need to be developed

As GNNs are widely deployed in social network recommendations, knowledge graph completion, drug-molecule interaction prediction, and other domains, the training quality of link prediction directly impacts downstream task performance. This research provides a new theoretical perspective for improving GNN training methods and lays the groundwork for developing more robust link prediction training strategies. Going forward, how to eliminate mini-batch bias while maintaining training efficiency will become an important research direction in the graph learning field.