A persistent homology-based algorithm for unsupervised anomaly detection in time series
Authors: Alexandre Bois
Brian Tervil
Laurent Oudre
Venue: Accepted by TMLR ()

Abstract: In this article, we propose a new algorithm for unsupervised anomaly detection in univariate time series, based on topological data analysis. It relies on delay embeddings and on the extraction of persistent cycles from the 1-dimensional persistent homology  constructed from the distance to measure Rips filtration. This filtration makes it possible to identify 1-cycles (i.e. loops) corresponding to recurrent patterns by leveraging density information. Points in those cycles are considered as normal, and the algorithm can then assign an anomaly score to any point which is its distance to the normal set.
In this paper, we describe the algorithm, make a theoretical study, and test it on several real-world and synthetic datasets, showing that it is competitive with state-of-the-art anomaly detection methods.

Published in Transactions on Machine Learning Research (12/2024)
A persistent homology-based algorithm for unsupervised anomaly detection in time series
alezandre. alezandre.bois@ens. hoisseen-pporis--eee poris-saclay. Université Paris Saclay, Université Paris Cité, ENS Paris Saclay, CNRS, SSA, INSERM, Centre Borelli Gif-sur- Yvelte, 91190, France
Alexandre Bois
Brian Tervil
brian.tervil perrilaens--priisssallyy Université Paris Saclay, Université Paris Cité, ENS Paris Suclay, CNRS, SSA, INSERM, Centre Borelli Gif-sul sur- Yuette, 91190, France
Laurent Oudre
lourent. www.oodddrreenerri----eeoeoeeeee
Université Paris Saclay, Université Paris Cité, ENS Paris Saclay, CNRS, SSA, INSERM, Centre Borelli Gif-sur- Yuette, 91190, France
Reviewed on OpenReview: https: oppnrevvee.. net/forunt id- H6ChfpM311
Abstract
In this article, propose algorithm for unsupervised anomaly detection in univariate time series, based on topological data analysis. It relies on delay embeddings and on the extraction of persistent cycles from the 1-dimensional persistent homology constructed from the distance to mcasure Rips filtration. This filtration makes it possible to identify 1-cycles (i.e. loops) corresponding to recurrent patterns by leveraging densily information. Points in those cycles are considered as normal, and the algorithm can then assign an anomaly score to any point which is its distance to the normal set. In this paper, describe the algorithm, make theoretical study, and test it several real-world and synthetic datasets, showing that it is competitive with state-of-the-art anomaly detection methods.
1 Introduction
Anomaly detection in time series is an important problem in data science, with applications in many fields such as healthcare (Ansari et al. 2017) and engincering (Woike et al., 2014p. A time series is a sequence of real numbers x = (x(s)ss (n will always denote the length of the time series). In the context of anomaly detection, is assumed be composed of normal behavior and anomalies, i.e. points or sequences of points that differ from the normal behavior. More preciscly, in several application contexts such industrial monitoring or healthcare, the time series is usually assumed to be composed of some repetitive tppetitivefrrquuent patterns, possibly of varying lengths (think for instance of an heartbeat in ECG data) among which some occur a large number of times (the normal ones) and some have significantly fewer occurrences (the abnormal ones) see Figure for an illustration.
Over the past. years, several unsupervised anomaly detection algorithms have been developed from different
research areas (Liu et al. 2008 Breunig et al. 2000 Goldstein & Dengel, 2012 Yeh al. 2018
Boniol al.
2021 Aggarwal & Aggarwal 2017 Sakurada & Yairi 2014
Malhotra et al. 2015 Li et al. 2007 Munir
et al. 2018 Schölkopf et al.
1999)
(see Paparrizos et al. (002 and Schmidl et al. (2022 for comprehensive
review). Among them, some rely on a model and use the prediction or reconstruction error as an anomaly detector and some are based on clustering or machine learning Lechniques applied on the subsequences in order to detect outliers. For instance, LOF (Breunig et al. 2000) transforms the time series into a point cloud and studies the donsity of each point to assess whether or not they correspond normal or abnormal behaviors. Some methods aim find subsequences that represent the normal behavior and define anomalies subsequences that differ from normality. The fact that the patterns have different lengths, that there

---

Published in Transactions on Machine Learning Research (12/2024)
can be multiple normal patterns and multiple occurrences of an anomaly, and noise make it difficult to build a universal anomaly detection algorithm (Paparrizos et al. 2022). The main differences between the approaches actually lie in the implied definition given to the notion of normality.
Topological data analysis (TDA), and more specifically persistent homology [deesbbuunner & Harer, 2010, Boissonnat et a 2018) a set of techniques derived from algebraic topology. which allows to analyze the structure of data by constructing sequence of simplicial complexes (a filtration). The persistence diagram sums up when connected components, loops going through the filtration. TDA has been applied to many fields (Chazal & Michel 2021 including time scries analysis. It is particularly adapted to study structured data such as time series with a periodic behavior [Perea & Harer 2015 Enrani et al.) 2014, Bonis et al. 2022 Bois et al., 2022), and methods from TDA benefit from stability theorems that guarantee a certain robustness to noise (Chazal et al.) 2014 Anai et al. 2020). The most commonly used filtrations are the Čoch and the Vietoris-Rips filtrations. As those filtrations are not robust to the presence of outliers, now variants based on the notion of distance to a mcasure were introduced in Chazal et al. (2011): Buchet et al. (2016); 6); Anai et al. 22020), along with new stability theorems. Other relevant filtrations are defined in De Silva & Carlsson (2004) Bell et al. (2019). The authors of Anai ct al. 20200: : Ueda ct al. (2022) Fernándoz ct al. (2023) explain how sequences of persistence diagrams can be used for change detection or anomaly detection in time series. However, these methods seems more relevant for change detection than anomaly detection as it is not designed to handle typical cases such as punctual anomalies, multiple normal behaviors or repeated anomalies. Indeed, they consist in computing the persistence diagram corresponding to a sequence of growing subwindows of a time series and to compare consecutive diagrams to detect changes. Thus, when there are multiple patterns, changes would be detected at the first occurrence of cach pattern but they would often not correspond to an anomaly. In the case of a repeated anomaly a change would only be detected at its first occurrence and the following ones would be missed. Moreover, this methods requires to compute many persistence diagrams which can lead to a high computation time.
nigher-dimensional simplices appear and disappear when
In the case of periodic functions, the importance of 1-dimensional persistent homology (the study of loops in point clouds) was theoretically studied in Perea & Harer (2015) and it was applied time series in Emrani et al.) 2014); Perca et al. (2015) by transforming the data into point cloud and considering the most important loop. By extension, I-dimensional persistent homology is also relevant to study time scries with repetitive patterns.
In a nutshell, our method consists in transforming the time series into a point cloud and extracting 1- cycles (i.e. loops) that are considered correspond to normal patterns of the time series. We will use the Vietoris-Ripe filtration associated the empirical distance to a measure as described in Anai et al. (2020). Those cycles are identified on the persistence diagram because density information is used to construct the filtration. Once "normal cycles" have been extracted, an anomaly score is defined for each point of the embedding as its distance to the normal cycles. The specificity of our method is that it makes a global study of the delay embedding to find loops corresponding to whole patterns and also integrates local density information through the choice of the filtration, that is used to distinguish normal and abnormal points by reading the persistence diagram.
Contributions. In this paper, we apply methods from topological data analysis to unsupervised anomaly detection in time series. Our contributions are listed below.
We propose a model of time series that makes it possible to formally define the anomaly detection problem. It includes the possibility of having multiple normal abnormal behaviors, repeating anomalies and noise. We show examples of real-life time series that fit this model.
We present a new method for anomaly detection based on persistent homology. The method uses a delay embedding and the Victoris-Rip Rips filtration associated to the empirical distance to measure to find 1-cycles made of dense points and identify them to the normal behavior.
We use a property of this filtration to deal with a subset of the point cloud while keeping information from the whole data in order to significantly decrease computation time.
2

---

