type
status
date
slug
summary
tags
category
icon
password
基于深度学习的图形异常检测综述
基于深度学习的图形异常检测综述摘要1 介绍1.1 在深度学习图异常检测（GADL）中的挑战。1.2 已有的异常检测综述研究1.3 贡献2 基础知识3 异常节点检测（ANOS ND）3.1 普通图的异常节点检测3.1.1 传统的非深度学习技术3.1.2 基于网络表示的技术3.1.3 基于强化学习的技术3.2 属性图的异常节点检测3.2.1 基于深度神经网络的技术3.2.2 基于GCN的技术3.2.3 基于强化学习的技术4 动态图的异常节点检测4.1 基于网络表示的技术4.2 基于 GAN 的技术异常节点检测技术摘要5 异常边缘检测（ANOS ED）5.1 基于深度神经网络的技术5.2 基于 GCN 的技术5.3 基于网络表示的技术6 动态图的异常边缘检测6.1 基于网络表示的技术6.2 基于 GCN 的技术7 异常子图检测（ANOS SGD）8 异常图检测（ANOS GD）8.1 基于 GNN 的技术8.2 基于网络表示的技术9 动态图的异常图检测异常边、子图和图检测技术总结10 已发表的算法和数据集 10.1 公开的算法10.2 公开的数据集10.3 合成数据集生成10.4 评估标准11 未来方向11.1 异常边、子图和图的检测11.2 动态图中的异常检测11.3 异构图中的异常检测11.4 大规模图中的异常检测11.5 多视图图异常检测11.6 伪装/对抗性异常检测11.7 不平衡的图异常检测11.8 多任务异常检测11.9 图异常解释性11.10 图异常识别策略11.11 系统性基准测试11.12 统一异常检测框架12 结论
摘要
（介绍异常检测）。通常，检测任务通过识别特征空间中的离群数据点来解决，但这种方法本质上忽略了现实世界数据中的关系信息。传统的异常检测技术无法很好地解决这个问题，因为图数据的复杂性（例如，不规则结构、关系依赖、节点/边的类型/属性/方向/重复/权重、大规模等）。由于深度学习的出现，成功地克服了这些限制，最近深度学习在图异常检测方面引起了越来越多的关注。在这份调查中，我们旨在提供对当代深度学习技术在图异常检测中的全面系统回顾。具体而言，我们提供了一个遵循任务驱动策略的分类法，并根据它们能够检测到的异常图对象对现有工作进行分类。在这项研究中，我们特别关注了这一领域的挑战，并讨论了各类技术中的关键直觉、技术细节以及相对优势和劣势。从调查结果中，我们突出了12个未解决和新兴问题的未来研究方向，这些问题涵盖了图数据、异常检测、深度学习和实际应用所引入的。此外，为了为未来的研究提供丰富的有用资源，我们编制了一组开源实现、公共数据集和常用的评估指标。通过这项调查，我们的目标是创建一个“一站式”资源，提供问题类别和现有方法的统一理解，公开可用的实际资源，以及使用深度学习进行图异常检测的高影响力开放挑战。
1 介绍
异常首次由格鲁布斯（Grubbs）于1969年[1]定义为“在其出现的样本中似乎明显偏离其他成员”，而异常检测的研究始于19世纪的统计学界。
为了检测异常，传统技术通常将现实世界的对象表示为特征向量，然后在向量空间中检测离群数据点[22]-[24]。尽管这些技术在定位表格数据格式下的偏离数据点方面表现出很大威力，但它们本质上舍弃了对象之间的复杂关系[25]。
在现实中，许多对象之间存在丰富的关系，这些关系可以为异常检测提供有价值的补充信息。例如社交网络中虚假用户可以使用正常用户的有效信息创建，或者模仿良性用户的属性来伪装自己，在这种情况下，虚假用户和良性用户的特征几乎相同，传统的异常检测技术可能无法仅仅通过特征信息来识别它们。
介绍早期依赖于手工制作的特征工程或领域专家构建的统计模型，数据量大计算开销大。不基于深度学习的技术还缺乏捕捉真实对象的非线性属性的能力[24]。深度图表示学习和图神经网络（GNNs），进一步丰富了深度学习在图数据挖掘中的能力[58]–[62]。深度学习图异常检测（GADL）开始在异常检测的前沿取得领先地位。
1.1 在深度学习图异常检测（GADL）中的挑战。
这些与深度学习相关的挑战被归类为技术特定挑战（Tech-CHs）
- 异常感知的训练目标。因为没有对于真实异常的先验知识，异常也和大多数情况不同，所以选数据很重要。
- 异常解释性。需要提供令人信服的证据来支持随后的异常处理过程。
- 高昂的训练成本。因为输入数据的规模问题，成本也高。
- 超参数调优。
监督学习中，有标记数据调整超参数比较简单。在无监督异常检测中，没有可用的标记数据来评估不同超参数设置下模型的性能，更困难。
1.2 已有的异常检测综述研究
关于广义异常检测技术，有一些代表性的综述文章，包括[18]、[45]和[44]。但只有Thudumu等人的最新工作[44]涵盖了图异常检测的主题。认识到深度学习的强大之处，这三篇当代综述文章，分别是Ruff等人的[71]、Pang等人的[24]和Chalapathy与Chawla的[47]，专门审查了基于深度学习的异常检测技术。
至于图异常检测，Akoglu等人的[25]、Ranshous等人的[48]和Jennifer与Kumar的[49]集中关注了图异常检测，审查了该领域的许多传统方法，包括统计模型和机器学习技术。其他综述文章专注于图异常检测的特定应用，如计算机网络入侵检测和在线社交网络中的异常检测，例如[3]、[6]、[19]和[50]–[54]。
（有人写技术，没人写综述，作者写了）下图技术时间线。
1.3 贡献
- 这是深度学习在图异常检测中的第一份综述。全面地针对深度学习在图异常检测中的综述
- 一份系统而全面的综述。包含各种期刊会议技术。然后，我们从以下角度全面回顾了现有研究成果：1) 深度方法背后的动机；2) 识别图异常的主要思路；3) 传统非深度学习技术的简要介绍；4) 深度学习算法的技术细节。
- 未来的方向。突出了12个未来的研究方向，涵盖了由图数据引入的新兴问题、异常检测、深度学习模型和实际应用领域。
- 充沛的资源。我们的综述还提供了大量的开源异常检测算法、公共数据集、合成数据集生成技术，以及常用的评估指标，以推动图异常检测领域的最新进展。这些已发布的资源为未来研究提供了基准数据集和基线。
- 一个新的分类系统。我们根据图或图数据库中存在的不同类型的异常（即节点、边、子图和图）对这份综述进行了组织。我们还指出了不同类型的图异常之间的差异和相似之处。
文章结构。第 2 节，不同类型的设定的基础知识。第 3-9 节，回顾检测异常节点、边、子图和图的现有技术。第 10 节，已知图异常检测算法和数据集，然后总结了常用的评估指标和合成数据生成策略。第 11 节，未来方向。第 12 节，总结。
2 基础知识
遵循了现有工作中图的传统分类，如[25]，[48]，[52]，将它们分类为静态图、动态图和图数据库。除非另有说明，否则以下各节提到的所有图形都是静态的。
- 定义 1 （普通图）。点、边、邻接矩阵等。
- 定义 2 （属性图）。在普通图的基础上，属性矩阵 表示，节点 的属性向量 ， 是向量维度
- 定义 3 （动态图）。 表示在时间步 时刻，节点集合、边集合、节点的属性矩阵，边的属性属性矩阵。
3 异常节点检测（ANOS ND）
在静态图中检测异常节点时，异常节点与常规节点之间的差异主要来自图的结构信息以及节点/边的属性[41]，[72]–[74]。在对静态图具有先验知识（即社群结构、属性）的情况下，异常节点可以进一步分为以下三种类型:
- 全局异常仅考虑节点属性。这些节点具有与图中所有其他节点显著不同的属性。
- 结构异常仅考虑图的结构信息。它们是具有不同连接模式的异常节点，例如连接不同区域、节点密集。
- 社群异常考虑了节点属性和图的结构信息。它们被定义为与同一社群中的其他节点相比具有不同属性值的节
3.1 普通图的异常节点检测
先总结代表性的传统非深度学习方法，再介绍一个种基于表示学习的更近期、先进的检测技术。
3.1.1 传统的非深度学习技术
传统的非深度学习技术关键思想是将图异常检测转化为传统的异常检测问题，因为具有丰富结构信息的图数据不能直接由传统的检测技术处理。为了弥合这一差距，许多方法[38]，[75]，[76]使用与每个节点相关的统计特征，如入度/出度，来检测异常节点。
举例来说，OddBall [38] 利用从每个节点及其 1 跳邻居中提取的统计特征来检测特定的结构异常，这些异常具有以下特点：
- 形成近似团或星形的局部结构
- 与邻居之间的连接非常密切，使得总权重极大
- 与其中一个邻居存在一个单一的主要重连接。
通过精选合适的统计特征，可以根据它们偏离的特征模式来识别异常节点。因此，这些技术通常需要巨大的成本来评估最显著的特征，并且不能有效捕捉结构信息。
3.1.2 基于网络表示的技术
为了从图结构中捕获更有价值的信息用于异常检测，广泛使用了网络表示技术。通常，这些技术将图结构编码成嵌入向量空间，并通过进一步的分析来识别异常节点。
例如，胡等人 [77] 提出了一种有效的嵌入方法，用于检测与许多社区连接的结构异常。首先，它采用图分区算法（例如，METIS [78]）将节点分组成 d 个社群（d是用户指定的数量）。然后，该方法采用特别设计的嵌入过程来学习节点嵌入，这些嵌入可以捕捉每个节点与 d 个社区之间的链接信息，生成节点 i 的嵌入 ，表示 i 属于社群 c 成员的程度。如果属于值为 ，否则是 0 进行初始化，使直接连接的节点具有相似的嵌入，而未连接的节点则是不相似的。
生成节点嵌入后，用于进一步的异常检测分析的节点 i 与 d 个社区之间的链接信息被量化表示为
NB(i) 包含节点 i 的邻居节点，如果 i 和社群 c 有很多连接，那么 的值会很大，最后胡等人[77]制定了一个评分函数来分配异常分数
迄今为止，许多常规的网络表示方法，如Deepwalk [79]、Node2Vec [80]和LINE [81]，已经展现出它们在生成节点表示方面的有效性，并被用于异常检测性能验证[82]–[85]。通过将传统的异常检测技术，如基于密度的技术[86]和基于距离的技术[87]，与节点嵌入技术配对，可以根据它们在嵌入空间中的可区分位置（即低密度区域或远离大多数节点的位置）来识别异常节点。
3.1.3 基于强化学习的技术
检测异常节点可以自然地视为一个问题，即确定节点属于哪一类 - 异常或良性。作为一般性选择性收集任务的特殊情况，可以通过最近的工作[88]来解决异常节点检测问题，该工作直观地将强化学习和网络嵌入技术结合起来进行选择性收集。所提出的模型，NAC，在没有任何人工干预的情况下，使用带标签的数据进行训练。
具体而言，它首先选择一个由部分观察到的节点和边组成的种子网络。然后，从种子网络开始，NAC采用强化学习来学习一个节点选择计划，以便可以识别未发现区域中的异常节点。这是通过奖励能够选择标记异常节点的选择计划来实现的。通过离线训练，NAC 将逐步学习一个最优/次优的异常节点选择策略，并逐步发现未发现图中的潜在异常。
3.2 属性图的异常节点检测
除了结构信息外，现实世界的网络还包含与节点关联的丰富属性信息[89]，[90]。这些属性提供了关于真实对象的补充信息，与图结构一起，现在可以检测到更多不平凡的隐藏异常。
为了清晰起见，在本调查中，我们区分深度神经网络和图神经网络。我们按以下方式回顾基于深度神经网络（Deep NN）的技术、基于GCN的技术和基于强化学习的技术，以进行异常节点检测（ANOS ND）。由于页面限制，其他现有的工作，包括传统的非深度学习技术、基于GAT [91]的技术、基于GAN的技术以及基于网络表示的技术，将在附录C中进行调查。
3.2.1 基于深度神经网络的技术
例如，Bandyopadhyay 等人（[82]）开发了一个无监督的深度模型，名为 DONE，用于检测属性图中的全局异常、结构异常和社群异常。该工作为每个节点测量了三个异常得分，这些得分指示了以下情况的可能性：
- 与不同社群中的节点具有相似性的属性
- 与其他社群相连
- 在结构上属于一个社群，但是属性遵循另一个社群的模式
如果特定节点展现出这些特征中的任何一种，那么它将被分配一个较高的得分，被视为异常节点。为了获取这些得分，DONE 采用了两个独立的自编码器（AE），即结构 AE 和属性 AE，如图 4 所示。两者都通过最小化重构误差和保持同质性（尽量保持数据的结构或特征的一致性）来训练，同质性假设连接的节点在图中具有相似的表示。在训练AE 时，本身结构或属性模式不符合标准的预定义特征节点因为很难重构，引入了更多的重构错误，应该减轻异常的不利影响以达到最小化误差的目标。因此，DONE专门设计了一个具有五个项的异常感知损失函数（公式 3、4、5、6、7，两个与节点的结构化信息和属性相关，两个公式用户维护同质性，一个使图结构和节点属性相互补充）。通过最小化这些损失函数的总和，可以量化每个节点的异常得分，并确定具有较高得分的前k个节点作为异常节点。
3.2.2 基于GCN的技术
在[93]中，Ding 等人使用了网络重构的结构和属性的错误来测量每个节点的异常得分。提出的方法DOMINANT 包括三个部分，即图卷积编码器、结构重构解码器和属性重构解码器。图卷积编码器通过多个图卷积层生成节点嵌入。结构重构解码器倾向于从学习到的节点嵌入中重构网络结构，而属性重构解码器则重构节点属性矩阵。整个神经网络被训练来最小化损失函数公式 8，根据公式 9 计算异常得分。
为了提高异常节点检测的性能，彭等人（Peng et al.）的后续研究[94]进一步探讨了来自多个属性视角的节点属性以检测异常。多个属性视角被用来描述对象的不同角度[95]–[97]。因为异常可能在一个视角下看起来正常，但在另一个视角下看起来异常。ALARM 应用多个GCNs来编码不同视角的信息，并采用加权聚合它们以生成节点表示。这个模型的训练策略类似于 DOMINANT [93]，它旨在最小化网络重构损失和属性重构损失（公式 10）
与使用重构错误来识别意外节点不同，Li等人提出了SpecAE [98]，通过密度估计方法，即高斯混合模型（GMM），来检测全局异常和社群异常。全局异常可以通过仅考虑节点属性来识别。对于社群异常，由于它们与邻居的特征有明显的差异，因此需要联合考虑结构和属性。因此，SpecAE 使用图卷积编码器来学习节点表示并通过反卷积解码器重构节点属性。然后，使用节点表示来估计 GMM 中的参数。由于全局和社群异常的属性模式不同，正常节点预计在 GMM 中表现出更大的概率，而具有最低概率的 k 个节点被视为异常。
在[99]中，Wang等人开发了一种新颖的欺诈检测模型，通过用户的关系和特征来识别欺诈者。他们提出的方法，Fdgars，首先将在线用户的评论和访问的物品建模为它们的特征，然后基于这些特征识别出一小部分重要的欺诈者。在最后一步中，通过使用用户-用户网络、用户特征和已标记的用户，以半监督的方式训练了一个图卷积网络（GCN）。训练后，该模型可以直接对未见过的用户进行标记。
GraphRfi [100]，也探索了将异常检测与其他下游图分析任务结合的潜力。它旨在利用异常检测来识别恶意用户，并通过减轻这些不可信用户的影响，为良性用户提供更准确的推荐。具体而言，它部署了一个GCN框架，将用户和物品编码成一个共享的嵌入空间，用于推荐，然后通过一个额外的神经随机森林，使用它们的嵌入来将用户分类为欺诈者或正常用户。对于用户和物品之间的评分预测，该框架通过将更少的权重分配给怀疑用户的训练损失，减少了可疑用户的相应影响。同时，用户的评分行为也为欺诈者检测提供了辅助信息。这两个应用（异常检测和推荐）之间的互惠关系表明了在多个图学习任务之间共享信息的潜力。
3.2.3 基于强化学习的技术
与NAC不同，Ding等人[101]研究了在带属性的图中使用强化学习进行异常节点检测。他们提出的算法，GraphUCB，同时对属性信息和结构信息建模，并继承了上下文多臂老虎机技术的优点[102]，以输出潜在的异常。通过根据节点特征将节点分组成k个簇，GraphUCB形成一个k臂老虎机模型，并测量选择特定节点作为潜在异常进行专家评估的回报。通过专家对预测异常的反馈，决策策略不断优化。最终，可以选择出最有潜力的异常。
4 动态图的异常节点检测
现实世界中的网络可以建模为动态图，用于表示不断演化的对象以及它们之间的关系。除了结构信息和节点属性外，动态图还包含丰富的时间信号，例如图结构和节点属性的演化模式。因为引入时间信息检测所以引入大量数据，可以提供更多细节也使成本提高。
在本节中，我们将按如下方式回顾基于网络表示的技术和基于生成对抗网络（GAN）的技术。传统的非深度学习方法的相关技术将在附录D中进行回顾。
4.1 基于网络表示的技术
在[84]中，Yu等人提出了一种灵活的深度表示技术，称为NetWalk，用于仅使用结构信息在动态（普通）图中检测异常节点。它采用自编码器来学习初始图上的节点表示，并在添加新边或删除现有边时逐步更新它们。为了检测异常，NetWalk首先执行流式 k 均值聚类算法[122]，将当前时间戳中的现有节点分成不同的簇。然后，针对每个节点，根据其与 k 个簇的最近距离来测量其异常分数。当节点表示被更新时，簇中心和异常分数会相应地重新计算。
4.2 基于 GAN 的技术
因为真实数据的稀缺性，许多研究工作投入到对异常或常规对象的特征进行建模，以便能够有效地识别异常，生成对抗网络（GAN）[123]因其在捕捉真实数据分布和生成模拟数据方面出色的性能而受到广泛关注。
受到最近“坏”的生成对抗网络（GAN）[124]的进展的启发，郑等人[121]通过仅使用观察到的良性用户属性来绕过欺诈检测问题。基本思想是抓住正常活动模式并检测行为明显不同的异常情况。所提出的方法，OCAN，首先通过使用良性用户的历史社交行为（例如，历史帖子、帖子的URL）来提取良性用户的内容特征，因此该方法被分类为动态类别。采用了基于长短时记忆（LSTM）的自编码器[125] 来实现这一点，并假设良性用户和恶意用户在特征空间中处于不同的区域。接下来，训练了一个新颖的单类对抗网络，包括一个生成器和一个鉴别器。具体来说，生成器生成位于良性用户相对低密度区域的互补数据点。鉴别器的任务是从良性用户生成的样本中区分出生成的样本。训练之后，鉴别器学习了良性用户的区域，因此可以根据它们的位置识别异常情况。
NetWalk [84] 和 OCAN [121] 都有望解决异常节点检测问题，但它们分别只考虑了图的结构或属性。考虑到静态图异常检测技术在分析这两个方面方面取得的成功，当同时考虑动态图中的结构和属性信息时，可以预见到增强的检测性能。因此，在第11节中，我们强调了这个尚未探索的领域，为未来的研究工作提供了重要的方向。
异常节点检测技术摘要
5 异常边缘检测（ANOS ED）
与异常节点检测不同，异常边缘检测（ANOS ED）旨在识别异常连接。这些连接通常反映了真实对象之间的意外或异常关系[126]。本节将回顾静态图的最新 ANOS ED 方法，第6节总结了动态图的技术。表3提供了摘要信息。本节包括基于深度神经网络（NNs）、图卷积网络（GCNs）和网络表示的方法。非深度学习技术在附录E中。
5.1 基于深度神经网络的技术
Ouyang等人[127]通过使用深度模型对边缘的分布进行建模，以识别最不可能出现为异常的现有边缘（如图6所示）。通过 FCN 层将每个边缘的概率转化为低维向量，并通过对其本身及其邻居向量进行均值聚合来生成节点 u 的表示。接下来，节点的表示被输入到另一个全连接网络（FCN）中，使用 softmax 和交叉熵损失函数来为每个边分配一个异常得分。
5.2 基于 GCN 的技术
Duan等人[128]证明异常的边缘会在节点嵌入时产生负面影响，但是节点嵌入应该解决异常边缘的影响，异常边缘的检测又是通过节点嵌入检测的。所以提出的 AANE 在训练过程中通过迭代更新嵌入和检测结果来共同考虑这两个问题。
在每个训练迭代中，通过 GCN 生成节点嵌入 Z，并学习一个指示矩阵 I 来发现潜在异常边，对于指示矩阵 I 的值，如果两个节点 u、v 的链接预测概率（使用两个节点嵌入的双曲正切计算）小于平均值为 1，其他情况为 0。（论文里有详细公式）
AANE 的总损失函数包含两个部分：异常感知损失（Laal）和调整拟合损失（Lafl）。Laal旨在惩罚链接预测结果和指示矩阵I（公式 11），其中 V 是节点集合 N(u) 是节点 u 的邻居。Lafl用于量化与潜在异常边缘的移除相关的重建损失（公式 12）。B 是从邻接矩阵 A 中去掉所有预测的异常。通过最小化这两个损失AANE将识别出具有最低概率的前k个边缘作为异常。
5.3 基于网络表示的技术
与使用节点嵌入进行ANOS ED不同，直接从图中学习的边缘表示也可以用于区分异常。如果边缘表示能够很好地保留图结构和节点对之间的交互内容（例如在线社交网络中的消息，引用网络中的合著论文），那么可以期望获得增强的检测性能。到目前为止，一些研究，例如Xu等人的研究[129]，已经显示出生成边缘表示的有希望的结果。尽管它们并不是专门为图异常检测而设计的，但它们指出了一种可能的ANOS ED方法。这在第11.1节中被强调为潜在的未来方向。
6 动态图的异常边缘检测
动态图在反映随时间出现/消失的边缘方面具有强大的能力[130]。可以通过建模图结构的变化并捕获每个时间步的边缘分布来区分异常边缘。本节回顾了关于动态图上的ANOS ED的最新方法。
6.1 基于网络表示的技术
基于网络表示的技术的直观思想是将动态图结构信息编码到边缘表示中，并应用上述传统的异常检测技术来识别不规则边缘。这听起来很简单，但在图结构演化时生成/更新信息丰富的边缘表示仍然存在重要挑战。
ANOS ND 模型 NetWalk [84] 也能够检测动态图中的异常边缘，遵循基于距离的异常检测思路，NetWalk 使用节点嵌入将边缘编码到一个共享的潜在空间中，根据它们到潜在空间中最近边缘簇中心的距离来识别异常。当新的边缘出现或现有的边缘消失时，节点和边缘表示会从每个时间戳的临时图中的随机游走中进行更新，之后重新计算边缘簇中心和边缘异常分数。
NetWalk 仅仅更新边缘表示，而没有考虑长期/短期节点和图结构的演化模式。
6.2 基于 GCN 的技术
为了更有效地进行ANOS ED，郑等人[131] 直观地结合了动态图中边缘的时间、结构和属性信息来度量其异常性。他们提出了一个半监督模型，AddGraph，该模型包括一个 GCN 和带有注意力机制的门控循环单元（GRU）[132]，以在每个时间戳中从时间图中捕捉更具代表性的结构信息和它们之间的依赖关系。
在每个时间戳 t，GCN使用 t-1 时刻的输出隐藏状态（Ht−1）生成节点嵌入，然后 GRU 从节点嵌入和先前隐藏状态的注意力中学习当前的隐藏状态 Ht（如图7所示）。在获得所有节点的隐藏状态Ht之后，AddGraph 基于与其相关联的节点为时间图中的每个边分配异常分数。所提出的异常得分函（公式 13），损失函数（公式 14）
7 异常子图检测（ANOS SGD）
不同于独立的个体图异常，即单个节点或边，可疑子图中的每个节点和边可能是正常的。然而，当将它们视为一个集合时，它们变得异常。例如，Wang等人[134]将在线购物网络表示为二分图（一种具有两种节点类型和一种边类型的异构图），其中用户是源节点，物品是汇节点。他们的研究旨在学习具有异常感知的用户表示，以便在向量空间中将同一组中的可疑用户定位在靠近的位置，而良性用户则会远离（如图8所示）
开发的模型DeepFD通过以下方式度量两个用户之间的行为相似性，每个物品在所有已经审查的物品中共享的物品的百分比，用户表示使用传统的自编码器生成，该编码器使用三个损失进行训练：
- 重构损失。确保可以使用学习到的用户表示和物品表示正确重构二分图结构。
- 保留了在学习到的用户表示中的用户相似性信息。如果两个用户行为相似，它们的表示也应该相似。
- 对所有可训练参数进行正则化。
另一项工作，FraudNE [136] 的目标是将这两种类型的节点编码到共享的潜在空间中，其中同一密集块中的可疑用户和物品非常接近，而其他节点均均匀分布，FraudNE采用了两个传统的自动编码器，分别是源节点自动编码器和汇节点自动编码器，用于学习用户表示和物品表示。这两个自动编码器都被训练以共同最小化它们各自的重构损失和一个共享的损失函数。重构损失衡量输入和解码特征之间的差距，共享损失保证了每个链接的用户和物品具有相似的表示。
8 异常图检测（ANOS GD）
除了异常节点、边和子图之外，图形异常还可能以一组/数据库中的异常图形形式出现。通常情况下，图数据库被定义为：
- 定义 4 （图数据库）。一组图，每个图包括节点集合、边集合、节点属性矩阵、边属性矩阵。
这种图级别的 ANOS GD 旨在检测与其他图明显偏离的个别图形。例如脑部疾病检测，不同的分子被表示为节点和边，可以作为异常分子检测。
ANOS ND/ED/SGD 与 ANOS GD 不兼容，因为它们专门用于检测单个图中的异常，而ANOS GD旨在检测图级别的异常。解决这个问题通常有以下方法：
- 使用图内核测量图之间的成对接近度 [139]
- 检测由异常节点组成的异常图信号的出现 [140]
- 使用频繁的模式对图进行编码 [63]
然而，这些方法都不基于深度学习。截至目前，进行深度学习的ANOS GD研究非常有限。因此，在第11.1节中将这个问题突出为潜在的未来方向。
8.1 基于 GNN 的技术
Dou 等人[141]将虚假新闻检测转化为一个 ANOS GD 问题，通过将新闻建模为树状传播图，其中根节点表示新闻片段，子节点表示与根新闻互动的用户。他们的端到端框架：UPFD 通过文本嵌入模型（例如word2vec、BERT）和用户参与嵌入过程分别提取了新闻片段和用户的两个嵌入。对于每个新闻图，其潜在表示是这两个嵌入的扁平串联，这是用于训练具有新闻标签的神经分类器的输入，由训练模型标记为伪造的相应传播图被视为异常。
赵和Akoglu的另一个代表性工作[142]采用了 GIN 模型和一类分类（即DeepSVDD [143]）损失，以端到端的方式训练了一个图级别的异常检测框架。对于图数据库中的每个个体图形，其图级别嵌入是通过对其节点的节点级嵌入进行均值池化生成的。如图 9 所示，如果一个图形位于学习到的高维球外部，最终被描述为异常。
8.2 基于网络表示的技术
还可以将一般的图级网络表示技术应用于ANOS GD。通过这些方法，检测问题被转化为嵌入空间中的传统异常值检测问题。使用图级表示技术，如 Graph2Vec [144]、FGSD [145]，将数据库中的图编码为共享的潜在空间。然后，采用现成的异常值检测器来衡量每个单个图的异常性。然而，这两个阶段之间是分离的，因此检测性能可能不够理想，因为嵌入相似性不一定是为了异常检测而设计的。
9 动态图的异常图检测
对于动态图，图级别的异常检测致力于识别异常的图快照/时态图。与动态图上的 ANOS ND 和 ED 类似，给定一系列图，可以通过其异常的演变模式、异常的图级特征或其他特征来区分异常的图。
为了获取每个图快照/时态图的特征，通常可以应用常用的GNN、LSTM和自编码器。Teng等人[147]应用了一个LSTM自编码器来检测异常的图快照，如图10所示。在他们提出的模型DeepSphere中，动态图被描述为三阶张量的集合，，其中每个 是沿着时间维度的切片是图快照的邻接矩阵。
为了识别异常张量，DeepSphere 首先使用LSTM自编码器将每个图快照嵌入到潜在空间中，然后利用一个单类分类目标 [143] 来学习一个超球，使得正常的快照被覆盖，异常的快照位于外部。LSTM 自编码器按顺序将邻接矩阵作为输入，并试图通过训练重构这些输入矩阵。
（提了一嘴恶意的对抗性攻击）
异常边、子图和图检测技术总结
10 已发表的算法和数据集
列出了具有公开可用实现的已发表算法，然后提供了一组公共基准数据集，并总结了常用的评估指标。最后，由于真实世界数据集中标记异常的数量有限，我们回顾了现有研究中使用的三种合成数据集生成策略。
10.1 公开的算法
已发表的算法和模型实现对基线实验起到了贡献作用。表格4提供了已发表实现的摘要，包括所使用的编程语言和平台、能够处理的图形类型，以及代码存储库的URL链接。
10.2 公开的数据集
表格5总结了最常用的数据集，只有Enron、Twitter Sybil、Disney、Amazon、Elliptic和Yelp数据集提供了标记的异常。在大多数现有研究中，会通过在正常数据集中注入异常来生成合成数据集，异常的数量因研究而异。
10.3 合成数据集生成
鉴于真实异常数据的稀缺性，许多研究人员采用合成数据集来探究他们提出的方法的有效性[83]，[171]，[172]。通常，这些数据集可以分类如下
- 注入异常的合成图表。根据真实世界网络创建图表。所有的节点和边缘都是手动添加的，并使用众所周知的基准数据集（例如，Lanchinetti-Fornunato-Radicchi（LFR）[173]，small-world[174]，scale-free graphs[175]）。一旦建立完成，现实真实的异常数据将被嵌入到网络中。为了生成预期规模的网络，先前的研究工作大多使用这一策略来验证其在异常检测中的基本直觉的可行性。
- 注入异常的真实世界数据集。这些数据集是基于真实世界的网络构建的。具体来说，异常是通过修改现有节点/边缘/子图的拓扑结构或属性，或者插入不存在的图形对象来创建的。
- 下采样的图分类数据集。广泛使用的图分类数据集（例如[142]中的NCI1、IMDB、ENZYMES等）可以通过两个步骤轻松转化为适用于异常检测的数据集。首先，选择一个特定的类别及其数据记录来代表正常对象。然后，其他数据记录按照指定的下采样率进行下采样，作为异常数据。通过这样的方式，生成的图异常检测数据集实际上是原始数据集的子集。这种策略的最大优势在于没有单个数据记录被修改。
10.4 评估标准
迄今为止，用于评估异常检测性能的最广泛使用的指标包括准确度、精确率、召回率、F1分数和AUC-AP（平均精度）。它们的公式/描述如表 6 所示。然而，需要更专业的分析以使用一些新的评估指标来进一步进行性能评估，因为异常检测对于不同应用有不同的要求[176]–[178]，例如假负和假正。例如，在入侵检测中对于假阳性不敏感，但是假阴性很严重。因此，在评估检测性能时，我们建议考虑应用领域的具体要求，以进行公平和合适的比较。
11 未来方向
到目前为止，我们已经审查了专注于图异常检测的当代深度学习技术。从我们的调查中可以明显观察到，由于异常检测的复杂性、图数据的复杂性以及深度学习技术在图数据挖掘方面的不成熟，仍然存在许多复杂的挑战。另一个观察是，深度学习技术在图异常检测中仍然局限于相对较少的研究，并且其中大多数集中在异常节点检测上。只需比较一下表 2 和表 3 的长度，就可以衡量一下。边、子图和图级别的异常检测明显受到了较少的关注。为了弥合这些差距并推动未来的工作，我们已经确定了图异常检测与深度学习的 12 个未来研究方向。
11.1 异常边、子图和图的检测
现有的异常边/子图/图检测技术与各种应用领域（例如社交网络、计算机网络、金融网络）中更高级解决方案的新需求之间存在巨大差距。在检测异常边/子图/图时，所提出的方法应能够利用图中包含的丰富信息，以找到可以区分特定应用中正常对象和异常的线索和特征。通常，这涉及提取边/子图/图级别的特征，建模这些特征的模式，并相应地衡量异常。然而，目前基于深度学习的图异常检测技术在这方面几乎没有付出太多努力。
机遇：首先考虑应用领域，探索领域知识，找到作为这些问题基础的互补线索。然后，受到最近在边、子图和图级别表示学习方面的深度学习进展的启发，可以进行大量工作，以学习一种能够提取异常模式的异常感知嵌入空间。
11.2 动态图中的异常检测
动态图可以捕捉实际对象及其属性之间不断演变的关系。这引发了任务的两个主要关切点。第一是考虑不同时间戳下每个图快照中包含的空间和时间信息，第二是探索节点、边、子图和图的演变模式，以及它们与节点/边属性随时间的互动。
机遇：根据我们的观察，大多数基于深度学习的动态图异常检测技术是基于 DeepWalk [79]、GCN [92]或其他直观设计用于静态图的深度模型构建的。这意味着其他信息，比如属性中的演变模式 [180]，[181]，在检测任务中没有充分利用。因此，我们可以确定未来研究的以下方向目标：
- 利用动态图挖掘工具。作为一个热门研究课题，深度学习用于动态图数据挖掘 [182]，[183] 已经显示出在支持动态图分析，如节点聚类和图分类 [60] 方面的有效性。可以预见未来将有更多的研究采用这些技术来进行异常检测。
- 获取异常检测的可靠证据。动态图中丰富的结构、属性和时间信息是识别异常的宝贵资源。除了目前广泛使用的指标，如节点对之间的连接突增或连接突然消失，我们建议深入探索结构和属性的变化。通过这些研究，我们可以得出额外的信息，以增强检测性能，比如异常属性的出现。
- 处理复杂的动态性。现实世界中的网络始终表现出网络结构和节点属性的变化，但只有极少数研究考虑了这种情况。大多数最新技术只考虑这些方面的变化中的一个。尽管这种“双重”情景非常复杂，检测这种类型的动态图中的异常非常具有挑战性，但值得研究，因为这些图高度反映了真实网络数据。
11.3 异构图中的异常检测
异构图是一种特殊类型的图，包含各种类型的节点和边。比如可以直观地将 Twitter 建模为一个由推文、用户、单词等构成的异构图。
机遇：利用异构图中不同类型节点之间的复杂关系进行异常检测，代表性的工作，如HGATRD [157]、GCAN [156] 和GLAN [158]，通常根据元路径（例如，包含推文和用户的路径以及包含推文和单词的路径）将异构图分解为各自的图。然后，它们使用D(G)NNs来学习用于图异常检测的嵌入。这种分解固有地忽视了不同类型节点/边之间的直接相互关系，并降低了嵌入的有效性。一个可能的解决方案是揭示不同类型节点和边之间的复杂关系，并将它们编码成一个独特的表示，以提高检测性能。
11.4 大规模图中的异常检测
在处理高维度和大规模数据时的方法可扩展性是异常检测技术面临的持续和重要挑战。面对像Facebook 和 Twitter 这样包含数十亿用户和友情链接的大规模网络，无论是在图的规模还是节点属性的数量方面，数据规模都非常庞大。然而，大多数现有工作缺乏在这种大规模数据中检测异常的能力，因为它们是转导模型，需要将整个图作为输入进行进一步分析。随着网络规模的增大，计算时间和内存成本急剧增加，这阻止了现有技术在大规模网络上的应用。
机遇：因此，需要可扩展的图异常检测技术。一个可能的方法是采用归纳学习方案，首先在整个图的一部分上训练检测模型，然后将该模型应用于检测未见数据中的异常。正如一些归纳学习模型，如GraphSAGE [184]，已经在大规模图上的链接预测和节点分类中显示出了其有效性，这种方法有望为大规模图中的图异常检测提供基础，并可以在未来进一步研究类似的技术。
11.5 多视图图异常检测
在现实世界的网络中，对象可能与其他对象形成不同类型的关系（例如，Twitter上的用户的关注和友谊关系）。他们的属性信息可能来自不同的资源，比如用户的个人资料、历史帖子等。这导致了两种类型的多视图图形：
- 多图（包含多个图形结构的数据集或对象。），其中包含两个节点之间的多种类型边[185]，[186]
- 多属性视图图（包含多个视图的图形数据），它在不同的属性视图中存储节点属性[94]，[187]，[188]。
机遇：这些多视图基本上允许我们从不同的角度分析真实对象的特征。每个视图还为其他视图提供了互补的信息，它们可能在异常检测方面具有不同的重要性。在数据挖掘领域，已经有许多关于多视图学习的研究工作 [189]，[190]。当前针对多视图图和多视图属性的异常检测研究还比较有限，需要更多的研究来充分利用这些信息。另外，要解决不同视图之间的一致性和矛盾问题也是一个挑战。
11.6 伪装/对抗性异常检测
异常实体伪装成普通对象，如果检测技术对这种情况不够健壮，即它们不能迅速有效地适应寻求逃避攻击者的演化行为。
机遇：迄今为止，很少有研究关注如何处理图中的伪装异常[26]，[27]，[76]。一个主要方向可能是共同分析超图中对象之间的属性、相关性（如三元、四元或高阶关系）[192]–[195]以及图中包含的其他信息。通过这种方式，只伪装其局部结构或属性的异常可以被有效地识别。加强现有技术可能是另一个方向。
11.7 不平衡的图异常检测
异常很罕见，这意味着异常检测始终与训练数据中的类别不平衡共存。由于深度学习模型严重依赖训练数据，这种不平衡对图异常检测构成了巨大挑战，仍然是深度学习技术的一大障碍。通常，不平衡的类别分布会降低检测技术捕捉异常和非异常之间差异的能力。甚至可能因为数据中异常很少而导致对异常类别的过拟合。如果检测模型忽视了这一关键事实并且训练不当，检测性能将不达标。
机遇：实际上，类别不平衡已经在各个研究领域广泛探讨过[117]，[118]。但是在图异常检测很少包含这种技术，可以采用偏向于异常的模型，比如对错误分类的异常施加额外的训练损失，这可能是一个解决问题的方向。此外，当采用图神经网络来聚合与目标节点相邻的信息，应该防止连接节点特征之间的过度平滑化，以便保留异常的可区分特征，以支持异常检测。
11.8 多任务异常检测
图异常检测与其他图挖掘任务密切相关，包括社群检测[58]、节点分类[196]和链接预测[197]。异常检测与其他任务之间的这种相互有益的协作本质上提供了多任务学习的机会，可以同时处理多种任务并在任务之间共享信息。
机遇：多任务学习提供了有效的机制，可以整合相关任务[198]，[199]。不同任务可以提供互补信息，增强检测性能。超越当前的工作，比如[100]，它共同执行异常节点检测和个性化推荐，探索将其他学习任务与图异常检测相结合的可能性很可能成为一个富有前景的未来方向。
11.9 图异常解释性
异常检测技术的可解释性对后续的异常处理过程至关重要。例如金融和保险系统需要提供可解释和合法的证据。最常用的指标是前k名排名和简单的异常评分函数，可以将对象标记为异常或非异常，但不能提供坚实的解释。深度学习技术也因其可解释性较低而受到批评，因此未来关于深度学习的图异常检测工作应更加关注这一点[200]。
机遇：为了弥补这一差距，将专门设计的解释算法或机制[201] [202]集成到检测框架中可能是一种可能的解决方案，需要注意的是这将固有地增加更高的计算成本。因此，未来的工作应该平衡异常检测性能和可解释性的成本。基于可视化的方法，例如仪表板和图表，也可能以用户友好的方式显示异常和非异常之间的区别。如果能够提供可解释的可视化结果，这个方向的进一步研究将会取得成功[203]。
11.10 图异常识别策略
在现有的无监督图异常检测技术中，主要基于以下策略来识别异常：残差分析[41]，[107]，重构损失[110]，基于距离的统计[84]，基于密度的统计[98]，图扫描统计[204][207]和单类别分类[115]。这些识别策略的基本思想是，异常具有与常规对象不一致的数据模式。目前，针对用于图神经网络的异常检测的新型损失函数的设计工作相对有限[67]。
机遇：尽管这些策略能够捕捉异常的偏离数据模式，但它们也存在不同的局限性。具体而言
- 残差分析、单类别分类和重构损失策略对嘈杂的训练数据敏感。嘈杂的节点、边或子图也会表现出较大的残差、距离原点/超球中心的距离较大和较高的重构损失。
- 基于距离和基于密度的策略只能在较低维度空间中异常和非异常之间明显分离时应用。
这需要未来广泛的努力来克服这些局限性，并探索新的异常识别策略。
11.11 系统性基准测试
系统性基准测试是评估图异常检测技术性能的关键。严格设计更好的基准测试框架将有助于揭示各种检测技术的优点和缺点，从而跟踪这一领域的公正和准确的进展记录。
11.12 统一异常检测框架
可能有不同的方式来定义某种类型的异常，比如社群的离群值与异常社群，或者基于属性的与结构的异常。在将检测技术部署到实际应用程序中时，期望能够在消耗最少的资源和时间的情况下识别所有类型的异常。一个直接的方法是集成独立的异常节点、边和子图检测技术。
机遇：能够同时检测各种类型异常的统一框架[208] [209]可能为弥合差距提供可行的解决方案。构建这种框架需要各种领域知识和不同检测技术。
12 结论
由于现实世界对象之间复杂的关系以及深度学习，尤其是图神经网络的最新进展，使用深度学习进行图异常检测目前处于异常检测的前沿。据我们所知，这是第一次专门介绍了现代深度学习技术在图异常检测领域的综合回顾。具体而言，我们根据它们可以检测的图异常类型，对当代深度学习技术进行了回顾和分类，包括：（1）异常节点检测；（2）异常边检测；（3）异常子图检测；最后，（4）异常图检测。我们提供了对不同研究的清晰总结和比较，以提供关于图异常检测领域的当前工作和进展的完整和详尽的画面。
此外，为推动这一领域的未来研究，我们已经提供了一个系统基础，通过汇编广泛使用的数据集、开源实现和合成数据集生成技术，为系统性基准测试提供了基础。基于调查结果，我们进一步提出了12个未来工作的潜在方向。我们坚信，使用深度学习进行图异常检测确实不仅仅是暂时兴趣的爆发，未来多个不同领域的应用都将从中受益，这是毫无疑问的。
- 作者:Braindance
- 链接:null/article/202308270
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章
A survey on graph neural networks for intrusion detection systems: Methods, trends and challenges
TS-IDS: Traffic-aware self-supervised learning for IoT Network Intrusion Detection
Anomaly traffic detection in IoT security using graph neural networks
AddGraph: Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN
安全问题统计
Anomaly Detection in Dynamic Graphs via Transformer