Rethinking Evaluation for Temporal Link Prediction through Counterfactual Analysis

Authors: Aniq Ur Rahman, Alexander Modell, Justin Coon
Primary area: learning on graphs and other geometries & topologies
Keywords: temporal link prediction, counterfactual reasoning, graph learning, evaluation

Abstract:
In response to critiques of existing evaluation methods for temporal link prediction (TLP) models, we propose a novel approach to verify if these models truly capture temporal patterns in the data. Our method involves a sanity check formulated as a counterfactual question: "What if a TLP model is tested on a temporally distorted version of the data instead of the real data?" Ideally, a TLP model that effectively learns temporal patterns should perform worse on temporally distorted data compared to real data. We provide an in-depth analysis of this hypothesis and introduce two data distortion techniques to assess well-known TLP models.
Our contributions are threefold: (1) We introduce two simple techniques to distort temporal patterns within a graph, generating temporally distorted test splits of well-known datasets for sanity checks. These distortion methods are applicable to any temporal graph dataset. (2) We perform counterfactual analysis on six TLP models JODIE, TGAT, TGN, CAWN, GraphMixer, and DyGFormer to evaluate their capability in capturing temporal patterns across different datasets. (3) We introduce two metrics -- average time difference (ATD) and average count difference (ACD) -- to provide a comprehensive measure of a model's predictive performance.

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

Reviews and discussion:
<thread>
creation date:
1730362408140

thread_type:
official_review

<thread_object>
creator: reviewer_riwp

<content>
summary:
In this paper, the authors considered the quality evaluation of the temporal link prediction (TLP) task. Two new evaluation strategies (i.e., Intense and Shuffle) based on counterfactual analysis on TLP models (with metrics of average time difference (ATD) and average count difference (ACD)) were proposed. Experiments demonstrate that under the new evaluation strategies, some SOTA TLP methods may still fail to 'capture temporal patterns' of some widely-used public dynamic graph datasets.

strengths:
**S1**. This paper is well-written and well-motivated, which makes it easy to read.

**S2**. The limitations of existing evaluation strategies of TLP (i.e., the major topic of this paper) are seldom studied or discussed in related literature.

**S3**. The idea of using counterfactual analysis to design new evaluation strategies of TLP is interesting.

weaknesses:
**W1**. Some of the statements regrading the motivation and research gaps are weak, which need further interpretations.

  For instance, in Section 1, the authors claimed that 'the timestamps in the query are restricted to the timestamps present in the ground truth , which makes the evaluation biased and does not test the model’s performance in the continuous time range' but why? Further, interpretations combined with toy examples or rigorous theoretical analysis are recommended.
  

***

**W2**. From my perspective, the theoretical analysis of Proposition 2.1 is relatively weak, which cannot be considered as a rigorous analysis.
  
  The statement 'model $f$ is capable of learning patterns' is weak. It is unclear how to determine (e.g., quantitatively measure) that a model is capable or incapable of learning some patterns. It is also similar for the statement 'can(not) capture/learn temporal patterns'. These are very strong statements. From my perspective, it is insufficient to qualitatively describe them only using natural languages. Instead, rigorous quantitative analysis is required.
  
  The performance of a model on test set may also decline when it encounters the well-known over-fitting issue. There are no further discussions regarding this issue.


***

**W3**. Experiments in Section 4 are, to some extent, too simple. Some details regarding experiment results also need further clarification.

  In Section 4, only the experiments results w.r.t. the AP metric were given. In Section 1, some other metrics (e.g., AU-ROC, MAR, and MRR) were mentioned. However, there are no further experiment results based on these metrics, which cannot fully validated the motivations of this paper.
  
  The proposed evaluation metrics involve two additional sampling strategies with hyper-parameters $K$ and $\bar \tau$. However, there are no further analysis regarding the effects of these hyper-parameters.
  
  Discussions about the experiment results in Table 3 are insufficient. After reading Table 3, it is still unclear for me on each dataset, which TLP method performs the best under the new evaluation metrics.
  
  It is a good presentation to give the example in Figure 2, but the concrete definitions of $\lambda^* (t)$ and $\lambda' (t)$ are not given. It is unclear for me how the corresponding edges were generated (e.g., following what probability distributions).

