Spatio-Temporal Graph Anomaly Detection
Peer-reviewed method for finding anomalies in time-varying graphs: predict each sensor's normal future with an attention-based graph network, then localize what's misbehaving from subgraph down to single node.
The brief
Traffic grids, sensor networks and financial guarantor networks are all spatio-temporal graphs: every node evolves over time and is coupled to its neighbours. Labelled anomalies barely exist for systems like these, so the problem has to be unsupervised. Train a model on normal behaviour, predict what each node should do next, and score the gap between expected and observed.
The paper’s contribution is where you look for that gap. Instead of scoring every node directly, the method works divide-and-conquer: first carve the graph into correlation-based subgraphs and find the one that is misbehaving (macro), then attribute the anomaly to specific nodes inside it (micro). Faster, and far more interpretable.
Statistically Inspired Discrepancy Detection for Anomalous Spatio-Temporal Graphs was accepted at IEEE DSAA 2024 (presented in person, San Diego) with a journal version in the Springer International Journal of Data Science and Analytics.
Where to read it: the journal article (DOI 10.1007/s41060-024-00656-0) or the DSAA 2024 extended abstract (DOI 10.1109/dsaa61799.2024.10722835).
How it works
- Predict the normal. An A3T-GCN (attention temporal graph convolutional network) forecasts each sensor: the GCN captures spatial coupling, a GRU captures temporal dynamics, and attention weights the timesteps. Trained on METR-LA (207 LA loop detectors at 5-minute granularity), forecasting one hour from one hour of history. It beat HA, ARIMA, SVR, GCN and GRU baselines.
- Macro: find the misbehaving subgraph. Pairwise sensor correlation is computed with Spearman rank correlation (robust to outliers and non-normal speed data), weighted by physical distance, and a BFS grows subgraphs where correlation clears a threshold. Adjacent sensors correlate at roughly 0.34 against 0.14 for non-adjacent ones, which validates the construction.
- Micro: attribute it to nodes. Inside an anomalous subgraph, z-score the prediction-versus-reality residuals per node and flag deviations beyond two sigma.
The honest bit
This was a preliminary study: a 2,000-timestep subset with 10% injected anomalies, and mean detection accuracy around 0.47. The credential is the peer review and the novel correlation-subgraph idea, not a production-grade detection rate. Correlation is not causality, and the paper says so. The public repo holds the prediction stage; the macro and micro algorithms live in the paper itself.
Credit
Co-authored with Atharv Tiwari, Shreyash Chatterjee and Sushanth Nair (the four of us contributed equally) and Prof. Bhaskarjyoti Das.