Time Series Subsequence Anomaly Detection via Graph Neural Networks
Authors: Weiqi Chen
Zhiqiang Zhou
Qingsong Wen
Liang Sun
Venue: Submitted to ICLR 2023 (2023)

Abstract: Time series subsequence anomaly detection is an important task in a large variety of real-world applications ranging from health monitoring to AIOps, and is challenging due to complicated underlying temporal dynamics and unpredictable anomalous patterns. Firstly, how to effectively learn the temporal dependency in time series remains a challenge. Secondly, diverse and complicated anomalous subsequences as well as the lack of labels make accurate detection difficult. For example, the popular subsequence anomaly detection algorithm---time series discord---fails to handle recurring anomalies. Thirdly, many existing algorithms require a proper subsequence length for effective detection, which is difficult or impossible in practice.  In this paper, we present a novel approach to subsequence anomaly detection which combines practical heuristics of time series discords and temporal relationships with deep neural networks. By performing length selection considering multi-scale information and incorporating prior knowledge using graph neural networks, our method can adaptively learn the appropriate subsequence length as well as integrated representations from both priors and raw data favorable to anomaly detection. In particular, our graph incorporates both semantic and temporal relationships between subsequences. The experimental results demonstrate the effectiveness of the proposed algorithm, which achieves superior performance on multiple time series anomaly benchmarks in comparison with state-of-the-art algorithms.

Under review as a conference paper at ICLR 2023
TIME SERIES SUBSEQUENCE ANOMALY DETECTION VIA GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Time series subsequence anomaly detection is an important task in large vari- cty of real-world applications ranging from health monitoring to AIOps, and is challenging due to complicated underlying temporal dynamics and unpredictable anomalous patterns. Firstly, how to effectively learn the temporal dependency in time series remains a challenge. Secondly, diverse and complicated anoma- lous subsequences as well as the lack of labels make accurate detection difficult. For example, the popular subsequence anomaly detection algorithm- discord-fails to handle recurring anomalies. Thirdly, many existing algorithms require a proper subsequence length for effective detection, which is difficult or impossible in practice. In this paper, present novel approach to subsequence anomaly detection which combines practical heuristics of time series discords and temporal relationships with deep neural networks. By performing length selec- tion considering multi-scale information and incorporating prior knowledge using graph neural networks, our method can adaptively learn the appropriate subse- quence length as well as integrated representations from both priors and raw data favorable to anomaly detection. In particular, our graph incorporates both seman- tic and temporal relationships between subsequences. The experimental results demonstrate the effectiveness of the proposed algorithm, which achieves supe- rior performance on multiple time series anomaly benchmarks in comparison with state-of-the-an the--artt algorithms. Codes and datasets are available online")
series
INTRODUCTION
Detecting anomalies in time series data has a large variety of practical applications, such as tracing patients' bio-signals for disease detection (Chauhan & Vigl 2015). monitoring operational data of
cloud infrastructure for malfunction location (Zhang et al. 2021). finding risks in IoT sensing time
series (Cook et al.] 2019), etc. It has received a great amount of research interests (Keogh et al.,
2005 Yankov et al.
2007 Boniol & Palpanas Shen et al.
2020 Lu et al. 2022).
The time series anomaly detection (TSAD) problem is commonly formulated locate anomalies at cach point of the time series (namely point-wise TSAD). However, this formulation fails in con- sidering temporal relationships of anomalous points as anomalies can go beyond occurring point by point but tend to exist consecutively over time interval in many real-world scenarios. For instance, some demand patterns from the power system change during holidays. Figure D shows a compari- son of point-wise anomalies and subsequence anomalies. In this paper, we investigate TSAD from a subsequence perspective by identifying anomalous patterns
time interval, which called time series subsequence anomaly detection. Generally speaking, a subsequence anomaly is sequence of observations that deviates considerably from some concept of normality. The somewhat "vague" definition itself also hints the challenges of the subsequence anomaly detection problem. Also, distinguishing feature of time series is temporal dependency. Thus, how to learn and utilize the tem- poral dependency for different time series data is key challenge in time series anomaly detection. Moreover, another key challenge in time series subsequence anomaly detection is how to determine the appropriate subsequence length, as illustrated in Figure 2 This problem becomes worse when there are multiple abnormal subsequences with different lengths in one series.
https::/ancnymous.. 4open. sci sciience/r//rappssa---

---

