From Link Prediction to Forecasting: Information Loss in Batch-based Temporal Graph Learning

Authors: Moritz Lampert, Christopher Blöcker, Ingo Scholtes
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Network, GNN, Temporal Graph, Dynamic Link Prediction, Dynamic Graph, Temporal Graph Learning, Dynamic Graph Learning, Temporal Graph Neural Network, TGNN, DyGNN, Dynamic Graph Neural Network

Abstract:
Dynamic link prediction is an important problem considered by many recent works
proposing various approaches for learning temporal edge patterns. To assess their
efficacy, models are evaluated on publicly available benchmark datasets involving
continuous-time and discrete-time temporal graphs. However, as we show in this
work, the suitability of common batch-oriented evaluation depends on the datasets’
characteristics, which can cause multiple issues: For continuous-time temporal
graphs, fixed-size batches create time windows with different durations, resulting in
an inconsistent dynamic link prediction task. For discrete-time temporal graphs, the
sequence of batches can additionally introduce temporal dependencies that are not
present in the data. In this work, we empirically show that this common evaluation
approach leads to skewed model performance and hinders the fair comparison of
methods. We mitigate this problem by reformulating dynamic link prediction as a
link forecasting task that better accounts for temporal information present in the
data. We provide implementations of our new evaluation method for commonly
used graph learning frameworks.

Decision: reject
Reviewer scores: 6, 5, 6, 5

Reviews and discussion:
<thread>
creation date:
1730496412861

thread_type:
official_review

<thread_object>
creator: reviewer_sddg

<content>
summary:
This work tackles the issue of information loss and leakage in the batch-oriented evaluation protocol for temporal graph learning. It first validates the existence of such loss and leakage through experiments that compute the NMI between batches and timestamps. To address this, the authors propose a new evaluation protocol for link forecasting and re-evaluate numerous existing methods within this framework. The provided code in the supplementary material appears comprehensive and sufficient.

strengths:
The paper presents a study that provides a novel perspective on the internal issues with the batch-oriented evaluation protocol. The overall presentation is clear, and it includes adequate background information. The experiments related to the new evaluation protocol are relatively comprehensive, with re-evaluation of numerous existing methods. However, there are some missing aspects (as noted in the identified weaknesses) that should be addressed.

weaknesses:
W1. Figure 2 and Figure 3 offer trivial or intuitive results, which seem to be redundant in the main text. I would suggest to just put part of them in the main text and the remaining in the appendix. Otherwise, these two figures would attract too much attention from the readers and make them lost before reading your point (Figure 4).

W2. The NMI may not be a trivial concept for common readers, therefore it would be helpful to include some technical details of it in the appendix and link to it at line 263. The current presentation of this paragraph is quite confusing as I cannot understand what lines 266-268 mean (how the NMI was computed). Maybe some formulation would help improve the clarification here.

W3. While the issue with the batch-oriented evaluation protocol is effectively identified using NMI, the paper does not adequately explain how this impacts previous evaluations and benchmarks that use this protocol. For instance, could you provide experimental validation to demonstrate the biases or flaws in past evaluations? The experiments in the current manuscript are associated with the new link forecasting protocol. Still, I am confused about how to experimentally validate that this protocol is better than the previous ones. 

W4. One advantage of the batch-oriented evaluation is the efficiency, but there seems to be no comparison or comment regarding the training/evaluation efficiency of the link forecasting protocol. I am aware of line 393, Computational cost, but I think such a not in-depth analysis is not enough. Some experimental results could be included.

W5. This is a relatively minor point, as is included in the limitation. For the frameworks that consider the temporal link prediction problem as a ranking task, is it possible to have more discussions about the pros/cons of time-window-based approaches and ranking approaches?

Minor: 
1. line 143, should be {$t_{b\cdot i}\, ..., t_{b\cdot (i+1)-1}$}? Also, line 244 seems to have the same mistake.
2. line 146, 147. if there is no constraint on (u,v), then it's possible that (u,v) is not in the B+ or B- batch. Is something like $(u, v) \in B^+ \cup B^-$ missing? I think similar issue exists for you link forecasting definition, line 379.
3. line 346. "negative edges that do not occur in time window [i · h,(i + 1) · h)". I feel it ambiguous. is those negative edges not in this time window, or in this time window but do not occur (interact)? Should be the latter?
4. Actually it could be an independent section for related work. I would recommend commenting on how existing TGNN benchmarks flow to validate that the widely-used batch-oriented training/evaluation does have issues that this work is trying to fix.
5. The code implementation largely builds upon an existing framework, DyGLib, and it would be helpful to include comments or documentation clarifying where the extensions and modifications occur at the code level (code snippets) in the appendix.

