PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.15559v1cs.LGcs.AI

TL;DR

StrGNN flags anomalous edges without attribution vectors, leaving explanation quality undefined. X-StrGNN adds structural and temporal post-hoc attributions while preserving detection, achieving 0.913 stability at 268× lower cost than per-instance optimisation and making full alarm-list explanation operationally feasible.

  • Problem

    StrGNN lacks attribution vectors, leaving explanation-quality metrics undefined for its flagged edges.

  • Method

    X-StrGNN wraps a frozen StrGNN with amortised structural and temporal masks whose unexplained pass exactly preserves the original computation.

  • Results

    0.913 stability is achieved at 268× lower cost than per-instance optimisation, while detection changes by ΔAUC = 0.0000.

  • Takeaways & Limitations

    Amortisation makes explanation of a full alarm list operationally feasible, while per-instance optimisation remains useful when latency is irrelevant.

  • Takeaways & Limitations

    Evaluation uses a single detector and corpus, and transfer to other detectors is expected but not demonstrated.

Abstract

from arXiv · show

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.

I. INTRODUCTION · II. RELATED WORK

Dynamic graph anomaly detection is practically urgent but technically demanding, while StrGNN captures structural and temporal dependencies without explaining its alerts. X-StrGNN addresses this gap with post-hoc dual attribution, exact detection preservation, amortised efficiency, controlled strategy comparison, and implementation auditing.

  • I. INTRODUCTION: Evolving financial, enterprise, trust, and social networks create urgent anomaly-detection challenges involving fraud, lateral movement, and coordinated inauthentic activity.
  • II. RELATED WORK: StrGNN scores edges using h-hop enclosing subgraphs across w consecutive snapshots, graph convolutions, SortPooling, and a gated recurrent unit.
  • I. INTRODUCTION: StrGNN emits only a scalar for flagged edges, identifying neither the evidential contextual interactions nor whether the anomaly emerged currently or accumulated historically.
  • I. INTRODUCTION: The paper introduces the first post-hoc StrGNN explanation layer because explanation metrics are undefined without an attribution vector.
  • I. INTRODUCTION: ∆AUC = 0.0000, while the layer provides dual structural and temporal attributions for every flagged edge over a frozen detector.
  • I. INTRODUCTION: 0.66 ms per edge, with an amortised spatio-temporal network emitting structural masks and observation-window gates under separate counterfactual objectives.
  • I. INTRODUCTION: The study compares four attribution strategies against a measured random floor under one protocol, one budget, and three seeds, producing deployment guidance.
  • I. INTRODUCTION: The implementation audit reports five defects affecting published numbers, including a tensor-axis error that breaks correspondence between recurrent steps and snapshots.

A. Anomaly Detection in Dynamic Graphs … III. PRELIMINARIES

The paper situates X-StrGNN among dynamic-graph anomaly detectors and graph explanation methods, then formalizes dynamic graphs, edge-level anomaly scoring, and the exact pass-through explainer architecture. It addresses the missing temporal attribution axis for StrGNN’s enclosing-subgraph-plus-recurrence design.

  • A. Anomaly Detection in Dynamic Graphs: Deep dynamic-graph detectors improved detection through random-walk, GCN-recurrent, enclosing-subgraph, Transformer, and related structural-temporal architectures.NetWalk combines random-walk embeddings with a reservoir; AddGraph pairs a GCN with an attention-augmented GRU; StrGNN uses enclosing-subgraph extraction and double-radius labelling; TADDY uses a Transformer encoder.
  • B. Post-Hoc Explanation for Graph Neural Networks: GNNExplainer optimises per-instance edge masks, PGExplainer amortises this optimisation across instances, and gradient attribution requires no training.These methods were designed for static graphs and lack an axis expressing when a decision was made.
  • C. Explanation for Temporal Models: TGNNExplainer and TempME explain continuous-time temporal GNNs, while relation-evolution methods address dynamic heterogeneous graphs with different input models.These settings differ from the discrete-snapshot window consumed by StrGNN.
  • C. Explanation for Temporal Models: No prior work supplies attribution for the enclosing-subgraph-plus-recurrence architecture targeted here.This gap distinguishes the paper’s explanation setting from prior continuous-time and heterogeneous-graph approaches.
  • III. PRELIMINARIES: A dynamic graph is a sequence G = {G1, . . . , GT } whose snapshots share node set V while their edge sets Et vary over time.This is the paper’s formal definition of dynamic graphs.
  • III. PRELIMINARIES: An edge-level anomaly scorer f : (e, t) 7→[0, 1] assigns each candidate edge at snapshot t a score, flagging edges above a threshold.The definition operates on candidate edge e = (u, v) and snapshot t.
  • III. PRELIMINARIES: The frozen detector is wrapped by a shared explainer that emits structural and temporal multiplicative masks, both identically one in the unexplained pass.The structural mask covers enclosing-subgraph messages, the temporal gate covers the w recurrent inputs, and the composition therefore reduces exactly to StrGNN.