Under review as a conference paper at ICLR 2023
Nornal Sabsequance
Anonnalors Subroogamnce
my Auocaas WiLL Contert
An Illustration of Selecting Proper Length for Subsequence Anomaly Detection. An anomalous subsequence is inside the dark grey zone. If we directly detect anomalies using this length, the anomaly might not be found as it is very similar to normal subsequences. e.g., the green zone. Instead, it is better to select a longer window size (marked in light grey) in- cluding the anomaly with its context to high- light the anomalous pattern.
Figure 2:
Point-wise Anomalies (Top) versus Subse- quence Anomalies (Bottom). The top website traffic time series with anomalies labeled by red dots that might be caused by cyberattacks. The bottom is an insect's ac- tivity signal recorded with an EPG apparatus, where time intervals marked in grey subsequences exhibiting dif- ferent anomalous characteristics, including period length variation, spike, and temporal morphological change.
Figure I:
Early research on anomaly detection mainly relies on shallow representations Breunig et al. (2000); Schölkopf et al. ) : Tax & Duin (004)). Later, Deep-SVDD (Ruff et al. 2018) enhances the representation learning capability using neural networks. Recently, TSAD methods (Carmona al.)
2022 [hen et al. (020) based on Deep-SVDD are prevailing due to their excellent performance. They introduce a suitable neural architecture for modeling time series and detecting anomalies by computing the distance between target with its corresponding reference in latent representation space, where the reference represents normal patterns. The main issue that these deep learning- based methods are difficult to enforce assumptions of anomalies, and typically require large training datasets to learn accurate models. In contrast, time series discord (Keogh et al. 2005 Ych et al,, 2016 Nakamura et al. 2020 Lu et al. 2022) is another category of distance-based TSAD methods. Discords are subsequences that are maximally different from all others in the time series, where the difference is measured via z-normalized Euclidean distance. The most appealing merit of discords is that anomalies can be discovered by merely examining the test data without a training phase. In spite (or perhaps because) of their extremely simple assumptions, discords are competitive with deep learning methods. However, there are still several important limitations that prevent them from broader applications. First, they fail in detecting anomalous patterns recurring at least twice, as each occurrence will be the others' nearest neighbor. Second, they rely on an explicit distance measure (z-normalized Fuclidean distance), which cannot account for diversified anomalies flexibly, as some anomalous patterns might be slight in the data space. Details about the Deep-SVDD and discord algorithms are provided in Appendix B
Moreover, most existing methods utilize predefined window length to detect anomalies, which is difficult or impossible to tune in practice. Here we emphasize the importance of the appropriate window size which highlights the normal or anomalous pattern of subsequence. On the one hand, the duration of anomalies varies. For example, if we use a large window to detect spikes and dips, the anomalies might be "hidden" in the normal data. While for long-term anomaly, short window cannot depict the full picture of it. On the other hand, even if we have a prior anomaly length, is still necessary intelligently infer suitable length according data characteristics. To the best of our knowledge, none of the existing algorithms can detect anomalous subsequences with different lengths and characteristies intelligently. For more details of related work, an extensive literature review is provided in Appendix
In this paper, we devote resolve the aforementioned challenges in TSAD by fusing practical heuristics of time series discords with deep neural networks, and propose GraphSAD, a graph neu- ral network-bace baased subsequence anomaly detection approach. Specifically, we construct graphs in which nodes represent subsequences and edges encode the relationship between corresponding sub- sequences. A unique feature of our graph is that we consider both the pair-wise semantic and tem- poral relationships between subsequences. As result, the temporal dependency from time series is incorporated in graph and utilized in further detection. Besides, in order to intelligently learn subsequence length, we introduce multi-scale feature encoder generate representations of multi- scale subsequence length with a length selection strategy to select the proper length. The proposed algorithm GraphSAD can intelligently detect different anomalous subsequences, which greatly im-
2

---

Under review as a conference paper at ICLR 2023
proves its usages in practice. When evaluated on multiple TSAD benchmark datasets, GraphSAD consistently outperforms state-of-the the-art baselines.
PRELIMINARIES
2.1 NOTATIONS AND PROBLEM DEFINITION
A univariate time series of length T can be denoted as a (01, 22. ,r), where 2; is real- series of
valued observation at time step I. A subsequence æt, (Ix, Fe+1," 1.... +++ continuous observations from time series starting at time step /. with length L, where S I T L + 1. The problem of subsequence anomaly detection is to output the anomaly score s( for each subsequence which should be high for anomalous data and low for the normal. Then one can sort the scores in descending order to detect anomalies.
Using the sliding window strategy with stride subsequences X RNX, where is the number of subsequences and is the subsequence length. We denote the ë-th subsequence 2(1-1)r+1,1, length T. is set to be large enough to support detecting various anomalies, which can be typically determined based domain knowledge. For instance, I. can be four times of the period length for some periodic time series, c.g., the weather time series.
time series be split into ordered set of
X; E R We assume that the initial subsequence
Note that in most real-world applications, finding and labeling anomalies extremely time- consuming and expensive, while the labeled normal data are much easier to access. Hence, TSAD methods are usually trained with normal and unlabeled data which are commonly treated as normal data as we assume that most data are normal due to the rareness of anomalies.
2.2 GRAPH NEURAL NETWORKS
A, where V [N] == (1,.... J is the set of node indices, A E {0, 1J.NNN is the adjacency matrix with Aij denoting directed edge (i, j) exists and A, 0 otherwise, and E NxNx xx, is sparse tensor of edge attributes and de is the corresponding dimension. The set of adjacent neighbors of is notated as N₁ = (j E Al 1}. Let H E Nxd be node representations, in which the i-th row H, Rd is the vectorized representation attached to node A GNN takes the node representations H along with the graph 9 as input and returns updated node representations H' E R xd' using a message passing paradigm, i... H' GNN(G, H). The operations for each node performed by GNN used in this work are defined as follows:
Graph neural networks ( Wu et al. (021), GNN) operate on graph 9
Message and Aggregation:
H = Σ MLP (H E,,))
JEN.
(1)
Update:
H = MLP (H,; HN:)):
where MLP(-) stands for a certain multilayer perceptron network and [ denotes vector concate- nation. In the remaining part of this paper, treat GNN(.) multi-layer message-passingg GNN to avoid notational clutter.
3 METHODOLOGGIES
In this section, we describe GraphSAD, a graph neural network-basd based subsequence anomaly detection approach. Figure shows the proposed architecture. Once a time series is split into sub- sequences, we construct semantic and temporal graphs representing data priors. Then multi-scale feature encoder generates subsequence representations of multi-scale lengths and length selection mechanism selects proper subsequence length. Finally, taking subsequence representations and prior graphs as inputs, graph networks generate the final representations for anomaly detection.
3.1 ENCODING PRIORS AS GRAPHS
At the very beginning, we would like to incorporate informative heuristics of time series discords and temporal relationships into approach by encoding these priors graphs. Compared with
3

---

Under review as a conference paper at ICLR 2023
Tire Serie
Multi-Scale Feature Encoder
Length Selection Mochanism Langh Weigts W
Mufh Scale Representations
Subaeequerce
Spi
Represstiaaions
Z
Gmph Gonetration
H
Semeero Goach
2
Terpora Graph
meas
vaterre
mac
mn
Mulk Scale Feature Encoder
Pooling
Pooking
6-20 2
Length Selection
TCN
CNN
Anomaty Desection
Figure 4: Learning Subsequence Representations Using
Sulti-Scale Encoder and Length Selection Mcchanism.
Figure 3: An Overview of GraphSAD.
existing works, our method considers both the temporal information and distance information in the graph construction.
Semantic Graph. An attributed directed semantic graph is constructed to encode the nontriv- ial distance information between pair-wise subsequences, which can be described by 3-tuple ( (V, A (se), ,E E(se)), where = [N] is the set node indices representing a subsequence each, (5))) E (0 is the adjacency matrix, and edge attributes E(se) R. N XNxx, store the distance information between subsequences. We build the semantic graph following three princi- ples: (1) multiple distance measures should be considered to characterize semantic relationships from different perspectives, (2) distance information multi-scale length should be introduced, and (3) only informative neighbors of each node are reserved for the sparsity and purity of the graph.
We take the edge (j.i) )) (a directed edge from j to i) and the corresponding edge attribute E/( Rd as example to illustrate how to build the semantic graph. First, we derive multi-scale views of subsequences with maximum length L. Specifically, the multi-scale view of subsequence X; is defined as X; (X 2'A, p 0, 1,..., ,P). where X₃,I indicates the first observations of X; with increasing exponentially, P is the largest positive integer satisfying 2P A < L, and A is the length of an indivisible segment. We calculate Euclidean distance dis. and z-normalized Euclidean distance dg-norm between subsequences i and j of length / = 2" A, p = 0, 1, 1....... P. and
dig
as an entry of the edge attribute E (se) where is the standard deviation of this distance. Moreover, the semantic graph follows the definition of the K-NN graph enforce sparsity, i.e., edge (j,i) is present if any distance between i and is among the K-th smallest distances between i and other nodes.
each distance dij is then transformed to a semantic proximity Wy: exp
Temporal Graph. One distinguishing feature of time series data is its temporal dependency. To effectively encode the temporal information, explicitly build the temporal graph (to)) E E(te)) for time series, where V node indices consistent with the semantic graph A (te) (V, A (te)
the adjacency matrix of temporal graph, and (n) E N denotes the edge weights for tem- poral proximity of subsequences. Specifically, we consider two types of edge connections in graph construction. The first one encodes the temporal dependency in the neighborhood. We connect tem- porally adjacent subsequences by setting the corresponding edge weight the neighboring subsequences are more likely to share similar dynamics. The other one captures the periodic temporal dependency for periodic time series by constructing the periodic connection. For periodic time series with period length m the subsequences It, and Zt-m,! are connected in the
Intuitively, we assume
We auto-correlation detect whether time series is periodic as well the period length.
4

---

Under review as a conference paper at ICLR 2023
temporal graph. To deal with the possible time warping, we introduce additional connections with less weights for certain tolerance: for any neighbors of node t + m, i..., Ij - (t + m)] S r for given radius r, we have
W = exp(- - m 1),
(2)
which stands for the periodic edge weight and is encoded in E(te), Note that the weight decays exponentially as the difference between time indices increases.
Anomaly Injection. As we mentioned above, the labeled anomaly data are rare for training in most situations. The anomaly injection method is used to inject several labeled artificial anomalous subsequences into the time series. Here we consider six different types of anomalies, including spike & dip, resizing, warping, noise injection, left-side right, and upside down. In more detail, spike & dip stands for standard point anomaly with unreasonable high or low value, resizing randomly changes the temporal resolution of subsequence, warping denotes random time warping and noise injection for random noise injected, while the latter two stand for reversement of subsequence from left to right and up to down, respectively. Despite the fact that such artificial anomalies may not coincide with real anomalies, it is beneficial for learning characteristic representations of normal behaviors.
3.2 LEARNING REPRESENTATION OF SUBSEQUENCES WITH MULTI-SCALE LENGTHS
While selecting proper subsequence length that highlights the characteristies of both normal and anomalous patterns is important for AD, most of the existing algorithms commonly set the sub- sequence length through trial and error or by some prior knowledge (e.g., the period length for periodic time series). A potential modification is to perform anomaly detection with multiple subse- quence lengths and vote for anomalies, while it is still not robust since anomaly scores of different lengths are hard to align. Thus, in order to learn expressive subsequence representations with proper length, we propose temporal convolution network ( (Bai et al. (2018). TCN) based multi-scale fea- ture encoder aggregating information at different length resolutions as well learnable length selection mechanism to generate representations of proper length.
Multi-Scale Feature Encoder. This encoder takes the raw subsequence X; E R- as input, and output the multi-scale representations Z, = iZ....... Z.,.). where P is the number of length scales, defined in Section 3.1 First, the TCN consists of several layers of causal convolution with ReLU activation and layer normalization outputs the intermediate embeddings R. TCN(X,) e Rlxd, where d is the hidden dimension and necessary padding is performed to keep the subsequence length unchanged. Then, we aggregate information of variable length by pooling R... E IR into single vector. Despite the fact that mean-pooling or max-pooling frequently used to generate a single vector summarizing sequence, they fail to characterize the statistical property adequately which crucial for anomaly detection. For example, The maximum and minimum are helpful for detecting spike and dip anomalies, but the variance increases when noises occur. To integrate this inductive bias into representation space, we define statistics pooling operator StatsPool()) that calculates and concatenates basic statistics including mean, variance, maximum, and minimum of an l-length subsequence embedding through the first dimension (time axis):
Z. StatsPool R.,.))
(R..a) var (R,,:)) (R,.) (R,,)) Rdd.
(3)
where length / = 2" A is the p-th scale length. By performing statistics pooling with multi-scale length from scale P, we can generate the multi-scale representations Z, (Z....... ZZ.P).
Length Selection Mechanism. As multi-scale subsequence representations are generated, the next problem is how select proper lengths among them. We propose to learn a length selection embedding W; E R² for each subsequence. Then the subsequence representation H; can be generated as follows:
Z: = Softmax W. (Z.,.
Z.PP) E E
(4)
H: = MZ.(Z.) E Rd.
(5)
The length selection embedding W, is initialized to all-zero vector for anomaly-agnostic scenar- ios, which is then jointly learned with model parameters (in Section 3.4). As a result, the weights of different lengths are the same in the beginning, and during the training procedure, this embedding is optimized to pay more attention to the proper length that minimizes the anomaly detection ob- jective. It is worth mentioning that one can introduce priors of subsequence length by adjusting the
5

