基于深度学习的图异常检测技术综述

陈波冯 李靖东 卢兴见 沙朝锋 王晓玲 张 吉

1(华东师范大学计算机科学与技术学院 上海 200062)

2(复旦大学计算机科学技术学院 上海 200433)

3(之江实验室 杭州 310000)

图作为一种通用的数据结构，被广泛用于表示复杂的结构化数据.相对于其他数据结构，它能更好地存储和表达实体及其联系.现实世界中，图在社交网络分析、Web网络分析、交通路网优化、知识图谱构建等领域均有广泛的应用.针对这些语义丰富、样式多样、规模庞大的图数据，如何快速、准确地检测其中的异常引起了学术界和产业界的广泛关注.图异常检测是指在一个大图或海量图数据库中寻找包含“陌生”或者“不寻常”模式的结构(包括节点、边或者子图)，具有广泛的应用场景，例如英特网中的恶意攻击、社交网络中的突发事件检测、电子商务中的水军发现等.相较于传统的异常检测方法，基于图的异常检测由于图具有强大的表达能力，不仅可以将复杂的数据加以直观的呈现，同时也能将数据中隐含的相关性融入到异常检测过程中.

面向图的异常检测工作最早发表于2003年[1]，现有工作大致可分为基于静态图和基于动态图2类.在基于静态图的异常检测工作中，一类方法利用ego网络[2]或者基于团体[3]研究问题；一类方法基于图的结构信息进行异常检测[4-6]，也有一些工作基于子空间选择，试图在节点特征的子空间中发现异常[7-9].还有一些工作通过概率、统计方法获取图的统计信息进行异常检测[10-13].尽管这些工作在异常检测上取得了不错的进展，但这些方法如利用ego网络的方法，由于处理图数据，必须考虑节点之间的交互，在图较为稀疏时难以实现较好的效果；或者如子空间选择和统计方法，由于浅层学习机制难以综合利用节点的属性和结构信息.在基于动态图的异常检测方面，同样有一些工作基于团体[14-15]、基于结构[6,16]、或基于概率统计[17-19]进行异常检测.另外一类典型的方法是首先获取图的概要，然后通过聚类和异常检测来确定概要中的异常，例如文献[20-21]，但是这些方法获得的概要无法保留重要的结构信息，比如邻接节点的信息.现有的基于动态图的异常检测方法大多依赖于启发式规则，通常只是简单地考虑某一类特征；虽然有部分方法[22-23]考虑了内容甚至时间因素，但并不灵活，导致其应用局限于特定的场景.

近年来，深度学习成为人工智能和机器学习中极为重要的部分，在提取数据中潜在复杂模式方面表现出优越的性能，并在音频、图像和自然语言处理等领域得到了广泛应用.深度学习方法能够合理处理复杂的属性信息，并且可以从数据中学习隐含的规律；此外，通过神经网络对图进行嵌入不仅可以很好地保留信息[24-26]，还可以很好地处理节点或边的属性，同时保留结构信息，进而方便检查隐空间中节点或边表示的相似性.近年来随着对图进行嵌入表示取得显著进展，如何利用深度学习方法进行图异常检测在过去几年中吸引了广泛关注.基于深度学习的图异常检测方法通常使用图的嵌入表示方法先将图表示为隐空间中的向量，然后使用该向量重构图从而剔除异常信息的影响，最后通过重构误差进行异常检测.

关于异常和离群点检测，已经存在非常全面的综述类文章，例如Zimek等人[27]重点介绍了关于高维离群值检测，Schubert等人[28]讨论了局部离群值检测技术.但是，这些文章通常关注多维数据实例的点，没有或者不是直接地关注基于图的检测技术.尽管文献[29]从图的角度对异常检测技术进行了调研，但是缺少对深度学习技术下的图异常检测技术的关注.与以往关于异常检测的综述不同，本文专注于大图或海量图数据库中的异常检测，并对基于深度学习的图异常检测技术进行全面地梳理和总结，是最早聚焦基于深度学习的图异常检测技术方面的研究综述.

本文首先对图上的异常定义做了全面的分析，然后详细介绍了基于深度神经网络的图表示学习方法，接着从静态图和动态图的角度出发，对现有基于深度学习的图异常检测方法进行系统地总结和归类，并讨论相关方法的局限性.接着简单介绍图异常检测技术的实际应用场景和相关的数据集，最后讨论基于深度学习的图异常检测研究面临的挑战及未来可行的研究方向.本文期望通过对目前基于深度学习的图异常检测研究现状的梳理，为后续研究提供可借鉴的思路.

1 图上的异常定义

关于图上的异常目前还没有统一的定义，并且异常通常跟应用领域或场景相关，本文分别从静态图和动态图的角度出发，梳理并总结了常见的图上的异常定义.

1.1 静态图上的异常定义

静态图上的异常通常是指图中很少的或者与观察到的模式有明显偏差的节点、边或子图.下面将根据结构、属性及其组合对静态图上的异常进行定义.

1) 静态图上的结构异常

① 节点与节点之间：给定一个图G，如果在属性不相符的节点之间有边连接，则定义该边为异常边.例如在DBLP数据集中，节点代表作者信息，来自2个不同领域的作者拥有完全不符的属性信息，突然合作发了一篇文章[30]，因此产生连接的边被定义为异常边.

② 节点与子图之间：给定一个图G和其中的节点v，v在属性上属于一个社区(社区内的节点拥有相似的属性信息)，如果v和属于其他社区的节点有边相连，那么定义该节点为异常节点，如图1(a)所示，其中较大的圆形和矩形分别表示异常节点及对应的属性，不同颜色表示不同社区，2个节点之间的箭头表示边的连接，2个属性之间的箭头表示某种度量下的相似性[31].图1(a)中较大的红色圆形节点在属性上与大量红色矩形相连，说明该节点在属性上属于红色社区，在结构上却与较多的其他社区节点相连，因此该节点被定义为异常节点.

③ 子图与子图之间：给定一个图G，可基于子图与子图之间的关系来发现异常，主要有2种情况：Ⅰ.Perozzi 等人[2]通过对子图的质量进行定义，从而将质量低的子图定义为异常.质量高的子图其内部节点紧密地相互连接，并且在属性上较为相似；子图之间区分明显，即子图与子图只有很少的边相连，或者即使相连，它们在属性上的差异也很大.Ⅱ.文献[1]中定义包含较少常见模式(提前确定)的子图为异常子图.

