CoDy: Counterfactual Explainers for Dynamic Graphs

We sincerely thank you for your time and insightful feedback on our paper. Please find our rebuttal to the weaknesses below:

W1: Potential bias in selection policies

The selection policies are indeed designed as heuristics to introduce a bias, guiding the search efficiently within the vast combinatorial space of potential counterfactual subgraphs (past events). This guidance is crucial for tractability. Our experiments explicitly demonstrate the value of this bias. While these policies prioritize recent/proximal/high-impact events, the MCTS framework in CoDy, particularly the exploration component in the selection score (Section 4.3), inherently encourages exploring less-immediately-promising paths. This helps mitigate the risk of exclusively focusing on recent events and allows CoDy to discover counterfactuals involving older or less obviously connected events if they are indeed critical. The search doesn't only consider these events; it prioritizes them while retaining the ability to explore alternatives.

W2: Reliance on prediction logits

We appreciate the reviewer's point regarding the term "model-agnostic." We use this term to indicate that CoDy does not require access to the internal architecture, parameters, or gradients of the TGNN model, unlike gradient-based or model-specific explainers. It interacts with the model solely through its input (perturbed graph history) and output (prediction score). We assume that a TGNN outputs a continuous output signal (like logits or probabilities), which is the case for all TGNNs that we are aware of. In a case of a TGNN that strictly produces binary outputs, there would indeed be little guidance for efficient search, likely necessitating brute-force approaches (however, we do not percieve this a realisitc setup of a TGNN).

W3: CoDy outperforms factual methods on $AUFSC_-$ scores

This is an excellent observation, and we agree it appears counter-intuitive since CoDy optimizes for counterfactuals ($fid_+$). The high $fid_-$/$AUFSC_-$ scores (sufficiency) achieved by CoDy, especially compared to T-GNNExplainer in several settings (Table 1), stem primarily from CoDy's search objective and fallback strategy. CoDy seeks the minimal necessary set of events to change the prediction. When a true counterfactual is not found within the search budget (either because none exists in the constrained search space or the search limit is reached), CoDy's fallback strategy (Section 4.3.5) returns the perturbation set $s_opt$ that caused the largest shift in the prediction logits. This $s_opt$ represents the set of most influential past events identified in the search. Even if not enough to flip the prediction, these events often still capture sufficient factual evidence for the prediction of the model. In fact, our evaluation shows, that this is highly effective in uncovering factual evidence. In contrast, factual methods like T-GNNExplainer aim directly for sufficiency but might identify larger subgraphs or be affected by approximations (as noted in their paper and our Section 5.3.2), potentially leading to lower $fid_-$/$AUFSC_-$ scores in some cases compared to CoDy's focused, impact-maximizing search (even in fallback).

W4: Lack of user studies or human-centered evaluations

We fully agree with the reviewer that user studies are invaluable for assessing the practical interpretability and utility of explanations. However, the primary contribution of this work is methodological: introducing the first counterfactual explanation framework (CoDy) specifically for TGNNs on CTDGs and rigorously evaluating its quantitative performance against existing factual methods and a novel greedy baseline using established metrics ($fid_+$, $fid_-$, sparsity, etc.). Given this focus, we considered extensive human-centered evaluations to be beyond the scope of this initial paper. Acknowledging the importance of user studies, we will explicitly recommend them as a direction for future work in the conclusion section of the revised manuscript.

W5: Experiments focus on social/interaction networks

Our choice of datasets (Wikipedia, UCI-Messages, UCI-Forums) was motivated by their prevalence in TGNN research and their representation of important real-world dynamic systems. While they primarily fall under social/interaction networks, they exhibit considerable diversity:

• Unipartite (UCI-Messages) vs. Bipartite (Wikipedia, UCI-Forums).
• Presence (Wikipedia) vs. Absence (UCI) of edge features.
• Varying temporal dynamics and graph densities (Table 2).

We believe these datasets provide a strong and representative initial validation of CoDy's effectiveness. While our datasets focus on interaction networks, the methodology extends to broader CTDG applications, such as financial modeling and dynamic recommendation systems.

