摘要

给定一个动态图，如何通过节点嵌入有效地跟踪异常子图是一个重要的挑战。解决这一问题需要一个有效的评分机制和创新的异常子图检测策略。然而，现有方法主要集中于设计评分策略或使用孤立节点的图结构，这导致无法有效捕捉异常子图的结构信息。

在本文中，我们提出了一种名为 SUBANOM 的新型子图异常检测框架，该框架能够高效识别异常子图。SUBANOM 包括三个关键组件：

1）我们采用当前最先进的动态嵌入方法，高效计算节点嵌入，从而成功捕捉所有节点级别的异常；

2）我们设计了新的子图识别策略，包括 k-hop 和 三元闭包（triadic-closure），这些策略可以区分强邻居和弱邻居，从而有效捕捉异常结构信息；

3）为了量化异常子图，我们提出了基于 p-范数 的评分聚合函数。

这些迭代步骤使我们能够高效处理大规模动态图。

引言

在动态图中识别异常子图是一项至关重要的任务，具有广泛的应用场景，例如在社交网络中检测事件、在金融网络中识别异常用户群体，以及在用户-项目图中发现异常的评论者集群等。这类任务的核心在于有效地检测出随着时间变化而发生的图结构变化，尤其是局部子图中显著的异常行为。

现有的子图异常检测方法主要可以分为两类：基于结构的方法和基于表示学习的方法。

基于结构的方法通常依赖用户指定的评分函数，通过复杂的优化算法对目标函数进行求解。然而，这类方法不仅计算成本高，在动态环境下也难以适用，因为动态图通常包含成千上万个快照，每个快照中又包含大量节点和边。

随着动态图表示学习技术的快速发展，基于表示学习的方法逐渐成为主流。这些方法通过节点嵌入来高效捕捉节点的异常信息，证明了在跟踪动态图中的异常节点方面具有较高的效率。然而，现有的基于表示学习的方法通常仅关注单个节点的异常检测，而忽略了局部子图的结构信息，从而无法识别隐藏的重要异常模式。

针对上述问题，本文提出了一个新颖的异常子图检测框架 SUBANOM，该框架基于动态节点嵌入，并通过创新的子图识别策略来有效捕捉局部异常子图结构。我们的研究旨在回答以下关键问题：如何基于动态节点嵌入有效地检测出子图级别的异常结构信息？

我们提出的 SUBANOM 框架包含三个关键组件：

实验结果表明，与当前最先进的子图异常检测方法相比，SUBANOM 在多个真实世界的数据集上均取得了显著的性能提升。我们的方法不仅提高了检测精度，还在处理大规模动态图方面表现出较高的计算效率。