Why Your Link Predictions Could Be Flawed: The β-Sampling Bias That Changes Everything

A new paper titled "Rethinking Sampling Strategy in Link Prediction" (arXiv:2606.19775) by Yilin Bi, Zhenyu Deng, Xinshan Jiao, and Tao Zhou challenges conventional wisdom in network science. The authors introduce β-sampling, where the probability of selecting a link for training or validation is proportional to the product of the degrees of its two endpoints raised to the power of β. This controlled sampling allows researchers to systematically investigate how the structural characteristics of missing links (simulated via different probe sets) affect prediction accuracy. Testing on 45 real-world networks, they found that missing links connecting high-degree nodes are substantially easier to predict, while links between low-degree nodes pose greater challenges. This suggests that many standard link prediction benchmarks may be inadvertently biased toward easier predictions.

Even more striking, the study demonstrates that the second-stage sampling—how the remaining links are split into validation and effective training sets—has a significant impact on final accuracy. The optimal second-stage strategy is neither random sampling (uniformly selecting validation links) nor consistent sampling (matching the probe set's degree distribution). Instead, the best approach depends on the network's topology and the prediction algorithm used. These findings have practical implications: researchers must carefully design their data splits to avoid misleadingly optimistic or pessimistic performance estimates. The work opens the door to more rigorous evaluation protocols for link prediction, benefiting applications from social network analysis to biological interaction prediction and fraud detection.