2) 静态图上的属性异常

给定一个图G和其中的节点v，v在结构上属于一个社区，如果v和大量属于其他社区的节点的属性相似，那么这种异常可以定义为属性上的异常，如图1(b)所示，较大的红色圆形节点与大量红色节点相连，说明该节点在结构上属于红色社区，在属性上较大的红色矩形却与较多的其他社区属性相连，因此被定义为属性异常节点.

Fig. 1 Example of anomaly definition on static graph图1 静态图上异常定义的示例[31]

3) 静态图上结构和属性的联合异常

给定一个图G和其中的节点v，v在结构上属于一个社区A，在属性上属于不同于A的社区B，那么这种异常可以定义为结构和属性的联合异常，也称为社区异常，如图1(c)所示，较大的红色圆形节点与大量绿色节点相连，属于绿色社区A，在属性上与大量蓝色属性相连，属于蓝色社区B，该节点在属性和结构上分别属于不同的社区，因此被定义为结构和属性的联合异常.

基于1)2)3)中异常定义，我们给出了静态图下异常检测任务形式化定义.

静态图异常检测：给定静态图G，静态图异常检测任务的目标是找到图G中不寻常的模式(结构异常模式，属性异常模式，联合异常模式).

1.2 动态图上的异常定义

对于一个随时间变化的动态图，图中可能会有新的节点或边的增加和删除，从而引起图结构和属性的动态变化，可能会出现异常.动态图上的异常通常是导致变化或事件发生的topk个节点、边或子图.

1) 基于结构变化的异常

基于社区的方法特别适合用于动态图结构的变化分析，因为社区具有总结图网络结构的能力.Chen等人[32]定义了图2中6种社区变化的异常，一般情况下稳定的社区不会随时间而改变，在连续的图快照之间发生以下改变可认为图结构发生了异常.

Fig. 2 Six possible community-based structural abnormalities in the evolutionary network[32]图2 进化网络中6种可能的基于社区的结构异常类型[32]

① 生长的社区：随时间的推移，快照t处的社区中新增了一些成员，从较小的社区发展成快照t+1中的一个大型社区，例如社区2.

② 收缩的社区：先前的更大社区失去一些成员收缩成更小的社区，例如社区4.

③ 合并的社区：快照t处的2个或多个小社区合并组成的社区，例如快照t+1处的社区7.

④ 划分社区：快照t处的社区可能会在快照t+1处分成多个社区，例如社区8.

⑤ 新生的社区：在某些快照中可能会出现新的社区，例如社区11.

⑥ 消失的社区：在某些快照中一些旧社区可能会消失，例如社区12.

2) 基于属性变化的异常

基于节点的属性特征为每个快照创建一个“good summary”，计算不同时刻图快照之间的距离，设定超过某个阈值时，将相应时序图快照标记为异常.在不同场景和算法中，构建“good summary”的方法以及使用的距离可以进行不同的定义.其中Akoglu等人[33]提出，如果某个节点的“行为”偏离其过去的“正常行为”，则该节点在某个时间范围内是异常的.

3) 基于结构和属性变化的异常

在随时间演变的大图中，Wang等人[34]对节点属性和图结构信息进行建模，如果一个节点的属性在时刻t不遵循其自身的历史行为模式且它所在的社区路径显示异常活动或不遵循其所属社区的模式，则认为该节点在时间t是异常的.

基于1)2)3)中异常定义，我们给出了动态图下异常检测任务形式化定义.

动态图异常检测：给定动态图Gd={G1,G2,G3,…,Gt}，Gt代表时刻t下的图信息，动态图异常检测任务的目标是找到动态图Gd中导致异常(基于结构变化的异常，基于属性变化的异常，基于结构和属性变化的异常)发生的节点，边或者子图.

1.3 异常检测评价指标

属性图中异常节点的数量远小于所有节点的数量，因此无法使用传统分类任务中的评估指标(例如精度和准确度)很好地评估异常检测任务的性能.例如学习一个把所有实例预测为正常的模型会得到一个很好的性能指标表现，但是，该模型无法检测到任何异常.曲线下面积(AUC)可以测量实例之间的相对关系，并且可以测量模型把异常实例排在正常实例前面的概率，这满足了我们在异常检测任务中寻找最佳可能异常实例的需求，因此各种实验中通常将AUC作为评估指标.此外，由于现实生活中错误识别异常具有很高代价，往往想要找到异常可能性最高的实例，因此异常检测任务中也通常将召回率(Recall)作为评价指标，即选取异常可能性最高的部分节点，将检测到的异常占所有异常的比例作为评价指标.

2 基于深度神经网络的图表示学习

进行异常检测等图分析研究的一个关键问题是如何合理地表示图中的特征信息，如何将图映射到低维向量空间，在保持原始图结构的同时支持推理的图表示学习研究引起了学术界和产业界的广泛关注.此外，由于节点的嵌入表示可以用于异常检测算法的输入，支持异常检测任务，因此，图表示学习方法在图异常检测领域具有重要作用.

在传统的图表示学习方法中，基于因子分解的方法以矩阵的形式表示节点之间的连接，并将该矩阵因子分解以获得节点的嵌入表示向量.例如LLE算法[35]假设每个节点的嵌入表示都是其在嵌入空间中邻居节点的嵌入向量表示的线性组合，Laplacian Eigenmaps算法[36]相比于LLE算法来说考虑了节点之间的权重.DeepWalk算法[37]第一次将深度学习技术引入到图表示学习领域，node2vec[38]采用了带有偏向的随机游走来学习图中节点的嵌入表示.上述方法虽然可以学到图中的节点表示，但大部分都是基于线性或浅层神经网络的表示，而现实世界中节点之间往往存在着非线性关系.由于深度神经网络模型在提取数据中潜在的复杂模式方面表现出极为优越的性能，因此越来越多的基于深度神经网络的方法应用于图的表示学习任务.

2.1 图神经网络模型及应用

