Detecting Anomalies in Dynamic Graphs via Memory enhanced Normality

📄 arXiv: 2403.09039v2 📥 PDF

作者: Jie Liu, Xuequn Shang, Xiaolin Han, Kai Zheng, Hongzhi Yin

分类: cs.LG, cs.AI

发布日期: 2024-03-14 (更新: 2024-08-15)

💡 一句话要点

提出STRIPE以解决动态图异常检测问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱五：交互与反应 (Interaction & Reaction)

关键词: 动态图 异常检测 图神经网络 记忆网络 无监督学习 空间时间特征 重构误差 互注意力机制

📋 核心要点

  1. 现有动态图异常检测方法依赖正常数据捕捉模式，难以直接识别正常性，且忽视空间与时间的区别。
  2. 本文提出STRIPE，通过图神经网络和门控时间卷积层提取特征，并利用记忆网络存储正常模式原型。
  3. 在六个基准数据集上，STRIPE的AUC得分提高5.8%，训练时间加快4.62倍，显示出显著的效果和效率。

📝 摘要（中文）

动态图中的异常检测因图结构和属性的时间演变而面临重大挑战。传统方法通常采用无监督学习框架，仅依赖正常数据捕捉正常模式，测试时识别偏差为异常。然而，这些方法存在关键缺陷：要么仅依赖代理任务进行表示而未直接识别正常模式，要么忽视空间和时间正常性模式的区分。为了解决这些挑战，本文提出了一种新颖的空间-时间记忆增强图自编码器（STRIPE）。STRIPE利用图神经网络和门控时间卷积层提取空间和时间特征，并结合独立的空间和时间记忆网络捕捉和存储正常模式的原型。实验结果表明，STRIPE在六个基准数据集上显著优于现有方法，AUC得分提高5.8%，训练时间加快4.62倍。

🔬 方法详解

问题定义：本文旨在解决动态图中的异常检测问题，现有方法往往依赖正常数据进行训练，无法有效识别正常模式，且忽视了空间和时间特征的差异性。

核心思路：STRIPE通过引入空间和时间记忆网络，分别捕捉和存储正常模式的原型，并通过互注意力机制将这些模式与图嵌入结合，从而提高异常检测的准确性。

技术框架：STRIPE的整体架构包括三个主要模块：首先，利用图神经网络和门控时间卷积层提取空间和时间特征；其次，采用独立的空间和时间记忆网络存储正常模式；最后，通过解码器重构图流，作为异常检测的代理任务。

关键创新：STRIPE的主要创新在于引入了空间-时间记忆网络，能够有效捕捉和存储正常模式的原型，解决了现有方法对正常模式识别的不足。

关键设计：在网络结构上，STRIPE结合了图神经网络和门控时间卷积层，损失函数设计上强调重构误差的最小化，同时确保嵌入的紧凑性和独特性。具体参数设置和网络结构细节在实验部分进行了详细说明。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在六个基准数据集上的实验结果显示，STRIPE在AUC得分上提高了5.8%，并且训练时间比现有方法快了4.62倍，展现了其在异常检测任务中的优越性能。

🎯 应用场景

该研究在网络安全、社交网络分析和交通流量监测等领域具有广泛的应用潜力。通过准确检测动态图中的异常行为，能够有效提升系统的安全性和可靠性，具有重要的实际价值和未来影响。

📄 摘要（原文）

Anomaly detection in dynamic graphs presents a significant challenge due to the temporal evolution of graph structures and attributes. The conventional approaches that tackle this problem typically employ an unsupervised learning framework, capturing normality patterns with exclusive normal data during training and identifying deviations as anomalies during testing. However, these methods face critical drawbacks: they either only depend on proxy tasks for representation without directly pinpointing normal patterns, or they neglect to differentiate between spatial and temporal normality patterns. More recent methods that use contrastive learning with negative sampling also face high computational costs, limiting their scalability to large graphs. To address these challenges, we introduce a novel Spatial-Temporal memories-enhanced graph autoencoder (STRIPE). Initially, STRIPE employs Graph Neural Networks (GNNs) and gated temporal convolution layers to extract spatial and temporal features. Then STRIPE incorporates separate spatial and temporal memory networks to capture and store prototypes of normal patterns, respectively. These stored patterns are retrieved and integrated with encoded graph embeddings through a mutual attention mechanism. Finally, the integrated features are fed into the decoder to reconstruct the graph streams which serve as the proxy task for anomaly detection. This comprehensive approach not only minimizes reconstruction errors but also emphasizes the compactness and distinctiveness of the embeddings w.r.t. the nearest memory prototypes. Extensive experiments on six benchmark datasets demonstrate the effectiveness and efficiency of STRIPE, where STRIPE significantly outperforms existing methods with 5.8% improvement in AUC scores and 4.62X faster in training time.