questions:
I currently lean towards a rejection of the manuscript but am very open to further discussion and increasing the based on how well my concerns get addressed. I encourage the authors to refer to the identified weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730604686299

thread_type:
official_review

<thread_object>
creator: reviewer_bi4c

<content>
summary:
This work introduces a reformulation of the dynamic link prediction (DLP) task as link forecasting (LF). LF differs from DLP in that LF ensures that each batch corresponds to a fixed time resolution. This small change to the problem statement yields relatively significant changes to the observed accuracies of these models on benchmark datasets.

strengths:
1. The problem with variable-time batch construction for DLP is made quite clear in section 3. The examples are easy to understand
2. The experiments in section 4 are nearly exhaustive. The models cover the big TGNNs out there, and the datasets cover many of the major datasets out there.
3. The problem statement is clearly articulated and easy to understand. I had no problem implementing the discrete time version of the data loader in an afternoon of work. This clarity is commendable.

weaknesses:
1. While the problem with DLP seems clear, it is hard for me to see why this requires the definition of a new task given that it's a straightforward modification of an existing one. I would recommend that the authors expand on this in the work to further draw the distinction, _or_ to assert that this is the way that DLP should be done in the future.
3. It appears that the models were not hyperparameter tuned for this new task. It stands to reason that because the new involves training on potentially quite different batch structures than the batches those hyperparameters were tuned for, that the reported model performance might be an underestimate. I would suggest that the authors investigate the hyperparameter sensitivity of the models training using LF.
4. The experimental details are a bit hard to follow in section 4. It appears that what was done is the authors trained a model using the horizon-based strategy, and then used this model to evaluate on both the horizon and batch based evaluation strategies. They then reported the performance differences. I would ask that the authors clarify these experimental details.

questions:
1. It's unclear to me what the authors mean when they assert that DLP yields different amounts of information loss for different models. It seems to me that, if the batch size is fixed across all models, then it seems to me that the information loss (or really, the inter-batch leakage) will be equivalent. In what ways are they not? Or is the assertion that because batch size is often treated as a (often implicit) hyperparameter, so model comparisons can be implicitly unfair?
2. Does LF suffer from the same temporal training-leakage that DLP does when h is larger than infinitesimal?
3. Which is more significant? Batches containing variable time gaps, or the identified temporal leakage?
4. The primary motivation to use larger batch sizes is the reduction of wallclock time during training. How does the training time for LF scale as a function of h?
5. How do the results reported in table 2/3 change if the model was trained using a DLP pipeline and then evaluated on both DLP/LF?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730617050125

thread_type:
official_review

<thread_object>
creator: reviewer_p4ga

<content>
summary:
In this paper, the authors considered the evaluation of dynamic link prediction on both discrete-time dynamic graphs (DTDGs) and continuous-time dynamic graphs (CTDGs). They first provided a series of empirical analysis results to demonstrate the limitations of existing batch-based evaluation strategies. A novel time-window-based approach was further proposed to address these limitations. The authors have also validated the effectiveness of the proposed evaluation approach on various public DTDGs and CTDGs datasets.

strengths:
**S1**. The authors have conducted a great amount of experiments to illustrate the limitations of existing techniques as well as the effectiveness of the proposed method.

**S2**. The limitations of the evaluation of dynamic link prediction are significant but seldom considered and addressed in most existing studies.

weaknesses:
**W1**. Some statements regarding the research gaps of existing techniques and motivations of this paper are weak, unclear, or confusing.

  According to my understanding, this study focuses on the evaluation of dynamic link prediction. However, the title of this paper uses the terminology 'temporal graph learning', which may not be consistent with the major topic of this study. From my perspective, learning may also include the training procedure (e.g., training algorithms, training losses, etc.), addition to evaluation of the inference procedure.
  
  The author claimed that 'within each batch, edges are typically treated as if they occurred simultaneously, thus discarding temporal information within a batch'. To some extent, I do not agree with this statement. According to my understanding, nodes or edges in most TGNNs are encoded as embeddings (i.e., low-dimensional vector representations), which usually involves the **temporal encodings**. In this sense, the temporal information has not been discarded. It is recommended to give some more toy examples about why and how is the temporal information discarded, especially for the case with temporal encodings.
  
  I also respectfully disagree with the definition of dynamic link prediction in Section 2, which was claimed to 'predict whether $(u, v) \in B_i^+$ or $B_i^-$ in terms of batches $B_i^+$ and $B_i^-$. According to my understanding, a dynamic link prediction model should be able to predict all the possible edges at a specific timestamp but not within a batch.
  
  The authors claimed that existing techniques may hinder the fair comparison of methods. However, it is unclear for me how to define and measure the fairness of comparison. A formal definition regarding this point is also recommended.

  From my perspective, using 'temporal link prediction' and 'temporal link forecasting' as two terminologies with different definitions may not be a good presentation, which may result in potential ambiguity issues, since they are more likely to be synonyms in natural languages. It is recommended to use a clearer terminology to replace 'dynamic link forecasting' (e.g., batch-based and window-based evaluation) that can help better distinguish between 'temporal link prediction' and 'temporal link forecasting'.