图神经网络的概念在文献[39]中首次提出，它拓展了现有的深度神经网络模型，用于处理以图的形式表示的数据.图神经网络的目标是学习一个包含每个节点邻居信息的嵌入表示向量，以方便执行节点标签分类、链接预测、异常检测等任务.图神经网络被广泛应用于图分析和挖掘领域，例如Battaglia等人[40]在物理系统领域将对象和关系的相关作用建模成图结构，通过输入到图神经网来对图网络结构中各种物理系统进行预测和推断；Schlichtkrull等人[41]将知识图谱中的关系建模成图结构，然后利用图神经网络对边进行预测，从而完成知识图谱中的链接补全等任务.

图卷积神经网络旨在将卷积推广到图领域，现有的图卷积神经网络分为谱方法和空间方法两大类.基于谱方法的图卷积神经网络[42-43]利用卷积定理在每一层定义图卷积算子，在损失函数指导下通过梯度反向回传学习卷积核，并堆叠多层组成神经网络.基于空间方法的图卷积神经网络[44]基本思想是利用图上的信息传播机制，通过信息构造、邻居聚集、表示更新3个步骤使用上一时刻相邻节点的状态信息.在图异常检测领域，Ding等人[45]将图卷积神经网络当作编码器用于捕捉网络结构和节点属性之间的复杂交互，获得节点的高质量的嵌入表示后进一步用于异常检测任务.

近年来，随着注意力机制在越来越多的领域取得成功，图注意力网络[46-48]也得到了广泛的研究和关注.与以往关心边上信息的模型不同，GAT通过注意力机制定义聚合函数，邻接矩阵仅被用来定义相关节点.具体来说，为了获得节点更好的特征表示，首先针对节点特征做一个线性变换，再针对中心节点i，计算邻居节点j对节点i的重要性程度eij，然后通过softmax函数归一化获得节点的重要性程度,最后通过加权求和的聚集函数来获得节点的表示.Nathani等人[49]将GAT用作编码器以捕获图结构中具有各种关系的实体的多样性，从关系里学习到实体新的向量表示后用于链接预测等下游任务.Wu等人[50]将社会关系抽象成图结构，利用多个图注意力网络建模不同的社会关系从而用于社交推荐任务.在图异常检测方面，Fan等人[51]使用GAT捕获中心节点不同邻居之间的重要性程度和网络结构和节点属性之间的复杂交互，在获得高质量的嵌入表示后将重构损失当作异常的可能性大小.Ding等人[52]在编码器和解码器部分使用了图注意力网络获得节点表示后利用二分类的方法对节点进行异常检测，此外，图注意力网络的引入使得模型适用于递推式异常点检测.

2.2 基于深度神经网络的图表示学习方法

由于深度自动编码器具有建模数据中非线性结构的能力，因此常被用于各种基于深度神经网络的表示学习任务.最近，SDNE(structural deep network embedding)[53],DNGR(deep neural networks for learning graph representations)[54]、图自编码器[55-56]，利用深度自动编码器可以捕捉数据非线性关系的能力来获得节点更好的表示.

SDNE使用深度自动编码器来保留一阶和二阶网络邻近度，并通过共同优化一阶和二阶邻近度来学习节点的嵌入表示.DNGR将随机测量与深度自动编码器结合，采用一种无监督的表示学习算法来学习节点表示，然后对学习的表示利用聚类算法对节点进行聚类，使用聚类性能来评估不同图上表示学习的质量.DNGR和SDNE仅考虑与节点对之间的连通性有关的节点结构信息，忽略了节点可能包含描述节点自身属性的特征信息.而图自编码器利用图神经网络可以同时编码节点结构信息和属性信息来捕捉节点的更好嵌入表示，它采用传统的深度自编码器的架构，即由encoder编码部分和decoder解码部分构成，将通过encoder后得到的嵌入表示作为节点的表示.

在图自编码器的研究中，Kipf等人[55]使用图神经网络作为encoder来得到节点的嵌入表示，将图神经网络视为一个以节点特征和邻接矩阵为输入，以节点的嵌入表示为输出的函数.在decoder部分，则采用了内积来重构原始的图结构.图注意力自编码器(GATE)[56]同样采用了深度自编码器的架构.GATE使用GAT作为encoder部分来得到节点的嵌入表示.GATE在decoder部分同样采用了注意力机制，通过重构原始图的结构和属性，从而获得节点的嵌入表示向量.

将图自编码器用于异常检测已有一些探索性的研究，Ding等人[45]将GCN当作编码器用于捕捉网络结构和节点属性之间的复杂交互，实现高质量的嵌入表示后将通过解码器重构的损失大小当作异常的可能性大小；Ding等人[52]在编码器和解码器部分使用图注意力网络获得节点表示，然后利用二分类的方法对节点进行异常检测.Fan等人[51]提出的对偶自动编码器(AnomalyDAE)使用了图自编码器的思想，在编码器部分使用GAT捕获中心节点不同邻居之间的重要性程度和网络结构与节点属性之间的复杂交互，获得高质量的嵌入表示后将重构损失当作异常的可能性大小.

3 基于深度学习的图异常检测方法

介绍了静态图和动态图上的异常检测定义，以及基于深度学习的图表示学习方法之后，本节详细介绍基于深度学习的图异常检测方法及其进展.目前具有代表性的基于深度学习的图异常方法如表1所示:

Table 1 Deep Learning Based Graph Anomaly Detection Methods表1 基于深度学习的图异常检测方法梳理

3.1 基于深度学习的静态图异常检测方法

在基于深度学习的静态图异常检测场景下，由于标签数据难以获得[65]，通常采用无监督或者半监督学习的方法来检测异常.无监督的深度异常检测技术仅根据数据实例的内在属性来检测离群值，通常用于未标记数据样本的自动标记.此外，在实际应用中，除了大量未标记的样本之外，还可以访问一小部分已标记的样本，例如某个领域专家验证为正常或异常的实例子集，因此半监督的学习也常用于异常检测.接下来本节将从无监督和半监督的角度对静态图上基于深度学习的异常检测方法进行介绍.

3.1.1 无监督的深度图异常检测方法

