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

Deep learning detectors for anomalies in dynamic graphs have achieved 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. The paper addresses 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.

The paper makes five contributions:

1. Presents X-AddGraph, to our knowledge the first post-hoc explainability framework for AddGraph and for the GCN+GRU paradigm of dynamic graph anomaly detection.

2. Introduces Dual Spatial-Temporal Attribution (DSTA), "a three-component mechanism in which each component is aligned with one architectural module of the detector: gradient-based relevance over the adjacency (spatial), direct reading of the CAB attention distribution (short-term, at zero additional cost), and gradient rollback through the GRU hidden states (long-term)."

3. Shows the framework is strictly post-hoc: detection AUC is preserved exactly by construction, and we verify ∆AUC = 0 empirically to ten decimal places.

4. Evaluates on a broadened protocol covering four edge populations (confident true positives, low-confidence true positives, false positives, and random samples) across multiple seeds, demonstrating that the long-term attribution identifies historical snapshots carrying substantially more counterfactual signal than random selection—a capability structurally unavailable to spatially-blind explainers.

5. Provides a qualitative walkthrough of real flagged anomalies and releases implementation publicly.

AddGraph maintains a hidden state matrix Ht across snapshots with three coupled operations:

• Structural encoding: A graph attention network takes the previous hidden state and current adjacency to produce a structural summary. Crucially, the input is accumulated temporal memory, not raw features: the spatial and temporal dimensions are coupled from the first step.

• Short-term attention (CAB): Over a sliding window of size ω, the contextual attention block computes attention vectors that constitute a normalized, model-endogenous importance distribution over the window—a fact our method exploits directly.

• Long-term integration (GRU): A GRU fuses the structural and short-term summaries through update and reset gates into the new state. History prior to the window is encoded implicitly in the recurrence.

The anomaly score for an edge is computed as: f(i,j,w) = w · σ(β‖a ⊙ hti + b ⊙ htj‖2 − µ), where σ is the logistic function applied exactly once.

Three principles guide the framework:

• (P1) Strictly post-hoc: The framework operates on a frozen, trained AddGraph. No retraining, no weight modification, no change to the inference pipeline.

• (P2) Architecture-aligned decomposition: A complete explanation must answer three orthogonal questions, one per architectural module.

• (P3) Exploit free signals: "The CAB attention weights are computed during every forward pass and already form a normalized distribution over window steps. Reading them directly is both computationally free and exactly faithful to the model's own internal weighting."

Component 1 (Spatial): Uses input-weighted gradient attribution over the adjacency matrix: φsp uv = At uv · ∂f/∂At uv. This gradient×input form is the practical instantiation of relevance propagation for the ELU-activated convolutional layer and correctly traverses the coupled path: the gradient flows backward through the score function, the GRU gates, and the graph attention layer in a single backward pass.

Component 2 (Short-term, zero-cost): Reads the cached CAB attention vectors directly: φsh s = ½(ati*[s] + atj*[s]). Since the softmax in Eq. (1) guarantees Σs ati[s] = 1, the attribution is a valid probability distribution requiring no renormalization and no additional computation whatsoever.

Component 3 (Long-term): Uses gradient rollback through the GRU hidden states via backpropagation through time: gk = ‖∂f/∂Ht*−ω−k‖F, with normalized weights φlo k = gk/Σk′ gk′. The rollback naturally respects the GRU's gating: snapshots whose influence was suppressed by the reset gate receive proportionally small gradient signal.

Each flagged edge receives the DSTA triplet: E(i*,j*) = (N*, t*−ω+s*, t*−ω−k*), read as: the anomaly is driven primarily by connections to N*; the most suspicious recent behavior occurred at window step s*; the historical context most responsible originates k* snapshots before the window.

Dataset: UCI Message benchmark with 1,899 nodes and 59,835 timestamped edges. The first 50% forms the training graph; anomalous edges are injected at 5%; snapshots contain 5,300 edges. The detector is trained for 35 epochs with original hyperparameters (hidden dimension 100, window ω=2, margin γ=0.6, four attention heads).

Detector performance: The trained detector reaches an average per-snapshot AUC of 0.8705 (per-snapshot values 0.895/0.867/0.852/0.873/0.849/0.888), exceeding the originally published 0.8083.

Edge populations: Four populations of ten edges each: confident true positives, low-confidence true positives, false positives, and random samples. All experiments repeated over two random seeds with mean ± standard deviation reported.

Baseline: A flat-gradient baseline—the same input-weighted adjacency gradient, but with no temporal decomposition of any kind—representative of what any static, spatially-oriented explainer can offer.

Detection preservation: "Because X-AddGraph never touches the detector, its detection performance is identical to AddGraph's by construction; we verify this empirically by reproducing every flagged edge's score through the explanation pipeline and measuring the maximum absolute deviation: ∆ = 0.0000000000."

Structural fidelity: The top-k structural explanation reproduces the anomaly score essentially perfectly on all true positives (Fidelity+ = 1.000 ± 0.000 to 1.001 ± 0.004) and near-perfectly on false positives (0.997 ± 0.006). Sparsity rises monotonically from 0.000 for confident anomalies to 0.750 for random edges.

Temporal fidelity: "The historical snapshot identified by X-AddGraph's gradient rollback carries a counterfactual divergence of 0.127, against 0.074 for a random pick—a 73% relative advantage, concentrated most strongly on confident true positives (0.332 vs. 0.125). This is precisely the capability that no static explainer possesses: a flat-gradient method has no mechanism for ranking historical snapshots at all and is reduced to random selection on this dimension."

