# Greedy and CoDy: Counterfactual Explainers for Dynamic Graphs

Zhan Qu  Daniel Gomm  Michael Färber

###### Abstract

Temporal Graph Neural Networks (TGNNs), crucial for modeling dynamic graphs
with time-varying interactions, face a significant challenge in explainability
due to their complex model structure. Counterfactual explanations, crucial for
understanding model decisions, examine how input graph changes affect
outcomes. This paper introduces two novel counterfactual explanation methods
for TGNNs: GreeDy (Greedy Explainer for Dynamic Graphs) and CoDy
(Counterfactual Explainer for Dynamic Graphs). They treat explanations as a
search problem, seeking input graph alterations that alter model predictions.
GreeDy uses a simple, greedy approach, while CoDy employs a sophisticated
Monte Carlo Tree Search algorithm. Experiments show both methods effectively
generate clear explanations. Notably, CoDy outperforms GreeDy and existing
factual methods, with up to 59% higher success rate in finding significant
counterfactual inputs. This highlights CoDy’s potential in clarifying TGNN
decision-making, increasing their transparency and trustworthiness in
practice.

Machine Learning, Explainability, Temporal Graphs, Graph Neural Networks

##  1 Introduction

Recent research has been particularly focused on the deployment and
application of deep neural networks to graph data, a domain that continues to
gain momentum (Wu et al., 2020). These models, known as Graph Neural Networks
(GNNs), have been successful in multiple areas. For instance, GNNs have
contributed to drug discovery by aiding in protein folding (Jumper et al.,
2021) and enhancing the accuracy of weather forecasting models (Lam et al.,
2022).

GNNs, however, have primarily been applied to static graphs, where the graph
structure remains constant over time. Yet, many real-world scenarios are
better represented by dynamic graphs, which evolve with time. Examples include
social networks with evolving relationships, road networks with changing
traffic conditions, and financial transaction networks with ongoing
transactions (Zhao et al., 2019; Rossi et al., 2020; Souza et al., 2022). In
such dynamic graphs, nodes and edges can be added or removed, and their
features can evolve over time. Dynamic graphs are typically depicted as a
sequence of events marked by timestamps, where each event signifies a
modification in the graph structure, including the addition or deletion of
nodes or edges. Neglecting the temporal aspect in these graphs can lead to
overlooking vital temporal information and can result in erroneous model
predictions (Xu et al., 2020). Addressing this, Temporal Graph Neural Networks
(TGNNs) have been developed, specifically tailored to handle dynamic graph
data effectively (Trivedi et al., 2019; Xu et al., 2020; Ma et al., 2020;
Rossi et al., 2020; Makarov et al., 2021; Souza et al., 2022).

Despite the increasing focus on deep models for dynamic graphs (Longa et al.,
2023), a significant challenge remains: these models often act as "black
boxes," offering little to no insight into their decision-making processes (Vu
& Thai, 2022). This lack of transparency is particularly problematic in
critical fields such as finance and healthcare, where understanding the
rationale behind model predictions is crucial (Prado-Romero et al., 2023).
Regulatory bodies are increasingly mandating explainability in these areas
(European Parliament, 2021). Current explanation methods, however, are
predominantly designed for static graphs and do not adequately account for the
temporal dynamics inherent in dynamic graphs (He et al., 2022; Liu et al.,
2023; Xia et al., 2023; Chen & Ying, 2023).

Most existing explanation methods for temporal models require deep access to
the model’s internals and are limited to factual explanations—those that
identify specific nodes and edges contributing to a prediction (Tan et al.,
2022). However, they fall short in exploring how changes in the input graph
could lead to different predictions. Counterfactual explanations, which
illustrate how altering elements in the graph could change the outcome, are
gaining popularity for their ability to establish causal relationships and
highlight decision boundaries (Byrne, 2019; Prado-Romero et al., 2023). They
offer actionable insights, help identify biases, and can uncover potential
adversarial examples (Lucic et al., 2022). Yet, no existing methods for
dynamic graphs effectively leverage the potential of counterfactual
explanations. Temporal graphs possess temporal relationships that may
naturally establish causal relationships between nodes, making counterfactual
explanation methods especially suitable for TGNN models.

Addressing this gap, this paper introduces two novel model-agnostic
counterfactual explanation approaches for dynamic graph models. The first,
GreeDy (Greedy Explainer for Dynamic Graphs), adopts a simple greedy search
strategy, providing a baseline for counterfactual explanations in dynamic
graph models. The second, CoDy (Counterfactual Explainer for Dynamic Graphs),
utilizes principles from the Monte Carlo Tree Search (MCTS) for efficient
traversal of the search space. Both methods aim to identify counterfactual
examples by altering a subset of past events in the input data, thereby
changing the model’s prediction. However, due to the specific objectives of
the method, counterfactual explanations are not always achievable. Several
search strategies have been developed, improving both the efficiency and
effectiveness of the search for counterfactual explanations. In scenarios
where counterfactual explanations cannot be found, a well-defined fallback
strategy is employed to identify the most optimal alternative that closely
aligns with the nature of a counterfactual explanation.

The comprehensive assessment conducted demonstrates that CoDy stands out as a
highly efficient method for generating counterfactual explanations for TGNN
models, such as TGN (Rossi et al., 2020) and TGAT (Xu et al., 2020). This
effectiveness is highlighted by its superior performance when compared to both
GreeDy and the sophisticated factual explainer T-GNNExplainer, specifically in
the context of future link prediction tasks across three distinct datasets,
UCI-Messages, UCI-forums, and Wikipedia. The evaluation was conducted
separately for correct predictions and wrong predictions made by the TGNN
models, as this approach allows for a more nuanced understanding of the
model’s performance, highlighting its reasoning for accurate predictions and
identifying areas for improvement where inaccuracies occur. Additionally, the
findings indicate that the integration of diverse search strategies aimed at
identifying the most impactful past events notably augments the abilities of
these explainers to uncover pertinent counterfactual explanations. This
suggests a promising direction for further enhancing the explanatory power and
precision of such models.

This paper makes several significant contributions to the field: (1) It
pioneers the exploration of counterfactual explanations in the context of
explaining Temporal Graph Neural Networks (TGNNs), offering actionable and
human-understandable insights; (2) It develops a more appropriate evaluation
framework specifically tailored for assessing counterfactual explanations; (3)
It introduces various search strategies designed to enhance the effectiveness
and efficiency of identifying potential explanations. 111The source code and
implementations are available at: https://anonymous.4open.science/r/CoDy-F2CF

##  2 Related Work

Numerous explanation methods for GNN on static graphs have been developed.
Explainability methods for Graph Neural Networks typically utilize gradients
(Baldassarre & Azizpour, 2019; Pope et al., 2019), perturbations (Ying et al.,
2019; Luo et al., 2020), decomposition rules (Schnake et al., 2020), surrogate
models (Huang et al., 2020; Vu & Thai, 2020), Monte Carlo Tree Search (MCTS)
(Yuan et al., 2021), and generative models (Yuan et al., 2020) to obtain the
explanatory subgraph. Compared with static GNN, the explainability of Temporal
Graph Neural Networks (TGNNs) remains challenging and less investigated.