目前已有的基于深度学习的无监督异常检测方法大都采用基于残差分析的思想，在基于残差分析的异常检测方法中，原始数据与估计数据的差距(即重构误差)是显示数据集中实例异常的有力指标.具体来说，具有较大重构误差的数据实例更有可能被认为是异常，因为它们的模式明显偏离大多数情况.在各种基于残差分析的异常检测方法中，深度自编码实现了最先进的性能[58-59].深度自编码器是所有无监督的深度学习异常检测模型的核心，其思想是假定正常的实例数目比异常实例数目多，深度自编码器可以记住正常的模式，但不能有效地从低维投影重建这些异常点，因此这些具有较少出现次数的异常点在通过自编码器后往往具有较大的残差，从而被判别为异常点.该类模型的框架如图3所示，针对输入数据通过一个编码器(encoder)得到数据的隐层表示，然后该表示通过一个解码器(decoder)重构输入数据，最后用输入和重构的输出之间的残差损失(residual loss)大小作为衡量数据异常的指标.

Fig. 3 Residual analysis based anomaly detection mode图3 基于残差分析的异常检测模型

在基于残差分析思想的基础上，学者们提出了一系列图上无监督的异常检测方法.

首先，Li等人在文献[57]中针对在没有先验知识的情况下，如何表征属性信息的残差以发现异常，以及如何利用属性残差和网络信息之间的一致性，从而以一般方式识别异常，提出了异常检测框架Radar，进而进行异常检测任务，通过学习和分析残差，发现与大多数样本不同的异常行为.最后在真实数据集上的实验表明了该残差分析框架Radar的效性和普遍性.

Bandyopadhyay等人[58]在文献[31]的基础上对异常检测的模型进行改进，提出了DONE和AdONE算法，模型结构如图4所示，该模型在编码器和解码器部分替换了文献[31]中使用的矩阵分解方法，采用了深度自编码器来获得结构和属性上的重构损失，用于捕捉非线性关系，同样利用损失函数引入了结构上的异常分数O1和属性上的异常分数O2.在获得节点属性和结构上的低维表示后，使用对抗学习的思想，学习社区异常中的映射矩阵W，让节点在属性和结构上具有一致性，从而获得社区角度的混合异常分数O3.

Fig. 4 Model structure of DONE and AdONE[58]图4 DONE和AdONE模型结构[58]

Liang等人[60]提出在做表示学习任务的过程中去检测异常点.文献[60]采用2个对偶深度神经网络去编码节点特征xi和节点的邻居特征xNi，获得编码后的节点特征h1(xi)和邻居节点特征h1(xNi).然后通过一个共享层融合节点的表示，即ei=λihl1(xi)+ (1-λi)hl1(xNi)，最后通过有标签的类型数据和无标签的表示学习任务去训练模型，由于异常点往往会影响表示学习的效果，因此通过将邻居信息融入到表示学习中，可以在表示学习任务中消除异常点的影响，在学习节点良好的嵌入表示的过程中同时检测出节点的异常分数.

上述介绍的基于深度学习的异常检测方法往往将节点的结构和属性信息分开考虑，忽略了两者之间的某些交互信息，而图神经网络可以同时编码节点结构和属性信息，将结构和属性信息结合起来考虑，可以捕捉到节点的更好表示.因此，图神经网络越来越多地被用于图上的异常检测领域.接下来将对已有的利用图神经网络的异常检测方法进行介绍.

Dominant[45]使用GCN对属性网络进行建模，解决了上述提到的分开考虑结构和属性信息的局限性，当处理与经过多层非线性转换的高阶节点交互时，GCN缓解了网络稀疏性的问题，可以捕获数据的非线性以及属性网络上2个信息源之间的复杂交互.该模型的结构如图5所示，具体来说，Dominant在自动编码器框架中利用从GCN获得的节点嵌入来重构原始的属性和结构信息.然后，通过结构上的重构误差和属性上的重建误差来获得异常分数，并通过异常分数的排序来标记异常.实验结果证明：利用GCN的深度模型Dominant的优越性.该方法虽然通过使用GCN可以很好地捕捉节点模态和属性模态的良好交互信息，但是该模型的设计比较简单，只是直接使用了GCN作为编码器，没有考虑到GCN的一些缺点，如平滑问题.

Fig. 5 Model structure of Dominant[45]图5 Dominant模型结构[45]

虽然将深度学习当作特征抽取工具提取出特征后用作异常检测任务已经取得良好效果，但是先进行特征抽取然后进行异常检测的方法很容易导致性能欠佳，因为第一步的特征抽取不知道随后的异常检测任务，很容易导致异常检测任务的关键信息在第一步已经被移除，从而陷入局部最优解.因此，Zong等人[66]采用了一种联合训练的方法，即将残差分析的损失与聚类分析的损失联合起来，构造一个统一的损失函数，利用深度神经网络技术去同时优化特征抽取与聚类分析的过程，从而取得更准确的异常检测结果.Li等人[59]首次将这种联合训练方法用于图上的异常检测，所提模型如图6所示，在模型左半部分，首先从结构和属性的角度提取特征，在获得节点在结构和属性上的隐层表示后，拼接其隐层特征后用于高斯密度估计，最后将特征重构的损失和密度估计的损失采用联合训练的方法，位于高斯分布边缘的节点具有较高异常分数.

Fig. 6 Model structure of SpecAE[59]图6 SpecAE模型结构[59]

图上的异常检测旨在发现模式与大多数参考节点明显不同的节点，但是，现有方法都忽略了图结构和节点属性之间复杂的跨模态交互.在文献[51]中，作者提出了一个通过双自动编码器(AnomalyDAE)进行异常检测的深度联合表示学习框架，该框架捕获了图结构和节点属性之间的跨模态交互，以实现高质量的嵌入.如图7所示，AnomalyDAE由结构自编码器和属性自编码器组成，以共同学习潜在空间中的节点嵌入和属性嵌入.该框架在结构编码器中通过采用注意力机制来学习不同邻居的重要性，以有效捕获结构模式，这在异常检测中扮演着重要作用.此外，通过将节点嵌入和属性嵌入两者作为属性解码器的输入，在重建节点属性的过程中学习结构和节点属性之间的跨模态交互作用.最后，可以通过从结构和属性2个角度测量节点的重构误差来检测异常.

Fig. 7 Model structure of AnomalyDAE[51]图7 AnomalyDAE 的网络结构[51]

Fig. 8 Model structure of AEGIS[52]图8 AEGIS模型结构[52]

3.1.2 半监督的深度图异常检测方法

