New Perspectives on the Evaluation of Link Prediction Algorithms for Dynamic Graphs
This work addresses evaluation challenges for researchers in dynamic network analysis, but it is incremental as it builds on existing benchmarks and methods.
The paper tackles the problem of evaluating link prediction algorithms for dynamic graphs by highlighting how performance depends on negative sampling and varies over time, introducing novel visualization methods to analyze these effects and showing that errors are unevenly distributed across data segments.
There is a fast-growing body of research on predicting future links in dynamic networks, with many new algorithms. Some benchmark data exists, and performance evaluations commonly rely on comparing the scores of observed network events (positives) with those of randomly generated ones (negatives). These evaluation measures depend on both the predictive ability of the model and, crucially, the type of negative samples used. Besides, as generally the case with temporal data, prediction quality may vary over time. This creates a complex evaluation space. In this work, we catalog the possibilities for negative sampling and introduce novel visualization methods that can yield insight into prediction performance and the dynamics of temporal networks. We leverage these visualization tools to investigate the effect of negative sampling on the predictive performance, at the node and edge level. We validate empirically, on datasets extracted from recent benchmarks that the error is typically not evenly distributed across different data segments. Finally, we argue that such visualization tools can serve as powerful guides to evaluate dynamic link prediction methods at different levels.