Sub-Adjacent Transformer: Improving Time Series Anomaly Detection with Reconstruction Error from Sub-Adjacent Neighborhoods

1 Introduction

In modern industrial systems such as data centers and smart factories, numerous sensors consistently produce significant volumes of measurements [Zhou et al., 2019; Shen et al., 2020]. To effectively monitor the systems' real-time conditions and avoid potential losses, it is crucial to identify anomalies in the multivariate time series [Pereira and Silveira, 2019; Chen, 2018]. This problem is known as time series anomaly detection [Bl´azquez-Garc´ıa et al., 2021]. Comprehensive surveys can be found in the literature [Bl´azquezGarc´ıa et al., 2021; Schmidl et al., 2022; Gupta et al., 2013].

∗ Corresponding Author

(a) Existing Methods

(b) Our Method

Figure 1: Illustration of our method in time domain. The point marked with a red circle, along with its neighbors, represents an anomaly on the sinusoidal signal. (a) Previous works typically utilize the attention across all the points within the window, while (b) our method encourages the use of attention of sub-adjacent neighborhoods (the highlighted area). Such an imposed constraint enlarges the reconstruction challenge for anomalies and thus improves the anomaly detection performance.

Effective and robust time series anomaly detection remains a challenging and open problem [Zhao et al., 2022]. Realworld time series usually exhibit nonlinear dependencies and intricate interactions among time points. Besides, the vast scale of data makes the labeling of these anomalies timeconsuming and costly in practice [Lai et al., 2023]. Therefore, time series anomaly detection is usually conducted in an unsupervised manner [Xu et al., 2022], which is also the focus of this paper.

Before the era of deep learning, many classic anomaly detection methods were proposed. These include the densityestimation method proposed in [Breunig et al., 2000], the clustering-based method presented in one-class SVM [Sch¨olkopf et al., 2001], and a series of SVDD works [Tax and Duin, 2004; Liu et al., 2013], along with graph-based methods [Cheng et al., 2008]. Traditional methods, which use handcrafted features, struggle to accurately express the relationship among time points and often suffer from poor generalization. Deep learning-based techniques have witnessed a diversity of methods during the recent decade. Broadly, they can be categorized into three main categories: Reconstruction-based methods reconstruct the time series and compare it with the original data [Park et al., 2018;

Li et al., 2021; Su et al., 2019; Pintilie et al., 2023], whereas prediction-based methods predict future points for comparison with actual data [Deng and Hooi, 2021; Hundman et al., 2018a; Ding et al., 2019; Lai et al., 2023]. Dissimilaritybased methods emphasize the discrepancy representation between normal and abnormal points in various domains [Shen et al., 2020; Sun et al., 2021; Xu et al., 2022]. It is noteworthy that these methods often combine multiple approaches to enhance performance. For example, TranAD [Tuli et al., 2022] integrates an integrated reconstruction error and discriminator loss; while [Lai et al., 2023] uses prediction results as the nominal data and combines them with reconstruction results.

In this paper, we focus on the attention matrix within the Transformer module. Transformers [Vaswani et al., 2017] have achieved great success in natural language processing [Brown et al., 2020], computer vision [Liu et al., 2021] and time series [Xu et al., 2022] in recent years. Previous work in [Xu et al., 2022] primarily concentrated on the dissimilarities in attention distributions. Our paper takes a different approach and introduces a simple yet effective attention learning paradigm. Our fundamental assumption is that anomalies are less related to their non-immediate neighborhoods when compared with normal points. Therefore, focusing exclusively on these non-immediate neighborhoods is likely to result in larger reconstruction errors for anomalies. Based on this assumption, our study introduces two key concepts: subadjacent neighborhoods and sub-adjacent attention contribution. As shown in Figure 1, sub-adjacent neighborhoods indicate the areas not immediately adjacent to the target point, and the sub-adjacent attention contribution is defined as the sum of particular non-diagonal elements in the corresponding column of the attention matrix. These concepts are integrated with reconstruction loss, forming the cornerstone of our anomaly detection strategy. Furthermore, we observe that the traditional Softmax operation used in standard selfattention impedes the formation of the desired attention matrix, where the predefined non-diagonal stripes are dominant. In response, we adopt linear attention [Shen et al., 2021; Han et al., 2023] for its greater flexibility in attention matrix configurations. We also tailor the mapping function within this framework, using learnable parameters to enhance performance. The main contributions of this paper are summarized as follows.