通常情况下，异常检测被当作一个无监督学习问题来处理，大多数现有的方法仅限于包括有标签的正常样本，只有少数方法可以利用标记的异常，已有的半监督的深度异常检测方法通常假设在输入空间和学习到的特征空间中，彼此接近的点更有可能共享相同的标签，在深度神经网络层的隐藏层中能够学习鲁棒特征，保留区分属性，用于分离正常点和离群数据点.

目前只有少数学者在图上利用半监督学习的方法进行检测异常任务，Kumagai等人[61]提出了一种新的半监督下同时考虑图结构的标签和所有节点的属性信息进行异常检测的深度学习方法.在文献[61]中，为了学习有用的节点嵌入以进行异常检测，作者提出学习一个超球面，使包围正常节点嵌入的超球面的体积最小化，同时将异常节点嵌入在超球面之外，当要检测的节点属于学习到的最小球半径之外，则将该数据当作异常节点.具体来说，该方法首先通过利用图卷积神经网络抽取节点的嵌入表示H，然后针对有标签的正常实例，最小化正常实例节点到球中心的距离：

Lnor(θ)

(1)

从而学习到一个包含尽可能多正常样本的超球.其次，为了更有效地使用异常样本，考虑正负样本不平衡的特性，采用近似AUC的思想[67]：

RAUC(θ)

(2)

其中f是sigmoid函数，当a(vn)≫a(vm)时，f(·)取得较大值；当a(vn)≪a(vm),f(·)取得较小值，因此最大化式(2)鼓励异常节点的分数值要比正常节点的分数值高，让异常节点距离超球中心c的距离较远.最后该模型结合式(1)(2)这2个损失函数去优化模型参数，对剩下的未标记样本执行异常检测任务:

L(θ)Lnor(θ)-λRAUC(θ).

(3)

通过在不同比例的有标签数据下进行实验证明该方法优于已有的异常检测方法.

虽然文献[61]提出的算法在半监督的背景下对图上节点进行了异常检测，但是文献[61]仅仅使用图卷积神经网络去提取特征，没有考虑不同的节点贡献度以及平滑问题; 其次，GCN很难应用在超大图上，每次卷积操作计算都需要将整个图放入到内存和显存，计算量和内存与显存占用量会随着节点数的增加而递增，因此如何针对大图进行异常检测也是半监督深度异常检测方法未来的一个重要研究方向.

3.1.3 静态图上的异常检测对比实验

为了验证上述基于深度学习的静态图异常检测方法的有效性，本节将使用目前已公布源码的2篇文献[45,58]的代码，在公开数据集上进行对比实验，以评估他们在图深度异常检测方面的效果.使用的数据集基本情况如表2所示.由于现有的公开数据集通常没有异常标注，我们手动将5%的异常(包括结构异常、属性异常和两者组合而成的异常)注入到部分公开的属性化网络数据集中.遵循文献[31]中使用的策略，以确保注入的异常与实际异常相接近.异常注入过程包括：

Table 2 Summary of the Datasets表2 实验数据集信息

1) 计算每个类的节点数目的概率分布；

2) 用这些概率选择一个分类；

3) 对于结构异常：在所选分类中注入一个异常节点，使该节点具有(m+/-10%)的边连接其余(未选定)分类的节点，其中，m是所选分类中节点的平均度数；

4) 结构异常的节点的属性在语义上与从所选类中采样得到的关键字一致.

对于属性异常(从不同的分类中随机抽取属性)和组合异常(分别从2个不同的类中采样边和属性)采用了类似的方法.

实验结果如图9所示.Ding等人[45]提出的方法名为Dominant，Bandyopadhyay等人[58]提出了DONE和AdONE两种方法.属性网络中的离群点检测非常重要.DONE和AdONE都会在节点embedding过程中生成异常分值.取3次异常检测的加权平均值作为节点的异常分值并根据该分值对节点进行排序生成排名表L.由于每个数据集中有5%的异常节点，我们绘制了从排名表(L)中排名前5%到25%的节点的召回率.图9的实验结果表明DONE的表现在3个数据集上相对于其他2种方法都要稍差一些，这是由于DONE将属性和结构分别建模后仅仅使用特征变换矩阵W建模属性和结构的交互信息，而AdONE和Dominant分别利用了更加复杂的对抗训练和图神经网络建模交互信息，因此总是相比DONE取得更好的效果.Dominant和AdONE在不同数据集上各有优势，特别地，我们发现在Citeseer数据集上Dominant具有显著优势，通过对数据集的分析发现，Citeseer数据集相比其他数据集的特征维度较高并且更加稀疏，这说明Dominant利用图神经网络同时建模属性和结构信息可以处理更加复杂的数据集.实验表明：目前基于深度学习的图异常检测算法已经可以取得较好的精确度.

Fig. 9 Experimental results of deep learning based anomaly detection in static graph图9 基于深度学习的静态图异常检测实验结果

3.2 基于深度学习的动态图异常检测方法

本节重点介绍动态图上基于深度学习的异常检测方法，因为基于深度学习的技术主要引入了图上的结构和属性信息，而这些信息都会随时间发生变化，所以我们重点介绍因为时序引发的图结构和属性变化的相关异常检测方法.

3.2.1 基于结构变化的动态图异常检测方法

这类方法的主要思路是：针对由一系列静态图组成的动态图，寻找那些时间点，在这些时间点上图发生了显著变化或者发生了异常事件；进而，发现影响最大的节点、边或者子图结构.

DPADS[68]算法检测图的异常是和文献[32]类似的思想：异常的子结构(或子图)是正常模式的结构变种(正常模式边和节点的增加或者缺失).假设d(G1,G2)表示2个图G1和G2之间的结构差异度量，计算把图G1转化为G2的同构图的计算量(添加、删除点与改变标签的变化数量)，衡量G1和G2之间的差异.

DPADS算法把静态图上的异常检测算法GBAD和并行异常检测算法PLAD扩展到大规模动态图的异常检测中，如图10所示，Ti-1，Ti，Ti+1为时间滑动窗口.本文定义了3种基本类型图的异常：添加、修改和移除.添加异常是正常模式增加了节点或边，修改异常包含了一个节点或边的意外标签，移除异常的子结构比正常子结构缺少了边或节点.算法的输入为n个子图，这些子图既可以是静态图的划分，也可以是时序图的一部分.DPADS主要可以分为2个阶段：初始化和迭代处理.其中初始化阶段，其主要的目标是在n个子图中找出正常模式S和与其存在差异的异常模式.这个阶段可以归纳为：