Temporal graphs come in various forms, with Discrete-Time Dynamic Graphs
(DTDGs) and Continuous-Time Dynamic Graphs (CTDGs) being the most prevalent.
DTDGs are characterized by a sequence of static snapshot graphs, each
representing a distinct time interval (Kazemi et al., 2020). The majority of
existing research has been centered around providing explanations for
predictions on DTDGs. The process of explaining predictions in DTDGs typically
involves aggregating feature importances across different graph snapshots (He
et al., 2022). The methods for these explanations predominantly rely on
surrogate models (He et al., 2022), temporal decomposition strategies (Xie et
al., 2022; Liu et al., 2023), and model-specific features (Fan et al., 2021).

On the other hand, Continuous-Time Dynamic Graphs (CTDGs) are represented as a
series of timestamped events (Kazemi et al., 2020). These graphs are
especially pertinent in real-world scenarios such as social networks, where
the continuous emergence and disappearance of nodes and edges lead to their
ongoing evolution. This makes CTDGs particularly valuable for real-world
applications. Despite their importance, the field of creating explanations for
CTDGs remains relatively unexplored. To date, there are only two explainers
specifically designed for CTDGs: T-GNNExplainer (Xia et al., 2023) and TempME
(Chen & Ying, 2023). Both of these explainers employ a perturbation-based
approach to generate factual explanations, identifying a crucial subset of
past events that significantly influence the model’s predictions.

T-GNNExplainer (Xia et al., 2023) employs a search-based perturbation
approach, utilizing Monte Carlo Tree Search and a Multi-Layer Perceptron
(MLP)-based navigator to predict event importances and guide search space
exploration. This method, an adaptation of the SubgraphX (Yuan et al., 2021)
approach for static GNNs, uniquely determines the size of an explanation
autonomously, incorporating spatial and temporal constraints in its search.
Conversely, TempME (Chen & Ying, 2023) focuses on identifying key temporal
motifs – recurring, significant substructures in dynamic graphs – to explain
predictions. It selects these motifs from the local neighborhood of nodes
relevant to the prediction, using a GNN trained to assess motif importance.
This helps construct explanations that reflect the combined influence of these
temporal motifs.

Counterfactual explanations are proven to be highly effective explanations, as
they overcome many problems in interpretability and accountability (Wachter et
al., 2017). Additionally, counterfactual explanations have already been
successfully applied to regular GNN (Tan et al., 2022; Lucic et al., 2022),
making their application in explaining models on dynamic graphs a logical next
step.

As ignored by previous works on temporal explanation, the current paper aims
for counterfactual explanations that are human-understandable and insightful
based on an adapted Monte Carlo Tree Search (MCTS) algorithm with different
searching strategies. Considering the limited existing research and their
significant practical relevance, the focus is directed towards CTDGs.

The current paper advances the capabilities of explanation methods for black-
box prediction models on dynamic graphs. It addresses the identified research
gap by proposing GreeDy and CoDy, two instance-level post-hoc explainers that
provide counterfactual explanations for TGNNs operating on CTDGs. The proposed
methods are model agnostic, treating the explained model as black-box with
model access only required on the level of inputs and predictions.

##  3 Preliminaries and Problem Formulation

##### Explaining Future Link Predictions

The task of a future link prediction model, denoted as
$f:\\{\mathcal{G}(t_{i}),\varepsilon_{i}\\}\rightarrow\mathbbm{R}$, involves
forecasting whether an upcoming edge addition event, symbolized as
$\varepsilon_{i}=\\{e_{j},a_{e_{j},t_{i}}^{edge},\mathrm{add},t_{i}\\}$, is
likely to occur. This prediction relies on the history of events
${\mathcal{G}(t_{i})=\\{\varepsilon_{l}|\varepsilon_{l}\in\mathcal{G},t_{l}\leq
t_{i}\\}}$ in the temporal graph $\mathcal{G}$ up to time $t_{i}$. The model
$f$ is assumed to provide predictions as real-valued logits, which are the
quantile functions of the standard logistical distribution. These logits
reflect the model’s confidence in the event’s occurrence. Model $f$ can be any
suitable function, such as a Temporal Graph Neural Network (TGNN) trained for
this task. In this context, the model is also known as the link prediction
function. A binary classification function $p:\mathbbm{R}\rightarrow\\{0,1\\}$
transforms the output of $f$ into a definitive prediction:

$p(f(\mathcal{G}(t_{i}),\varepsilon_{i}))=\begin{cases}1,&\text{if
}f(\mathcal{G}(t_{i}),\varepsilon_{i})\geq 0\\\ 0,&\text{else}\end{cases}$ (1)

A result of $1$ indicates a prediction for the future link’s occurrence, while
$0$ indicates its non-occurrence. An explainer, denoted as $ex(\cdot)$, is a
function that provides a rationale for the model’s prediction. For future link
predictions, $ex(\cdot)$ takes the link prediction function $f$, the event in
question $\varepsilon_{i}$, and the past events $\mathcal{G}(t_{i})$, and
yields an explanation for the prediction.

##### Counterfactual Examples in Future Link Prediction

Counterfactual explanations offer insightful and actionable explanations for
specific predictions, making them highly relevant for interpreting predictions
from complex deep graph models like TGNNs. A counterfactual example
$\mathcal{X}{\varepsilon_{i}}$ related to a prediction about a future link
$\varepsilon_{i}$ consists of a critical subset of past events
$\mathcal{X}_{\varepsilon_{i}}\subseteq\mathcal{G}(t_{i})$ necessary for the
original prediction. This necessity is defined by the following condition:

$p(f(\mathcal{G}(t_{i}),\varepsilon_{i}))\neq
p(f((\mathcal{G}(t_{i})\setminus\mathcal{X}_{\varepsilon_{i}}),\varepsilon_{i}))$
(2)

For any given future link $\varepsilon_{i}$, multiple or no counterfactual
examples may exist. The set containing all existing counterfactual examples
for a potential future link $\varepsilon_{i}$ is denoted as
$\Psi_{\varepsilon_{i}}$. A counterfactual explainer for future link
prediction, $ex$, is a function that inputs a link prediction function $f$, a
temporal graph $\mathcal{G}(t_{i})$, and a future link $\varepsilon_{i}$. It
outputs a subset of the original graph’s events as the counterfactual
explanation:

$ex:\\{f,\mathcal{G}(t_{i}),\varepsilon_{i}\\}\rightarrow\bigcup_{k=0}^{|(\mathcal{G}(t_{i})\setminus\varepsilon_{i})|}{(\mathcal{G}(t_{i})\setminus\varepsilon_{i})\choose
k}$ (3)

This output represents any combination of past events, adhering to the
notation for permutations of a size $k$ as per (Stanley, 1986).

