본 글은 논문 [Graph Neural Network-Based Anomaly Detection in Multivariate Time Series(2021)]을 바탕으로 graph based time series anomaly detection 방법론인 Graph Deviation Network(GDN)에 대해 설명하고자 합니다.
▶ Multi-variate Time series
시계열(time series) 데이터는 시간의 흐름에 따라 순차적으로(sequentially) 기록된 데이터입니다.
- 일변량 시계열 데이터(univariate time series)는 변수가 1개인 시계열 데이터를 의미합니다.
- 다변량 시계열 데이터(multivariate time series)는 변수가 여러 개인 시계열 데이터를 의미합니다.
실제 다변량 시계열 데이터는 복잡(complex)한 고차원(high dimension) 데이터입니다. 공장을 예시로 들면, 수 많은 센서(변수)가 존재하며 각 센서(변수)에는 많은 양의 시계열 데이터가 존재하며 센서(변수)들끼는 서로 비선형 관계를 가지고 있습니다. 먼저 기존의 multi-variate time series model을 소개하고 기존 방법론이 갖고 있는 문제점에 대해 설명하겠습니다.
- [Multi-variate time series model]
- Classical method: Auto Regressive(AR) model, Auto-regressive integrated moving average(ARIMA) model
- Deep Learning based method: Convlutional Neural Network(CNN), Long Short Term Memory(LSTM), Generative Adversarial Networks(GAN)
- Graph based method: Graph Convlutional Neural Network(GCN), Graph Attention Network(GAT)
AR 또는 ARIMA 모델의 경우 과거 데이터를 기반으로 선형 모델(linear model)을 학습하기 때문에 복잡한 비선형 특성을 가진 시계열 데이터의 경우 적합하기에는 어렵습니다. 딥러닝 기반 모델인 CNN, LSTM, GAN 등은 복잡한 비선형 특성을 가진 고차원의 시계열 데이터에 우수한 성능을 보이지만 서로 다른 다양한 시계열 패턴을 가진 변수들간의 관계를 명백하게 학습하지 않습니다. 그래프 기반 모델의 경우 변수들간의 관계를 모델링하지만 존재하는 방법론들은 모두 stationary time series를 기반으로 디자인되어 non-stationary time series를 적합하는데 한계가 존재합니다.
※ Stationary time series(정상 시계열)이란, 어느 시점 $t$에 관측해도 확률 과정의 성질($E[X_t], Var[X_t]$)이 변하지 않는 데이터입니다.
▶ Anomaly detection
이상치 탐지(Anomaly detction)은 대다수의 정상 데이터로부터 비정상 데이터를 탐지하는 방법으로 비지도 학습(unsupervised learning) 방법론입니다. 이상치 탐지 방법론은 크게 다음 4가지로 나누어 볼 수 있습니다.
- [Anomaly Detection model]
- Linear model based approach
- Distance based approach
- One class method based on SVM
- Deep Learning baed technique: Auto-encoder(AE), Geneartive Adversial Networks(GAN), LSTM
[Method 1]~[Method 3]의 경우 센서들 간의 관계를 단순한 방식으로 모델링하며 [Method 4]는, 고차원 데이터에서 이상치 탐지에 우수한 성능을 보이지만 센서들간의 관계를 명백하게 학습하지 않습니다.
논문의 저자는 기존의 multi-variate time series 모델과 anomaly detection 모델의 한계점에 대해서 공통적으로 변수들간의 관계를 모델링하지 않는다는 점을 지적합니다. 논문에서는 다음 2가지의 질문을 바탕으로 새로운 모델 Graph Deviation Network(GDN)을 제안하였습니다.
- Question1: How can we detect anomalies events given high dimensional time-series data?
- Question2: How can we do this in a way that captures complex inter-sensor relationships and detects and explains anomalies which deviate from these relationships?
GDN은 고차원 시계열 데이터에서 변수들 간의 관계 학습을 위해 graph neural network를 도입하였으며 탐지된 비정상 객체에 대해서 설명력(explainability)를 제공하기 위해 attention weights를 사용합니다.
0. Background
GDN에 대해 본격적으로 설명하기에 앞서 graph(그래프)에 대해 간단하게 설명하겠습니다.
▶ Graph란?
- 초록색 원 $V$: node, vertices
- 검은색 선 $E$: edge
Graph $(V, E)$란, 방향성이 있거나(directed) 없는(undirected) 엣지(edge)로 연결된 노드(node, vertices)의 집합입니다.
$$G = (V,E)$$
- $V = \{v_i\}_{i=1,\cdots,p}, \, v_i \in \mathbb{R}^n$: node의 집합
- $E=\{e_{ij}\}$: edge의 집합
※ [참고] 논문에서는 센서들 사이의 dependency pattern이 꼭 대칭(symmetric)일 필요는 없기 때문에 undirected graph를 사용하지 않고 directed graph를 사용합니다.
▶ Adjacency matrix란?
그래프 구조(graph structue)는 adjacency matrix(인접행렬) $A \in \mathbb{R}^{p \times p}$로 표현가능합니다.
$$A = \begin{cases} 1 &\text{if } (v_i,v_j) \in E \\ 0 &\text{if } (v_i,v_j) \notin E \end{cases}$$
두 노드 사이에 엣지가 존재하는 경우($(v_i,v_j) \in E$), 1 아니면 0인 원소를 갖는 행렬입니다.
▶ Graph Neural Network(GNN)
Graph Neural Network(GNN)은 graph structured data에서 복잡한 패턴을 모델링하는데 우수한 성능을 보였으며 각 노드의 상태는 이웃 노드의 상태에 영향을 받는다고 가정합니다. GNN의 대표 모델에는 GCN, GAT가 존재합니다.
- Graph Convolution Network(GCN)은 이웃 노드의 representation vector(embedding vector)에 동일한 가중치를 부여함으로써 타겟 노드의 feature representation을 학습합니다.
- Graph Attention Network(GAT)는 이웃 노드의 representation vector(embedding vector)에 서로 다른 가중치(attention score)를 부여함으로써 타겟 노드의 feature representation을 학습합니다.
1. Proposed Framework
▶ Main challenge
다변량 시계열 데이터 기반 이상치 탐지에 graph neural network(GNN)을 사용할 때 주된 문제점(main challenge) 2가지가 존재합니다.
- 기존 GNN의 경우 각 노드의 행동 혹은 특성을 모델링할 때 모든 노드에 대해서 같은 파라미터를 사용해 학습합니다.
- 하지만, 서로 다른 시계열 패턴을 가진 변수(노드)들은 서로 다른 파라미터로 모델링해야합니다.
- 기존 GNN의 경우 입력 데이터에 그래프 구조(→ 인접행렬 $A$)를 사용합니다.
- 노드간의 관계 정보(그래프 구조에 대한 정보)가 대부분 없기 때문에 그래프 구조 $A$에 대한 추정이 필요합니다.
▶ Graph Deviation Framework
노드간의 관계를 그래프를 통해 학습하고 다변량 시계열 데이터 기반 이상치를 탐지하는 GDN은 2가지의 주된 문제점을 반영하였으며 크게 4가지의 구성 요소로 이루어집니다.
- Sensor(Node) Embedding: 각 노드의 고유한 특성(unique characteristics) 값을 갖는 임베딩 벡터(embedding vector) $v_i, \, i \in \{1,2,\cdots, N\}$를 학습하는 단계
- Graph Structure Learning: 학습된 노드 임베딩 벡터 $v_i$를 바탕으로 노드간의 관계를 학습하는 단계(→ 인접행렬 $A$를 학습하는 단계)
- Graph Attentional Based Forecasting: 학습된 노드 임베딩 벡터 $v_i$와 인접행렬 $A$를 기반으로 이웃 센서의 정보와 타겟 정보를 종합할 때 attention mechanism을 사용함으로써 시점 $t$에 대한 타겟 정보의 값을 예측하는 것을 학습하는 단계
- Graph Deviation Scoring: 학습된 노드간의 관계를 바탕으로 이상치를 탐지하고 설명하는 단계
1.1 Problem Setup
훈련 데이터셋과 검증 데이터셋은 모두 다변량 시계열 데이터로 총 $N$개의 노드가 존재하며 각 노드는 시계열 데이터를 갖고 있습니다.
▶ Training dataset(훈련 데이터셋)
$$s_{train} = [s^{(1)}_{train}, s^{(2)}_{train}, \cdot, s^{(T_{train})}_{train}], \, s^{(t)}_{train} \in \mathbb{R}^N$$
- 각 time $t\in \{1,2, \cdots, T_{train}\}$에는 총 $N$개의 노드(센서)가 존재합니다.
- 각 노드(센서)에는 총 $T_{train}$개의 시계열 데이터가 존재하며 서로 다른 다양한 시계열 패턴을 갖고 있습니다.
비지도 이상치 탐지 방법론에 따라 훈련 데이터셋의 경우 모두 정상 데이터로 구성되어 있다고 가정합니다.
▶ Test dataset(검증 데이터셋)
우리는 검증 데이터셋에서 비정상 객체를 탐지할 것입니다.
- 입력 데이터(input data): $s_{test} = [s^{(1)}_{test}, s^{(2)}_{test}, \cdot, s^{(T_{test})}_{test}], \, s^{(t)}_{test} \in \mathbb{R}^N$
- 출력 데이터(output data): $a(t) \in \{0, 1\}$(binary labels)
$a(t) = \begin{cases} 1 &\text{if, time t is anomalous} \\ 0 &\text{otherwise}\end{cases}$
1.2 Sensor(Node) Embedding
▶ Idea
서로 다른 노드는 서로 다른 고유한 특성을 갖고 있으며 서로 복잡한 관계를 가지고 있습니다. 이 아이디어를 기반으로 sensor(Node) embedding 학습 단계에서는 각 노드가 갖고 있는 고유한 특성을 추출하는 것이 목표입니다.
▶ Notation
$$u_i \in \mathbb{R}^d, \, \text{ for } i \in \{1,2,\cdots, N\}$$
$u_i$는 각 노드의 임베딩 벡터로 $d$차원으로 이루어져 있습니다($d$: hyper-parameter). 임베딩 벡터의 초기값 $u_i^{(0)}$은 랜덤하게 초기화 된 후 학습이 이루어집니다. 학습된 임베딩 벡터 값이 서로 비슷한 노드들은 비슷한 시계열 패턴 혹은 행동을 갖고 있다는 것을 의미합니다. GDN에서는 학습된 임베딩 벡터를 다음 2가지에 활용합니다.
- Graph structure learning: 값이 비슷한 임베딩 벡터를 가진 노드들은 서로 연결될 가능성이 높다는 아이디어를 기반으로 그래프 구조를 학습합니다.
- Attention Mechanism: 이웃 노드의 정보를 종합(aggregate)하는 과정에 있어 각 이웃 노드에 서로 다른 가중치(attention score)를 부여합니다. 이 때 학습된 임베딩 벡터의 유사성을 기반으로 attention score를 계산합니다.
자세한 내용은 [Section 1.3]과 [Section 1.4]에서 살펴보도록 하겠습니다.
1.3 Graph Structure Learning
Graph structure learning 단계에서 주 목적은 학습된 임베딩 벡터 $u_i, \, i \in \{1,2,\cdots, N\}$를 바탕으로 그래프 구조 $A$를 학습하는 것입니다.
▶ Candidate relationship set $C_i$
앞서 크게 2가지의 경우에 대해 생각해 볼 수 있습니다
- 그래프 구조에 대한 사전 정보(prior information)가 존재하는 경우
- 그래프 구조에 대한 사전 정보(prior information)가 존재하지 않은 경우
[Prior information O]
그래프 구조에 대한 사전 정보가 존재하는 경우 각 node $i$마다 candidate relationship 집합 $C_i$은 다음과 같이 정의합니다.
$$C_i \subseteq \{1,2,\cdots,N\} \backslash \{i\} \tag{1}$$
식 $(1)$을 통해 self-loop(자기 자신과의 연결)는 고려하지 않는다는 사실도 알 수 있습니다.
[Prior information X]
그래프 구조에 대한 사전 정보가 존재하지 않은 경우는 자기 자신을 제외한 모든 노드가 candidate relation 집합 $C_i$에 포함됩니다.
$$C_i = \{1,2,\cdots,N\} \backslash \{i\}$$
▶ Form a graph structure
각 node $i$와 이웃 후보 집합 $C_i$에 속하는 $j \in C_i$와의 연결 여부(dependency)를 결정짓기 위해 각 노드의 학습된 임베딩 벡터를 사용합니다.
$$e_{ij} = \dfrac{u_i^T u_j}{||u_i|| \cdot ||u_j||} \text{ for } j \in C_i \tag{2}$$
$$A_{ij} = \mathbb{1} \{j \in TopK(\{e_{ki}: k \in C_i\})\} \\ \text{ TopK: hyperparameter}\tag{3}$$
식 $(2)$는 node $i$와 $j \in C_i$의 임베딩 벡터 $u_i, \, u_j$ 사이의 유사도를 내적을 통해 계산한 값입니다(분모: normalization term).
식 $(3)$을 통해 타겟 노드 $i$의 모든 이웃 노드 $j \in C_i$에 대하여 유사도 $e_{ij}$ 값을 상위 TopK에 대해서만 $1$, 그 외의 노드에 대해서는 $0$을 부여함으로써 인접 행렬 $A$를 정의 및 학습하는 것을 알 수 있습니다.
1.4 Graph Attention-Based Forecasting
Graph Attention-based forecasting 단계에서는 학습된 임베딩 벡터 $v_i$와 인접 행렬 $A$를 바탕으로 비정상 객체를 판단하는 단계입니다. 지난 과거 데이터를 기반으로 각 시간 $t$별 각 sensor별의 값을 예측하는 forecasting-based 접근법으로
graph attention 방법을 사용합니다.
▶ Notation
- Input data: $\mathbf{x}^{(t)} = [s^{(t-w)}, s^{(t-w+1)}, \cdots, s^{(t-1)}] \in \mathbb{R}^{N \times w} $
- 크기가 $w$인 sliding window에 속하는 시점 $t$ 이전의 데이터
- output data: $\hat{s}^{(t)}$
- 현재 시점 $(t)$에 대한 예측값
▶ [$1^{st}$ layer] Graph attention based feature extractor layer
노드간의 관계를 이용하기 위해 학습된 그래프 구조 $A$를 바탕으로 타겟 노드 $i$와 이웃 노드 $j \in N_i$의 정보를 종합하는데 graph attention based feature extractor 방법을 도입하였습니다. 기존의 graph attention mechanism과는 다르게 GDN에서는 학습된 노드 임베딩 벡터 $v_i$도 함께 활용하여 attention score를 계산합니다([Figure 2-(b)] 참조).
[Attention score 계산]
$$\mathbf{g}^{(t)}_i = v_i \bigoplus Wx^{(t)}_i \tag{4}$$
$$\pi(i,j) = LeakyReLU(a^T(\mathbf{g}^{(t)}_i \bigoplus \mathbf{g}^{(t)}_j)) \tag{5}$$
$$\alpha_{i,j} = \dfrac{exp(\pi (i,j))}{\sum_{k \in N_i \cup \{i\}} exp(\pi(i,k))} \tag{6}$$
- $a$: vector of learned coefficients for the attention mechanism
식 $(4)$에서 $\bigoplus$는 concatenation을 의미합니다. 즉, $\mathbf{g}^{(t)}_i$는 노드 임베딩 벡터 $v_i$와 input feature를 선형변환한 $Wx^{(t)}_i$를 concatenate한 값입니다. 식 $(5)$에서는 타겟 노드 $i$와 이웃 노드 $j$의 유사도를 계산하는 식으로 유사도 함수는 1-layer feed foward network를 사용하였습니다. 식 $(6)$은 최종 attention score 값으로 normalization(정규화)를 수행하기 위해 softmax function을 사용한 것을 알 수 있습니다.
[$z^{(t)}_i$: node $i$'s aggregated representation vector]
$$z^{(t)}_i = ReLU(\color{darkred}{\alpha_{i,i}} Wx^{(t)}_i + \sum_{j \in N_i}\color{darkred}{\alpha_{i,j}}Wx^{(t)}_j) \in \mathbf{R}^{d \times 1}$$
- $x^{(t)}_i \in \mathbb{R}^w$: 시점 $t$ 이전의 데이터로 노드 $i$의 input feature
- $N_i = \{j| A_{i,j} > 0\}$: 학습된 인접 행렬 $A$로부터 얻어진 노드 $i$의 이웃 노드 집합
- $W \in \mathbb{R}^{d \times w}$: 모든 노드의 선형 변환에 사용되는 trainable weight matrix
- $\alpha_{i,j} \, j \in N_i$: attention score
계산한 attention score $\alpha_{i,j}$를 바탕으로 타겟 노드 $i$의 정보와 이웃 노드 $j \in N_i$의 정보를 종합한 $z^{(t)}_i$를 학습할 수 있습니다.
우리는 각 노드마다 서로 다른 파라미터로 학습하고자 이와 같은 layer를 총 $N$개 쌓습니다.
▶[$2^{nd}$ layer] Output Layer
우리는 feature extracter layer로부터 $N$개의 aggregated representaion vector $\{z^{(t)}_1, \cdots z^{(t)}_N\}$를 얻을 수 있습니다. Output layer의 각 $z^{(t)}_i$에 상응하는 노드 임베딩 벡터 $v_i$와의 elementwise multiply($\circ$) 값을 입력으로 받아 stacked fully connected layer $f(\cdot)$을 통해 output $\hat{s}^{(t)}$을 산출합니다.
$$\hat{s}^{(t)} = f([v_1 \circ z^{(t)}_1, \cdots, v_N \circ z^{(t)}_N]) \in \mathbb{R}^{N \times 1}$$
▶ Loss Function
손실함수는 예측 값 $\hat{s}^{(t)}$과 실제값 $s^{(t)}$의 차이를 비교하고자 Mean Squared Error를 사용하였습니다.
$$L_{MSE} = \dfrac{1}{T_{train}-w} \sum^{T_{train}}_{t=w+1} || \hat{s}^{(t)} - s^{(t)}||^2 _2$$
1.5 Graph Deviation Scoring
훈련 데이터로 학습한 GDN 모델을 기반으로 검증 데이터셋에서는 이상치 여부를 판단해야 합니다. 논문에서는 graph deviation scoring 방법을 제안합니다.
1. 각 노드에 대한 개별적인 anomalousness score를 계산합니다.
$$Err(i) = |s^{(t)}_i - \hat{s}^{(t)}_i|$$
서로 다른 특성을 갖고 있는 노드들은 매우 다른 범위를 갖기 때문에 $Err_i(t)$의 평균 및 분산 대신 더 robust한 중앙값과 IQR 값을 사용하여 정규화를 수행하였습니다.
$$a_i(t) = \dfrac{Err_i(t) - \tilde{\mu}_i}{\tilde{\sigma}_i}$$
- $\tilde{\mu}_i$: $Err_i(t)$의 중앙값
- $\tilde{\sigma_i}$: $Err_i(t)$의 inter-quartile range(IQR^2) 값
2. 각 시간 $t$에서 계산된 $a_i(t)$를 종합하여 하나의 anomalousness score를 산출합니다.
$$A(t) = \max_i a_i(t)$$
각 시간별 하나의 anomalousness score를 산출하는데 max function을 사용했으며 만약 $A(t) > \tau$이면 시간 $t$에서 노드 $i$의 객체는 비정상인 것으로 판단합니다. $\tau$는 사용자가 임의로 지정해주는 임계값입니다.
Section 1을 토대로 GDN의 경우 각 노드별 임베딩 벡터 및 그래프 구조를 학습함으로써 특정 시간 $t$에 대한 행동을 예측함으로써 실제 값과 예측 값의 차이를 토대로 anomaly score를 산출합니다. 논문의 저자가 강요했던 변수간의 관계를 graph attention mechansim을 통해 모델링을 하였습니다. 다음 글에서는 GDN의 단점을 지적하며 새로운 방법론을 제안한 MTAD-GAT에 대해 살펴보고자 합니다.