Fig. 10 Diagram of DPADS[68]图10 DPADS[68]示意图

1) 并行处理n个子图，然后分别检测top-M个正常模式，一共可以得到n×M个正常模式;

2) 判断得到正常模式S;

3) 根据正常模式S得到异常模式结构.

迭代处理阶段的主要目标是迭代分析时序数据的结构异常.

1) 算法把时间窗口向后移动一个窗口，让新获取的子图包含在滑动窗口内;

2) 在新来到的子图中检测top-M个正常模式，从滑动窗口中的所有子图中判断得到正常模式S′.如果S′=S，那么就只需检测新子图里的异常；否则需要对窗口里的每个子图都基于正常模式S′检测异常结构;

3) 对每个异常子结构计算R值，值最小的子结构判定为异常结构,重复迭代过程.

为了减少恶意活动的影响并及时启动恢复过程，AnomRank[64]在准确性和实时性做出了改进，提出了一种快速准确的在线算法用于检测动态图中的异常.首先对异常进行分类，如图11(a)所示，除了像DPADS将节点的增加或者缺失作为异常外，如图11(b)所示，AnomRank将连接的节点之间的边数的变数作为异常，例如恶意的端口攻击中的频繁连接.论文基于已有的衡量节点重要性的PageRank算法，认为异常导致节点分数突然变化.作者首先定义了仅考虑节点的节点重要性(ScoreS)和考虑了节点和边权重的节点重要性(ScoreW)，在此基础上，作者设计了动态的重要性计算函数实现快速计算，将重要性分数变化大的节点识别为异常节点，从而实现实时的异常检测.

Fig. 11 Two changes in dynamic graphs: Structure change and edge weight change[64]图11 动态图的2种改变: 结构改变和边权重改变[64]

Yu等人[62]则是提出了一种基于图嵌入的动态图异常检测框架NetWalk，提出一种新的基于深度自编码神经网络的Clique Embedding方法来学习节点的向量表示(最小化每个walk中顶点对的距离)，这种节点向量表示方法，可以很好的基于聚类进行Clique Embedding异常检测.同时为了应对边异常，还构建了一个查询表，根据学习的图表示和阿达马变换(Hadamard Transform)对新的边进行实时编码，这种节点和边的编码方式可以得到“良好的摘要”.网络还为每个顶点维护了一个固定大小的蓄水池，用来解决动态图的数据更新问题，文献[62]中给出了新的边到来时候的3种更新策略，总结来说就是新的边到来时，会以P的概率替换水池里存在的顶点，删除边的时候只针对已经删除了的顶点进行替换，然后通过蓄水池中新的walk来更新网络.文中的边异常判断是通过计算新来的边和中心节点的距离来确定.

3.2.2 基于属性变化的动态图异常检测方法

基于特征的异常检测方法.这类方法的主要思想是“相似的图可能共享某些特征”，反过来说就是指异常结点(子图)和其他正常结点(子图)的特征存在很大不同，所以这类方法的主要步骤都是：

1) 从输入图的每个快照中，提取关键的特征值来为每个快照构造“摘要”;

2) 使用距离函数比较连续摘要;

3) 当距离大于阈值时，将相应摘要定性为异常.

其中不同算法的区别体现在：

1) 构造“图摘要”的方法不同；

2) 使用的距离或相似度函数不同；

3) 定义和选择阈值以将实例标记为异常的方式不同.

其中Akoglu等人[33]提出为每个快照创建摘要(例如将相关特征进行向量表示)，并使用距离函数对摘要进行连续快照比较，2个快照之间的某个阈值以上的距离表示它们之间的变化点或异常.算法会先为图中所有节点提取几个网络特征的时间序列，再建立一个相关矩阵，表示在特定时间窗口内图中所有节点对之间的“行为”相关性.然后导出所有节点的“行为”向量，并将其与在多个先前时间窗口内检测到的最近的过去“行为”的向量进行比较.如果发现当前的“行为”与最近的历史有很大不同，则将当前的时间窗口标记为异常.

基于社区的异常检测方法.这类方法的主要思想是时间序列中其社区结构与最近过去的快照有很大不同的快照是存在异常的.Miz等人[63]针对时空数据集(例如Web和社交网络的用户活动日志)提出了一种可扩展的异常检测方法，对此类网络中用户的集体行为进行异常检测.对一个属性图而言，节点的属性是动态时序信号，该方法先进行特征提取与过滤，仅保留时间序列中潜在的异常节点(时序属性中必须达到足够数量的异常)，丢弃明显非异常节点.然后借鉴Hebbian学习规则：2个神经元的共同激活会导致2个神经元之间的连接(突触)增强.该方法使用Hopfield网络方法学习一个记忆网络，即给定网络的初始结构，对2个初始连接的节点i和j，在时间t，根据某种相似性度量Sim{i,j,t}更新它们之间边的权重，因此相邻节点之间的边会随着相似性的变化得到增强或消除，最终具有相似行为的节点会强连接并在记忆网络中聚集在一起.通过对网络学习后的每个社区进行分析，可以了解发生的事件和异常活动.

3.2.3 基于结构和属性变化的动态图异常检测方法

在随时间演变的大图中，Wang等人[34]通过对节点属性和图结构信息进行建模，设计出一个异常定位框架来确定导致图结构发生变化的特定图实体并降低误报率.该方法先使用VAR模型(Vector Autoregression model)建模不同时刻图快照的特征矩阵,描述动态图中单个节点的行为历史的方法：

(4)

然后使用快速贪心算法对每个时间戳处的图快照进行分区，若相邻时间戳Ct,a和C(t-1),x检测到的社区的相似性超过阈值，相似性计算：

(5)

则将其中的2个社区连接匹配到一起，再使用VAR模型来了解社区路径的活动如何随时间变化，建模进化的社区路径，得到社区路径异常分数.再定义一个以社区为中心的节点模型，在固定的时间戳下将节点的特征向量与其所在社区的其他节点的平均特征向量进行比较，差异即为基于社区的节点模型中该节点的异常分数.如图12所示，给定一个节点，异常定位框架会判断当前节点在时刻t的属性是否满足：1)不遵循其自身的历史行为模式且其所在的社区路径显示异常活动;或2)不遵循其自身的历史行为模式,其所在的社区路径活动正常，但不遵循其所属社区的模式.若满足2个条件之一则认为节点在时间t是异常的.