Published in Transactions on Machine Learning Research (12/2024)
We use model to derive upper bound on the interleaving distance between the filtration used in our algorithm (with discrete, noisy data with anomalies) and filtration obtained in an ideal situation with a continuous signal without noise or anomalies.
We study the behavior of our algorithm with different parameters and the influence of noise, and show that it competitive to state-of-the-art anomaly detection methods on different real-world datasets.
The article is organized as follows. in Section 2 we introduce our model of time scries and our definition the anomaly detection problem, along with the theoretical background required for the rest of the paper. Section
X describes our algorithm. Section f contains the theoretical study. In Section 5 we present the 13 state-of-the-art anomaly detection methods and real-world and syuthetic datasets. In Section G we use these datasets to study the behavior of our algorithm with different paramcters and the influence of noise, compare to state-of-the-arl anomaly detection methods. Note that section 2.2, 2.3 and 4.1 present already existing objects and results. Every other sections describe new research.
2 Background and problem formulation
In this scction, we give the mathematical background required to understand the studied problem and the proposed algorithm. Notations that used throughout the paper listed in Table 1
2.1 Model and problem
In this subsection, we introduce a model for time series which makes it possible to formally define the anomaly detection problem.
Let (x({))eeo.1) and (e(())eejo.) be real-valued functions defined on [0, 1]. We call the signal and is called the noise.
Remark 1. We will always use the term signal for continuous real-valued functions, and time series for sonile sequences of real rumbbers.
We use convolutional sparse coding model (Papyan et al. 2017) with an additional hypothesis to describe x as sequence of atoms, which are either normal or abnormal. Formally, we assume that can be written in the following way:
Mn
M a,
x
n.
m
+
ax.
(1)
The n, and a; are respectively normal and abnormal aloms of length In < 1 (resp. l.,,, iee. contin- uous functions on [0, with support [0, n..] (resp. [0, and such that n,(0) = n; (4,.) = (resp. a,(0) a,,,) = 0). There are Mn normal atoms and M, abnormal atoms. The n and a are the activations: binary functions on [0, 1] that take the value 1 only finite number of times. Thus, n; m) is signal where occurvence of n; starts at each time where n/[t]] 1. For each i, the number of occurrences of atom n; (resp. a,) is denoted by kn, |imilo (resp. ka. =|osllo), where l|-Ilo is the number of non-zero values of a function or vector.
Finally, we define the normal and abnormal parts of the signal as
Ma
M,
n; * m, and X. = >
X,
a, 04;
i=1
3

---

Published in Transactions on Machine Learning Research (12/2024)
Table Notations
Notation
Description
Time
Length of the time series.
Dimension of the time delay embedding. Delay of the time delay embedding. Signal: a continuous function defined on [0, 1].
T
(x(1)))
(8l1))sisn
Time series: a finite uniform subsampling of Normal atom i.
n;
Abnormal atom i.
(resp. Xa)
Normal (resp, abnormal) part of the signal. Normal (resp. abnormal) part of the time series.
on (resp. 8n)
Mn. (resp. Ma.)
Number of normal (resp abnormal) atoms. Activations of n, (resp. az).
7 (resp. oc;)
ki: (resp. ka:)
Number of occurrences of n, (resp. ai).
In (resp. las)
Length of atom n, (resp. a,).
Number of normal occurrences: Σ Ma, knn
kn
ki
Number of abnormal occurrences: >i=1 kas-
Ma,
lix V (Va) JaERt
Total number of occurrences: kin Ki. A filtration.
V
Persistent homology module corresponding to the filtration V. Persistence diagram corresponding to the persistence module V. Time delay embedding of a signal or time series x, with dimension and delay т (or, in Section 2.2 a subset of E). A probability measure on E with support included in B. Distance function the measure jB with parameter m.
Diag(V) (V)
Xd.7 or X
PB (where B E)
dan. d;
Interleaving pseudo-distance.
dy
Bottleneck distance.
W2
Wasserstein distance with quadratic cost.
dи
Hausdorff distance.
p E N m X) ej0, 1[ (with g E N)
Parameter of the weighted filtrations.
Parameter m of the DTM.
Cech X, f.p) p] (where B C E)
Weighted Čech filtaaion with parameters (X, ppp
with function f, and parameters m, p. Weighted Rips filtration with parameters (X, f .P). with function f, and parameters m,
Rips[X, f.p (where BCE)
along with the numbers kn = MMa, kins Ka
Ma, Diel ka, and 1x = kin + hig
Let > e N. In the rest of the paper, will always denote by å the uniform subsampling of size of any given signal (s(t))<ejo.1), that is $ ($D)))sisn) where $[5] -| All the above signals, atoms, activations and quantitics can be defined the same way in the discrete case starting from
Ma
Ma à
*
n
n +
1=1
With this model, can formally define the anomaly detection problem.
Definition (Anomaly detection problem). The anomaly detection problem consists in finding the of integers [1,m] such that { 0, which means fonding all the discrete abnormal activations and alom
4

---

Published in Transactions on Machine Learning Research (12/2024)
500
1000
1500
2000
2500
3000
Figure 1: An example time series, with normal patterns in green and red (and the mull parts in dark blue) and three abnormal ones (in blue, orange and purple), with Gaussian noise of amplitude 0.1.
lengths.
We now make some assumptions related to the model in the context of anomaly detection. The first assumption states that all the and a, * a have disjoint supports, which implies that each point x(t) is either normal or abnormal.
Assumption 1. if we denote by (G))sisM.+M. the list of all the activations T and as, the assumption is:
E G14 +0 i is [t,t = 0.
Assumption 2. The observed data & (the time series) is a uniform subsampling of a noisy version of the signal x: ÿ = =
Assumption 3. For the anomaly detection problem, we will assume that max(ka,) is significantly lower than min(ki,,, which means that anomalies are rore atoms.
Remark 2.
Assumption 1 implies that all the atoms start and end at zero. This will be crucial for our method as we will transform the signal into curue on which we will look for loops. The assumption ensures that each pattern corresponds to at least one loop.
Assumption 2 corresponds to the situation where a quantily assumed to vory continouussy is mea- sured at regular intervals, with noise corresponding to errors or perturbations. Note that the only assumption we will make on the noise is that ||ε||>< is small compored to the variations of the signal. Thus, it could represent small variations each occurvence of an atom, of noise due to the data acquisition process. Moreover, introducing also makes it possible to study the problem without the disjoint supports assumplãon as long as the overlap belween supports causes a small enough change in the infinity norm of x.
Assumplion corvesponds to the specificity of the anomaly delection problem (compured, for example, to the pattern detection problem).
Our model is illustrated on Figure 1 All the atoms start and end at zero and have disjoint supports. The green and red ones each occur ten times: they are the normal atoms. The blue one occurs twice, the orange and purple
each occur once. Note that atoms can have significantly different lengths.
Figure 2 show two example of time scries that fit our model, from real-world datascts included in the TSB- CAD suite. The first one comes from the ECG dataset, which is a standard electrocardiogram dataset with anomalies that represent ventricular premature contractions. This shows that our model relevant study structured activities that present repetitive behaviors over time where anomalics in the real-world manifest as anomalies on the signal (here: pathologies cause premature ventricular contractions that appear anomalies the ECG). The second comes from the NAB dataset, which is composed of labeled
5

---

Published in Transactions on Machine Learning Research (12/2024)
real-world and artificial time series including AWS server metrics, online advertisement clicking rates, real time traffic data, and collection of Twitter mentions of large publicly-traded companies.
Figure 2: Two example of real-world time series that fit our model, with anomalies in red. from the ECG dataset. Right: Time series from the NAB dataset. See Paparrizos al. (2022) for details the datasets.
Left: Time series
2.2 Topological data analysis background
In this subsection, we introduce the objects and results from TDA (mostly from Anai et al. (2200)) that will be used in the rest of the paper. See Boissonnat et al. (2018); Edelsbrunner Harer (2010): Chazal
Oudot 2008 Chazal et al. 2012 2014); Anai et al. (2020) for more complete background.
2.2.1 Filtrations and persistence modules
For the rest of this paper, let Rd be endowed with the Euclidean norm ||-
set X Rd is unordered tuple [zo,... Fnl of k+1 1 distinct elements of X. The elements To, ... Fg are called the verlices of a. If each verlex of simpleer is also node of a, then is called face of a. A simplicial compler K is set of simplices such that ony face of a simplex of K is a simplex of K.
Definition 2 (Simplicial complexes). A k-simpler
Definition 3 (Filtrations and interleavings). A filtration is a family V (Va)aeR+ of topological spaces or simplicial complezes such that S B Va Vg. For O, two filtrations V and W are called e-interleaved if for all 2 0, Va C Wate and W. C Vate- The interleaving pseudo-distance is then defined as d.(V, W) = inf(e 2 V and W are e-inlerleaved).
In our algorithm, the sets Va will be simplicial compleres in Rdd.
In the case of filtration of simplicial complexes finite set, only finite mumber of values of a correspond to strict inclusion in the filtration. We call filtration value of a simplex the lowest such that E Va.
Definition 4 (Persistence modules). Let K be a field. persistence module is a family V (Vo, (v )osss)) where the Vo K-vector spaces and the va are linear maps Va Va such that for all real numbers a vi = ld and va o of =
Definition 5 (Morphisms and interleavings persistence modules). Let 2 0. An e-morphism between two persistence modules V and W family of linear maps & (Øa Va W WateloERt such that the following diagrom commutes for all a S b
V
ltee
W att
W Wote

---

Published in Transactions on Machine Learning Research (12/2024)
If c 0 and if all the @a are isomorphisms, is called an isomorphism of persistence modules.
An e-interleaving between two persistence modules V and W is a pair (6. v) of morphisms such that the following diagroms commute for all a E R:
V 2+
a+t
Patt
Vla
Pute
10g
W a+t
W
W Wa+2e
a
The interleaving pseudo-distance is then defined as
4(4, W) = inf 2 OfVand Ware e-inlerleaved).
2.2.2 Persistent homology
Applying the (singular or simplicial) homology functor to a filtration and its inclusion maps gives a persistence module of homology groups (V.())))) for each dimension i E [0, d). Tf for all a S b, va is of finite rank, then V is called g-tame and can be decomposed into direct sum of interval modules θ ((oggo)))))) where the [arg). Qy) are left closed, right open intervals and each [ou,), is a basic persistence module that represent feature that appears at index ong) and disappears at index ay (see Chazal et al. (2012) for more details). In this case, the persistence diagram of V can be defined. The persistence diagram Diag(V) of i-dimensional persistent homology module is a multiset {()) such that a new homology class that appears in H.(Vang)) disappears HVa)) (arg) called its birth date and 0j its death date, if the component never dies, aj = =o)) We call aj 04() the persistence of the point. By convention and be able define the bottleneck distance, we include every points (a, a) to the diagram, with infinite multiplieity. O-dimensional homology classes connected components, and 1-dimensional classes are loops.
a,)},
Definition 6. The bottleneck distance between two persistence diagrams D and D' is defined as:
dD D')
inf TEN(D,D" (a.8)E
sup 11(,, ((ao
where T(D, D') is the set of bijections from D to D', and where 11(a,)) (a', (l laaa'll when 3 = 3' +o0.
Note that if two filtrations are e-interleaved, then the corresponding persistence modules are also e-interleaved. Moreover, the isometry theorem (Chazal et al. 2012] states that dVV, W) ds(Diag(V), Diag(W)) for q-tame modules V and W. We will implicitly use this in Section 1 as a bound on the interleaving distance between filtrations induces bound the bottleneck distance between persistence diagrams, which are the objects studied by algorithm.
2.2.3 DTM filtrations
Let X Rd, f
++ and p 2 be real mumber. For X and Rt, we define rz ra( as:
r2 (a)= - (a (
if < f()) otherwise
or (a) = for p = oo. Now, let us denote by Bx a) the closed ball B(x, (a)rr (by convention, ball is empty its radius is -c0). We can now define the weighted Čech filtration as union of growing balls.

---

Published in Transactions on Machine Learning Research (12/2024)
Definition 7. With the above notations, the weighted Cech filtration with parameters (X. Cech[X, f.p). is defined by:
S. U (,( xEX
Let (CCech(X, f.p) = (N((Ceh[[X, f. fPla))a2 denote the nerve of the above cover of X by closed Euclidean balls, i.c. the filtration of simplicial complexes whose (i - -isiplliees (with - 1 I d) are defined by
[......,,.]]] E JCCecc((X,..Ilaa
n By (1g. #0.
The persistent nerve theorem (Chazal & Oudot (2008), Lemma 3.4) states that the persistence (singular) homology module associated the weighted Čech filtration is isomorphic to the persistence (simplicial) homology module associated its nerve. The latter is computable in practice (Edelsbrunner & Harer
2010 Boissonnat et al. 2018
Definition 8. With the above notations, the weighted Victoris- Rips filtration with parometers f.P).)). Rips[X, is the flag complex of [CCCch(XX f,p), i.c. the filtered simplicial complex such that each vertex (or 0-simplex) E X has filtration value f(x), and such that for 2 S sisd+l
I11..... 1i....,, rz] E Rips[X, f.pla = v(. By(z,, (y(xx, + 0.
The Vietoris-Rips complex is easier to compute than the Čech complex practice because one only needs know the filtration values of the 0 and simplices to characterize the whole filtration. The following proposition gives this value in the case p 1, which will in this paper (see Anai al. (0200) for values when p or p 2o).
Proposition 1 Anai al. (200 ). Let x, X. The fillration value of [x] in Rips[X, is f(x), and the filtration value of [z, y) in Rips X, is:
max max(f(x), f())) | (w)))
f1 -Il < -
olherwise.
In the rest of this paper, the function f will always be a distance to measure function. Those functions were introduced in Anai et al. (2020) to make weighted filtrations robust to outlicrs.
Definition 9 (DTM). Let be a probability measure on TRd and let m E [0, Let 5p be the function defined on dRd by 8 (x) = inf {r ((B((xr)) > m). The distance to measure (DTM) a with parameter m is the function defined on Rd by:
1 T 82 (z)(.
d dp (x) (1)=(x==11
=
If X is finite subset of Rd, we denote by Mx the empirical measure on X. 1fm- Card[X]
9
with g N, then:
Vx E Rdd (x))
|a (N)
where (x) the tth nearest neighbor r. The DTM Čech and Vietoris-Rips filtrations for measure I and a parameter defined as the filtrations Cech X, du p) and Rips dy.m:

---

Published in Transactions on Machine Learning Research (12/2024)
2.3 Delay embeddings
A delay embedlding is way of transforming signal/time series into curve/point cloud of chosen dimension
d. Delay embeddlngg come from the field of dynamical systems, with strong theoretical guaranties (Takens.
1981 Sauer et al. 1991b.
Using the above notations, we define the delay embedding of a signal with dimension 2 and delay IR as the following curve in Rd:
Definition 10.
Sa, (Sar-1))ee0
[(s]t), rl..... sit + (d 10.01110000
The delay embedding of the time series with dimension 2 and delay & E N is the following point cloud in R
((S(i).Si fl....,
S (d 1)
(iisnn(d-- -as-n-(a11f (d-1)+
n n- (d n ()==11)) OSiSn-1-(d-1ff
8
n
Note that 7 - then S4,t C Sa.. In the rest of the paper, we fix d and f for time series and use d and T n for signals. When there is no ambiguity, we use S and á instead of Sa, and Sd,
In the following sections, we will use the embeddings X, Xa of the signals x, Xn Xa the embeddings X, X., Xa of the time series &, En. Sa. and their noisy versions (Y X + & being the notation for the embedding of the noisy signal =xx+ + e). Figure shows delay embedding of the time series from Figure Each colored loop on Figure 3 corresponds to the atom of the same color on Figure 1 The presence of noise makes loops corresponding to normal atoms (in green and red) thicker, as these atoms have more occurrences.
3 Method
In this section, we describe our algorithm for unsupervised anomaly detection. We start by explaining the main ideas behind the algorithm, and then describe its four steps: compute the DTM Rips filtration of subset of the delay embedding, identify the normal 1-cycles, extract them, and compute the anomaly scores. We use the above notations for all parameters and mathematical objects.
3.1 Motivation
The solution to the anomaly detection problem described in Section is binary vector of length each point yli] of the time series is either normal or abnormal. Our algorithm, like most anomaly detection algorithrns (Paparrizos et al., 2022; Schmidl et al.) 2022), works by giving an anomaly score to each { which should be high if the point is abnormal. binary answer can then be obtained by choosing a threshold over which points are considered abnormal. We do not give specific method to choose the threshold, as it depends on the application.
Our algorithm works by studying delay embedding Y of y to identify set of points as normal. Then, each point of is given an anomaly score which is its distance to the set of normal points. Finally, we get an anomaly score for g by averaging the scores of all points in & of which { is a coordinate.
The idea behind our algorithm that, we consider our model of signals from Scction 2 and if (d 1)7 is small enough, Assumption [ implies that the embedding of each occurrence of atom should starts and ends

---

Published in Transactions on Machine Learning Research (12/2024)
4
22
0
5
y 2
Figure 3: Delay embedding of the time series from Figure 1 (PCA in 3D), with d 10 and f 4. Colors
corrrespond to the colors atoms on Figure
at (O.....O) 0), so has least one loop. 1-dimensional persistent homology can be used to detect those loops in y homology classes of 1-cycles. Each point. from a normal alom n, will have king occurrences and each point from an abnormal atom a will have ka, occurrences, so if max(ka,) < S min(kn,) (see Assumption 3 then ddy-==d=ıj should be close to zero for normal points and strictly higher for abnormal points, which would make possible to discriminate the corresponding 1-cycles on the persistence diagram, as their birth date will be different. Our set of normal points is then the set of 1-cycles detected as normal.
Remark 3. One could argue that using 1-cycles is useless because points could be studied individually using their filtration value (i.e. the birth dates on the O-dimensional persistence diagram) which the opposite of a measure of the density of y around each point. This opproach would then be similar to the LOF algorilhm [Breunig el al., 2000). However, in praclice, dala do not fil our ideal model (there differences between occurrences of the same atoms non-disjoint supports) and there is way to be certain that max(ka.) < min(km,) so the filtration values can take a range of values and choosing threshold would be hard. Moreover, an abnormal alom with slow variations will give dense points in Y which would make the 0D approach or LOF fail. Considering 1D persistent homology and considering only cycles with a high persistence makes the choice of normal points easier by focusing on a few cycles (and thus a few birth dates) corresponding structured components of Y. It also makes possible to eliminate atoms with slow variations (because the corresponding cycles have low persistence).
be noise,
3.2 Algorithm description
The input of our algorithm is time series y. There are five parameters that will be described below:
d, f, Apointss q Oding-
10

---

Published in Transactions on Machine Learning Research (12/2024)
3.2.1 Delay embedding, subsampling and DTM Rips filtration
We start by choosing dimension d and delay 7 and computing the delay embedding Y Ya,+- As point clouds can be very large (they have n - (d 1)f points), computing persistent homology can be too long for the algorithm to be used in practice (O(n²) in the worst case for 1D persistent homology and cycle extraction [Boissonaa et al. 2018 Edelsbrunner et al.) 2002) To solve this problem, we choose number pposnts and take a subsample Y of Y made of Apoints points. In practice, we use greedy method: we start with a random point and, until we have Opoints points, add the furthest one to the set of already chosen points.
We then choose an integer q > and set the DTM parameter m to m Card(y) EJo, 1[ and compute the filtration = Rips[Y dpp... 1] with 1. We chose to always use p = because among the three possible values for which Anai et al. (2020) provides explicit formulas for the filtration values (1, 2, and oo), p = gives the strongest theoretical guaranlees (see section I and the highest value to edges, which can give more persistent cycles that are easier identify on the diagram.
Remark 4. Nole that the filtration values of points in Y are their original values from drva. m (subsampling does not change the fact that V is a filtration.. This is important to keep the density information from the whole point cloud when subsampling (otherwise, the effect of the number of occurvences of normal atoms would disappeor).
3.2.2 Identifying normal cycles
The second step consists in identifying normal 1-cycles by reading the persistence diagram, and extracting those cycles. Let Diag(V) be the persistence diagram corresponding to the filtration V. To identify normal cycles, we propose an algorithm that relies on the choice of two thresholds: the persistence threshold (we focus on the most persistent points, which describe important structures), and the birth date threshold (among those points, we consider those with a birth date above the cycle be abnormal).
To choose the persistence threshold, we sort the persistence of all points by decreasing order in list L, find the index such that Lii] L + 1] is maximal, and keep points corresponding to indices from 1 to i- Raiagg where Vdiaa is chosen parameter. See Algorithm for a formal description. We will use Rdiag 2 2 in practice, to keep at least three points and thus to be able to compare at least two differences in birth dates.
Algorithm Persistence Threshold (lists start at index 1)
Require: Diag(V), Adiag
I. - (d-b for (b,d) in Diag(V))
Sort L in decreasing order.
3: N + LL)
4: Diffs < [L[]] Lii + 1] for i 1
5: hsr <- argmax Diffs)
return Mec. + naaa + L Behe +n
We choose the birth date threshold as follows: we take the points that are above the persistence threshold and the point with minimal birth date, and sort their birth dates by increasing value in list L' (indices start at 1). Let iaiss be the index such that the birth date difference is maximal and êpere the index of the most persistent point. If ipers < idiff, then the birth date threshold is set to the birth date of L'[aarss (this is the typical case where we look for the highest difference). If iaiss = 1, we consider that all the persistent points are close from one another and are all normal cycles, so we set the threshold to too. If laiss < ipers: we set the threshold to the birth date [[ipers], assuming that the most persistent cycle is always normal, See Algorithm for a formal description.
11

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm 2 BirthDateThresholk (lists start at index 1)
Require: Diag(V) V), Addigg
1: - [(b,d) for (b, d) in [V)
2: (bmin: domin) + min(b for (6, d) L] for the lexicographic order.
p + PersisennceThreshodddDaaa///
mddaag)
L' +- [[bmin; do.....] [(b,d] d) for (b, in L if b2 p)
Sort L' using the lexicographic order.
Lirrth Ib for (b, d) in L']
7: pors + [d - for (b, d) in L']
8: N' +- -eeggthTT')
Diffspirth f bin [ + birth for i == 1 N'. -
10: Diffspers -- pars i + pers for 1. 1... -1]
11: hais + argmax (ifhh
12: ipers + argmax Diffs pers
13: idsss == 1 then
14: return +00
15: end if
16: if 1 << <iass ipers then
17: return Marrh Spers Lhann Bpeer +1
2
18: else
19: return lasee Lian [+tr++]]
20: end if
Finally, keep all points above the persistence threshold and whose birth dates below the birth date threshold.
If there are no 1-cycles on the diagram, we take an arbitrary "cycle" as normal. In this case, one should look for different parameters d and & to make the point cloud less dense.
Figure illustrates our algorithm applied to the time series from Figure I (with delay embedding from We used q 10, Vddiog = 2 and Ppoints 200. On this example, the birth date threshold is around 2.5, the two points in the upper left corner detected as normal (among the most persistent ones).
Fi Figure 3
3.2.3 Cycle extraction
The cycle extraction step consists computing a list of cycles Legetees (C1,..., .., Cneystes); ) each one representing the homology class of cycle identified normal at the previous step (a cycle stored as list of points).
In practice, we will compute persistent homology with coefficients in K = 2/22. In that case, the following matrix reduction algorithm from Edelsbrunner et al. (2022) can be used.
Let us write our finite filtered simplicial complex as V (where 0++1 is simplex), and let Ô be the N N matrix of the boundary operator (0., if o; face of aj), with columns C ....CG Cx. Let low(C;) be the greatest index such that Cуl -.. * (or if the column only has zeros). The matrix reduction algorithm is described in Algorithm cycle corresponding to point (I()).) on the persistence diagram is >N Cylilo,.
Vo C Vi C... C Vv such that V,+1 V, VoUt
3 The representative
12

---

Published in Transactions on Machine Learning Research (12/2024)
Persistence diagram
Birth date throshok
Ferkinacca Proskizdd
5
10
Death
4
3
2
1
Birth
Figure Left: persistence diagram of the DTM-filtration of the delay embedding from Figure with persistence and birth date thresholds in blue. Right: subsampling of the delay embedding with 200 points, and cycles detected normal (in green and red).
Algorithm MatrixReduction
Require: 0 (C1... CN.
1: for = 1.... N do
2: for = N - I,..., do
3: if low(C;) = low(C,) + 0: then
C +- G + C, m))
end if
end for end for 8: return θ
The green and red cycles on the point cloud Y from Figure 4 are the two normal cycles extracted with this mothod, corresponding to the two points evoked above (notice that we found the green and rod cycle from Figure
3.2.4 Anomaly scores
Once the list Laycles of normal cycles has been computed, an anomaly score given to each point x e Ý, which is its distance to Leyetes: d(r, Teyeles).
Finally, we get an anomaly score for y; by averaging the scores of all points in y which y, is a coordinate: 1)f) S S i)).
Score(y); + mean (dd(,, Teeyotes) max(0,í
One can choose threshold the anomaly score get a binary answer. Typically, one can chose to keep score only above certain quantile. In Section 5 we will compare algorithms using the AUC-ROC curve obtained by varying the threshold from 0 to in order not to be biased by arbitrary choice of threshold. We do not give specific method to choose the threshold, as it depends on the application (in Section we will compare algorithms using the AUC-ROC curve of each anomaly score nol. to be biased by an arbitrary choice of threshold). Figure 5 shows the results and ROC curve of our algorithm applied to the signal from Figure [ (with delay embodding from Figure 3 and normal cycles from Figure 4 The two cycles corresponding to the normal patterns have been extracted so those patterns have an anomaly score close
zero.
13

---

Published in Transactions on Machine Learning Research (12/2024)
TPR
0.2
0.0
0.8
10
FPR
0.4
02
500
1000
Figure Top left: signal from Figure with anomalies in red. Bottom: Anomaly score obtained with our algorithm (distance the cycles from Figure normalized). Top right: ROC curve (AUC 0.98).
4 Theoretical study
In this section, we recall stability thcorems for DTM filtrations, define probability mcasure on delay embeddings of signals and use it (and some additional assumptions) derive an upper bound on the interleaving distance between the filtration used in our algorithm (with discrete, noisy data with anomalies) and a filtration obtained in an ideal situation with a continuous signal without noise anomalies.
4.1 Overview of existing stability theorems for DTM filtrations
Here, we recall stability results from Anai et al. 2020). In this subsection, X and Y will denote any subsets of Rd. Let V[X, p] be either the DTM Cech or the DTM Vietoris-Rips filtration, and let V[X, d,. p] the associated persistence module.
Proposition 2 Anai et al. (020)) Prop. 3.1). If X is bounded, V[X, dumm, pl is q-tome.
Let W2 denote the Wasserstein distance with quadratic cost between js and v
/ Jxexxd I v/ ul|=dd(u,,))
W2(u,v) inf =ell(pe)) V
where 11 v) is the set of transport plans between a and v du denote the Hausdorff distance between sets, defined as
(see Santambrogio 2015 for more details). Let
de dx Y) max
sup Y), supd (x)dd(X.) (z
WEY
Prop. 4.3). Let px and by be two probability measures on Rdd with compact supports X and Y. Then
Proposition 3 Anai et al. 2020))
de dv(V(( [X, d my p), V(Y, m,y m We 2t, Y).
14

---

Published in Transactions on Machine Learning Research (12/2024)
The following result is specific to the case p (weaker results are given for p > 1 in Anai et al 2020
Proposition 4 (Anai et al. 2020), Prop. 4.4). Let μ be a probability measure on R with compact support
supp(μ) and let c(j,, m) = sup du.m-
supp(n)
If (upp(u) C X and supp(u) c yr, then V[X, dy 1] and V[Y, dp 11 d.(V dum:: 1), V[, 1]) S m)
m) (ou.m)--neee interleaved and thus
4.2 Upper bound on the interleaving distance between the real and ideal filtrations
The idea of our study is to define a filtration of Xn, which represents the ideal case of contimuous data without any anomaly nor noise, and to show that this filtration is close in terms of interleaving distance to the filtration V[Y, dup.mm constructed from the observed data Y = X + and associated empirical measure. As explained in Section a bound on the interlcaving distance between filtration also induces a bound on the interleaving distance between the associated persistence modules and on the bottleneck distance between the associated persistence diagrams, which we use in our algorithm identify normal cycles. So our algorithm should find cycles that approximate the true normal set Xn. We start by making additional assumptions and defining probability measure pxx, Xn, and use the DTM filtration V[Xn= d d our filtration of Xn to state our main result.
4.2.1 Assumption of the theorem and probability measure on curves
In this section, we add some assumption on our model from Section 2 and define probability measure on Rd whose support is the curve X Xd,r (or Xa) that is adapted to the anomaly detection problem, i.e. such that sections corresponding to anomalies have low probability.
We assume that the delay is small enough so that the curve always returns to 0 between two atoms, and at the beginning and end:
Assumption 4. Let (Gi)ssisM.+M, denote all the activations. We assume that:
1. Vi, Vt [0,
Vj i [t, Ig. (d - (1))) Sylt] = [ for all i and for all j (d 1)T and j 2 1 (d 1)T.
Note that small enough erists because of Assumption 1
Remark 5. This assumption ensures that each occurrence of an stom gives (at least) one loop in the delay embedding. It also ensures that each occurrence is complete, which is not mandatory but will make it simpler to compute the probability of each atom.
Let us now define the probability measure px. Here, X (H) denotes the pre-image of R under the function:
{1 1)r]
[0, 1 (d -
+ Rd + x[| = (x[1), + Th.... xit + (d-10 1)7]).
Definition 11. Let X denote the Lebesgue measure on R. μa is the Borel measure Rdd such that for any d-rectangle R = In .... Ia where the I, are open closed intervals:
XR))
(R) 1- (d 1)T
It clear that μx is a probability measure with support X.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Assumption 5. let N, (resp. A.) be the delay embedding of n, m. (resp. a, a.). We assume that the intersection of any pair of sets omong the N₂ \ {0} and A; \ (0} has null measure.
In this case, for any i, Px (0)) ln and px {0)) ka.la.
Remark 6.
Assumption makes sense the contert of anomaly detection as implies that except for set of wull measure, point x, is either normal or abnormal (i.e. normal and abnormal atoms connol coincide un interval).
If the atom lengths are equal, then the probability of each atom is proportional to its number of occureences.
If the signal constant on an interval, there will be a point with non zero probability in X. It is the case for O, which we consider to be part of the normal behavior.
Here, it can already be noticed that the algorithm could foil if an abnormal otom was too long.
The measure μx, is defined the same way starting from Xn (which is X without the anomalies).
4.2.2 Theorem statement
The aim of the section is to prove the following result:
Theorem 1. With the above notations and assumptions, if xn is contireuously differentiable, and with p = for DTM fitrations, we have:
dV ml, V[Xn: dax, ml) S (bn + |Elllo) vd m +
Ma Ka
+ V X 1lo
d m | 1o + V min(kn.)
with bn
n
Ma Notice that the sampling EMA la is the proportion the signal that is abnormal, so it can be assumed to be small in the context of anomaly detection. So with high sampling frequency low noise amplitude ||lloo, and if normal atoms occur many times, the bound should be small (after choosing m not too close to zero).
We divide the proof of this theorem in three steps:
Sampling step: Proposition bounds d, dv(V du ms p), V[X, dux.m. pl).
Noise step: Proposition bounds d, (V( d day mi p), V[X, d, ug mm pl).
Anomaly step: Proposition bounds d.(V[X [X, d m) v[X du ml)
We then conclude using the triangular inequality.
16

---

With the above notations and Published in Transactions on Machine Learning Research (12/2024)
Remark 7. We now make additional remark regarding the optional subsampling step in algorithm. Let Y be any finile point cloud in R2. This sleps consists in compuling the fillration on Y, which is subset of Y, but we still use the DTM function duy.m so Proposition 3 gives:
dV dp V(Y, m))) S 2d 2dnn(Y
In particular, one can take only one point for each occurrence of an atom while still using the information from the number of occurrences through dug.. (which would nol be the case we used due..m; leading to an important change in the filtration values that would make it hard to discriminate onomalies from normal atoms). This is very useful in practice as computing persistent homology on large datasets con be long.
Remark 8. Finally, we give a link between this section and Section 3. If m = n-(d-1) -- with max(kai) <
I min(km.) then for all normal point Y, dyz.m(y) I Vd(b,, + + So all normal points are dense, and for each abnormal point, al least q max(kin,) neighbors which are considered to compule their DTM do not correspond to the same point from a distinct occurrence. This does not guarantee that abnormal point have a lower density as a single point can oppear several times in one occurvence, or the variations can be very slow. So our algorithm can fail detect an anomaly (even with small ka.) if its variations are slow but still forms large enough 1-cyele to be considered significant. This could especially happen with large atom length la,, which reflects in our model we approrimate measure pxx such that px (x(AA \)) = la.la.
4.2.3 Sampling step
The next result states that if the signal is well-sampled (i.e. if is large) then there should be little difference between studying a continuous signal sampled version &. Recall that n-I- For simplicity, we assume that | E N, so Card(X) 1-(d-1) (points can be counted multiple times).
Proposition 5 (Stability for sampling). Let bn sup
(xx[t) - x(s]]).
|t -
assumptions we have:
dV
.8..dyy duy m. p). V[X, m.pm s Sbn (m= + +
Proof. From Proposition we get:
d, (V([ V[X, m. pl) S m +We ux) + +2 It is immediate from the definitions that du (8, X)= < bn Vnvd.
Let us now derive an upper bound for W2(Hx ux). We refer to Santambrogio 20015 Villani et al. (2009)
for and introduction to optimal transport. Let [.] denote the floor function, we define as
x X X₂
T:
+ X [[(n - 1)tl + 1]
So T(X(t) = 8[[(n +1]=+1]=] X
[n-1)c 1)d n-1
with t l(n-1)el
-
n-1
We have for any measurable bounded function f:
J f(w)du - s(w)ux(tu))
vE
1
Σ f(w)
())d(X)
ye
Σ f(v)
1 (d 1)T
VEX
17

---

Published in Transactions on Machine Learning Research (12/2024)
and
[(T()))dx(()> Σ [ ( ((1)du(())
x
DEX (I-+(W)
Σ [(0)xx((T-(x1)
yEX
Σ [(v) 1- (d VEX
So Fx = px o T and Mx is (deterministic) transport plan and thus:
(x( S V Jpeaee 1|u - 1l/2ddT(u v)
$
11u 11u- ((u=((()(ddx(())
b, Vd.
4.2.4
Noise step
The next result states that the construction is robust noisc.
Proposition 6 (Stability in the presence of noise). With the above notations and assumptions we have:
d(VlV, dpp. m .p, V[K dag m. pl) s ||ε||oc vd (m + 2T
3 to derive a Hausdorff distance term and a Wasserstein distance term. The fact that for all t. |1(X + 8) Xell s || vd immediately implics that du (8, Ý) < || vd. Let T be the function from to Y defined by (() = Y] so that Ny = Mx o T-1 and
Proof. As for the previous proof, we use Proposition
π = (Uxx & o 1-1 is a (deterministic) transport plan and thus:
/ 2dxxdd
Walmg <
||u w1| v1(=dT(u,v)
Σ - T(x)]1
(ard(X)
V
xcx
$ $1lellovVd
4.2.5 Anomaly step
We now fix p = 1 and use Proposition 4 to bound the change in interleaving distance between the filtrations obtained respectively with and without anomalics (and the associated DTMs). We note V[X, d mn) instead of V[X, dux.m: 1].
18

---

Published in Transactions on Machine Learning Research (12/2024)
Proposition 7 (Stability in the presence of anomalies). With the above notations and assumptions, if Xn is continuously differentiable:
Ma 2
Ka la + V V d ml ml|x||
di (V V(X, dux S 5m= >==Vvd|xall 00
min(kn.)
1=1
Proof. From Propositions 3
(which still applies in this case where supp(ux.)) = Xn C. X with X compact)
and
we have:
4, V m))) S dV(V(X, m, V(X, d duxmmm))
+ dv(V(X, dux, m) V[X, dux)ma))
m W2(ux, (xx)) + c(ux.:
Let us first give an upper bound on (o(xX,A,)) Let T; X + Xn be equal to the identity function on Xn and to the mull function on X Xn- Recall that = Xn Xx and that by assumption μux (X,, nX \0) = Also notice that µ = μxx, on Xn \0.
For any measurable bounded function f we have:
J (((()))dxx(()= f [(T(=))dpx(()+ + J [(T(=))d(xx())
xa,0
=f xavo
f(0)x(() Xxa1
f(0)dpx(x)
.S [x,10 f(x)dux. +00)xxxXXX000 + (Xa))x(Xa))) (0)
Mn
Ma
-Sx xx,1 ((x)dux. (x) S(0) 1
Σ
kin In;
Σ
kindln
Ma +(0)
la
=/ x
f(x)dux,.( (x)+ +000)x
((x)dpx.(())
The fourth equality comes from the fact that Nu kn. and EMa ka,la, are respectively the amount of time taken by normal and abnormal atoms (the rest of the time is spent at 0), so px 1- -. knd EM, ka, la, and (X \ 0) = Ma la,la, The fifth equality comes from the fact that when we use PX.: replace all the abnormal atoms with 0, pxx, (0) AMa knglnn
19

---

Published in Transactions on Machine Learning Research (12/2024)
The above calculation implies that μ.x. px OT and (ux, Mx TT is (deterministic) transport
plan and thus:
3dx3d |/u d112dd((u,))
J |/u ((uu)lduuxx))
|/ul|edux(u)
1 V d xa Bootix (Xa)
Mr
S Val|xallo
Σ
kacla la
where the fourth incquality comes from the fact that for all u = (#I, Ua) E Xa we have: Vi, S X Kallo
Let us now compute an upper bound on c(px,, m). Let t,s E [0, - (d - 1)7]. As xn is continuously diffcrentiable we have:
xn + Xn|s ir]l S dlt - =|² | [|,[(] - X [+]|
Let EjO, 1[- We will compute upper bound on 5pxm.. (see Definition 9 for the definition). For all 2 0 have:
It s-
||,n Xn[s]| S
so, as there are at least min(kn.) occurrences each atom Xn
min
px, (B(X)(t)))
Vdllx//lo
and thus:
uv /vd|xx /x
(B( >
r min(kin,)
lddllxll and: min(kn,) )
So we have 8px, (Xa(t)) s
V [ m
duxmmm m (Xalt))
52 ix (X dt)
d ml mm|xaallo
S V 3 min(kin;)
Note that Proposition 4 enabled us to replace (X, with c(xx,, using only Proposition The latter can be equal to Vd /d/x some cases, whereas the former has a factor min(kn,) that assumed to be small in our anomaly detection problem.
m) in the upper bound (compared
20

---

Published in Transactions on Machine Learning Research (12/2024)
Indicos
Anomaly
Several normal aloms
Repeating anomalies
type
20
Punctual
21 40
Sequential
41 60
Punctual
61 80
Sequential
81 100
Sequential
V
101 120
Both
Table 2: Characteristics of each part of the synthetic datasets.
5
Experimental setup
This section describes the datasets and anomaly detection methods we will use to test our algorithm in Section f
5.1 Synthetic dataset
We generated 120 time series following the model described in Section 2 Each atom is generated specifying random length, choosing a random integer N, computing N points on a Gaussian random walk starting at zero, and interpolating them with cubic splines to get an atom of the desired length, which then multiplied by a random amplitude factor between 0.5 and Atoms length set for punctual anomalics and can take values between 150 and 400 for normal atoms and sequential anomalies. N is set to for punctual anomalies and can take values between and 15 for normal atoms and sequential anomalies. For each time series, each normal atom has at most 15 occurrences, and at least 7 more occurrences than the most frequent anomaly: at least 8 when anomalies do not repeat, and 10 when they can have several occurrences (up to 3). Time series have lengths between 1964 and 13234. The dataset can be found at https://gitth: com/ foreeetttttooo--ooeeeeeeeeoeeeee
Alex- Broo----/A-persisteeme
wttprriiddddaaolla-dddeeeettetee deteetllldetetioon-- in seineesseriss
The dataset is divided in six equal parts, depending on the anomaly type of the time series (punctual sequential), the presence absence of multiple normal atoms and the possibility for anomalies to have several occurrences (two threc). Table 2 shows the characteristies of each part.
5.2 Real-world datasets and methods from TSB-UAD
Our real-world datasets are the 18 public datasets provided by the TSB-UAD benehmark suite (Paparrizos ct al. 2022), for a total of 1980 univariate time series with labelod anomalies. Table 3 shows the names, sizes (i.e. number of time series), average lengths and data types of 18 datasets.
For each time series, compute the area under the ROC curve (AUC-ROC) obtained by looking at all the possible thresholds on the anomaly score. The same method is applicd to 13 anomaly detection algorithms
[Liu et al. 2008 Breunig el. al.) 2000 Goldstein & Dengel 2012 Yeh et al. 2018 Boniol el. al.) 2021
Aggarwal & Aggarwal 2017
Sakurada & Yairi 2014] Malhotra et al. 2015
Li et al. 2007 Munir et al, Lu al. (0222 in PPaparrizos et al. (2022). Table provides succinct
2018 Schölkopf et al. 1999
description of the methods. Using the AUC-ROC, the evaluation does not depend on the choice of a
threshold for each algorithm.
The datasets and the implementations of the 13 methods be found
6 Results
In this section, we start by showing the results our the benchmark on real-world datasets. Then, we use the synthetic dataset to study the influence of our five parameters and of noise on the performance and computation time of our algorithm.
21

---

Published in Transactions on Machine Learning Research (12/2024)
Name
Size
Average lengths
Data type
Dodgers
1
50400.0
Freeway traffic
ECG
53
230351.9
Electrocardiogram
IOPS
58
102119.2
Performance indicators for machines
MGAB
10
100000.0
Differential equations (used for biological models)
NAB
58
6301.7
Server metries and internet traflic
NASA-MSL
27
2730.7
Spacecraft telemetry
NASA-SMAP
54
8066.0
Spacecraft telemetry
Sensorscope
23
27038.4
Environmental data
YAHOO
367
1561.2
Metries on Yahoo services
KDD21
250
77415.06
Composite dataset
Daphnet
45
21760.0
Acceleration sensors Parkison's is disease patients
GHL
126
200001.0
Metrics on Gasoil reservoirs
Genesis
6
16220.0
Industrial time series
MITDB
32
650000.0
Fleetrocardiogram
OPP
465
31616.9
Motion sensors on humans
Occupancy
10
5725.8
Environmental data
SMD
281
25562.3
Server metrics
SVDB
115
230400.0
Electrocardiogram
Table 3: Characteristios of the real-world datasets from TSB-UAD.
Method
Unsupervised
Delay embedding
Description
TDA
Our method: TDA to find normal L-cyeles
[oorest] 1
Liu et sl.
2008
Random forest on time seties to find outliers
|Forest Liu et al.
2108
Randon Jorest on delay embesdiig to lind outliers
LOI [Bronnig
(2000
Outlier score based local density
HBOS Goldstein
Dengel
20012
Outlier score bused bistogranss
MP Voch ot ml.
2018
5
X
Distance betaoon closest subseqqunne anomuly som
DAMP [Lu et al.
2022
X
A versson of the Matrix Profile designed to better handle mulsiple anomalies Chustering to fudd normal subaeqeences
NORMA Boniol et al 20221
PCA Aggarwal Aucarwal
2017
PCA to define normal lyperplane
AE & Yairi 2014
Reconstruction
auommly score, based deep loarning
LSTM Malhotra et al 2015
Prediction eroor as anomaly score, based on deep learning
POLY et sl. (2077
x
Prediction error as anomaly soore, besed ou polynomial interpolation
CNN Munir aL (21188
Prodiction error as anomaaly score, besed deep learning
OCSVM Schilkopl
1999
SVM to find nornal points on delay rubeeding
Table 4: Overview of the anomaly detection methods used in our benchmark. The "Delay embedding" column indicates if the methods uses delay embedding not.
6.1 Benchmark on real-world data
Here, we show the results of our algorithm on the TSB-UAD benchmark described in Section 5.2 The parameters of our algorithm are chosen the same way for all time series. We estimate a period L for the time series using the first maximum of the autocorrelation function (we used the find length function from TSB-UAD, which was used for all other methods using a delay embedding). We empirically chose = 6 (in practice, if f is too small, the embodding will stay close the line spanned by (I...., 1) and it will be harder to detect cycles). In Perea & Harer (2015) Perea and Harer show that in the case of trigonometric functions, df should be a multiple of the period to maximize persistence in 1D homology. With this in mind. we empirically set d = max(40, min(120, [)). We chose _ following the intuition from Section 3.1 as this value would approximate the mumber of normal occurrences in the case where there is one normal atom. Finally, we use Nldiog = 2 and Rpoints = 400.
The algorithm was implemented in Python. The DTM filtration was computed with the GUHDI li- brary (Maria et al. 2014). The cycle extraction algorithm was implemented with dionysus more specif-
httpe://ppp.orr/ppsjs////ssssss
22

---

Published in Transactions on Machine Learning Research (12/2024)
TDA
IForest
1orest
LOF
MP
PCA
NORMA
HBOS
POLY
OCSVM
AE
CNN
LSTM
DAMP
Dodgers
0.79
0.79
0.61
0.54
0.52
0.77
0.79
0.3
0.69
0.64
0.73
0.68
0,39
0.62
EOG
0.88
0.75
0.61
0.56
0.58
0.71
0.95
0.68
0.70
0.64
0.73
0.52
0,54
0.72
IOPS
0.82
0.54
0.78
0.50
0.72
0.74
0.76
0.64
0.68
0.71
0.63
0.61
0,61
0.50
MGAB
0.58
0.57
0.58
0.96
0.91
0.54
0.55
0.54
0.51
0.52
0.71
0.58
0.56
U.55
NAB
0.76
0.45
0.56
0.48
0.49
0.69
0.58
0.68
0.75
0.61
0.54
0.52
0.50
0.54
NASA-MSL
0.61
0.57
0.69
0.52
0.52
0.75
0.55
0.77
0.81
0.61
0.70
0.57
0.57
0.67
NASA-SMAP
0.83
0.68
0.68
0.80
0.77
0.65
0.68
0.64
0.77
SenpotScope
0.52
0.56
0.56
0.55
0.50
0.54
0.59
0.56
0.51
0.52
0.53
0.56
YAHOO
0.64
0.62
0.81
0.86
0.86
0.57
0.92
0.37
0.7G
0.50
0.79
0.96
0.94
0.78
KDD21
0.75
0.65
0.57
0.78
0.90
0.58
0.88
0.60
0,58
0.60
0.79
0.71
0.66
0.76
Duphnet
0.70
0.74
0.68
0.78
01.44
0.69
0.46
0.69
0.77
0.45
0.44
0.47
0.44
0.50
GHI
0.86
0.94
0.94
0.54
0.42
0.91
0.64
0.92
0.7G
0.45
0.63
0.47
0.47
0.53
Genesis
0.84
0.78
0.66
0.68
0.35
0.85
0.6
0.59
0.87
0.70
0.72
0.73
0.53
0.71
MITDB
0.71
0.70
0.61
0.61
0.69
0.67
0.86
0.70
0.68
0.65
0.80
0.58
0.51
0.66
OPP
0.48
0.52
01.45
0.82
0.52
0.65
0.54
0.38
0.70
0.47
0.57
0.65
Occupancy
0.53
0.78
0.53
0.32
0.53
0.80
0.66
0.79
0.71
0.53
SMD
0.77
0.85
0.73
0.69
0.51
0.80
0.61
0.77
0.87
0.61
0.61
0.58
0.57
SVDB
0.77
0.72
0.58
0.59
0.74
0.68
0.92
0.71
0.67
0.68
0.79
0.58
0.55
0.70
Table 5: Average AUC-ROC on each dataset. Results for methods other than TDA come from Paparrizos
ct al. (2022).
com/Alex-B-44 waarrcchh-frruuuuuuuueue atwprriiaddaaoolllyeeeeetttaaaaa -ime-----iseeee----ieeees----- Results for the other methods come from Paparrizos et al. (2022) except for DAMP, for which we used the implemen- tation from TSB-UAD.
ically with a modified version of cyclonysus The code can be found at howptatt--oooooooo-bbeeeeeee
Table shows the average AUC-ROC obtained on each dataset with our method (TDA) with the above parameters, and the results of the TSB-UAD benchmark (Paparrizos et al. 2022).. Figure @ shows the critical diagrams comparing the average rank of each method using the Friedman test followed by the Wilcoxon or Nemenyi test with a = 0.05, as described in Demšar (2006).
These results show that our method is competitive with the state-of-the-art in anomaly detection on 18 standard datasets. It has the best score on 4 of them, the best average rank (though the difference with the best methods is not significant as shown on Figure 6), and it is in the top 5 on 13 datasets. We found three reasons to cxplain what can make our algorithm perform well or not. First, our algorithm the problem described in Section _ which makes it appropriate for structured data with repetitive patterns but datasets can differ from our model in several ways: the absence of a clear normal behavior, a trend, or a lack of continuity (for example binary time series or time series with very fast variations) or too much noise can lead to a delay embedding with no relevant normal cycles to detect. Anomalies can also have a nature that our algorithm cannot detect, such as a longer pause between two atoms. The second reason is the choice of parameters. Even though our heuristics to choose the parameters seem relevant (see Sections 6.2 and b. it is still not optimal to have the same rule to choose parameters for datasets with different types of data, lengths, sampling rates... The delay embedding parameters d and should not be too low else the curve will not have enough space to form persistent cycles, but if they are too high points of the delay embedding will represent different atoms and the structure will be higher to detect. Moreover, if di is significantly larger than the length of an anomaly, there will be false positive because the algorithm will detect too many indices as abnormal. We believe that q and Baiag have less influence on performance (sce Scctions 6.2 and 6.3). The third reason is the quality the subsampling Y. If the time series short, or if it. has many repetitive patterns, then 400 points can be enough to represent the whole point cloud, but many time series have more than 100000 points so if they have numerous and/o or long atoms then it is not enough and the distance between points will be too low for cycles to persist (this is studied in more details in Section 4
designed for
htttp:://gichub..co////////
23

---

Published in Transactions on Machine Learning Research (12/2024)
14
13
12
11
10
9
8
7
6
5
4
3
2
1
LSTM
10.3889
TDA
OCSVM
10.0556
5,4444
NORMA
MP
9.3889
5,8889
POLY
LOF
8.9722
6.0278
AE
CNN
8.9722
6.1944
FForest
DAMP
8.0278
6.4167
PCA
IForest1
HBOS
12
11
10
5
4
3
2
LSTM
10.3889
5,0000
TDA
OCSVM
10.0556
5,4444
NORMA
MP
9.3889
5,8889
POLY
LOF
AE
CNN
8.9722
6.1944
IForest
DAMP
8.0278
6.41667
PCA
IForest1
7.4167
6.8056
HBOS
Figure 6: Critical diagrams for a = 0.05. Top: Friedman test + Wilcoxon test. Bottom: Friedman test +
Nemenyi test.
6.2 Influence of the embedding dimension and delay
Here, study the influence of the delay embedding parameters d and f by looking at the performance of our algorithm on our synthetic dataset with different pairs of parameters (d, f), while the other parameters are fixed. Figure 7 is heat map that shows the average AUC-ROC on the whole dataset when d varies
between 3 and 70 and f varies between and 11. We fixed Πpoints = 100 and Ndiag 2. We set = 1 where L found using the autocorrelation function, as in Section
On Figure there is one zone where the AUC-ROC is above 0.81 and the AUC-ROC decreases as parameters go away from this zone (below above), going to the 0.78 0.81 zone then to the 0.75 0.78 zone... until reaching 0.6 at the top right and bottom left corners. The shape of the zones AUC > 0.81, AUC > 0.78, and AUC 2 0.75 and of their fronticrs suggest that the best scores are obtained when the product df is constant. This product represent the time window represented by each point of the delay embedding. The window should be large enough to capture complex patterns but the window should not cover several atoms. In our dataset, atom lengths can have random values between 50 and 400. Figure 7 suggests that di should be approximately between 40 and 80. This empirically confirms the intuition from Section 5 and Perea & Harer (2015) that the product dł should be of the order of the atom lengths. Moreover, an AUC-ROC above 0.84 is never reached with d above 30 below 10, with & above 8 below 2. This indicates that each parameter should not take extreme values. Indeed, for given value of the product df, if f is too small then the delay embedding will be concentrated around the line = x2 points on the embedding will not represent the local variations that constitue the shape of the atoms.
and if it is too high then
6.3 Influence of the number of neighbors and points on the diagram
Here, we study the parameters q, which has an influence on the filtration values and thus on the persistence diagram, and Datagg which influences the way we read the persistence diagram. We look at the performance
24

---

Published in Transactions on Machine Learning Research (12/2024)
0.87
70
0.84
60
0.81
50
0.78
AUC-ROC
0.75
40
0.72
30
0.69
20
0.66
0.63
10
0.60
2
4
8
10
2
Figure 7: Heat map representing the average AUC-ROC on the whole dataset with different values of d and f.
of algorithm our synthetic dataset with different pairs of parameters (g, (g,niig while the other parameters are fixed. Figure S shows the average AUC-ROC the whole dataset when varies between and 140 and Vddin varies between 2 and 16 (as explained in 3.2.2 always set Radnn 2 2). We fixed Rpoints = 100, d= 15 and =
On Figure
we can see zones of constant AUC-ROC separated by almost horizontal lines, except for where the zone AUC 0.92 gets thinner as nading decreases. Moreover, the AUC-ROC significantly decreases when g gets lower than 20. This suggests that the algorithm is robust to changes of q and Ndiing except for very low values of (the proposed heuristic makes 9 proportional to avoid this situation), and that setting Rataag little higher than 2 can make it casier to reach optimal performance, but considering more cycles can make it harder to find the right birth date threshold.
S Fiding
6.4 Computation time and influence of the subsampling parameter
A nice property of our method is the possibility of computing persistent homology subset of the point cloud while keeping density information about the whole point cloud in the filtration. This makes the complexity of the algorithm go from 0(n3) (Edelsbrunner et al. 2002) to O(n + n²),, homology is computed on a point cloud of size Nlpointa, but the distance matrix of the full points cloud must be computed. Figure 9 shows the computation time when Npoints varies from 50 to 600 (on average on the 20 first time scries of the dataset),, on normal and logarithmic scale (to empirically confirm the theoretical complexity), along with the AUC-ROC (to study the compromise between computation time and performance). We set d 15, & 15, 50 and Ddding 2.
persistent
25

---

Published in Transactions on Machine Learning Research (12/2024)
0.92
140
0.88
120
0.84
100
0.80
80
0.76
60
0.72
40
0.68
20
0.64
2
4
6
8
10
12
14
16
n diag
Figure 8: Heat map representing the average AUC-ROC on the whole dataset with different values of q and
Rdiag
11A Mastofroiie Peroo
100
Mastorotta POLT HBCS
0.90
300
0.55
0.5
4,p0000
8,poires
Figure Left: computation time (in seconds) as function of Npointa. Middle: computation time a function of poontss logarithmic scale. Right: AUC-ROC function of Npoints- All quantities averaged over 20 time scries.
On Figure g it appears that the AUC-ROC stops increasing after Npoints 200, value above 0.95. Computing persistent homology without subsampling (i.c. on thousands of points) would take hours for each time series, but these examples show that performance can be almost optimal for values of Apoints significantly smaller than n (here, of the order of 10 times smaller, which makes computation about 1000 times faster). This study, and the fact that our algorithm performed well with nooitt 400 on time scries with lengths above 100000 our benchmark from Section 6.1 indicate that the algorithm has certain scalability with points increase slower than
26

---

Published in Transactions on Machine Learning Research (12/2024)
0.9
TDA
0.8
LOF
MatrixProfile
AUC ROC
PCA
0.7
DAMP
IForest
POLY
0.6
HBOS
0.5
0.0
0.2
0.4
0.6
0.8
1.
Noise ratio
Figure 10: Average AUC-ROC of each algorithm on the whole synthetic dataset, when the noise ratio of the centered Gaussian noise varies between 0 and 1.
6.5 Robustness to noise and benchmark on synthetic data
Here, we study the robustness of our algorithm to noise, and compare to the unsupervised methods from the benchmark Section 5 whose code is publicly available, and DAMP (Lu al.) 2022). For cach signal = x + E, we define the noise ratio as Var[x] (the inverse of the signal-to-noise ratio). Figure 10 shows the average AUC-ROC of each algorithm on the whole synthelic dataset, where centered Gaussian noise is added to each time series, with a noise ratio between 0 and 1. Note that the real benchmark is in Section 6.1 we only make comparisons here to gain insights our algorithm. It should be noted that since the synthetic data are generated according to the exact model used by our method, the comparison biased.
Var(e)
Figure 10 shows that our algorithm clearly outperforms all the other unsupervised methods up a noise ratio of 30%, and stays in the top performers for higher noise ratios (it seems that the AUC-ROC of about detected, which would explain the fact that it
0.7 corresponds to points where only easy anomalies can be reached by all the algorithms, even with a lot of noise). When looking into more details at our study synthetic data, it appears that our algorithm usually performs better than the others when there are multiple normal atoms or repeating anomalies. However, LOF can outperform in the case of punctual anomalies, especially when the normal behavior complex (several atoms or a lot of noise). Also note that the significant docline performance of the Matrix Profile and DAMP in the presence noise can be explained by the fact that they use z-normalized Euclidean distance, which can amplify the noise when looking at sequences between atoms those sequences detected anomalies and even hide other anomalies.
Our method gets an AUC-ROC above 0.8 for noise ratios up to approximately 20%. Too much noise can fill the loops so the main cycles are less persistent and thus more difficult to identify on the persistence diagram. All the other methods except the Matrix Profile and DAMP are very robust noise. However, would seem more relevant to study those methods on data for which they perform very well see how much noise makes them fail.
27

---

Published in Transactions on Machine Learning Research (12/2024)
7 Conclusion
This article describes unsupervised anomaly detection algorithm based on ID persistent homology. We proposed model of lime series in which the anomaly detection problem is well defined, which enabled us to create our method and to derive mathematical properties of the method. The algorithm empirically proved to be competitive to statc-of-tho-art anomaly detection methods on different real-world datasets. time/performance compromise that enabled us to significantly decrease computation time. Future research could improve compromise by using faster ways of extracting cycles finding sparse versions of the filtrations. Another research perspective would be adapt the algorithm to more general models of time series, for example to deal with the presence of linear trend, or with multivariate time series.
The subsampling step induces
References
Charu C Aggarwal and Charu C Aggarwal. An infroduction to outlier analysis. Springer, 2017.
Hirokazu Anai, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hiroya Inakoshi, Raphaël Tinarrage, and Yuhei Umeda. Dtm-based filtrations. In Topological Data Analysis: The Abel Symposium 2018, pp. 33-66.
Springer, 2020.
Sardar Ansari, Negar Farzaneh, Marlena Duda, Kelsey Horan, Hedvig B Andersson, Zachary D) Goldberger, Brahmajee K Nallamothu, and Kayvan Najarian. A review of automated methods for detection of my- ocardial ischemia and infarction using clettrocardiogran and electronic health records. IEEE reviews in bioeddicl engineering, 10:264 10:264-298, 2017.
Gregory Bell, Austin Lawson, Joshua Martin, James Rudzinski, and Clifford Smyth. Weighted persistent homology. Involve, Journal of Mathematics, 12(5))823 837, 2019.
Alexandre Bois, Brian Tervil, Albane Moreau, Aliénor VienneJuueaau, Damien Ricard, and Laurent Oudre. A topological data analysis-based method for gait signals with an application to the study of multiple sclerosis. Plos one, 17(5)ee0288475, 2022.
Jean-Danicl Boissonnat, Frédéric Chazal, and Marictte Yvinec. Geometric and topological inference, vol- ume 57. Cambridge University Press, 2018
Paul Boniol, Michele Linardi, Federico Roncallo, Themis Palpanas, Mohammed Meftah, and Emmanuel Remy. Unsupervised and scalable subsequence anomaly detection in large data series. The VLDB Journal, pp. 1-23, 2021.
Thomas Bonis, Frédéric Chazal, Bertrand Michel, and Wojciech Roise. Topological phase estimation method for reparameterized periodic functions. arXiv preprint ar Xio: 14390, 2022.
Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander. Lof: identifying density- local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pp. 93 104, 2000.
Mickaël Buchet, Fródéric Chazal, Steve Y Oudot, and Donald R Shechy. Efficient and robust persistent homology for measures. Computational Geometry, 58:70-96 96, 2016.
Frédéric Chazal and Bertrand Michel. An introduction to topological data analysis: fundamental and practical aspects for data scientists. Frontiers in artificial intelligence, 4:667963, 2021.
Frédéric Chazal and Steve Yann Oudot.. Towards persistence-based reconstruction in euclidean spaces. Proceedings of the twenty-fourlh anreall symposium on Computational geometry, pp. 232 241, 2008
Frédéric Chazal, David Cohen-Steince. and Quentin Mérigot. Geometric inference for probability measures. Foundations of Computational Mathematies, 11:733-751 2011.
28

---

Published in Transactions on Machine Learning Research (12/2024)
Frédéric Chazal, Vin De Silva, Mare Glisse, and Steve Oudot. The structure and stability of persistence modules. arXiv preprint arxi::1207. 120::2273774 21, 2012.
Frédéric Chazal, Vin De Silva, and Steve Oudot. Persistence stability for geometric complexes. Geometriae Dedicata, 173(1):193-211 2014.
Vin De Silva and Gunnar E Carlsson. Topological estimation using witness complexes. In PBG, pp. 157-166, 2004.
Janez Demšar. Statistical comparisons of classifiers over multiple data sets The Journal of Machine learning research, 7:1-30, 2006.
Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete & Computa- lional Geomelry, 28:511 533, 2002.
Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathematical Soc., 2010.
Saba Emrani, Thanos Gentimis, and Hamid Krim. Persistent homology of delay embeddings and its appli- cation to wheeze detection. IEEE Signal Processing Letters, 21(4):459 463, 2014.
Ximena Fernández, Eugenio Borghimi, Gabriel Mindlin, and Pablo Groisman. Intrinsic persistent homology via density-based metric learning, Journal of Mochine Learning Research, 24(75):1-44 2023.
Markus Goldstein and Andreas Dengel. Tiistgrram-bsse outlier score (hbos): A fast unsupervised anomaly detection algorithm. KI-2012: poster and demo track, 1:59 63, 2012.
Zhi Li, Hong Ma, and Yongbing Mei. A unifying method for outlier and change detection from data streams based on local polynomial fitting. In Advonces in Knowledge Discovery and Data Mining: 11th Pacific- Asia Conference, PAKDD 2007, Nanjing, China, May 22- 22-25, 2007. Proceedings 11, pp. 150-161. Springer, 2007.
Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou, Isolation forest. In 2008 eighth feee international conference on data mining, pp. 413 422. IEEE, 2008
Yue Lu, Renjie Wu, Abdullah Mueen, Maria A Zuluaga, and Famonn Keogh. Matrix profile xxiv: scaling time series anomaly detection to trillions of datapoints and ultra-fast arriving data streams. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1173-1182, 2022.
Pankaj Malhotra, Lovekesh Vig, Gautam Shroff, Puneet Agarwal, et al. Long short term memory networks for anomaly detection in time series. In Esann, volume 2015, pp. 89, 2015.
Clément Maria, Jean-Daniel Boissonnat, Marc Glisse, and Mariette Yvinec. The gudhi library: Simplicial complexes and persistent homology. In International congress on mathematical software, pp. 167-174. Springer, 2014.
Mohsin Munir, Shoaib Ahmed Siddiqui, Andreas Dengel, and Sheraz Ahmed. Deepant: A deep learning approach for unsupervised anomaly detection in time series. leee Access, 7:1991 2005, 2018.
John Paparrizos, Yuhao Kang, Paul Boniol, Rucy S Tsay, Themis Palpanas, and Michael J Franklin. Tsb-uad: an end-to-end benchmark suite for univariate time-series anomaly detection. Proceedings of the VLDB Endowment, 1698) 2022.
Vardan Papyan, Jeremias Sulam, and Michael Elad. Working locally thinking globally: Theoretical guaran- tees for convolutional sparse coding. IEEE Transactions on Signal Processing, 65(21):5687-5701 2017.
Jose A Perea and John Harer. Sliding windows and persistence: An application of topological methods signal analysis. Foundations of Computational Mathemalics, 15(3):799 838, 2015.
29

---

Published in Transactions on Machine Learning Research (12/2024)
Jose A Perea, Anastasia Deckard, Steve B Haase, and John Harer. Swipers: Sliding windows and 1- persistence scoring; discovering periodicity in gene expression time series data. BMC bioinformalics, 16 (1):1 12, 2015.
Mayu Sakurada and Takehisa Yairi. Anomaly detection using autoencoders with nonlinear dimensionality reduction. In Proceedings of the MLSDA 2014 2nd workshop machine learning for sensory data analysis, pp. 4- 11, 2014.
Filippo Santambrogio. Optimal transport for applicd mathematicians. Birküuser, NY, 55(58-633:94, 2015.
Tim Sauer, James A Yorke, and Martin Casdagli. Embedology. Journal of statistical Physics, 63(3)5579 616, 1991.
Scbastian Schmidl, Phillip Wenig, and Thorsten Papenbrock. Anomaly detection in time series: compre- hensive evaluation. Proceedings of the VLDB Endoument, 15(9):1779-13 1797, 2022.
Bernhard Schölkopf, Robert C Williamson, Alex Smola, John ShyworTaylor, and John Platt. Support vector method for novelty detection. Advances in neurol information processing systems, 12, 1999.
Floris Takens. Detecting strange attractors in turbulence. In Dynamical systems and turbulence, Warwick 1980, pp. 366 381. Springer, 1981.
Kohei Ueda, Yuichi Ike, and Kenji Yamanishi. Change detection with probabilistic models persistence diagrams. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 1191-1196. IEEE, 2022.
Cédric Villani al. Optimal transport: old and new, volume 338. Springer, 2009.
Mark Woike, Ali Abdul-Aziz, Aziz, and Michelle Clem. Structural health monitoring on turbine engines using microwave blade tip elcarance sensors. In Smart Sensor Phenomena, Technology, Networks, and Systems Integration 2014, volume 9062, pp. 167 180. SPIE, 2014.
Chin-Chia Michael Ych, Yan Zhu, Liudmila Ulanova, Nurjahan Begum, Yifci Ding, Hoang Anh Dau, Zachary Zimmerman, Diego Furtado Silva, Abdullah Mueen, and Eamonn Keogh. Time series joins, motifs, discords and shapelets: a unifying view that exploits the matrix profile. Data Mining and Knowledge Discovery, 32:83 123, 2018
30


Reviews:
[{"review_id": "PVEUCpoo8E", "reviewer": "Reviewer_PodD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The time series model is general and the assumptions are reasonable.\n\n2) They are able to use an anomaly detection method based on TDA which can deal with various types of anomalies in the dataset, from burst to spikes, repeated and non-repeated, as long as they are not too large a fraction of the total data points the time series array.\n\n3) They have theoretical results that guarantee that their algorithms identify approximately the \"right\" normal parts of a time series. For this they on techniques from Optimal Transport (under mild assumptions).\n\n4) The experimental results on many real data sets beat various other approaches (that include DNN based ones).\n\nWeaknesses:\n\n1) The paper is likely to be hard to follow for an average ML researcher. While the authors have tried to provide intuition, some of the mathematical background related to persistent homology could go in the appendix. I would believe highlighting the algorithm is perhaps more useful to the majority of the ML community interested in anomaly detection.\n\n2) A lot of the results depend on prior work (Anai et al., 2020) and in places it is not clear the differences in contributions of this paper vs (Anai et al., 2020). I have added a few points regarding this in the \"Requested Changes\" section below.\n\n\nReferences:\nAnai, Hirokazu, et al. \"DTM-based filtrations.\" Topological Data Analysis: The Abel Symposium 2018. Springer International Publishing, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Authors study time series anomaly detection using Topological Data Analysis (TDA). They provide an algorithm that can detect different types of anomalies and is based on loop detection in persistent homology. Their theorems, algorithms and techniques are applicable generally and require only mild assumptions. Furthermore, they run experiments on many synthetic and real data sets to show the effectiveness of their approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) Please clarify the main technical differences from (Anai et al., 2020). Many definitions and theorems of this paper rely on (Anai et al.,2020).\n\n2) Authors mentioned that (Anai et al., 2020) are able to perform changepoint detection for timeseries. Can the authors describe why one cannot use their method as a subroutine, perform a sliding window routine across the time series and call their subroutine to perhaps identify minimal intervals where the changepoint occurs. The proposed method is not efficient, however it would great if the authors could better highlight the subtle differences in changepoint detection and anomaly detection. \n\n3)  Related to point 2), it would be great if the authors can describe how their approach (either algorithmically or theoretically) different and better suited for anomaly detection.\n\n4) Can this algorithm be implemented in cases of sensor networks where the nodes have limited computational resources and the anomalies have to be flagged immediately?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LuLii9glou", "reviewer": "Reviewer_R1QX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nA new algorithm based on 1D persistent homology associate with theoretical analysis is proposed for analyzing anomaly detection problems. \n\nWeakness\n\n1. The problem setting considered in this paper is limited. e.g., it focuses on unsupervised anomaly detection in univariate time series, while it would be more interesting to consider more general cases, i.e., multivariate time series. In addition, the model established in the paper is not suitable for many types of data and there are many restrictive assumptions.\n\n2. The experiments do not fully demonstrate the effectiveness and efficiency of the proposed algorithm. It seems that many existing methods outperform the proposed method. Specifically, first, in Table 5, NORMA and POLY seem to have better prediction behavior than TDA. In particular, for the ECG dataset, NORMA has an AUC-ROC score of 0.95, while TDA has an AUC-ROC score of 0.88. This is a very unreasonable result because according to Section 2, ECG is a dataset that matches the model established in this paper, but TDA's results on this dataset are not as good as NORMA. The effectiveness of the proposed algorithm needs to be verified. Secondly, the paper points out that \"One advantage of our method is that persistent homology can be calculated on a subset of the point cloud while retaining the density information of the entire point cloud in filtering. This reduces the complexity of the algorithm from O(n^3) to O(n_points^3 + n^2)...\". Section 6.4 provides some discussion and illustrations in this direction, but this is not enough to prove the computational efficiency of the proposed method. It would be better to compare the computation time with state-of-the-art methods. Also, there are a lot of hyperparameters to choose from and I'm not sure it's easy to choose.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper describes an unsupervised anomaly detection algorithm based on 1D persistent homology. To be detailed, the authors first proposed a time series model that formally define the anomaly detection problems. Given this model, a new anomaly detection algorithm is proposed based on persistent homology, which relies on delay embeddings and the Vietories-Rips filtration. Theoretical analysis for the proposed method is established. Finally, the behavior of the proposed method is studied. Overall, the paper is well-written and the studied topic is interesting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. See weakness (2).\n\n2. Assumptions 1-3 in Section 2 need some discussion.\n\n3. What does \"uniform noisy subsampling\" mean in Assumption 2?\n\n4. The paper assumes that all the atoms start and end at zero. What if some atoms don't start and end at zero?\n\n5. At the beginning of Section 2.2.1, $|| . ||$ should be $|| \\cdot ||$.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tCcKNyRrzi", "reviewer": "Reviewer_Nnzu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "For my comments below I am relying on Wu and Keoghs\nA) Current Time Series Anomaly Detection Benchmarks are Flawed and are Creating the Illusion of Progress. IEEE Trans. Knowl. Data Eng. 35(3): 2421-2429 (2023)\nB)  Their frequent Linkined postings on datasets, which they archive here. https://www.dropbox.com/scl/fi/cwduv5idkwx9ci328nfpy/Problems-with-Time-Series-Anomaly-Detection.pdf?rlkey=d9mnqw4tuayyjsplu0u1t7ugg&st=bkj3i9wn&dl=0\nHowever, with my students, I have largely confirmed their claims.\n--\nMy main problem with your paperis that I don’t believe your experiments show the utility of your ideas, because..\n\n1)\tLook at SVDB. 56.5% of the data is anomalous!!!  This is a simple classification problem, it is not a TSAD problem.\n2)\tLook at YAHOO. The synthetic subset can be solved with one line of code, and the real subset has many false positives and false negatives in the ground thruth\n3)\tMITDB you can solve with fast parameter-free (and over 20 years old) time series discords, you don’t need a complex algorithm.\n4)\tDodgers has huge problems with its ground truth, it has many false negatives\n5)\tSensorScope has dozens of false negatives in the ground truth\n6)\tLook at Genesis.  There are long runs of 0,0,0,0,0,0,0,0,0,0,0,0,0,0,…   and some of these are anomalies and some are not.  It is really hard to believe that the ground truth is meaningful here, and I would be VERY suspicious of any algorithms that did well on this (without access to out of band data)\n7)\tWhat about IOPS?  Wu and Keogh show you can solve it with this single line of code plot(diff(IOPS(1:end,1))>10);       Again, you don’t need a complex algorithm\n8)\tWhat about GHL?    Again Wu shows you can solve it with one line of code       plot(zscore((LevcorrTempfaultseed199vars23(:,6)))>1.1)\nI think the problem is that you lean uncritically on Paparrizos et al. But he assembled these datasets with no real thought or introspection (other than trying to cripple the Matrix Profile /repeated anomalies) \n\n•\tThe best dataset you consider is the kdd21, where you do worse than the MP.\n•\tYou appear to do well on Dodgers, but look at slide 45 of [B], the ground truth here is better than random, but is clearly has LOTs of false positives.\n•\tYou appear to do well on MSL, but look at https://arxiv.org/pdf/2009.13807 fig 9. There are at least two false negatives in this single subset.\n•\tYou appear to do well in IOPS, but we can solve that with one line of code, how excited should we be?\n•\tEtc etc\n\nIn summary, your experiments do not offer forceful evidence that your algorithm is competitive with much simpler ideas like the MP or iForest. Maybe it is, but we cannot tell from these experiments. If you look at how kdd21 was created, it does seem that this is a very high quality datasets, and we should weight its evidence more, which I am inclined to do.\n\n\n\n\nThe discussion of “repeated anomalies.” is problematic.   Paparrizos and others like to pretend it is a problem for the Matrix Profile, but I think DAMP finally kills that.  However, “repeated anomalies.” Can greatly inflate an algorithms performance by overcounting success.\nSuppose you have one second video (30 fps) of Brad Pitt smiling, and you run an algorithms on it to classify the face. Can you say “we got 30 out of 30 correct!!”?  Clearly no, these are not independent, if you get any one correct, you will surely get all correct.   Repeated anomalies are the same. You can take credit for the first one you find, but after that you are just taking credit for the same thing.\n\nAlong those lines, you should compare to left-Matrix Profile (DAMP) not classic Matrix Profile if you are going to include the datasets (like ecg) that Paparrizos included to try to make his method better look good relative to the MP\n\nour fundamental idea is “Points in those cycles are considered as normal, and the algorithm can then assign an anomaly score to any point which is its distance to the normal set.”  It is similar to time series discords “Subsequences (cycles) close to other subsequences are considered as normal, and the algorithm can then assign an anomaly score to any subsequence which is its distance to nearest other Subsequence.”, it would be good to compare/contrast.\n\n\nIn table 5 you mention “ECG” dataset, that is a little vauge as there are many such datasets with that name.\nYou show that for MGAB, the Matrix profile is goodish, but not perfect (table 5), if you look at slide 65 of [B] that is surprising, as the Matrix Profile is perfect on MGAB", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce a new TSAD algorithm based on delay imbedding", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see experiments on meaningful datasets.\n\nSuch datasets exist, but they take a little more effort to find (the kdd21 is a good start).\n\n Most of the dataset you consider are either tiny, trivial or mislabeled.   Think about it, if 20% of the data is mislabeled, you cannot say \"we are 5% better than algorithm A!\"", "broader_impact_concerns": "no issues", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers recommend "leaning accept" while the third recommends "leaning reject".   One reviewer is concerned with the difference between the proposed approach and Anal et al. (2020), the reviewer didn't have further comments after the author's response.   Another reviewer was concerned with the datasets used, while the authors didn't add more datasets, they add one more existing method DAMP, which the reviewer seems satisfied and recommends "leaning accept."  

While the proposed method is competitive, not better than, with existing methods, their topological analysis approach is interesting, which could provide a different perspective to the community.
Decision: Accept (poster)