Amortised Post-Hoc Explanation with Exact Preservation for Dynamic Graph Anomaly Detectors

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

cs.LGAug 16, 2026

Amortised Post-Hoc Explanation with Exact Preservation for Dynamic Graph Anomaly Detectors

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

Organizations: LCSI Laboratory, National higher School of Computer Science (ESI), Algiers, Algeria · Université Claude Bernard Lyon, Lyon, France

Abstract

Anomaly detection in dynamic graphs underpins financial fraud analysis, intrusion detection, and platform integrity, where automated decisions require human-interpretable justifications. StrGNN, the strongest performer in recent benchmarks, produces no explanation: when an edge is flagged, the analyst receives only a score. Explanation metrics are undefined for StrGNN because no attribution vector exists. This paper closes that gap. We present X-StrGNN, a post-hoc explanation layer that wraps a trained, frozen StrGNN and emits, for every flagged edge, dual attributions: a structural attribution identifying which contextual interactions in the enclosing subgraph drove the decision, and a temporal attribution identifying which historical snapshot carried the signal. Both attributions are multiplicative masks identically one in the unexplained pass, so the layer is an exact pass-through: detection is preserved to machine precision, verified rather than asserted (Delta AUC = 0.0000, Delta AP = 0.0000, Delta P@100 = 0.0000). Attribution costs 0.66 ms per edge, making explanation of an entire alarm list feasible. We conduct the first controlled design study of attribution strategies for this architecture, comparing gradient attribution, per-instance mask optimisation, and amortised parameterisation under one protocol, one budget, and three seeds. X-StrGNN attains the highest stability (0.913) at 268x lower cost than per-instance optimisation, and its temporal attribution (1.601 against a measured random floor of 0.973) is separably better than its ablated control, while per-instance optimisation - the most expensive strategy - falls below that floor. Code, protocol, and per-seed measurements are released.

Figures & tables

Panel of Figure 1 — Fig. 1: X-StrGNN. The detector (grey) is frozen; a shared explainer network (blue) emits a structural mask over enclosing-subgraph messages and a gate over the $w$ recurrent inputs, conditioned on the detector’s own internal representations. Both masks are multiplicative and identically one in the unexplained pass, so the composition reduces exactly to StrGNN.

ID	Defect
P1	Evaluation reports AP and F1 on the normal class
P2	Target link retained in its own enclosing subgraph (leakage)
P3	Training and test use different temporal windows
P4	GRU input reshaped, not transposed: step $t\neq$ snapshot $t$
P5	Device handling hardcoded to CUDA

TABLE I: Defects found in the released StrGNN implementation, all patched before measurement. P4 is load-bearing for any temporal claim.

Metric	StrGNN	X-StrGNN	$\Delta$
AUC-ROC	0.8749834853	0.8749834853	0.0000
AP	0.5163393989	0.5163393989	0.0000
P@100	0.6600000000	0.6600000000	0.0000
max $\|\Delta s\|$ over all test edges			$1.19\mathrm{e}{-}07$

TABLE II: Detection parity. The explanation layer is inactive at

m\!=\!g\!=\!1

, so detection is unchanged; the residual on raw scores is float32 epsilon.

Capability / Metric	StrGNN	X-StrGNN	Status
Structural attribution	n/a	✓	Introduced
Temporal attribution	n/a	✓	Introduced
Fidelity $\mathrm{Fid}^{+}$	n/a	0.317	Introduced
Characterisation	n/a	0.286	Introduced
Temporal fidelity	n/a	1.601	Introduced
Attribution stability	n/a	0.913	Introduced

TABLE III: Capabilities introduced. n/a denotes undefined : no attribution vector exists for StrGNN, so evaluation is not possible. Mean over three seeds;

\mathrm{Fid}^{+}

\mathrm{Fid}^{-}

normalised by the detector ablation range (

0.326

Attribution strategy	$\mathrm{Fid}^{+}\uparrow$	$\mathrm{Fid}^{-}\downarrow$	$\mathrm{Char}\uparrow$	Temporal $\uparrow$	Stability $\uparrow$	ms/expl $\downarrow$
Random (measured floor)	$0.228\!\pm\!0.003$	$0.820\!\pm\!0.002$	$0.201\!\pm\!0.001$	$0.973\!\pm\!0.050$	$0.002\!\pm\!0.004$	$0.00$
Gradient $\times$ input	$0.336\!\pm\!0.001$	$0.656\!\pm\!0.000$	$0.340\!\pm\!0.000$	$\mathbf{1.842\!\pm\!0.034}$	$0.405\!\pm\!0.002$	$1.79\!\pm\!0.12$
Per-instance mask optimisation	$\mathbf{0.337\!\pm\!0.001}$	$\mathbf{0.556\!\pm\!0.002}$	$\mathbf{0.383\!\pm\!0.000}$	$0.836\!\pm\!0.032$	$0.538\!\pm\!0.002$	$177.97\!\pm\!2.15$
Amortised, sufficiency only (ablation)	$0.221\!\pm\!0.005$	$0.800\!\pm\!0.026$	$0.209\!\pm\!0.016$	$1.081\!\pm\!0.427$	$0.863\!\pm\!0.005$	$\mathbf{0.63\!\pm\!0.02}$
X-StrGNN (full objective)	$0.317\!\pm\!0.068$	$0.739\!\pm\!0.084$	$0.286\!\pm\!0.078$	$1.601\!\pm\!0.364$	$\mathbf{0.913\!\pm\!0.010}$	$0.66\!\pm\!0.02$

TABLE IV: Design study: attribution strategies for StrGNN, all introduced in this work. UCI-Messages, three seeds (mean

\pm

sd), frozen detector,

20\%

budget.

\mathrm{Fid}^{+}

\mathrm{Fid}^{-}

normalised by the ablation range (

0.326

); temporal fidelity of

1

is the measured random floor. Best per column in bold.

GNN Explainability

Graph neural network explainability studies how to identify and communicate the features, nodes, edges, and subgraphs behind graph-model predictions.

See all 80 papers

Dual Spatial-Temporal Attribution: Architecture-Aligned Post-Hoc Explainability for Recurrent Graph Anomaly Detection
Aug 12, 2026Iyad Assaad Nekka, Hamida Seba, Khaled Walid Hidouci +1Gradient-Based Attribution Interpretable Anomaly Detection
LCSI Laboratory, National Higher School of Computer Science (ESI), Algiers, Algeria · Université Claude Bernard Lyon 1, Lyon, France
Declarative Explanations for Graph Neural Networks: A Demonstration
Oct 19, 2026Cibo Yu, Haitong Tang, Yinghui Wu +4GNN Explainability Graph Neural Networks
Zhejiang University, Hangzhou, China · Case Western Reserve University, Cleveland, USA · Bowling Green State University, Bowling Green, USA
Hierarchical Attention-based Graph Neural Network with Relevance-driven Pruning
May 10, 2026Seungwoo KumGraph Attention Networks Heterogeneous GNNs
Korea Electronics Technology Institute (KETI) Seongnam, Republic of Korea

Aug 12, 2026J/K move · Enter open · S save

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

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

LCSI Laboratory, National Higher School of Computer Science (ESI), Algiers, Algeria · Université Claude Bernard Lyon 1, Lyon, France

Gradient-Based Attribution Interpretable Anomaly Detection GNN Explainability Anomaly Detection Graph-Based Anomaly Detection

Open paper AskPDF 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.

Abstract

GNN Explainability

Explore similar work

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

Declarative Explanations for Graph Neural Networks: A Demonstration

Hierarchical Attention-based Graph Neural Network with Relevance-driven Pruning