##### Objectives for Counterfactual Explanation

When explaining future link predictions via counterfactual examples, two
primary goals are identified:

  1. 1.

Maximize Discoveries: The first goal is to identify a counterfactual example
for as many cases as possible. Considering the exponential increase in
potential past event combinations, the explainer $ex$ aims to efficiently
pinpoint necessary explanations. This is quantified by maximizing the
following expression:

$\frac{1}{\mathcal{G}}\sum_{\varepsilon_{i}\in\mathcal{G}}\mathbbm{1}(ex(f,\mathcal{G}(t_{i}),\varepsilon_{i})\in\Psi_{\varepsilon_{i}})$
(4)

Here,
$\mathbbm{1}(ex(f,\mathcal{G}(t_{i}),\varepsilon_{i})\in\Psi_{\varepsilon_{i}})$
indicates whether $ex$ finds a counterfactual example.

  2. 2.

Minimize Complexity: When multiple counterfactual examples are available, the
explainer should choose the simplest yet most informative one. This follows
Occam’s razor principle, suggesting that explanations should be concise,
containing only relevant details (Yuan et al., 2023; Tan et al., 2022):

$\operatorname*{arg\,min}_{\mathcal{X}_{\varepsilon_{i}}^{j}\in\Psi_{\varepsilon_{i}}}|\mathcal{X}_{\varepsilon_{i}}^{j}|$
(5)

Here, $|\mathcal{X}{\varepsilon_{i}}^{j}|$ denotes the number of events in
$\mathcal{X}_{\varepsilon_{i}}^{j}$.

##  4 Proposed Methods: GreeDy and CoDy

This section offers a concise overview of two explanation methods, GreeDy and
CoDy, aimed at elucidating predictions in future link prediction models on
CTDGs. These methods revolve around efficiently navigating a defined search
space for counterfactual examples.

##### Search Space

The search space consists of potential counterfactual examples, each being a
subset of past events relative to a future link in a dynamic graph.
Mathematically, this space, $S_{\varepsilon_{i}}$, encompasses all
combinations of past events, excluding the future link $\varepsilon_{i}$.

Given the complexity, the search is streamlined through spatial and temporal
constraints, reducing the scope to a manageable subset of past events within a
certain range of the target event.

##### Search Space Constraints

Spatial constraints limit the search to events within a defined range of the
target event, while temporal constraints focus on the most recent events. The
resulting constrained space, $\hat{S}_{\varepsilon_{i}}$, still poses
computational challenges but is more feasible for exploration.

$\hat{S}{\varepsilon_{i}}=\bigcup{l=0}^{|C(\mathcal{G},\varepsilon_{i},k,m_{max})|}{C(\mathcal{G},\varepsilon_{i},k,m_{max})\choose
l}$ (6)

##### Search Tree Structure

To facilitate the search, a partial search tree $P$ is constructed (see Figure
1), with each node representing a unique combination of past events. The root
node, denoted as $n_{root}$, starts with no perturbations and is expanded to
include child nodes that represent incremental additions of past events. This
structure supports an efficient search for simple counterfactual explanations.

Both GreeDy and CoDy build upon this structured search space. GreeDy adopts a
direct approach, iteratively exploring the most promising paths in the search
tree, while CoDy, more intricate, employs a Monte Carlo Tree Search-based
method, considering additional node attributes and employing a more iterative,
exploratory process.

###  4.1 Selection Strategies

Selection strategies guide the exploration of unexplored nodes in a search
tree, impacting the efficiency and effectiveness of the search for
counterfactual examples. Four primary strategies are proposed:

  * •

Random: As a baseline, this strategy randomly selects among the available
nodes.

  * •

Temporal: Ranks the events based on their recency. Recent events are
considered more influential.

  * •

Spatio-Temporal: Integrates both spatial proximity and temporal recency.
Events with closer spatial distance are ranked higher. Events with the same
spatial distance are then ranked by their recency.

  * •

Local-Gradient: The local-gradient selection strategy ranks alternative events
based on their local gradient, which is the change in prediction caused by
omitting an event from the input graph.

Each strategy offers a unique heuristic: Temporal and Spatio-Temporal
strategies leverage structural information of the graph, while the Local-
Gradient strategy examines the isolated effect of events on predictions. The
$\Delta$-function is used in the Local-Gradient strategy to measure the shift
in prediction, indicating the potential for a different classification
outcome. These strategies are designed to enhance the search algorithm’s
ability to identify counterfactual examples efficiently.

$\Delta(pred_{ori},pred_{j})=\begin{cases}pred_{ori}-pred_{j},&\text{if
}pred_{ori}\geq 0\\\ pred_{j}-pred_{ori},&\text{else}\end{cases}$ (7)

###  4.2 GreeDy: Counterfactual Search in Dynamic Graph Models

The core of GreeDy is a greedy algorithm that navigates the search space,
starting from the root node and progressively exploring nodes that most
significantly alter predictions. The Algorithm and an example of GreeDy is
provided in Appendix A.

In each iteration, GreeDy samples $l$ child nodes based on a selection
strategy, focusing on those with the greatest impact on prediction change. The
algorithm assesses the potential of each child node in shifting the prediction
further from its original state. If a node is found to be a counterfactual
example, or if no further significant shifts in prediction are possible, the
search concludes.

The algorithm’s output is the best explanation found, represented by the most
impactful perturbation set in the search tree. This could either be a
counterfactual example or the set leading to the largest non-counterfactual
prediction shift.

###  4.3 CoDy: Counterfactual Explainer for Dynamic Graph Models

CoDy utilizes an adapted Monte Carlo Tree Search (MCTS) algorithm to identify
counterfactual examples in dynamic graph models. MCTS algorithm has already
been applied to obtain factual explanations for static GNNs (Yuan et al.,
2021) and TGNNs (Xia et al., 2023). CoDy’s process involves iterations of
Selection, Simulation, Expansion, and Backpropagation, with each step
specifically tailored for counterfactual search in dynamic graphs.

Figure 1: Illustration of CoDy

An example scenario illustrates CoDy’s process in action (Figure 1). The
search algorithm (Algorithm 1) initiates with the selection of a node,
$n_{j}$, for expansion. This process begins at the root and employs a
recursive child selection policy. A node is suitable for expansion if it is
not associated with child nodes ($children_{j}=\varnothing$) and lacks a
prediction score ($prediction_{j}=\text{null}$). The child selection algorithm
aims to balance exploration and exploitation within the search tree. The
selection of a child node is determined by a selection score, formulated as:

$selection\\_score(n_{k})=\alpha\cdot score_{k}+\beta\cdot
score_{exploration}(n_{k})$ (8)

where $score_{exploration}(n_{k})$ is derived from the ‘Upper Confidence Bound
1’ and $score_{k}$ denotes the exploitation score. Parameters $\alpha$ and
$\beta$ adjust the balance between exploration and exploitation.

