查看原文
其他

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

刘祖龙 PaperWeekly 2022-09-21


©作者 | 刘祖龙

单位 | 南京邮电大学

来源 | 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 神经网络,旨在对多频信号进行自适应组合。大量实验结果证明了本文方法的有效性。


更多阅读



#投 稿 通 道#

 让你的文字被更多人看到 



如何才能让更多的优质内容以更短路径到达读者群体,缩短读者寻找优质内容的成本呢?答案就是:你不认识的人。


总有一些你不认识的人,知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。 


PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学术热点剖析科研心得竞赛经验讲解等。我们的目的只有一个,让知识真正流动起来。


📝 稿件基本要求:

• 文章确系个人原创作品,未曾在公开渠道发表,如为其他平台已发表或待发表的文章,请明确标注 

• 稿件建议以 markdown 格式撰写,文中配图以附件形式发送,要求图片清晰,无版权问题

• PaperWeekly 尊重原作者署名权,并将为每篇被采纳的原创首发稿件,提供业内具有竞争力稿酬,具体依据文章阅读量和文章质量阶梯制结算


📬 投稿通道:

• 投稿邮箱:hr@paperweekly.site 

• 来稿请备注即时联系方式(微信),以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信(pwbot02)快速投稿,备注:姓名-投稿


△长按添加PaperWeekly小编




🔍


现在,在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧


·
·

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存