💻 computer science

Dual Spatial-Temporal Shapley Attribution for Explainable Anomaly Detection in Dynamic Social Graphs

This paper introduces a post-hoc explainability framework that enhances the high-performing TADDY anomaly detector for dynamic social graphs by generating dual spatial and temporal Shapley attributions to identify influential neighbors and historical snapshots, achieving high fidelity and sufficiency metrics without compromising detection accuracy.

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

Published 2026-08-25

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Iyad Assaad NEKKA, Hamida seba, 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 vast, shifting landscape of the digital world, social networks are never truly still. They are living structures where connections form and dissolve every second, from the moment a message is sent to the instant a rating is posted. In these evolving webs of interaction, bad actors often hide, creating patterns that look like normal behavior but are actually coordinated attempts to deceive, defraud, or disrupt. Detecting these anomalies is a high-stakes challenge for online platforms, financial systems, and trust networks. For years, powerful computer programs have been able to spot these suspicious activities with great accuracy, acting like highly sensitive alarms that ring when something is wrong. However, a critical problem has remained: when these programs sound the alarm, they offer no explanation. They can tell a human operator that a specific connection is suspicious, but they cannot say why. They do not reveal which person in the network triggered the warning, nor do they explain if the trouble started right now or if it was building up over time. Without this context, the people responsible for keeping these platforms safe are left with a score and a question mark, unable to make informed decisions about whether to block a user or investigate further.

A new study addresses this gap by giving these silent detectors a voice. Researchers have developed a method that wraps around existing, high-performing anomaly detection systems to generate clear, human-readable reasons for their decisions. The work focuses on a specific type of advanced detector that analyzes social networks by looking at both the immediate neighbors of a connection and its history over time. While this detector was already excellent at finding bad connections, it previously produced no explanation for its choices. The new framework changes this by breaking down the decision into two distinct parts. First, it identifies the spatial cause: which specific people or nodes in the network were the primary drivers of the suspicion. Second, it identifies the temporal cause: which moments in the past carried the strongest signal that something was wrong. This dual approach answers the two questions that analysts actually need to know: was this anomaly caused by a suspicious partner, or by a suspicious pattern in how they have interacted in the past?

To achieve this, the researchers adapted a mathematical concept known as Shapley values, which is used to fairly distribute credit or blame among a group of contributors. In this context, the "contributors" are the various pieces of information the computer used to make its decision. The team had to be careful about how they tested the system. If they simply removed a piece of information, the computer might get confused because the remaining data would look unnatural. Instead, they replaced the removed information with a neutral average of the remaining data, ensuring the computer's internal logic remained stable and the results were accurate. This allowed them to measure exactly how much each specific neighbor or each specific moment in time contributed to the final warning. The result is a detailed map of influence for every flagged connection, showing exactly which elements pushed the score over the line.

The researchers tested this method on three different real-world social network datasets, including online messaging platforms and cryptocurrency trading networks where trust is essential. Before this work, it was impossible to measure how well these detectors could explain themselves because they had no explanation mechanism at all. After applying the new framework, the system proved highly effective. It successfully identified the key factors behind the detection in nearly all cases, with a measure of accuracy reaching 0.9562. It also confirmed that the top few factors identified were sufficient to trigger the alarm on their own, reaching a score of 0.9658. Crucially, adding this layer of explanation did not slow down the detector or make it less accurate at finding the actual problems; the detection performance remained exactly the same. The system was also tested on thousands of specific connections, including those that were correctly identified, those that were false alarms, and those that were difficult to classify. In every category, the framework provided clear, actionable reasons for the decision.

One of the most significant findings involves how the system handles false alarms. In the real world of social media moderation, false alarms are common and costly because they waste human time. The new framework excelled here as well, explaining why the detector mistakenly flagged a normal interaction as suspicious. By pinpointing the exact structural pattern that caused the confusion, the system allows human operators to quickly clear these false alarms without having to manually review the entire history of the interaction. This capability is a major step forward for practical deployment, as it turns a raw alert into a guided investigation. The study also revealed a subtle but important nuance in how anomalies behave. For some difficult cases, the warning signal was not concentrated in a single person or a single moment, but was spread out across the entire network history. The framework was able to detect this distributed pattern, showing that the anomaly was a result of a general context rather than a specific event.

The significance of this work extends beyond just one type of computer program. The approach is designed to be a post-hoc solution, meaning it can be applied to detectors that are already trained and in use without needing to be retrained from scratch. This makes it immediately useful for organizations that rely on these systems for safety and security. By providing a principled way to understand the "why" behind the "what," the research bridges the gap between powerful artificial intelligence and human accountability. It ensures that when an automated system flags a user or a transaction, the people in charge can understand the reasoning, verify the logic, and take appropriate action. The study confirms that it is possible to have both high-performance detection and deep, interpretable explanations, a combination that was previously missing from the most advanced tools used to monitor the dynamic social web.

