Reevaluating Link Prediction and New Approaches and Best Practices

Link prediction (LP) is a crucial problem in network science and machine learning. However, existing evaluation methods often adopt a standardized approach, overlooking key factors that influence LP performance across different applications. In this study, we identify several important factors, including network type, problem type, geodesic distance between end nodes and its class distribution, the applicability of LP methods, class imbalance and its impact on early retrieval, and evaluation metrics. To address these challenges, we propose a rigorous experimental framework that accounts for these factors, ensuring a more controlled and comprehensive evaluation of LP methods. We conduct extensive experiments on real-world network datasets to analyze the interactions between these factors and LP performance. By testing a series of carefully designed hypotheses, we uncover valuable insights into how these elements influence LP outcomes. Based on our findings, we provide a set of best practices for evaluating LP methods, ensuring more reliable and meaningful comparisons. Our study highlights the need for a nuanced evaluation approach that goes beyond conventional setups, ultimately improving the robustness and applicability of LP techniques across diverse domains.