💻 computer science

Exact Deviation Attribution and Amortised Event Explanation for Semi-Supervised Anomaly Detection on Dynamic Graphs

This paper introduces a framework for semi-supervised anomaly detection on dynamic graphs that provides exact, closed-form deviation attribution and learns an amortised event mask to explain decisions with zero impact on detection performance, while revealing that alerts often stem equally from individual node behavior and population baseline shifts.

Original authors: Iyad Assaad NEKKA, Walid Khaled Hidouci, Karima Amrouche

Published 2026-08-25

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Iyad Assaad NEKKA, Walid Khaled Hidouci, Karima Amrouche

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital world, networks are not static maps but living, breathing streams of activity. Every message sent, every transaction made, and every connection formed happens in real time, creating a dynamic graph that constantly shifts and evolves. For decades, computer scientists have built systems to watch these networks, looking for the rare, dangerous moments when something goes wrong—a fraudster making a suspicious transfer, a hacker probing a server, or a bot spreading misinformation. These systems, known as anomaly detectors, are excellent at spotting the unusual. They can calculate a score that says, "This looks wrong," with high accuracy. But for a long time, they could not say why. They offered a warning without a reason, leaving human operators to guess what triggered the alarm. In high-stakes fields like finance or cybersecurity, a warning without an explanation is often useless; you need to know which past action caused the alert to decide whether to block a user or ignore a false alarm.

The challenge is particularly difficult when the network is continuous. Unlike a photograph that captures a single moment, a dynamic graph is a video stream of events. Traditional methods often chop this stream into snapshots, losing the nuance of how interactions unfold over time. A newer type of detector, called SAD, was designed to handle this continuous flow. It works by keeping a memory of what "normal" looks like, updating this memory as time passes to account for seasonal changes or holidays. When a new event happens, the system compares it against this living memory. If the event deviates too far from the norm, it raises an alert. However, even this advanced system had a blind spot: it could tell you that a node was an outlier, but it could not break down the score to show you which specific past interactions caused the deviation, nor could it tell you if the alert was due to the node acting strangely or if the entire population's behavior had simply shifted.

A team of researchers has now filled this gap with a new framework called X-SAD. They did not build a new detector; instead, they built a way to look inside the existing one and understand its reasoning. Their work reveals that the system's decision-making process can be split into two distinct parts. The first part identifies the specific events in the past that led to the alert. Imagine a security guard who not only sounds an alarm but also points to the exact three people in the crowd whose movements triggered it. The researchers created a method that learns to highlight these critical past interactions, effectively creating a mask that shows which connections mattered most. Crucially, they achieved this without slowing down the system or changing its ability to detect threats. The detector remains just as accurate as before, but now it comes with a clear, instant explanation of its logic.

The second part of their discovery is even more profound because it does not rely on learning or guessing at all. Because the SAD detector works by comparing a node to a specific, calculated average of past behavior, the researchers found they could mathematically separate the alert into two components: the node's own behavior and the behavior of the group it belongs to. This is like knowing whether a student is failing because they are not studying, or because the entire class has suddenly become much harder. In their tests on a real-world dataset of online course interactions, they found that the alerts were split almost perfectly down the middle. Roughly half of the time, the alert was driven by the individual node acting strangely. The other half of the time, the alert was triggered because the baseline behavior of the entire population had shifted. This distinction is something no other system could offer, and it changes how a human analyst should respond to an alert. If the problem is the population, the solution might be to update the system's expectations; if it is the individual, the solution might be to block them.

To ensure their new explanation tool was reliable, the researchers ran rigorous tests comparing it against other methods. They found that their approach, which learns a shared pattern to explain many alerts at once, was vastly superior to methods that try to solve each alert from scratch. The shared method was not only more accurate but also hundreds of times faster, taking less than a tenth of a millisecond to generate an explanation. This speed means that explanations can be provided instantly, the moment an alert is raised, rather than being reserved for later forensic analysis. They also discovered that some common ways of measuring how good an explanation is were actually misleading. Standard methods often penalized explanations that correctly identified evidence that cleared a suspect, treating them as bad explanations simply because they lowered the suspicion score. The researchers corrected this by developing a new way to measure fidelity that respects the unique nature of anomaly detection, where proving innocence is just as important as proving guilt.

The study also uncovered a few hidden flaws in the original software code used for the detector, which the team fixed before running their final experiments. One of these flaws meant that a key feature of the detector was effectively turned off during testing, which would have skewed the results. By patching these issues, they ensured that the numbers they reported were true to the system's actual capabilities. Their final conclusion is that when a detector is built with a clear reference point, like a memory bank of normal behavior, it is possible to extract exact, mathematical reasons for its decisions without any guesswork. This approach offers a new standard for transparency in artificial intelligence, proving that complex, real-time systems can be both highly accurate and fully understandable. The result is a system that does not just shout "danger," but quietly and precisely explains the story behind the danger, allowing humans to make better, faster decisions in a world that never stops moving.

Technical Summary: Exact Deviation Attribution and Amortised Event Explanation for Semi-Supervised Anomaly Detection on Dynamic Graphs

Problem Statement

Semi-supervised anomaly detectors for dynamic graphs, such as SAD (Semi-supervised Anomaly Detection), are critical for domains like fraud analysis and intrusion detection. However, these models typically emit only a scalar anomaly score without providing a rationale for the decision. This lack of explainability is operationally insufficient.

