论文地址：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% 时，大部分能量集中在低频部分（λ<0.5）。通过增大异常节点相对于正常节点的方差 σ 或比例 α，数据的异常程度逐渐增大，频谱上低频部分的能量逐渐变少，高频部分则相应增加。基于高斯分布假设，本文 从理论上严格证明了数据异常程度的增大和频谱能量的 “右移” 之间存在单调关系 。
在实际场景中，异常数据通常遵循更加复杂的分布。在四个大规模图异常检测数据集上，研究者同样证实了 “右移” 现象的存在。以下图亚马逊异常用户检测数据集为例，当删除数据中一部分异常节点后，频谱上低频能量显著增多，同时高频则相应减少。如果删除同样数量的随机节点，频谱的能量分布几乎没有变化。这进一步验证了异常数据是频谱能量 “右移” 的关键。
图 3 : 亚马逊异常用户检测数据集上删除不同节点对频谱能量分布的影响：原图 (The Original)，删除随机节点 (Drop-Random)，删除异常节点 (Drop-Anomaly)
图异常检测的新利器：Beta 小波图神经网络
上节的分析表明，在图异常检测时需要关注 “右移” 效应。例如上图亚马逊数据集中，特征值 λ=1 附近的频谱信息与异常数据有较大关联。为了更好地捕获异常信息，图神经网络需要具备带通滤波器的性质，只保留 λ=1 附近的信号同时过滤其余信号。
遗憾的是，现有的图神经网络大多属于低通滤波器或者自适应滤波器，它们无法保证带通性质。其中自适应滤波器虽然具有拟合任意函数的能力，但在异常检测中同样可能退化为低通滤波器。这是因为在整个数据集中，异常数据对应的高频信息占比较小，而大部分频谱能量仍然集中在低频。
为了更好处理异常数据造成的 “右移”，研究者提出了一种图异常检测的新方法 —— Beta 小波图神经网络 (BWGNN) 。通过借鉴 Hammond 图小波理论，他们基于 Beta 函数设计了新的小波核作为图神经网络的频谱滤波器。
相比于常用的热核 (Heat Kernel) 函数，Beta 函数作为小波核不仅符合带通滤波器的要求，还具有更好的频域局部性与空域局部性。下图对比了热核小波与 Beta 核小波的区别。
图 4：热核小波与 Beta 核小波在谱域（左）和空域（右）上的对比，Beta 函数具有更好的带通与局部性质。
本文 在四个大规模图异常检测数据集上验证了 BWGNN 的性能 。其中，Yelp 数据集面向点评网站异常评论检测，Amazon 数据集面向电商平台异常用户检测，T-Finance 数据集面向交易网络异常用户检测，T-Social 数据集面向社交网络异常用户检测，包含多达五百万个节点和七千万条边。
从下表可以看出，与传统分类模型、通用图神经网络和专门的图异常检测模型相比，BWGNN 在 40% 训练数据和 1% 训练数据（半监督）两个场景下均取得更好的效果。在运行效率上，BWGNN 与大部分通用图神经网络耗时接近，比其余图异常检测模型更高效。
总结
本文中，研究者发现图上异常节点的出现会导致频谱能量 “右移”，为面向结构化数据的异常检测提供了一种新视角。基于该发现，本文提出了图异常检测的新工具 ——Beta 小波图神经网络 (BWGNN)。它通过专门设计的带通滤波器来捕获 “右移” 产生的高频异常信息，在多个数据集上取得了最优效果。
在实际落地中，图异常检测通常是一个复杂的系统工程，但选择合适的图神经网络是影响系统性能的一个关键因素。研究者提出的 BWGNN 设计精简、复杂度低、易于替换，是图神经网络的一项新选择。