• We propose a novel attention learning regime based on the sub-adjacent neighborhoods and attention contribution. Specifically, a new attention matrix pattern is designed to enhance discrimination between anomalies and normal points.
• Furthermore, we leverage the linear attention to achieve the desired attention pattern. To the best of our knowledge, this is the first introduction of linear attention with a learnable mapping function to time series anomaly detection.
• Extensive experiments show that the proposed SubAdjacent Transformer delivers state-of-the-art (SOTA) performance across six real-world benchmarks and one synthetic benchmark.

2 RelatedWorks

Time Series Anomaly detection. In recent year, graph neural networks and self-attention have been explored in time series anomaly detection [Deng and Hooi, 2021; Zhao et al., 2020; Boniol and Palpanas, 2022; Xu et al., 2022; Lai et al., 2023; Wu et al., 2023]. The most related work to ours is Anomaly Transformer [Xu et al., 2022], which also exploits the attention information. The discrepancy between the learned Gaussian distribution and the actual distribution is used to distinguish abnormal points from normal ones. A somewhat complicated min-max training strategy is adopted to train the model. Generally, Anomaly Transformer is complex and somewhat indirect. Our proposed method is more straightforward and exhibits improved performance.

Linear Attention. Compared with vanilla self-attention, linear attention enjoys more flexibility and lighter computation burden. Existing linear attention methods can be divided into three categories: pattern based methods, kernel based methods and mapping based methods. We mainly focus on mapping based methods in this paper. Efficient attention [Shen et al., 2021] applies Softmax function to Q (in a row-wise manner) and 𝐾 (in a column-wise manner) to ensure each row of QK 𝑇 sums up to 1. Hydra attention [Bolya et al., 2022] studies the special case where attention heads are as many as feature dimension and Q and K are normalized so that ∥Q𝑖 ∥ and ∥K𝑖 ∥ share the same value. EfficientVit [Cai et al., 2023] uses the simple ReLU function as the mapping function. FLatten Transformer [Han et al., 2023] proposes the power function as the mapping function to improve the focus capability. In this paper, we apply Softmax to matrices Q and K both in a row-wise manner to approximate the focus property of the vanilla self-attention. Empirical experiments verify its performance superiority to other mapping methods in time series anomaly detection.

3 Methods

3.1 ProblemFormulation

Let X = {x1, · · · , x𝑇} ∈ R 𝑇×𝐷 denote a set of time series with x𝑡 ∈ R 𝐷 , where 𝑇 is the time steps and 𝐷 is the number of channels. The label vector y = {𝑦1, · · · , 𝑦𝑇} indicates whether the corresponding time stamp is normal (𝑦𝑡 = 0) or abnormal (𝑦𝑡 = 1). Our task is to determine anomaly labels for all time points ˆy = { ˆ𝑦1, · · · , ˆ𝑦𝑡 }, where ˆ𝑦𝑡 ∈ {0, 1}, to match the ground truth y as much as possible. Following the practice of [Xu et al., 2022; Schmidl et al., 2022; Tuli et al., 2022; Lai et al., 2023], we mainly focus on the F1 score with point adjustment.

3.2 Sub-Adjacent Neighborhoods

Time points usually have stronger connections with their neighbors and fewer connections with distant points. This characteristic is more pronounced for anomalies [Xu et al., 2022]. As shown in Figure 1, if we rely solely on subadjacent neighborhoods to reconstruct time points, the reconstruction errors of anomalies will become more pronounced, thereby enhancing their distinguishability. This is the core idea of the Sub-Adjacent Transformer.

In this paper, we define the sub-adjacent neighborhoods as the region where the distance to the target point is between K1 and K2. 𝐾1 and 𝐾1 are the pre-defined area bounds and satisfy 𝐾2 ≥ 𝐾1 > 0. The highlighted red area in Figure 1 (b) show the sub-adjacent neighborhoods of the point marked with the red circle.

We now apply our thought to the attention matrix. The subadjacent neighborhoods are represented by the highlighted stripes in the attention matrix, as depicted in Figure 2. To focus attention on these stripes, we introduce the concept of attention contribution. This concept involves viewing the columns of the attention matrix as each point's contribution to others within the same window. Let A𝑖 𝑗 denote the element in the 𝑖-th row and 𝑗-th column of the attention matrix A. The value of A𝑖 𝑗 reflects the extent of point 𝑖's contribution to point 𝑗; the larger A𝑖 𝑗 is, the more significant the contribution. We define the sub-adjacent attention contribution of each point as the aggregate of values within the pre-defined sub-adjacent span in the corresponding column, which is