***

**W4**. At the end of this paper, there is no conclusion section to discuss the limitations of this study and possible future work to address these limitations.

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

</thread>
<thread>
creation date:
1730471434907

thread_type:
official_review

<thread_object>
creator: reviewer_3vif

<content>
summary:
This paper presents a new approach to evaluating temporal link prediction models, stating that the model should perform worse on temporally distorted test data. Two data distortion techniques are introduced, namely intense and shuffle. Two new evaluation metrics are proposed: average time difference and average count difference. Empirical experiments are carried out on six temporal graph datasets.

strengths:
Novelty: The paper provides a new perspective to evaluate the temporal link prediction models.

Presentation: The paper is well-written and pretty understandable. The figures help demonstrate the points of the paper.

weaknesses:
1.  The weaknesses of the binary classification approach claimed in the introduction section are not justified appropriately, especially the first and the second. Different metrics are designed for different tasks. We can imagine that when finding a temporal path between two nodes, we only care about whether an edge exists when needed, not within a time interval. For example, "Is the gate open at 9 a.m.?" instead of "Is the gate open between 7 a.m. and 3 p.m.?" when you only need to pass the gate at 9.

2. Proposition 3.1's proof is incorrect, making it vulnerable. The proposition discusses the probability that prediction accuracy drops when the test data is distorted, while s6 in the proof does not address this probability. Also, claiming that satisfying s1-s5 will result in s6 is assuming the conclusion.

3.

questions:
Can you elaborate more about why the binary classification approach is ill-posed?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730982799398

thread_type:
official_review

<thread_object>
creator: reviewer_x51e

<content>
summary:
This study presents a method to verify whether existing temporal link prediction (TLP) models effectively capture temporal patterns in data. To this end, the authors propose a counterfactual question: "What if a TLP model is tested on a temporally distorted version of the data instead of the real data?" They argue that, ideally, TLP models that capture temporal patterns well on the training set should perform worse on temporally distorted data compared to the original data. Specifically, the authors introduce two simple techniques for distorting temporal graphs and create a distorted test dataset to conduct counterfactual analysis on six existing TLP models.

strengths:
•	S1. Well Motivated: Traditional evaluation methods for temporal link prediction often assess whether an edge exists between two nodes at a specific time. However, these methods are limited to timestamps within the ground truth, constraining the evaluation to specific query times. This study highlights the need for alternative evaluation metrics for temporal link prediction.

•	S2. Originality: By using evaluation methods beyond the standard metrics in temporal link prediction, the study provides a diverse and new assessment of model performance on the temporal link prediction task.

•	S3. Clarity: The paper is generally well-structured and easy to follow. It addresses issues with current evaluation methods, introduces new evaluation metrics, explains them in detail, and then applies them to analyze existing TLP models.

weaknesses:
•	W1. Logical Structure: While the paper identifies issues with existing evaluation metrics, the proposed counterfactual question may not fully address these issues. The connection between the shortcomings of current metrics and the model's ability to capture temporal patterns is not adequately explained. Additionally, there is insufficient support for Proposition 3.1 in the counterfactual analysis. The reasoning behind why models that perform well on the distorted test set have failed to learn temporal patterns is unclear based on the provided proof.

•	W2. Experimental Support: The counterfactual analysis posits that if TLP models perform similarly or better on the distorted test set compared to the original test set, they have not learned temporal patterns in the training set. However, the experiments in Table 3 simply show that many TLP models perform similarly or even better on the distorted test set, with some results deviating from the expected trend. This limited experimental evidence does not conclusively support the claim that TLP models fail to learn temporal patterns from the training set.

•	W3. Definition of Key Terms: The paper lacks clear definitions for several crucial terms. Key concepts like "temporal pattern" and "learnability of a temporal graph" in the Proposition 3.1 are not adequately defined or explained, which makes it difficult to interpret the claim that TLP models fail to learn temporal patterns.