***

**W2**. There seems to be some flaws for the proposed evaluation approach.

  In Section 3.2, the authors discussed one possible limitation that the proposed approach 'cannot preclude memory overflows entirely'. A possible solution was then discussed, which 'splits large time windows into smaller batches for GPU-based gradient computation'. In this sense, the proposed method still used the old bath-based technique, which may still 'ignore the temporal information within each batch', as claimed at the very beginning of this paper.
  
  According to my understanding, the proposed method may also suffer from the empty window issue, where there are no edges in a 'pre-defined' window, due to the heterogeneous distribution of temporal edges. However, there are no discussions regarding this limitation and possible solutions.

***

**W3**. Some details of experiments need further clarification. Some additional experiments are also recommended.

  In the empirical analysis of this paper, NMI is a significant metric to 'measure the temporal information that is retained after dividing edges into batches'. However, the formal definition regarding how to compute such a measurement is not given. As a result, it is still hard for me to understand the physical meaning of NMI using in the empirical analysis.
  
  According to my understanding, the proposed time-window-based approach introduces another hyper-parameter $h$. However, there seems no parameter analysis regarding different settings of $h$ (like the empirical analysis shown in Fig. 3).


***

**W4**. Although the authors have provided a great amount of empirical results to demonstrate the limitations of existing techniques and validate the effectiveness of the proposed approach, it is better to provide some theoretical guarantees w.r.t. the evaluation of dynamic link prediction.

questions:
See **W1**-**W4**.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730642638905

thread_type:
official_review

<thread_object>
creator: reviewer_m8vp

<content>
summary:
This paper highlights an overlooked issue in the evaluation of dynamic link prediction task: fixed batch-size evaluation alters the task properties, as for continuous-time temporal graphs, leading to inconsistent duration evaluations across batches; for discrete-time temporal graphs, leading to possible data leakage due to additional introduced temporal dependencies

To explore this issue in depth, the paper first defines a quantitative metric, NMI, to measure information loss, and conducts extensive empirical analysis to demonstrate how fixed batch sizes distort the task setting. It then formulates a fairer setting, *link forecasting*, enabling consistent time durations for each evaluation batch. Finally, the authors reproduce experiments on existing methods within this reformulated task to reveal their true performance.

strengths:
*S1* This paper addresses an important yet overlooked issue in temporal link prediction task, i.e., fixed batch size evaluation can distort the task itself by losing or introducing extra information.

*S2* The authors provide extensive data illustrations and quantitative results to facilitate understanding, demonstrating that each dataset has a distinct interaction distribution and how fixed batch-size evaluation can alter the task characteristics.

*S3* This paper formulates a new task setting, *link forecasting*, and offers implementation and reproduction of existing methods to provide valuable insights.

weaknesses:
I appreciate the issue raised in this paper and the extensive empirical analysis that clarify the motivation behind the study. However, for the experiments on existing methods within the formulated link forecasting task, I think further discussion is required, e.g., **the reasons for performance changes across diverse settings can be addressed.**

 The authors explain why memory-based methods tend to experience performance degradation on discrete-time graphs, which is appreciated. However, it would be beneficial to discuss why other methods might improve in this setting. Additionally, the performance trends for continuous-time graphs appear mixed, potentially due to specific dataset characteristics. I think a more in-depth discussion on these points would enhance the paper.

questions:
Please refer to the "Weaknesses" section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732372202968

thread_type:
official_comment

<thread_object>
creator: area_chair_rk1f

<content>
comment:
Dear Reviewers,

The authors have uploaded their rebuttal. Please take this opportunity to discuss any concerns you may have with the authors.

AC
</content>
</thread_object>

</thread>
<thread>
creation date:
1733301523207

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank all reviewers for the constructive discussions and their helpful suggestions. We are happy to see that you think that the "overall presentation is clear" with "clarity [that] is commendable" and unanimously agree that the soundness of our paper is good. We further appreciate that the reviewers agree that our paper "addresses an important yet overlooked issue" and contains "a great amount of experiments to illustrate the limitations of existing techniques as well as the effectiveness of the proposed method". 