Upon selecting a node, the simulation step involves predicting the outcome for
$n_{j}$. The expansion step updates the node’s attributes and adds child
nodes, expanding the search tree:

$score_{j}\leftarrow\max\left(0,\frac{\Delta(prediction_{orig},prediction_{j})}{|prediction_{orig}|}\right)$
(9)

Backpropagation updates the search tree from the parent of the expanded node
to the root, recalculating exploitation scores and assessing node
selectability. The search concludes after a predefined number of iterations or
when all nodes have been explored.

The algorithm selects the best counterfactual example, prioritizing minimal
complexity. In the absence of counterfactuals, a fallback strategy is applied,
it involves choosing the set of perturbations that has the greatest potential
to significantly change the prediction’s outcome in the opposite direction:

$n_{best}\leftarrow\operatorname*{arg\,max}_{n_{j}\in
P}\Delta(prediction_{orig},prediction_{j})$ (10)

The search is optimized with constraints to minimize explanation complexity,
caching for reducing redundant calculations, and a two-stage approximation-
confirmation approach for faster link prediction.

##  5 Experiments

###  5.1 Experimental Setup

##### Datasets

The explainers are evaluated on three different datasets: Wikipedia (Kumar et
al., 2019), UCI-Messages (Kunegis, 2013), and UCI-Forums (Kunegis, 2013). The
statistics of the datasets are provided in Table 1. Both UCI datasets are
online social networks with no node or edge features included. Wikipedia
dataset consists of events representing edits of Wikipedia pages. It is a
bipartite graph and the edges are associated with attributes that represent
the associated edit texts.

Dataset | # Nodes | # Edges | # Unique Edges | Timespan | Graph Type
---|---|---|---|---|---
UCI-Messages | 1,899 | 59,835 | 20,296 | 196 days | Unipartite
UCI-Forums | 1,421 | 33,720 | 7,089 | 165 days | Bipartite
Wikipedia | 9,227 | 157,474 | 18,257 | 30 days | Bipartite

Table 1: Statistics for datasets

##### Target Model

The target model that is explained in all experiments is the dynamic graph
model TGN (Rossi et al., 2020). TGN is used as the target model since it is
popular within research (Souza et al., 2022) and achieves state-of-the-art
performance in different tasks on dynamic graphs (Rossi et al., 2020; Souza et
al., 2022). To its users, the model mostly remains a black-box with little
transparency over what leads to a specific prediction. The TGAT model (Xu et
al., 2020) is also employed, but the outcomes observed were akin to those
obtained using the TGN model. As a result, the findings specific to TGAT are
not included in the paper, but the code is available in the repository.

##### Configurations

For the experiments, the TGN model is configured with a Gated Recurrent Unit
(GRU) (Cho et al., 2014) as the memory updater, graph attention as an
embedding module, last message aggregation, and the identity memory function.
This corresponds to the TGN-attn configuration presented as the default
configuration in the original paper (Rossi et al., 2020). After training for
$30$ epochs with early stopping on the model accuracy, the TGN model archives
a high average precision: UCI-Messages Transductive 85.86%, Inductive 83.26%;
UCI-Forums Transductive 92.97%, Inductive 89.39%; Wikipedia Transductive
97.80%, Inductive 97.39%.

##### Explainers

T-GNNExplainer (Xia et al., 2023), a method for explaining predictions on
CTDGs, is used as the baseline. TempME (Chen & Ying, 2023), another explainer
for CTDGs, isn’t included due to unavailable code at this time. Other
baselines such as GNNExplainer (Ying et al., 2019) and PGExplainer (Vu & Thai,
2020) that are used in previous papers are not included since they are not
state-of-the-art (Xia et al., 2023; Chen & Ying, 2023).

Given the inherent differences between factual and counterfactual
explanations, the evaluation focuses separately on the necessity and
sufficiency aspects. This dual assessment allows a nuanced understanding of
both factual and counterfactual dimensions in explanations. Unless otherwise
stated, experiments maintain consistent settings across explainers for a fair
comparison.

T-GNNExplainer is implemented as per its original design, with 500 iterations
and 30 candidate events considered. GreeDy’s candidate event limit is set at
64, sampling up to 10 events per iteration. For CoDy, the limit is similar at
64 candidate events, with a maximum of 300 iterations and hyperparameters
$\alpha$ = 2 and $\beta$ = 1 to balance exploration and exploitation.

##### Evaluation Metrics

Fidelity measures the identification of key input features, with different
formulations used in previous studies (Yuan et al., 2023; Xia et al., 2023;
Prado-Romero et al., 2023; Lucic et al., 2022; Amara et al., 2022). This work
calculates fidelity in relation to the model, adapting scores $fid_{-}$ and
$fid_{+}$ for CTDGs:

$fid_{-}=1-\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}(p(f(\mathcal{G}(t_{i})),\varepsilon_{i})=p(f(\mathcal{X}_{\varepsilon_{i}},\varepsilon_{i})))$
(11)

$\begin{split}fid_{+}=1-\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}(p(f(\mathcal{G}(t_{i})),\varepsilon_{i})\\\
=p(f((\mathcal{G}(t_{i})\setminus\mathcal{X}_{\varepsilon_{i}}),\varepsilon_{i})))\end{split}$
(12)

Here, $\varepsilon_{1},...,\varepsilon_{N}$ are possible future links and
$\mathcal{X}_{\varepsilon_{1}},...,\mathcal{X}_{\varepsilon_{N}}$ are the
respective explanations for the predictions of their occurrences. The
indicator function $\mathbbm{1}(a=b)$ returns $1$, if $a$ is equal to $b$,
else it returns $0$.

For these two metrics, $fid_{-}$ measures sufficiency, while $fid_{+}$
assesses necessity. Both scores range from $0$ to $1$, with higher values
indicating better performance. The weighted harmonic mean, $char$, combines
these scores for a comprehensive assessment.

Sparsity, another key metric, measures explanation complexity. Lower values
are preferred, indicating less complex explanations:

$sparsity=\frac{1}{N}\sum_{i=1}^{N}\frac{|\mathcal{X}{\varepsilon_{i}}|}{|C(\mathcal{G},\varepsilon_{i},k,m{max})|}$
(13)

The evaluation also encompasses runtime, which assesses the duration required
for a method to generate explanations; search iterations, examining the
influence of varying search iteration counts on the explanations; and Jaccard
similarity, a metric comparing the overlap between explanations derived from
different methods. The corresponding results are detailed in Appendices E, F,
and G.

