Mitigating Anomaly Hallucination: A Model-Agnostic Framework for Unsupervised Anomaly Detection on Dynamic Graphs

Abstract

Temporal graph neural networks (T-GNNs) are powerful for representation learning on continuous-time dynamic graphs (CTDGs), but naively applying them to unsupervised anomaly detection is often unreliable. The key challenge is learning normal dynamics while being exposed to unlabeled anomalies, which destabilizes optimization and anomaly scoring. We further observe that gradient spikes are not unique to anomalies: many normal nodes also have large gradient norms. These nodes are typically sparse, offering limited temporal-structural context for message passing, so T-GNNs may mistake event sparsity for abnormality under an unsupervised setting. We term this phenomenon anomaly hallucination, which increases false positives and degrades detection performance. To address this challenge, we propose AHEAD, an unsupervised anti-hallucination anomaly detection framework featuring a hallucination refinement pipeline and a temporal-structural detector, which is compatible with various T-GNN backbones for reliable anomaly detection on CTDGs. For the refinement pipeline, we define a node-level uncertainty score that combines gradient norms and temporal-structural residuals to quantify optimization sensitivity, and then filter out high-sensitivity nodes for training the T-GNN backbone, which stabilizes gradient flow and improves representation learning. To sharpen the decision boundary, we propose an amplified divergence loss that ensures a wider discrepancy between normal dynamics and latent anomalies, reducing the false positive rate. Last, we theoretically and empirically show loss separability as a natural indicator of abnormality and build on this insight to develop a temporal-structural anomaly detector, improving detection performance. Extensive experiments demonstrate that the proposed AHEAD consistently improves anomaly detection accuracy, achieving up to 28.02% AUROC gains across five T-GNN backbones.