论文标题 ｜ Graph Neural Network-Based Anomaly Detection in Multivariate Time Series
论文来源 ｜ AAAI 2021
论文链接 ｜ https://arxiv.org/abs/2106.06947
源码链接 ｜ https://github.com/d-ailin/GDN

TL;DR

论文中提出一种基于 GNN 的结构学习模型 GDN（Graph Deviation Network）来解决多变量时间序列异常检测的问题，此外还利用 GAT 学习到的注意力权重来解释检测到的异常。实验部分在两个真实 sensors 数据集中验证了 GDN 模型不仅比 baselines 更加准确地检测出异常，还可以捕获不同传感器间的关系来辅助定位异常根因。感觉和另一篇文章思路有些类似 MTAD-GAT：基于图注意力网络的多变量时间序列异常检测模型

Problem Statement

论文中的训练数据包括NN 个 sensors 在TtrainT_{train} 范围内数据strain =[strain (1),⋯ ,strain (Ttrain )]\mathbf{s}_{\text {train }}=\left[\mathbf{s}_{\text {train }}^{(1)}, \cdots, \mathbf{s}_{\text {train }}^{\left(T_{\text {train }}\right)}\right]，在每个时刻tt 的数据strain(t)∈RN\mathbf{s}_{train}^{(t)}\in \R^N 为NN 维向量表示NN 个 sensors 对应的值。对于无监督模型训练数据中一般仅包含正常数据。

模型的目标是检测测试数据集stest =[stest (1),⋯ ,stest (Ttest )]\mathbf{s}_{\text {test }}=\left[\mathbf{s}_{\text {test }}^{(1)}, \cdots, \mathbf{s}_{\text {test }}^{\left(T_{\text {test }}\right)}\right] 的TtestT_{test} 个时刻中是否为异常，每个时刻数据结果为a(t)∈{0,1}a(t) \in\{0,1\}。

Algorithm/Model

论文中提出的模型框架如下图所示：

GDN 模型框架
GDN 模型框架

主要包括四部分：

  • Sensor Embedding：学习到每个 sensor 的特征向量表示；
  • Graph Structure Learning：学习 sensors 间依赖关系的图结构表示；
  • Graph Attention-Based Forecasting：基于图注意力机制预测每个 sensor 下个时刻的值；
  • Graph Deviation Scoring：从学习到的关系中确认偏差并且定位和解释偏差；

Sensor embedding

对于每个 sensor 学习到一个 embedding vector 来表示其特征

vi∈Rd, for i∈{1,2,⋯ ,N}\mathbf{v}_{\mathbf{i}} \in \mathbb{R}^{d}, \text { for } i \in\{1,2, \cdots, N\}

embedding vector 首先是实际初始化然后进行训练，论文将每个 sensor 的 embedding 用于两方面：

  • 结构学习：判断 sensor 间的相关性；
  • 注意力系数学习：考虑不同种类 sensor 间的异质影响程度；

图结构学习

考虑到不同 sensor 间依赖模式是不对称的，论文中利用有向图来表示 sensor 间的关系，其对应的邻接矩阵为AijA_{ij}。

对于每个 sensorii 其依赖的 condidate relations 为Ci⊆{1,2,⋯ ,N}\{i}\mathcal{C}_{i} \subseteq\{1,2, \cdots, N\} \backslash\{i\}。如果有先验知识那么Ci\mathcal{C_i} 可以自定义，如果没有那么为除本身外的全集。

为了选择 sensorii 的依赖，需要计算其对于每个 condidate relations 中j∈Cj\in \mathcal{C} 的相似性：

eji=vi⊤vj∥vi∥⋅∥vj∥ for j∈CiAji=1{j∈TopK⁡({eki:k∈Ci})}\begin{aligned} e_{j i} &=\frac{\mathbf{v}_{\mathbf{i}}^{\top} \mathbf{v}_{\mathbf{j}}}{\left\|\mathbf{v}_{\mathbf{i}}\right\| \cdot\left\|\mathbf{v}_{\mathbf{j}}\right\|} \text { for } j \in \mathcal{C}_{i} \\ A_{j i} &=\mathbf{1}\left\{j \in \operatorname{TopK}\left(\left\{e_{k i}: k \in \mathcal{C}_{i}\right\}\right)\right\} \end{aligned}

然后选择 top-k 个最相似的作为其依赖 sensor，至于kk 值需要根据稀疏性进行判断。

基于图注意力预测

为什么采用预测模型？1. 判断哪个 sensor 偏离异常 2. 判断 sensor 如何偏离异常的。

在时刻tt 模型输入为x(t)∈RN×w\mathbf{x}^{(t)} \in \mathbb{R}^{N \times w}，其ww 表示历史序列时间窗口，目标是需要判断在当前时刻值s(t)\mathbf{s}^{(t)}

x(t):=[s(t−w),s(t−w+1),⋯ ,s(t−1)]\mathbf{x}^{(t)}:=\left[\mathbf{s}^{(\mathbf{t}-\mathbf{w})}, \mathbf{s}^{(\mathbf{t}-\mathbf{w}+\mathbf{1})}, \cdots, \mathbf{s}^{(\mathbf{t}-\mathbf{1})}\right]

