Graph-based anomaly detection for time series

Most anomaly detection tutorials hand you one wiggly line and a threshold. Real systems are never one line. A quick-commerce dark store has hundreds of SKUs selling together; a data centre has thousands of machines breathing in sync; a crowd has dozens of camera zones filling and emptying in a choreography. The interesting failures aren't "this number got big." They're "these things stopped moving together the way they always do." That relational shift is exactly what a graph is built to see, and it's why I keep reaching for graph-based methods on multivariate time series.

Why a single threshold quietly fails

Say you monitor 50 sensors. The classic approach is 50 independent detectors — a z-score or an ARIMA residual per stream. It works until the day two sensors that are always correlated silently drift apart. Each one stays inside its own normal band, so every individual detector says "fine." But the relationship broke, and that's often the earliest, clearest symptom of a real fault. Per-stream models are structurally blind to it because they never modelled the relationship in the first place.

On the demand-forecasting work I did, this showed up constantly: individual SKUs looked plausible, but the joint pattern — milk up while bread flat during a festival window — was the actual signal. You only catch that if your model knows the two series belong together.

Turn the series into a graph

The move is to stop thinking "streams" and start thinking "nodes and edges."

• Nodes are your entities — sensors, SKUs, machines, camera zones. Each node carries its own recent time-series window as its features.
• Edges encode which entities are related. Sometimes you know this a priori (these two machines share a power rail). Often you learn it from the data — an edge exists if two series have historically moved together.

Now "normal" isn't a band around one line. It's the whole shape of the graph — its topology plus the values flowing across it. An anomaly is a moment where the current graph doesn't look like the graphs the model learned to expect.

Building the edges (when nobody hands you a topology)

The two approaches I use most:

• Correlation / similarity graphs. Compute pairwise correlation (or DTW distance for lagged relationships) over a training window and connect the strongest k neighbours per node. Simple, transparent, and a genuinely strong baseline.
• Learned graphs. Let the model discover the adjacency itself. Give each node an embedding and let it learn which other nodes it should attend to — the graph becomes a trainable parameter instead of a preprocessing step. This is the trick behind graph attention approaches like GDN (Graph Deviation Network).

import numpy as np

# k-nearest-neighbour correlation graph over a training window
# X_train: shape (timesteps, n_series)
corr = np.corrcoef(X_train.T)          # (n_series, n_series)
np.fill_diagonal(corr, 0)

k = 8
edges = []
for i in range(corr.shape[0]):
    neighbours = np.argsort(np.abs(corr[i]))[-k:]   # top-k related series
    edges += [(i, j) for j in neighbours]

How the detector actually flags something

Once you have the graph, a Graph Neural Network learns to predict each node's next value from its neighbours. That framing is the whole game. A GNN layer lets every node "listen" to the nodes it's connected to and combine their recent behaviour to forecast its own next step. Because it forecasts through the relationships, it encodes what normal collective behaviour looks like.

Detection then has a satisfying rhythm:

• At each timestep, the GNN predicts what every node should do next.
• Compare prediction to reality — the gap is a per-node deviation score.
• When one node's deviation spikes far past its own historical error, flag it. Because the prediction used its neighbours, a spike means "this node broke the pattern its community expected of it" — not just "this number moved."

The payoff you don't get from per-stream models: localization. The graph tells you not only that something is wrong but which node and, by walking its edges, which related nodes are implicated. In an incident review, "node 34 and its three neighbours diverged at 02:14" is worth ten dashboards of red lines.

The parts that bite you in practice

• Non-stationarity. Relationships drift. A festival, a deploy, a season — the "normal" graph from March may be wrong in October. You need to retrain or use a rolling window, or you'll drown in false positives that are really just concept drift.
• Threshold-setting is still the hard part. The GNN gives you clean deviation scores; turning them into alerts is a business decision. I lean on a smoothed error (POT / peaks-over-threshold, or a simple robust z-score on the deviations) rather than a hard constant.
• Labels are scarce. You almost never have labelled anomalies, so this lives in unsupervised territory. Validate on the handful of known incidents you do have, and be honest that precision is hard to estimate.

When it's worth the extra machinery

Be honest with yourself: if you have a handful of independent streams, a good per-series model with solid seasonality handling will beat a fancy graph and cost you a tenth of the effort. Graph-based detection earns its complexity when the relationships between series carry the signal — dozens or hundreds of entities that move as a system, where the failures you care about are failures of coordination. That's when modelling the edges stops being elegant overkill and starts being the only thing that actually sees the problem.

A single time series can only tell you it changed. A graph of time series can tell you the relationship changed — and that's usually the alarm you actually wanted.