New Perspectives on the Evaluation of Link Prediction Algorithms for Dynamic Graphs

• URL: http://arxiv.org/abs/2311.18486v1
• Date: Thu, 30 Nov 2023 11:57:07 GMT
• Title: New Perspectives on the Evaluation of Link Prediction Algorithms for Dynamic Graphs
• Authors: Rapha\"el Romero, Tijl De Bie, Jefrey Lijffijt
• Abstract summary: We introduce novel visualization methods that can yield insight into prediction performance and the dynamics of temporal networks. We validate empirically, on datasets extracted from recent benchmarks, that the error is typically not evenly distributed across different data segments.
• Score: 12.987894327817159
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• From Link Prediction to Forecasting: Information Loss in Batch-based Temporal Graph Learning [0.716879432974126]
  We show that the suitability of common batch-oriented evaluation depends on the datasets' characteristics. We reformulate dynamic link prediction as a link forecasting task that better accounts for temporal information present in the data.
  arXiv  Detail & Related papers  (2024-06-07T12:45:12Z)
• Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms [14.82820088479196]
  Dynamic Link Prediction (DLP) addresses the prediction of future links in evolving networks. In this work, we contribute tools to perform such a comprehensive evaluation. We describe an exhaustive taxonomy of negative sampling methods that can be used at evaluation time.
  arXiv  Detail & Related papers  (2024-05-27T14:03:28Z)
• Temporal graph models fail to capture global temporal dynamics [0.43512163406552007]
  We propose a trivial optimization-free baseline of "recently popular nodes" We show how standard negative sampling evaluation can be unsuitable for datasets with strong temporal dynamics. Our results indicate that temporal graph network architectures need deep rethinking for usage in problems with significant global dynamics.
  arXiv  Detail & Related papers  (2023-09-27T15:36:45Z)
• Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking [66.83273589348758]
  Link prediction attempts to predict whether an unseen edge exists based on only a portion of edges of a graph. A flurry of methods have been introduced in recent years that attempt to make use of graph neural networks (GNNs) for this task. New and diverse datasets have also been created to better evaluate the effectiveness of these new models.
  arXiv  Detail & Related papers  (2023-06-18T01:58:59Z)
• Energy-based Out-of-Distribution Detection for Graph Neural Networks [76.0242218180483]
  We propose a simple, powerful and efficient OOD detection model for GNN-based learning on graphs, which we call GNNSafe. GNNSafe achieves up to $17.0%$ AUROC improvement over state-of-the-arts and it could serve as simple yet strong baselines in such an under-developed area.
  arXiv  Detail & Related papers  (2023-02-06T16:38:43Z)
• A Closer Look at Debiased Temporal Sentence Grounding in Videos: Dataset, Metric, and Approach [53.727460222955266]
  Temporal Sentence Grounding in Videos (TSGV) aims to ground a natural language sentence in an untrimmed video. Recent studies have found that current benchmark datasets may have obvious moment annotation biases. We introduce a new evaluation metric "dR@n,IoU@m" that discounts the basic recall scores to alleviate the inflating evaluation caused by biased datasets.
  arXiv  Detail & Related papers  (2022-03-10T08:58:18Z)
• Comparing Test Sets with Item Response Theory [53.755064720563]
  We evaluate 29 datasets using predictions from 18 pretrained Transformer models on individual test examples. We find that Quoref, HellaSwag, and MC-TACO are best suited for distinguishing among state-of-the-art models. We also observe span selection task format, which is used for QA datasets like QAMR or SQuAD2.0, is effective in differentiating between strong and weak models.
  arXiv  Detail & Related papers  (2021-06-01T22:33:53Z)
• Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress? [84.43405961569256]
  We shed light on the state-of-the-art of network embedding methods for link prediction. We show, using a consistent evaluation pipeline, that only thin progress has been made over the last years. We argue that standardized evaluation tools can repair this situation and boost future progress in this field.
  arXiv  Detail & Related papers  (2020-02-25T16:59:09Z)
• A Multi-Channel Neural Graphical Event Model with Negative Evidence [76.51278722190607]
  Event datasets are sequences of events of various types occurring irregularly over the time-line. We propose a non-parametric deep neural network approach in order to estimate the underlying intensity functions.
  arXiv  Detail & Related papers  (2020-02-21T23:10:50Z)
• A clustering approach to time series forecasting using neural networks: A comparative study on distance-based vs. feature-based clustering methods [1.256413718364189]
  We propose various neural network architectures to forecast the time series data using the dynamic measurements. We also investigate the importance of performing techniques such as anomaly detection and clustering on forecasting accuracy. Our results indicate that clustering can improve the overall prediction time as well as improve the forecasting performance of the neural network.
  arXiv  Detail & Related papers  (2020-01-27T00:31:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.