where subscript (:, 𝑖) denotes the 𝑖th column of the corresponding matrix, and win size is the window size.

The sub-adjacent attention contribution plays a pivotal role in two aspects. Firstly, it steers the focus of attention towards the sub-adjacent neighborhoods by being integrated into the loss function (Eq. 5). This is achieved by increasing SACon (A) for all points during the training stage. Secondly, it assists in anomaly detection. This is due to its incorporation into the anomaly score calculation, where anomalies typically show a lower attention contribution than normal points.

Moreover, the number of the highlighted cells in Figure 2 is lower for the marginal points (where 𝑖 < 𝐾2 or 𝑖 > win size𝐾2), leading to imbalance among points. It is mainly because the 𝑗 in Eq. 1 is bounded by 0 ≤ 𝑗 < 𝑤𝑖𝑛 𝑠𝑖𝑧𝑒. To break through this limitation, one plausible way is to use a circular shift function to calculate A𝑗𝑖 in Eq. 1:

where Q,K ∈ R win size×dmodel are the query and key matrix, respectively, ⟨·, ·⟩ represents the inner product of two vectors, Roll (Q, 𝑖 - 𝑗) cyclically shift matrix Q by 𝑖 - 𝑗 along the first dimension. The 𝑗 values in A𝑗𝑖 of Eq. 2 can satisfy the conditions 𝑗 < 0 or 𝑗 ≥ 𝑤𝑖𝑛 𝑠𝑖𝑧𝑒 and ensure that the number of 𝑗s for each 𝑖 is the same. Actually, the cyclic operation in Eq. 2 is equivalent to setting SACon � A:,𝑖 � in Eq. 1 as:

where [ 𝑗] = 𝑗 +𝑛 · 𝑤𝑖𝑛 𝑠𝑖𝑧𝑒, 𝑛 ∈ {0, ±1} such that 0 ≤ [ 𝑗] < 𝑤𝑖𝑛 𝑠𝑖𝑧𝑒. In implementation, we use Eq. 3 instead of Eq. 2 for efficiency. As shown in Figure 3(b), the use of Eq. 3 results in two extra side stripes in the attention matrix.

Linear Attention. Vanilla self-attention employs the Softmax function on a row-wise basis within the attention matrix, leading to competition among values in the same row, as depicted in Figure 3(a). In contrast, linear attention does not face such constraints. As shown in Figure 4, linear attention can be expressed as Φ (Q) Φ (K) 𝑇 V, where Φ (·) is the mapping function. As shown in Figure 3, linear attention demonstrates better attention matrix shaping capabilities. Quantitative results can be found in Table 5.

The mapping function directly impacts the focusing capability and overall performance of linear attention. Herein we introduce a novel learnable mapping function:

where Softmax is applied row-wise to the input matrix, and 𝜏 is a learnable parameter to adjust dynamically the Softmax temperature. Note that in Eq. 4, the Softmax function is applied to the matrices Q and K, rather than directly to the attention matrix, as is the case with vanilla selfattention. This distinction is fundamental to the increased flexibility of the attention matrix. Moreover, we set all negative values in the matrices Q and K to a large negative number, such as -100, to ensure that these values are close to 0 after applying the mapping function. Various mapping functions have been explored in prior research, including the power function [Han et al., 2023], column-wise Softmax [Shen et al., 2021], ReLU [Cai et al., 2023], and elu function [Katharopoulos et al., 2020]. Our empirical experiments demonstrate the effectiveness of our mapping function in time series anomaly detection, as detailed in Table 5.

3.3 Loss Function and Anomaly Score

Loss Function. Reconstruction loss is fundamental in unsupervised time series anomaly detection. As aforementioned, we also introduce the sub-adjacent attention contribution into the loss function, which guides the model to focus on the sub-adjacent neighborhoods. By integrating these two losses, the loss function for the input series X ∈ R 𝑇×𝐷 is formulated as follows:

where Lrec is the reconstruction loss and Lattn is the attention loss, λ > 0 is the weight to trade off the two terms. ∥·∥𝐹 and ∥·∥1 in Eq. 5 are the Frobenius and k-norm, respectively. ˆX ∈ R 𝑇×𝐷 denotes the reconstructed X.

Anomaly Score. To identify anomalies, we combine the sub-adjacent attention contribution with the reconstruction errors. Consistent with with the approach in [Xu et al., 2022], the Softmax function is applied to -SACon (A) to highlight the anomalies with less attention contribution. Subsequently, we perform an element-wise multiplication of the attention results and reconstruction errors. Finally, the anomaly score for each point can be expressed as

where ⊙ is the element-wise multiplication. Typically, the anomalies exhibit less attention contribution and higher reconstruction errors, leading to larger anomaly scores.

Dynamic Gaussian Scoring. Following the practice of [Schmidl et al., 2022], we fit a dynamic Gaussian distribution to anomaly scores obtained by Eq. 6 and design a score based on the fitted distribution. Let 𝜇𝑡 and 𝜎𝑡 denote the dynamic mean and standard variance, respectively, which can be computed in the way of sliding windows. Then the final score with dynamic Gaussian fitting can be computed via

where cdf is the cumulative distribution function of the standard Gaussian distribution 𝑁 (0, 1).

4 Experiments

4.1 Datasets

We evaluate the Sub-Adjacent Transformer on the following datasets, whose statistics are summarized in Table 1.

SWaT (Secure Water Treatment) [Mathur and Tippenhauer, 2016] is collected continuously over 11 days from 51 sensors located at a water treatment plant. WADI (WAter DIstribution) [Ahmed et al., 2017] is acquired from 123 sensors of a reduced water distribution system for 16 days. PSM (Pooled Server Metrics) [Abdulaal et al., 2021] is collected from multiple servers at eBay with 26 dimensions. MSL (Mars Science Laboratory rover) and SMAP (Soil Moisture Active Passive satellite) are datasets released by NASA with 55 and 25 dimensions respectively. SMD (Server Machine Dataset) [Su et al., 2019] is collected from a large compute cluster, consisting of 5 weeks of data from 28 server machines with 38 sensors. NeurIPS-TS (NeurIPS 2021 Time Series Benchmark) is a synthetic dataset proposed by [Lai et al., 2021] and includes 5 kinds of anomalies that cover pointand pattern-wise behaviors: global (point), contextual (point), shapelet (pattern), seasonal (pattern), and trend (pattern).

4.2 Implementation Details

Following the common practice, we adopt a non-overlapping sliding window mechanism to obtain a series of sub-series. The sliding window size is set as 100 without particular statements. 𝐾1 and 𝐾2 are set as 20 and 30, respectively. The choices of these parameters will be discussed later in ablation studies. The points are judged to be anomalies if their anomaly scores (Eq. 7) are larger than a certain threshold 𝛿. In this study, following the practice of paper [Lai et al., 2023; Xu et al., 2022], the thresholds are chosen to output the best F1 scores. The widely-used point adjustment strategy [Xu et al., 2022; Tuli et al., 2022; Garg et al., 2022;

Wu et al., 2023] is adopted. Note that point adjustment has its practicality: one detected anomaly point will guide system administrators to identify the entire anomalous segment. The Sub-Adjacent Transformer contains 3 layers. Specifically, we set the hidden dimension 𝑑model as 512, and the head number as 8. The hyper-parameter λ as 10 in Eq. 5 to balance recognition loss and attention loss. The Adam optimizer [Kingma and Ba, 2015] is used with an initial learning rate of 10 -4 . Following [Xu et al., 2022], the training is early stopped within 10 epochs with the batch size of 128. Experiments are conducted using PyTorch and one NVIDIA RTX A6000 GPU.

4.3 Main Results

Real-World Datasets. In Table 2, we report AUC and F1 metrics for various methods on six real-world datasets with 15 competitive baselines. The Sub-Adjacent Transformer consistently achieves state-of-the-art performance across all benchmarks, with an average improvement of 1.7 and 0.4 percentage points in F1 score over the current SOTA for singleentity and multi-entity datasets, respectively. Note that for multi-entity datasets, we combine all entities and train them together using a single model, whereas some methods, such as simple heuristics [Garg et al., 2022] and NPSR [Lai et al., 2023], train each entity separately and average the results. Even though entity-to-entity variations are large (especially MSL and SMD datasets), the Sub-Adjacent Transformer still achieves better anomaly detection results using one model than the multi-model counterpart, showing the advantage of the proposed attention mechanism. We have retained all dimensions of the original datasets, even though some of them are constant and do not play a role. Additionally, we also report F1 results without using point-adjustment in the supplementary material, where the Sub-Adjacent Transformer also exhibits competitive performance.

