论文标题丨LUNAR: Unifying Local Outlier Detection Methods via Graph Neural Networks
论文来源丨AAAI 2022
论文链接丨https://arxiv.org/abs/2112.05355
源码链接丨https://github.com/agoodge/lunar

TL;DR

局部离群点检测的方法例如 KNN、LOF 和 DBSCAN 等由于缺少可训练参数，因此难以自适应不同数据集。这篇文章基于图神经网络和局部离群点检测的思想提出了一种统一的异常检测框架 LUNAR (Learnable Unified Neighbourhood-based Anomaly Ranking)，可以基于近邻节点学习特征从而检测异常点。实验部分证明 LUNAR 效果明显优于现有的局部异常点检测方法和其它的深度学习模型，并且对模型参数的鲁棒性进行效果检验。

Problem Definition

无监督异常检测的定义：给定mm 个正常训练样本x1(train) ,…,xm(train )∈Rd\mathbf{x}_{1}^{\text {(train) }}, \ldots, \mathbf{x}_{m}^{(\text {train })} \in \mathbb{R}^{d} 和nn 个测试样本x1(test) ,…,xn(test )∈Rd\mathbf{x}_{1}^{\text {(test) }}, \ldots, \mathbf{x}_{n}^{(\text {test })} \in \mathbb{R}^{d}，对于每个测试样本xi(test)\mathbf{x}_{i}^{\text {(test)}} 所发需要输入一个异常分数。

Algorithm/Model

类推理论

首先证明局部异常点检测方法可以形式化的类比为 GNN 的信息传递机制；

首先看空域 GNN 信息聚合公式如下

hNi(k)=□j∈Niϕ(k)(hi(k−1),hj(k−1),ej,i)hi(k)=γ(k)(hi(k−1),hNi(k))\begin{aligned} \mathbf{h}_{\mathcal{N}_{i}}^{(k)} &=\square_{j \in \mathcal{N}_{i}} \phi^{(k)}\left(\mathbf{h}_{i}^{(k-1)}, \mathbf{h}_{j}^{(k-1)}, \mathbf{e}_{j, i}\right) \\ \mathbf{h}_{i}^{(k)} &=\gamma^{(k)}\left(\mathbf{h}_{i}^{(k-1)}, \mathbf{h}_{\mathcal{N}_{i}}^{(k)}\right) \end{aligned}

其中□\square 表示聚合函数，ϕ\phi 表示邻居发送的消息，γ\gamma 表示更新函数。

为了便于理解文章中采用 KNN 的思路说明信息传递机制。

每个样本对应图中节点，文章中构造的是kk-NN directed graph，📢 注意是有向边。

对于节点ii 其邻居节点j∈Nij\in \mathcal{N}_i，其边特征ej,i\mathbf{e}_{j, i} 对应节点距离

ej,i={dist⁡(xi,xj) if j∈Ni0 otherwise. e_{j, i}=\left\{\begin{array}{l} \operatorname{dist}\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) \text { if } j \in \mathcal{N}_{i} \\ 0 \text { otherwise. } \end{array}\right.

那么 KNN 信息传递方式如下

信息

ϕ(1):=ej,i\phi^{(1)}:=\mathbf{e}_{j, i}

聚合

hNi(1):=max⁡j∈Niϕ(1)\mathbf{h}_{\mathcal{N}_{i}}^{(1)}:=\max _{j \in \mathcal{N}_{i}} \phi^{(1)}

更新

γ(1):=hNi(1)\gamma^{(1)}:=\mathbf{h}_{\mathcal{N}_{i}}^{(1)}

从上面即可看出 KNN 是一种特殊的 one-layer 信息传递模式！🤔

同样地 LOF 和 DBSCAN 中对应上面步骤的方法如下

模型设计

首先是构图，论文中采用 k-NN 有向图，边特征为样本点间的欧式距离如下

ej,i={dist⁡(xi,xj) if j∈Ni0 otherwise. \mathbf{e}_{j, i}=\left\{\begin{array}{l} \operatorname{dist}\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) \text { if } j \in \mathcal{N}_{i} \\ 0 \text { otherwise. } \end{array}\right.

Message

从节点jj 传播到节点ii 的消息为ϕ(1):=ej,i.\phi^{(1)}:=\mathbf{e}_{j, i} .

Aggregation

为了适应不同的信息聚合方式，论文中提到可学习的信息聚合函数。对于每个节点的 k 近邻距离构造向量

e(i):=[e1,i,…,ek,i]∈Rk\mathbf{e}^{(i)}:=\left[\mathbf{e}_{1, i}, \ldots, \mathbf{e}_{k, i}\right] \in \mathbb{R}^{k}

然后将向量通过神经网络F\mathcal{F} 映射到一标量值表示节点ii 的异常程度

hNi(1):=F(e(i),Θ)\mathbf{h}_{\mathcal{N}_{i}}^{(1)}:=\mathcal{F}\left(\mathbf{e}^{(i)}, \Theta\right)

Update

更新函数结果即为聚合函数输出的结果，异常点输出分数为 1，正常点输出分数为 0；

γ(1):=hNi(1)\gamma^{(1)}:=\mathbf{h}_{\mathcal{N}_{i}}^{(1)}

为了提高模型的适应性论文中还使用了负样本进行训练，不再细述；模型采用 MSE 作为损失函数。

Experiments

实验部分采用了 8 组数据集进行对比，数据集统计信息如下

实验结果如下所示

对比不同kk 取值对局部离群点检测实验结果的影响如下

Thoughts

  • 论文整体想法新颖，基于 GNN 结合局部近邻的思想来解决离群点检测问题。✔️
  • 主要创新在于问题的转化和 GNN 模型构造的创新性，尤其是 learnable aggregation function。✔️
  • 如果去掉 GNN 这层包装，貌似主要逻辑就是 KNN + DNN ？