Runtime: "A full DSTA explanation takes 10.1 s per flagged edge on a single T4 GPU (spatial pass, cached attention read, and K=5 BPTT rollbacks), against 1.65 s for the flat-gradient baseline that produces only the spatial component. The overhead applies exclusively to flagged edges—a small fraction of the stream—and leaves detection throughput untouched."

Three flagged anomalies are walked through:

• Edge (17, 1199), score 0.9911: spatial attribution points to the endpoint pair itself 1199, 17, indicating an isolated, structurally unprecedented connection; long-term component points to lag 4 (weight 0.475).

• Edge (490, 888), score 0.9544: spatial drivers 888, 490, 34 with a third participating node; long-term identifies the immediately pre-window snapshot (lag 1, weight 0.473).

• Edge (931, 698), score 0.6986: a lower-confidence alarm with "a richer structural explanation 1263, 698, 1282, 244 and the strongest historical concentration of the three (lag 1, weight 0.668)—the analyst learns that this alarm rests predominantly on recent historical memory rather than on the instantaneous topology."

Generalization: DSTA's design principle—align each attribution component with one architectural module—extends by construction to the GCN+GRU family AddGraph founded. StrGNN shares the same backbone at the subgraph level; EvolveGCN admits the same gradient rollback through its recurrent weight evolution; the short-term component transfers to any architecture exposing an internal attention distribution.

Limitations:

1. "The discriminative power of the short-term component is inherently bounded by AddGraph's original window size ω = 2, under which the attention distribution has a single degree of freedom and remains close to uniform in the trained model."

2. The present evaluation covers one benchmark; extending to Digg and to heterogeneous settings is planned.

3. Our fidelity metrics are counterfactual proxies; ground-truth causal evaluation would require benchmarks with annotated culprit structures, which do not yet exist for dynamic graph anomaly detection.

The paper concludes: Detection without explanation is useful; detection with a faithful, architecture-aligned explanation is auditable, trustworthy, and actionable—the standard that cooperative information systems increasingly demand.

Improvements to AI Systems:

1. Architecture-Aligned Explainability for Recurrent Graph Models: I can implement a post-hoc attribution framework that decomposes explanations into spatial (gradient×input over adjacency), short-term (direct read of internal attention distributions), and long-term (gradient rollback through GRU hidden states) components. This enables any GCN+GRU-based anomaly detector to provide auditable, three-part explanations for each flagged edge without retraining or altering detection performance.

2. Zero-Cost Temporal Attribution via Internal Attention Caching: I can exploit existing attention weights computed during forward passes to generate short-term temporal explanations at no additional computational cost. This makes explainability feasible in real-time streaming environments where latency is critical.

3. Counterfactual Historical Snapshot Ranking: I can use gradient rollback through recurrent hidden states to rank historical snapshots by their causal influence on a current anomaly score. This provides a capability that static explainers lack—identifying which past time steps most contributed to a current flag, enabling analysts to trace anomalies to their temporal origins.

4. Fidelity-Preserving Explanation Pipeline: I can guarantee that explanations do not alter detection accuracy by construction (verified to 10 decimal places), making the system safe for deployment in regulated environments where both performance and interpretability are non-negotiable.

5. Confidence-Aware Explanation Granularity: I can automatically adjust explanation sparsity based on anomaly confidence—providing dense, precise attributions for high-confidence true positives and sparser, more cautious explanations for low-confidence or false-positive flags. This helps analysts calibrate trust in both the detection and its explanation.

6. Multi-Population Evaluation Protocol for Explainers: I can adopt a rigorous evaluation methodology that tests explainers across four edge populations (confident true positives, low-confidence true positives, false positives, random samples) and multiple seeds, ensuring robustness and revealing where explanations are most and least reliable.

7. Transferable Explainability Across GCN+GRU Variants: I can extend the same architecture-aligned attribution principles to related models like StrGNN (subgraph-level) and EvolveGCN (weight evolution), providing a unified explainability layer across a family of dynamic graph detectors.

8. Actionable Analyst Workflow: I can output a structured triplet per flagged edge—(key structural driver, most suspicious recent window step, most responsible historical lag)—that directly answers what, when, and why for each alarm, enabling faster triage and incident response in cooperative information systems.

What the Improved AI System Can Do:

• Detect anomalies in dynamic graphs with state-of-the-art accuracy while simultaneously explaining every flag in three complementary dimensions (structure, short-term context, long-term history).

• Operate in real-time streaming settings, as the short-term explanation is free and the full explanation adds only 10 seconds per flagged edge on a single GPU, without affecting detection throughput.

• Provide auditable, trustworthy decisions in regulated environments (e.g., financial fraud, network intrusion) where automated actions must be justified to stakeholders or regulators.

• Enable analysts to distinguish between anomalies driven by unprecedented topology (e.g., a new connection between isolated nodes) versus those driven by recent historical context (e.g., a node exhibiting suspicious behavior over the past few snapshots).

• Trace anomalies back to specific historical snapshots with 73% better counterfactual signal than random selection, allowing root-cause analysis of recurring attack patterns.

• Maintain identical detection performance before and after explanation, ensuring that adding interpretability never compromises accuracy.

• Generalize to other GCN+GRU-based detectors without architectural changes, providing a plug-and-play explainability module for a broad class of dynamic graph models.