建模时空图异常检测中的频谱能量偏移

# 建模时空图异常检测中的谱能量偏移
来源：https://arxiv.org/html/2606.00304
###### 摘要

图异常检测方法旨在区分异常节点。虽然现有方法通过谱能量分布中增加的变异性来表征异常，但它们忽略了那些导致变异性降低的异常，即伪装成正常节点的隐蔽异常。我们表明，这种类型的异常在多个数据集中持续存在，并且现有谱方法无法检测。为了解决这一局限性，我们提出了一种节点级谱能量公式，该公式与消息传递完全兼容，并能检测隐蔽异常。基于此公式，我们引入了一个能量感知图学习框架，通过能量驱动的消息传递在静态图和时间序列图中建模谱偏移。此外，我们的统一架构无需引入专门的序列模块即可扩展到时间设置，从而在长滑动窗口下实现高效学习。在大规模基准上的大量实验证明了我们方法的有效性和可扩展性。我们的代码见 https://github.com/AICPS-Lab/Spectral-Energy-Shifts-in-GAD。

机器学习，ICML

## 1 引言

网络系统支撑着关键应用领域，包括金融交易网络 (Ma et al., 2021 (https://arxiv.org/html/2606.00304#bib.bib3))、电子商务平台、社交图 (Hooi et al., 2016 (https://arxiv.org/html/2606.00304#bib.bib23)) 和信息物理基础设施 (Deng and Hooi, 2021 (https://arxiv.org/html/2606.00304#bib.bib5))。在这些应用中，诸如欺诈交易、虚假评论和恶意账户等异常并非孤立发生，而是通过连接性传播，放大其影响，并导致重大经济损失和系统故障 (Liu et al., 2021 (https://arxiv.org/html/2606.00304#bib.bib4); Deng and Hooi, 2021 (https://arxiv.org/html/2606.00304#bib.bib5))。因此，在图结构数据中检测此类异常（称为图异常检测，GAD）至关重要，但仍然是一个未解决的问题 (Liu et al., 2022 (https://arxiv.org/html/2606.00304#bib.bib39))。

在 GAD 中，现有方法大致可分为两个方向：空间方法和谱方法 (Tang et al., 2023 (https://arxiv.org/html/2606.00304#bib.bib41))。空间方法旨在增强图表示学习，包括各种方法 (Li et al., 2019 (https://arxiv.org/html/2606.00304#bib.bib42); Dou et al., 2020 (https://arxiv.org/html/2606.00304#bib.bib24))。另一方面，谱方法通过设计不同的图滤波器（如 AMNet (Chai et al., 2022 (https://arxiv.org/html/2606.00304#bib.bib8))）来在频域中捕获异常模式。在这些工作中，Tang et al., 2022 (https://arxiv.org/html/2606.00304#bib.bib9) 提出的谱公式用高变异趋势（即“右移”现象）来表征节点属性异常。该公式显示出学习异常行为的潜力，并启发了后续研究 (Lin et al., 2024 (https://arxiv.org/html/2606.00304#bib.bib10); Duan et al., 2023 (https://arxiv.org/html/2606.00304#bib.bib12))。

然而，该谱公式存在两个关键局限性：范围有限和可扩展性差。该公式侧重于“右移”，即能量分布中呈现高方差的异常，而忽略了隐蔽异常 (Gao et al., 2023 (https://arxiv.org/html/2606.00304#bib.bib11))。这些异常通过模仿良性节点行为嵌入到图中，导致与正常节点高度相似，且与大多数分布的偏差很小 (Dou et al., 2020 (https://arxiv.org/html/2606.00304#bib.bib24))。此类异常存在于公开基准数据集中，但现有的基于能量的公式无法有效检测。在我们对 YelpChi (Rayana and Akoglu, 2015 (https://arxiv.org/html/2606.00304#bib.bib13)) 数据集的观察中（图1 (https://arxiv.org/html/2606.00304#S2.F1)），异常并非一致地遵循右移模式。在 32 个特征中，异常节点在 26 个特征上表现出比正常节点更低的谱能量。这一结果表明，这些异常并未显著偏离正常节点，因而被谱方法所忽视。此外，图级谱能量计算成本高昂，限制了在大规模图上的可扩展性。为了解决这些挑战，我们提出了能量图神经网络 (EGNN)，一种节点级谱 GAD 方法。EGNN 通过 i) 使用瑞利商量化隐蔽异常，以及 ii) 利用观察到的“左移”现象来描述异常引起的低变异趋势，从而将谱公式的范围扩展至包含隐蔽异常。为了提高可扩展性，我们提出了一种局部能量代理来近似图能量。

虽然静态检测依赖于单一快照的谱足迹，但时序检测依赖于能量分布的轨迹。谱公式天然关注能量分布的变化，使其成为时序设置中的一种有前景的表示。在时间序列 GAD 中，各种方法涵盖了无监督和半监督范式，范围从线性模型到深度学习方法 (Tuli et al., 2022 (https://arxiv.org/html/2606.00304#bib.bib14); Ruff et al., 2018 (https://arxiv.org/html/2606.00304#bib.bib16); Xu et al., 2021 (https://arxiv.org/html/2606.00304#bib.bib17); Wu et al., 2022 (https://arxiv.org/html/2606.00304#bib.bib18))。大多数现有方法通过在静态图骨干上堆叠时序模块来解耦空间和时间建模 (Pareja et al., 2020 (https://arxiv.org/html/2606.00304#bib.bib21))。这类框架具有大量可学习参数，并且在标签稀缺和高度不平衡的设置下数据效率低下。此外，它们对滑动窗口的依赖使得性能对窗口长度敏感 (Huang et al., 2023 (https://arxiv.org/html/2606.00304#bib.bib20); Ma et al., 2024 (https://arxiv.org/html/2606.00304#bib.bib19))，并导致优化不稳定 (Pascanu et al., 2013 (https://arxiv.org/html/2606.00304#bib.bib22))（例如，梯度消失或爆炸）。对于时序图，EGNN 避免引入额外的时序模块；相反，它通过滑动窗口内的能量变换和自适应门控来建模时间依赖，从而产生一种数据效率高且对窗口大小不敏感的设计。我们的贡献总结如下。

- • 我们揭示了一种先前被忽视的、在多个公共数据集中出现的隐蔽异常模式，并用谱公式对其进行表征。
- • 我们提出了 EGNN，一种基于节点级谱能量的 GAD 方法。它将谱公式的范围扩展至包含隐蔽异常，并通过 GNN 实现能量驱动的消息传递。我们进一步通过使用局部能量代理来近似图能量，缓解了可扩展性问题。
- • 我们将 EGNN 推广到时间序列图，利用局部谱代理来表征随时间的变化以及滑动窗口内的自适应门控。EGNN 产生了一个轻量级、数据高效的模型，即使在标签稀缺和高度不平衡的监督下，也能以数量级更少的参数超越最先进的方法。
- • 我们对包含静态图和时序图的 7 个基准进行了全面评估，与 14 个基线（包括最先进的方法）进行了比较。EGNN 持续表现优异，证明了其在各种设置下的有效性。

## 2 异常图的谱能量

本节介绍用于图异常检测的谱能量视角，并总结我们的关键观察。第 2.1 节 (https://arxiv.org/html/2606.00304#S2.SS1) 介绍 GAD 问题公式化，定义谱能量，并回顾相关的谱右移现象。第 2.2 节 (https://arxiv.org/html/2606.00304#S2.SS2) 识别出现实世界图中一种未被充分探索的异常模式，通过精确定义将其形式化，并在合成数据集上进行验证。第 2.3 节 (https://arxiv.org/html/2606.00304#S2.SS3) 进一步分析谱能量如何在子图级别显现，从而激发用于可扩展检测的局部化建模。

### 2.1 问题设置与谱能量

#### 图异常检测。

设 \( \mathcal{G} = (\mathcal{V}, \mathcal{E}) \) 表示一个无权图，其中 \( \mathcal{V} = \{ v_i \}_{i=1}^{N} \) 是 \( N \) 个节点的集合，\( \mathcal{E} \subseteq \mathcal{V} \times \mathcal{V} \) 是边集。每个节点 \( v_i \) 关联一个 \( d \) 维特征向量 \( x_i \in \mathcal{X} \subseteq \mathbb{R}^d \)，我们将特征集 \( \mathcal{X} \) 收集为 \( X = \{ x_i \}_{i=1}^{N} \)。令 \( \mathbf{x} := [x_1, ..., x_N]^\top \)，且 \( \mathbf{x}_f \in \mathbb{R}^N \) 表示索引为 \( f \) 的图特征列向量。本文中，我们关注 **节点级异常** 并假设图结构是可靠的，即所有边都不含异常。我们将异常节点集表示为 \( \mathcal{V}_a \subseteq \mathcal{V} \)，正常节点集表示为 \( \mathcal{V}_n \subseteq \mathcal{V} \)，其中 \( \mathcal{V}_a \cap \mathcal{V}_n = \emptyset \)。据此，我们将 GAD 公式化为一个二分类问题。给定图 \( \mathcal{G} \)、节点特征 \( \mathcal{X} \) 以及部分节点标签 \( \mathcal{V}_a \) 和 \( \mathcal{V}_n \)，目标是学习一个分类器，为每个未标记节点 \( v \in \mathcal{V} \) 分配标签。

参见图注 图 1：YelpChi 数据集中的谱能量分布。每个柱状图显示每个特征上正常节点与异常节点之间的平均谱能量差。蓝色表示异常节点能量较低，黄色表示异常节点能量较高。
#### 谱能量分布

设 \( A \in \mathbb{R}^{N \times N} \) 为图 \( \mathcal{G} \) 的邻接矩阵，\( D \in \mathbb{R}^{N \times N} \) 为相应的度矩阵，对角元 \( D_{ii} = d_i \)，其中 \( d_i = \sum_j A_{ij} \)。归一化拉普拉斯矩阵定义为 \( L = I - D^{-1/2} A D^{-1/2} \)，其中 \( I \) 是适当维度的单位矩阵。当底层图是无向的，即 \( \mathcal{E}_{ij} = \mathcal{E}_{ji} \) 时，拉普拉斯矩阵 \( L \) 是对称的，即 \( L = L^\top \)。这种对称性保证了 \( L \) 具有实特征值和一个标准正交特征基。设 \( L = U \Lambda U^\top \) 为 \( L \) 的特征分解，其中特征值满足 \( 0 = \lambda_1 \leq \cdots \leq \lambda_N \)，且 \( U = [u_1, u_2, ..., u_N] \) 是相应的标准正交特征向量。考虑特征索引 \( f \) 处的图属性 \( \mathbf{x}_f \)，其图傅里叶变换定义为 \( \hat{\mathbf{x}}_f = U^\top \mathbf{x}_f \)。那么频率 \( \lambda_k \) ( \( 1 \leq k \leq N \) ) 处的谱能量定义为 \( \frac{ \hat{\mathbf{x}}_{k,f}^2 }{ \sum_{i=1}^N \hat{\mathbf{x}}_{i,f}^2 } \)。

#### 右移现象

先前研究 (Tang et al., 2022 (https://arxiv.org/html/2606.00304#bib.bib9)) 已表明，异常模式倾向于集中在谱域的高频分量中。当谱能量分布向更高频率移动时，观察到右移现象。具体来说，它通过瑞利商格式描述了特征 \( f \) 处图信号的能量分布：

\[
E_f^{(\mathrm{R})} = \frac{ \sum_{k=1}^N \lambda_k \hat{x}_{k,f}^2 }{ \sum_{k=1}^N \hat{x}_{k,f}^2 } = \frac{ \mathbf{x}_f^\top L \mathbf{x}_f }{ \mathbf{x}_f^\top \mathbf{x}_f }.
\]
(1)

### 2.2 隐蔽异常

考虑一个完全平滑、无异常的图信号，其中节点特征独立同分布为 \( \mathbf{x}_f \sim \mathcal{N}(\mu \mathbf{1}, \sigma^2 I) \)，这里 \( \mathbf{1} \) 是全一向量，\( \mu \) 和 \( \sigma^2 \) 分别表示均值和方差。增加右移异常的比例会增大比值 \( \sigma / |\mu| \)。然而，并非所有现实世界中的异常都表现出高方差。先前研究 (Hooi et al., 2016 (https://arxiv.org/html/2606.00304#bib.bib23); Dou et al., 2020 (https://arxiv.org/html/2606.00304#bib.bib24)) 识别出一种独特的异常类型，称为隐蔽异常，其中恶意节点通过故意模仿正常良性节点的行为来破坏图。这种异常类型从根本上不同于常见的高方差假设，因为此类异常数据并非分布之外的点。相反，这些节点与正常节点高度相似，它们的插入会降低特征方差。这种异常的一个代表性例子出现在亚马逊虚假评论检测中，付费评论者倾向于产生一致的高评分。在这种情况下，原本自然的评分分布（包含多样的意见）被过多的相同高分评论所污染，导致整体分布向单一值集中，方差和多样性降低。

参见图注 图 2：在不同比例 \( \alpha \) 的邻居平均异常下，BA 图上的谱能量分布。较高的 \( \alpha \) 将能量向较低频率移动，表明左移现象。从概率角度来看，这种效应可以解释为一种 **方差抑制污染过程**：注入相同或高度集中的样本会降低经验方差。在谱域中，这种分布坍缩抑制了高频变化，并将谱能量向低频分量移动，产生 **左移** 现象。

###### 定义 2.1 (左移)。

由分布坍缩引起的异常将谱能量从高频移至低频，导致谱能量分布向左移动，即 \( \sigma / |\mu| \) 减小。

参见图注 图 3：在不同异常方差 \( \sigma \) (a, c) 和异常比例 \( \alpha \) (b, d) 下的局部谱异常。子图 (a, b) 对应 BA 图，子图 (c, d) 对应 Minnesota 网络。在所有图中，异常的高流行程度和高程度都会使曲线右移，显示了局部谱能量的有效性。
#### 现实数据集中的隐蔽异常。

我们进一步在两个广泛使用的图异常检测基准 YelpChi 和 Amazon 上验证了隐蔽异常的存在。数据集统计信息总结在表 LABEL:tab:static_dataset 中。结果如图 1 (https://arxiv.org/html/2606.00304#S2.F1) 所示，Amazon 的附加结果见附录 C (https://arxiv.org/html/2606.00304#A3)。对于每个数据集，我们计算正常节点和异常节点沿每个特征维度的平均局部谱能量。在 YelpChi 上，异常节点在一半的特征中表现出较低的谱能量，这表明这种模式并非偶然，而是与分布坍缩密切相关。一个合理的现实世界解释是，隐蔽异常