---

Under review as a conference paper at ICLR 2023
initialization of W. to e = Lo............. E Rp with a at position p. For instance, e can be set for the time series dataset which point-wise anomalies (e.g., spike and dip) often occur.
3.3 MULTI-CONTEXT AWARE ANOMALY DETECTION
Once subsequence representations H E Rxxd are obtained, we enhance them with prior knowledge encoded in graphs via GNN. For a target node (subsequence), the networks utilize representations of its neighboring nodes as well the proximity information (i.e.. distance information in the semantic graph and temporal information in the temporal graph) encoded in neighboring edges and generate context-enhanced representations, which are then concatenated as the final representations:
H (e) GNN (g(se),
H)
R Nxd
(6)
(t) 2 (te)
(g(())
H RW
(7)
H
(ee)
(tt))
E N N2d
(8)
where GNN (-) and G-N2(-) are multi-layer graph neural networks performing on the semantic graph and temporal graph, respectively.
Following the distance- based anomaly detection methods, our approach identifies anomalies by comparing the target representation with a reference. Note that in our implementation the refer- ence considers both semantic and temporal context. Formally, we propose distance-based anomaly score function, namely multi-context aware hypersphere anomaly score defined as
X H c( + (1- a))
-(te)
where a E [0, 1] is a hyperparameter, (( and c((e) are the semantic and temporal context of X;, respectively, which are the mean of node representations within S-hop neighbors of X, the two graphs and can be calculated in matrix form as
C (Binary
A:)
H
(10)
where the context C Nx2d be either C(se) C(te), and does the adjacency matrix A. A returns the s-hop adjacency matrix, where (A")s,; is number of s-hop path from node i to j. B-nary(-) is a binarization function applied on each entry of matrix, which returns 1 if the entry
T greater than 0 and returns 0 otherwise. As result, the i-th row of (Binary (E:, - can represent nodes that can reach within S hops (node itself is removed).
3.4 MODEL LEARNING
By incorporating artificially labeled anomalies, we propose a loss function L following the Hyper- sphere Classifier (HSC) (Ruff et al. 2020) objective with the multi-contex. aware anomaly score
C = Σ (11 (X)) ys log(1 exp(-s(X.))),
(11)
where sX.;) is the anomaly score of subsequence X, (see Equation 9 and y: E {0, 1) with 1 for (artificial) anomalous subsequences and 0 for normal and unlabeled subsequences. Details about HSC is summarized Appendix B Furthermore, in the scenarios with both normal and unlabeled data in the training set, we actually use weighted version of HSC objective, where normal data is assigned with larger weight than unlabeled data, as a known normal sample gets a high anomaly score, it needs to be penalized more.
Regularizations. We introduce two regularizations for stable learning including auto encoding regularization and Laplacian regularization.
Auto- nuto-encoding regularization. We introduce an auxiliary MLP decoder to reconstruct the original subsequence X, using the output of GNN H. The auto-encoding regularization is defined as
Laec Σ MSE(X,, Dec(())
(12)
where MSE(.) denotes the mean squared error loss and Dec(-) is the decoder. Suppose that artificial anomalies not involved, i.e., y: 0 for all training samples, the network might corrupt map

---

Under review as a conference paper at ICLR 2023
all samples to constant representation and achieve the optimal. This regularization is utilized to restrict the network to preserve the information of input data to avoid trivial solutions. Even with anomaly injection, it can still conduce the model robustness.
Laplacian regularization of length selection embedding. We impose a restriction that the length selection embeddings of adjacent nodes in both graphs should be close, which can be implemented with a Laplacian regularization defined as
Lap Σa E Evijev| IW; -W,l =A E pmI WT (D A)W
(13)
where W E RNP the row vector W; E EI.. N) is the length selection embedding of each node, W., E E (1,.... P) is the column vector, Å = max A, A returns symmetric adjacency matrix (i.e., makes graphs undirected), and A (s(s)) denotes the diagonal degree matrix of the undirected graph with D = E, A.j. and D Å returns the unnormalized graph Laplacian.
(se) A (ee). J. D E R
Training Procedure. As two components need to be optimized, i.e., model parameters O and length selection embedding W, we propose training strategy with two phases towards better con- trol of joint optimization
< arg min C + XLdeet
(14)
W < arg min L + /LLapp W
where À >> O and μ > 0 are hyperparameters. The two phases above alternate during model training.
4 EXPERIMENTS
In this section, compare the performance of our approach with other methods on multiple bench- mark datasets, conduct case studies to analyze the model's behavior, and investigate model variations in ablation studies.
4.1 DATASETS AND EVALUATION METRICS
We evaluate our method using the following five annotated real and synthetic datasets:
UCE the well-known subsequence anomaly dataset from "KDD cup 2021 multi-dataset time se- ries anomaly detection" competition, consisting of 250 univariate time series from different domains with one subsequence anomaly per series. The lengths of the series vary from 4000 to one million.
UCR-Aug" since UCR contains anomaly per time series, augment UCR by adding various types of subsequence anomalies with variable-length into each time series which is more consistent with most real-world scenarios.
SMAP and MSL Soil Moisture Active Passive satellite (SMAP) and Mars Science Laboratory rover (MSL), two datasets published by NASA (Hundman et al 2018). with 55 and 27 series re- spectively. The lengths of the time series vary from 300 to 8500 observations.
SMD: Server Machine Dataset Su et al. 2019), a 5 weeks long dataset with 28 38-dimensional time series each collected from different machine in large internet companies.
Evaluation Metrics. For the first two subsequence anomaly datasets, We choose AUC and Recall as evaluation metrics, where AUC stands for the area under receiver operating charac- teristic (ROC) curves, and @ecall@k is the recall rate for the number of anomalous subsequences found in the top-kn anomaly scored ones where n is the total number of anomalous subsequences in one time series, i.c., for each anomaly, we have & reporting opportunities considering the cost of check is limited in reality. For the last three multivariate datasets, report Fl scores computed by choosing the best threshold on the test set following prior works.
ucr edu wtwp://eamon////eeee /t iieeime__ss rrr__serre___ data__011 Thii dataset is included in the Anonymous GitHub link the Abstract. SSMAP, MST. and the following SMD) have predefined train/test split, we do not use labels in training set following unsupervised paradigm.
https: ///w:///wwwww
7

---

Under review as a conference paper at ICLR 2023
Table 1: Performance of models UCR.
Metric
AUC
Recall@1
R
Recall
Recall 10
Matrix Profile
0.8631
0.436
0.548
0.396
0.644
Srrp
0.6847
0.276
0.348
0.372
0.408
LOF
0.5995
0.312
0.360
0,409
0.461
NCAD
0.6413
0.352
0.412
0.520
0.648
GraphSAD
0.8864
0.444
0.572
0.640
0.696
Table 2: Performance of models on UCR-Aug.
Metric
AUC
Recall@1 |
@
Recall @5
Recall 10
Matrix Profile
0.8683
0.709
0.841
0.873
0.899
Serahs2Graph
0.7252
0.442
0.610
0.687
0.761
LOF
0.6129
0.594
0.736
0.798
0.861
NCAD
0.8414
0.722
0.803
0.839
0.890
GraphSAD
0,9022
0.792
0.925
0,953
0,981
4.2 IMPLEMENTATION DETAILS
Subsequence split. We set the length of indivisible segment A 0.125 m for periodic time series with period length m, and = 10 for non-periodic time series. We utilize a sliding window with stride 2A to generate subsequences. For the multi-scale length of subsequences, the maximum length scale P = 5, and thus the length can vary from 0.125 to 4 times of period length for periodic time series, which stand for most common anomalies.
set
Extension to multivariate data. GraphS can be naturally extended to multivariate data as neural networks support multivariate input. We just need to modify the graph construction strategy. For the semantic graph, we calculate the distance for each variate and encode them into edge attributes, and for the temporal graph, we only retain the neighboring connection.
Due to space limitations, we only list these important experimental settings. For more details, e.g., hyperparameters, learning rate, and operational device, we refer Appendix C.I
4.3 COMPARISON EXPERIMENTS
We compare GraphSAD with detectors that are specified for subsequence anomaly detection used subsequence anomaly datasets, including Matrix Profile Yeh et al. 2016) (a time series discord search method), Series2Graph (Boniol & Palpanas), LOF (Breunig et al. 2000). and NCAD (Car- mona et al. 2022). Table and 1 report the model performance on UCR and UCR-Aug. respec- tively. Our method outperforms Matrix Profile (the second best method) by reasonable margin on UCR and a large margin on UCR-Aug. This is mainly because UCR has one anomaly per time series, which time series discords are naturally applicable. While each time series in UCR-Aug can contain multiple anomalies and some of them are similar in anomalous patterns.
Thows the performance on multivariate datasets of GraphS compared against the state-of- the-art deep learning methods, including DeepSVDD (Ruff et al. 2018), OmniAnomaly (Su et al., 2019). THOC (Shen et al., (2020). and NCAD (Carmona et al., 2022). GraphSAD outperforms all baselines on two of the datasets, while its score is only slightly lower than NCAD on MSL. Considering that anomalies in these three datasets are mainly point-wise, which is not our main concern, yet GraphSAD still remains highly competitive.
Table 3: Fl score of models on multivariate datasets.
Datusct
SMAP
MSL
SMD
Deep SVDD
71.71
88.12
OmniAnomaly
84.34
89.89
88.57
THOC
95.18
93.67
NCAD
94.45
95.6
80.16
GraphSAD
96.67
95.32
91.12
8

---

Under review as a conference paper at ICLR 2023
Ground Truth
Matrix Profile
GraphSAD
Figure 5: GraphSAD Can Handle Recurring Anomalies Compared with Matrix Profile. There are 5 subsequence anomalies (marked in grey) in time series, where Anomaly 3 and share similar anomalous pattern. Matrix Profile find 1 of anomalies in its top-5 scored subsequences which cannot deal with recurring anomalies, while GraphSAD find 4 of 5.
Table 4: Performance of model variations UCR and UCR-Aug
Dataset
UCR
UCR-Aug
Metric
AUC
Recall
Recall@5
AUC
Recall
Recall
w/o semantic graph
0.7498
0.366
0.609
0,8513
0.714
0.881
w/o temporal graph
0.8832
0.446
0.587
0.8991
0.766
0.923
w/o anomaly injection
0.8640
0.440
0.587
0,9003
0.745
0.939
w/o length selection
0.8339
0.428
0.620
0.8731
0.762
0.936
fixed length
0.8765
0.396
0.594
0.8647
0.741
0.900
GraphSAD
0.8864
0.444
0.640
0.9022
0.792
0,953
4.4
CASE STUDIES
Here we conduct case studies investigate how well GraphSAD handles recurring anomalies with similar patterns. Figure iillustrates a heartbeat time series in UCR-Aug. There are subsequence anomalies (marked in grey) in time series, where Anomaly and 4 share a similar anomalous pat- tern. Matrix Profile find of 5 anomalies in its top-5 scored subsequences which cannot deal with recurring anomalies, while GraphSAD find of It can be seen that the proposed GraphSAD algorithm detects recurring anomalous subsequences much better than the Matrix Profile algorithm.
4.5 ABLATION STUDIES
To better understand the effectiveness each component in GraphSAD, we perform ablation studies on UCR and UCR-Aug. We introduce model variations as in Table where the first three are used to verify the effectiveness of semantic graph, temporal graph, and anomaly injection, the variation w/o length selection" denotes multi-scale representations are averaged before input GNN, i.e., different lengths are treated equally, and the variation "fixed length" denotes that we do not use the multi-scale representations but select a fixed subsequence length (which is for periodic time series and constant 160 for the periioiid.. Results in Table demonstrate the advantages of each component. performance degrades lot, suggesting the significance of discords- based prior knowledge.
be the period length
important to note that without the semantic graph, the
CONCLUSION
We propose to bridge the gap between time series discords and deep learning-based TSAD meth- ods and introduce a novel subsequence anomaly detection approach (GraphSAD). In addition to incorporating effective heuristics into neural networks, the model also adaptively leam proper subsequence length through a length selection mechanism, benefiting the subsequence AD problem. Experiments multiple datasets demonstrate the effectiveness of the proposed model.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv: /803.01277 2018.
Paul Boniol and Themis Palpanas. Series2Graphh: Graph-based subsequence anomaly detection for time series. Proceedings of the VLDB Endowment, 13(7).
Markus M Breunig, Hans-Petee Kriegel, Raymond T Ng, and Jörg Sander. LOF: identifying density- based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pp. 93-104, 2000.
Chris U. Carmona, François- Xavier Aubet, Valentin Flunkert, and Jan Gasthaus. Neural contextual anomaly detection for time series. In Proceedings of the Thirty-First International Joint Confer- ence on Artificial Intelligence (IJCAI), pp. 2843-2851, 2022.
Sucheta Chauhan and Lovekesh Vig. Anomaly detection in eeg time signals via deep long short- term memory networks. In 2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA), pp. 1-7. IEEE, 2015.
Andrew A Cook, Göksel Misrh, and Zhong Fan. Anomaly detection for iot time-series data: A survey. IEEE Internet of Things Journal, 7(7):6481-644) 2019.
Ada Wai-chee Fu, Oscar Tat-
Tat-Wing Wing Leung, Eamonn Keogh, and Jessica Lin. Finding time series discords based on haar transform. In Xue Li, Osmar Zaïane, and Zhanhuai Li (eds.), Advanced Data Mining and Applications, pp. 31-41, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
Kyle Hundman, Valentino Constantinou, Christopher Laporte, Ian Colwell, and Tom Soderstrom. Detecting spacecraft anomalies using LSTMs and nonparametric dynamic thresholding. In Pro- ceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 387-395, 2018.
E. Keogh, J. Lin, and A. Fu. Hot sax: efficiently finding the most unusual time series subsequence. In Fifth IEEE International Conference Data Mining (CCDM'S)) pp. pp.-, 2005.
Yue Lu, Renjie Wu, Abdullah Mueen, Maria A. Zuluaga, and Eamonn Keogh. Matrix profile xxiv: Scaling time series anomaly detection to trillions of datapoints and ultra-fast arriving data streams. KDD 222 pp. 1173-1188 182, 2022.
Junshui Ma and Simon Perkins. Time-series novelty detection using one-class support vector chines. In Proceedings of the International Joint Conference on Neural Networks, 2003., vol- ume 3, pp. 1741-1745, 2003.
Takaaki Nakamura, Makoto Imamura, Ryan Mercer, and Eamonn Keogh. MERLIN; Parameter-fiee free discovery of arbitrary length anomalies in massive time series archives. In 2020 IEEE interna- tional conference on data mining (ICDM), pp. 1190-1195, 2020.
Daehyung Park, Yuuna Hoshi, and Charles Kemp. A multimodal anomaly detector for robot- assisted feeding using an Istm-based variational autoencoder. IEEE Robotics and Automation Letters, 3(3):1544 -55111444111,, 2018.
Lukas Ruff, Robert Vandermeulen, Nico Goernitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Alexan- der Binder, Emmanuel Müller, and Marius Kloft. Deep one-class classification. In International conference on machine learning, pp. 4393-4402, 2018.
Lukas Ruff, Robert Vandermeulen, Billy Joe Franks, Hoburt Müller, and Marius Kloft. Rethinking assumptions in deep anomaly detection. arXiv preprint 0000029006.0033, 2020.
Thomas Schlegl, Philipp Seeböck, Sebastian M Waldstein, Ursula Schmidt- Schmidt-Erfurth, and Georg Langs. Unsupervised anomaly detection with generative adversarial networks to guide marker discovery. In International conference on information processing in medical imaging, pp. 146-
157, 2017.
10

---

Under review as a conference paper at ICLR 2023
Bernhard Schölkopf. John C Platt, John Shawe-Taylor, Alex J Smola, and Robert C Williamson. Estimating the support a high-dimensional distribution. Neural computation, 13(7):143314771, 2001.
Lifeng Shen, Zhuocong Li, and James Kwok. Timeseries anomaly detection using temporal hier- archical one-class network. Advances in Neural Information Processing Systems (NeurlPS), 33: 13016-13026, 2020.
Ya Su, Youjian Zhao, Chenhao Niu, Rong Liu, Wei Sun, and Dan Pei. Robust anomaly detection for multivariate time series through stochastic recurrent neural network. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2828-2837. 2019.
David MJ Tax and Robert PW Duin. Support vector data description. Machine learning, 54(1): 45-66, 2004.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4 2021.
Jiehui Xu, Haixu Wu, Jianmin Wang. and Mingsheng Long. Anomaly transformer: Time series anomaly detection with association discrepancy. In International Conference on Learning Repre- sentations (ICLR), 2021.
Dragomir Yankov, Eamonn Keogh, and Umaa Rebbapragada. Disk aware discord discovery: Find- ing unusual time series in terabyte sized datasets. In Seventh IEEE International Conference on Data Mining (ICDM 2007), pp. 381-390, 2007.
Dragomir Yankov, Eamonn Keogh, and Umaa Rebbapragada. Disk aware discord discovery: finding unusual time series in terahyte sized datasets. Knowledge and Information Systems, 17(2))241- 262, 2008.
Chin-Chia Michael Yeh, Yan Zhu, Liudmila Ulanova, Nurjahan Begum, Yifei Ding, Hoang Anh Dau, Diego Furtado Silva, Abdullah Mueen, and Eamonn Keogh. Matrix profile I: all pairs similarity joins for time series: a unifying view that includes motifs, discords and shapelets. In 2016 IEEE 16th international conference on data mining (ICDM), pp. 1317-1322, 2016.
Chuxu Zhang, Dongjin Song, Yuncong Chen, Xinyang Feng, Cristian Lumezanu, Wei Cheng, Jingchao Ni, Bo Zong. Haifeng Chen, and Nitesh V Chawla. A deep neural network for un- supervised anomaly detection and diagnosis multivariate time series data. Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 1409-1416, 2019.
Yingying Zhang, Zhengxiong Guan, Huajie Qian, Leili Xu, Hengbo Liu, Qingsong Wen, Liang Sun, Junwei Jiang, Lunting Fan, and Min Ke. CloudRCA: root cause analysis framework for cloud computing platforms. In Proceedings of the 30th ACM International Conference Information
& Knowledge Management (CIKM), pp. 4373-4382 2021.
Hang Zhao. Yujing Wang, Juanyong Duan, Congrui Huang, Defu Cao, Yunhai Tong. Bixiong Xu, Jing Bai, Jie Tong, and Qi Zhang. Multivariate time-series anomaly detection via graph attention network. In 2020 IEEE International Conference on Data Mining (ICDM), pp. 841-850, 2020.
Bo Zong, Qi Song, Martin Renqiang Min, Wei Cheng, Cristian Lumezanu, Daeki Cho, and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection, In Inter- national conference learning representations (ICLR), 2018.
11

---

Under review as a conference paper at ICLR 2023
A
RELATED WORK
Subsequence anomaly detection in time series remains challenging problem in the time series com- munity. In this section, we briefly introduce some state-of-the-arr algorithms for subsequence time series anomaly detection, including discord based methods, one-class based methods, reconstruction based methods, and other methods.
A.1 ANOMALY DETECTION BASED ON DISCORDS.
Subsequence anomaly detection can be formulated by finding discords in time series, where the discords are the subsequences maximally different from other subsequences in the same time se- ries (Keogh et al.
2005). In Yankov et al. (2007), it is defined as the subsequence with the high- est distance to its nearest neighbors. The distances can be calculated directly on the original sig- 2007), or on the representations like wavelets (Fu et al. 2006). Many methods in been proposed, like Matrix Profile (Yeh et al. (016) and its latest variants (Naka mura et al. 2020 Lu al. 2022). Matrix profile turns out to be efficient solution for easy settings due to its efficient distance computation implementation. One limitation of matrix profile is the chal- lenging parameter tuning. For example, its performance would degrade significantly if the window size is not properly set. In addition, it can easily capture the most different anomaly, but fails to de- tect similar anomalies which recur multiple times as illustrated in previous examples. Although this can be mitigated to some extent by taking k-th nearest neighbor into consideration (Yankov et al., 2008) is hard to select an appropriate value of and the performance highly sensitive k.
nal (Yankov et al.
this category have
A.2 ANOMALY DETECTION BASED ON ONE- CLASS CLASSIFIER.
One-class approaches are common since the majority of the data is usually normal in anomaly de- tection. The One-Class Support-Vector-Me
( (Schölkopf al. (2001), OC-SVM) and Support Vector Data Description ( (Tax & Duin (2044), SVDD) are two well- methods in this cate- gory, which use hyperplane and hypersphere to separate the normal data from anomalous data in the kernel-induced feature space, respectively. These methods can also be extended to time series anomaly detection (Ma Perkins, 2003). However, their performances are often not satisfied when facing complex and high-dimensional datasets, due to the curse of dimensionality and non-efficient computational scalability. To overcome these limitations, Deep Support Vector Data Description (Rufi et al. (2018), DeepSVDD) is proposed to jointly train deep neural network and optimize data-enclosing hypersphere in output space. Inspired by Deep SVDD, the THOC (Shen et al. 2020) extends this deep one-class model by considering multiple spheres from all intermediate layers of dilated recurrent neural network to extract multi-scale temporal features for better performance. Fur- thermore, Neural Contextual Anomaly Detection (Carmona al. (2022), NCAD) incorporates the idea of Hypersphere Classifier (HSC) which improves the Deep SVDD by utilizing known anoma- lies data under the (emmi))uupervsedd setting (Ruff et al. 2020), as well as a window-based approach specified for time series anomaly detection. Another popular one-class classifier based method is the Deep Autoencoding Gaussian Mixture Model ( (Zong et al. (2018). DAGMM) which integrates a deep autoencoder with the Gaussian mixture model (GMM) to generate a low-dimensional rep- resentation to capture the normal data pattern. However, directly applying DAGMM in time series may bring inferior performance since it does not properly model temporal dependencies.
A.3 ANOMALY DETECTION BASED ON RECONSTRUCTION.
The reconstruction-basel models usually learn representation of the time series in latent space, reconstruct the signal from that representation, and conduct anomaly detection based on the re- construction error. The long short-term memory based variational autoencoder (Park et al. (2018), LSTM-VAE) adopts serially connected LSTM and VAE layers to obtain the latent representation, estimates the expected distribution from the representation, and detects an anomaly when the log- likelihood of current observation given the expected distribution is lower than a threshold. Omni- Anomaly (Su et al. 2019) designs a stochastic recurrent neural network with state space models and normalizing flows for multivariate time series anomaly detection. AnoGAN (Schleg) et al., 2017) proposes deep generative adversarial network (GAN) to model data distribution and estimate their probabilities in latent space for anomaly detection. The Multi-Scale Convolutional Recursive En-
12

---

Under review as a conference paper at ICLR 2023
coder Decoder Zhang al. (2019), MSCRED) convolutional encoder and convolutional LSTM network to capture the inter-series and temporal patterns, respectively, and adopts a convolu- tional decoder to reconstruct the input time series for anomaly detection.
A.4 OTHER ANOMALY DETECTION METHOSS
The rest the anomaly detection methods roughly include density-based transformer- and graph-based schemes. The Local Outlier Factor (Breunig al. (2000), LOF) is classic density- estimation method that assigns each object a degree of being an outlier depending on how isolated the object is with respect the surrounding neighborhood. Anomaly Transformer (Xu et al.) 2 proposes new anomaly-attentio mechanism to replace the original attention module and compute the association discrepancy, which can amplify the normal-abnormal distinguishability in time se- ries under minimax strategy to facilitate anomaly detection. Series2Graph (Boniol & Palpanas) transforms time series subsequences into lower-dimensional space and constructs a directed cyclic graph, where the graph's edges represent the transitions between groups of subsequences and can be utilized for anomaly detection. MTAD-GAT (Zhao et al., 2020) designs two graph attention lay- ers for learning the dependencies of time series in both temporal and feature dimensions, and then jointly optimizes a forecasting- based model and a reconstruction based model for better anomaly detection results. While the existing graph-based methods achieve good results in some scenar- ios, they still have difficulty modeling and adapting to the challenging variable-length subsequences anomalies.
B DISTANCE-BASER ANOMALY DETECTION METHODS
Distance-based anomaly detection methods usually calculate the distance between a target sample subsequence) and its reference in explicit data space or latent representation space as the anomaly score. We now detail a prevailing part of them.
B.1 TIME SERIES DISCORDS
Time series discords compute anomaly score of X, as
8( s(x)) = x-norrm(X X,) - z-norm X X NN)
(15)
where z-norm(xx = (x mcan(x)) /std(x) returns zero-normalized subsequence with mean(.)
and std(.) standing for mean and standard deviation of input subsequence, and the corresponding reference X (N-NN) is the k-th nearest neighhour of X,. Despite its effectiveness and wide usage,
has several limitations as we discussed in Section [
B.2 DEEP SUPPORT VECTOR DATA DESCRIPTION BASED METHODS
The OC-SVM and SVDD rely on proper kernel to map data features to high dimensional space for data separation. And the DeepSVDD algorithm replaces the kerncl-induced feature space in the SVDD method with the feature space learned in a deep neural network. Specifically, DeepSVDD (Ruff al. 2018) an unsupervised anomaly detection method that solves the follow- ing optimization problem
min Ei=1 |NN(X.) - cc
(16)
where DeepSVDD calculates the latent distance [|NN(X.) cll2 as anomaly scores, NN(.) is a deep neural network, and is a global reference which is the center of all the training data.
-
B.3 HYPERSPHERE CLASSIFIER
The Hypersphere Classifier Ruff et al. 2020), HSC) improves DeepSVDD by training the network with the binary cross entropy objective function, which extends the model training with labeled anomalies. In particular, the HSC loss is given by
(1 V/)) log (NN)(..) y: log(1 I(NN(X))),
(17)
'k is usually 1.
13

---

Under review as a conference paper at ICLR 2023
where y4 {0, 1) with 0 for the normal and for the anomalous, and / R (0, 1) maps the representation to a probabilistic prediction. Choosing ((2) exp( exp(-11=113) would reduce equation 17 to DeepSVDD objective with center when all labels are 0.
C EXPERIMENTAL DETAILS
C.I IMPLEMENTATION DETAILS OF GRAPHSAD
Hyperparameters. For hyperparameter tuning, we randomly select 8 time series to perform grid search. We use this inferred hyperparameters for all datasets. The hyperparameter settings are summarized in T
Table 5: Hyperparamter settings
Hyperparameter
Description
Value
0.125 times of period length for periodic time series, and 10 otherwise
the length of indivisible segment
stride length
2A
the maximum length scale
5
the maximum subsequence length
2PA
number of hops when calculating contexts
2
the coefficient to balance semantic and temporal anomaly score
0.8
the coefficient of auto-encoding regularization
1.0
the coefficient of Laplacian regularization
0.2
Model Training. We run the model times on each of the benchmark datasets and report the average score. We train the model with Tesla V100 32GB GPU. For all datasets, train Graph- SAD for 10 epochs with learning rate x 10 4 for model parameters and x 10 -4 for length selection embeddings.
14


Reviews:
[{"review_id": "QZEeqBt475", "reviewer": "Reviewer_8d5u", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper addresses the problem of time-series subsequence anomaly detection, and this is executed through converting the time-series to a graph, and then performing anomaly detection on this graph representation. The problem is motivated by the fact that time-series anomalies can be subsequences, while most existing work focuses on point anomalies.\n\nThe method starts with splitting the time-series into multiple subsequences, followed by construction of graph priors - semantic priors and temporal priors. Semantic graphs is based on distances measures and incorporates multi-scale lengths. Temporal graph also uses multiple heuristics to incorporate temporal information. These graphs are followed by a multi-scale feature encoder and a length selection module to aid representation learning for the time-series. Auto encoding regularization and Laplacian regularization is used to stabilize the training. Experiments are performed on both synthetic and real world datasets, and GraphSAD achieves competitive performance - even performs well for point anomaly detection which is not the focus of the algorithm. ", "summary_of_the_review": "Overall the paper reads well and is a well done work (though not something I'd consider as breakthrough). I'll be happy to raise score after author's justify the key technical novelty compared the baselines addressing the same problem.", "strength_and_weaknesses": "Strengths: Fairly well written and motivated well, appears technically novel from an application perspective, experiments seem convincing\nWeakness: The key distinction from so many of the competing baselines is not argued well (e.g. Series2graph, THOC), which makes it slightly unclear what the new principle of this paper is compared to the literature, as these papers also try to address the same problem from a certain angle (e.g. subsequence, multi-scale). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EfHxtysAGTA", "reviewer": "Reviewer_GTLu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes GraphSAD, a subsequence time-series anomaly detection method that fuses discord-based anomaly detection solutions with graph neural network (GNN) /deep neural network (DNN) architectures. The core contribution of the paper is the construction of two types of graphs, semantic and temporal, to capture the distances and temporal dependencies in the data.  In addition, the proposed method proposes a solution for selecting the appropriate length for subsequences, a core parameter for that family of methods. Experimental results demonstrate the benefits of the proposed solution against several baselines on multiple datasets.", "summary_of_the_review": "I believe the paper is on the correct track to getting accepted eventually in a top venue. However, I have significant concerns about the evaluation of the work: missing recent comprehensive benchmarks in the area and missing the appropriate methods to evaluate subsequence methods. For the baselines, similar tricks for selecting the length should be used to ensure fairness.\n\nFrom the ablation study, we see that the most important \"idea\" is the temporal graph. Semantic graph lacks behind, which contradicts the entire concept of using GNNs in the first place. Temporal information seems sufficient and tons of methods exist (and not being evaluated) to capture these cases. Check references for appropriate evaluation on new benchmarks and new evaluation measures, using the appropriate baselines.", "strength_and_weaknesses": "Strengths:\n\n1. Important and timely problem for time series\n2. Well-written paper and easy to follow\n3. Practical ideas fused appropriately into a single method\n\nWeaknesses\n\n1. Lack of novelty, mainly fusion of ideas \n2. Missing several baselines\n3. Missing several appropriate datasets and evaluation measures\n\nComments:\n\n- The ideas are reasonable and appropriately merged into a single DNN/GNN framework. Unfortunately, there is a lack of technical depth and novelty. If we abstract the contributions, the core idea is to construct two types of graphs, and both such kinds of graphs exist/are well known (no novelty here). The remaining parts are mainly plug-ins of existing solutions. There is some interesting concepts in choosing lengths, but really similar solutions could be applied to every solution (e.g., run the method with different parameters, select on that maximizes anomaly score or using some voting etc.)\n\n- Core very recent works are missing. There has been new works published well in-advance before the ICLR submission about new measures for evaluating subsequence anomaly detection methods as well as new benchmarks with 2000+ time series. Unfortunately, the paper does not consider the more recent advances in the area, and some methods are outdated. This is a fast pacing field, unfortunately.\n\n\"Tsb-uad: an end-to-end benchmark suite for univariate time-series anomaly detection.\" Proceedings of the VLDB Endowment 15.8 (2022): 1697-1711.\n\n\"Volume under the surface: a new accuracy evaluation measure for time-series anomaly detection.\" Proceedings of the VLDB Endowment 15.11 (2022): 2774-2787.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Do6QtWdF5du", "reviewer": "Reviewer_s2pX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes a method to identify anomalous subsequences in a long time series using a graph neural network. The core idea is to use two different graph representations for fixed length subsequences from the time series, one which captures the semantic distance (based on different distance measures) and the second which captures the temporal distance (both time adjacency and periodicity). The method allows for capturing similarity between subsequences at different length scales. The two graph neural networks are then combined within a single learning framework to learn representations for the subsequences, which are then used for anomaly detection. \n\nThe method is compared to a few other methods and shown to outperform them on a selection of data sets.", "summary_of_the_review": "Overall, the paper is targeting an important problem. There is some marginal benefit shown on a set of data sets over a selection of methods. But the results are not convincing enough to show that the approach is generally applicable. There are some questions on the novelty. ", "strength_and_weaknesses": "Strengths:\n- The problem is important and has real-world applications.\n- The idea of not relying on a single window length is good and could make the method applicable in more settings.\n\nWeaknesses:\n- The paper is not very well-written and it is hard to understand how all the steps fit together. While the overview figure is useful, it does not provide the complete picture.\n- The paper seems to be putting together several individual components to solve the problem but is not necessarily pushing the boundary significantly. While I agree that the results are better than others, the comparison is not comprehensive enough to show that this will generalize well. I can see some novelty in using two different representations (semantic and temporal), but the authors do not discuss the impact of using both representations.\n- The experimental results are not comprehensive. I would have liked to see comparisons with the vast literature on discord detection which have been shown to be very effective in such problems, and for many of the data sets used in this paper.\n- While I commend the relaxation of the need to specify a window length, it is unclear what is impact of the choice of the initial window length on the overall performance", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4xcgU6c2lR", "reviewer": "Reviewer_s3os", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper presents a method for anomaly detection in time series. The proposed method constructs two graphs of subsequences of the input time series, by encoding subsequence distance and periodic patterns, with multiple choices of length scales of subsequences. The model uses GNN and length embeddings to learn to weigh different scales. The aim is to capture resolve the problem of selecting subsequence lengths. The experimental results demonstrate the method outperforms some baseline methods.", "summary_of_the_review": "The paper introduces a graph based subsequence anomaly detection in time series. The overall novelty of the proposed method is limited. The method design and experiments remain to be further justified and improved.", "strength_and_weaknesses": "Strength\n1. The proposed method considers two versions of graphs to encode the relationship between subsequences, a distance based graph and periodic pattern based graph.\n2. The method introduces a subsequence length selection mechanism which is trained together with other parts of the model so that the length selection problem is mitigated to some extent.\n3. The experimental results demonstrate the effectiveness of the proposed method in terms of improvements over several baseline methods.\n\nWeakness\n1. The overall novelty of the proposed method is limited. Using graph and multi-scale subsequence length of anomaly detection in time series has been studied before (e.g., A deep neural network for unsupervised anomaly detection and diagnosis in multivariate time series data. AAAI, 2019). Learning to select lengths is not significant innovation as it can be done by adding some attention based mechanisms. The paper briefly discussed these existing methods in the appendix, without sufficient details. Comparison may be necessary. The related work section is important, and should be moved to the main paper.\n2. The proposed method may be limited by the initial subsequence length selection, which was assumed to be large, without a clear selection guidelines and impacts on performance.\n3. It is not clear what the dimension $d_{e}$ is in $E_{j,i}^{(se)}$. It seems to be 1 for representing the semantic proximity.\n4. The temporal graph only encodes periodic patterns, which may ignore other temporal dependency patterns.\n5. The meaning of $Z_{i,0}, ..., Z_{i,P}$ are not clear. The question is why to aggregate information for all lengths before $l$, i.e. , $R_{i, :l}$, instead of using $l$ directly, i.e., $R_{i,l}$.\n6. The intuition behind the length selection method Eq 4 and Eq 5 should be better elaborated. The current description is unclear because $Z_{i,P}$ represents aggregation for all lengths less than $l$, instead of using $l$ directly.\n7. The motivation to use GNN to encode context information for each subsequence representation is also unclear. To detect anomalies, the method aims to find the difference between a subsequence and its context using Eq 9. GNN seems do the contrary. It aims to mitigate the difference between a subsequence representation and its context.\n8. The authors may want to discuss if the model trained with injected anomalies is biased to detect anomaly patterns follows the injection. This could be further investigated in the experiments. Also Eq. 11 does not consider unbalanced classes (normal and abnormal).\n9. The experiments could be further improved by including more evaluation metrics, and baseline methods. There are more subsequence based anomaly detection methods, as discussed in Anomaly Detection in Time Series: A Comprehensive Evaluation, VLDB 2022. Some of them could be evaluated in the experiments.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject