今回は、GAT(Graph Attention Network)を利用した異常検知手法であるGDN(Graph Deviation Network)について解説します。
GDNは2021 年にAAAIで発表された Graph Neural Network-Based Anomaly Detection in Multivariate Time Series 手法で、2022年現在140件以上引用されており、この手の異常検知手法の中ではそれなりに影響力のある手法となっています。
今回は、このGDNについて解説します。よく巷では論文解説記事で、理論面について詳しく解説する記事は多くありますが、実装まで踏み込んだ解説はあまりないので、今回はGDNの実装にまで踏み込んで解説していきます。
実装には、Pytorchの関連ライブラリである pytorch geometricを利用しています。
手法としての肝は、多変量センサーデータをEmbeddingを用いた分散表現を取り入れ、GATを用いて異常検知をしている点です。
実装面で少し難易度が高いのが、GNNの汎用的なフレームワークであるMPNNを用いたMessage Passingを用いたモデルの実装あたりですので、そのあたりを重点的に解説していきます。
解説と言っても深層学習初心者なので、厳密な内容よりは、分かりやすさを重視して解説していきます。
GDNの手法の解説
論文にもありますが、GDNでは主に次の4つの要素から構成されます。
- Sensor Embedding
- Graph Structure Learning
- Graph Attention-Based Forecasting
- Graph Deviation Scoring
このうち、上2つのSensor EmbeddingとGraph Structure Learningで、センサー間の依存関係を学習し、下2つのGraph Attention-Based Forecasting とGraph Deviation Scoring で、センサー値を予測し、異常なセンサーを特定する流れとなっています。
また4つの要素から構成されていますが、これらは1つのニューラルネットでEndToEndで実装されています。
以降で、それぞれの内容について、1つずつ丁寧に解説していきます。
1. Sensor Embedding
先ほど、センサー間の依存関係を最初に学習すると書きましたが、ここでは、多変量多変量時系列データをEmbedding(埋め込み)して、センサーの特徴を残したまま、低次元に次元削減しています。
センサー$i$のEmbedding後のベクトルを次のように表現しています。
\begin{equation}
\bm{v}_i \in \mathbb{R}^{d}, ~~ \operatorname{for} ~~ i \in \{ 1, 2, \dots, N \}
\end{equation}これらの埋め込み表現は、初期化されていますが、モデルの後半で訓練されるとしています。
後半で解説しますが、(1)で示される センサーの埋め込み表現$\bm{v}_i$は、全結合層によるパラメータ$\bm{W}$を学習することで、訓練されます。
実装レベルでは、pytorchのnn.torch.Embeddingを用いていますが、後ほど詳細に解説します。
この埋め込みしたベクトル$\bm{v}_i$を、後続のGraph Structure Learningでセンサー間の依存関係を学習します。
2. Graph Structure Learning
続いて、Graphの構造学習です。ここでは、センサーデータ間の依存関係をグラフ構造として得ることが目的です。
GDNの手法では、有向グラフを用いて、センサーデータの依存関係を整理しています。あるノード$i$とノード$j$に対し、エッジがある場合、ノード$j$の情報を表現するのに、ノード$i$の情報を利用できる関係性の時に、このようなエッジが引かれます。
この有向グラフを$A$としたとき、$A_{ij}$成分が1になっているとき、ノード$i$からノード$j$に対して、エッジがあることを示しています。この辺りは隣接行列の説明です。
またセンサー間の依存関係が事前にわかっている場合は、candidate relation$\mathcal{C_i} \in {1, 2, \cdots, N } \backslash { i}$を用いて、このように依存関係を表現します。
ここで、センサー$i$における類似度を次のように定義します。
$\bm{v}$がセンサー値の埋め込み表現であることは学びましたね。
\begin{equation}
e_{ji} = \frac{\bm{v_i}^T \bm{v_j}}{|\bm{v_i}| \cdot |\bm{v_j}|} ~~ \operatorname{for} ~ j \in \mathcal{C}_i
\end{equation}このセンサー値の類似度$e_{ji}$を計算し、上位K個のセンサーに依存関係があるとして、隣接行列を次のように設定します。
\begin{equation}
A_{ji} = 1 \operatorname{if} \{ j \in TopK(\{ e_{ki}: k \in \mathcal{C}_i\})\}
\end{equation}ここまでで、グラフ構造の決定までできました。
要約すると、多変量センサーデータを埋め込み表現し、その埋め込みベクトルが類似しているK個のセンサーを依存関係があるとして、隣接行列$A$を設定するということでした。
3. Graph Attention-Based Forecasting
ここまでで、センサー間の依存関係を得ることができたので、続いて予測モデルの実装に入っていきます。ここで実際にGAT(Graph Attention Network)を利用していきます。
GATについてはこちらで詳しく解説しているので、ぜひご覧ください。
ここでは、特徴抽出層(Feature Extraction Layer)と出力層(Output Layer)から構成されます。
まず、Feature Extraction Layerから見ていきます。
特徴抽出層
ここで、モデルの入力としては、sliding window幅を$w$とした時、$\bm{x^{(t)}} \in \mathbb{R}^{N \times w}$です。よくあるように、全センサーの値に対して、sliding windowで区切って入力として与えています。
sliding window幅を$w$とした時、時刻tにおけるセンサーデータは次のようになっている。
\begin{equation}
\bm{x^{(t)}} \in \mathbb{R}^{N \times w}
\end{equation}ここで、本手法では、GATに$\bm{v}_i$と隣接行列$A$を使います。
GATにおけるノード$i$の集約表現(aggregated representation) $\bm{z}_i$は、次のように定義しています。
\begin{equation}
\bm{z_i}^{(t)} = \operatorname{ReLU}
\biggl (
\alpha_{i, i} \bm{W} \bm{x_i}^{(t)}
+ \sum_{j\in\mathcal{N(i)}} \alpha_{i. j} \bm{W}\bm{x_i}^{(t)}
\biggr)
\end{equation}ここで、$\bm{x_i}^{(t)}$は、時刻$t$におけるセンサーデータの入力であり、$\mathcal{N}(i)$は、センサー$i$と依存関係があるセンサー$j$の集合で、数式で表現すると次のようなものである。
\mathcal{N}(i) = \{ j | A_{ji} > 0\}また、$\bm{W}$は学習パラメータです。
いよいよ難しくなってきましたね。GATの数式に慣れていないと難しく感じるかもしれませんが、$W$はGNNでよく登場する、ノード特徴量を変換する重みベクトルです。
また、(5)式に登場する$\alpha_{i. j}$はアテンション係数で次式で計算されます。
\begin{equation}
\begin{split}
\bm{g_i}^{(t)} &= \bm{v_i} \oplus \bm{W} \bm{x_i}^{(t)} \\
\pi(i, j )& = \operatorname{LeakyReLU}(\bm{a}^T (\bm{g_i}^{(t)} \oplus \bm{g_j}^{(t)})) \\
\alpha_{i. j} &= \frac{exp(\pi(i, j ))}{\sum_{k \in \mathcal{N}(i) \cup \{ i\} } exp(\pi(i, k ))}
\end{split}
\end{equation}ここで、オペレータ$\oplus$は、ベクトルの連結(concatenation)です。
(6)式でGATの畳み込みレイヤーの計算までできました。最後に、OutPutLayerで出力値を得ます。
出力層(Output Layer)
続いて、出力層に入っていきます。特徴抽出の(5)式と、アテンション係数(6)式によって、各ノードの抽象表現$\bm{z_i}$が得られました。
ここで、最後の出力の値を$\bm{\hat{s}^{(t)}}$とすると、$\bm{\hat{s}^{(t)}}$は次のように計算されます。
$f_{\theta}$を全結合層の非線形関数とした時、モデルの出力$\bm{\hat{s}^{(t)}}$は次式で定義する。
\begin{equation}
\bm{\hat{s}^{(t)}} = f_{\theta}
\biggr(
\biggr[
\bm{v_i} \circ \bm{z_i}^{(t)}, \dots, \bm{v_N} \circ \bm{z_N}^{(t)}
\biggl ]
\biggl)
\end{equation}となっています。(7)式がモデルの出力となります。
ここで、$\circ$はアダマール積です。
これがモデルの出力になり、損失関数は平均二乗誤差(MSE, Mean Square Error)を利用しています。
\begin{equation}
L_{MSE} = \frac{1}{T_{train} -w}
\sum_{t= w + 1}^{T_{train}}
|| \bm{\hat{s}^{(t)}} - \bm{s}^{(t)} ||^2_{2}
\end{equation}4. Graph Deviation Scoring
ここでは、センサーの異常スコアをどのように定式化するかについて記載されています。
あるセンサー$i$における異常スコア$Err_{i} (t)$は、予測値$\bm{\hat{s}}_i^{(t)}$と実際のセンサーの値$\bm{s}_i^{(t)}$の差分の絶対値で表現します。
Err_{i} (t) = | \bm{s}_i^{(t)} - \bm{\hat{s}}_i^{(t)}|ただ、これだとセンサーの値でスケールが異なるため、上記の異常度を正規化した次の値を異常値のスコアとしています。
\begin{equation}
a_{i} (t) = \frac{Err_{i} (t) - \tilde{\mu}_i}{ \tilde{\sigma}_i}
\end{equation}ここで、$\tilde{\mu}_i$はセンサー$i$の平均で、$\tilde{\sigma}_i$は四分位数(IQR)です。
さらに、$a_{i} (t)$を全てのセンサーに対して求めたあと、その最大値をその時刻$t$の異常度$A_i(t)$とします。
\begin{equation}
A(t) = \underset{i} {\operatorname{max}} ~ a_{i} (t)
\end{equation}この(10)式の異常度を基本的にその時刻$t$の異常度としますが、突然のセンサーの値の変化にセンシティブになるので、ここでは(10)式の単純移動平均線(SMA, Simple Moving Average)を用いた値$A_S(t)$を用います。
$A_S(t)$が閾値を超えた際に、その時刻$t$を異常と判定します。
GDNのモデルの解釈性
GDNはモデルの解釈性が高い手法となっています。
GDNは、Dynamic Graph Structure Learningのモデルを取り入れており、センサーの依存関係をダイナミック(センサーのデータから)に学習し、可視化することができます。そのため、依存関係の崩れなどから、異常を可視化することができます。
論文のFigure2の引用ですが、Embedding(埋め込み)空間上でのセンサーの距離をt-SNEで可視化したものがこちらの図になりますが、近いセンサーが埋め込み空間上で近い位置に配置されるように学習されているのがわかります。
こちらが、さらに学習したグラフとattention weightを可視化したものです。
GDN実装と全体アーキテクチャ
続いて、GDNの実装の解説に入っていきます。実装は、Githubに掲載されている実装に基づいて解説をしていいます。
理論だけでは理解できなくても、実装を見ながら式を追っていくことで理解できる部分もあると思うので、上記の理論と実装を往復しながら見ていただけたらと思います。
GDNのアーキテクチャは、入力層を上とした時に、次のようになっています。
今回は、このレイヤーを上から辿りながら、かつ先ほどの理論と照らし合わせながら解説していきます。前処理部分や、モデルの本質的なところ以外は省略していくので、ご注意ください。
まだ実装自体は、pytorch とpytorch-geometricを利用しています。pytorch geometricの利用方法は下記lの記事で解説しているので、もしよろしければご覧ください。
また、論文でのpytorch-geometricの実行環境は、version 1.5.0 です。2019年当時で、pytorch-geometricに破壊的な変更が入っており、このversionのpytorch-geometricでしか動かないので注意しましょう。
それでは、実装の解説に入っていきます。
GDNにおける主要なクラス
実装の中で、主要なクラスは次の3つあたりです。継承元の親クラスをカッコ内に記述しています。
- GDN (torch.nn.module)
- GNNLayer (torch.nn.module)
- GraphLayer (torch_geometric.nn.conv.MessagePassing)
GDNクラス
GDNクラスは、torch.nn.Moduleを継承しており、モデル全体がこのクラスで実装されています。
パラメータとして、次の引数を取ります。
- edge_index_sets(Tensor) … ？？
- node_num(int) … ノード(センサー)の数。多変量時系列データの次元数でもある。
- dim(int) … 埋め込みベクトルの次元数 (デフォルト64)
- input_dim(int, optional) … スライディング ウィンドゥ$w$ の幅 (デフォルト10)
- out_layer_inter_dim(int, optional) … 出力層の出力次元(デフォルト1)
- topk(int, optional) … topK個のセンサーの依存関係を取得(3)式参照。(デフォルト20)
このGDNクラスのイニシャライザとforward()関数を見ていくと、大まかな処理の流れがわかります。
埋め込みの処理もここで実装しています。
GNNLayer
GraphLayerのラッパークラスとして振る舞っています。
さしたる内容がないので省略します。
GraphLayer
GATの実装をGraphLayerクラスで行なっています。
このクラスはtorch_geometric.nn.conv.MessagePassing クラスを継承していおり、MPNNフレームワークに基づくGATの実装がされています。
引数は次のようになっています。
- in_channels(int) … 入力次元数
- out_channels(int) … 出力次元数
- heads(int) … multi-head attentionの数(デフォルト1)
- concat(bool, optional) … multi-head attentionの演算でconcatenationかaverageか
- negative_slope(float, optional) … LeakyReLUにおけるslope係数(デフォルト: 0.2)