PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Better Evaluation for Dynamic Link Prediction

Farimah Poursafaei, Shenyang Huang, Kellin Pelrine, Reihaneh Rabbany

arXiv:2207.10128v2cs.LGcs.SI

TL;DR

Dynamic link prediction lacks evaluation procedures and datasets that reliably distinguish methods and reflect recurring real-world relations. The paper introduces visualization tools, harder negative-sampling strategies, EdgeBank, and six diverse datasets; EdgeBank performs strongly because standard evaluation often uses easy negatives.

  • Problem

    Current dynamic link-prediction procedures and datasets may not properly differentiate approaches, especially when benchmarks use easy negative edges and limited domains.

  • Method

    The paper develops recurrence visualizations, historical and inductive negative sampling, the parameter-free EdgeBank memorization baseline, and six datasets from diverse domains.

  • Results

    EdgeBank is surprisingly strong across settings, while harder negative sampling changes method rankings and provides more robust evaluation.

  • Takeaways & Limitations

    Dynamic link prediction should be evaluated with varied negative edges, strong memorization baselines, and datasets spanning domains beyond social and interaction networks.

  • Takeaways & Limitations

    Negative sampling can produce the same edge as both positive and negative, especially in denser datasets such as UN Vote and UN Trade.

Abstract

from arXiv · show

Despite the prevalence of recent success in learning from static graphs, learning from time-evolving graphs remains an open challenge. In this work, we design new, more stringent evaluation procedures for link prediction specific to dynamic graphs, which reflect real-world considerations, to better compare the strengths and weaknesses of methods. First, we create two visualization techniques to understand the reoccurring patterns of edges over time and show that many edges reoccur at later time steps. Based on this observation, we propose a pure memorization baseline called EdgeBank. EdgeBank achieves surprisingly strong performance across multiple settings because easy negative edges are often used in the current evaluation setting. To evaluate against more difficult negative edges, we introduce two more challenging negative sampling strategies that improve robustness and better match real-world applications. Lastly, we introduce six new dynamic graph datasets from a diverse set of domains missing from current benchmarks, providing new challenges and opportunities for future research. Our code repository is accessible at https://github.com/fpour/DGB.git.

1 Introduction

The paper argues that current dynamic link-prediction evaluations can produce near-perfect results without properly distinguishing methods. It proposes harder negative sampling, a memorization baseline, visualization tools, and six datasets spanning additional domains.

  • Motivation: Current dynamic link-prediction benchmarks may fail to differentiate approaches despite near-perfect reported performance.The paper attributes this concern to limitations in evaluation procedures and datasets.
  • Dataset diversity: Existing benchmarks are concentrated in social and interaction networks, motivating evaluation across more diverse domains.The paper adds datasets from politics, economics, and transportation.
  • Temporal patterns: Many edges reoccur over time, but recurrence patterns vary across networks and domains.The paper introduces visualization techniques to examine these temporal patterns.
  • Negative sampling: SOTA methods lose performance and change relative ranking when evaluated with harder negative edges rather than standard sampled negatives.The proposed historical and inductive strategies select negatives using recurrence of observed edges.
  • Memorization baseline: EdgeBank stores observed edges and predicts memorized edges as positive, achieving the second-best ranking under historical negative sampling.It requires neither learning nor hyper-parameter tuning.
  • Contributions: The paper contributes historical and inductive negative sampling, EdgeBank, six datasets, and TEA and TET visualization tools.These contributions target more robust evaluation and analysis of dynamic link prediction.
  • Reproducibility: The code repository and datasets are publicly accessible.The paper provides repository and dataset links for reproducibility.

2 Related Work

