ICML 2022

机器之心专栏

机器之心编辑部

图神经网络（GNN）被广泛应用于结构化数据的异常检测，例如社交网络恶意账号检测、金融交易欺诈检测等。香港科技大学和斯坦福大学的研究者首次从谱域的角度（即图拉普拉斯矩阵的谱分解）分析了异常数据可能造成的影响。核心发现是：异常数据将导致频谱能量出现 “右移” 现象，即频谱能量分布从低频向高频移动。基于这一发现，他们又提出了 Beta 小波图神经网络（BWGNN）。它拥有多个具有局部性的带通滤波器，能够更好捕获 “右移” 产生的高频异常信息。在四个大规模图异常检测数据集上，BWGNN 的性能均优于现有的模型。

论文地址：https://arxiv.org/abs/2205.15508

代码地址：https://github.com/squareRoot3/Rethinking-Anomaly-Detection

面向结构化图数据的异常检测：背景与挑战

异常检测是数据挖掘的经典任务之一。分析异常数据有助于企业或用户理解其背后的形成机制，从而做出相应决策，避免损失。随着网络发展，面向结构化数据的异常检测，即图异常检测，受到越来越多关注。

图异常检测具体可定义为：寻找图上的少部分对象（节点、边、子图等），它们与其余大多数对象有着不同分布规律。本文专注于图上异常节点的检测任务。相较于传统的异常检测方法，图异常检测能够利用不同实体之间的关联信息，更好服务于网络安全、欺诈检测、水军检测、金融风控、故障监测等实际场景。

下图直观对比了传统异常检测与面向图的异常检测任务之间的区别。

图 1：传统异常检测与面向图的异常检测任务对比。

近年来，图神经网络成为分析处理结构化数据的一大利器。图神经网络通过学习包含节点自身特征和邻居信息的嵌入表示，来更好完成分类、重建、回归等下游任务。

然而，通用的图神经网络（如图卷积网络等）主要针对正常数据设计，在异常检测任务上容易遇到 “过平滑”(over-smoothing) 问题，即异常节点和正常节点的表达难以区分，影响异常检测的准确率。例如，在金融欺诈检测的实际应用中，异常账户通常会先与多个正常账户进行正常交易来伪装自己，降低自身可疑程度，之后再展开违规交易。这种 “关系欺诈” 进一步增加了图异常检测的难度。

为了解决上述困难，研究者专门提出针对异常检测任务的图神经网络模型，包括（1）利用注意力机制从多个视图聚合邻域信息；（2）利用重采样方法聚合不同类别的邻域信息；（3）设计额外的损失函数来辅助图神经网络的训练等。这些方法主要从空域的角度设计图神经网络来处理异常，但并没有人从谱域的角度考虑过该问题。

事实证明，选择不同的频谱滤波器（spectral filter）会影响图神经网络的表达能力，从而造成性能上的差异。

另辟蹊径：谱域视角下的图异常检测

为了填补现有研究的空白，本文希望回答这样一个问题：如何为图神经网络量身定做一个频谱滤波器用于异常检测？

本文首次尝试了从谱域视角分析图上的异常数据，并观察到：异常数据会导致频谱能量的 “右移”，即能量更少集中在低频，同时更多集中在高频。

为了可视化这种右移现象，研究者首先随机生成了一个有 500 个节点的 Barabási–Albert 图（BA 图），并假设图上正常节点和异常节点的属性分别遵循两个不同的高斯分布，其中异常节点的方差更大。

图片的上半部分展示了包含不同程度异常的数据在 BA 图上的分布，而下半部分展示了对应的频谱能量分布。其中，柱状图代表对应频谱区间的能量占比，折线图代表从零到该点频域能量的累积占比。

图 2：频谱能量 “右移” 现象的可视化。

从上图可以看出，当异常数据占比为 0% 时，大部分能量集中在低频部分（λ