A. StrGNN · IV. THE X-STRGNN FRAMEWORK · A. Design Principles

StrGNN explains dynamic-edge decisions through contextual interactions observed across a sequence of graph snapshots. X-StrGNN therefore wraps the frozen detector with separate structural and temporal attribution axes.

  • A. StrGNN: For target edge (u, v) at snapshot t, StrGNN extracts h-hop enclosing subgraphs across snapshots t − w + 1 through t.The target edge is removed from its own subgraph during evidence construction.
  • A. StrGNN: Double-radius node labels encode each node’s role relative to the target endpoints u and v.
  • A. StrGNN: StrGNN’s structural feature extraction applies a graph convolutional stack and SortPooling to each snapshot’s enclosing-subgraph representation.
  • A. StrGNN: The evidence consists of contextual interactions rather than the target edge itself.
  • IV. THE X-STRGNN FRAMEWORK: Because the detector operates on a sequence, faithful explanation requires a temporal degree of freedom that static attribution cannot express.
  • A. Design Principles: X-StrGNN uses post-hoc, zero-modification wrapping around a trained, frozen detector, leaving weights, training, and inference untouched.The framework separates attribution into structural and temporal axes: which contextual interactions and which snapshots matter.

B. Masked Forward Pass · C. Amortised Parameterisation

X-StrGNN uses multiplicative structural and temporal masks while preserving the frozen detector exactly when both masks equal one. A shared amortised network predicts these masks from detector representations using binary concrete relaxation, with separate structural and temporal heads.

  • B. Masked Forward Pass: Structural masks m_e ∈[0, 1] multiply messages carried by undirected enclosing-subgraph edges.The masks are applied within the detector’s masked message aggregation.
  • B. Masked Forward Pass: Temporal masks g_t ∈[0, 1] multiply recurrent inputs at each of the w historical steps.At step t, the recurrent input becomes g_t · s_t.
  • B. Masked Forward Pass: Exact pass-through holds: fϕ(G | m ≡1, g ≡1) = fϕ(G) identically.Both masks enter multiplicatively, and degree normalisation is computed on the unmasked graph.
  • B. Masked Forward Pass: The unexplained pass is a structural guarantee, because mask-independent normalisation reduces the computation term-by-term to the original detector.This is not merely an empirical near-match.
  • C. Amortised Parameterisation: A single shared network ψ predicts structural mask logits for every instance from the detector’s graph-convolutional representations.The parameterisation follows PGExplainer and incorporates learned positional embeddings.
  • C. Amortised Parameterisation: Structural masks use the binary concrete relaxation m = σ((ω + log u −log(1 −u))/τ), with u ∼U(0, 1) and τ annealed from 5.0 to 0.5.A bound B prevents the relaxation from saturating to a constant.
  • C. Amortised Parameterisation: A separate temporal head predicts snapshot-mask logits from snapshot representations and window context using its own positional embedding ρτ.The structural and temporal heads share no parameters.

D. Objective

The objective defines attribution from the frozen StrGNN’s own prediction, producing structural evidence per edge and temporal evidence over historical snapshots.

  • Objective: The detector’s own prediction is defined as ŷ = arg max fϕ(G).
  • Objective: The attribution algorithm computes structural and temporal masks from internal edge and snapshot representations in one forward pass.
  • Objective: The method returns top-p structural evidence and the snapshot with maximum temporal attribution.

E. Explanation Quality Metrics · V. EXPERIMENTS · A. Setup 