questions:
•	Q1. How does the counterfactual question relate to the issues with existing evaluation methods in the introduction for temporal link prediction? The previously mentioned issues are limited to the timestamps within the ground truth and performance variation due to negative sampling. How does the counterfactual question address each of these concerns?

•	Q2. In the introduction section, it is stated that the counterfactual question tests a TLP model's ability to capture temporal patterns in a temporal graph. Could you clarify the definition of "temporal patterns"? Additionally, why should a TLP model capable of learning temporal patterns perform worse on temporally distorted data? In my opinion, if a model generalizes well, it might perform better even on temporally distorted data, depending on the distortion method.

•	Q3. I found Proposition 3.1 in the counterfactual analysis difficult to understand. What does it mean for a temporal graph to be "learnable," and is this a reasonable assumption? Moreover, why should statement 6 hold if statements 1 through 5 are satisfied?

•	Q4. According to the temporal distortion techniques in section 3.2, methods like INTENSE can add edges frequently appearing in the training set back into the test set. Wouldn’t TLP models that learn structural and temporal patterns still perform well by leveraging the learned structural patterns from past interactions?

•	Q5. Based on the results in section 4, most TLP models fail to capture temporal patterns across most datasets according to the counterfactual analysis. However, this conclusion is only valid if the counterfactual question itself is valid. To support the claim that models fail to capture temporal patterns, more diverse and rigorous experiments are necessary.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731012385004

thread_type:
official_review

<thread_object>
creator: reviewer_aqyn

<content>
summary:
The authors of this work propose an approach to apply counterfactual analysis in the evaluation of dynamic link prediction. To this end, they first introduce the idea to use distorted versions of the test set in a temporal graph, where temporal information is (partly) removed. They argue - based on formal logics - that a model trained on an undistorted temporal graph that generally performs as well or better on a temporally distorted test set does not actually learn temporal patterns in the training set. Building on this idea, the authors introduce two different temporal distortion approaches, along with two temporal distortion metrics that can be used to quantitatively compare distorted and undistorted temporal graphs. They then apply their approach to five temporal graph data sets and six state-of-the-art dynamic link prediction techniques, concluding that the majority of state-of-the-art temporal graph learning methods actually does not learn temporal patterns in common data sets.

strengths:
[S1] The authors address an important open issue in the evaluation of dynamic link prediction

[S2] The authors combine the approach of counterfactual analysis from causal inference and apply it to the evaluation of temporal graph learning. To the best of my knowledge, this is a novel combination (even though comparisons to shuffled temporal graphs have been considered in other works). 

[S3] The results are interesting and important as they suggest that the majority of temporal graph learning architectures actually do not learn temporal information (at least for the link prediction task and considering the random shuffle distortion).

[S4] The paper is exemplary in terms of its clarity. It is a joy to read it.

weaknesses:
[W1] I would have expected a more detailed description of the experimental evaluation in section 3, including the hyperparameters used to train the models, batch sizes, negative sampling strategy etc. 

[W2] The analysis does not take into account some of the issues outlined in recent works (and also mentioned in this paper), in particular the influence of the negative sampling strategy on the evaluation of dynamic link prediction.

[W3] I am not convinced that the specific verbal description of proposition 3.1 holds in this generality (see question below) and I would appreciate if this crucial aspect (which also influences the interpretation of results for one of the distortion methods) could be clarified by the authors.

[W4] I did not understand the motivation of the Intense distortion function, and what we can learn from it about the ability of a model to learn temporal patterns (see my question below). This somehow limits the contribution of the work to an - albeit interesting - analysis of dynamic link prediction in test sets with randomly permuted timestamps.

questions:
Referring to [W1], please report all details of the experimental evaluation, especially which hyperparameters were used. Also, the batch size used to train the models is known to influence the  of dynamic link prediction, especially for those models aggregating links within batches.