Synthetic Dataset. NeurIPS-TS is a challenging synthetic dataset. We generate the NeurIPS-TS dataset using the source codes released by [Lai et al., 2021], and it includes 5 anomalous types covering both the point-wise (global and contextual) and pattern-wise (shapelet, seasonal and trend) anomalies. As shown in Table 3, the Sub-Adjacent Transformer achieves state-of-the-art performance with an astonishing 9.1 percentage points improvement of F1 score relative to Anomaly Transformer [Xu et al., 2022], demonstrating the effectiveness of the proposed model on various anomalies. Visualization results can be found in Figure 5. We can see that anomalies do have less sub-adjacent contribution (the third column), which is consistent with our assumption. A full version of Figure 5 can be found in the supplementary material.

4.4 Ablation Studies

Vanilla and Linear Transformer. We compare vanilla self-attention and linear attention with different mapping functions using our method. As shown in Table 5, the proposed Softmax-based mapping function with learnable parameters outperforms other mapping functions and vanilla self-attention, with a maximum F1 score increase of 1.5 percentage points.

Choices of 𝐾1 and 𝐾2. Choices of 𝐾1 and 𝐾2 directly affect the performance of the Sub-Adjacent Transformer. We evaluate the effect in Table 4 with the window size being 100. The configuration of 𝐾1 = 20 and 𝐾2 = 30 typically yields the best performance (with the exception of the SMD dataset), while the performance of other settings is also satisfactory, with nearly half of the values exceeding the current SOTA. When the sub-adjacent span is getting close to the diagonal (the second and third rows in Table 4), the performance worsens. We also explore the extreme case where 𝐾1 = 𝐾2 = 0. In that case, the performance drops significantly, highlighting the importance of sub-adjacent attention.

Module Ablation. We evaluate the contribution of linear attention module and dynamic scoring module in Table 6. For the Sub-Adjacent Transformer, the baseline means the proposed sub-adjacent attention mechanism accompanied with vanilla self-attention and anomaly score (Eq. 6). Then linear attention and Gaussian dynamic scoring (Eq. 7) are introduced in turn. As shown in Table 6, compared with the baseline, linear attention brings +1.0 improvement on average over six datasets and Gaussian dynamic scoring brings another +0.2 improvement, verifying the effectiveness of the proposed modules.

Furthermore, we also apply the two modules to Anomaly Transformer [Xu et al., 2022]. As we can see from Table 6, the proposed linear attention model provides +1.2 percentage points performance gain averagely, and Gaussian dynamic scoring provides another +0.1 gain. Moreover, as shown in Table 6, without the support of linear attention and dynamic Gaussian score, our method (baseline) still outperforms the Anomaly Transformer by an average of +1.8 percentage points, thereby validating the efficacy of our subadjacent attention design.

Choices ofWindow Size. Table 7 gives F1 values with different window sizes for six datasets. One can see that our model exhibits good robustness to the window size. The optimal performance is typically achieved with a window size of 100, the only exception being the SWaT dataset.

Choices of Parameter λ. Table 8 compares the performance for different values of λ. The best results are achieved when λ is set to 10, while the second-best results occur at different values of λ for different datasets. It is noteworthy that without the inclusion of attention loss (λ = 0), performance drops drastically, affirming the effectiveness of our sub-adjacent attention design.

5 Conclusion

In this paper, we present the Sub-Adjacent Transformer, a novel paradigm for utilizing attention in time series anomaly detection. Our method distinctively combines sub-adjacent attention contribution, linear attention and reconstruction error to effectively detect anomalies, thereby enhancing the efficacy of anomaly detection. It offers a novel perspective on the utilization of attention in this domain. Without bells and whistles, our model demonstrates superior performance across common benchmarks. We hope that the Sub-Adjacent Transformer could act as a baseline framework for the future works in time series anomaly detection.

Acknowledgments

This work was supported by the National Science Foundation of China (NSFC) (No. 62371009 and No. 61971008).