Thank you for your comprehensive review and valuable feedback.

1. CoDy strictly removes events from the input graph reflecting the causal relationship between those events and the prediction; i.e., if events $\\{e_i,...\\}$ would not have happened, the prediction would be different. The counterfactuals thus depend on the identified events, including edge and node additions/removals (note that the evaluated TGNNs only cover additions)

2. We use "local-gradient" to reflect the impact that removing a single event has on the prediction logits. The term "local gradient" reflects this in the sense of the influence that an infinitesimal change to the input (removal of event) has on the output. We agree that the term could be misconstrued as implying access to model internals and are thus renaming it to “local-event-impact”.

3. Our search algorithm balances exploration and exploitation, dynamically adapting the search based on previously explored trajectories, similar to Monte-Carlo Tree Search. This flexibility is especially important in a vast combinatorial space as in CTDGs. We have indeed considered learning an MLP to inform a selection strategy, however, our initial experimentation with this gave a strong indication that such a surrogate fails to perform sufficiently to provide a good selection indication in this setting.

4. We have followed your suggestion and simplified the formulation.

5. Our goal in selecting the candidate with the largest shift is to identify the minimal set of features whose removal has the most decisive impact on the prediction. In many counterfactual explanation methods (e.g., Wachter et al.), the distance from the decision boundary is a primary metric, and our approach follows a similar principle by prioritizing the “critical” events. To ensure a balanced selection, we combine this approach with a sparsity criterion, avoiding unnecessary complexity while maintaining interpretability.

6. Our procedure for PGExplainer was to generate factual explanations - i.e., the subgraph that supports the prediction - and then construct a counterfactual by removing this subgraph from the input graph. Although this is a heuristic adaptation, it provides a baseline for comparing fidelity. Adapting most static CF methods (especially generative ones like CLEAR or optimization-based like MEG) to the CTDG setting requires significant methodological changes (handling event sequences, temporal dynamics, defining valid edits in time) and engineering effort, making it a substantial research project in itself. Our focus was on establishing a baseline within the CTDG CF setting, which motivated the development of GreeDy. We believe GreeDy serves as a more direct and fair baseline for CoDy's search strategy within the same problem formulation. On a similar note, CF² requires applying continuous masks on nodes/edges which is difficult to translate to the event-based nature of TGNNs like TGAT and TGN.

7 + 10. Fidelity definitions vary across works. We follow GraphFramEx’s model-focused fidelity definition (Amara et al. 2022) and clarify this in Appendix D.

We evaluate instances in which the TGNN makes correct predictions separately from instances where it misclassifies future links. We state this in 5.1 under “Explained Instances”. Given your feedback, we have added further clarification on this and the fidelity metric.

8. We appreciate the suggestion to use GED. However, CoDy only performs event removal. In this specific setting, the number of removed events (captured by the numerator in sparsity) is the graph edit distance from the original graph's event set to the perturbed graph's event set (where edits are event deletions). Since CoDy operates solely via event removal, sparsity naturally captures structural distance, making GED an unnecessary addition in this context.

9. Thank you for highlighting this. The 6.11x improvement in fidelity refers to average improvement of CoDy-spatio-temporal over PGExplainer shown in the table in Appendix F. The number is an artefact of a previous revision and we will replace it with an insight from Table 1 and add an explanation.

11. We believe the Jaccard similarities are a natural consequence of the fact that, regardless of the selection policy, all variants start with the same underlying search tree and balance exploration & exploitation, steering the search along promising paths. When the key causal events are strongly influential, even a random policy may discover similar substructures. For the local-gradient variant, although its ranking metric is based on the logit difference, the fact that its explanations significantly overlap with those from the spatio-temporal variant reinforces that the same vital events are consistently identified.

We thank the reviewer for highlighting other related works. We have added GRACIE to related work. While addressing a different problem, it is an important addition for completeness.

We sincerely thank you for the detailed and insightful review.

Runtime vs. Performance Trade-off

