Paper deep dive

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

Iyad Assaad Nekka, Hamida Seba, Khaled Walid Hidouci, Karima Amrouche

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 33

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%

Last extracted: 8/14/2026, 4:22:07 AM

Summary

The paper introduces X-AddGraph, a post-hoc explainability framework for the AddGraph dynamic graph anomaly detector. It employs a Dual Spatial-Temporal Attribution (DSTA) mechanism to provide faithful explanations for flagged edges by attributing scores to spatial neighbors, short-term temporal attention, and long-term historical snapshots, without modifying the frozen detector or degrading its AUC performance.

Entities (10)

AddGraph · model · 99%X-AddGraph · framework · 98%DSTA · method · 95%UCI Message · dataset · 92%GCN · component · 90%GRU · component · 90%CAB · component · 88%EvolveGCN · model · 85%StrGNN · model · 85%GNNExplainer · method · 82%

Relation Signals (10)

X-AddGraph → explains → AddGraph

confidence 98% · We present a strictly post-hoc explainability framework, X-AddGraph... for AddGraph

X-AddGraph → usesmechanism → DSTA

confidence 95% · X-AddGraph, built on a Dual Spatial-Temporal Attribution (DSTA) mechanism

X-AddGraph → evaluatedon → UCI Message

confidence 92% · On the UCI Message benchmark, our trained AddGraph baseline reaches an average per-snapshot AUC of 0.8705

DSTA → alignswith → AddGraph

confidence 90% · whose three components are each aligned with one of AddGraph's architectural modules

AddGraph → consistsof → GCN

confidence 90% · AddGraph, the foundational GCN+GRU framework

AddGraph → consistsof → GRU

confidence 90% · AddGraph, the foundational GCN+GRU framework

AddGraph → usescomponent → CAB

confidence 88% · a contextual attention block (CAB) that summarizes a sliding window of past states

StrGNN → followsparadigm → AddGraph

confidence 85% · establishing the GCN+GRU paradigm that subsequent methods such as StrGNN [2]... have followed

EvolveGCN → followsparadigm → AddGraph

confidence 85% · establishing the GCN+GRU paradigm that subsequent methods such as... EvolveGCN [3] have followed

GNNExplainer → comparedwith → X-AddGraph

confidence 80% · All assume a static model and provide no mechanism for temporal attribution: applied to AddGraph, each would explain at most the structural component

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

31,699 characters extracted from source content.

Expand or collapse full text