| Fidelity+ | Sparsity
---|---|---
| UCI-Messages | UCI-Forums | Wikipedia | UCI-Messages | UCI-Forums | Wikipedia
| corr. | wrg. | corr. | wrg. | corr. | wrg. | corr. | wrg. | corr. | wrg. | corr. | wrg.
T-GNNExplainer | $0.10$ | $0.25$ | $0.05$ | $0.28$ | $0.05$ | $0.22$ | $0.43$ | $0.35$ | $0.29$ | $0.35$ | $0.33$ | $0.43$
GreeDy-rand. | $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-temp. | $0.14$ | $0.33$ | $0.43$ | $0.31$ | $0.10$ | $0.30$ | $0.05$ | $0.04$ | $0.05$ | $0.03$ | $0.06$ | $0.03$
GreeDy-spa-temp. | 0.20 | $0.38$ | 0.46 | $0.30$ | $0.14$ | $0.39$ | $0.08$ | $0.04$ | $0.05$ | $0.04$ | $0.07$ | $0.04$
GreeDy-gradient | $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-rand. | $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-temp. | $0.14$ | $0.39$ | $0.39$ | $0.38$ | $0.13$ | $0.48$ | $0.07$ | $0.04$ | $0.10$ | $0.05$ | $0.06$ | $0.06$
CoDy-spa-temp. | 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-gradient | $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- | Char
| UCI-Messages | UCI-Forums | Wikipedia | UCI-Messages | UCI-Forums | Wikipedia
| corr. | wrg. | corr. | wrg. | corr. | wrg. | corr. | wrg. | corr. | wrg. | corr. | wrg.
T-GNNExplainer | 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-rand. | $0.34$ | $0.97$ | $0.28$ | 0.99 | $0.57$ | 0.93 | $0.04$ | $0.14$ | $0.08$ | $0.12$ | $0.09$ | $0.19$
GreeDy-temp. | $0.56$ | 0.98 | $0.61$ | $0.98$ | $0.77$ | $0.90$ | $0.22$ | $0.49$ | $0.50$ | $0.47$ | $0.17$ | $0.45$
GreeDy-spa-temp. | $0.70$ | $0.96$ | $0.64$ | $0.95$ | $0.82$ | $0.88$ | $0.31$ | $0.54$ | $0.53$ | $0.46$ | $0.23$ | $0.54$
GreeDy-gradient | $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-rand. | $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-temp. | $0.69$ | $0.96$ | $0.66$ | $0.98$ | $0.88$ | $0.88$ | $0.23$ | $0.55$ | $0.49$ | $0.54$ | $0.22$ | $0.62$
CoDy-spa-temp. | $0.72$ | $0.95$ | 0.69 | $0.93$ | 0.91 | $0.86$ | 0.31 | $0.57$ | 0.54 | $0.52$ | 0.30 | $0.65$
CoDy-gradient | $0.70$ | $0.96$ | $0.68$ | $0.95$ | $0.88$ | $0.90$ | $0.27$ | 0.58 | $0.50$ | 0.57 | $0.27$ | 0.68

Table 2: Results on the fidelity+, $sparsity$, fidelity-, and $char$ scores of
the different explanation methods for explaining correct and wrong
predictions. The best result for each experimental setting is bold, and the
second best is underlined.

###  5.2 Results

####  5.2.1 Necessity of Explanations

Table 2 presents a comprehensive view of the $fid_{+}$ scores in various
experimental scenarios. In all but one scenario, CoDy, employing either
spatio-temporal or local-gradient selection strategies, emerges as the most
effective. A consistent trend is observed where CoDy-spatio-temporal excels in
explaining correct predictions across datasets, while CoDy-local-gradient is
superior in elucidating wrong predictions. GreeDy-spatio-temporal shows
optimal performance for correct predictions in the UCI-Messages and UCI-Forums
datasets. The random selection strategy is generally less effective compared
to the others, except for CoDy-temporal, which is marginally inferior to CoDy-
random for correct predictions on the Wikipedia dataset. This indicates that
the temporal, spatio-temporal, and local-gradient strategies enhance the
ability of GreeDy and CoDy to uncover necessary explanations, as evidenced by
their superior $fid_{+}$ scores over the random strategy, especially in the
case of GreeDy.

However, focusing solely on the $fid_{+}$ metric overlooks the objective of
minimizing explanation complexity. Therefore, the sparsity of explanations is
also crucial. Table 2 illustrates the conciseness of explanations provided by
different explainers, showing that GreeDy and CoDy generally offer more
succinct explanations than T-GNNExplainer, highlighting the complexity
advantage of counterfactual explanations. It’s notable that GreeDy variants
consistently yield lower sparsity scores compared to their CoDy counterparts.
Nonetheless, considering these sparsity values in isolation can be misleading,
as minimally sparse explanations are only advantageous if they also pinpoint
crucial information. For example, while GreeDy-random achieves low sparsity
scores, it falls short in $fid_{+}$ score compared to other GreeDy variants.
Higher $fid_{+}$ values are preferable, coupled with lower sparsity. A figure
that displays the cumulative distribution of necessary explanations across
varying sparsity levels is provided in Appendix C.

The disparity between explanations for correct and wrong predictions is
particularly pronounced in the UCI-Messages and Wikipedia datasets. For
incorrect predictions, all explainers identify necessary explanations more
than twice as frequently compared to correct predictions. This phenomenon
could be attributed to the fundamental difference between correct and wrong
predictions. In the case of incorrect predictions, the model misconstrues past
information, making the identification of misleading information comparatively
straightforward. Conversely, for correct predictions, identifying a
counterfactual example requires omitting information to render the prediction
incorrect, which can be challenging if most past data aligns with the
prediction. Despite this disparity, explaining incorrect predictions is
arguably more insightful, as it focuses solely on elucidating the target model
without introducing biases associated with correct predictions.

Overall, CoDy, particularly with the local-gradient and spatio-temporal
strategies, is most adept at achieving the dual objectives of maximizing
counterfactual example discovery and minimizing explanation complexity.
GreeDy-spatio-temporal also demonstrates commendable performance across most
settings.

####  5.2.2 Sufficiency of Explanations

Table 2 delineates the performance of different methods according to this
metric. Given that T-GNNExplainer is designed to provide factual explanations,
it is anticipated to excel in the $fid_{-}$ metric. Indeed, it demonstrates
superior performance for correct predictions in the UCI-Messages dataset.
However, in other settings, different explainers emerge as more effective.
This variation in performance could stem from the implementation nuances of
T-GNNExplainer, specifically, the approximation strategy used in the original
implementation as proposed by its authors (Xia et al., 2023). This strategy,
which involves restricting past events to a $k$-hop neighborhood and
processing input events in batches, might introduce discrepancies between the
approximated and actual model outputs, potentially impacting the $fid_{-}$
scores.

An intriguing observation is the disparity in the performance of CoDy and
GreeDy between correct and wrong predictions. CoDy variants outperform GreeDy
counterparts for correct predictions. However, for wrong predictions, GreeDy
approaches exceed CoDy configurations. Remarkably, the $fid_{-}$ scores for
CoDy and GreeDy in the context of incorrect predictions are consistently high,
exceeding $0.86$ across all settings. This underscores the efficacy of these
methods in explicating wrong predictions, suggesting that counterfactual
explanations inherently possess a high degree of sufficiency for wrong
predictions.