The noted potential 10-fold increase in model calls for CoDy is largely a configurable design choice, not an inherent limitation of CoDy. CoDy, in our experiments, continues searching after finding the first counterfactual (CF) to identify potentially sparser explanations. GreeDy terminates immediately upon finding a CF or reaching a local optimum. As shown in Appendix F.2, CoDy typically finds the first counterfactual explanation relatively quickly, often within a number of iterations comparable to GreeDy's total calls. If configured to stop after finding the first CF (maintaining fidelity while deprioritizing minimal sparsity), CoDy's runtime becomes much closer to GreeDy's, while still being more robust. Thus, CoDy’s runtime is highly adjustable, allowing users to trade off speed for sparsity and more interpretable explanations as needed. We will clarify this in the paper.

Sparsity Control

Neither CoDy nor GreeDy take sparsity as an input; they identify the minimal necessary event set to flip the prediction. Sparsity is an outcome of the search, not a hyperparameter. T-GNNExplainer also determines size automatically; only PGExplainer is configured with a fixed sparsity of 0.2. The fidelity values $fid_+$ and $fid_-$ are computed aggregately over all explanations found for the test instances, representing the overall success rate for the method across its generated explanations. To calculate the AUFSC, we integrate over the cumulative fidelity achieved at sparsity levels (the fraction of instances for which a method found a counterfactual explanation with $sparsity \leq s$, at sparsity level s). This is a standard way to evaluate methods producing variable-size outputs, directly comparing their ability to find concise and necessary explanations.

Connection to Discrete-Time Methods

While CTDGs can be discretized, this process inherently loses temporal precision, as multiple events are grouped within fixed intervals, erasing exact timing and ordering information. TGNNs designed for CTDGs (e.g., TGN, TGAT) explicitly leverage this fine-grained information. Applying a DTDG explanation method to a discretized CTDG explains a different, approximated system and model, not the original CTDG and TGNN. Methods like Prenkaj et al. (2024) are designed for such models that have different assumptions about graph evolution. CoDy directly explains higher-fidelity CTDG models, ensuring explanations faithful to the underlying temporal structure.

Performance

We agree that char scores around 0.5-0.6 are not perfect, but they represent a significant achievement for this novel and challenging task. As the harmonic mean of $fid_+$​ and $fid_−$, $char$ is sensitive to the lower of the two. Finding minimal necessary counterfactuals (high $fid_+$) on complex temporal graphs is inherently difficult, especially for correctly predicted instances where substantial evidence might support the original prediction (Section 5.3.1). Achieving these scores demonstrates a meaningful ability to identify crucial subgraph structures.

We appreciate the reviewer noting GreeDy's strong performance. We introduce GreeDy precisely as a competitive baseline. While GreeDy is effective when its greedy path aligns well with the optimal solution, CoDy's approach offers greater robustness against local optima. Appendix F.2 illustrates this: CoDy's performance continues to improve with more iterations, eventually surpassing GreeDy even in challenging settings.

We respectfully disagree that there are no clear patterns. The results consistently show: (i) Counterfactual methods (CoDy/GreeDy) significantly outperform factual baselines on $fid_+$, as expected. (ii) Spatio-temporal and Local-gradient selection policies substantially outperform Random and often Temporal policies (Section 5.3.4). (iii) There's a notable difference in explainability between correct and wrong predictions (Section 5.3.1). To make the results easier to interpret, we will reorganize the results tables and group evaluation together based on if the predictions were correct or wrong, showing a clearer picture of the results.

Relevance & Significance

Regarding the perceived specificity of our topic, we emphasize that CTDGs offer high-fidelity representations for ubiquitous evolving systems like financial networks, social media, and recommendation platforms, where powerful TGNNs are increasingly applied. As these TGNNs operate in high-stakes domains, understanding their 'black-box' decisions through interpretable methods is critical for trust, regulatory compliance, and debugging; counterfactual explanations provide particularly actionable insights in these contexts. Therefore, CoDy addresses the crucial and growing need for trustworthy TGNNs on high-fidelity CTDGs, bridging a significant gap for deploying these models responsibly in real-world applications.