Dual Spatial-Temporal Attribution: Architecture-Aligned Post-Hoc Explainability for Recurrent Graph Anomaly Detection Iyad Assaad Nekka Affiliation: LCSI Laboratory, National Higher School of Computer Science (ESI), Algiers, Algeria E-mail i_nekka, w_hidouci, k_amrouche@esi.dz Hamida Seba Affiliation: Université Claude Bernard Lyon 1, Lyon, France E-mail hamida.seba@univ-lyon1.fr Khaled-Walid Hidouci Affiliation: LCSI Laboratory, National Higher School of Computer Science (ESI), Algiers, Algeria E-mail i_nekka, w_hidouci, k_amrouche@esi.dz Karima Amrouche Affiliation: LCSI Laboratory, National Higher School of Computer Science (ESI), Algiers, Algeria E-mail i_nekka, w_hidouci, k_amrouche@esi.dz Abstract 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 (Δ =0=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. Keywords: Dynamic graphs Anomaly detection Explainable AI Post-hoc attribution Graph neural networks Trustworthy information systems. 1 Introduction Modern cooperative information systems—financial transaction networks, enterprise communication platforms, distributed infrastructures—generate continuous streams of interactions that are most naturally modeled as dynamic graphs: sequences of graph snapshots in which nodes and edges appear, evolve, and vanish over time. Detecting anomalous edges in these streams is a critical capability: a fraudulent transaction, a lateral-movement connection in an intrusion, or a coordinated manipulation campaign all manifest as edges that deviate from the system’s learned normality. Deep learning has become the dominant paradigm for this task. AddGraph [1], presented at IJCAI 2019, was among the first and remains among the most influential frameworks: it combines a graph attention network for structural encoding with a contextual attention-based module and a Gated Recurrent Unit (GRU) for temporal integration, establishing the GCN+GRU paradigm that subsequent methods such as StrGNN [2] and EvolveGCN [3] have followed. Yet AddGraph, like the family it founded, is a black box. When it flags an edge as anomalous, it produces a probability and nothing else. An analyst cannot determine whether the alarm is driven by the edge’s structural neighborhood in the current snapshot, by a suspicious pattern within the recent attention window, or by long-term historical memory accumulated in the recurrent state. In the cooperative and regulated environments that motivate this conference—where decisions must be justified to auditors, regulators, and affected parties—a detector that cannot explain itself is difficult to trust, audit, or act upon. To our knowledge, no prior work has equipped AddGraph, or any GCN+GRU dynamic graph anomaly detector, with post-hoc explainability. The challenge is architectural. AddGraph’s anomaly score is the product of three coupled components: a graph convolution that propagates the previous hidden state (not raw features) through the current adjacency; a contextual attention block (CAB) that summarizes a sliding window of past states; and a GRU that fuses both into the state used for scoring. A single generic attribution method cannot disentangle these three signal paths. A complete explanation must answer three distinct questions: which neighbors, which recent step, and which historical snapshot drove the decision. Contributions. This paper makes the following contributions: 1. We present 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. We introduce 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. We show that the framework is strictly post-hoc: detection AUC is preserved exactly by construction, and we verify ΔAUC=0 =0 empirically to ten decimal places. 4. We evaluate on a broadened protocol covering four edge populations (confident true positives, low-confidence true positives, false positives, and random samples) across multiple seeds, comparing against a flat-gradient baseline, and demonstrate 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. We provide a qualitative walkthrough of real flagged anomalies and release our implementation publicly for full reproducibility.11 1 https://github.com/iyadnekka/x-addgraph Paper organization. Section 2 reviews AddGraph’s architecture and formulates the explainability problem. Section 3 positions our work within the explainability literature. Section 4 presents the DSTA mechanism and the X-AddGraph algorithm. Section 5 describes the evaluation protocol, and Section 6 reports quantitative and qualitative results. Section 7 discusses implications for trustworthy information systems, generalization, and limitations. Section 8 concludes. 2 Background: The AddGraph Architecture 2.1 Problem Formulation A dynamic graph is a sequence of snapshots =Gtt=1TG=\G^t\_t=1^T with Gt=(V,Et)G^t=(V,E^t), where each edge e=(i,j,w)∈Ete=(i,j,w)∈ E^t connects nodes i and j with weight w at time t. The detector computes an anomaly score f⁡(e)∈[0,1]f(e)∈[0,1] for every edge; edges whose score exceeds a threshold τ are flagged. The explainability problem we address is: given a flagged edge, produce a faithful, human-readable account of which structural and temporal factors produced its score, without modifying the detector. 2.2 Three Coupled Components AddGraph maintains a hidden state matrix Ht∈ℝn×dH^t ^n× d across snapshots. At each time t, three operations update it. Structural encoding. A graph attention network takes the previous hidden state Ht−1H^t-1 and the current adjacency AtA^t and produces the structural summary t=GAT⁡(Ht−1,At)Current^t=GAT(H^t-1,A^t). 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 ω, for each node i the contextual attention block computes ait=softmax⁡(r⊤tanh⁡(Q[hit−ω;…;hit−1]⊤))∈ℝω,a^t_i=softmax\! (r \! (Q\,[h_i^t-ω;…;h_i^t-1] ) ) ^ω, (1) and the short-term summary ℎit=∑s=1ωait[s]hit−ω+s−1Short^t_i= _s=1^ωa^t_i[s]\,h_i^t-ω+s-1. The attention vector aita^t_i is computed during the standard forward pass and constitutes a normalized, model-endogenous importance distribution over the window—a fact our method exploits directly. Long-term integration (GRU). A GRU fuses tCurrent^t and ℎtShort^t through update and reset gates into the new state HtH^t. History prior to the window is encoded implicitly in the recurrence. Scoring. For an edge (i,j,w)(i,j,w), f⁡(i,j,w)=w⋅σ⁡(β‖a⊙hit+b⊙hjt‖22−μ),f(i,j,w)=w·σ\! (β \|a h_i^t+b h_j^t \|_2^2-μ ), (2) where a,b,β,μa,b,β,μ are learned or fixed parameters and σ denotes the logistic function. Note that σ is applied exactly once, inside Eq. (2); all attribution procedures in this paper operate on this final squashed score. 3 Related Work Anomaly detection in dynamic graphs. AddGraph [1] established the GCN+GRU template. StrGNN [2] applies it at the enclosing-subgraph level; EvolveGCN [3] evolves the convolution weights themselves through a recurrent cell; TADDY [4] replaces the pipeline with a Transformer over sampled neighborhood tokens. Surveys confirm deep methods as the dominant paradigm for this task [5]. Post-hoc explainability for GNNs. GNNExplainer [6] learns soft masks over edges and features for static GNNs; PGExplainer [7] parameterizes the mask generator globally; GraphSVX [8] extends Shapley values to graph inputs; GRAM [9] computes gradient-weighted attention maps. All assume a static model and provide no mechanism for temporal attribution: applied to AddGraph, each would explain at most the structural component while silently ignoring the CAB and GRU contributions. Explainability for dynamic and temporal GNNs. Closest to our setting, DGExplainer [10] derives layer-wise relevance propagation rules for GCN→ pipelines and empirically outperforms GNNExplainer, PGExplainer, SubgraphX, T-GNNExplainer [11], and DyExplainer [12]. However, DGExplainer’s propagation rules assume a direct GCN→ composition with no intermediate attention: AddGraph’s CAB module breaks this assumption, and DGExplainer provides no rule for a softmax attention layer interposed between convolution and recurrence. DyExplainer [12] takes the intrinsic route, training a self-explainable backbone with sparse attentions—an approach that requires retraining and therefore cannot preserve a deployed detector’s behavior. Recent work has also begun addressing heterogeneous settings: Han et al. [13] explain anomalies in dynamic heterogeneous graphs via relation evolution, underscoring the community’s growing consensus that detection without explanation is operationally insufficient. Our work fills the specific gap left open by this literature: an attribution framework whose components are aligned, one-to-one, with the coupled GAT–CAB–GRU architecture, requiring no retraining and no architectural modification. 4 X-AddGraph: Dual Spatial-Temporal Attribution 4.1 Design Principles Three principles follow directly from the architecture analysis. (P1) Strictly post-hoc. The framework operates on a frozen, trained AddGraph. No retraining, no weight modification, no change to the inference pipeline. Detection behavior is therefore preserved by construction. (P2) Architecture-aligned decomposition. A complete explanation must answer three orthogonal questions, one per architectural module. A method answering only one provides an incomplete and potentially misleading account. (P3) Exploit free signals. The CAB attention weights (Eq. 1) 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—strictly preferable to approximating the same quantity through an additional backward pass through the softmax. 4.2 Component 1: Spatial Attribution For a flagged edge (i∗,j∗)(i^*,j^*) at time t∗t^*, we attribute the score to entries of the adjacency by the input-weighted gradient ϕuvsp=|Auvt∗⋅∂f⁡(i∗,j∗,w∗)∂Auvt∗|,ϕusp=∑vϕuvsp+∑vϕvusp.φ^sp_uv\;=\; |\,A^t^*_uv· ∂ f(i^*,j^*,w^*)∂ A^t^*_uv |, φ^sp_u\;=\; _vφ^sp_uv+ _vφ^sp_vu. (3) This gradient×input form is the practical instantiation of relevance propagation for the ELU-activated convolutional layer, consistent with the rules derived in DGExplainer [10], 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. The top-k nodes by ϕuspφ^sp_u form the structural explanation ∗N^*. 4.3 Component 2: Short-Term Attribution (Zero-Cost) The short-term attribution for edge (i∗,j∗)(i^*,j^*) is the endpoint average of the CAB attention vectors, ϕssh=12(ai∗t∗[s]+aj∗t∗[s]),s=1,…,ω,φ^sh_s= 12 (a^t^*_i^*[s]+a^t^*_j^*[s] ), s=1,…,ω, (4) with the most suspicious window step s∗=arg⁡maxs⁡ϕsshs^*= _sφ^sh_s. Since the softmax in Eq. (1) guarantees ∑sait∗[s]=1 _sa^t^*_i[s]=1, the attribution is a valid probability distribution requiring no renormalization and no additional computation whatsoever. 4.4 Component 3: Long-Term Attribution History beyond the window is encoded in the recurrence. We attribute the score to each pre-window snapshot by the Frobenius norm of the gradient obtained through backpropagation through time, gk=∥∂f⁡(i∗,j∗,w∗)∂Ht∗−ω−k∥F,ϕlok=gk∑k′gk′,k=1,…,K,g^k= \| ∂ f(i^*,j^*,w^*)∂ H^\,t^*-ω-k \|_F, φ^lo_k= g^k _k g^k , k=1,…,K, (5) where K is the lookback horizon. The rollback naturally respects the GRU’s gating: snapshots whose influence was suppressed by the reset gate receive proportionally small gradient signal. The most influential historical snapshot is k∗=arg⁡maxk⁡ϕklok^*= _kφ^lo_k. 4.5 The DSTA Explanation Triplet Each flagged edge receives the triplet ℰ⁡(i∗,j∗)=(∗,t∗−ω+s∗,t∗−ω−k∗),E(i^*,j^*)= (N^*,\;t^*-ω+s^*,\;t^*-ω-k^* ), (6) read in natural language as: “the anomaly is driven primarily by connections to ∗N^*; the most suspicious recent behavior occurred at window step s∗s^*; the historical context most responsible originates k∗k^* snapshots before the window.” Algorithm 1 summarizes the procedure. Algorithm 1 X-AddGraph: DSTA explanation generation 1: frozen AddGraph; flagged edges ℱF at time t∗t^*; window ω; top-k; lookback K 2: DSTA triplet ℰ⁡(e)E(e) for each e∈ℱe 3: for each e∗=(i∗,j∗,w∗)∈ℱe^*=(i^*,j^*,w^*) do 4: Spatial: one backward pass of f w.r.t. At∗A^t^*; compute ϕspφ^sp via Eq. (3); ∗←N^*← top-k nodes 5: Short-term: read cached attention ai∗t∗,aj∗t∗a^t^*_i^*,a^t^*_j^*; compute ϕshφ^sh via Eq. (4); s∗←arg⁡maxs⁡ϕsshs^*← _sφ^sh_s ⊳ zero cost 6: Long-term: for k=1..Kk=1..K: one BPTT backward pass per lag; compute ϕloφ^lo via Eq. (5); k∗←arg⁡maxk⁡ϕklok^*← _kφ^lo_k 7: ℰ⁡(e∗)←(∗,t∗−ω+s∗,t∗−ω−k∗)E(e^*)←(N^*,\,t^*-ω+s^*,\,t^*-ω-k^*) 8: end for 9: return ℰ⁡(e∗)\E(e^*)\ 4.6 Computational Cost Per flagged edge, the framework requires one forward–backward pass for the spatial component, zero computation for the short-term component, and K backward passes for the long-term rollback. The overhead applies only to the small fraction of edges exceeding the detection threshold, and detection throughput itself is entirely unaffected. 5 Evaluation Protocol 5.1 Dataset and Detector Training We evaluate on UCI Message [14], a standard benchmark from the original AddGraph study: 1,899 nodes and 59,835 timestamped edges from an online student community. We follow the original protocol exactly: the first 50% of the edge stream forms the training graph; anomalous edges are injected into the remaining stream at 5%; snapshots contain 5,300 edges. We train the faithful reference implementation for 35 epochs with the original hyperparameters (hidden dimension 100, window ω=2ω=2, margin γ=0.6γ=0.6, four attention heads, selective negative sampling with hard-negative resampling). Training converges from a margin-loss plateau of 0.600 to 0.408. Our 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 [1] and thereby providing a strong, non-trivial detector to explain. 5.2 Broadened Edge Populations Explainability evaluations that consider only high-confidence true positives risk overstating performance on the easiest cases. We therefore evaluate across four edge populations, ten edges each: (i) confident true positives (highest-scored injected anomalies), (i) low-confidence true positives (correctly flagged but near-threshold), (i) false positives (normal edges the detector scored highest), and (iv) a uniformly random sample. All experiments are repeated over two random seeds, and we report mean ± standard deviation. Each edge is explained using the exact hidden state, adjacency, and history that produced its detection score. 5.3 Metrics and Baseline We report Fidelity+ (does the top-k structural explanation alone reproduce the score?), Sparsity (how concentrated is the explanation relative to the full neighborhood?), and per-explanation runtime. As a comparison method we implement 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 when applied to this architecture. To isolate the contribution of the temporal components—which a spatially-blind method cannot produce at all—we introduce a temporal fidelity test: for each explained edge, we compare the counterfactual effect of the identified window step / historical snapshot against that of a randomly selected one. Random selection is the honest stand-in for a method with no temporal mechanism. For the short-term test we replace the identified step with the mean of the remaining window states and measure the score change; for the long-term test we measure the divergence between the counterfactual score at the identified lag and at a random lag. 6 Results 6.1 Detection Preservation: The Post-Hoc Guarantee Table 1 reports the central result. 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 =0.0000000000. Where AddGraph offers no explanation capability of any kind (N/A), X-AddGraph provides the full DSTA triplet at zero detection cost. The AUC of the explainer-side run (0.8491) differs slightly from the training-side evaluation (0.8705) only because the stochastic anomaly-injection procedure is re-seeded when the test stream is rebuilt; the underlying detector and all its scores are bit-identical, as the Δ verification confirms. Table 1: Detection and explainability: AddGraph vs. X-AddGraph on UCI Message. X-AddGraph is strictly post-hoc; detection is preserved exactly. N/A indicates the capability does not exist in the base detector. Property AddGraph X-AddGraph Avg. per-snapshot AUC 0.8705 0.8705 Δ (verified) — 0.0000000000 Structural explanation N/A ✓ Short-term temporal explanation N/A ✓ Long-term temporal explanation N/A ✓ Fidelity+ (confident TPs) N/A 1.00 ± 0.00 Long-term attribution vs. random N/A 0.127 vs. 0.074 6.2 Structural Fidelity and Sparsity Across Populations Table 2 reports Fidelity+ and Sparsity across the four edge populations. The top-k structural explanation reproduces the anomaly score essentially perfectly on all true positives (Fidelity+=1.000±0.000^+=1.000± 0.000 to 1.001±0.0041.001± 0.004) and near-perfectly on false positives (0.997±0.0060.997± 0.006). Sparsity rises monotonically from confidently flagged anomalies (0.000) to random edges (0.750): edges that the detector confidently flags tend to involve structurally isolated endpoints whose entire local neighborhood is explanation-relevant, whereas explanations of ordinary edges concentrate on a small fraction of a larger neighborhood—itself an interpretable and operationally useful signal. One structural property of the base detector deserves explicit mention: because AddGraph’s convolution operates on one sparse snapshot at a time (mean within-snapshot degree 1.75), a top-5 explanation frequently covers the full local neighborhood, which is why structural fidelity saturates for both methods in Table 2. Fidelity values marginally above 1 on the random population indicate cases where the removed edges were actively suppressing the anomaly signal. Table 2: Structural fidelity and sparsity across four edge populations (mean ± std over 2 seeds, 10 edges per population). Population Fidelity+ (ours) Fidelity+ (flat grad.) Sparsity Confident TP 1.001 ± 0.004 1.001 ± 0.004 0.000 Low-conf. TP 1.000 ± 0.000 1.000 ± 0.000 0.133 False positives 0.997 ± 0.006 0.997 ± 0.006 0.133 Random 1.092 ± 0.280 1.092 ± 0.280 0.750 6.3 Temporal Fidelity: What Spatially-Blind Methods Cannot Do Table 3 reports the decisive comparison. 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. The long-term attribution is therefore not an incremental improvement over an existing baseline but a categorical addition to what can be explained. Table 3: Long-term temporal fidelity: counterfactual effect of the identified historical snapshot vs. a random selection (mean over seeds). Random selection represents the ceiling of any method lacking a temporal attribution mechanism. Long-term attribution Identified (ours) Random All populations (mean) 0.127 0.074 Confident TPs 0.332 0.125 6.4 Runtime A full DSTA explanation takes 10.1 s per flagged edge on a single T4 GPU (spatial pass, cached attention read, and K=5K=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. 6.5 Qualitative Walkthrough Explainability metrics alone do not convey operational value; we therefore walk through three genuinely flagged anomalies from the confident-TP population. Example 1. Edge (17, 1199), score 0.9911. The spatial component attributes the alarm to the endpoint pair itself 1199, 17, indicating an isolated, structurally unprecedented connection. The long-term component points to lag 4 (weight 0.475): the historical context four snapshots before the window contributed most to the memory state that rendered this edge anomalous. Example 2. Edge (490, 888), score 0.9544. Spatial drivers 888, 490, 34: a third node participates in the structural context. The long-term component identifies the immediately pre-window snapshot (lag 1, weight 0.473). Example 3. 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. In each case the analyst receives, alongside the score, a ranked neighbor list and a concrete temporal locus—exactly the information required to triage, audit, or dismiss the alarm. 7 Discussion 7.1 Implications for Trustworthy Cooperative Systems Anomaly detectors are increasingly embedded in cooperative information systems where their outputs trigger consequential actions: freezing transactions, revoking credentials, escalating incidents. Regulatory frameworks increasingly require that such automated decisions be explainable to auditors and affected parties. X-AddGraph demonstrates that this requirement need not force a trade-off against detection quality: because the framework is strictly post-hoc, organizations can retrofit explainability onto already-deployed, already-validated detectors with zero behavioral risk—the deployed model’s every decision remains bit-identical. This deployment property is, in our view, as important as the attribution quality itself for adoption in production information systems. 7.2 Generalization Beyond AddGraph DSTA’s design principle—align each attribution component with one architectural module—extends by construction to the GCN+GRU family AddGraph founded. StrGNN [2] shares the same backbone at the subgraph level and is directly compatible with the spatial and long-term components; EvolveGCN [3] admits the same gradient rollback through its recurrent weight evolution. The short-term component transfers to any architecture exposing an internal attention distribution, which is an increasingly common design pattern. 7.3 Limitations We note our limitations transparently. First, the discriminative power of the short-term component is inherently bounded by AddGraph’s original window size ω=2ω=2, under which the attention distribution has a single degree of freedom and remains close to uniform in the trained model; a systematic study across larger window sizes is planned for the final version of this work. Second, the present evaluation covers one benchmark; extending to Digg and to heterogeneous settings is planned, and we deliberately prioritized depth of protocol (four edge populations, seed variance, counterfactual temporal tests) over dataset breadth. Third, 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 and which we view as an important direction for the community. 8 Conclusion We presented X-AddGraph, to our knowledge the first post-hoc explainability framework for AddGraph and for the GCN+GRU paradigm of dynamic graph anomaly detection. Its Dual Spatial-Temporal Attribution mechanism aligns three attribution components with the detector’s three architectural modules, exploits the model’s own attention weights as a zero-cost short-term signal, and preserves detection performance exactly—ΔAUC=0 =0, verified to ten decimal places on a detector whose 0.8705 average AUC exceeds the originally published result. Across four edge populations, the long-term attribution identifies historical snapshots carrying 73% more counterfactual signal than random selection, a capability that is categorically unavailable to spatially-blind explainers. 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. Acknowledgements. In accordance with the conference’s policy on generative AI, we disclose that the AI assistant Claude (Anthropic) was used to assist with language editing of the manuscript and engineering of experimental scaffolding code; all scientific ideas, the methodology, the experiments, and the validation of all results are the authors’ own, who take full responsibility for the entire content. References [1] Zheng, L., Li, Z., Li, J., Li, Z., Gao, J.: AddGraph: Anomaly detection in dynamic graph using attention-based temporal GCN. In: Proc. 28th International Joint Conference on Artificial Intelligence (IJCAI), p. 4419–4425 (2019) [2] Cai, L., Chen, Z., Luo, C., Gui, J., Ni, J., Li, D., Chen, H.: Structural temporal graph neural networks for anomaly detection in dynamic graphs. In: Proc. 30th ACM International Conference on Information and Knowledge Management (CIKM), p. 3747–3756 (2021) [3] Pareja, A., Domeniconi, G., Chen, J., Ma, T., Suzumura, T., Kanezashi, H., Kaler, T., Schardl, T.B., Leiserson, C.E.: EvolveGCN: Evolving graph convolutional networks for dynamic graphs. In: Proc. 34th AAAI Conference on Artificial Intelligence, p. 5363–5370 (2020) [4] Liu, Y., Pan, S., Wang, Y.G., Xiong, F., Wang, L., Chen, Q., Lee, V.C.S.: Anomaly detection in dynamic graphs via transformer. IEEE Transactions on Knowledge and Data Engineering 35(12), 12081–12094 (2023) [5] Ekle, O.A., Eberle, W.: Anomaly detection in dynamic graphs: A comprehensive survey. ACM Transactions on Knowledge Discovery from Data 18(8), 1–44 (2024) [6] Ying, Z., Bourgeois, D., You, J., Zitnik, M., Leskovec, J.: GNNExplainer: Generating explanations for graph neural networks. In: Advances in Neural Information Processing Systems 32 (NeurIPS) (2019) [7] Luo, D., Cheng, W., Xu, D., Yu, W., Zong, B., Chen, H., Zhang, X.: Parameterized explainer for graph neural network. In: Advances in Neural Information Processing Systems 33 (NeurIPS) (2020) [8] Duval, A., Malliaros, F.D.: GraphSVX: Shapley value explanations for graph neural networks. In: Proc. European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD), p. 302–318 (2021) [9] Pope, P.E., Kolouri, S., Rostami, M., Martin, C.E., Hoffmann, H.: Explainability methods for graph convolutional neural networks. In: Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 10772–10781 (2019) [10] Xie, J., Liu, Y., Shen, Y.: Explaining dynamic graph neural networks via relevance back-propagation. In: Proc. 34th International Joint Conference on Artificial Intelligence (IJCAI) (2025) [11] Xia, W., Lai, M., Shan, C., Zhang, Y., Dai, X., Li, X., Li, D.: Explaining temporal graph models through an explorer-navigator framework. In: Proc. 11th International Conference on Learning Representations (ICLR) (2023) [12] Wang, T., Lin, X., Liu, S., et al.: DyExplainer: Explainable dynamic graph neural networks with sparse attentions. arXiv preprint arXiv:2310.16375 (2023) [13] Han, X., Hu, X., Ma, C., Shang, X.: Explainable anomaly detection in dynamic heterogeneous graphs via relation evolution. IEEE Transactions on Knowledge and Data Engineering (2026) [14] Opsahl, T., Panzarasa, P.: Clustering in weighted networks. Social Networks 31(2), 155–163 (2009)

Instant research discovery