Moreover, CoDy with the spatio-temporal and local-gradient strategies often
parallels or surpasses T-GNNExplainer in $fid_{-}$ scores. The robust
$fid_{-}$ scores achieved by these strategies affirm that the explanations
they generate are largely sufficient for explaining predictions, capturing
relevant information effectively.

####  5.2.3 Convergent Analysis of Sufficiency and Necessity

The characterization score $char$ synthesizes the dimensions of sufficiency
and necessity. Table 2 presents the explainers’ performance along this metric.
Notably, CoDy-local-gradient excels in explaining incorrect predictions,
whereas CoDy-spatio-temporal is superior for correct predictions. This dual
perspective is further illustrated in Appendix D, which compares the
performance of the explainers in both $fid_{+}$ and $fid_{-}$ metrics. The
$fid_{+}$ and $fid_{-}$ scores reveal that CoDy-local-gradient and CoDy-
spatio-temporal not only deliver excellent explanations in terms of necessity
but also maintain comparably strong sufficiency. This underscores the
significance of the fallback strategy, ensuring the provision of explanations
even in the absence of counterfactual examples. This strategy is crucial, as
exemplified by the fact that while the methods cannot find counterfactual
explanations for all cases, depending on the experimental setting, they still
deliver sufficient explanations in most cases. Thus, even though not all
explanations are counterfactual, they consistently highlight pertinent input
information.

####  5.2.4 Comparison of Selection Strategies

The performance of GreeDy and CoDy varies based on their selection strategies,
affecting their operation in explanation approaches. Unlike the random
strategy, other strategies enhance performance in exploring the search space,
as shown by $fid_{+}$ and $fid_{-}$ metrics. The spatio-temporal strategy
performs best for GreeDy, influencing predictions significantly. For CoDy,
there’s no definitive best strategy. The spatio-temporal strategy excels in
explaining correct predictions, while local-gradient is better for incorrect
ones. CoDy-temporal generally ranks third. This pattern is also reflected in
$char$ scores. GreeDy’s explanatory performance is more influenced by the
selection strategy than CoDy’s. CoDy adapts its search based on initial
results, exploring other directions if necessary, while GreeDy sticks to its
initial path, making it more dependent on the selection strategy and prone to
local optima. Overall, the spatio-temporal and local-gradient strategy is
superior in most settings for both GreeDy and CoDy, highlighting spatial
proximity’s importance in link prediction models.

##  6 Conclusion

In this paper, two novel counterfactual explanation methods are proposed for
Temporal Graph Neural Networks. Extensive evaluation reveals that CoDy, which
adapts Monte Carlo Tree Search, outperforms GreeDy and a factual explanation
method T-GNNExplainer, providing counterfactual examples more frequently and
with lower complexity. The experiments also uncover that the heuristic
selection strategy has a large effect on explanatory performance. Using a
selection strategy that considers spatio-temporal aspects and local gradients
to select promising events for the explanation is preferable over random
selection.

Counterfactual examples do not have to be limited to the omission of
information but could also encompass adding events to the input, changing the
node and edge features, or changing the timing of events. However,
incorporating these dimensions would inevitably result in a substantial
expansion of the search space, necessitating the development of novel methods
to effectively navigate and address these more complex circumstances.

