  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.
