AddGraph: Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN

type

status

date

slug

summary

摘要

在动态图中进行异常检测在许多不同的应用场景中变得非常关键，例如推荐系统，但由于异常的高度灵活性和缺乏足够的标记数据，它也带来了巨大的挑战。最好通过考虑所有可能的提示，包括结构、内容和时间特征，来学习异常模式，而不是利用部分特征上的启发式规则。在本文中，我们提出了AddGraph，这是一个通用的端到端异常边检测框架，使用扩展的时间GCN（图卷积网络）和注意模型，可以捕捉动态图中的长期模式和短期模式。为了应对标记数据不足的情况，我们以半监督的方式在AddGraph的训练中采用了选择性负采样和边际损失。我们在真实世界的数据集上进行了大量实验，并展示了AddGraph在异常检测方面可以明显优于最先进的竞争对手。

1. 介绍

（介绍异常背景知识和场景）异常标记数据不足。如CAD [Sricharan和Das，2014] 和Netwalk [Yu等人，2018]，已经将图嵌入方法应用到了动态图中。他们的方法设计得很好，在检测动态图中的异常方面取得了良好的结果。然而，它们不能捕捉节点的长期和短期模式，这在更通用的图模型框架中用于检测异常时非常需要。

本文将原始的GCN模型扩展为支持使用基于GRU（门控循环单元）的上下文关注模型的时间信息，并在模型训练中引入了选择性负采样和边缘间隔损失，以逐步处理异常边。具体来说，我们的工作的主要贡献总结如下：

我们提出了AddGraph，一个用于异常边检测的半监督学习框架，它使用了扩展的时间GCN与基于注意力的GRU，可以结合节点的长期行为模式和包含节点短期模式的窗口信息的隐藏状态。

引入了一种选择性负采样策略和边缘间隔损失。

真实世界的数据集上测试，有效的。

2. 相关工作

回顾现有的异常检测方法，图嵌入模型和一些异常检测的尝试。

2.1 动态图的异常边缘检测

（老方法）[Goutlier，Aggarwal等，2011] 认为异常边通常出现在两个不同的节点簇之间。提出先对节点分区，然后为分区内的边构建了一个边生成模型。模型产生的分数可以作为检测异常边的重要衡量标准。[Sun等，2006；Shin等，2016；Shin等，2017] 将异常视为密集子图，在动态二分图中定义了一个密度函数。

CM-Sketch [Ranshous等，2016] 是一种基于草图的方法，它使用局部结构信息和边附近的历史行为来判断边是否异常。SpotLight [Eswaran等，2018] 从整个节点集中随机抽样一系列节点集，并通过计算这些集合与当前边集的节点之间的重叠来将每个时间戳的图编码为一个向量。该方法通过对这些向量进行聚类来找出异常图。然而，它只能捕捉瞬时的异常情况。

2.2 图嵌入

（介绍Deepwalk [Tang等，2015]、LINE [Tang等，2015] 和Node2vec [Grover和Leskovec，2016]）GCN及其后续扩展的工作可以处理结构特征和内容特征，但是不考虑动态图中的时间特征。工作[Defferrard等，2016；Kipf和Welling，2017]从不同的角度改进了基本GCN的性能，例如在时间/空间复杂性方面的优化。

知识图嵌入将三元组（h，r，t）映射到低维向量空间，以保留多关系数据之间的潜在相似性和差异性。不足的数据也是知识图嵌入的一个关键挑战，因为原始数据集中只有黄金三元组，这可能导致不同关系中的数据差异不明显。为了解决这一挑战，我们使用负采样来通过随机替换头部或尾部实体来生成边 [Bordes等，2013]。在[Wang等，2014]中，使用伯努利分布进行负采样，它对替换关系中的头部和尾部具有不同的概率。为了使负采样产生的三元组与黄金三元组不同，我们使用边际损失来增大正例三元组和负样本之间的差异。在本文中，我们借用了知识图嵌入中的负采样和边际损失的类似思想，以解决异常检测中数据不足的问题。

2.3 图嵌入上的异常检测

我们将GCN扩展为时态GCN，以更合理地捕获时间特征，同时构建了一个端到端的半监督学习模型来检测异常边，而不是采用两阶段聚类，这有可能取得更好的结果。

3. 具体方法

3.1 问题定义

（动态图定义）

3.2 AddGraph 定义

AddGraph 使用GCN处理当前快照上一节点状态和边，考虑节点的结构和内容特征。短窗口内的节点状态由上下文关注的模型汇总为短期信息。将GCN和短窗口信息的输出，输入到GRU中获得新时间步的隐藏状态。使用每一个时间步的隐藏状态计算现有边和负采样边的异常概率，然后将它们输入到边际损失中。

GCN的内容和结构特征。通过以下公式传播 t-1 时刻的隐藏状态

代表当前状态，将输入和长期隐藏状态结合。是[ Kipf and Welling, 2017]中提到的L层GCN。详细表示如下

就是传统GCN中的添加自相关和行列归一化的表达。

使用带attention的GRU组合长期和短期状态。[Liu etal., 2017]和[Cui et al., 2017]提出的基于注意力的上下文模型。框架中构建本地窗口的短状态如下：

（5）中的代表i节点的t时刻隐藏状态，代表短时信息的窗口参数。和是优化模型的参数。

所以现在有了：组合了当前输入和长时间信息隐藏状态。和：经过注意力机制捕获的短时窗口信息，AddGraph使用GRU处理它们获得时序特征编码

（介绍GRU各种门公式）。现在就包含了结构，内容和时序信息。

边缘的异常分数计算。 包含了时间时刻的节点隐藏状态，通过确定节点隐藏状态来计算边的异常得分

是sigmod函数，是输出层的优化参数，和是得分函数中的超参数。注意，本文中使用的单层网络可以被其他复杂的网络结构所替代。

3.3 选择性负采样与损失

为了处理异常数据不足的情况，我们尝试构建一个模型来描述正常数据。之前提到，在训练阶段我们假设所有边缘都是正常的。对于图中的每个正常边缘，我们生成一个负样本作为异常边缘。受到[Wang et al., 2014]的启发，负样本通过替换中的为参数

其中表示节点的度。所以

由于生成的节点依然可能是正常的，所以不能直接用严格和损失函数如交叉熵，因此，我们采用了与[Bordes等人，2013]相同的思路边界的成对损失，其中是边的异常得分函数

在处理混合正常边和异常边时，我们选择一些更准确的可信边，具体来说，对于每个边，生成的异常边，如果的边会被丢弃。最总的损失函数加上一个L2正则化损失避免过拟合

4. 实验

使用了UCI Message和Digg数据集。UCI Message是一个包含加州大学欧文分校在线社区中消息的有向网络。每个节点代表一个用户，每条有向边表示两个用户之间的消息。Digg是Digg社交新闻网站的响应网络。网络中的每个节点都是该网站的用户，每条边表示一个用户回复另一个用户。我们随机为每个节点生成一个初始向量作为其内容特征。我们需要手动构建所需的数据集，因为测试阶段的真实数据很难获得[Akoglu et al., 2015]，遵循[于等人，2018]中使用的方法将异常边注入两个数据集中。