Modeling Spectral Energy Shifts in Spatio-Temporal Graph Anomaly Detection

Graph anomaly detection methods aim to distinguish anomalous nodes. While prior methods characterize anomalies through increased variation in the spectral energy distributions, they overlook those that result in decreased variation, i.e., camouflaged anomalies that appear normal. We show that this type of anomaly persists across multiple datasets and remains undetectable by existing spectral approaches. To address this limitation, we propose a node-level spectral energy formulation that is fully compatible with message passing and enables the detection of camouflaged anomalies. Building on this formulation, we introduce an energy-aware graph learning framework that models spectral shifts through energy-driven message passing in both static and time-series graphs. Besides, our unified architecture extends to temporal settings without introducing specialized sequence modules, enabling efficient learning under long sliding windows. Extensive experiments on large-scale benchmarks demonstrate the effectiveness and scalability of our approach. Our code is available at https://github.com/AICPS-Lab/Spectral-Energy-Shifts-in-GAD.

Many real-world systems, including review platforms, financial networks, social media, and infrastructure sensors, can be modeled as graphs where suspicious behaviors propagate through relational structures. Existing graph anomaly detection methods mainly identify nodes that deviate sharply from their neighbors. However, many anomalies are camouflaged: they mimic normal behavior and appear overly smooth rather than irregular. We show that this overlooked pattern exists in real benchmark datasets, where anomalous nodes can exhibit lower spectral energy instead of the higher energy emphasized by prior work. To address this, we propose EGNN, a scalable graph neural network that captures both increases and decreases in local spectral energy around each node. This enables detection of both conspicuous and camouflaged anomalies without costly whole-graph spectral computations. We further extend this idea to dynamic graphs without relying on heavy sequence models. Across seven static and time-series benchmarks, EGNN consistently improves anomaly detection while remaining scalable and parameter-efficient.