CoDy: Counterfactual Explainers for Dynamic Graphs
Authors: Zhan Qu
Daniel Gomm
Michael Färber
Venue: ICML 2025 poster (2025)
Keywords: Explainability
Temporal Graphs
Graph Neural Networks
Primary area: social_aspects->accountability_transparency_and_interpretability

Abstract: Temporal Graph Neural Networks (TGNNs) are widely used to model dynamic systems where relationships and features evolve over time. Although TGNNs demonstrate strong predictive capabilities in these domains, their complex architectures pose significant challenges for explainability. Counterfactual explanation methods provide a promising solution by illustrating how modifications to input graphs can influence model predictions. To address this challenge, we present CoDy—Counterfactual Explainer for Dynamic Graphs—a model-agnostic, instance-level explanation approach that identifies counterfactual subgraphs to interpret TGNN predictions. CoDy employs a search algorithm that combines Monte Carlo Tree Search with heuristic selection policies, efficiently exploring a vast search space of potential explanatory subgraphs by leveraging spatial, temporal, and local event impact information. Extensive experiments against state-of-the-art factual and counterfactual baselines demonstrate CoDy's effectiveness, with improvements of 16% in AUFSC+ over the strongest baseline. Our code is available at: https://github.com/daniel-gomm/CoDy

CoDy: Counterfactual Explainers for Dynamic Graphs
Zhan Qu 123
Daniel Gomm 45 Michael Färber
Abstract
Factual
Students
Forums
Explanation
Temporal Graph Neural Networks (TGNNs) are widely used to model dynamic systems where relationships and features evolve over time. Al- though TGNNs demonstrate strong predictive capabilities in these domains, their complex ar- chitectures pose significant challenges for ex- plainability. Counterfactual explanation meth- ods provide promising solution by illustrat- ing how modifications to input graphs can influ- ence model predictions. To address this chal- lenge, we present CoDy MoDyyCoonterractuua Ex- plainer for Dynamic Graphs-a model-agnostic, instance-level explanation approach that identi- fies counterfactual subgraphs to interpret TGNN predictions. CoDy employs a search algorithm that combines Monte Carlo Tree Search with heuristic selection policies, efficiently exploring a vast search space of potential explanatory sub- graphs by leveraging spatial, temporal, and lo- cal event impact information. Extensive experi- ments against state-of-the-arr factual and counter- factual baselines demonstrate CoDy's effective- ness, with improvements of 16% in AUFSC+ over the strongest baseline. Our code is available at: https://gthuub.com/aneee// gomm//CoD
Maths 1
B
Maths
Predicted Future Link
Counterfactual
Eplanation
History 1
Age of edge
Old
New
Figure 1. Bipartite dynamic graph of student posts university social network. Edge colors represent their ages.
evolving temporal dependencies. Consequently, Temporal Graph Neural Networks (TGNNs) have been specifically de- veloped to leverage the rich spatial and temporal information inherent in dynamic graphs (Zhao et al., 2019; Rossi et al., 2020; Xu et al., 2020). However, as with many deep learning models, TGNNs often function as "black boxes", offering limited insight into their decision-making processes (Xia et al., 2023; Chen & Ying, 2023).
Explainability methods for Graph Neural Networks (GNNs) aim to identify small subset of nodes and edges that most strongly influence a model's prediction. However, most existing methods are designed for static graphs and do not generalize well to dynamic graphs, which involve complex temporal interactions (He et al., 2022; Xia al., 2023; Chen & Ying, 2023). In temporal graphs, multiple events may occur at the same timestamp and the same position, adding complexity to the dependencies between interactions (Han et al., 2020; He et al., 2022). The explanations for TGNNs should be temporally approximate and spatially adjacent to the target (Kovanen et al., 201 1; Chen & Ying, 2023).
1. Introduction
Dynamic graphs are commonly used to model applications with features that change over time, such as social networks, e-commerce platforms, and collaborative online encyclope- dias like Wikipedia (Huang et al., 2024; Longa et al., 2023; Yu et al., 2023). addition the statie topological graph structure, dynamic graphs also capture the continuously
'qqual contribution 'TU Dresden, Dresden, Germany AL, Dresden, Germany 'Karlsruhe Institute of Tech- nology, Karlsruhe, Germany "University of Amsterdam, Ams- terdam, Netherlands 'Centrum Wiskunde Informatica, Am- sterdam, Netherlands. Correspondence to: Daniel Gomm <danicl gomm @ cwi.nl>, Zhan Qu quccuu deeeuudresdendd>..
The few methods targeting TGNN models focus primarily on factual explanations, which identify specific nodes and edges contributing prediction (Xia et al., 2023; Chen & Ying, 2023). They fall short of exploring how changes in the input graph could lead to different outcomes. Counter- factual explanations, which illustrate how altering the graph changes the prediction, are gaining popularity for their abil- ity to establish causal relationships and highlight decision
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

CoDy: Counterfactual Explainers for Dynamic Graphs
1. seloct
1. select
3. Expand
Example Input Graph
Dreot
Omrinien wit
0
11
Ortiseon art
Rd
8c0r 0.77
8007 E4 mull
Backgropagate
ordered by temporal selection policy
10g
Oncomion knt
Ontteton wit
2. Simulate
Predicted Future Link
Perturbed
Iupnt
Sc0r
0.39
Scores = mull
Age of edge
Old
New
123
fg
Ontissiin ort
TGNN
SCOrc3 0.15
800TC6
null
scores 1.12
CoDy search framework. The left side shows an example of a temporal input graph, where the explained future link is highlighted in blue, and the other links are color-coded based on their ages. On the right, one iteration of the CoDy algorithm is illustrated. Each rectangle represents a node in the search tree, corresponding to a specific perturbation of the input graph.
Figure 2.
boundaries (Byme 2019; Reade-Romeroooooo et al., 2024). They provide actionable insights, help identify biases, and can uncover adversarial examples (Lucic et al., 2022). Despite temporal relationships in TGNNs often naturally suggesting causal links between nodes, no existing methods effectively leverage counterfactual explanations. Fig. 1 shows an exam- ple comparing factual and counterfactual explanations for a TGNN model's prediction that Student B will post on the Math 2 forum the future. The factual explanation traces this prediction through indirect connections: Student pre- viously posted on Math 1, Student A posted both Math and Math 2, and both A and B posted History 1. This can be complex and cognitively demanding to interpret. In con- trast, the counterfactual explanation simplifies the reasoning by showing that, if Student had not posted on Math 1, the post on Math 2 would not have occurred higheddhhiihhihinng the minimal set of actions necessary for the prediction (Lucic al., 2022; Prado-Roment et al., 2024). In summary, fac- tual explanations aim to identify subgraph with sufficient information to reproduce the same prediction, while coun- terfactual methods seek the subset of information necessary to alter the outcome (Tan et al., 2022).
We propose a comprehensive evaluation framework that jointly assesses factual and counterfactual explanations on dynamic graphs. Our evaluation shows that CoDy excels in generating counterfactual explanations for TGNN models such as TGN (Rossi al., 2020) and TGAT (Xu et al., 2020), outperforming GreeDy and factual methods, including PG- Explainer (Luo et al., 2020) and T-GNNExxlainer (Xia et al., 2023) across multiple datasets. Additionally, we demon- strate that incorporating spatio-temporal context and local event impact significantly improves the relevance and fi- delity of counterfactual explanations. This insight opens new directions for advancing TGNN explainability by lever- aging richer temporal and structural cues.
In summary, our main contributions are as follows:
1. We introduce CoDy, the first method for generating counterfactual explanations for TGNNs.
2. We develop GreeDy, a baseline approach for counter- factual explanations in dynamic graphs.
3. We create an evaluation framework tailored to counter- factual explanations on dynamic graphs.
To address the need for concise and actionable explana- tions, we introduce CoDy (Counterfactual Explainer for Dynamic Graphs), a model-agnostic instance-level explainer for TGNNs. CoDy adopts principles from Monte Carlo Tree Search to efficiently identify counterfactual examples by modifying a subset of past events to alter the model's prediction. Further, we develop policies that leverage spatio- temporal structure and local event impacts to enhance search efficiency and effectiveness. Since CoDy is the first counter- factual explanation method for TGNNs, we develop GreeDy (Greedy Explainer for Dynamic Graphs), strong counter- factual baseline that employs greedy search.
4. We conduct extensive benchmarks of CoDy, showing its superior performance compared to counterfactual and factual baselines.
2. Related Work
Numerous explainability methods have been proposed for GNNs on static graphs, leveraging techniques such as gra- dients (Baldassarre & Azizpour, 2019; Pope et al., 2019), perturbations (Ying et al., 2019; Luo et al., 2020), decompo- sition rules (Schnake et al., 2021), surrogate models (Huang et al., 2022; Vu & Thai, 2020), Monte Carlo Tree Search
2

---

CoDy: Counterfactual Explainers for Dynamic Graphs
(MCTS) (Yuan et al., 2021), and generative models (Yuan et al., 2020; Shan et al., 2021; Miao et al., 2022; Li et al., 2023). Still, explainability for Temporal Graph Neural Net- works (TGNNs) remains underexplored and challenging.
3. Preliminaries and Problem Formulation
Continuous Time Dynamic Graphs (CTDG) We de- note CTDG as a sequence of timestamped events g {EI, 52, $2,.... Each event E; is associated with a timestamp t that f,-1 t. < f,+1- Events represent the addition, removal, or attribute change of nodes or edges. Within a CTDG, we distinguish temporal distance, which is the difference in timestamps between two events, and spatial distance, defined as the shortest path distance within the graph structure between the nodes or edges involved in the events at their respective times. The k-hop neighborhood of an event E; covers the set of events that occurred within k-edges of any nodes involved in event E, until time t,.
Dynamic graphs are commonly represented using Discrete- Time Dynamic Graphs (DTDGs) and Continuous- Time Dy- namic Graphs (CTDGs) (Kazemi al., 2020). DTDGs represent a system through a sequence of static snapshots, each corresponding to a specific time interval. Most isting explainability methods focus on DTDGs, relying techniques such as surrogate models (He et al., 2022), tem- poral decomposition (Liu et al., 2023), and model-specific feature analysis (Fan et al., 2021). These approaches typ- ically aggregate feature importances across snapshots to provide explanations. Recently, generative approaches such as GRACIE (Prenkaj et al., 2024) have been proposed for counterfactual explanation in DTDGs. GRACIE leverages class-specine variational autoencoders to account for distri- butional shifts across discrete time steps and performs gener- ative classification by modeling class-conte conditional graph dis- tributions. Predictions are inferred via latent reconstruction loss, enabling principled counterfactual generation without relying on fixed decision boundaries. However, GRACIE is tailored to discrete- time snapshots and cannot be readily applied to CTDGs without substantial adaptation to account for continuous, event-based graph dynamics.
Future Link Prediction A future link prediction model f : (g(t)), + IR estimates the likelihood that a future event e; will occur in the graph. Without loss of gener- ality, we assume that the model ʃ outputs logit values as an approximation of these odds. The prediction is based on the history of events (tx)) = (EIlEz E G. S fx] in the temporal graph G up to time 4, The model f can be any suitable function, such as TGNN trained for this task. binary classification function p + {0, 1} transforms the output of into definitive prediction, where 1 indicates that the future link is predicted to occur.
In contrast, CTDGs capture continuously evolving inter- actions through timestamped events, making them more representative of real-world applications such as social net- works. Despite their significance, explainability for CT- DGs remains relatively unexplored, with only two meth- ods proposed: T-GNNExplainer (Xia et al., 2023) and TempME: (Chen& & Ying, 2023). T-GNNExplainer employs a search-based perturbation approach, utilizing MCTS and a Multi-Layer Perceptron- perceptron-based navigator to predict event importances and guide search space exploration. TempME, on the other hand, identifies key temporal motifs motifs-reeurring patterns in dynamic graphs-to explain predictions.
Counterfactual Examples in Future Link Prediction Counterfactual explanations provide actionable insights into specific predictions, making them particularly valuable for interpreting the outputs of complex deep graph models like TGNNs. A counterfactual example Xz,, explaining a predic- tion of a future link s;, consists of a critical subset of past events Xx, S G(4.) necessary for the original prediction. This necessity is defined by the condition:
p(f(G(t))..) # p(f((g(()) \ (z)))
(I)
For any given future link e,, there may be multiple or no counterfactual examples. A counterfactual explainer, de- noted as ear(), provides rationale for the model's predic- tion. For future link predictions, ez(-) is a function that takes input the TGNN model f, the temporal graph G(t;), and the future link Es, and outputs subset of the origi- nal graph's 's events as counterfactual explanation, i.e. any combination of past events:
Existing methods, however, are limited to factual explana- tions that identify influential factors but do not consider alternative scenarios. Counterfactual explanations, which have been successfully applied to static GNNs (Tan et al., 2022; Lucic al., 2022), provide more intuitive way to explore "what if" scenarios by identifying minimal changes needed to alter model predictions. However, adapting coun- terfactual explanations to temporal graphs is challenging due to their evolving nature and complex dependencies.
((t())
(g(t)) (,s)
ex : (f. +
(2)
To address this, we propose a novel counterfactual explana- tion approach for CTDG-based TGNNs that captures both temporal dependencies and spatial structures. Our method enhances interpretability by providing explanations that are not only intuitive but also actionable.
k
A==
The output of ex can be any combination of past events. For- mula 2 adheres to the notation for permutations described by Stanley (1986).
3

---

CoDy: Counterfactual Explainers for Dynamic Graphs
Objectives for Counterfactual Explanation We iden-
in CoDy is specifically designed for counterfactual explo- ration. The goal is to identify the minimal set of events whose removal alters the model's prediction. Any child node in the tree extends the set of omitted events associated with its parent node by an additional event. This search tree is dynamically constructed as the search progresses, facilitating efficient traversal through the space of potential counterfactual explanations while minimizing unnecessary expansions. This structure promotes the identification of concise and relevant counterfactual examples, aligning with the dual objectives of maximizing discoveries and minimiz- ing complexity.
tify two primary objectives: maximizing the discovery of counterfactual examples and minimizing the complexity of these explanations. The goal of maximizing discoveries is to provide counterfactual explanations for as many instances as possible, while minimizing complexity aligns with the principle of Occam's s razor, suggesting that explanations should be concise and contain only relevant details (Yuan et al., 2023; Tan et al., 2022). Thus, the explanation should contain as few events as possible.
4. Methodology
This section presents the Counterfactual Explainer for Mod- els on Dynamic Graphs (CoDy) alongside the baseline method, Greedy Explainer for Models on Dynamic Graphs (GreeDy). Both approaches elucidate predictions made by TGNNs on CTDGs, focusing on efficiently navigating a defined search space to identify counterfactual examples.
4.1. Selection Policies
Selection policies guide the traversal of the partial search tree by prioritizing which nodes to explore. Each node in the search tree represents a unique combination of past events, with child nodes differing by the omission of single event from their parent node. The selection policies rank these potential event omissions, directing the search toward efficiently discovering counterfactual examples. We propose four distinct policies:
Search Space In a dynamic graph, each subset of past events related to a futuree link may constitute a counterfactual example. Therefore, the complete search space Se, includes all combinations of past events of the predicted future link Ex- Given that this search space grows exponentially with the number of past events, we streamline the search process by imposing spatial and temporal constraints, narrowing the focus to a subset of past events located within the spatio- temporal vicinity of the target future link event. To limit the search space spatially, we only consider events within a t-hop-neighborhood of the target future link. The value of k is selected based on the specific dynamic graph model; for explaining TGNNs, we set & equal to the number of layers in the TGNN, as contemporary TGNNs primarily aggregate information from events within this neighborhood (Yuan et al., 2021). Temporally, we retain only the Mmaz most recent events that satisfy the spatial constraint. We denote this constrained subset of past events as C(G, Si k; Mmaz). yielding the constrained search space Se::
Random A baseline policy that randomly ranks events for omission from the input graph, serving as com- parison against more structured strategies.
Temporal This policy ranks events based on their tem- poral distance from the explained event e,, assuming that more recent events have a greater influence on the model's prediction. The ranking function is defined as:
Ttemp (E)) = |t: -ty tzl
(4)
where 4; is the time of the future link event and Lj is the timestamp of the past event Ej. Events with smaller Ttemp (i.e., shorter temporal distance) are prioritized.
Spatio-Tempores This policy integrates both spatial proximity and temporal recency. Events are initially ranked by their spatial distance to the nodes involved in the explained event &,. Among events with the same spatial proximity, they are further ranked by temporal distance. The ranking function is:
k.mmne)l U
(C(g, Ess k, mmax)
Se. =
(3)
I
Search Tree Structure The search is guided by a partial search tree P. Each node represents removing a unique subset of past events from the original input graph. The root node Rroot corresponds to the original input graph without removing events, while other nodes represent the result of omitting past events from the graph. The depth of a node reflects the number of omitted events, with deeper nodes corresponding to more extensive modifications.
Tap-temple (E3) = (E) 14: - -(y)) (5)
where dapattial (Ej, et) is the shortest path distance be- tween the nodes of e, and e at time 4,
Event-Impact This policy evaluates the impac of omitting each event from the full input graph on the model prediction by measuring the change in predic- tion logits. The event impact for an event Ey is defined as the difference between the original prediction Porig
In contrast to search trees utilized for factual explana- tions (Xia et al., 2023; Yuan et al., 2021), the search tree
4

---

CoDy: Counterfactual Explainers for Dynamic Graphs
and the prediction py made when e is removed from the input graph. The ranking is determined by:
Algorithm 1 Search algorithm of CoDy.
Input: TGNN model f. input graph G, explained event Ei
selection policy 6, max iterations ifma
Poriy Pj. if Porig 2 0
(pPorig: Pj)
Output: best explanation found
Pj
Porigs
else
Porig ((G(t)),
Tooot f (0, (0,,l null, Ø, null, 1)
The search tree is first fully expanded at depth 1, ex- ploring the effects of separately removing each event in the search space C(G, St, k, mmaz), calculating A (Porig.P) for each event, and ranking events based on the magnitude of this change. Events with larger event impact the prediction are prioritized.
it + 0
while it < itmaas and Broot is selectable do
negelccted + select 5)
(selectedd: simulate (imulate(nscllcted: f, Es)
expand (1 zelected: (eaiectteddPPig))
backpropagate(pprrentie it + +1
Each selection policy offers a unique heuristic to guide the search. The Temporal and Spatio-Tempora policies leverage the structural properties of the graph by exploit- ing event timing and spatial relationships. In contrast, the Event-Impact policy directly measures the predictive influ- ence of individual events, allowing for more informed search based on the model's internal decision- decision-making pro- cess. These policies provide a diverse set of strategies to navigate the search space efficiently and effectively.
end
Tabest < select best(nroot)
return Sheat
algorithm. The process begins with the recursive selection of node in the search tree. In the depicted case, node ni is initially chosen due to its high score. Node n1 has three unexpanded child nodes, each without a score. Following the temporal selection policy, node n, is selected next. Since n4 has no child nodes, the recursion halts at this point. The simulation step then follows, where the model's output is inferred by perturbing the original input graph, omitting the events corresponding n2. After this, node n4 is assigned score based on the TGNN model's output. The node is then expanded to include its child nodes. Finally, the new score is backpropagated through the tree, updating the scores of all parent nodes until the root node Tyoot. In the following subsections, we provide an overview of these steps, with full details available in Appendix B.
4.2. GreeDy: Greedy Explainer on Dynamic Graphs
GreeDy is a search algorithm designed to find impactful counterfactual explanations by greedily exploring the search space. This exploration iteratively advances through the par- tial search tree P by selecting paths that result in the greatest immediate change in the TGNN's prediction. Appendix A details the full algorithm.
At each iteration, GreeDy evaluates subset of I child nodes, sampled based on a selection policy. The sampled child nodes are ranked based on their potential to cause a shift in the TGNN model's prediction, with priority given to nodes that yield the most significant change. The search continues until counterfactual example is found further exploration no longer produces meaningful shifts.
Selection Each search iteration begins by selecting a node for expansion, starting from the root and recursively travers- ing the tree. During this traversal, the algorithm evalu- ates and selects child nodes based on the selection score sel sel_score( which balances the need to explore new nodes and exploit known high-scoring ones:
The algorithm's output is the most impactful explanation dis- covered during the search, represented by the set of events whose omission causes the largest change in the model's prediction. This result can either be valid counterfactual example or simply the set of events with the greatest non- counterfactual impact on the model's prediction.
sel score((()))) = a score; + (1 at) score (1
The exploration score scoreezptore (ru) is derived from the 'Upper Confidence Bound 1' (Auer et al., 2002), encour- aging exploration, while scores denotes the exploitation score, reflecting the node's known potential to lead to counterfactual example based on the outcomes of previous simulations. The parameter E [0, 1] controls the trade-off between exploration and exploitation.
4.3. CoDy: Counterfactual Explainer on Dynamic Graphs
CoDy draws Monte Carlo Tree Search (Kocsis & Szepesvári, 2006), adapting its four key steps-Selection, Simulation, Expansion, and Backpropagation suit the search for counterfactual explanations in dynamic graphs. Algorithm provides a high-level overview of CoDy.
Simulation After selecting a node, the simulation step consists of inferring the prediction of the target TGNN
Figure 2 illustrates an example iteration within the CoDy
5

---

CoDy: Counterfactual Explainers for Dynamic Graphs
model using perturbed input graph. Specifically, events associated with the selected node nj are omitted from the original input graph, resulting in a new prediction Pj. This prediction is then used to compute the scorey:
5. Experiments
5.1. Experimental Setup
Datasets We evaluate on three datasets: Wikipedia (Ku- mar et al., 2019), UCI-Messages (Kunegis, 2013), and UCI- Forums (Kunegis, 2013). These datasets have diverse graph structures and event dynamics, allowing us to assess the generalizability of CoDy across different types of networks. The UCI datasets come from online social networks with- out node or edge features. Specifically, UCI-Messages is a unipartite graph of messages sent between students, while UCI-Forums is a bipartite graph of interactions between stu- dents and forums. The Wikipedia dataset consists of events representing edits made Wikipedia articles. It is bipar- tite, with edges associated with attributes that detail edits to Wikipedia articles. Appendix C supplements detailed statistics and discusses the diversity of these datasets.
0,
(pPorig Pi)
scorez < max
Pooign
A scorej >> 1 signifies that the perturbation set associated with n2 forms counterfactual example. In this case, this set of nodes is saved as a counterfactual example.
Expansion The expansion adds child nodes to the selected node. Following the definition of the search tree, each new child node is initialized with a set of events to omit from the input graph. The attribute score; of each added child node ni is set to null, indicating that these nodes are unexplored.
Target Models We evaluate two dynamic graph models: TGN (Rossi et al., 2020) and TGAT (Xu et al., 2020). Both are widely used in dynamic graph research (Souza et al., 2022: Chen & Ying, 2023; Xia et al.. 2023) and excel at capturing temporal patterns within dynamic graphs. They are considered state-of-the-art for various dynamic graph tasks (Rossi et al., 2020; Souza et al., 2022). Despite their predictive success, TGN and TGAT operate as black-box models, providing limited insight into how input features influence their predictions. Due to page limitations, the results for TGAT are presented only in Appendix E, as they closely resemble those for TGN.
Backpropagation The backpropagation recursively up- dates the search tree, starting from the parent node of the expanded node and proceeding until the root node. During this process, the exploitation and exploration scores are re- calculated. The exploration score score, of ng is updated as:
max 0,
A A(PorsonP3)) + (scores sels)
Porsal
MCE
scorej
selj
(9)
Configurations We train the TGN model using the "TGN- attn" configuration from the original paper (Rossi et al., 2020). The trained TGN model achieves high average precision scores (Transduetive/lndduttiv))) UCI-Messages 85.86%/83..0 26%; UCI-Forums 92.97% 939%%; Wikipedia 97. 97.80% 39%. The TGAT model achieves comparable performance: UCI-Messages 85. 15.1//082;000 UCI-Forums 91.31% Wikipedia 97.47%
Here, Cj refers to the child nodes of nt,, and sed, represents the total number of selections of node ny.
Explanation Selection Once the search tree is fully ex- panded or the maximum number of iterations is reached, CoDy selects an explanation. To minimize complexity, CoDy prioritizes counterfactual examples with the mini- mum number of events. If multiple candidates share this minimal size, the one inducing the largest change in the TGNN's prediction (as defined in Eq. 6) is chosen, reflect- ing the most decisive minimal explanation. If no valid counterfactuals are found, a fallback-strategy is applied, which selects the most informative perturbation set encoun- tered during the search, i.e., the one producing the greatest prediction shift according Eq.6.
Factual Baselines We adapt two factual explainers as baselines: PGExplainer (Luo et al., 2020) and T- GNNExplainer (Xia et al., 2023). Though PGExplainer was originally developed for static graphs, it provides a valuable comparative perspective when adapted to dynamic contexts. We apply it with fixed explanation sparsity of 0.2. T-GNNExplainer designed for Temporal Graph Neu- ral Networks and operates at the event level, making an ideal baseline for methodology. We follow its original specifications, using 500 iterations and 30 candidate events. While TempME (Chen & Ying, 2023) also explains TGNNs, it has a fundamentally different bosee- approach and limited comparability with our event-level counterfactual explanation framework. The authors primarily report neg-
To enhance search efficiency, CoDy incorporates several optimization techniques: constraints are applied to mini- mize explanation complexity, caching mechanisms are uti- lized to reduce redundant calculations, and a two-stage cenoxiiaatioooonfimattit approach is implemented to expedite inference during search.
6

---

CoDy: Counterfactual Explainers for Dynamic Graphs
Table Results for the AUFSC-. and char scores of different explanation methods applied to the TGN model. Results are reported for three datasets: UCI- UCI-Messages (msg.), UCI-Forums (for.), and Wikipedia (wiki... The best result for each experimental setting shown bold, and the second best underlined.
AUFSC+
AUFSC-
char
Correct
Incorrect
Correct
Incorrect
Correct for.
Incorrect
Dataset
msg.
for.
wiki.
mag.
for:
wiki.
msg.
for.
wiki,
msg.
for
wiki.
msg.
wiki.
msg.
for.
wiki.
PGExplainer
0.02
0.03
0.03
0.08
0.04
0.11
0.39
0.35
0.67
0.61
0.67
0.54
0.05
0.07
0.09
0.17
0.08
0.22
T-GNNExplainer
0.05
0.03
0.01
0.14
0.19
0.10
0.45
0.36
0.61
0.53
0.49
0.43
0.17
0.08
0.09
0.39
0.40
0.34
GroeDy-rand.
0.02
0.05
0.04
0.07
0.06
0.10
0.33
0.27
0.53
0.95
0.97
0.91
0.01
0.09
0.14
0.12
0.19
GreeDy-teng
0.13
0.41
0.08
0.32
0.30
0.29
0.52
0.58
0.72
0.95
0.95
0.87
0.22
0.50
0.17
0.49
0.47
0.45
0.19
0.44
0.12
0.37
0.29
0.37
0.64
0.60
0.76
0.93
0.91
0.85
0.31
0.53
0.23
0.54
0.16
0.54
GrveDD--entt-ippe
0.10
0.28
0,07
0.31
0.26
0.27
0.62
0.61
0.67
0.95
0.96
0.88
0.18
0.39
0.14
0.51
0.42
0.43
Co rand.
0.10
0.30
0.12
0.34
0.30
0.41
0.63
0.59
0.82
0.91
0.92
0.82
0.19
0.43
0.24
0.52
0.47
0.58
CoDy temp..
0.13
0.36
0.11
0.38
0.36
0.46
0.64
0.58
0.83
0.92
0.93
0.84
0.23
0.49
0.22
0.55
0.54
0.62
CoDy-spa-temp.
0.19
0.43
0.16
0.39
0.35
0.50
0.67
0.63
0.84
0.92
0.90
0.82
0.31
0.54
0.30
0.57
0.52
0.65
CoDy-evnt-lnper
0.38
0.40
0.39
0.52
0.61
0.92
0.85
0.27
0.27
0.58
0.57
0.68
ative scores, suggesting explanations that preserve model predictions, instead of altering them. Additionally, the pro- vided code is incomplete. We thus decided not to include TempME baseline.
In contrast, fid, assesses if removing the identified fea- tures changes the model's prediction, thus capturing the necessity (Amara et al., 2022). We assess the relationship between fidelity and sparsity by calculating the Area Un- der the Fidelity-Sparsity Curve (AUESC) as AUFSC+ and AUFSC-, respectively. We also report the Character- ization Score char, which is the harmonic mean of fid_ and fid+ (Amara et al., 2022), and provides an integrated assessment of sufficiency and necessity.
Counterfactual Explainers We configure GreeDy with candidate event limit of 64, sampling up to 10 events per iteration. For CoDy, we also limit the search space to 64 events, with a maximum of 300 iterations and a to emphasize exploration over exploitation. Appendix shows a sensitivity analysis on these parameters.
Qane
Formal definitions of the metries are provided in Appendix D. Appendix F provides additional evaluations explainer runtime, the impact of search iterations, and the similarities between explanations from different explainers. Positive results further highlight CoDy's strong performance.
Explained Instances Recognizing that explanations can differ between correct and incorrect predictions (Amara et al., 2022), we separately evaluate instances where the TGNN makes correct versus incorrect predictions. This distinction allows for a more comprehensive assessment of the robustness and reliability of explanation methods across different prediction outcomes.
5.3. Results
5.3.1. NECESSITY OF EXPLANATIONS
Table 1 presents a comprehensive overview of the AUFSC+ scores in various experimental scenarios. CoDy generally achieves the highest AUFSC+ scores, except for correct pre- dictions in the UCI-Forums dataset, where GreeDy-spatio- temporal (0.44) narrowly exceeds the result of CoDy-spatio- temporal (0.43). This hightlights the proficiency of CoDy in providing concise necessary explanations. We observe consistent trend of CoDyy-sputio-temporrl excelling in explaining correct predictions, while CoDy-event-inge -impettt performs better in elucidating incorrect predictions, albeit by minor margins (0.01-0.04). This hints at the higher im- portance of events that are spatially and temporally close to a correctly predicted future link, whereas for incorrect predictions, this seems to be of slightly less importance, For GreeDy, the spatio-temporal selection policy generally yields the best results. In general, factual baselines show poor performance in AUESC, scores; T-GNNExplainer, despite being specifically developed for TGNNs, averages 75.05% lower than the tor-performing explainer, CoDy- spatio-temporal.
5.2. Evaluation Framework
Factual and counterfactual explanations inherently address different aspects of model predictions. Factual explanations aim to identify the sufficient information for a prediction, while counterfactual explanations focus on identifying the necessary information (Tan et al., 2022). Our evaluation framework thus comprises metrics that allow a nuanced eval- uation of necessity and sufficiency. Sparsity measures the complexity of an explanation by measuring the proportion of utilized features relative to the total number of available features. Sparsity scores range from 0 to 1, with lower scores indicating more concise explanations. Fidelity mea- sures how effectively an explanation identifies key input characteristies that drive predictions. Based the defi- nitions of the probability of necessity and the probability of sufficiency introduced by Tan et al. (2022), we adopt two fidelity metrics, fid_ and fid,. fid. measures how well the explanations capture sufficient features required so that the predictions remain unchanged (Amara et al., 2022).
The disparity between explanations for correct and incor-
7

---

CoDy: Counterfactual Explainers for Dynamic Graphs
JCI-Messages
UCI-Forums
Wikipedia
0.6
0.6
0.6
CoDy GreaDy
sonahue
fid.
0.4
fid.
0.4
fid.
0.4
temponal
0.2
0.2
0.2
event impact
T-GNNExpphiner
0.2 0.4 0.6 0.8
0.2
0.4
0.6
0.8
1
0.2
0.4
0.6
0.8
1
sparsity
sparsity
sporsity
Figure 3. Cumulative fid, score relative to an upper sparsity limit for incorrect predictions with TGN as target model. PGExplainer excluded since it is assessed with fixed sparsity.
rect predictions is particularly pronounced in UCI-Messages and Wikipedia. All explainers identify necessary explana- tions for incorrect predictions more than twice as often as for correct ones. This suggests a fundamental difference between correct and incorrect predictions. For incorrect predictions, the model tends to misinterpret past informa- tion, making explanations easier to identify. In contrast, identifying a counterfactual example for correct predictions requires omitting information to render the prediction incor- rect, which can be challenging if most past data align with the prediction. Despite this, explaining incorrect predictions is often more insightful, as it reveals misleading input fea- tures and uncovers model limitations. This understanding can inform model improvements and enhance robustness by highlighting areas where the model is vulnerable. Addition- ally, focusing incorrect predictions allows for clearer examination of the decision-making process, revealing po- tential biases and providing actionable insights for refining the model.
5.3.2. SUFFICIENCY OF EXPLANATIONS
Analyzing the sufficiency of the explanations through the AUFSC_ score, shown in Table 1, reveals that CoDy consistently achieves high scores of over 0.82 for incorrect predictions and 0.58 for correct predictions, indicating that the generated explanations fulfill the sufficiency criteria to a high degree. Among CoDy variants, performance remains notably stable across different settings, with only minor differences observed.
Although factual methods are expected to achieve better AUFSC_ scores, as they aim to identify sufficient explana- tions for predictions (Tan et al., 2022), PGExplainer and T-GNNExplainer do not consistently outperform their coun- terfactual counterparts. While T-GNNExplainer achieves impressive fid_ scores of 0.82 and 0.9 for correct predic- tions in UCI-Messages and Wikipedia, it generally falls behind CoDy and GreeDy in AUFSC_. This inconsistency may be attributed to specific implementation details in T- GNNExplainer, particularly an approximation used in model calls, as noted by its original authors (Xia et al., 2023). Such approximations may hinder its ability to fully capture suffi- cient explanations.
The superior performance of CoDy further illustrated in Figure 3, which shows the fid+ score achieved with explanations up to given sparsity level. At sparsity 1, all necessary explanations are considered. All CoDy vari- ants, especially spatio-temporal and event-impact, exhibit a rapid increase in fid, at low sparsity levels, highlight- ing CoDy's effectiveness in delivering concise explanations. T-GGNEExpliine fails to achieve comparable performance, even at high sparsity levels, as it often neglects the most critical features relevant the model's predictions.
Overall, the strong performance of CoDy and GreeDy under- scores their effectiveness in providing concise yet impactful explanations, demonstrating that counterfactual methods excel not only in necessity but also in sufficiency.
5.3.3. CONVERGENT ANALYSIS
Overall, CoDy, particularly with the spatio-tempord and event-impact policies, excels at balancing the dual objec- tives of maximizing counterfactual example discovery and minimizing explanation complexity. Unlike GreeDy, which rigidly follows its initial search direction, CoDy dynamically adapts to information gathered during search. Although GreeDyy may occasionally outperform CoDy when its early path aligns with the optimal solution, CoDy's i flexibility gen- erally leads to better results. Further experiments show that CoDy's performance can be further improved by increasing search iterations (see Appendix F.3) and hyperparameter tuning (see Appendix G).
The characterization score char synthesizes the dimensions of sufficiency and necessity into single score. Table I presents the explainers' performance along this metric. No- tably, CoDy-event-impact excels in explaining incorrect predictions, whereas CoDDy-patio-tempoor is superior for correct predictions. The AUFSC+ and AUFSC- scores re- veal that CoDy-event-impact and CoDyy-paaio-tempordd not only deliver excellent explanations in terms of necessity but also maintain comparably strong sufficiency. This under- scores the significance of the fallback strategy, ensuring the provision of explanations even in the absence of counter- factual examples. These fallback explanations still deliver
8

---

CoDy: Counterfactual Explainers for Dynamic Graphs
mostly sufficient explanations. Thus, even though not all explanations counterfactual, they consistently highlight pertinent input information.
6. Conclusion
In this paper, we introduced CoDy, a counterfactual explana- tion method tailored for Temporal Graph Neural Networks (TGNNs) operating on Continuous-Time Dynamic Graphs. CoDy adapts Monte Carlo Tree Search to generate con- cise and actionable explanations. Our extensive evaluation demonstrates that CoDy outperforms existing factual expla- nation methods, such as PGExplainer and T-GNNExplainer, as well as GreeDy, a novel counterfactual baseline based on greedy search. We further show that incorporating spatio- temporal and event-impact information effectively guides the search process, significantly enhancing the quality of counterfactual explanations for TGNNs.
5.3.4. COMPARISON OF SELECTION POLICIES
Selection policies significantly impact the performance of GreeDy and CoDy. The random policy yields the poorest results for either method. For GreeDy, applying the tempo- ral selection policy improves the AUFSC+ score by 386% on average, while the spatio-temporal and event-impact policies yield improvements of 485% and 304%, respec- tively, over the random policy. CoDy exhibits a similar trend, albeit with smaller average improvements: 14.3% for temporal; 7% for spatio-temporal; 29.6% for event- impact. This underscores the importance of spatial and temporal information for explanations. Across all tasks, sapyy--paioo-teporal outperforms the strongest baseline (i.e.,
While our evaluation confirms CoDy's ability to identify compact counterfactual examples, future work could inves- tigate its practical utility through user studies in real-world applications. Additionally, although CoDy currently focuses on generating explanations by removing graph components, it could be extended to also support operations such as adding nodes or edges, modifying features, or adjusting event timestamps. These extensions would substantially enlarge the search space, necessitating the development of new strategies to manage the increased complexity.
by 16% in AUFSC+.
The results demonstrate that CoDy robustly adapts its search based on initial results, exploring different paths if necessary. GreeDy adheres to its initial path, making it more reliant on the selection policy and susceptible to local optima.
Overall, the evaluation shows that CoDy consistently out- performs baseline methods, validating its effectiveness in generating factual and counterfactual explanations. This approach not only improves the identification of necessary and sufficient information but also shows the importance of leveraging spatio-temporal and event-impact insights to effectively navigate the complex search space.
Despite these challenges, CoDy and its selection policies of- fer strong potential to advance the interpretability of TGNNs. By providing deeper insights into model decisions, CoDy can support the adoption of TGNNs in high-stakes domains such as finance, healthcare, and scientific research.
Impact Statement
5.3.5. PRACTICAL CONSIDERATIONS
This work contributes to the broader goal of interpretable machine learning by introducing novel counterfactual explanation method for temporal graph neural networks (TGNNs). As TGNNs are increasingly applied in high- stakes domains, such as finance and healthcare. CoDy pro- vides actionable, modellaagostic explanations that can help users trust, debug, and audit temporal models. This work promotes transparency in evolving decision environments and may serve as a foundation for future human-in-the-loop or regulatory-compile AI systems.
In practice, CoDy emerges as the most robust and reli- able choice. While it may require more computation when searching for minimal sparsity, its performance remains consistent across diverse scenarios. A practical implemen- tation can significantly reduce runtime by terminating the search upon finding the first valid counterfactual, while still retaining CoDy's 'ss strong explanatory capabilities.
If computational efficiency and rapid explanation genera- tion are the primary concerns, GreeDy offers a compelling, faster alternative. It can yield good results quickly, espe- cially when its initial greedy choices align with an effective counterfactual path. However, this speed comes at the cost of a higher risk of suboptimal explanations and greater likelihood of getting stuck in local optima.
Acknowledgements
The authors acknowledge support from the state of Baden- Württemberg through bwHPC and conducted substantial parts of this work at the Karlsruhe Institute of Technology. This work was funded by the Federal Ministry of Education and Research of Germany and the Saxon State Ministry for Science, Culture, and Tourism as part of the Center for Scalable Data Analytics and Artificial Intelligence Dres- den/Leipzig (ScaDS.AI, project ID: SCADS24B).
The spatio-temporal selection strategy is the most suitable choice for real-world applications where ground-truth labels are not available. It performs best on correct predictions- which are most common in properly functioning TGNNs- and only slightly underperforms the event-impact policy when explaining incorrect predictions.
9

---

CoDy: Counterfactual Explainers for Dynamic Graphs
References
Kazemi, S. M., Goel, R., Jain, K., Kobyzev, I., Sethi, A.,
Forsyth, P., and Poupart, P. Representation learning for dynamic graphs: A survey, J. Mach. Learn. Res., 21: 70:1-70:73, 2020.
Amara, K., Ying, Z., Zhang, Z., Han, Z., Zhao, Y., Shan, Y., Brandes, U., Schemm, S., and Zhang, C. Graphframex: Towards systematic evaluation of explainability meth- ods for graph neural networks. In Learning on Graphs Conference, LoG 2022, 9-12 December 2022, Virtual Event, volume 198 of Proceedings of Machine Learning Research, pp. 44. PMLR, 2022.
Kocsis, L. and Szepesvári, C. Bandit Based Monte-Carlo Planning. In Fürmkranz, J., Scheffer, T., and Spiliopoulou, M. (eds.), Machine Learning: ECML 2006, Lecture Notes in Computer Science, pp. 282-293. Springer, 2006. ISBN 36--3-540-46056-5
Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2))235-256, 2002. ISSN 1573-0565.
Kovanen, L., Karsai, M., Kaski, K., Kertész, J., and Saramäki, Temporal motifs in time-dependent net- works. Journal of Statistical Mechanics: Theory and Experiment, 2011(11):P11005 2011.
Baldassarre, and Azizpour, H. Explainability tech- niques for graph convolutional networks. In International Conference on Machine Learning (ICML) Workshops, 2019 Workshop on Learning and Reasoning with Graph- Structured Representations, 2019.
Kumar, S., Zhang, X., and Leskovec, Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 1269-1278, ACM, 2019.
Byrne, R. M. J. Counterfactuals in Explainable Artificial Intelligence (XAI): Evidence from Human Reasoning. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pp. 6276-6282, 2019.
Kunegis, J. KONECT - The Koblenz Network Collection. In Proc. Int. Conf. on World Wide Web Companion, pp. 1343-1350, 2013.
Chen, J. and Ying. Z. Tempme: Towards the explainability of temporal graph neural networks via motif discovery. In Thirth-seventh Conference on Neural Information Pro- cessing Systems, 2023.
Li, W., Li, Y., Li, Z., HAO, J., and Pang, Y. DAG matters! GFlownets enhanced explainer for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.
Fan, Y., Yao, Y., and Joe- Wong, C. Gen-se: explainability for node classification in dynamic graphs In 202/ IEEE International Conference on Data Mining (ICDM), pp. 1060-1065 IEEE Computer Society, 2021.
Attention as
Liu, Y. L., Zhang, X., and Xie, S. A differential geometric view and explainability of gnn on evolving graphs. In The Eleventh International Conference on Learning Rep- resentations (ICLR 2023). International Conference on Learning Representations, 2023.
Han, Z., Chen, P., Ma, Y., and Tresp, V. Explainable sub- graph reasoning for forecasting on temporal knowledge graphs. In International conference on learning represen- tations, 2020.
Longa, A., Lachi, V., Santin, G., Bianchini, M., Lepri, B., Lio, P., Scarselli, F,, and Passerini, A. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. Transactions on Machine Learning Research, 8, 2023.
He, W., Vu, M. N., Jiang, Z., and Thai, M. T. An explainer for temporal graph neural networks. In IEEE Global Communicatioon Conference, GLOBECOM 2022, Rio de Janeiro, Brazil, December 4-8, 2022, pp. IEEE, 2022.
Lucic, A., ter Hoeve, M. A., Tolomei, G., de Rijke, M., and Silvestri, F. Cf-gnnexplainer: Counterfactual ex- planations for graph neural networks. In International Conference on Artificial Intelligence and Statistics, AIS- TATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pp. 1499-4511 PMLR, 2022.
Huang, Q. Yamada, M., Tian, Y., Singh, D., and Chang, Y. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering. 35(7):6968-699 06726,9722222 2022.
Luo, D.,, Cheng, W., Xu, D., Yu, W., Zong, B., Chen, H., and Zhang, X. Parameterized explainer for graph neural network. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020
Huang, S., Poursafaei, F., Danovitch, J., Fey, M., Hu, W., Rossi, E., Leskovec, J., Bronstein, M., Rabusseau, G., and Rabbany, R. Temporal graph benchmark for ma- chine learning on temporal graphs. Advances in Neural Information Processing Systems, 36, 2024.
10

---

CoDy: Counterfactual Explainers for Dynamic Graphs
Miao, S., Liu, M., and Li, P. Interpretable and generaliz- able graph learning via stochastic attention mechanism. In International Conference Machine Learning, pp. 15524-15544 PMLR, 2022.
Vu, M. N. and Thai, M. T. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Process- ing Systems 2020, NewrIPS 2020, December 6- 12, 2020, virtual, 2020.
Pope. P. E., Kolouri. S., Rostami, M., Martin, C. E... and Hoffmmann, H. Explainability methods for graph convolu- tional neural networks. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pp. 10772-10781. Computer Vision Foundation/ IEEE, 2019.
Xia, W., Lai, M., Shan, C., Zhang, Y., Dai, Li, X., and Li, D. Explaining temporal graph models through an explorer-navigator framework. In The Eleventh Interna- tional Conference on Learning Representations. 2023.
Prado-Romero, M. A., Prenkaj. B., Stilo, G., and Giannotti, F. A survey on graph counterfactual explanations: defini- tions, methods, evaluation, and research challenges. ACM Computing Surveys, 56(7):1-37, 2024.
Xu, D.., Ruan, C., Körpeoglu, E., Kumar, S., and Achan, K. Inductive representation learning on temporal graphs. In 8th International Conference on Learning Represen- tations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net 2020.
Prenkaj. B., Villaizán-Valleladd, M., Leemann, T., and Kas- neci, G. Unifying evolution, explanation, and discern- ment: A generative approach for dynamic graph coun- terfactuals. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.
Ying. Z., Bourgeois, D., You, J., Zitnik, M., and Leskovec, J. Gnnexplainer: Generating explanations for graph neural networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pp. 9240-9251, 2019.
2024.
Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., and Bronstein, M. Temporal graph networks for deep learning on dynamic graphs. CoRR, abs/2006.10637 10637, 2020.
Yu, L., Sun, L., Du, B., and Lv, W. Towards better dynamic graph learning: New architecture and unified library. Ad- vances Neural Information Processing Systems, 36: 67686-67700, 2023.
Schnake, T., Eberle, O., Lederer, J., Nakajima, S., Schütt, K. T., Müller, K.-R., and Montavon, G. Higher-order explanations of graph neural networks via relevant walks. IEEE transactions on pattern analysis and machine intel- ligence, 44(11):7581-7555 2021.
Yuan, H., Tang, J., Hu, X., Ji, S. XGNN: towards model- level explanations of graph neural networks. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pp. 430 438. ACM, 2020.
Shan, C., Shen, Y., Zhang, Y., Li, X., and Li, D. Rein- forcement learning enhanced explainer for graph neural networks. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NewrlPS 2021, December 6-14, 2021, virtual, pp. 22523-22533, 2021.
Yuan, H., Yu, H.,, Wang, J., Li, K., and Ji, S. On explainabil- ity of graph neural networks via subgraph explorations. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 12241-12252. PMLR, 2021.
Souza, A., Mesquita, D., Kaski, S., and Garg, V. Provably expressive temporal graph networks. Advances in neural information processing systems, 35:32257-32269, 2022.
Yuan, H. Yu, H., Gui, S., and Ji, S. Explainability in graph neural networks: A taxonomic survey. IEEE Trans. Pattern Anal. Mach. Intell., 45(5):5782-5799, 2023.
Stanley, R. P. Enumerative Combinatorics. Springer US
Zhao, L., Song, Y., Zhang, C., Liu, Y., Wang, P., Lin, T., Deng, M., and Li, H. T-gen: A temporal graph convolu- tional network for traffic prediction. IEEE transactions intelligent transportation systems, 21(9))3848-33 -8588, 2019.
Boston, MA, 1986. ISBN 978- 778-1-4615-9765-0 978-1- 4615-9763-6.
Tan, J., Geng, S., Fu, Z., Ge, Y., Xu, S., Li, Y., and Zhang, Y. Learning and evaluating graph neural network expla- nations based on counterfactual and factual reasoning. In wWW 22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pp. 1018-1027. ACM, 2022.

---

CoDy; Counterfactual Explainers for Dynamic Graphs
A. Details of the GreeDy Algorithm
A GreeDy search algorithm for counterfactual examples.
Input:
TGNN model f. input graph G, explained event E₁ selection policy 5, number of events to sample in each iteration 7 Output: best explanation found X'
Porig + =((((t)),
Troot + (0, Porig: null, 2)
Mbest t- -rroots
while Sbeat does not include all candidate events C(G, ki Mmaar) do childrenbest <- set of child nodes with highest rank according to 6, each child Rehita initialized with prediction
Pehild = f((g(t,)) (e Aebeatchhldd + arg max,, Echildrenees A (porig Py) if A (poeats Pbest.chaa) > then
Robst.child shi the predicti cediction further towards the opposite sign the ori ori griginal
prediction
Whest
Abest_child if ApPorig Phest) > Porigl then Shest a countersacte example
break
end
else
break
end
end
return Shest
Figure 4 depicts the operation of GreeDy. Each iteration involves selecting three past events (7 = 3) using policy 8. Starting from the root node, node n2 is chosen as the best node (Nbest) in the first iteration, with a perturbation set 82 $2 and a prediction score of 1.996. As iterations proceed, the prediction score of libest decreases until becomes negative in third iteration. At this point, the search ends, yielding the counterfactual example X 8g = E2, E1,
Nyoot
Initialization:
Phest + Broot predorig 2.854
Aleest +- 112
Iteration 1:
n2
133
predbest = 1.996
Sbest {52)
Abest f 114
Iteration 2:
71.
T1
predbest = 0.816
Sbest {E2,
Wbest
Iteration 3:
mS
Tig
predicat -0.052
Sbeat (E2, E1, 55]
Figure 4. Example the operation of the GreeDy approach.
12

---

CoDy; Counterfactual Explainers for Dynamic Graphs
B. Details of the CoDy Algorithm
CoDy models nodes the search tree as tuples. A node nj defined by the tuple:
"l ($j, parent,, seleeddion selections,, scorej, selectables)
(10)
sy denotes the perturbation set (i.e., set past events) associated with ny. parent, denotes the parent node in the search tree, while childreny denotes the set of child nodes in the search tree. selections, is an integer value that tracks how often the specific node has been selected. selectable; indicates whether the node is still considered for selection (for example, it does not make sense to select node that already constitutes counterfactual example, since its child nodes only contain counterfactual examples with higher complexity).
Algorithm 3 shows the recursive child node selection process. Child nodes are first ranked by their selection and ties in this score are broken using a selection policy
Algorithm 3 Recursive selection algorithm.
Function select(n,, 8)
ny not yet expanded then return ny; end
Whest +- arg máX selectable.chhlddreeeny sel_score(ms) if there is more than one child with the highest selection
score then
Rhest highest ranking child node according to selection strategy 6
end
return select(n6ee)
end
The simulation algorithm (Algorithm consists of calling the explained TGNN to predict the score for the future link given the input graph without the events s, associated with the selected node ni-
Algorithm Algorithm for simulating the link prediction on the selected node.
Function simulate(ng, J, G, e;): Pj + f((G(t.) ss)), return end
Algorithm 5 showcases the expansion process. First, values for selections; and score, are set for the selected node ni-- Second, depending on whether s, constitutes counterfactual example the node is added to the list of counterfactual examples, or expanded further. This expansion entails adding all possible child nodes with initial null values.
Algorithm 5 Function for expanding the selected node.
Function expand(n.. njj Porig): :
selections, + score, f- max (o, A(Porig:Ps)
[Porill
if scorej > 1 then
selectable Add n, a list of counterfactual examples ef Lezamples else
children, +- [(*x, rull, ny. 0,0, null, 1) ax E Se, with [sa| [s51 + 1,85 C cak if chuldren, = 2 then selectable 0 end
end end
The backpropagartion algorithm (Algorithm 6) recursively updates the score,, selections,, and selectable, values each traversed node ny.
13

---

CoDy; Counterfactual Explainers for Dynamic Graphs
Algorithm 6 Backpropagation function that recursively updates the information of nodes in the search tree.
Function backpropagate(n;))
nn null then return end
selections; + selections; + 1 score; + max (0,
Pp [Povial
score; + score; + Echildreenn (score:
selections)) scorej acore, seleclable, sciectionsy end end
if No child in children, is selectable then
C. Dataset Statistics
The explainers evaluated on three different datasets. These datasets diverse in terms of their size, their structure, and the temporal density of events, aiming to verify that the explanation approaches perform similarly different datasets.
Table 2 provides an overview of the key statistics datasets. The two datasets from the UCI social network cover a longer timespan and are more sparse the temporal dimension than the Wikipedia dataset. Another substantial difference is that, contrast to the other datasets, the UCI-Messages dataset contains a relatively high number of unique edges compared to the number of total edges. Furthermore, the UCI-Messages and UCI-Forums datasets have proportionally fewer multi-edges compared to the Wikipedia dataset.
Table 2. Statistics for datasets
Nodes
Edges
Unique Edges
Timespan
Graph Type
"CI-Messsgess (Kunegis, 2013)
1,899
59,835
20,296
196 days
Unipartite
UCI-Forums (Kunegis, 2013)
1,421
33,720
7,089
165 days
Bipurtite
Wikipedia (Kumar et al., 2019)
9,227
157,474
18,257
30 days
Bipartite
14

---

CoDy: Counterfactual Explainers for Dynamic Graphs
D. Evaluation Framework
evaluate the explanation methods using sparisty, AUTS
char.
Sparsity: Sparsity is a widely used metric to gauge the complexity of explanations (Prado-Romero et al., 2024; Yuan al., 2023; Amara et al., 2022), capturing how well the complexity of explanations is minimized. We define it as the mean ratio between the size of explanations (X,, and the size of the full set of candidate events |C(g, Exy Mmnar)
1 N
sparsity
(11)
C(g, Cay kt Mmaz)
The fidelity metrics capture how well the explanations capture pertinent events. Since we comparing factual and counterfactual explainers we adapt the definions for the probability of sufficiency and the probability of necessity introduced by Tan et al. (2022) and map them to two fidelity metrics, fid+ and fid-, for the context temporal graphs. In line with the definitions of Amara et al. (2022) we assess fidelity with regards to the predictions of the model, not in regards to the ground truth labels. This is sometimes termed "correctness" or "validity" Prado-Romero al. (2024).
Fidelity:
fid
Σ (() e(),,,,; N
1
(12)
fid, =
e) p(S(((()) (.)),
(13)
N
In these equations, &N represent the explained future links in an experiment, and X :..,.., Kxy denote their corre- sponding explanations. The indicator function I(a 6) returns equals otherwise, it returns 0. Based on the fidelity scores we calculate AUFSC and AUFSC_ by integrating over the -idelity-pparsity curve.
Characterization Score: by Amara et al. (2022):
To jointly assess necessity and sufficiency, adopt the characterization char introduced
W4+ + Fid,
char
(14)
Jid.
Here, w4 and w. are weights for fid, and fid- that allow putting more emphasis on either sufficiency or necessity. make fair comparison between the counterfactual explainers and the factual baselines, the weights are set W4 w. 0.5. The characterization score char takes values between 0 and where larger values indicate better performance.
15

---

also finds more CoDy: Counterfactual Explainers for Dynamic Graphs
E. Evaluation of Explanation Methods Applied to TGAT
When explaining the TGAT model (Xu et al., 2020) we find similar results to the findings on TGN, The results presented in Table 3 show the counterfactual explanation methods GreeDy and CoDy outperforming the factual baseline T-GNNExplainer regarding sparsity, fid+ and the chor score. T-GNNExplainer faires better regarding the fid_ metric, achieving the highest score for correct predictions in the UCI-Messages (0.76) and the Wikipedia (0.87) dataset. In the other settings, the counterfactual explainers achieve better results.
The main difference in the performance of GreeDy and CoDy is that with the evaluated settings, GreeDy-spatio-temppe nearly outperforms all CoDy variants regarding fid+ on the UCIIMMssagess dataset. Looking at the relationship between [id+ and sparsity in Figure 5 shows the reason for the limited performance of CoDy in these settings: While GreeDy and CoDy variants find similar amount of necessary explanations with low sparsity, SreelDy-spatio-terr counterfactual examples with higher sparsity. The fact that CoDy does not elucidate explanations with larger sparsities to similar degree suggests that the explainer is configured sub- sub-optimally. We investigate this further in the sensitivity analysis performed in G and show that changing the balance between exploration and exploitation through parameter and increasing the candidate size maar can boost the performance of CoDy without increasing search iterations.
Table Results on the fidelity+. sparsity, fideiiyy and char scores of the different explanation methods for explaining correct and incorrect predictions for the TGAT larget model. The best result for each experimental setting bold, and the second best is underlined.
Fidelity+
Sparsity
UCI-Messages
UCI- Forums
Wikipedia
UCI-Messe ICI-Messages
UCI-Forums
Wikipedia
corr.
wrg.
corr.
wrg.
coTr.
wrg.
corr.
wrg.
corr.
wrg.
corr.
wrg.
T-GNNExplainer
0.14
0.08
0.11
0.19
0.08
0.24
0.36
0.29
0.03
0.26
0.25
0.39
GyeeDy-rand.
0.06
0.08
0.21
0.18
0.05
0.11
0.1
0.04
0.07
0.08
0.04
0.02
GreeDy-temp:
0.17
0.26
0.42
0.36
0.10
0.30
0.07
0.04
0.05
0.05
0.06
0.03
GreeDy-spu-temp.
0.38
0.34
0.47
0.39
0.11
0.05
0.06
0.05
0.07
0.04
GreeDy-event-mmmect
0.22
0.29
0.31
0.33
0.08
0.28
0.11
0.07
0.09
0.09
0,05
0.02
CoDy-rand
0.17
0.26
0.38
0.34
0.15
0.35
0.03
0.04
0.22
0.06
0.08
0.05
CoDy-temp.
0.19
0.30
0.46
0.37
0.18
0.35
0.03
0.04
0.13
0.05
0.08
0.04
CoDy-spa-temp.
0.32
0.33
0.56
0.35
0.18
0.35
0.05
0.04
0.08
0.04
0.08
0.04
E-Dy-event-impac
0.24
0.32
0.48
0.34
0.18
0.41
0.04
0.05
0.21
0.06
0.08
0.05
Fidelity-
Char
UCI-Messages
UCI- Forums
Wikipedia
UCI-Messages
UCI- Forums
Wikipedia
corr.
inc.
corr.
inc.
inc.
corr:
inc.
corr.
inc.
corr.
inc.
T-GNExplaiinr
0.76
0.91
0.46
0.50
0.87
0.84
0.24
0.14
0.17
0.03
0.14
0.38
GreeDy-ramd
0.39
1.00
0.49
0.97
0.57
0.93
0.10
0.15
0.29
0.30
0.09
0.19
GreeDy-temp.
0.57
1.00
0.67
0.77
0.90
0.26
0.41
0.51
0.53
0.17
0.45
GreeDy-spa-temy
0.32
1.00
0.69
0.95
0.82
0.88
0.48
0.50
0.56
0.51
0.23
0.54
GreeDy-event-impact
0.66
1.00
0.69
0.98
0.72
0.90
0.32
0.44
0.43
0.49
0.14
0.43
CoDy-rand.
0.66
1.00
0.76
0.96
0.81
0.97
0.26
0.41
0.51
0.50
0.25
0.51
CoDy-temp.
0.65
1.00
0.76
0.98
0.83
0.97
0.29
0.46
0.57
0.54
0.29
0.51
CoDy CoDy-spa-temp.
0.61
1.00
0.77
0.95
0.83
0.96
0.42
0.50
0.65
0.51
0.29
0.51
Col CoDy-event-imparr
0.66
1.00
0.77
0.97
0.83
0.97
0.35
0.48
0.59
0.50
0.30
0.58
16

---

CoDy; Counterfactual Explainers for Dynamic Graphs
Correct predictions
Wrong predictions
UCI-Messages
0.4
0.4
fid.
fid
0.2
0.2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
sparsity
sparsity
Correct predictions
Wrong predictions
0.6
0.6
UCI- -ol-Forums
0.4
0.4
fid.
fid+
0.2
0.2
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
sparsity
spersity
Correct predictions
Wrong predictions
Wikipedia
0.4
fid.
fid+
0.2
0.2
0.2
0.4
0.6
0.8
0.4
0.8
sparsity
sparsity
random temporal spatio-temporal event-impact no selection strategy
CoDy
GreeDy
T-GNNExplainer
Figure 5. Results on the relationship between fid, and sparsity under different experimental settings for the TGAT model.
17

---

CoDy; Counterfactual Explainers for Dynamic Graphs
F. Extended Evaluation of Explanation Methods Applied to TGN
supplement our analysis the evaluation of our explanation approaches with further results extracted from explaining predictions by the TGN model. Detailed results on the fidelity and sparsity scores are depicted in Table The results on fidelity largely overlap with the results in AUFSC.
Figure 7 shows the relationship between fid+ and sparsity for correct predictions. On the UCI-Forums dataset, we see the only setting where GreeDy variant outperforms all CoDy variants. In F.3, we show that increasing the number of search iterations leads to Co outperforming GreeDy in this setting as well.
Table Results on the fidelity+. sparsity, fidliiyy and char scores of the different explanation methods for explaining correct and incorrect predictions. The best result for each experimental setting is bold, and the second best is underlined.
Fidelity+
Sparsity
UCI- -Cs-Messages
UCI-Forums
Wikipedia
UCI-Messagee
UCI-Forums
Wikipedia
wrg.
wrg.
wrg.
wrg.
wrg.
wrg.
PGExplainer (Luo et al., 2020)
0.03
0.10
0.04
0.05
0.05
0.13
0.20
0.20
0.20
0.20
0.20
0.20
T-GNNEExpliine (Xia et al., 2023)
0.10
0.25
0.05
0.28
0.05
0..2
0.43
0.35
0.29
0.35
0.33
0.43
GreeDy-random
0.02
0.08
0.05
0.07
0.05
0.11
0.03
0.02
0.02
0.02
0.04
0.02
GreeDy-temporal
0.14
0.33
0.31
0.10
0.30
0.05
0.04
0.05
0.06
0.03
StreDD--ppatio--emmpral
0.20
0.38
0.46
0.30
0.14
0.39
0.08
0.04
0.05
0.04
0.07
0.04
Gree StreeD--event-mmpect
0.11
0.35
0.29
0.27
0.08
0.28
0.06
0.03
0.04
0.03
0.05
0.02
CoDy-random
0.11
0.36
0.32
0.31
0.14
0.43
0.08
0.05
0.09
0.06
0.07
0.07
CoDy-tempord
0.14
0.39
0.39
0.38
0.13
0.48
0.07
0.04
0.10
0.05
0.06
0.06
Cy spasstoo--ttporra
0.20
0.41
0.44
0.36
0.18
0.53
0.06
0.04
0.08
0.04
0.07
0.05
CoDy-event-impace
0.17
0.42
0.40
0.41
0.16
0.54
0.07
0.05
0.09
0.06
0.07
0.06
Fidelity- UCI-Forums
Char
UCI-Messages
Wikipedia
UCI-Messages
UCI-Forums
Wikipedia
corr.
wng.
wrg.
wrg.
wrg.
wrg.
corr.
wrg.
PGExplainer (Luo et al., 2020)
0.49
0.76
0.44
0.84
0.87
0.68
0.05
0.17
0.07
0.08
0.09
0.22
T-GNNExplainer (Xia et al., 2023)
0.82
0.83
0.57
0.72
0.90
0.69
0.17
0.39
0.08
0.40
0.09
0.34
GreeDy-ramdon
0.34
0.97
0.28
0.99
0.57
0.93
0.04
0.14
0.08
0.12
0.09
0.19
Dremoo-temporal
0.56
0.98
0.61
0.98
0.77
0.90
0.22
0.49
0.50
0.47
0.17
0.45
BrreeDysputio--emmpe
0.70
0.96
0.64
0.95
0.82
0.88
0.31
0.54
0.53
0.46
0.23
0.54
Gree FrreDD-event-imper
0.67
0.98
0.64
0.99
0.72
0.90
0.18
0.51
0.39
0.42
0.14
0.43
CoDy D-rrdoooo
0.68
0.95
0.66
0.97
0.88
0.88
0.19
0.52
0.43
0.47
0.24
0.58
CoDy-temporal
0.69
0.96
0.98
0.88
0.55
0.49
0.22
SoDyyspatio-temporc
0.72
0.95
0.69
0.93
0.91
0.86
0.31
0.57
0.54
0.52
0.30
0.65
CoD CoDy-eventimppar
0.70
0.96
0.68
0.95
0.88
0.90
0.27
0.58
0.50
0.57
0.27
0,68
18

---

CoDy: Counterfactual Explainers for Dynamic Graphs
Correct predictions
Wrong predictions
UCIIMMssagees
0.4
0.4
fid.
fid
0.2
0.2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
sparsity
sporsity
Correct predictions
Wrong predictions
UCI-Forums
0.4
0.4
fid+
fid+
0.2
0.2
0
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
sparsity
sporsily
Correct predictions
Wrong predictions
0.6
0.6
Wikipedia
fid4
0.4
fid4
0.4
0.2
0.2
0
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
sparsity
sporsity
random temporal spatio peatio-temporal event-impact no selection strategy
CoDy
GreeDy
T-GNNExplainer
Figure 6. Results on the relationship between fid, and sparsity under different experimental settings for the TGN model.
F.1. Fidelity+ to Sparsity for correct predictions
UCI-Messages
UCI-Forums
Wikipedia
0.3
0.6
0.3
CoDy GreeDyy
fid+
fid4
0.4
fid,
0.2
temporal
spatto comporal
0.1
0.2
0.1
avent-innuact
T-GNNExplainer
0.2 0.4 0.6 0.8
0.2
0.4
0.6 0.8
0.2
0.4
0.6
0.8
sparsity
spar
spar sity
Figure 7. Results the relationship hetween fid, and sporsity for correct predictions made by the TGN model.
19

---

CoDy: Counterfactual Explainers for Dynamic Graphs
F.2. Runtime
UCI-Messages
Duration per explanation (s)
100
50
CoDy
GreeDy
T-GNNExxlaiiner
UCI-Forums
Duration per explanation (s)
50
CoDy
GreeDy
T-GNNExxplainer
Wikipedia
Duration per explanation (s)
100
CoDy
GreeDy
T-GNNExxlainer
random
temporal
spatio-temporal
event-impact
no selection strategy
Correct prediction
Wrong prediction
Figure& 8. Average duration for explaining predictions across various settings when targeting the TGN model.
We report the runtime achieved during the evaluation of the explainers. For replicability, we run the experiments on high-performmace computing cluster with an Intel Xeon Gold 6230 CPU, 16GB of RAM, and an NVIDIA Tesla V100 SXM2 GPU with 32GB of VRAM.
Figure 8 presents the average explanation times across datasets. GreeDy consistently requires the least time, with its event-impact variant taking longer due to more frequent calls to the TGNN, as detailed in Table 5. In comparison, CoDy calls this function more often than GreeDy, which concludes explanations upon finding a counterfactual example or reaching a search impasse. CoDy, in contrast, continues until a set number of iterations are completed or the search tree is fully explored.
20

---

CoDy: Counterfactual Explainers for Dynamic Graphs
The potential runtime increase of CoDy over GreeDy is largely configurable design choice. In our experiments. CoDy continues searching for better explanation, even after valid counterfactual has already been found. Thus, the runtime of CoDy could be substantially reduced by only searching until finding the first counterfactual example instead of searching for the predefined number of maximum iterations. Further, a hybrid approach of CoDy and GreeDy could be employed to speed up the search. By first employing GreeDy and, if unsuccessful, running CoDy, starting with the existing partial search tree initialized with GreeDy, one could harness the performance of GreeDy, while benefiting from the better performance of CoDy.
CoDy, GreeDy, and T-GNNExplainer allocate 97.85% 99.83%, and 82.72% of their time, respectively, calling the TGNN. This indicates that CoDy's scalability is largely dependent on the underlying TGNN model, which may encounter difficulties with larger or more complex datasets (as seen in the Wikipedia dataset in Figure 8). By efficiently navigating the search space through a balanced approach to exploration and exploitation, along with heuristic selection policies, CoDy optimizes the explanation process, which is especially important for complex and suboptimal TGNN implementations. Notably, T-GNNExplainer dedicates more time to the search process than the other methods.
Since calling the TGNN constitutes the predominant part of the runtime we analyze the time complexity CoDy in terms of the number of calls the TGNN. Following Algorithm 1, CoDy has a worst-case time complexity of O (ilma)) in all variants except for the event- peent-impact where the initial local gradient exploration of the N candidate event adds to the complexity, resulting in worst-case complexity of Oiimmar N).
Table 5 shows consistent call frequencies to the prediction model across datasets for each explainer. However, CoDy and GreeDy show significant variation explanation times across datasets, especially on the Wikipedia dataset. This could be due to the dataset's s longer model response times, possibly because of its edge features and larger size compared to the other datasets. Note that PGExplainer and T-GNNExplainer are excluded from this table because PGExplainer does not directly interact with TGNNs, and T-GNNExplainer relies on an approximation of the TGNN models.
Overall, GreeDy offers the shortest explanation durations, making it preferable for rapid explanations.
Table 5. Average number of calls to the TGNN performed by the explanation methods for the different experimental settings performed by GreeDy and CoDy.
UCI-Messages
UCI-Forums Correct
Wikipedia
Correct
Incorrect
Incorrect
Correct
Incorrect
GreeDy-random
27.10
23.40
24.80
21.80
23.15
18.55
Greepoytemp
43.70
29.85
36.15
29.15
32.30
24.65
GreeDDy-pputoo-eemprrr
57.60
29.40
37.65
35.25
39.35
22.35
GreeDy-eventimppare
100.15
79.18
88.10
78.15
80.47
69.36
CoDy-random
287.91
246.83
261.13
257.23
284.52
237.16
CoDy-temporal
287.92
245.64
261.23
256.31
284.85
236.26
BeDDy-ppatio-emppe
287.95
245.44
260.95
256.44
284.98
236.26
CoDy event- impact
346.50
292.23
312.00
305.70
339.90
272.52
21

---

CoDy: Counterfactual Explainers for Dynamic Graphs
F33 Search Iterations
In the experiments with CoDy, key parameter the maximum number of search iterations (ifmaa), initially at 300. Further investigation performance involved increasing man to 1200, specifically focusing correct predictions in the Wikipedia dataset where Satol--ppatoo-emporee surpasses all CoDy variants. Figure 9 illustrates the fid+ scores relative to the number of iterations, highlighting that CoDy variants eventually outperform GreeDy counterparts, albeit with varying iteration requirements. While random and event-impaci policies require fewer iterations, CoDy-spatio-tempore and CoDy-temporal need close to 1000 and 1200 iterations, respectively, for superiority.
0.5
0.4
0.3
fid+
0.2
0.1
200
400
600
800
1,000
1,200
Search iterations (itmax)
random temporal spatio-temporal event-impact
CoDy GreeDy
Figure 9. Comparison of fid4. scores for various explanation methods on the Wikipedia dataset and the TGN model, highlighting CoDy's performance over iterations.
The figure reveals that CoDy can potentially find the minimal counterfactual example with unlimited iterations, by exploring the entire search space. However, the high iteration count for certain CoDy variants to outperform GreeDy indicates need for optimizing the parameter which balance exploration and exploitation. This is inferred from GreeDy's initial superiority, suggesting its more effective exploration of the search space. CoDy's delay in matching GreeDy's 's partial search tree performance implies an imbalance its selection policy.
22

---

CoDy: Counterfactual Explainers for Dynamic Graphs
F.4. Similarities in Explanations
The Jaccard similarity is used compare explanations from various explainers, focusing on correct predictions in the Wikipedia dataset (Figure 10). This heatmap serves representative example. T-GNNExplainer's explanations differ significantly from those of GreeDy and CoDy, partly due to their lower sparsity (Table 1). GreeDy-temporal and GreeDy- and CoDy explanations.
spatio-temporal show high similarity, as do GreeDy--spatiotemmppnn
Comparatively, CoDy variants' explanations are more similar to each other. CoDy-temporal and CoDy-spatio-tempore have high similarities with each other and with CoDy-event-impe imppttt...c..... This indicates CoDy's search procedure's 's ability to explore similar areas, highlighting the likeness of temporal, spatio temio-te and event-impact policies over the random policy.
GreeDy-spanne -ppptspttoooooo temporal speatt--emmoor
CoDy CoDy-spatio- ses---patt--ppppee Cempooll
GreeDy--venntimppa
T-GNNExplaines
GreeDy randon
SreeDy-temporal
CoDy-random
CoDy-remporal
LoDy-event-impare
T-GNNExplainer
1.00
0.05
0.08
0.09
0,05
0.06
0.09
0.11
0.08
0.9
GreeDy-random
1.00
0.17
0.09
0.22
0.10
0.11
0.11
0.11
0.8
GreeDy-temporee
0.08
0.17
1.00
0.46
0.30
0.23
0.33
0.30
0.27
0.7
GreeDDy-spatoo-eemporl
0.09
0.09
0.46
1.00
0.23
0.27
0.37
0.40
0.36
0.6
Jaccard similarityy
GreeDDy-vent--mpact
0.05
0.22
0.30
0.23
1.00
0.21
0.24
0.24
0.24
0.5
CoDy-random
0.06
0.10
0.23
0.27
0.21
1.00
0.38
0.38
0.41
0.4
temporel
0.09
0.11
0.33
0.37
0.24
0.38
1.00
0.74
0.51
0.3
CoDy-sppatio-emmporl
0.11
0.11
0.30
0.40
0.24
0.38
0.74
1.00
0.54
0.2
0.1
JoDy-event-impace
0.08
0.11
0.27
0.36
0.24
0.41
0.51
0.54
1.00
Figure 10. Results on the Jaccard similarity between explanations of correct predictions on the Wikipedia dataset for explaining the TGN model.
23

---

CoDy: Counterfactual Explainers for Dynamic Graphs
G. Sensitivity Analysis
For running the experiments, we not tune the parameters of CoDy and instead relied on informed guesses for suitable parameters. To gauge the impact of tuning the exploration parameter a, as well the influence of the size of the constraint search space Momar in sensitivity analysis. For this analysis, we ran experiments explaining correct predictions of the TGAT model on the UCI-Messages dataset with the ppatio-temporal selection policy. The base experiment hyperparametens and Mimax = 64. To shift the balance between exploration and exploitation run experimentation with stronger emphasis on exploration with = 3. moaz = 64, and an experiment with stronger emphasis on exploitation with a 7. Mmaa 64. To explore different search-space sizes, we run an experiment with mmmar 48, and one with
Mmar = 96.
Exploration/explootttion trade-off
Candidate Size Myma
0.4
0.4
CoDly pepp--pullooooooo romporlt
0.3
0.3
f
64
fid4
fid
0.2
0.1
0.1
48
Mmax 96
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
sparsity
sparsity
Figure 11. f -sporsily plots for experiments in sensitivity analysis.
Looking at the influence of adjusting a, we see that incentivizing exploitation (larger a) improves the performance of CoDy. This suggests that the experimental configuration suboptimal and misses explanations that require more aggressive exploitation of the partial search tree.
Similarly, the candidate size mmma has an influence on the performance of CoDy. Here, increasing the candidate size to 96 improves performance, whereas lowering to 48 deteriorates the performance. These results hint that there exist explanations to be found beyond the limit of 64 candidates. Increasing the candidate size can thus improve performance, which is the case in the evaluated setting.
Overall, the results of the sensitivity analysis highlight that CoDy has the potential to achieve significantly higher scores by tuning the parameters to the specific data and model. However, as shown in our evaluation, CoDy achieves state-of-the-art performance for counterfactual explanations on dynamic graphs even without such tuning efforts.
24


Reviews:
[{"review_id": "t5074xDKXK", "reviewer": "Reviewer_Sw8d", "summary": "This paper proposes CoDy and GreeDy, two algorithms that can generate counterfactual explanations for continuous-time dynamic graphs (CTDGs). The main component of the algorithm is a Monte-Carlo-Tree Search to find good edge combinations for removal. The method is experimentally evaluated on three dynamic graphs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the detailed and insightful review.\n\n**Runtime vs. Performance Trade-off**\n\nThe 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.\nAs 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.\n\n**Sparsity Control**\n\nNeither 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. \n\n**Connection to Discrete-Time Methods**\n\nWhile 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.\n\n**Performance**\n\nWe 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.\n\nWe 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.\n\nWe 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).\nTo 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.\n\n**Relevance & Significance**\n\nRegarding 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.", "claims_and_evidence": "The main claim of this paper is the method CoDy. While some evidence for the method is there, I think it could be made more compelling (see below).", "methods_and_evaluation_criteria": "I think the metrics are okay, but I wonder how the sparsity of the explanation can be selected with CoDy/GreeDy. It seems the evaluation AUFSC was done with different sparsity levels. I there a hyperparameter to select this or did the authors just rank the explanations? I am not sure whether this metric would be valid then, because if a method assigns non-sparse but always correct explanations it should get a high score, vs. a method that tries to optimize sparsity, but is not always correct.\n\nI think it would make more sense to compute this curve for a hyperparameter that trades off sparsity vs. fidelity / correctness.\n\nThere are three datasets used, which is okay but also not a very extensive benchmarking.", "theoretical_claims": "There are no theoretical claims in this work.", "experimental_designs_or_analyses": "The claimed superiority over the baselines is studied in experiments with several datasets and baselines. I could not find any substantial flaws in the setup.\n\nHowever, I think the results are mixed so I am not entirely enthusiastic.\nFirst, the generated explanations do not seem to be very reliable. As far as I understand, e.g., the char score is supposed to be between 0 and 1. On average, the best-performing methods presented in this work show scores between 0.4 and 0.5., which does not seem very good. GreeDy further shows very good performance on TGAT in particular, so there is no clear suggestion on which method to use.\n\nThe spatio-temporal method has the best performance, but also makes the most calls to the model (Table 5, Appendix).\nAblations of the different components: The method has several steps, and I am unsure how systematic the exploration of these is. So far, I only see an ablation for the selection policy. There is some improvement over random, but it is small. Further, the results from GreeDy show that greedy search is also quite good. Given the 10-fold increase in runtime (Appendix F.1), I am not convinced that the full method is worth the additional investment in practice.\n\nGenerally speaking, the experimental design is valid, but the experimentation could be more extensive, and have better insights (it is basically a huge results table, where some methods will on some datasets, some on otheres, but I cannot see a clear pattern or learning from it).", "relation_to_broader_scientific_literature": "This work contributes a new method for *continuous-time dynamic graph counterfactual explainability*. I agree that there are not many methods for this graph counterfactual of problem and therefore the paper does make a contribution.\n\nHowever, as the many specifiers to the domain suggest, I think the problem is relatively niche and only relevant to a very specific subgroup of the ICML community.", "essential_references_not_discussed": "I am not aware of highly relevant missing references.\n\nHowever, I think the connection between discrete time and continuous time graphs could be more deeply discussed. There are simple processing methods to convert discrete into continuous time graphs and vice-versa.\nHowever, for discrete time graphs, there are already explanation methods, like Prenkaj et al. (2024). I wonder wheter applying these methods on a discretized version of the graph would not already solve the problem. I think this connection necessitates further consideration.\n\n\nPrenkaj, Bardh, et al. \"Unifying Evolution, Explanation, and Discernment: A Generative Approach for Dynamic Graph Counterfactuals.\" Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.", "other_strengths_and_weaknesses": "**Summary.** I find it hard to form an opinion about this paper. On the one hand there are no obvious methological flaws. The writing is good. However, I am not very enthusiastic about the experimental results, which don't seem to tell a clear story. Also the problem feels very specific. Overall, I  award this paper a borderline rating.", "other_comments_or_suggestions": "Minor\n*  i.e., (comma missing, l.124, right)\n*  Equation 2 does not seem to make much sense: What does the vector notation mean? It seems we have a vector where one element (upper) is a graph and the other one (lower) is an integer", "questions_for_authors": "Can you please explain how the sparsity of the explanations is controlled and how the AUFSC is computed? Also, what sparsity levels are the fid+, fid- scores computed at? How do you explain the difference in performance between the algorithm versions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "P9kBtVpcW7", "reviewer": "Reviewer_NKwF", "summary": "The paper introduces CoDy, a method for generating counterfactual explanations for Temporal Graph Neural Networks (TGNNs). Unlike existing methods that focus on factual explanations, CoDy explores how minimal modifications to a dynamic graph can alter predictions (counterfactuals). \n\nCoDy employs Monte Carlo Tree Search (MCTS)-based algorithm with heuristic selection policies that leverage temporal, spatial, and local gradient (*why did you call it like this?*) information to efficiently identify counterfactual subgraphs. To benchmark its performance, the authors develop GreeDy - although there are other static counterfactual explainers in the literature - and propose an evaluation framework assessing necessity and sufficiency of explanations. Experiments on three real-world datasets (Wikipedia, UCI-Messages, UCI-Forums) and two TGNN models (TGN, TGAT) show that CoDy outperforms factual and counterfactual baselines.\n\nThe results highlight that counterfactual explanations offer a distinct interpretability advantage by illustrating what minimal changes would lead to different outcomes, especially for misclassified predictions. CoDy provides a structured approach to exploring decision boundaries in dynamic graphs.\n\n## Update after rebuttal\nFor the AC: I changed my score from weak accept to strong accept. I went back and forth with the reviewers, and they've answered most of my questions and followed my suggestions. There were some disagreements with them, but that shouldn't undermine this paper's acceptance. I'm willing to champion this paper as it's the best in my batch of reviews.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comprehensive review and valuable feedback.\n\n**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)\n\n**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”.\n\n**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.\nWe 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.\n\n**4.** We have followed your suggestion and simplified the formulation.\n\n**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.\n\n**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.\nAdapting 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.\nOn 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.\n\n**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. \n\nWe 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.\n\n**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.\n\n**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.\n\n**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.\n\nWe 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.", "claims_and_evidence": "The authors claim to be the first to propose a continuous temporal graph counterfactual explainer, *which is fair enough*. To the best of my knowledge only [1] does temporal graph counterfactual explanations on a snapshot-based graph. However, I'm not sure why the authors need to distinguish between the two? The snapshot-based graph methods can be easily transformed into their continous version by just not framing the graph in $\\Delta$ time intervals of the same time span.\n\n[1] Prenkaj et al. Unifying Evolution, Explanation, and Discernment: A Generative Approach for Dynamic Graph Counterfactuals. KDD'24\n\nThe authors also claim to have a $6\\times$ improvement in fidelity. However, I can't seem to find where this claim is supported. Table 1 doesn't showcase this, or am I missing something?", "methods_and_evaluation_criteria": "They partially do, however the authors miss a lot of related work and metrics used in the literature to solidify their empirical claims for CoDy. Please see *Experimental Designs and Analyses*.", "theoretical_claims": "There are no theoretical claims.", "experimental_designs_or_analyses": "I believe the authors didn't explore enough time-graph datasets. I found out that the TUDataset website has a lot of them that are easy to integrate in the authors' codebase and contain continuous time events. Examples of datasets follow:\n1. DBLP-Coauthors [1]\n2. BTC-Alpha, BTC-OTC [2]\n3. Bonanza [3]\n\n[1] Benson et al. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences. 2018\n\n[2] Kumar et al. Rev2: Fraudulent user prediction in rating platforms. In WSDM'18\n\n[3] Derr et al. Balance in signed bipartite networks. In CIKM'19\n\n----\nThe authors decide to adapt a single explainer, PGExplainer, from static scenario to a dynamic one. How? Why only PGExplainer? Also are you adapting it for counterfactuality? If not, how are you evaluating fidelity on it?\n\nAdditionally, there are a lot of other counterfactual - although PGExplainer is factual (see question #6) - explainers. For example, Prenkaj et al. [4] adopted a lot of static counterfactual explainers: BDDS [5], MEG [7], CLEAR [6]. The authors might scrutinize the goodness of these adapted explainers in a DTDG scenario. Nevertheless, to be fair to previous work, I would suggest to follow the same strategy to complete the analyses made in this paper. For now, the authors just compare to 2 explainers. Also, in the literature, researchers compare against a random baseline - and I'm not talking about *GreeDy-rand.* - to check the sanity of their proposed method. \n\n[4] Prenkaj et al. Unifying Evolution, Explanation, and Discernment: A Generative Approach for Dynamic Graph Counterfactuals. In KDD'24\n\n[5] Abrate & Bonchi. Counterfactual graphs for explainable classification of brain networks. In KDD'21\n\n[6] Ma et al. Clear: Generative counterfactual explanations on graphs. NeurIPS'22\n\n[7] Numeroso and Bacciu. Meg: Generating molecular counterfactual explanations for deep graph networks. IJCNN'21\n\n---\nRecall that fidelity is a measure based on the underlying predictor. See Prado-Romero et al.'s [8] definition (see pag. 23):\n$$\\Psi(x, x') = \\chi(x) − \\mathbf{1}[\\Phi(x') = y_x],$$ where $x$ is the input, $x'$ is the counterfactual produced. $\\chi(x)$ gives 1 if $x$ was correctly classified, and 0 otherwise, and $y_x$ is the ground truth label of $x$. A value of 1 entails that both the explainer and predictor are working correctly. 0 and −1 describe something wrong with the explainer or the oracle. However, we cannot attribute the incorrect function to\nthe explainer or the oracle. This is a shortcoming of fidelity since it bases the assessment of the correctness on the ground truth label $y_x$ instead of the prediction $\\Phi(x)$. Therefore, the literature [1-8], use also validity (correctness) to evaluate their counterfactual's goodneess. This metric is never used in this paper. \n\nFurthermore, the structural distance, measured by Graph Edit Distance (GED) [8], is never used. The used *sparsity* metric just measures the distance on the node features. However, since the authors advocate for spatial distance as well, it's wierd that GED isn't there, which undermines the claims of the search tree producing \"close-by\" counterfactuals.\n\n[8] Prado-Romero et al. A survey on graph counterfactual explanations: definitions, methods, evaluation, and research challenges. CSUR'24.\n\n---\nThe authors claim that their local-gradient CoDy variant is the best-informed counterfactual explainer. Table 1 shows that the choice for CoDy is random. Sometimes, even the GreeDy variant surpasses it. That's why correctness (validity) and GED should be here. **Moreover, the abstract states that the authors have a 6$\\times$ improvement in fidelity than SoTA methods. This improvement doesn't appear to emerge from the table!**\n\n---\nIt seems very wierd that the authors try to evaluate both necessity and sufficiency, as does CF$^2$ [9], but never compare to it. Why choose PGExplainer as comparison and not CF$^2$ undermines the authors claims to be the best in *AU FSC-*. This method is specifically developed to minimize both necessity and sufficiency.\n\n[9] Tan et al. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In WWW'22", "relation_to_broader_scientific_literature": "This works opens doors to graph counterfactual explainability in time-graphs although this field has already been partially explored in [1]. I can't seem to find why [1] nor this paper should or can have a broader scientific impact. Both paper's evaluations are in controlled environments that do not show how they could be employed in real-world scenarios, although both authors argue that *\"their datasets are real-world*.\n\n[1] Prenkaj et al. Unifying Evolution, Explanation, and Discernment: A Generative Approach for Dynamic Graph Counterfactuals. In KDD'24", "essential_references_not_discussed": "I came across this paper [1] that trates temporal graph counterfactual explainability when considering the time-graph as a sequence of snapshots - i.e., what the authors named DTDGs. I believe it should be treated at least in the related work section. I'm not sure wheather it would fit the authors' comparisons since they discretize the time component and get snapshots of the graph changes. I read Prenkaj et al.'s paper and I believe they explain GNNs on a specific snapshot, particularly the first one, and then use their explainer to generatively classify the incoming graphs and explain them dynamically. This doesn't seem to fit with what CoDy is trying to do; however, I still believe that this comparison between \"real\" TGNN  and snapshot-based counterfactual explainability should be treated in the **Related Work** section. To the best of my knowledge, this is the only work - after some search - in dynamic counterfactual explainability in graphs. Maybe instead of **GreeDy**, the authors could compare against **GRACIE** [1]?\n\n*[1] Prenkaj B, Villaizán-Vallelado M, Leemann T, Kasneci G. Unifying Evolution, Explanation, and Discernment: A Generative Approach for Dynamic Graph Counterfactuals. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining 2024 Aug 25 (pp. 2420-2431).*\n\nI believe Prado-Romero et al's bibtex citation should be the following.\n\n*@article{prado2024survey,\n  title={A survey on graph counterfactual explanations: definitions, methods, evaluation, and research challenges},\n  author={Prado-Romero, Mario Alfonso and Prenkaj, Bardh and Stilo, Giovanni and Giannotti, Fosca},\n  journal={ACM Computing Surveys},\n  volume={56},\n  number={7},\n  pages={1--37},\n  year={2024},\n  publisher={ACM New York, NY}\n}*\n\nI had complaints in other venues from reviewers that the paper isn't only an arXiv- Rather it is an ACM CSUR publication. Just to give the authors a heads-up.\n\n---\n\nThe first paragraph in the related work section misses a lot of static counterfactual explainers (e.g., [2-8] among others).\n\n[2] Abrate & Bonchi. Counterfactual graphs for explainable classification of brain networks. KDD'21\n\n[3] Ma et al. Clear: Generative counterfactual explanations on graphs. NeurIPS'22\n\n[4] Numeroso & Bacciu. Meg: Generating molecular counterfactual explanations for deep graph networks. IJCNN'21\n\n[5] Prado-Romero et al. Robust stochastic graph generator for counterfactual explanations. AAAI'24\n\n[6] Lucic et al. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. AISTATS'22\n\n[7] Bajaj et al. Robust counterfactual explanations on graph neural networks. NeurIPS'21 (*factual-based explainer just like PGExplainer*)\n\n[8] Chen et al. D4explainer: In-distribution explanations of graph neural network via discrete denoising diffusion. NeurIPS'23\n\n[9] Faber et al. Contrastive Graph Neural Network Explanation. ICLM'20 Workshop (*this guy always produces correct counterfactuals, but it's bound by the dataset: i.e., can't generate something ex-novo*)", "other_strengths_and_weaknesses": "See other sections, please; the reviewer form is already cluttered with a lot of sections. The paper raises a lot of questions, specifically in the experimental section, and the lack of prudent evaluation with the plethora of static graph counterfactual explanations, and the usage of adequate metrics to measure the goodness of the proposed method. While the authors want to showcase *fidelity-* and *fidelity+* as CF$^2$ [1] does, it's a puzzle why they refrain from comparing CoDy to an adapted version of CF$^2$ to dynamic graphs...\n\n[1] Tan et al. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In WWW'22", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. So is CoDy only able to perform edge addition/removal operations to generate the counterfactuals? There's no node addition/removals right?\n2. Why are you calling your selection strategy *local-gradient*? It's just a logit-based difference... Are you saying that you have access to the gradients of the predictor? I don't think so; otherwise, you're \"blowing-up your cover\" for treating black-box TGNNs; rather they should be called grey-boxes. I'd argue that you change this nomenclature to something more suitable.\n3. Instead of having the heuristic guide your tree traversal, have you thought of learning the path that guides you toward the counterfactual? If so, how would you do that? If not, why didn't you? CoDy's tree algorithm \"screams\" reinforcement learning to me: did you consider doing this? My question would be, what's the motivation behind Monte-Carlo Search and not other strategies?\n4. In Eq. (7) why is the exploration and exploitation governed by $\\alpha$ and $\\beta$, and not only $\\alpha$? In other words, why isn't the equation equal to $selscore(n_k) = \\alpha\\cdot score_k + (1-\\alpha)\\cdot score_{explore}(n_k)$?\n5. When you have multiple counterfactual candidates, you state that you select the one with the largest shift in the TGNN prediction. Doesn't this, in some sense, suggest that you're overshooting the decision boundary of your predictor? See Wachter et al's distance requirement [1]. Or is this distance tackled during the search algorithm?\n6. The authors use PGExplainer as a baseline for static graphs and adapt it to dynamic ones. I wonder why the authors chose a factual explainer in a counterfactual fashion? This doesn't make sense. How are you evaluating fidelity on a factual explainer? How are the authors generating counterfactuals with a factual explainer? Are you simply removing the factual explanation generated from the input graph to hopefully produce a valid counterfactual?\n7. Since fidelity has been shown to have inherent weaknesses as a metric (see [2]), why don't you use correctness (validity) to assess the goodness of the produced counterfactuals?\n8. Can you please show the Graph Edit Distance (GED) [2] of your counterfactuals? This is a necessary metric to support your claims of the search tree producing \"close-by\" counterfactuals.\n9. Where is your claim of $6\\times$ improvement in fidelity supported? I can't see it from Table 1.\n10. I don't understand what correct and wrong predictions are in Table 1. Can you please clarify? I can't seem to find anything related to it in the experimental section.\n11. In Fig. 9, it is concerning that Cody-Rand. has >0.35 Jacard similarity with the other \"more informed\" variants, especially with \"local-grad.\" How do you explain this? Is the local-grad. variant that informed? Recall that is just the difference between logits in the original prediction and the counterfactual one.\n\n\n[1] Wachter S, Mittelstadt B, Russell C. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harv. JL & Tech.. 2017;31:841.\n\n[2] Prado-Romero MA, Prenkaj B, Stilo G, Giannotti F. A survey on graph counterfactual explanations: definitions, methods, evaluation, and research challenges. ACM Computing Surveys. 2024 Apr 9;56(7):1-37.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VTKNsrbE33", "reviewer": "Reviewer_5zq2", "summary": "This paper introduces CoDy (Counterfactual Explainer for Dynamic Graphs), a method for generating counterfactual explanations to interpret predictions made by Temporal Graph Neural Networks (TGNNs) on continuous-time dynamic graphs (CTDGs). Existing explanation methods focus on static graphs or factual explanations, which are insufficient for capturing temporal dependencies and actionable scenarios in dynamic graphs. To close this gap, CoDy combines Monte Carlo Tree Search (MCTS) with heuristic policies to efficiently explore the search space of past events, identifying minimal subsets of events whose removal alters the model’s prediction. The authors also develop a greedy baseline that iteratively selects events causing the largest immediate prediction change. Experimental results empirically demonstrate the superior performance of CoDy in identifying concise yet impactful counterfactual explanations.\n\n## update after rebuttal\nThanks for the authors' efforts in the rebuttal. I intend to keep my rating.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your time and insightful feedback on our paper. Please find our rebuttal to the weaknesses below:\n\n**W1: Potential bias in selection policies**\n\nThe 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. \nWhile 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.\n\n**W2: Reliance on prediction logits**\n\nWe 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).\nWe 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).\n\n**W3: CoDy outperforms factual methods on $AUFSC_-$ scores**\n\nThis 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).\n\n**W4: Lack of user studies or human-centered evaluations**\n\nWe 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.\n\n**W5: Experiments focus on social/interaction networks**\n\nOur 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:\n- Unipartite (UCI-Messages) vs. Bipartite (Wikipedia, UCI-Forums).\n- Presence (Wikipedia) vs. Absence (UCI) of edge features.\n- Varying temporal dynamics and graph densities (Table 2).\n\nWe 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.", "claims_and_evidence": "The main claims made in this paper are generally supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria are well-aligned with the problem of explaining TGNN predictions on dynamic graphs.", "theoretical_claims": "No theoretical claims were made in this paper.", "experimental_designs_or_analyses": "The soundness of all the experimental designs and analyses has been carefully checked.", "relation_to_broader_scientific_literature": "This paper advances prior works in two key areas: GNN explainability and counterfactual reasoning. Existing GNN explanation methods focus on static graphs, lacking effectiveness to handle temporal dependencies. For dynamic graphs, prior methods are limited to factual explanations, which identify contributing features but fail to explore \"what-if\" scenarios. CoDy bridges this gap by adapting counterfactual explanation to temporal contexts, leveraging insights from causal reasoning and temporal graph modeling.", "essential_references_not_discussed": "Most of the key related work are cited.", "other_strengths_and_weaknesses": "Strengths:\nS1. This paper introduces a novel counterfactual explanation framework for temporal graph neural networks on continuous-time dynamic graphs, addressing a clear gap in dynamic graph interpretability.\nS2. This paper presents a well-defined methodology that combines Monte Carlo Tree Search with spatio-temporal and gradient-based selection policies.\nS3. The experimental evaluation is comprehensive. The authors test the proposed method CoDy on multiple datasets and compare against both factual and greedy baselines.\n\nWeaknesses:\nW1. The spatio-temporal and gradient-based policies may introduce a large bias, favoring recent or proximal events while neglecting older, causally critical events.\nW2. While the authors claimed that CoDy is model-agnostic, its reliance on prediction logits may produce inconsistent results for TGNNs with differing architectures, which the paper does not investigate.\nW3. Discussion on the reason why CoDy outperforms factual methods in achieving better AUFSC- scores is not given. This is a bit counter-intuitive because CoDy is not configured to achieve this.\nW4. Although the evaluation is extensive, it relies primarily on quantitative metrics. It would be great if the authors could also incorporate user studies or human-centered evaluations to assess the interpretability of the generated counterfactuals.\nW5. Nit picking: the experiments focus on social/interaction networks. Performance on dynamic graphs with fundamentally different dynamics (e.g., biological networks, sensor networks) remains unverified, raising questions about method universality.", "other_comments_or_suggestions": "The notation p in Equation (6) can be easily confused with the binary classification function p.", "questions_for_authors": "Please refer to the weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "n/a"}}]

Author rebuttal:

Meta-review: The paper introduces a method for generating counterfactual explanations for temporal graph neural networks.

There were significant discussions between authors and the reviewers and also among the reviewers. I believe Reviewer NKwF, an expert in the area, played a crucial role in convincing us to provide an acceptance recommendation.

The reviewers unanimously liked the paper. In particular, the reviewers appreciated the framework for continuous temporal graph counterfactual explainer. While they were minor concerns, such as char scores of around 0.5-0.6, I believe this would be a good starting point to ignite future progress on this problem. I encourage the authors to add a discussion about this in the limitation section. There was also some related work (mainly about the connection between discrete and continuous time) that has not been cited, and I encourage the authors to include these references in the camera-ready version. Also, Reviewer NKwF provides a lot of excellent points during the discussion, and the authors have provided many clarifying answers, which I think can be included in the paper to clarify the significance of the work more clearly.
Decision: Accept (poster)