Technical Summary: Dual Spatial-Temporal Shapley Attribution for Explainable Anomaly Detection in Dynamic Social Graphs

Problem Statement
Anomaly detection in dynamic social graphs is critical for high-stakes domains such as online trust communities, fraud analysis, and coordinated inauthentic behavior detection. While state-of-the-art detectors like TADDY (Transformer-based Anomaly Detection for Dynamic Graphs) achieve strong performance by modeling spatial and temporal dependencies, they operate as black boxes. When an edge is flagged as anomalous, these models provide only a score without justification. In operational settings (e.g., trust-and-safety teams or regulatory compliance), the inability to explain why an edge was flagged—specifically, which neighbor nodes or historical time steps drove the decision—creates a deployment barrier. Prior to this work, TADDY produced no attribution vectors, rendering standard explainability metrics (Fidelity, Sufficiency, Comprehensiveness) undefined for this class of models.

Methodology
The authors propose a post-hoc explainability framework that wraps a trained, frozen TADDY model without modifying its weights or inference pipeline. The framework generates two complementary attribution vectors for every flagged edge:

Spatial Attribution: Identifies which neighbor nodes contributed to the anomaly.
Temporal Attribution: Identifies which historical snapshots carried the strongest signal.

The core technical approach adapts GraphSVX (a Shapley value-based explainer for Graph Neural Networks) to TADDY's specific architecture, which uses a windowed token sequence. Key methodological innovations include:

Graph-Aware Embedding-Space Perturbation: Standard masking of tokens in index space is invalid for TADDY because index 0 corresponds to the highest-ranked neighbor, not a neutral token. Instead, the framework replaces excluded tokens with the mean embedding of the active coalition. This keeps perturbed sequences within the convex hull of active token embeddings, ensuring they remain in-distribution for the Transformer.
Dual Decomposition: The framework aggregates Shapley values along two orthogonal axes. For a token matrix $H \in \mathbb{R}^{D \times d}$ , the Shapley coefficients $\hat{\beta}$ are summed by node identity to produce $\phi_{spatial}$ and by time step to produce $\phi_{temporal}$ .
Surrogate Fitting: A "Smarter" coalition sampler is used, anchoring on the full and empty coalitions to enforce Shapley efficiency. A Weighted Least Squares (WLS) Ridge regression surrogate is fitted to approximate the Shapley values.

Key Contributions

First Post-Hoc Framework for TADDY: This is the first method to introduce explainability to TADDY-style dynamic graph anomaly detectors, transforming undefined metrics into measurable quantities.
Dual Spatial-Temporal Attribution: Unlike scalar methods that provide a single importance score per token, this framework simultaneously answers whether an anomaly was driven by a suspicious counterparty (spatial) or a suspicious interaction history (temporal).
Robust Perturbation Strategy: The introduction of an embedding-space perturbation strategy that avoids pathological artifacts associated with standard index-space masking in token-based architectures.
Comprehensive Evaluation: An expanded evaluation covering 2,471 edges across true positives, false positives, and low-confidence detections, demonstrating robustness across different edge categories.

Experimental Results
The framework was evaluated on three dynamic social graph benchmarks: UCI-Message, Bitcoin-Alpha, and Bitcoin-OTC.

Zero Performance Cost: The explainability layer preserves detection performance exactly, with $\Delta AUC = 0.0000$ across all datasets.
Metric Introduction: Before this work, Fidelity, Sufficiency, and Comprehensiveness were undefined for TADDY. After applying the framework:
- Fidelity reached 0.9562 (averaged across all true positives).
- Sufficiency reached 0.9658.
- Comprehensiveness was confirmed as positive across all datasets.
False Positive Explainability: The framework achieved high fidelity (0.836–0.996) on false positive edges, enabling analysts to identify the specific structural patterns that triggered false alarms.
Borderline Detections: The study observed negative Comprehensiveness in low-confidence true positives (e.g., -0.3995 on Bitcoin-Alpha), revealing a distinct "contextual anomaly" pattern where the signal is distributed across many tokens rather than concentrated in a few.

Significance and Claims
The paper claims that its primary contribution is not merely an incremental improvement in Fidelity scores, but the introduction of explainability into a model class where it previously did not exist. The authors argue that scalar attribution methods (gradients, attention weights) fail to measure causal contribution in the Shapley sense and cannot answer the specific operational questions practitioners need: "Was this anomaly driven by a suspicious counterparty or a suspicious history?"

The framework is presented as a principled, post-hoc template applicable to any dynamic graph detector using token-based representations. It addresses the "explainability gap" that currently hinders the deployment of deep learning anomaly detectors in regulated or high-stakes social network environments. The authors emphasize that by providing dual attribution vectors, the framework offers actionable insights for triaging alerts, particularly for filtering false positives without exhaustive manual review.

Technical Summary: Dual Spatial-Temporal Shapley Attribution for Explainable Anomaly Detection in Dynamic Social Graphs

More like this