Prior work studies benchmarking problems, negative sampling, and dynamic graph representation learning. This paper focuses these concerns on evaluation for dynamic link prediction.

  • Benchmarking Graph Learning Methods: Studies of graph-learning benchmarks identify inconsistent experimental settings and repeated train-test splits as evaluation issues.OGB addresses related concerns with diverse datasets and unified protocols, metrics, and data splits.
  • Dynamic link prediction: Prior dynamic-link-prediction work distinguishes static and dynamic tasks by edge insertion or deletion and studies future-link prediction in social networks.Reviews also distinguish missing-link prediction from future-link prediction.
  • Negative Sampling of Edges in Graphs: Static graph studies commonly sample negative edges randomly, while alternatives use node properties or geodesic distance.Prior work argues that negative sampling is important for graph representation learning.
  • Dynamic Graph Representation Learning: Dynamic graph research includes surveys, terminology, temporal embeddings, and models such as JODIE, DyRep, TGAT, TGN, and CAWN.The paper notes that these methods often approach perfect performance on current dynamic-link-prediction tasks, hindering comparisons.

3 Understanding Dynamic Graph Datasets

The paper characterizes dynamic graphs through dataset diversity and temporal edge-recurrence patterns, showing that datasets differ substantially in the balance, consistency, and timing of new and repeated edges.

  • Temporal Graph Datasets: The study combines seven existing benchmarks with six new dynamic graphs from under-studied domains to compare temporal patterns across datasets.The new datasets include domains such as politics, economics, and transportation.
  • Temporal Edge Appearance (TEA) Plot: TEA plots show the proportion of repeated and newly observed edges at each timestamp, while the novelty index summarizes the average ratio of new edges.Repeated edges are shown in grey and new edges in red.
  • Temporal Edge Appearance (TEA) Plot: Dynamic graphs vary widely: Social Evo. is dominated by repeated edges, whereas MOOC contains a high proportion of new edges.Flights has significantly more unique edges and more edges per timestamp than comparison datasets.
  • Temporal Edge Traffic (TET) Plot: TET plots visualize edge recurrence over time and distinguish train-only, test-only inductive, and train-test transductive edges by color.Edges are ordered by first appearance and, within timestamps, by their last occurrence.
  • Temporal Edge Traffic (TET) Plot: A high recurrence index with a low surprise index indicates consistent recurrence, making memorization more likely to succeed than when edges appear intermittently or remain unseen.The contrast between Social Evo. and UN Trade illustrates that similar TEA distributions can conceal different recurrence consistency in TET plots.

4 EdgeBank: A Baseline for Dynamic Link Prediction

EdgeBank tests how far pure memorization can perform in dynamic link prediction by storing observed edges, while contrasting long-term and recent-memory variants and clarifying its baseline role.

  • EdgeBank Design: EdgeBank stores newly observed edges in a dictionary and requires no parameters, with storage proportional to the number of dataset edges.Its memory is updated at each timestamp.
  • Prediction Rule: At test time, EdgeBank predicts an edge positive if it has appeared before and negative otherwise, correctly targeting frequently recurring edges.Errors arise for unseen edges and previously observed edges that are negative at the current time.
  • Memory Variants: EdgeBank∞ retains all observed edges and risks false positives for edges that appear once, whereas EdgeBanktw retains only edges from the recent test-length window.The two variants represent long-term and short-term memory strategies.
  • Role of the Baseline: EdgeBank is intended as a strong diagnostic baseline rather than a replacement for state-of-the-art methods, which should outperform pure memorization.It measures how far memorization alone can go on each dataset.

5 Revisiting Negative Sampling in Dynamic Graphs

