Research map / Graph learning / Knowledge and temporal graphs
CoDy: Counterfactual Explainers for Dynamic Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CoDy, a Monte Carlo Tree Search-based model-agnostic counterfactual explainer for TGNN future link predictions on continuous-time dynamic graphs, plus a greedy baseline GreeDy.
Problem
Explaining predictions of temporal graph neural networks on continuous-time dynamic graphs; existing explainers for TGNNs are factual only, and no counterfactual explainer existed for CTDG-based TGNNs.
Approach
Adapts Monte Carlo Tree Search to search over subsets of past events to omit, guided by spatial, temporal, and event-impact selection policies, to find minimal counterfactual event sets that flip a future-link prediction.
Key results
- CoDy-spatio-temporal achieves about 16% higher AUFSC+ than the strongest baseline GreeDy-spatio-temporal across tasks.
- T-GNNExplainer averages 75.05% lower AUFSC+ than CoDy-spatio-temporal.
- CoDy variants generally achieve the highest AUFSC+ and char scores on TGN and TGAT across the three datasets, with GreeDy occasionally best on UCI-Forums correct predictions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CoDy with spatio-temporal selection instead of the strongest baseline | TGN explanations · Across all evaluated tasks | AUFSC+: 16% | Helped |
| Use spatio-temporal selection instead of random selection (ablation) | CoDy · Across evaluated tasks | AUFSC+: 36.7% | Helped |
| Use temporal selection instead of random selection (ablation) | CoDy · Across evaluated tasks | AUFSC+: 14.3% | Helped |
| Use event-impact selection instead of random selection (ablation) | CoDy · Across evaluated tasks | AUFSC+: 29.6% | Helped |
| Use spatio-temporal selection instead of random selection (ablation) | GreeDy · Across evaluated tasks | AUFSC+: 485% | Helped |
| Use temporal selection instead of random selection (ablation) | GreeDy · Across evaluated tasks | AUFSC+: 386% | Helped |
| Use event-impact selection instead of random selection (ablation) | GreeDy · Across evaluated tasks | AUFSC+: 304% | Helped |
| Use spatio-temporal selection for correct predictions and event-impact selection for incorrect predictions (ablation) | CoDy · TGN explanations across UCI-Messages, UCI-Forums, and Wikipedia | AUFSC+: 0.19 vs 0.16; 0.43 vs 0.39; 0.16 vs 0.14; 0.39 vs 0.38; 0.52 vs 0.50 | Mixed |
Surprising findings
- Explaining incorrect predictions was easier (higher AUFSC+) than explaining correct ones, by more than a factor of two on UCI-Messages and Wikipedia for all explainers.
- Factual baselines PGExplainer and T-GNNExplainer do not consistently beat counterfactual methods on sufficiency (AUFSC-).
Limitations
- CoDy requires substantially more TGNN calls and runtime than GreeDy and factual baselines.
- Only event removal is supported; adding nodes/edges, feature edits, or timestamp changes are not explored.
- Evaluated only on three datasets and two TGNN models (TGN, TGAT); no user study of explanation usefulness.
Experimental setup
Datasets: Wikipedia UCI-Messages UCI-Forums
Benchmarks: Wikipedia UCI-Messages UCI-Forums
Metrics: AUFSC+ AUFSC- characterization score (char) fidelity+ fidelity- sparsity runtime
Baselines: PGExplainer T-GNNExplainer GGreeDy (greedy counterfactual baseline) Random selection policy
Builds on: Monte Carlo Tree Search UCB1 T-GNNExplainer PGExplainer TGN TGAT
Closest papers by meaning
- Training-free Counterfactual Explanation for Temporal Graph Model Inference (ICLR 2026 · similarity 0.93)
- COMRECGC: Global Graph Counterfactual Explainer through Common Recourse (ICML 2025 · similarity 0.87)
- UNR-Explainer: Counterfactual Explanations for Unsupervised Node Representation Learning Models (ICLR 2024 · similarity 0.86)
- Graph Inverse Style Transfer for Counterfactual Explainability (ICML 2025 · similarity 0.86)
- Unifying Text Semantics and Graph Structures for Temporal Text-attributed Graphs with Large Language Models (NeurIPS 2025 · similarity 0.86)
- Temporal-Aware Evaluation and Learning for Temporal Graph Neural Networks (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.