IJCAI 2022 | 图神经网络可以检测到异常吗？

会员服务 ·

IJCAI 2022 | 图神经网络可以检测到异常吗？

2022 年 8 月 7 日 PaperWeekly

©作者 | 刘祖龙

单位 | 南京邮电大学

来源 | MIND Laboratory

论文标题：

Can Abnormality be Detected by Graph Neural Networks?

论文链接：

https://www.ijcai.org/proceedings/2022/0270.pdf

代码链接：

https://github.com/zjunet/AMNet

图中的异常检测由于其在金融、生物等众多领域的广泛应用，引起了学术界和工业界的极大兴趣。与此同时，图神经网络 (GNNs) 正在成为图数据建模的有力工具。于是便自然出现一个问题：即 GNN 可以检测到图上的异常数据吗？

近期的研究表明。大多数 GNN 模型的表达能力仅限于低通滤波器，它强化低频信号（即更加平滑的信号），从而抑制了高频信号（更加振荡的信号）。GNN 在大多数真实网络数据上表现出了良好的性能，因为这些数据遵循同质性假设，即具有相似特征的节点往往彼此相连。然而，在包含异常的网络中，这一假设可能会被削弱：正常节点仍然倾向于与其正常邻居（低频信号）共享共同特征，而异常则倾向于与邻居具有不同的特征（高频信号）。因此，包含异常的网络倾向于混合高频和低频的局部模式（如图 1 所示）。

本文认为，对于图上的异常检测，直接采用大多数 GNN 无法取得最优的效果，原因如下：1）GNN 的低通特性与包含异常的网络本质上是不一致的。GNN 通过过滤掉高频信号来平滑正常节点和异常节点之间的差异。这就导致 GNN 学习到的异常节点表示无法区分，从而不可避免地导致图异常检测问题的性能不佳；2）大多数 GNN 是对网络的所有节点采用具有全局滤波特性的方法，然而，异常节点和正常节点可能会分别利用不同频段的信号，对正常/异常节点利用不同频率信息缺乏自适应性，从而导致模型难以区分异常节点与正常节点。

为了解决上述问题，本文提出了一种用于图异常检测的自适应多频滤波图神经网络 (AMNet)，其核心思想是自适应融合低频信息和高频信息，学习节点嵌入以识别异常节点。更具体地说，AMNet 不是使用全局低通滤波器，而是开发了一种新的可学习的多频滤波器组，可以同时有效地捕获低频和高频的图形信号。然后，滤波器组的输出信号传递多个频率的信息。

本文方法

1.1 相关定义

给定无向图，X 为特征矩阵，A 为邻接矩阵，Y 表示节点是否为异常节点的指示向量，给定 G 以及部分节点标签，本文的目标是学习一个分类器来判断给定节点是否为异常节点。

根据图信号处理理论，可以定义基于傅里叶变换的图滤波操作。L 为对称标准化的拉普拉斯算子，特征分解为，Λ 为特征值对角矩阵，信号 x 经过滤波器 g 转换为：

1.2 模型描述

为了使 GNN 自适应地利用低频率和高频率信息，本文首先设计了 K 个图滤波器，每个滤波器捕获不同频率的图信号。图中的每个节点得到 K 个信号，其频率由图滤波器的参数控制。为了模拟信号之间的差异，本文进一步提出使用节点级注意机制来自适应融合信号。最后，采用融合后的嵌入进行分类。图 2 展示 AMNet 的整体框架。

1.2.1 模型描述

为了同时捕获不同频率的图信号，本文设计了多频滤波器组。更具体地说，每个组由多个并行运行的可训练图过滤器组成，每个滤波器都以端到端方式独立训练。滤波器组可表示为，图信号表示为：

1.2.2 自适应结合信号

通过图滤波，得到了 K 个具有不同频率特性的特定信号，考虑到每个节点可以专注于不同的频段，使用学习相应的重要性。更具体地说，考虑到带有滤波信号的节点，其注意力分数表示为：

对上述分数利用 softmax 进行归一化，得到最终的注意力权重：

令，最终得到嵌入。

另一方面，AMNet 实际上为每个节点应用了个性化的图滤波器，特别地，节点的最终嵌入可表示为：

为了贝叶斯可追溯性，将上式中的解耦为两个后验概率的乘积：

其中个性化滤波器为带有注意力权重的滤波器组的线性组合。因此，AMNet 提供了每个节点学习对滤波器的适应性。

1.3 图滤波器的选择

1.3.1 组合图滤波器参数化

由式 5 可知，AMNet 通过组合多频滤波器组中的滤波器自适应学习每个节点的滤波器。然而，设计一个适合组合的图滤波器是十分困难，因为现有的大多数图滤波器，如切比雪夫多项式，面临以下两个挑战：1）现有的图滤波器大多会推导出负谱函数，根据图信号处理理论，导致组合结果复杂；2）滤波器的频率特性是尺度不变的。

这意味着较大尺寸的滤波器滤波效果优于较小尺度的滤波效果，从而降低了对不同频率聚焦学习的适应性。为了解决上述问题，本文引入限制性伯恩斯坦多项式参数化，以近似求出多滤波器组中的滤波器。

1.3.2 严格伯恩斯坦多项式

定义用 Bernstein 多项式参数化的图滤波器，其系数限制在区间 [0,1] 内：

其中，θ 为多项式系数的可学习参数。对于任意 λ∈[0,1]，，从而避免相移。此外，由于图片，θ 区间为 [0,1]，故 h(λ) 区间为 [0,1]，故滤波器组的所有过滤器共享统一的维度。因此，本文的方法避免了上述结合的局限性，同时又具有现有方法的优势，如空间定位和线性学习复杂度。

1.4 目标函数

1.4.1 注意力约束

直观地看，为了增强差异，异常节点需要利用更多的高频信息。这里，本文对注意力训练施加了约束，以鼓励异常节点和正常节点分别专注于不同的过滤器。例如，假设有两个过滤器，其注意力为时，其约束表示为：

其中，ζ 是松弛变量，用来控制注意值之间的边界；时，，反之， .

1.4.2 优化损失

利用上文得到的嵌入 Z 进行半监督节点分类任务，假设表示节点属于异常或正常的概率，可由下式计算得出：

最终的损失表示为：

其中表示节点分类得到的损失（如交叉熵），β≥0 是约束项的权重参数。

实验

本文使用的数据集包括 Yelp，Elliptic 等常用基准数据集，具体如下表所示：

本文的实验结果如表 1 所示，本文方法在四项数据集上都取得了最好的效果。

图滤波器自适应性的可视化分析如图 3、图 4、图 5 所示。

本文的消融实验如下表所示，其中，AMNet-Cheb：将 AMNet 中图滤波器的 Bernstein 多项式替换为切比雪夫多项式。AMNet- ac：它消除了 AMNet 中基于边际的注意力约束。

总结

本文研究了图神经网络能否检测异常的问题。首先本文通过探索 GNN 的本质来回答这个问题，并分析了异常检测场景中图信号的特征。现有的 GNN 大多只考虑单频图信号，而异常节点和正常节点则偏好不同的频率。因此，为了进一步提高 GNN 的异常检测性能，本文提出了一种新的自适应多频图 (Adaptive Multi-frequency Graph) AMNet 神经网络，旨在对多频信号进行自适应组合。大量实验结果证明了本文方法的有效性。

更多阅读