Fig. 12 Dynamic graph anomaly location framework[34]图12 动态图异常定位框架[34]

4 图异常检测应用场景和数据集

4.1 图异常检测应用场景

在许多应用中，检测异常的能力变得越来越重要.目前，已经有许多成功的异常检测方法被开发出来，并将其广泛应用于一些高影响力领域.例如欺诈检测[69]、Web垃圾邮件和恶意软件检测[70-72]、垃圾评论检测[10,73]、网络入侵检测[74]以及医疗保健监视和警报[75]等.下面我们将介绍一些基于图数据的异常发现算法在现实场景中的应用.

4.1.1 电信欺诈

在众多类型的电信欺诈中，最普遍存在的一种是订阅欺诈.欺诈者经常使用虚假身份获取账户，目的是免费使用该服务而不进行任何付款.

最早基于图数据的在电信欺诈检测中有效的研究是由Cortes等人[76]完成的，他们主要将链接分析与时间和呼叫量信息一起使用.围绕每个电话账户构建和维护的子图被称为该账户的“communities of interest”(COI).COI主要包含在动态加权度量方面与给定账户最相关的其他电话账户，这些度量考虑了这些通话方之间的通话数量和持续时间.作者使用每天更新的这些信息丰富的子图，可以观察到2个区分性质.首先，作者发现欺诈性电话账户之间有关联，这些欺诈者要么直接相互呼叫，要么拨打相同的电话号码，这使得他们在COI中非常接近.第2个观察结果表明，有可能通过其COI与以前标记的欺诈性COI相似来发现新的欺诈性账户，这是由于被电话运营商检测到的欺诈者创建新账户并表现出相似的通话习惯，而这些习惯被其COI有效地捕获.

4.1.2 垃圾评论检测

客户每天都会在在线购物网站(亚马逊、淘宝网)上发表很多评论.评论会影响客户的购买决定，同时也会吸引大量旨在误导买家的垃圾评论发送者.例如2017-08—2018-07中国最大的二手商品应用程序闲鱼也遭受了垃圾评论的困扰，这些垃圾评论需要清除，因为它们不仅破坏用户体验，而且还为互联网欺诈提供了温床.

大多数现有的垃圾评论检测方法都专注于从评论内容或评论者行为中提取可靠的工程特征.Jindal等人[77]研究了重复评论内容以检测垃圾评论，他们收集了分别以评论、评论者、产品为中心的特征，并将其提供给逻辑回归模型;Ott等人[78]仅关注评论的内容，作者使用朴素贝叶斯和SVM分类器来解决问题.但关系在垃圾评论检测中也起着重要作用，例如，垃圾评论制造者经常将垃圾评论广告成组发布；基于关系的观察，Wang等人[79]提出了第1种基于图的垃圾评论检测方法，他们使用3种类型的节点(评论者、商店和评论)构建了“评论图”，然后以类似HITS的方式增强了评论者的信任度，商店的可靠性和评论的诚实性；Lucker等人[80]利用文献[79]构建的评论图和评论者之间的关系图进行垃圾评论检测；Akoglu等人[81]利用关系分类来检测垃圾评论，并开发了基于RMN的关系模型，以捕获评论者和商店之间的相关性，然后使用LBP进行推理；Li等人[72]提出了一种基于图卷积网络(GCN)的大规模反垃圾评论方法，用于在咸鱼上检测垃圾评论广告.

4.1.3 网络入侵检测

大多数基于图的网络入侵检测方法都专注于网络图的动态增长和变化.在此图中，节点表示网络中的代理，例如广告、文件、目录服务器和客户端节点，边表示它们在网络上的通信.跟踪网络图的动态性质实际是基于计算节点的通信行为在受到攻击时会发生变化的假设.

Idé等人[82]监视节点的“活动”向量.节点的活动分数是集体计算的，如果一个节点链接到许多活动节点，则其活动得分很高.通过此定义，活动向量实质上成为描述通信图的邻接矩阵的主要特征向量.他们通过测量向量方向和大小的变化来跟踪该向量随时间的变化，并开发在线阈值技术来决定何时将更改标记为重要事件.这些事件可能对应于网络攻击、故障和其他网络配置更改.Sun等人[83]利用矩阵分解来捕获网络活动的范数.他们采用称为紧凑矩阵分解的稀疏高效方法来分解网络图的邻接矩阵，并使用重构的相对和平方误差作为随时间变化的变化度量，以跟踪网络图新来的快照.Ding等人[84]考虑了网络社区的分析, 监视跨社区的通信行为以发现网络入侵.直觉上，跨越社区界限的交流被认为是可疑的，可以视为攻击的信号. ROC曲线表明，他们提出的方法可实现90%以上的检测准确率，但在带有恶意攻击的ground truth数据中，误报率较高，约为50%.

4.1.4 社交网络

对于在社交网络平台上传播恶意软件的新方法，我们将其称为Socware. Socware可由出现在诸如Facebook和Twitter之类的社交媒体平台的新闻源中的任何帖子组成，这些帖子有4个特点：

1) 引导用户进入危害用户设备的恶意网站；

2) 为了谋取利益，给用户承诺提供虚假奖励并使用户执行某些任务(例如填写调查问卷)；

3) 使用户通过单击或“点赞”来提高某些页面的声誉和知名度等；

4) 使用户分享或重新发帖.

为了对抗Socware，Rahman等人[85]提出了一个分类框架，该框架利用了“social-context-aware”特征，例如共享特定帖子的不同用户之间帖子的消息相似性.除了其他基于内容的特征外，还包括该帖子在网络中的传播大小，其他网络用户对该帖子的“喜欢”和评论计数等.Gao等人[86]基于网络级的特征，例如发件人的程度，用户之间的交互历史等，使用增量聚类对社交网络进行在线垃圾邮件过滤，这些方法依赖于基于集体特征集的学习分类器.

4.2 图异常检测数据集介绍与构造

4.2.1 公开数据集