## References

  * Amara et al. (2022) 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 methods 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.
  * Baldassarre & Azizpour (2019) Baldassarre, F. and Azizpour, H.  Explainability techniques for graph convolutional networks.  _CoRR_ , abs/1905.13686, 2019.
  * Byrne (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, July 2019.  doi: 10.24963/ijcai.2019/876.
  * Chen & Ying (2023) Chen, J. and Ying, Z.  Tempme: Towards the explainability of temporal graph neural networks via motif discovery.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Cho et al. (2014) Cho, K., Van Merriënboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., and Bengio, Y.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  _arXiv preprint arXiv:1406.1078_ , 2014.
  * European Parliament (2021) European Parliament.  Proposal for a regulation of the european parliament and of the council laying down harmonised rules on artificial intelligence (artificial intelligence act) and amending certain union legislative acts, 2021.
  * Fan et al. (2021) Fan, Y., Yao, Y., and Joe-Wong, C.  Gcn-se: Attention as explainability for node classification in dynamic graphs.  In _2021 IEEE International Conference on Data Mining (ICDM)_ , pp. 1060–1065. IEEE Computer Society, 2021.
  * He et al. (2022) He, W., Vu, M. N., Jiang, Z., and Thai, M. T.  An explainer for temporal graph neural networks.  In _IEEE Global Communications Conference, GLOBECOM 2022, Rio de Janeiro, Brazil, December 4-8, 2022_ , pp. 6384–6389. IEEE, 2022.  doi: 10.1109/GLOBECOM48099.2022.10001619.
  * Huang et al. (2020) Huang, Q., Yamada, M., Tian, Y., Singh, D., Yin, D., and Chang, Y.  Graphlime: Local interpretable model explanations for graph neural networks.  _CoRR_ , abs/2001.06216, 2020.
  * Jumper et al. (2021) Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A., et al.  Highly accurate protein structure prediction with alphafold.  _Nature_ , 596(7873):583–589, 2021.
  * Kazemi et al. (2020) 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.
  * Kumar et al. (2019) Kumar, S., Zhang, X., and Leskovec, J.  Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 1269–1278, Anchorage AK USA, July 2019. ACM.  ISBN 978-1-4503-6201-6.  doi: 10.1145/3292500.3330895.
  * Kunegis (2013) Kunegis, J.  KONECT – The Koblenz Network Collection.  In _Proc. Int. Conf. on World Wide Web Companion_ , pp. 1343–1350, 2013.  URL http://dl.acm.org/citation.cfm?id=2488173.
  * Lam et al. (2022) Lam, R., Sanchez-Gonzalez, A., Willson, M., Wirnsberger, P., Fortunato, M., Pritzel, A., Ravuri, S., Ewalds, T., Alet, F., Eaton-Rosen, Z., et al.  Graphcast: Learning skillful medium-range global weather forecasting.  _arXiv preprint arXiv:2212.12794_ , 2022.
  * Liu et al. (2023) 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 Representations (ICLR 2023)_. International Conference on Learning Representations, 2023.
  * Longa et al. (2023) 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.  _arXiv preprint arXiv:2302.01018_ , 2023.
  * Lucic et al. (2022) Lucic, A., ter Hoeve, M. A., Tolomei, G., de Rijke, M., and Silvestri, F.  Cf-gnnexplainer: Counterfactual explanations for graph neural networks.  In _International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event_ , volume 151 of _Proceedings of Machine Learning Research_ , pp. 4499–4511. PMLR, 2022.
  * Luo et al. (2020) 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.
  * Ma et al. (2020) Ma, Y., Guo, Z., Ren, Z., Tang, J., and Yin, D.  Streaming graph neural networks.  In _Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020_ , pp. 719–728. ACM, 2020.  doi: 10.1145/3397271.3401092.
  * Makarov et al. (2021) Makarov, I., Savchenko, A., Korovko, A., Sherstyuk, L., Severin, N., Mikheev, A., and Babaev, D.  Temporal graph network embedding with causal anonymous walks representations.  _arXiv preprint arXiv:2108.08754_ , 2021.
  * Pope et al. (2019) Pope, P. E., Kolouri, S., Rostami, M., Martin, C. E., and Hoffmann, H.  Explainability methods for graph convolutional 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.  doi: 10.1109/CVPR.2019.01103.
  * Prado-Romero et al. (2023) Prado-Romero, M. A., Prenkaj, B., Stilo, G., and Giannotti, F.  A Survey on Graph Counterfactual Explanations: Definitions, Methods, Evaluation.  _ACM Comput. Surv._ , September 2023.  ISSN 0360-0300.  doi: 10.1145/3618105.  arXiv:2210.12089 [cs].
  * Rossi et al. (2020) Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., and Bronstein, M. M.  Temporal graph networks for deep learning on dynamic graphs.  _CoRR_ , abs/2006.10637, 2020.
  * Schnake et al. (2020) Schnake, T., Eberle, O., Lederer, J., Nakajima, S., Schütt, K. T., Müller, K., and Montavon, G.  XAI for graphs: Explaining graph neural network predictions by identifying relevant walks.  _CoRR_ , abs/2006.03589, 2020.
  * Souza et al. (2022) Souza, A. H., Mesquita, D., Kaski, S., and Garg, V.  Provably expressive temporal graph networks.  In _NeurIPS_ , 2022.
  * Stanley (1986) Stanley, R. P.  _Enumerative Combinatorics_.  Springer US, Boston, MA, 1986.  ISBN 978-1-4615-9765-0 978-1-4615-9763-6.  doi: 10.1007/978-1-4615-9763-6.
  * Tan et al. (2022) Tan, J., Geng, S., Fu, Z., Ge, Y., Xu, S., Li, Y., and Zhang, Y.  Learning and evaluating graph neural network explanations 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.  doi: 10.1145/3485447.3511948.
  * Trivedi et al. (2019) Trivedi, R., Farajtabar, M., Biswal, P., and Zha, H.  Dyrep: Learning representations over dynamic graphs.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.
  * Vu & Thai (2020) 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 Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Vu & Thai (2022) Vu, M. N. and Thai, M. T.  On the limit of explaining black-box temporal graph neural networks.  _CoRR_ , abs/2212.00952, 2022.  doi: 10.48550/arXiv.2212.00952.
  * Wachter et al. (2017) Wachter, S., Mittelstadt, B., and Russell, C.  Counterfactual explanations without opening the black box: Automated decisions and the gdpr.  _Harv. JL & Tech._, 31:841, 2017.
  * Wu et al. (2020) Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y.  A comprehensive survey on graph neural networks.  _IEEE transactions on neural networks and learning systems_ , 32(1):4–24, 2020.
  * Xia et al. (2023) Xia, W., Lai, M., Shan, C., Zhang, Y., Dai, X., Li, X., and Li, D.  Explaining temporal graph models through an explorer-navigator framework.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Xie et al. (2022) Xie, J., Liu, Y., and Shen, Y.  Explaining dynamic graph neural networks via relevance back-propagation.  _arXiv preprint arXiv:2207.11175_ , 2022.
  * Xu et al. (2020) Xu, D., Ruan, C., Körpeoglu, E., Kumar, S., and Achan, K.  Inductive representation learning on temporal graphs.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020.
  * Ying et al. (2019) 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, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pp. 9240–9251, 2019.
  * Yuan et al. (2020) Yuan, H., Tang, J., Hu, X., and 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.  doi: 10.1145/3394486.3403085.
  * Yuan et al. (2021) Yuan, H., Yu, H., Wang, J., Li, K., and Ji, S.  On explainability 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.
  * Yuan et al. (2023) 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.  doi: 10.1109/TPAMI.2022.3204236.
  * Zhao et al. (2019) Zhao, L., Song, Y., Zhang, C., Liu, Y., Wang, P., Lin, T., Deng, M., and Li, H.  T-gcn: A temporal graph convolutional network for traffic prediction.  _IEEE transactions on intelligent transportation systems_ , 21(9):3848–3858, 2019.

##  Appendix A Example GreeDy

Figure 2 depicts the operation of GreeDy. Each iteration involves selecting
three past events ($l=3$) using a strategy $\delta$. Starting from the root
node, node $n_{2}$ is chosen as the best node ($n_{best}$) in the first
iteration, with a perturbation set $s_{2}={\varepsilon_{2}}$ and a prediction
score of $1.996$. As iterations proceed, the prediction score of $n_{best}$
decreases until it becomes negative in the third iteration. At this point, the
search ends, yielding the counterfactual example
$\mathcal{X}=s_{9}={\varepsilon_{2},\varepsilon_{1},\varepsilon_{5}}$.

$n_{root}$$n_{2}$$n_{1}$$n_{3}$Iteration $1$: $n_{best}\leftarrow n_{2}$
$prediction_{best}=1.996$ $s_{best}=\\{\varepsilon_{2}\\}$ Initialization:
$n_{best}\leftarrow n_{root}$
$prediction_{orig}=2.854$ $n_{4}$$n_{5}$$n_{6}$Iteration $2$:
$n_{best}\leftarrow n_{4}$ $prediction_{best}=0.816$
$s_{best}=\\{\varepsilon_{2},\varepsilon_{1}\\}$
$n_{7}$$n_{8}$$n_{9}$Iteration $3$: $n_{best}\leftarrow n_{9}$
$prediction_{best}=-0.052$
$s_{best}=\\{\varepsilon_{2},\varepsilon_{1},\varepsilon_{5}\\}$ Figure 2:
Example for the operation of the GreeDy approach.

##  Appendix B Example CoDy

Figure 3 illustrates the CoDy algorithm’s search process in constructing a
partial search tree. In this example, three past events,
$\varepsilon_{1},\varepsilon_{2},\varepsilon_{3}$, are considered as candidate
events. Initially, the root node’s simulation yields a prediction score of
$3.179$, indicating a likely future link. The first expansion adds child nodes
for each event. In the second iteration, selection strategy $\delta$ chooses
node $n_{2}$, which is then expanded to include combinations
${\varepsilon_{1},\varepsilon_{2}}$ and ${\varepsilon_{2},\varepsilon_{3}}$.
The third iteration focuses on node $n_{5}$, adding a child node
${\varepsilon_{1},\varepsilon_{2},\varepsilon_{3}}$. The fourth iteration
involves selecting and backpropagating node $n_{6}$, rendering it and its
parent $n_{5}$ unselectable.

In the fifth iteration, due to high exploration scores, node $n_{1}$ is
selected over $n_{2}$. Its simulation results in a negative score, identifying
a counterfactual example. Dynamic constraints then mark nodes with more than
one element in their perturbation set as unselectable, affecting node $n_{4}$
and subsequently $n_{2}$. Finally, node $n_{3}$ is selected as the only
remaining option. With no nodes left to explore, the search concludes,
selecting node $n_{1}$ and its associated perturbation set ${\varepsilon_{1}}$
as the minimal counterfactual example.

Figure 3: Schematic depiction of the iterative expansion of the partial search
tree.

##  Appendix C Fidelity+ to Sparsity

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$sparsity$$fid_{+}$Correct
predictions$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$sparsity$$fid_{+}$Wrong
predictionsUCI-Messages

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$sparsity$$fid_{+}$Correct
predictions$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$sparsity$$fid_{+}$Wrong
predictionsUCI-Forums

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$sparsity$$fid_{+}$Correct
predictions$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$sparsity$$fid_{+}$Wrong
predictionsWikipediarandom temporal spatio-temporal local-gradient no
selection strategy CoDy GreeDy T-GNNExplainer

Figure 4: Results on the relation between $fid_{+}$ and $sparsity$ for the
different experimental settings.

##  Appendix D Fidelity+ to Fidelity-

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$fid_{-}$$fid_{+}$Correct
predictions$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$fid_{-}$$fid_{+}$Wrong
predictionsUCI-Messages

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$fid_{-}$$fid_{+}$Correct
predictions$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$fid_{-}$$fid_{+}$Wrong
predictionsUCI-Forums

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$fid_{-}$$fid_{+}$Correct
predictions$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$fid_{-}$$fid_{+}$Wrong
predictionsWikipediarandom temporal spatio-temporal local-gradient no
selection strategy CoDy GreeDy T-GNNExplainer

Figure 5: Results on the $fid_{+}$ score in relation to the $fid_{-}$ score
achieved by the explanation approaches.

##  Appendix E Runtime

CoDyGreedyCFT-GNNExplainer$0$$50$$100$Duration per explanation (s)UCI-Messages

CoDyGreedyCFT-GNNExplainer$0$$50$$100$Duration per explanation (s)UCI-Forums

CoDyGreedyCFT-GNNExplainer$0$$100$$200$Duration per explanation (s)Wikipedia

random temporal spatio-temporal local-gradient no selection strategy Correct
prediction Wrong prediction

Figure 6: Average duration for explaining predictions across various settings.

Figure 6 presents the average explanation times across datasets. GreeDy
consistently requires the least time, with its local-gradient variant taking
longer due to more frequent calls to the link prediction function, as detailed
in Table 3. 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.

Regarding explanation duration, CoDy, GreeDy, and T-GNNExplainer spend 97.85%,
99.83%, and 82.72% of their time, respectively, on calling the link prediction
function. This suggests that a faster link prediction model could reduce
explanation times. Notably, T-GNNExplainer allocates more time to the search
process than the other methods.

Table 3 shows consistent call frequencies to the prediction model across
datasets for each explainer. However, CoDy and GreeDy show significant
variation in explanation times across datasets, especially on the Wikipedia
dataset. This could be due to the dataset’s longer model response times,
possibly because of its edge features and larger size compared to the other
datasets.

Overall, GreeDy offers the shortest explanation durations, making it
preferable for rapid explanations.

| UCI-Messages | UCI-Forums | Wikipedia
---|---|---|---
| Correct | Wrong | Correct | Wrong | Correct | Wrong
GreeDy-random | $27.10$ | $23.40$ | $24.80$ | $21.80$ | $23.15$ | $18.55$
GreeDy-temporal | $43.70$ | $29.85$ | $36.15$ | $29.15$ | $32.30$ | $24.65$
GreeDy-spatio-temporal | $57.60$ | $29.40$ | $37.65$ | $35.25$ | $39.35$ | $22.35$
GreeDy-local-gradient | $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$
CoDy-spatio-temporal | $287.95$ | $245.44$ | $260.95$ | $256.44$ | $284.98$ | $236.26$
CoDy-local-gradient | $346.50$ | $292.23$ | $312.00$ | $305.70$ | $339.90$ | $272.52$
Table 3: Results on the average number of calls to the link prediction
function performed by the explanation methods for the different experimental
settings.

##  Appendix F Search Iterations

In the experiments with CoDy, a key parameter is the maximum number of search
iterations ($it_{max}$), initially set at 300. Further investigation on
performance involved increasing $it_{max}$ to 1200, specifically focusing on
correct predictions in the Wikipedia dataset where GreeDy-spatio-temporal
surpasses all CoDy variants. Figure 7 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 local-gradient strategies require fewer
iterations, CoDy-spatio-temporal and CoDy-temporal need close to 1000 and 1200
iterations, respectively, for superiority.

$0$$200$$400$$600$$800$$1{,}000$$1{,}200$$0$$0.1$$0.2$$0.3$$0.4$$0.5$Search
iterations ($it_{max}$)$fid_{+}$random temporal spatio-temporal local-gradient
CoDy GreeDy  Figure 7: Comparison of $fid_{+}$ scores for various explanation
methods on the Wikipedia dataset, 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 a need for optimizing the hyperparameters $\alpha$ and
$\beta$, 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 partial search tree
performance implies an imbalance in its search strategy.

##  Appendix G Similarities in Explanations

The Jaccard similarity is used to compare explanations from various
explainers, focusing on correct predictions in the Wikipedia dataset (Figure
8). This heatmap serves as a representative example. T-GNNExplainer’s
explanations differ significantly from those of GreeDy and CoDy, partly due to
their lower sparsity (Table 2). GreeDy-temporal and GreeDy-spatio-temporal
show high similarity, as do GreeDy-spatio-temporal and CoDy explanations.

Comparatively, CoDy variants’ explanations are more similar to each other.
CoDy-temporal and CoDy-spatio-temporal have high similarities with each other
and with CoDy-local-gradient. This indicates CoDy’s search procedure’s ability
to explore similar areas, highlighting the likeness of temporal, spatio-
temporal, and local-gradient strategies over the random strategy.

T-GNNExplainerGreedyCF-randomGreedyCF-temporalGreedyCF-spatio-
temporalGreedyCF-local-gradientCoDy-randomCoDy-temporalCoDy-spatio-
temporalCoDy-local-gradientT-GNNExplainerGreedyCF-randomGreedyCF-
temporalGreedyCF-spatio-temporalGreedyCF-local-gradientCoDy-randomCoDy-
temporalCoDy-spatio-temporalCoDy-local-
gradient1.000.050.080.090.050.060.090.110.080.051.000.170.090.220.100.110.110.110.080.171.000.460.300.230.330.300.270.090.090.461.000.230.270.370.400.360.050.220.300.231.000.210.240.240.240.060.100.230.270.211.000.380.380.410.090.110.330.370.240.381.000.740.510.110.110.300.400.240.380.741.000.540.080.110.270.360.240.410.510.541.00$0.2$$0.4$$0.6$$0.8$$1$Jaccard
similarity Figure 8: Results on the Jaccard similarity between explanations of
correct predictions on the Wikipedia dataset.