The paper defines explanation metrics for attribution-based evaluation and establishes a corrected, controlled experimental setup for X-StrGNN. StrGNN itself has no attribution vector, while the explanation layer leaves detection unchanged when inactive.

  • E. Explanation Quality Metrics: StrGNN’s explanation metrics are undefined because the detector produces no attribution vector, rather than receiving zero or low scores.
  • E. Explanation Quality Metrics: Raw fidelity is normalised by the ablation range ∆max to reduce dependence on detector confidence and checkpoint-specific probability scales.
  • E. Explanation Quality Metrics: 1 is the measured random floor for temporal fidelity, which compares nominated-snapshot ablation against uniformly chosen-snapshot ablation.
  • A. Setup : The objective enforces sufficiency and separate structural and temporal necessity, while R promotes density, low mask entropy, and temporal smoothness.
  • A. Setup : Temporal attribution training makes snapshots compete because their weights sum to one, so increasing one snapshot decreases the others.
  • A. Setup : Five released-StrGNN implementation defects were patched before measurement, including a channel-major reshape that incorrectly interleaved channels into the temporal axis.The correction is load-bearing for temporal claims; without it, temporal attribution is evaluated against a scrambled axis.
  • A. Setup : Detection is unchanged when the explanation layer is inactive at m = g = 1, with the raw-score residual limited to float32 epsilon.

B. Detection Is Preserved Exactly

X-StrGNN preserves detection exactly: every detection metric is bit-identical, with explainability added at zero detection cost. The largest per-edge deviation is only float32 epsilon from the exponential.

  • Exact preservation: Bit-identical detection metrics confirm exact preservation across every reported detection measure.Table II numerically confirms Proposition 1.
  • Exact preservation: 0 detection cost is incurred when adding explainability to the frozen detector.The explanation layer preserves the detection model used in subsequent measurements.
  • Exact preservation: float32 epsilon is the largest per-edge deviation, arising in the exponential.This deviation is attributed to floating-point computation rather than a detection change.

C. Explainability Introduced · D. Design Study: Which Attribution Strategy Suits StrGNN?

X-StrGNN introduces the first attribution layer for StrGNN, making previously undefined explanation metrics evaluable while preserving operationally feasible analysis. A controlled four-strategy study finds that amortisation offers the strongest stability-cost trade-off, whereas per-instance optimisation retains a fidelity advantage for latency-insensitive cases.

  • C. Explainability Introduced: No attribution vector previously existed for StrGNN, making every explanation metric undefined; X-StrGNN supplies structural and temporal attributions.The attributions are multiplicative masks that preserve the detector’s unexplained pass exactly.
  • C. Explainability Introduced: 1.601 temporal fidelity exceeds the measured random floor of 0.973, indicating that the selected snapshot carries roughly 1.6× an arbitrary snapshot’s decision weight.Attribution costs 0.66 ms per edge, so explaining 1,653 test edges takes approximately one second.
  • D. Design Study: Which Attribution Strategy Suits StrGNN?: Four attribution strategies are implemented and compared under one protocol, one budget, and three seeds because no prior strategy existed for this architecture.The comparison is framed as a design study rather than a leaderboard against prior art.
  • D. Design Study: Which Attribution Strategy Suits StrGNN?: 0.913±0.010 stability for X-StrGNN exceeds 0.538 for per-instance optimisation at 268× lower cost.The study links higher stability to explanations that remain consistent under imperceptible input perturbations.
  • D. Design Study: Which Attribution Strategy Suits StrGNN?: N/A denotes undefined evaluation because StrGNN has no attribution vector; Fid+/Fid− are normalised by the detector ablation range of 0.326.Table III reports means over three seeds.
  • D. Design Study: Which Attribution Strategy Suits StrGNN?: 0.383 characterisation for per-instance optimisation exceeds 0.286 for X-StrGNN, establishing a fidelity advantage for per-instance explanations.This strategy is appropriate when a small number of adjudicated cases require maximal faithfulness and latency is irrelevant.
  • D. Design Study: Which Attribution Strategy Suits StrGNN?: 178 ms per edge makes per-instance optimisation prohibitive for explaining an entire alarm list at analyst-facing latency.Amortised attribution is instead suited to deployment requiring explanations across many flagged edges.