目前主要的可用于图异常检测的公开数据集如表3所示.此外，异常检测数据集(outlier detection datasets, ODDS)提供了大量带有ground truth的异常检测数据集，包含来自不同领域的数据集，并将其集中地呈现给研究者.ODDS将数据集进行了划分，主要包括：1)多维点数据集：每个数据点有一个记录，每个记录包含多个属性;2)用于事件检测的时间序列图数据集：时间图数据，其中图随时间推移动态变化，新的节点和边会到达，或现有的节点和边会消失;3)时间序列点数据集(多变量/单变量)：时间点数据，其中每个点都有一个或多个属性，并且这些属性会随时间变化;4)对抗/攻击场景和安全性数据集：来自在线评价系统的意见欺诈检测数据,网络安全数据，例如DoS，DDoS等攻击场景的入侵检测;5)拥挤场景视频数据：用摄像机获取的视频片段.其中时序图数据集可作为图异常检测的数据集.

Table 3 Public Datasets for Graph Anomaly Detection表3 图异常检测公开数据集

4.2.2 异常注入方法

异常检测的研究大多使用真实数据用以实验.此外很多研究者还使用合成数据来模拟特定场景.出于隐私考虑，组织和利益相关者不愿意分享他们可用于异常检测的信息.因此可以考虑使用综合创建的数据，即在已有的公开数据集中人为地注入异常数据.目前异常注入方法主要有3种：1)扰动原始数据，即将原本图中正常的数据进行人为的调整，使其呈现异常状态；2)插入新的异常数据，即对原有图进行扩展，插入异常的节点、边等；3)在包含阶段类别标签的图中，将对应标签数目出现次数最少的节点作为异常进行处理.

5 图异常检测研究挑战和未来

尽管目前在图的异常检测领域已有丰富的研究工作，但是仍面临着很多挑战：

1) 数据的相关性.首先，数据的相关性使得针对图对象的异常定义变得困难.在传统的异常检测中，对象或数据点被视作是相互独立的、同分布的，而图数据中的对象由于节点间边的存在往往具有复杂的相关性.因此，如何使用深度学习更好地挖掘这种相关性是异常检测面临的挑战之一.

2) 定义的多样性.鉴于图的丰富表示形式，图中异常的定义比传统的异常点检测要更加多样化.例如，与图子结构相关的新型异常类型在许多应用中都有所展现，如交易网络中的洗钱环节等.深度学习算法如何兼容这些多样化的异常定义也面临挑战.

3) 检测结果的可解释性.尽管深度学习可以获得较好的效果，但其结果的可解释性较差，而异常检测中的结果解释和归因尤为重要，基于深度学习的图异常检测算法如何为结果提供更好的解释也是面临的重要挑战之一.

4) 算法的效率和自适应性.深度学习的效率也是其缺陷之一，在图的规模不断扩大的情况下，检测算法需要高效且可扩展；此外，当动态图的变化幅度较大时，基于深度学习的检测算法需要能够处理这种变化；最后，由于深度学习在不同的数据上往往需要人工设置不同的参数，如何减少人工的参与也是挑战之一.

综上所述，基于深度学习的图异常检测的未来方向主要包括4个方面：

1) 考虑将深度学习异常检测算法并行化和分布式化.面对越来越复杂的任务，数据和深度学习模型的规模都变得日益庞大.例如，Twitter用户数量已经超过3亿，因此其形成的社交网络的规模非常之大.因此，如果不做任何剪枝处理，深度学习模型可能会拥有上百亿、甚至是几千亿个参数，必然会导致基于深度学习的异常检测算法耗时过长的情况，因此尝试对其进行并行和分布式处理是有效且直观的解决方式.但是对深度学习算法的并行和分布式化，不应只局限在对串行算法进行多机实现以及底层实现方面的技术，更应该基于对机器学习的完整理解，将分布式和深度学习紧密结合在一起，结合深度学习以及图数据的特点，设计全新的真正合二为一的“分布式深度学习异常检测”算法.

2) 图类型的兼容性.面对日益复杂的图，现有的深度学习图异常检测算法不能很好地适用所有场景，大多数模型针对同质图，对包含不同形态的异质图的研究很少.例如在异常检测中通常会涉及到静态图、动态图、属性图等类型，而目前论文提出的方法都只针对其中某一种类型，无法兼顾所有的图类型，更无法处理更为复杂的异质图.因此，应当考虑设计可以兼容多种图数据类型的算法，以应对日益复杂的数据类型.

3) 异常的解释和归因.深度学习的解释性通常较差，将其运用到图异常检测上往往会导致检测结果难以直观地理解；但是图异常检测不应只停留在算法层面，而是应当更好地去考虑如何呈现给用户更易理解的检测结果.首先必须考虑将异常检测结果进行直观的、可视化的呈现，其难点在于对于大规模的图，其可视化需要耗费大量CPU和内存资源，应当如何去兼顾资源消耗和可视化效果.深度学习模型可解释性指对模型内部机制的理解以及对模型结果的理解.其重要性体现在：在建模阶段，辅助开发人员理解模型，进行模型的对比选择，必要时优化调整模型；在投入运行阶段，向业务方解释模型的内部机制，对模型结果进行解释；但是目前此深度学习模型的可解释性仍是学术界的难点及研究热点之一.

6 总结与展望

本文首先介绍了图异常检测的相关背景和技术基础，之后从静态图和动态图的角度出发，讨论了基于深度学习的图异常检测的各种技术方法.然后介绍了图异常检测方法在各个领域的实际应用，并介绍了现有工作中常用的数据集和异常注入方法，为之后研究人员开展相关的研究打下了基础.最后，本文还讨论了基于图数据运用深度学习进行异常检测面临的挑战和未来研究趋势，这些对未来本领域的研究具有很强的指导意义.这篇综述的目的是调查和分析用于图异常检测的各种深度学习模型，并评估相关技术方法的适用性，在为特定领域的异常检测选择深度学习模型时，这些评估和分析结果可以作为指南性的意见.基于深度学习的异常检测技术目前仍然是十分活跃的研究方向，但是在图数据方面的应用研究却相对缺乏，未来会有更多的技术和研究成果出现，综述的内容也会进行不断地更新和扩展.

作者贡献声明：陈波冯负责论文主要内容的调研和撰写，以及论文的校验，李靖东辅助调研相关内容并提供指导意见，卢兴见，王晓玲，沙朝锋，张吉对文章的结构和内容提供指导意见，其中卢兴见和王晓玲贡献相同，为共同通信作者.