When we think of an anomaly in a time series, we often picture a sudden spike or a dramatic drop—a single data point that stands far apart from the rest. However, real-world anomalies are rarely that simple. Often, the individual pieces of a sequence look completely normal, but their ordering or context is broken. For instance, in an electrical grid, a medical monitor, or a traffic intersection, every individual action might be routine, but an unprecedented sequence of these actions indicates a severe failure, theft, or accident.
Traditional anomaly detection methods struggle here. They rely heavily on computing pairwise distances between subsequences in a high-dimensional space. This approach breaks down under two conditions: when the anomaly is defined by a rare transition between normal patterns, and when an anomaly repeats multiple times (known as the "twin freaks" problem), causing distance-based metrics to mistake the recurring anomalies for a legitimate cluster of normal behavior.
To solve this, a powerful paradigm has emerged: transforming continuous time series into temporal transition graphs. In his foundational work on large sequences, Paul Boniol proposes shifting the focus from finding isolated outliers to building a robust topological model of normal behavior. By mapping subsequences to nodes and sequential transitions to edges, this approach shifts the problem from geometric distance to topological density.
From Continuous Series to Discrete Topology
How do you turn a continuous, fluctuating line into a network of nodes and edges? The core idea is to discretize the time series by identifying its underlying structural building blocks.
As detailed by Ziqiang Cheng et al. in their Time2Graph framework, a time series can be broken down into short, representative subsequences or "shapelets." Instead of treating these shapelets as static, isolated features, the authors organize them into a shapelet evolution graph to capture how temporal data changes over time.
In a typical unsupervised implementation, such as the Series2Graph algorithm developed by Paul Boniol et al. in SAD: An Unsupervised System for Subsequence Anomaly Detection, the process follows a clear pipeline:
- Sliding Window Extraction: The long time series is sliced into overlapping subsequences using a sliding window.
- Shape Space Embedding: These subsequences are embedded into a lower-dimensional space that captures their shape characteristics.
- Node Mapping: Similar shapes are clustered together. Each cluster becomes a node in the graph, representing a specific "state" or pattern of the system.
- Edge Generation: The algorithm traces the original time series chronologically. If the system moves from a subsequence in Cluster A to a subsequence in Cluster B, a directed edge is drawn from Node A to Node B.
Continuous Time Series: /\_/\__/\_/\__/\_/\_/\__
↓
Discretized Subsequences: [Pattern A] -> [Pattern B] -> [Pattern A]
↓
Graph Topology: (Node A) ======[High Weight]======> (Node B)
By the end of this process, the continuous temporal data is completely captured within a directed graph topology.
Why Graph Topology Exposes Anomalies
To understand why this works, imagine a time series representing a heartbeat. A normal heartbeat goes: lub-dub, pause, lub-dub, pause. If we cluster these shapes, we get three nodes: [lub], [dub], and [pause]. The normal transitions are [lub] → [dub] → [pause] → [lub]. This forms a high-traffic loop in our graph.
Now imagine an anomaly occurs: lub-pause-dub. The individual shapes [lub], [pause], and [dub] are completely normal. But the transition [lub] → [pause] is extremely rare. In the graph, this creates a faint, low-weight edge that immediately stands out.
In a healthy, repetitive system, normal behaviors manifest as high-traffic highways: dense hubs of highly connected nodes and thick, high-weight edges. Conversely, anomalies stand out because of their position within the network topology. As explained by Paul Boniol et al. in Series2Graph: Graph-based Subsequence Anomaly Detection for Time Series, patterns that traverse low-weight edges or visit isolated, low-degree nodes are flagged as anomalies because they deviate from the high-frequency paths that define normal behavior.
Researchers leverage different topological properties to score these anomalies:
- Edge Weights and Degree: The simplest approach flags subsequences that traverse edges with very low transition frequencies, naturally isolating anomalies as fringe trajectories.
- Random Walks: Haibin Cheng et al. demonstrated that by running a random walk over a similarity-based graph, anomalous time points can be identified as nodes that are rarely visited due to their low connectivity.
- Graph Diffusion: To capture long-range context in interconnected systems, Guansong Pang et al. highlight the use of graph diffusion mechanisms to model complex dependencies over time, ensuring that a pattern that seems normal in isolation is flagged if it violates the broader contextual topology.
Defeating the "Twin Freaks" Problem
One of the most compelling reasons this graph-based transformation works so well is its inherent resistance to the twin freaks problem, where an anomalous pattern repeats multiple times in a dataset.
Imagine our heartbeat patient has a specific arrhythmia that happens 50 times during a 24-hour scan. In a traditional distance-based algorithm, these 50 subsequences will sit extremely close to one another in feature space. The algorithm looks at this tight cluster of 50 points and concludes, "Because these points are close to each other, they must represent normal behavior." The anomaly effectively hides in plain sight by duplicating itself.
Graph-based modeling fundamentally changes this dynamic. In a system like GraphAn, developed by Paul Boniol et al., all identical or highly similar subsequences are grouped into the exact same nodes. If an anomalous pattern repeats 50 times, it simply flows through the same path 50 times. Crucially, if the normal behavior path has been traversed 100,000 times, the anomalous path's edge weight remains miniscule by comparison.
As the authors of Series2Graph note, the graph representation preserves the relative "traffic" difference. This structural separation allows the system to easily distinguish low-traffic anomaly paths from high-traffic normal trajectories, no matter how many times the anomaly repeats.
Scaling and Broadening the Paradigm
Because graph topology abstracts away raw, continuous data, it provides a highly flexible and interpretable framework that scales across diverse domains.
In a comprehensive overview of the field, Paul Boniol et al. in New Trends in Time Series Anomaly Detection note that graph-based transformations convert temporal sequences into nodes and edges to leverage density-based outlier detection, mapping anomalies to sparsely connected or isolated regions within the generated graph topology.
This concept extends naturally from univariate time series to spatial trajectories. In the uTRAND framework by Giacomo D'Amicantonio et al., traffic monitoring is revolutionized by mapping vehicle movements onto a semantic-topological graph of an intersection. An anomalous maneuver (like an illegal U-turn) is instantly flagged because it attempts to traverse a non-existent or low-probability edge in the learned transition graph. This provides immediate, human-readable explanations for why a trajectory is anomalous.
Furthermore, this structural simplification enables massive performance gains. Because the graph eliminates the need for expensive, exhaustive pairwise distance calculations across millions of data points, it can run orders of magnitude faster than traditional methods. As Phillip Wenig et al. demonstrate, the transition-graph formulation can be distributed efficiently across computing clusters, unlocking unsupervised sequential anomaly detection for massive, industrial-scale IoT and sensor streams.
Key Foundational Work
GraphAn: Graph-based Subsequence Anomaly Detection (2020) — contributed 3 concept elements to this direction.
Series2Graph: Graph-based Subsequence Anomaly Detection for Time Series (2020) — contributed 2 concept elements to this direction.
Unsupervised Subsequence Anomaly Detection in Large Sequences (2020) — contributed 2 concept elements to this direction.