Furthermore, we are glad that we were able to **clear up most concerns and, especially, all concerns of the reviewers m8vp, Bi4c, and sDdG**. Specifically, we improved our explanations for the performance changes due to the comments made by reviewer m8vp. Thanks to suggestions made by reviewer sDdG, we were able to provide additional empirical evidence that support our explanations of the performance changes as well as our claims about the prediction task being skewed and unfair. Thanks to reviewer sDdG, a runtime evaluation showing comparable results for our method and the batch-based approach supporting our claims about computational cost in our manuscript will be added in the camera-ready version. We were also able to correct typos and improve the general formulations in our manuscript to avoid potential misunderstandings thanks to the comments of the reviewers. Following the suggestion made by reviewers P4Ga and sDdG, we added an additional appendix that explains the NMI measure in more detail and agree with Reviewer sDdG who thinks "it is pretty clear now". However, we are happy to follow reviewer P4Ga's suggestion and will provide examples that use our notations that will help with the understanding in the camera-ready version.

Next, we provide further clarifications about the unresolved concerns of reviewer P4Ga about the time horizon $h$:

We agree that the horizon $h$ is a parameter that can be changed. We further agree that there might not be a distinct value that makes sense for all forecasting tasks (e.g. forecasting links on Reddit, as mentioned by reviewer P4Ga). However, in contrast to the batch size - a **hyperparameter that is typically tuned for best performance** - the **horizon $h$ is a parameter that defines the task and cannot be tuned**.

Additionally, while it might make sense to calculate a deterministic unique value for some tasks based on the dataset's characteristics as reviewer P4ga proposes, there are also many cases where the **time horizon of the task is very different from the optimal time horizon based on the datasets characteristics**. A temporal network of train connections, for example, might have an optimal horizon $h=24h$ since most trains follow a daily schedule. Instead of learning the fixed schedule, the task for the forecasting model could be to learn unforeseen deviations from the schedule to react accordingly, e.g. by rerouting trains. As such, the forecasting horizon $h$ should be based on the minimum reaction time that is needed to make, e.g. the rerouting of a train possible, but at the same time as short as possible to give the model access to the most up-to-date information, e.g. $h=60min$ instead of $24h$ as suggested by the data. 

Thus, while the separate problem of **finding an optimal time horizon with theoretical guarantees** is related and can help for some link forecasting tasks where no specific time horizon is required, it is **out of scope for our work**. For further insights into this separate problem, we kindly refer to papers addressing this separate problem:

Clauset, A. & Eagle, N. Persistence and periodicity in a dynamic proximity network. in Proceedings of the DIMACS Workshop on Computational Methods for Dynamic Interaction Networks (2007).

Darst, R. K. et al. Detection of timescales in evolving complex systems. Sci Rep 6, 39713 (2016).

Petrović, L. V. et al. Higher-Order Patterns Reveal Causal Timescales of Complex Systems. Preprint at https://doi.org/10.48550/arXiv.2301.11623 (2023).

In general, our discussion with reviewer P4Ga about the task definition of dynamic link prediction and the time horizon $h$ highlights the complexity of the problem itself. Therefore, we believe that by pointing out problems in the current evaluation approaches and by suggesting a replacement that fixes these problems, our work is a valuable contribution that helps to bring temporal graph learning closer to making real-world impact.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper addresses the limitations of existing evaluation strategies for dynamic link prediction (DLP) tasks in temporal graphs, proposing a new task setting called link forecasting (LF). The authors highlight how fixed batch-size evaluation distorts task properties and can lead to issues like temporal dependencies or information leakage. They introduce a novel time-window-based evaluation approach, backed by extensive empirical results, to provide more accurate performance assessments of existing models.

While the proposed model shows promising results, there are several weaknesses that still need to be addressed:

1. The batch-oriented evaluation problem in continuous-time graphs only affects memory-based methods. Recent sequence-based models (e.g., GraphMixer, DyGFormer) ensure that each node is assigned all its historical neighbors immediately before the prediction time, thereby avoiding the issues described.
2. The proposed LF setting doesn’t fully resolve the problem, as it still faces information leakage when the edges in a time window exceed GPU memory. While the authors suggest that discarding information within each time window can mitigate information leakage, this can also be achieved when using batch-based evaluation.
3. The time-window approach introduces an unfixed number of edges per batch, which could impact training stability and convergence, but this is not discussed in the paper.

Based on these weaknesses, we recommend rejecting this paper. We hope this feedback helps the authors improve their paper.