One family of time-series anomaly detectors turns a long signal into a map. Each short window of the signal becomes a point. Windows with similar shapes are grouped into a node, and consecutive windows are joined by a directed edge whose weight counts how often that transition occurred. Normal behaviour shows up as busy routes through this map. An anomaly is a subsequence that takes a rarely used edge or visits a sparse node. These transition graphs work well: they catch anomalies that repeat, which defeats nearest-neighbour methods, and they catch abnormal orderings of shapes that each look normal on their own.
The weak point is how they treat rarity. A rarely used edge might be truly rare, or it might simply reflect too little observed data. These detectors cannot distinguish the two, and nothing in the method says how much normal data is enough. We propose to replace raw edge counts with a statistical test. A transition is flagged only when we are confident its true probability is below a rarity level. The test also tells the detector how finely it can afford to divide shape space into nodes given the data it has. The result is a detector whose false-alarm rate is controlled at small training sizes and whose accuracy does not decay as more data arrives. It also yields a finite-sample bound on the amount of normal history a transition graph needs, which no current graph-based detector has.
Core Claim
Series2Graph (Series2Graph; interactive version GraphAn) builds its graph in four steps. It embeds sliding windows with PCA, rotates the embedding to separate signal offset from shape, finds nodes as density peaks using kernel density estimation, and scores subsequences by edge weight and node degree. It reports average Top-k accuracy of 0.98 against 0.73 for STOMP and 0.78 for supervised LSTM-AD on its subsequence benchmarks. Its node resolution and score threshold are fixed by hand, and it provides no theory of how much data the graph needs.
A separate line of work, Finite Sample Complexity of Rare Pattern Anomaly Detection (PAC-RPAD), proves the relevant kind of result for i.i.d. tabular points. There, the data needed to detect rare patterns depends on the complexity of the family of candidate patterns, measured by its VC dimension, and not on the input dimension. It also documents non-monotonic learning: with more data, detectors start isolating "distractor" patterns that are rare but meaningless.
Our claim is that a transition graph is a pattern family of exactly this kind. Its complexity is set by the number of nodes $K$, which allows up to $K^2$ possible edges. Its samples are dependent, because they come from a Markov-like walk. Treating it this way gives three things. First, it gives a principled rarity test. Second, it gives a data-dependent rule for choosing $K$. Third, it gives a prediction that fixed-resolution graphs show both failure modes: too many false alarms when data is scarce, and distractor edges once data is plentiful.
The test works as follows. Let $n_i$ be the number of visits to node $i$, and let $\hat p_{ij}$ be the empirical frequency of the transition from node $i$ to node $j$. Using an empirical Bernstein bound with a union bound over all $K^2$ edges, we compute an upper confidence bound on the true transition probability:
$$ U_{ij} = \hat p_{ij} + \sqrt{\frac{2\hat p_{ij}\log(K^2/\delta)}{n_i}} + \frac{3\log(K^2/\delta)}{n_i}, $$
Here $\delta$ is the allowed failure probability. A transition is declared anomalous only if $U_{ij} < \tau$, where $\tau$ is the rarity level that counts as anomalous.
For an edge never seen in training, $U_{ij}$ reduces to $3\log(K^2/\delta)/n_i$. Such an edge can therefore be certified as rare only once node $i$ has been visited at least $3\log(K^2/\delta)/\tau$ times. Every node needs that many visits. Let $\pi_{\min}$ be the long-run share of time the walk spends in the least-visited node, and let $t_{\text{mix}}$ be the chain's mixing time, which corrects for the fact that consecutive windows are not independent. The required normal history is then roughly
$$ N \gtrsim \frac{t_{\text{mix}}\,\log(K^2/\delta)}{\tau\,\pi_{\min}}. $$
This is the transition-graph counterpart of the PAC-RPAD bound. The penalty for finer resolution enters through $\log K^2$ and through $\pi_{\min}$, which shrinks as nodes are split more finely.
The practical consequence is an adaptive resolution rule. We merge any node whose visit count is below the certification threshold into its nearest neighbour in shape space. We split a node only when both halves would still be certifiable. As a result, the graph coarsens automatically when data is scarce and refines as data accumulates. A secondary benefit is that one rarity level $\tau$ and one confidence level $\delta$ replace Series2Graph's dataset-specific density threshold. Those two values have a meaning that carries across datasets.
Research Program
The work has three parts.
The first part is theory. We will prove the bound above for transition graphs estimated from a single stationary, ergodic trajectory, using Markov-chain concentration in place of i.i.d. arguments. We will also characterise the extra error introduced because nodes are themselves estimated from data, which is a source of error that PAC-RPAD's fixed rectangles do not have. A clean result for fixed nodes, plus an empirical study of node-estimation error, would already be useful. A full joint bound is the stretch goal.
The second part is the detector. We keep Series2Graph's embedding and kernel-density node extraction unchanged. On top of them we add the confidence-bounded score and the merge/split rule. The window length stays fixed at the Series2Graph default, so that the change being tested is purely statistical.
The third part tests the predicted failure modes of fixed-resolution graphs. For the scarce-data regime, we look for false alarms in short training prefixes. For the plentiful-data regime, we inject benign noise into long normal training streams and check whether spurious low-weight edges cut precision, testing the distractor effect from PAC-RPAD in the temporal setting.
The proposal treats the three directions unevenly. The transition graph is the mechanism, subsequence detection is the application, and sample complexity is the lens. Multivariate extension is out of scope.
Baselines
The naive reference is a detector that scores each subsequence by its distance to the nearest normal training window, with no graph. It shows what any structure adds.
The strongest structural competitor is unmodified Series2Graph, run at its published defaults. We also run an oracle-tuned Series2Graph, whose node bandwidth and threshold are chosen per dataset using test labels. This gives fixed-resolution graphs every advantage. The proposal counts as beating it if, at small training prefixes, it matches or exceeds oracle-tuned Series2Graph without using any labels, and if its accuracy rises monotonically with training length where Series2Graph's does not.
The strongest number available on Lacuna for a non-graph method on a shared benchmark is subsequence PCA. It reaches VUS-PR 0.4233 on TSB-AD-U (Complexity- and Statistics-Guided Anomaly Detection in Time Series Foundation Models), where VUS-PR is a threshold-free precision-recall summary for time series. The same paper reports 0.3857 for base MOMENT, a pretrained time-series foundation model, and 0.4679 for its ensemble of subsequence PCA with a statistics-augmented MOMENT. That ensemble is the bar on TSB-AD-U. Beating subsequence PCA is the minimum we expect, and approaching the ensemble would be a strong result.
On the UCR archive, MDI and MERLIN beat deep methods in Is It Worth It?; no reported result was found on Lacuna for their scalar AUC ROC. Isolation Forest on subsequence features represents the PAC-RPAD view that it plateaus at 1,024 samples. On sequential data no reported result was found on Lacuna for it in this setting.
All methods are trained on the same training prefixes, with the same window length where one is needed, on CPU. Every tunable method gets the same unsupervised hyperparameter budget, except the oracle Series2Graph, which is labelled as an oracle.
Two ablations isolate the contribution. The first adds additive (Laplace) smoothing of edge counts to fixed-resolution Series2Graph. The second uses the confidence-bounded score without adaptive merging and splitting.
Why not just…?
Why not just smooth the edge counts? Adding pseudo-counts to every edge is the simplest fix for unseen transitions, and it is a real threat. Smoothing shrinks all estimates toward the same prior regardless of how often each node was visited. Our score instead adjusts per node through $n_i$, and adaptive resolution changes $K$ itself. If smoothing with one tuned pseudo-count matches the confidence-bounded score across all training lengths, the scoring contribution reduces to a justification for choosing the pseudo-count. The merge/split ablation then decides whether adaptive resolution adds anything beyond that. We will report this outcome honestly either way.
Why not just tune Series2Graph's thresholds per dataset? In the unsupervised setting there are no labels to tune against, and Series2Graph's open problems include exactly this threshold sensitivity. The oracle-tuned baseline measures the cost directly. If an untuned confidence-bounded graph is close to the oracle, the calibration claim holds.
Why not just use Isolation Forest or subsequence PCA, which are already sample-efficient? PAC-RPAD's plateau at 1,024 samples is proven for i.i.d. points. Point-wise partitioning is blind to ordering swaps, as Signature Isolation Forest shows. PCA reconstruction error does not register an abnormal ordering of two shapes that each reconstruct well. Subsequence PCA is nonetheless strong at 0.4233 VUS-PR, so the learning-curve comparison on TSB-AD-U will show whether transition structure pays off when data is limited.
Why not just use a pretrained foundation model, which needs no task data? Foundation models reconstruct anomalies as well as normal patterns. Their per-window normalisation (reversible instance normalisation) removes mean and variance shifts, as reported in Complexity- and Statistics-Guided Anomaly Detection in Time Series Foundation Models. The TAB benchmark (TAB) finds that simple non-learning methods often match them on univariate data.
Proposed Experiments
The central experiment is a set of learning curves. For each series we train on prefixes containing increasing numbers of normal cycles and evaluate on the same held-out segment. The datasets are the NASA simulated engine disk data, MIT-BIH record 820, and NYC taxi from the Series2Graph papers; the 250-series UCR archive; and TSB-AD-U. Metrics are VUS-PR, Top-k accuracy, and false alarms per thousand normal windows.
There are three decisive checks.
The first checks the bound. The measured false-alarm rate of the confidence-bounded detector should stay at or below its nominal level once $N$ exceeds the predicted threshold, and should exceed it below that threshold. We verify this on synthetic Markov-switching signals where $\pi_{\min}$ and $t_{\text{mix}}$ are known.
The second checks the distractor effect. When benign noise is injected into longer training streams, fixed-resolution Series2Graph should lose precision while the adaptive detector does not. If neither degrades, the distractor hypothesis fails in the temporal setting.
The third checks repeated anomalies. Rerunning Series2Graph's repeated-anomaly cases, the confidence test should preserve their detection. There is one honest caveat. An anomaly that repeats often enough in training will, correctly by this test's logic, be certified as a normal transition. We will report the repetition count at which that happens.
References
- Series2Graph: Graph-based Subsequence Anomaly Detection for Time Series
- GraphAn: Graph-based Subsequence Anomaly Detection
- Finite Sample Complexity of Rare Pattern Anomaly Detection.
- Complexity- and Statistics-Guided Anomaly Detection in Time Series Foundation Models
- Is It Worth It? Comparing Six Deep and Classical Methods for Unsupervised Anomaly Detection in Time Series
- Signature Isolation Forest
- TAB: Unified Benchmarking of Time Series Anomaly Detection Methods