E. Design Notes

The design study identifies separate positional embeddings and density matching as load-bearing implementation choices for reproducible structural and temporal explanations. Separate tables prevent objective interference, while a squared density-matching penalty aligns training with the hard top-p evaluation budget.

  • Implementation choices: Separate positional tables keep structural and temporal gradient paths disjoint, allowing each explanation axis to respond independently to its own hyperparameters.A shared table makes the objectives compete for one parameter and can falsely suggest an intrinsic trade-off between structural and temporal explanation.
  • Implementation choices: A weak L1 penalty leaves the soft mask near density 0.5, despite evaluation after a hard top-p cut.This mismatch means the ranking is learned in a regime the metric never tests.
  • Implementation choices: Penalising (m̄ − p)^2 aligns training density with the evaluation budget and materially improves characterisation.The explainer is evaluated after a hard top-p cut, motivating density matching rather than L1.

F. Sanity Check … B. Why Dual Decomposition Is the Contribution

X-StrGNN’s post-hoc, dual attribution design preserves the frozen detector while separating structural and temporal explanations. The sanity check shows that explainer-family differences affect how model randomisation should be interpreted.

  • F. Sanity Check: ρ(trained, re-initialised) = 0.272 ± 0.061 indicates residual correlation in the model-randomisation test.For an amortised explainer, the shared network retains trained weights and continues emitting a structured ranking after detector randomisation.
  • F. Sanity Check: Per-instance methods instead optimise directly against the randomised detector and collapse in this sanity check.The test therefore has different meanings across explainer families and should be interpreted within family.
  • A. Why Post-Hoc Is the Correct Design: ΔAUC = 0.0000 demonstrates that X-StrGNN wraps existing trained checkpoints without detection degradation.Post-hoc explanation is positioned as a deployment-compatible alternative to retraining intrinsic self-explaining detectors.
  • VI. DISCUSSION: Post-hoc separation prevents joint detection-and-explanation optimisation from conflating competing objectives.The design allows detection and explanation to improve independently.
  • B. Why Dual Decomposition Is the Contribution: A single edge-attribution vector cannot distinguish whether an alert reflects a suspicious counterparty or an interaction-history pattern.This motivates decomposing explanations into structural and temporal axes.
  • B. Why Dual Decomposition Is the Contribution: Below the random floor, the most computationally expensive strategy shows that temporal fidelity cannot be inferred from structural attribution alone.Structural faithfulness does not certify temporal attribution and may certify the opposite.

C. Operational Implications · D. Limitations · VII. CONCLUSION

X-StrGNN makes StrGNN explanations operationally feasible by providing stable structural and temporal attributions with zero detection cost. The study also highlights seed variance as a reporting limitation and releases an auditable framework for broader dynamic-graph anomaly detectors.

  • C. Operational Implications: 0.66 ms per edge makes explaining an entire alarm window a sub-second operation, enabling explanations for every alert at triage time.Combined with stability 0.913, the explanation of a given alert remains consistent across time.
  • C. Operational Implications: 0.913 stability supports operational trust by making an alert’s explanation consistent tomorrow as well as today.The passage identifies this consistency as a precondition for operational trust beyond fidelity alone.
  • D. Limitations: ±0.078 and ±0.016 seed-to-seed dispersion for learned strategies exceed ±0.001 for parameter-free strategies.Results are therefore reported as mean ± standard deviation over three seeds, with differences below 2σ treated as ties.
  • VII. CONCLUSION: X-StrGNN supplies structural and temporal attributions for every flagged edge at 0.66 ms per explanation, with ∆AUC = 0.0000 detection cost.Before this work, fidelity, characterisation, and temporal attribution were undefined for StrGNN because no attribution vector existed.
  • VII. CONCLUSION: 0.913 attribution stability and 268× lower cost make amortisation suited to full alarm lists, while per-instance optimisation retains a fidelity advantage when latency is irrelevant.The temporal counterfactual objective converts a windowed detector’s observation history into an interpretable axis.
  • VII. CONCLUSION: The framework addresses a gap extending beyond StrGNN by offering a post-hoc template for essentially every deep dynamic-graph anomaly detector.The authors release the protocol, runners, and per-seed measurements for direct application and auditing.
Loading 2608.15559v1…