图异常检测（GAD）与基于深度学习的图异常检测（GADL）综述。

X. Ma et al., “A Comprehensive Survey on Graph Anomaly Detection With Deep Learning,” IEEE Trans. Knowl. Data Eng., vol. 35, no. 12, pp. 12012–12038, Dec. 2023, doi: 10.1109/TKDE.2021.3118815.
https://ieeexplore.ieee.org/document/9565320/

【摘要】异常是样本中偏离其他观测值的罕见观察值（例如数据记录或事件）。过去几十年，异常挖掘研究因其广泛的应用领域（例如安全、金融和医学）而受到越来越多的关注。因此，异常检测，即识别这些罕见观察值，已成为世界上最重要的任务之一，并在防止有害事件（如财务欺诈、网络入侵和社会垃圾信息）方面展现出其威力。传统的异常检测技术通常通过识别特征空间中的异常数据点来解决检测任务，这本质上是忽略了现实世界数据中的关系信息。同时，图已被广泛用于表示结构/关系信息，这引发了图异常检测问题——在一个图中识别异常图对象（即节点、边和子图），或在图集/数据库中识别异常图。由于图数据的复杂性（例如，不规则结构、关系依赖性、节点/边类型/属性/方向/多重性/权重、大规模等），传统的异常检测技术无法很好地解决此问题。然而，得益于深度学习在突破这些限制方面的出现，基于深度学习的图异常检测近年来受到了越来越多的关注。在本调查中，我们旨在提供对当代基于深度学习的图异常检测技术的系统性和全面回顾。具体来说，我们提供了一个任务驱动策略的分类法，并根据现有工作可以检测的异常图对象对它们进行分类。我们特别关注该研究领域的挑战，并讨论了每个类别中各种技术的关键直觉、技术细节以及相对优缺点。从调查结果中，我们强调了12个未来的研究方向，涵盖图数据、异常检测、深度学习和现实应用中引入的未解决和新兴问题。此外，为了为未来的研究提供大量有用的资源，我们还整理了一套开源实现、公共数据集和常用评估指标。通过这次调查，我们的目标是创建一个“一站式”商店，为图异常检测使用深度学习的问题类别和现有方法、公开可用的动手资源和具有高影响力的开放挑战提供统一的了解。

【关键词】异常检测，异常值检测，欺诈检测，谣言检测，假新闻检测，垃圾信息检测，虚假信息，图异常检测，深度学习，图嵌入，图表示，图神经网络

1 异常检测与图异常检测

异常检测的目标是识别数据集中偏离主流模式的罕见观察值。传统的异常检测方法通常将现实世界对象表示为特征向量，并在特征空间中检测异常数据点。然而，这种方法忽略了数据对象之间的复杂关系，这在现实世界中非常重要。_{(P1, P2)}

图作为一种强大的工具，可以有效地表示对象之间的结构信息。图异常检测（GAD）旨在识别单个图或图集中异常的图对象（节点、边或子图）。由于图数据的复杂性，传统的异常检测技术无法有效地解决GAD问题。_{(P1, P2)}

2 基于深度学习的图异常检测（GADL）

GADL利用深度学习技术，如图嵌入和图神经网络（GNNs），来提取图数据中的丰富信息，从而更准确地识别异常。GADL技术面临着数据特定挑战和技术特定挑战：

• 数据特定挑战（Data-CHs）：图数据的复杂性，例如不规则结构、关系依赖性、大规模等。_(P2)
• 技术特定挑战（Tech-CHs）：设计异常感知训练目标、异常可解释性、高训练成本和超参数调整等。_(P3)

3 GADL技术的分类

根据GADL技术可以检测的异常图对象类型，可以将它们分为以下几类：

• 异常节点检测（ANOS ND）：识别单个节点，例如网络入侵者、欺诈用户或假新闻。_(P2)
• 异常边检测（ANOS ED）：识别异常链接，例如网络入侵者和良性用户之间的交互。_(P11)
• 异常子图检测（ANOS SGD）：识别异常子图，例如网络中的欺诈用户群体。_(P13)
• 异常图检测（ANOS GD）：识别整个图或图集中异常的图，例如异常的分子或脑部疾病。_{(P14, P15)}

4 GADL技术的详细解读

4.1 ANOS ND

• 传统方法：使用统计特征，例如度数或权重，来检测异常节点。_(P7)
• 基于网络表示的方法：将图结构编码到嵌入空间中，并通过分析节点在嵌入空间中的位置来检测异常节点。_(P7)
• 基于强化学习的方法：将异常节点检测视为一个决策问题，并使用强化学习来学习识别异常节点的策略。_{(P7, P8)}

4.2 ANOS ED

• 基于深度神经网络（DNN）的方法：使用自编码器或全连接网络来学习节点表示，并通过分析节点的重构误差来检测异常边。_{(P11, P12)}
• 基于图卷积网络（GCN）的方法：使用GCN来捕获图结构信息，并通过分析节点的重构误差或嵌入分布来检测异常边。_(P12)
• 基于网络表示的方法：直接学习边的表示，并通过分析边的重构误差或嵌入分布来检测异常边。_(P12)

4.3 ANOS SGD

• 基于深度网络表示的方法：使用自编码器或GCN来学习用户和物品的表示，并通过分析用户之间的相似性或DBSCAN算法来检测异常子图。_(P14)

4.4 ANOS GD

• 基于图神经网络（GNN）的方法：使用GNN来对单个图进行分类，并根据其是否在超球面之外来判断其是否异常。_(P15)
• 基于网络表示的方法：使用图级网络表示技术将图编码到嵌入空间中，并使用单类分类器来检测异常图。_(P15)

5 未来研究方向

基于本次调查结果，我们提出了12个GADL的未来研究方向：_(P19~P22)

• 异常边、子图和图检测
• 动态图异常检测
• 异常检测在异构图上
• 大规模图异常检测
• 多视图图异常检测
• 隐藏/对抗性异常检测
• 不平衡图异常检测
• 多任务异常检测
• 图异常可解释性
• 图异常识别策略
• 系统性基准测试
• 统一异常检测框架

6 结论

GADL技术在图异常检测领域取得了显著的进展，并展现出巨大的潜力。未来，随着图数据、异常检测和深度学习技术的不断发展，GADL技术将迎来更多的机遇和挑战，并为各个领域的应用带来更大的价值。