Existing evaluation often samples easy negatives, allowing memorization to appear effective and limiting method differentiation. The paper proposes historical and inductive negative sampling strategies that target reoccurring edges.

  • Random Negative Sampling: Current evaluation samples negatives randomly from almost all possible node pairs, often without collision checking.This can allow the same edge to appear as both positive and negative, especially in denser datasets.
  • Random Negative Sampling: Random sampling rarely selects previously observed edges, making easy negatives common and allowing EdgeBank to perform well.The paper notes that predicting recurring edges is more practical in applications such as flight prediction.
  • Alternative Strategies: The proposed alternatives sample from previously observed edges, addressing random sampling’s failure to test recurrence patterns.The strategies are illustrated in Figure 4 and are designed to resolve the lack of reoccurring negatives.
  • Historical Negative Sampling: Historical negative sampling selects previously observed edges absent at the current timestamp to test whether models predict when edges reoccur.Its objective is to distinguish timestamp-specific recurrence from always predicting an observed edge as present.
  • Inductive Negative Sampling: Inductive negative sampling tests whether models learn recurrence patterns for edges first observed during the test phase.After such edges appear, models predict whether they will exist in later test timestamps.

6 Experiments

Experiments evaluate five state-of-the-art methods and EdgeBank across 13 datasets and multiple negative-sampling settings. Results show that rankings change substantially, while memorization dependence predicts performance losses under harder sampling.

  • Experimental Setup: Five state-of-the-art methods and EdgeBank are evaluated on 13 datasets using chronological splits and AU-ROC as the main metric.Results are averaged over five runs, with exact AU-ROC and AP values provided in the appendix.
  • Random Negative Sampling: Under standard random sampling, EdgeBank is competitive with state-of-the-art methods and outperforms them on LastFM, Enron, and UN Trade.Performance also varies substantially across datasets, and relative method rankings are inconsistent.
  • Alternative Negative Sampling: Alternative negative-sampling strategies produce clearer gaps from memorization baselines and change the ranking of methods.The figure caption contrasts these rankings with those obtained under the standard setting.
  • Historical Negative Sampling: EdgeBanktw is highly competitive under historical sampling and achieves state-of-the-art performance on UN Trade, UN Vote, Flights, Enron, and Contact.This indicates that recently observed edges contain important information for prediction in these datasets.
  • Generalization and Memorization: Models more correlated with EdgeBank∞ tend to suffer larger losses under historical and inductive sampling.CAWN and JODIE have the highest correlations and largest losses, whereas DyRep is least correlated and loses the least under historical sampling.

7 Conclusion

The paper’s broader evaluation framework combines memorization baselines, harder negative sampling, visualization tools, and datasets spanning underrepresented domains. Its supplementary material documents additional datasets, baselines, and dynamic-graph visualizations.

  • Conclusion: Figure 6 relates correlation with EdgeBank∞ to performance loss under the two harder negative-sampling settings.Lower predicted performance loss is shown on the right side of the figure.
  • Supplementary Material: The supplementary material adds information about baselines, datasets, and experimental settings.It includes descriptions of DGNN baselines and dataset construction details.
  • Baselines: The supplementary material describes implementations of JODIE, DyRep, TGAT, TGN, and CAWN as DGNN baselines.These methods use node and edge features when available, or zero vectors for unattributed networks.
  • Dataset Diversity: The added datasets extend dynamic link-prediction evaluation to domains including flights, politics, and legislative interactions.Flights represents air traffic during the COVID-19 pandemic, while parliamentary datasets represent political networks.
  • Visualization Tools: The Reddit dataset’s supplementary visualization uses TEA and TET plots with novelty, reoccurrence, and surprise indices.The figure reports these indices in parentheses, as defined in Section 3.

A.4 Discussion on Different Performance Metrics

The paper evaluates dynamic link prediction as binary classification and emphasizes threshold-independent metrics for fairer comparison. It reports AU-ROC and Average Precision rather than threshold-dependent measures.

  • Metric Choice: Dynamic link prediction is modeled as binary classification, motivating threshold-curve metrics such as AU-ROC and Average Precision.Accuracy, precision, recall, and F1 require a confidence threshold that may be ill-defined across methods.
  • Visualization Context: Figure 7 presents TEA and TET plots for Reddit, annotating novelty, reoccurrence, and surprise indices.The figure is included as supplementary information for the Reddit dataset.
  • Reported Metrics: The experiments report AU-ROC in Tables 3, 6, and 10 and Average Precision in Tables 2, 4, and 8.These metrics avoid dependence on a manually selected confidence threshold.
  • Experimental Settings: Experimental runs use fixed optimization and architecture settings, including Adam, a 0.0001 learning rate, 50 epochs, and early stopping.The reported configuration also uses dropout 0.1, two attention heads, and 100-dimensional node embeddings.
  • Experimental Settings: Baseline results are averaged over five runs, with each run taking about 24 hours on specified GPUs, while EdgeBank runs efficiently on CPU.The reported runtime varies with dataset and method.

