[paper review]Multivariate Time-series Anomaly Detection via Graph Attention Network

Abstract

Introduction

1. Malhotra et.al은 LSTM 기반의 encoder - decoder network를 제시하고, multiple sensor들에서 에러를 디텍팅하는데 사용

2. Hundman et. al은 prediction error를 기반으로 한 다변량 시계열 이상치 탐지 연구를 진행

3. OmniAnomaly는 stochastic recurrent neuarl network를 사용, latent variable을 활용하여 다변량 시계열 modelling data 분포의 normal pattern을 획득

4. 위 3개의 예시와 같이 시계열 이상치 탐지를 위해, 변수간 관계를 파악하는 것이 중요

솔루션

contribution

1. self-supervised 를 통해 multivariate-time series 문제를 다루어 당시 SOTA score 달성

2. 2개의 parallel 한 graph attention (GAT)를 활용하여 다른 time-series와 timestamp의 relationship을 이전의 정보가 불필요한 상태에서 찾음

3. forecasting(single time-stamp prediction 에 목적) 과 reconstruction(entire time-series 의 latent representation 에 목적) 기반의 모델을 joint optimizing 함

4. 해석 가능하고, 직관적인 attention score 사용

Related work

1. Univariate Anomaly Detection
1. Hypothesis testing, waveltet analysis, SVD, ARIMA
2. Netflix : PCA를 통한 이상치 탐지
3. Twitter : Seasonal Hybrid Exteme Study Deviation test
4. DONUT : unsupervised anomaly detecion method based on Cariational Auto Encoder and SR-CNN

2. Multivariate Anomaly Detection
1. Forecasting-based Models : prediction error 를 통해 이상치 탐지
1. LSTM-NDT : unsupervised 및 non-parametric thresholding을 제시
2. Ding et. al : Hierarchical Temporal Memory(HTM) and Bayesian Netwrok 기반 real-time 이상치 탐지 알고리즘
3. Gugulothu et. al : non-temporal dimension reduction 및 recurrent auto-encoder를 통해 end to end learning framework 제시
4. DAGMM : temporal dependency를 고려하지 않고 이상치 탐지 고려하여 단지 전체의 observation을 인풋으로 함
2. Reconstruction-based Models : Latent variable을 통해 entire time-series를 복원하도록 학습
1. Pankaj et. al : LSTM-based Encoder-Decoder framework로 normal 시계열 data의 representation 학습
2. Kitsune : unsupervised로 feature를 instance로 mapping을 하고 decoder를 통해 reconstruction
3. MAD-GAN : entire variable set 을 고려하여 latent interactions를 capture
4. GAN-Li : GAN으로 학습된 discriminator에 실제와 fake를 넣어 residuals을 만듦
5. LSTM-VAE : LSTM을 variational auto-encoder에 integrates 하여 singals를 fuse 하고 분포를 재구성, temporal dependencies를 latent space에 LSTM encoder를 통해 압축
6. OmniAnomaly : deterministic method로 unpredictable instances 때문에 실수할 가능성이 높으므로 stochastic model을 제시하여 다변량 시계열 이상치탐지를 진행함. 정상 pattern을 stochastic variable connection과 plannar normalizing flow를 통해 normal pattern 을 capture함

Methodology

1. overview



1. 첫번째 레이어에 1-D convolution을 커널 사이즈 7을 활용하여 고차원의 feature 추출함
2. 과정 1의 feature를 2가지 GAT layer에 input으로 사용
3. 2 GAT layer output을 concatenate 한 뒤 GRU 에 feed
4. GRU output을 forecasting 과 reconstruction model에 넣어서 final result를 도출
 

2. Data Preprocessing
1. Data normalization
2. Data cleaning
1. Spectral Residual
FFT 활용하여, 각 윈도우 내의 신호에서 평균 spectrum을 빼고, 역변환하여 Saliency Map 생성
SR-CNN처럼, Saliency Map의 일정 threshold 이상인 값을 anomaly로 라벨링
해당 라벨이 붙은 값은 주변 값으로 imputation하여 cleaning
 

3. Graph attention





1. Feature-oriented graph attention layer
1. 다변량의 시계열을 graph로 다루고, 각 node는 특정 feature를 represent
2. 각 edge는 2개의 상호작용 feature의 relationship
3. 각 노드 xi = {xi,t|t ∈ [0, n]} 이므로, k 노드가 있고, timestamp의 수는 n, k는 mulicariate features의 수
2. Time-oriented graph attention layer
1. temporal dependency를 capture하기 위해 사용, 모든 타임스탬프를 슬라이딩하여 complete graph화
2. node xt는 time stamp t에서의 feature vector를 나타내며 주변의 노드는 현재 슬라이딩 윈도우의 모든 타임스탬프를 포함
3. 최종적으로 feature oriented graph attention layer의 아웃풋 (kxn의 행렬)과, time-oriented graph attention layer의 아웃풋 (nxk의 크기)과, 원본 input을 concatenate하여 nx3k의 크기의 final node feature 생성
4. GRU를 사용하여 final node feature를 Joint Optimization (forecasting, Reconstruction)
 

4. Joint Optimization
1. Forecasting-based model



1. 다음 시점의 값을 예측하도록 학습
2. anomaly score를 산출 할 때, 변화에 민감하게 반응
 
2. Reconstruction-based model



1. a의 데이터 변화에 대한 강건성 문제 완화
2. input 데이터의 분포 추정
3. b만 사용할 경우 이상치가 학습된 분포 안에 포함될 때 포착 불가
 
3. Model Inference



((예측값과 실제값의 차이) ** 2 + * (reconstrction based model 에서 abnormal 확률)) / 1+

Experiments

1. Datasets
SMAP (Soil Moisture Active Passive satellite) MSL (Mars Science Laboratory rover) TSA (Time Series Anomaly detection system) *

2. Metrics
precision, recall and F1-score, AUC scores

3. Setup
1. window size = 100
2. 은 grid search를 통해 설정 (0.8)
3. adam, 100 epoch, 0.001 learning rate

4. Comparison with SOTAs

5. Evaluation with Different Delays
delay delta 가 10일때 53.98%, 13.04%, 19.93% 의 차이를 보임

Analyses

1. Effectiveness of Graph Attention

2. Effectiveness of Joint Optimization



Forcasting based model은 시계열의 랜덤성에 강건하고, Reconstruction based model은 잡음, 데이터 변화에 강건하여, joint optimization하는 것이 f1 score 가 높고, anomaly detection에 효과적임을 입증

3. Analysis of

Case Study

1. 단변량일 경우 몇몇 feature를 이상치로 탐지 했겠지만, 본 모델은 feature를 종합적으로 고려했을 때, 전체 노드간의 상관관계가 변하지 않았기에 정상으로 분류했고, 실제 정상인 경우

2. 다른 feature는 정상이지만,Checkpoint와 CPU가 비정상 패턴을 보이고, 그 패턴이 학습된 적이 없기에 정상 상황임에도 이상치로 오분류한 경우

Conclusion