New Perspectives on Link Prediction Evaluation: A Taxonomy of Negative Samples

Dynamic link prediction (DLP) is a task that involves predicting missing links in a network, similar to how we predict missing words in a sentence. However, DLP is more complex because it deals with dynamic networks, where the links and nodes are constantly changing over time. In recent years, there has been a growing awareness of the importance of evaluating DLP methods properly, as traditional evaluation metrics may not accurately reflect their performance.
One challenge in evaluating DLP is that the negative events used to compare with positive events are often selected randomly, which can lead to biased results. Moreover, the distribution of prediction errors in DLP is not uniform like in conventional machine learning tasks, making it difficult to evaluate methods using visualization tools.
To address these challenges, the authors propose a new evaluation method that considers the entire list of possible events instead of just selecting a few negative ones. They also split DLP algorithms into several categories and analyze their performance on different datasets.
The authors observe that events corresponding to previously unobserved nodes/edges tend to have a higher rank than those further in the list, which aligns with our intuition that we have limited information about newly encountered entities. This observation highlights the importance of considering all possible events when evaluating DLP methods.
The article provides a comprehensive survey of DLP, demystifying complex concepts by using everyday language and engaging metaphors or analogies. By focusing on the essence of the article without oversimplifying, this summary captures the key findings and insights in an informative and accessible way.