轻松进行动态图异常检测，南洋理工提出GeneralDyG

OpenCV学堂 2025-01-05 20:54

如何提升高压系统的实时性能? 【有奖直播】精密半导体参数测试解决方案

点击上方↑↑↑“OpenCV学堂”关注我

来源：公众号机器之心授权

此项研究成果已被 AAAI 2025 录用。该论文的第一作者是南洋理工大学计算与数据科学学院 (CCDS) 的硕士生杨潇，师从苗春燕教授，主要研究方向是图神经网络。该论文的通讯作者为南洋理工大学百合研究中心的瓦伦堡 - 南洋理工大学校长博士后研究员赵雪娇；申志奇，南洋理工大学计算与数据科学学院高级讲师，高级研究员。

论文标题：A Generalizable Anomaly Detection Method in Dynamic Graphs
论文链接：https://arxiv.org/abs/2412.16447
代码：https://github.com/YXNTU/GeneralDyG

研究背景与问题描述

随着动态图数据的广泛应用，它在社交网络、电商和网络安全等领域展现了强大的建模能力。然而，与静态图相比，动态图因节点和边的动态演变特性，给数据分析带来了更大的挑战，尤其是在异常检测方面。异常检测是保障系统安全和数据完整性的关键任务，旨在识别显著偏离正常模式的异常事件，例如欺诈交易、社交媒体垃圾信息和网络入侵等。及时发现这些异常对系统的可靠性和安全性至关重要。

基于深度学习的动态图异常检测方法已取得一定进展，例如利用图神经网络提取结构信息或通过时序模型捕获时间依赖性。然而，这些方法在通用性方面仍存在显著不足。具体而言，它们通常难以适应不同的数据集和任务场景，难以高效捕获动态图中局部与全局的复杂特征。此外，一些方法在处理大规模动态图时计算成本较高，异常事件的编码也不够准确，导致在新场景中的检测性能显著下降。

方法设计

本文针对动态图异常检测中的数据分布多样、动态特征捕捉困难以及计算成本高三大挑战，提出了一种通用方法（GeneralDyg）。首先，为应对数据分布多样问题，我们提取节点、边及其拓扑结构的关键信息，从而适应不同数据集的复杂特征分布。其次，为解决动态特征捕捉的难题，我们结合全局时间动态和局部结构变化，深入建模动态图中的多尺度动态模式。最后，为降低计算成本，我们构建了一种轻量化框架，能够高效捕获关键动态特征，同时显著提升计算效率。

如图 1 所示，本文方法由三部分组成，每部分针对上述挑战提供了解决方案：

（a）时间 ego-graph 采样模块，通过构建紧凑的子图结构有效应对计算资源限制；（b）图神经网络提取模块，全面捕获动态图的节点与边的多样性和复杂结构；（c）时间感知 Transformer 模块，有效融合全局和局部动态特征。

图 1 ：动态图异常检测框架 GeneralDyG 的整体架构

（a）时间 ego-graph 采样模块旨在通过构建紧凑的子图结构有效缓解动态图大规模数据带来的计算压力。具体来说，该模块基于中心事件，通过 k-hop 算法提取其周围交互历史，构成时间 ego-graph。k-hop 算法的设计考虑了事件间的时间顺序与拓扑关系，确保采样过程兼顾时间动态与结构特性。此外，为了捕捉事件之间的层级关系，该模块引入了特殊标记（如层级标记符号）来分隔不同层次的交互信息。这些标记能够帮助 Transformer 模块更好地识别与学习时间序列中的层级动态。此外，该模块还通过限制 k 的范围来控制采样的规模，从而在信息完整性与计算效率之间取得平衡。这样的设计在保留动态结构信息的同时，显著降低了计算复杂度。

（b）在时间 ego-graph 的基础上，本文设计了一种新的图神经网络（TensGNN）来提取丰富的结构信息。TensGNN 通过交替应用节点层和边层来实现特征信息的传播与更新，从而在节点特征和边特征之间构建强关联。具体而言，节点层利用节点的邻接矩阵和特定拉普拉斯矩阵进行卷积运算，同时结合边的特征更新节点表示。相应地，边层则基于边的邻接关系和节点的状态更新边的特征表示。这种交替堆叠的方式能够更好地捕捉动态图中的局部与全局特性。此外，该模块引入了轻量化的算子，避免了冗余计算，在大规模数据集上也能保持较高的计算效率。

（c）时间感知 Transformer 模块：最后，GeneralDyG 通过时间感知 Transformer 模块整合时间序列和结构特征。在自注意力机制中，模型分别利用 Query 和 Key 编码图的拓扑结构信息，而将 Value 保留为原始事件特征，以确保异常检测的准确性。通过这一模块，模型能够有效捕获动态图中全局的时间依赖性和局部的动态变化，从而实现对复杂异常模式的准确建模。

实验验证

本文在节点级别（node level）和边级别（edge level）两个层面上进行了实验评估，使用了四个真实数据集：SWaT 和 WADI 用于节点级别异常检测，Bitcoin-Alpha 和 Bitcoin-OTC 用于边级别异常检测。

我们将 GeneralDyG 与 20 种主流基线方法进行对比，这些基线方法涵盖了图嵌入（如 node2vec、DeepWalk）和异常检测（如 TADDY、SAD、GDN）两大类别。实验通过 AUC、AP 和 F1 等指标全面评估模型性能，并在不同异常比例（1%、5%、10%）下进行了系统性测试。结果表明，GeneralDyG 在所有数据集上均显著优于现有方法，展现了卓越的通用性与检测能力，如图 2 所示。