B.1 Extended Results

The extended results report AP and AU-ROC for dynamic link prediction under random, historical, and inductive negative sampling, plus losses relative to random sampling.

  • Reported metrics: The appendix reports AP and AU-ROC under random, historical, and inductive negative sampling settings.It also reports AP and AU-ROC losses for historical and inductive sampling compared with random sampling.

B.2 More Discussion on Historical and Inductive Negative Sampling

Historical negative sampling can be implemented without random fallback, whereas inductive sampling may require random negatives early in testing. Across methods, harder sampling generally reduces performance, especially on Flights and Contact.

  • Historical negative sampling: All considered datasets provide enough historical edges for test-phase negative sampling, eliminating the need for random edges.The appendix directs readers to Table 12 for the counts of historical versus random negatives.
  • Inductive negative sampling: Inductive sampling may lack enough negatives in early test batches, requiring random edges to maintain dataset balance.Social Evo uses mostly random negatives, which corresponds to a less severe observed performance drop.
  • Performance impact: At least 10 percentage points of average performance decrease occurs when historical or inductive sampling replaces random sampling across SOTA methods.The decrease is averaged across methods and datasets in Figure 8.
  • Performance impact: Flights and Contact show more than 25 percentage points of average loss under historical or inductive sampling compared with random sampling.For Flights, the result concerns predicting whether a previously observed flight will recur.

C Broader Impact

The paper argues that diverse datasets, visualization tools, and stronger evaluation practices can broaden and strengthen dynamic graph research. It also notes potential misuse risks and the possibility of benchmark concentration.

  • Datasets: Five new datasets from less explored real-world domains are intended to enrich dynamic graph learning resources and facilitate novel model development.The stated domains include politics, transportation, and economics.
  • Tools and evaluation: TEA, TET plots, and novelty, reoccurrence, and surprise indices summarize dynamic graph dataset characteristics.These tools are presented alongside EdgeBank and the negative-sampling investigation.
  • Tools and evaluation: The negative-sampling investigation is intended to support more robust dynamic link prediction evaluation and methodological advancement.The paper presents this consequence within dynamic graph machine learning.
  • Risks: A potential negative impact is that future research may narrow its study to the datasets investigated in this work.The authors aim to update the datasets with community input to mitigate this issue.
  • Risks: Improved link prediction can be associated with negative use cases such as user profiling, although the work does not directly lead to them.The authors recommend awareness and appropriate precautions.

D Limitations

The work is limited by its temporal split, transductive-only evaluation, task scope, and reliance on maintained benchmark resources. These boundaries constrain how broadly its evaluation procedures and baseline apply.

  • Evaluation setup: The evaluation uses a single split between past and future links rather than alternatives with more temporal points or exact edge-time prediction.The authors identify richer temporal evaluation as potentially more relevant.
  • Evaluation scope: The study considers only the transductive setting, and EdgeBank plus historical negative sampling are restricted to that setting.All nodes are seen during training in the evaluated setup.
  • Task scope: The work studies dynamic link prediction only and leaves analogous investigation of dynamic node classification for future work.This is stated as an additional limitation beyond the two main limitations.
  • Benchmark maintenance: The benchmark repositories require regular updates as additional datasets and benchmarks become available.The paper describes ongoing maintenance as part of providing an accessible benchmark.
Loading 2207.10128v2…