为了考虑 sensor 间的关系，论文中采用图注意力机制来融合 sensor 特征vi\mathbf{v}_{\mathbf{i}}，对于节点ii 聚合特征zi\mathbf{z}_{\mathbf{i}} 计算方法如下

zi(t)=ReLU⁡(αi,iWxi(t)+∑j∈N(i)αi,jWxj(t))\mathbf{z}_{i}^{(t)}=\operatorname{ReLU}\left(\alpha_{i, i} \mathbf{W} \mathbf{x}_{i}^{(t)}+\sum_{j \in \mathcal{N}(i)} \alpha_{i, j} \mathbf{W} \mathbf{x}_{j}^{(t)}\right)

这种模式太熟悉了就不再介绍每个参数代表的含义。注意力系数计算方法如下

gi(t)=vi⊕Wxi(t)π(i,j)= LeakyReLU (a⊤(gi(t)⊕gj(t)))αi,j=exp⁡(π(i,j))∑k∈N(i)∪{i}exp⁡(π(i,k))\begin{aligned} \mathbf{g}_{i}^{(t)} &=\mathbf{v}_{i} \oplus \mathbf{W} \mathbf{x}_{i}^{(t)} \\ \pi(i, j) &=\text { LeakyReLU }\left(\mathbf{a}^{\top}\left(\mathbf{g}_{i}^{(t)} \oplus \mathbf{g}_{j}^{(t)}\right)\right) \\ \alpha_{i, j} &=\frac{\exp (\pi(i, j))}{\sum_{k \in \mathcal{N}(i) \cup\{i\}} \exp (\pi(i, k))} \end{aligned}

其中⊕\oplus 表示链接操作，a\mathbf{a} 是注意力机制学习到的系数向量。

以上特征融合的过程就可以得到NN 个节点的特征表示{z1(t),⋯ ,zN(t)}\left\{\mathbf{z}_{1}^{(t)}, \cdots, \mathbf{z}_{N}^{(t)}\right\}。对于每个zi(t)z_i^{(t)}, 论文中又 element-wise 乘特征表示vi\mathbb{v}_i ，再经过 FC 得到输出维度NN 的向量来预测tt 时刻 sensor 的值s(t)\mathbf{s}^{(t)}

s^(t)=fθ([v1∘z1(t),⋯ ,vN∘zN(t)])\hat{\mathbf{s}}^{(\mathbf{t})}=f_{\theta}\left(\left[\mathbf{v}_{1} \circ \mathbf{z}_{1}^{(t)}, \cdots, \mathbf{v}_{N} \circ \mathbf{z}_{N}^{(t)}\right]\right)

对于数值型就直接采用 MSE 作为损失函数，

LMSE=1Ttrain −w∑t=w+1Ttrain ∥s^(t)−s(t)∥22L_{\mathrm{MSE}}=\frac{1}{T_{\text {train }}-w} \sum_{t=w+1}^{T_{\text {train }}}\left\|\hat{\mathbf{s}}^{(\mathbf{t})}-\mathbf{s}^{(\mathbf{t})}\right\|_{2}^{2}

图偏差评分

为了检测和解释 sensor 的异常，论文中的模型首先针对每个 sensor 计算一个异常值，然后再合并得到一个组合分数。

对于tt 时刻 sensorii 的异常值为

Err⁡i(t)=∣si(t)−s^i(t)∣\operatorname{Err}_{i}(t)=\left|\mathbf{s}_{\mathbf{i}}^{(\mathbf{t})}-\hat{\mathbf{s}}_{\mathbf{i}}^{(\mathbf{t})}\right|

由于不同 sensor 的偏差值有不同的量纲，因此需要标准化

ai(t)=Err⁡i(t)−μ~iσ~ia_{i}(t)=\frac{\operatorname{Err}_{i}(t)-\widetilde{\mu}_{i}}{\widetilde{\sigma}_{i}}

其中μ~i\widetilde{\mu}_{i} 和σ~i\widetilde{\sigma}_{i} 表示中位数和四分位数，至于为什么不用均值和标准差作者认为这种方式对于异常检测更加 robust。🤔

取所有 sensor 最大的异常值为异常分数

A(t)=max⁡iai(t)A(t)=\max _{i} a_{i}(t)

由于模型难以预测到突刺，因此作者使用 SMA (simple moving average) 来生成平滑分数As(t)A_s(t)，最后得到的值如果超过设定的阈值那么该时刻被标记为异常。

Experiments

实验部分采用了两个真实数据集来测试 GDN 及其 baselines 的性能对比。

实验中考虑的问题非常齐全，包括准确率测试、消融实验、模型解释性、异常定位等。👍

每个部分的实验结果如下所示

性能对比
性能对比
消融实验对比
消融实验对比
可解释-可视化效果
可解释-可视化效果
异常解释和定位
异常解释和定位

Thoughts

  • 论文整体思路简洁明了，尤其是实验部分比较 solid 符合对模型的认知 👍
  • 需要改进的点在于模型的设计及其采用的方法：
    • 图结构学习部分采用有向图是非常合理的，但是采用了相似度计算和 top-k 的构图方法，相似度计算是对称的明显达不到想要的有向图效果。
    • 最后的 output layer 采用了 embedding 和 feature 进行 element-wise multiply，有点硬。
  • 异常评分模块给人感觉是 tricks 堆叠，🐂 啊 🐂。