Specifically, for SAD—a continuous-time detector that scores nodes based on their standardised deviation from a time-decayed reference distribution maintained in a memory bank—explanation quality metrics are currently undefined. Because no attribution vector exists for the detector's decision, standard evaluation methods (such as fidelity or characterisation) cannot be applied. Furthermore, existing post-hoc explainers for graph neural networks (e.g., GNNExplainer, PGExplainer) are designed for opaque scoring mechanisms and cannot analytically decompose a score derived from a comparison against an explicit reference distribution.

Methodology: The X-SAD Framework

The paper introduces X-SAD, a post-hoc explanation framework designed specifically for SAD. The framework operates on two distinct axes that differ in nature:

Axis A: Amortised Event Attribution
This axis addresses the question: Which past interactions in the temporal neighbourhood produced the decision?

Mechanism: Following the approach of PGExplainer, X-SAD employs a shared network to predict a soft mask over neighbourhood events. This mask enters the attention logits of the frozen SAD detector additively as $\log m_e$ .
Preservation of Detection: The design ensures that when the mask is unity ( $m \equiv 1$ ), $\log 1 = 0$ , leaving the softmax unchanged. This guarantees that the explanation mechanism is inactive when not needed, preserving the detector's performance to machine precision.
Optimization: The objective regresses the alert score under the mask against the original score, rather than a binary threshold, to avoid degenerate solutions where the explainer masks all evidence. A density penalty aligns the soft mask with a specific evaluation budget.

Axis B: Exact Deviation Decomposition
This axis addresses the question: Did the alert reflect the node's own behaviour or a shift in the population baseline?

Mechanism: Leveraging the specific architecture of SAD, where the anomaly score is a standardised deviation from a weighted mean of memory entries, the paper derives a closed-form decomposition of the deviation equation.
Formula: The total deviation $dev_i(t)$ is decomposed into an instance term (the node's own score) and a baseline term (the weighted sum of memory entries).
$dev_i(t) = \underbrace{\frac{s_i(t)}{\sigma_r(t)}}_{\text{instance}} - \underbrace{\sum_j \frac{w_j(t) r_j}{\sigma_r(t)}}_{\text{baseline}}$
Properties: This decomposition is exact, requires no sampling or surrogate models, has no hyperparameters, and carries no seed variance. It sums to the total by construction.

Evaluation Metrics and Defects
The authors also identified and patched four defects in the released SAD implementation (e.g., time-weighted statistics being discarded at inference, memory bank initialization with noise). Crucially, they propose a new metric formulation for anomaly detection:

Magnitude vs. Signed Fidelity: Standard signed fidelity penalizes "exculpatory evidence" (removing which raises the score). For anomaly detectors, this is counter-intuitive. The paper proposes scoring fidelity on magnitude ( $|p_0 - p_S|$ ) and reporting direction (incriminating vs. exculpatory) separately.

Key Results

Experiments were conducted on the MOOC dataset (7,144 nodes, 4,066 anomalies) using a frozen SAD detector.

Detection Parity: The introduction of the event mask (Axis A) resulted in zero deviation in detection metrics ( $\Delta AUC = 0.0000$ , $\Delta AP = 0.0000$ ), confirming the "exact pass-through" property.
Exact Attribution: Axis B achieved a completeness residual of $3.8 \times 10^{-6}$ on 6,000 real targets, confirming the mathematical exactness of the decomposition.
Instance vs. Baseline Split: On the MOOC dataset, the decomposition revealed that roughly half of the average alert's standing is attributable to the node's own behaviour (49.9%) versus a shift in the population baseline (50.1%).
Amortisation Efficiency: A controlled study of event-attribution strategies on an alarm list of 600 alerts showed that the amortised explainer achieved a characterisation score of 0.874, significantly outperforming per-instance optimisation (0.667) at 453 times lower computational cost. The amortised approach was separable from per-instance optimisation at 5.98 standard deviations.
Baseline Performance: A parameter-free gradient baseline ( $Gradient \times Input$ ) tied the trained explainers in characterisation (0.869), suggesting that for this specific detector, complex training objectives may not be necessary to achieve high-quality attribution.
Metric Correction: The study demonstrated that signed fidelity systematically mis-scores anomaly explanations. Random ablation raised the score on 78% of alerts, leading to large negative values for correct explainers under signed conventions.

Significance and Claims

The paper claims that X-SAD is the first post-hoc explanation framework for SAD, transforming previously undefined metrics (fidelity, characterisation, deviation attribution) into measurable quantities.

The primary significance lies in the duality of the approach:

Axis A provides a learned, approximate explanation for the decision logic, demonstrating that amortisation is the key driver of efficiency and stability over per-instance optimisation.
Axis B provides an exact, analytic decomposition of the anomaly score. The authors argue that this is a general design principle: detectors that expose their reference distribution admit exact attribution without learning. This allows analysts to distinguish between "entity-driven" and "baseline-driven" alerts, a distinction no existing dynamic-graph explainer can pose.

The paper concludes that where a detector's score admits an analytic decomposition, that decomposition should be preferred over learned masks due to its lack of hyperparameters, training budget, or seed variance. The framework operates at sub-second speeds (0.070 ms per alert), making explanation a routine attribute of triage rather than a forensic instrument.

Technical Summary: Exact Deviation Attribution and Amortised Event Explanation for Semi-Supervised Anomaly Detection on Dynamic Graphs

Problem Statement

Methodology: The X-SAD Framework

Key Results

Significance and Claims

More like this