Regarding [W2], if I understood the experimental evaluation correctly, a simple random negative sampling was used. Referring to Porsafaie et al. 2022, I wonder whether the negative sampling strategy used to train the models will also affect the results in table 3? What is your expectation? Did you evaluate this?

Considering [W3], I believe that the specific verbalization of proposition 3.1 is too strong. Let me explain: In proposition 3.1 the counterfactual question is used to imply that a model f cannot learn the temporal patterns in E_{train}. However, since the counterfactual question depends on a *specific method* to temporally distort the test set, I would argue that this aspect must also appear in the sentence after the implication. As an example, we may temporally distort a graph such that the temporal patterns that are learned by a model are preserved, in which case the probability P(y_x | x', y') can be zero. But this does not necessarily imply that the model cannot learn temporal patterns. It only implies that it cannot learn those temporal patterns that are destroyed by this specific distortion approach. It would be much appreciated if the authors could clarify this aspect, or show me why my argument above is wrong.

Finally - and referring to [W4] - this may also explain why in table 3 none of the methods can distinguish the real temporal graphs from those where the Intense distortion has been applied. This could simply be due to the fact that the Intense method leaves crucial temporal patterns untouched, in which case this result is neither surprising nor interesting. In this sense, I find the results on the Shuffle distortion much more convincing, as it guarantees that temporal patterns are destroyed (and the implication above becomes valid). Could the authors clarify their motivation to study the Intense distortion function?

In light of my open questions and suggestions above, I have assigned an overall rating of 6 for now, but would be willing to raise it if my concerns are adequately addressed.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733180176648

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Author-Reviewer Discussion

comment:
- The reviewers raised doubts on Proposition 3.1 and its accompanying proof. We reframed it as a Conjecture and presented the rationale through a simplified example of **distorting binary sequences** `(pages 4-5)`
- We added `Fig. 5 on page 7` to visually explain how INTENSE distortion works.
- We defined the terms **temporal patterns** and **learnability** to aid the understanding of the counterfactual setup presented next `(page 3)`.
- We updated the **results** section and arranged the datasets in increasing order of size. We added a paragraph on key insights `(pages 7-8)`.
- The reviewers appreciate the **clarity** of our paper
- The reviewers acknowledge the **novelty** of counterfactual analysis in temporal link prediction
- We provided additional information regarding the training of the models in our response
- We furnished the reviewer with additional results on **AU-ROC** metric
- We re-explained concepts from the paper to some reviewers to clarify their doubts

---

We believe that our work is useful for the temporal graph learning community, especially those working on the temporal link prediction problem, as it will serve as a sanity check for models and encourage researchers to adopt better evaluation methods. This work can be seen as a step towards bridging the gap between statistics and causality in the context of temporal graph learning.

To summarize, this paper asks the question:

**Do the TLP models understand the order in which the edges appear and the frequency with which they appear in an interval?**

---

We thank the chairs and the reviewers for their valuable time and look forward to a fair decision.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The authors apply counterfactual analysis to evaluate temporal link prediction (TLP). Their key insight is that if a model trained on the original data performs better on data with distorted temporal patterns, it indicates a failure to effectively capture temporal patterns. Building on this idea, the paper introduces (1) two distinct distortion methods and (2) two novel evaluation metrics. Using them, the authors conduct a comprehensive analysis of existing TLP methods.

All reviewers agreed that the authors point out an important, previously overlooked issue, present a novel approach, and provide a clear presentation.

However, the reviewers were not fully convinced by the claim that better performance on distorted data implies that TLP methods fail to capture temporal patterns, due to several reasons:
- (Reviewer AQyN): The validity of the claim relies on specific distortion methods, which require better justification.
- (Reviewers x51E & 3ViF): The claim depends on the problem formulation or training objectives (particularly their differences from evaluation methods), which need further exploration.
- (Reviewer RiwP): Model performance can be influenced by other factors, such as overfitting

Considering all, the meta-reviewer recommends rejection, as the paper, despite its clear merits, has significant room for improvement based on the feedback provided.