# Dual Spatial-Temporal Attribution: Architecture-Aligned Post-Hoc Explainability for Recurrent Graph Anomaly Detection

arXiv: https://arxiv.org/abs/2608.12441 · HTML: https://mlsanity.com/paper/2608.12441/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 16 references that are in the map.
- First posted on arXiv 12 Aug 2026.

## Builds on (most cited first, 8 of 8)

- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [GraphSVX: Shapley Value Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.10482/) (2021)
- [Anomaly Detection in Dynamic Graphs via Transformer](https://mlsanity.com/paper/2106.09876/) (2021)
- [Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs](https://mlsanity.com/paper/2005.07427/) (2020)
- [Anomaly Detection in Dynamic Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2406.00134/) (2024)
- [Explaining Dynamic Graph Neural Networks via Relevance Back-propagation](https://mlsanity.com/paper/2207.11175/) (2022)
- [DyExplainer: Explainable Dynamic Graph Neural Networks](https://mlsanity.com/paper/2310.16375/) (2023)

## Abstract (arXiv)

Deep learning detectors for anomalies in dynamic graphs have reached strong accuracy, yet they remain opaque: when an edge is flagged, the analyst receives a score but no reason. This opacity is untenable in the cooperative, regulated information systems where such detectors are deployed, where automated decisions must be auditable and trustworthy. We address this gap for AddGraph, the foundational GCN+GRU framework for edge-level anomaly detection in dynamic graphs, which to our knowledge has never been equipped with any form of explainability. We present a strictly post-hoc explainability framework, X-AddGraph, built on a Dual Spatial-Temporal Attribution (DSTA) mechanism whose three components are each aligned with one of AddGraph's architectural modules: a gradient-based relevance attribution over the current adjacency structure (spatial), a direct reading of the contextual attention weights already computed during inference (short-term temporal, at zero additional cost), and a gradient rollback through the recurrent hidden states (long-term temporal). Because the detector is frozen, detection performance is preserved exactly (Delta AUC = 0, verified empirically to ten decimal places). On the UCI Message benchmark, our trained AddGraph baseline reaches an average per-snapshot AUC of 0.8705, exceeding the originally published result; X-AddGraph reproduces every score identically while adding explanations where none existed. Evaluated across four edge populations - confident true positives, low-confidence true positives, false positives, and random samples - the long-term attribution identifies historical snapshots carrying significantly more counterfactual signal than random selection (0.127 vs. 0.074), a capability that no spatially-blind explainer can provide. We release our implementation for full reproducibility.