GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction

论文地址：GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction

代码仓库：Graph-COM/GAD-NR: [WSDM 2024] GAD-NR : Graph Anomaly Detection via Neighborhood Reconstruction

关键词：Anomaly Detection, Graph Neural Network, Auto-Encoder

1.介绍

1.1 背景

现有的图自编码器（GAE）方法通过将图数据编码为节点表示，然后评估图的重建质量来检测异常。然而，现有的GAE模型主要优化的是直接连接的重建，导致在处理复杂结构的异常时效果较差，尤其是那些不符合簇型结构的异常节点。

为了解决这个问题，本文提出了一种新的方法——GAD-NR，即基于邻域重建的图异常检测方法。GAD-NR不仅重建节点之间的连接，还通过邻域重建来评估节点的异常性，考虑节点的局部结构、节点自身的属性以及邻域内其他节点的属性。通过计算节点邻域的重建误差，GAD-NR能够有效地区分正常节点和异常节点。

异常检测被分为以下三种主要类型：

1. 上下文异常（Contextual Anomalies）

定义：上下文异常指的是那些在属性上与其周围邻居有显著差异的节点，即它们的属性特征与大多数相邻节点不同。
示例：在社交网络中，某个用户的属性（例如年龄或兴趣）与其好友的属性有显著差异，可能代表异常行为，如虚假账户或恶意用户。

2. 结构异常（Structural Anomalies）

定义：结构异常指的是连接模式上异常的节点，即它们的连接结构与其他节点显著不同。
示例：在电子商务平台上，某些卖家之间通过异常密集的连接互相支持可能是虚假评论网络的一部分。

3. 联合类型异常（Combination/Joint Anomalies）

定义：联合类型异常同时在属性和结构上都显著偏离常规模式。这类异常需要同时考虑节点的属性特征和连接模式，才可以有效识别。
示例：在电子邮件网络中，一个节点可能表现出异常的属性特征（如不常用的语言），同时还与多个社区中大量用户有不正常的连接，这可能代表钓鱼邮件的发送者。

这三种异常类型分别从节点属性、连接结构以及两者的联合特征出发，为异常检测任务提供了不同的视角。GAD-NR模型通过邻域重建机制，尝试综合捕捉这三类异常，从而提升异常检测的全面性和准确性。

1.2 创新点

1.2.1. 引入邻域重建机制

传统的图自编码器（GAE）模型通常通过直接重建节点的连接结构来检测异常，而忽略了邻域的整体信息。这种方法在处理复杂的非簇型结构异常时存在局限性。
GAD-NR 提出了邻域重建机制，不仅重建节点的直接连接，还通过建模邻域特征分布，捕捉邻域的更全面的信息。这种方法使得模型在处理多样化的异常结构时表现更好，尤其是能够检测到复杂的联合类型异常。

1.2.2. 高斯分布近似邻域特征

在邻域重建中，GAD-NR创新性地使用了高斯分布来近似节点的邻域特征分布，而不是直接对邻域特征进行解码。这种分布式建模方法不仅能够有效表达邻域特征的统计属性，还显著降低了计算复杂度，从而提高了模型的效率。
通过估计邻域特征的均值和协方差矩阵，GAD-NR能够在保留邻域特征信息的同时，大大减少对高维邻域特征直接重建的复杂性，提升了计算效率和鲁棒性。

1.2.3. 重构损失的多维度综合设计

GAD-NR 在设计重建损失时，综合了自属性重建、度重建和邻域分布重建三种损失，并通过加权方式组合。这种多维度的重建损失能够捕捉到不同类型的异常特征，包括：
- 上下文异常：主要通过节点自属性重建损失捕捉。
- 结构异常：通过度重建损失来识别结构异常。
- 联合类型异常：通过邻域分布重建损失有效检测。
这种设计增强了模型的灵活性，使得它能够适应各种类型的图异常检测需求。

1.2.4. 重参数化技术与KL散度优化邻域分布重建

在邻域特征分布的重建中，GAD-NR通过重参数化技巧生成邻域特征样本，并使用KL散度作为损失函数，比较实际邻域分布和重建分布的差异。这种创新方法不仅提升了分布重建的稳定性，还在优化过程中增强了对异常特征的捕捉能力。
通过KL散度优化邻域分布，使得模型能够在较大范围内对比真实分布和重建分布的差异，从而有效识别出分布异常。

3. 问题定义和表述

3.1. 符号定义

文中定义了一个带有节点属性的静态图 $G = (V, E, X)$ ，其中：

$V$ 表示节点集合，包含 $N$ 个节点。
$E$ 表示边集合，描述节点之间的连接关系。
$X$ 是节点属性矩阵， $x_u$ 表示节点 $u$ 的属性向量。

其他符号包括：

$d_u$ ：表示节点 $u$ 的度，即与其相连的边数。
$y_u$ ：节点 $u$ 的标签，0 表示正常节点，1 表示异常节点，但在实际检测中假设异常标签是未知的。

3.2. 邻域定义

为捕捉节点的局部信息，定义了一阶邻域和增强的一阶邻域集合：

一阶邻域 $N_u$ ：指节点 $u$ 的直接相邻节点集合，即与节点 $u$ 相连的节点。
增强一阶邻域集合 $\overline{N}_u$ ：包括节点 $u$ 自身的属性以及其邻域节点的属性集合，用公式表示为： $\overline{N}_u = (x_u, \{x_v | v \in N_u\})$

这种定义扩展了传统邻域的范围，使得节点的邻域信息能够包括自身属性和周围节点的属性。

3.3. 问题表述

图异常检测的核心任务是识别图中的异常节点。具体目标是设计一个检测模型 $f(G)$ ，对图中的每个节点分配一个异常分数，用于判断该节点是否异常。文中假设正常节点和异常节点的增强邻域集合在统计分布上存在差异，这种差异可以通过邻域特征分布重建的损失来捕捉，从而实现异常检测。

4.方法

整体结构图

第四部分详细描述了 GAD-NR 模型的设计和实现，包括编码器和解码器的架构与算法。以下是各部分的细化讲解及其公式：

4.1 动机

GAD-NR 模型的动机是基于图自编码器（GAE）的局限性。传统GAE通过节点直接连接重建图结构，无法捕捉邻域的全局信息，因而对检测联合类型异常的能力较弱。GAD-NR引入了邻域重建，采用高斯分布来建模节点邻域特征，从而更好地捕捉图结构和属性之间的复杂关系。

4.2 通过邻域重建的 GAE

GAD-NR的关键是基于邻域重建的图自编码器。编码器部分利用图神经网络生成节点表示，解码器部分利用节点表示重建节点的自属性、度信息和邻域特征分布。

编码器部分

编码器使用信息传递机制，将节点及其邻域的属性进行聚合，生成最终的节点表示。节点 $u$ 的初始表示为其属性 $h^{(0)}_u = x_u$ ，在第 $l$ 层的聚合和更新操作为：

$h^{(l+1)}_u = \text{UPDATE}\left(h^{(l)}_u, \text{AGG}\left(\{h^{(l)}_v : v \in N_u\}\right)\right)$

其中 AGG 函数用于聚合邻居节点的表示，UPDATE 函数用于更新节点表示。通过多层迭代，最终得到节点 $u$ 的嵌入表示 $h^{(L)}_u$ 。

解码器部分

解码器重建节点的多维信息，包括节点自属性、度信息和邻域特征分布。

自属性重建：
解码器使用节点的最终表示 $h^{(L)}_u$ 来重建节点的原始属性 $h^{(0)}_u$ ，重建公式为：
$\hat{h}^{(0)}_u = \psi_x(h^{(L)}_u)$
其中 $\psi_x$ 是一个多层感知机（MLP）。节点自属性的重建损失 $L^x_u$ 通过距离函数 $D(\cdot, \cdot)$ 度量：
$L^x_u = D(h^{(0)}_u, \hat{h}^{(0)}_u)$
节点度重建：
度信息重建利用另一个MLP $\psi_d$ 来预测节点的度信息，公式为：
$\hat{d}_u = \psi_d(h^{(L)}_u)$
节点度重建损失 $L^d_u$ 计算实际度和重建度的差异：
$L^d_u = D(d_u, \hat{d}_u)$
邻域特征分布重建：
GAD-NR将邻域特征集合近似为高斯分布，使用均值和协方差矩阵描述邻域特征分布。邻域均值 $\mu_u$ 和协方差矩阵 $\Sigma_u$ 的计算公式为：
$\mu_u = \frac{1}{d_u} \sum_{v \in N_u} h^{(0)}_v$ $\Sigma_u = \frac{1}{d_u - 1} \sum_{v \in N_u} (h^{(0)}_v - \mu_u)(h^{(0)}_v - \mu_u)^\top$
使用MLP $\phi_\mu$ 和 $\phi_\sigma$ 从隐藏表示生成估计的高斯分布参数：
$\hat{\mu}_u = \phi_\mu(h^{(L)}_u)$ $\hat{\Sigma}_u = \text{diag}\left(\exp(\phi_\sigma(h^{(L)}_u))\right)$
邻域分布的重建损失通过KL散度计算：
$L^n_u = \text{KL}(\mathcal{N}(\mu_u, \Sigma_u) \| \mathcal{N}(\hat{\mu}_u, \hat{\Sigma}_u))$

4.3 异常检测

4.3.1. 异常分数的计算

每个节点的异常分数由三项重建损失的加权和构成，这三项损失分别是：

自属性重建损失 $L^x_u$ ：衡量节点的属性特征是否可以通过其编码表示有效重建，适用于捕捉上下文异常。
节点度重建损失 $L^d_u$ ：衡量节点度信息的重建误差，主要用于识别结构异常。
邻域特征分布重建损失 $L^n_u$ ：通过KL散度计算真实邻域特征分布与重建分布的差异，能够有效捕捉联合类型异常。

每个节点 $u$ 的总重建损失（即异常分数）计算公式为：

$L_u = \lambda_x L^x_u + \lambda_d L^d_u + \lambda_n L^n_u$

其中， $\lambda_x$ 、 $\lambda_d$ 和 $\lambda_n$ 是控制每项重建损失的权重超参数。这些权重参数可以根据检测任务的需求进行调整，以便优先关注不同类型的异常特征。

4.3.2. 不同类型异常的检测

GAD-NR模型可以灵活调整重建损失的权重，以适应不同的异常检测需求：

上下文异常：如果任务主要针对上下文异常（即节点属性与邻域差异显著的节点），则可以适当增加自属性重建损失的权重 $\lambda_x$ ，以提升模型对上下文异常的敏感度。
结构异常：若需要检测连接结构异常的节点（即连接模式与其他节点显著不同的节点），则可以增加度重建损失的权重 $\lambda_d$ ，从而强化模型对结构异常的捕捉能力。
联合类型异常：对于既包含属性差异又有结构异常的联合类型异常，可以增加邻域特征分布重建损失的权重 $\lambda_n$ ，以确保模型对联合类型异常的识别能力。

这种灵活性使GAD-NR可以根据不同应用场景或先验知识，调整模型对异常类型的偏好，从而提升检测效果的针对性。

4.3.3. 异常检测流程

GAD-NR的异常检测流程包括以下步骤：

训练模型：通过最小化重建损失来训练模型的编码器和解码器。
计算异常分数：对图中的每个节点，计算其自属性重建损失、度重建损失和邻域特征分布重建损失。
综合损失：将各项损失加权合成异常分数 $L_u$ ，重建损失越大的节点更可能是异常节点。
异常检测：通过设定阈值或直接排序，将异常分数较高的节点标记为异常节点。

4.3.4. 灵活性与适应性

GAD-NR的设计使得模型可以通过不同权重组合灵活适应多种类型异常的检测需求。例如，在网络安全应用中，可能更关注结构异常，因此可以加大度重建损失的权重；而在社交网络中，通常更关注上下文异常，这时可以增加自属性重建损失的权重。这种灵活的加权机制使得GAD-NR在实际应用中具备了更广泛的适应性。

5. 实验验证

5.1 实验设置

5.1.1. 数据集与基线模型

实验在六个真实数据集上进行：Cora、Weibo、Reddit、Disney、Books和Enron。这些数据集覆盖了不同的应用场景，如学术引用、社交媒体、公司邮件等，以确保GAD-NR的结果具备广泛的适用性。

基线模型包括以下几类：

基于特征的检测方法：如LOF（Local Outlier Factor）、IF（Isolation Forest）和MLPAE（MLP-based AutoEncoder）。
基于结构的检测方法：如SCAN（Structural Clustering Algorithm for Networks）。
基于属性和结构联合的模型：如GCNAE（Graph Convolutional Network AutoEncoder）、DOMINANT和GAAN（Graph Attention Autoencoder Network）。

5.1.2. 实验设置

实验将数据集分为两类进行评估：

真实异常数据集：如Weibo、Reddit等，包含真实标记的异常节点。
人工注入异常数据集：对于缺乏标记的Cora等数据集，实验通过注入上下文、结构和联合类型异常节点来模拟不同的异常情境。

5.2 问题介绍

围绕作者提出的四个关键问题，文章通过具体的实验设计和数据分析进行了验证：

5.2.1. 邻域重建对模型性能的提升有多大？

文章对GAD-NR和基线模型在不同类型异常检测上的性能进行了详细比较，涵盖了上下文异常、结构异常、联合类型异常等多种异常类型：

总体结果：GAD-NR在大多数数据集上优于基线模型，特别是在检测基准异常标签、上下文异常标签以及结构+联合类型异常标签方面表现出色。
性能提升的关键原因：GAD-NR的性能优势主要得益于其完整的邻域重建机制。GAD-NR不仅包含自属性重建和节点度重建，还引入了邻域特征分布重建，从而使得模型能够更全面地捕捉节点与邻居之间的复杂关系。这一机制帮助GAD-NR在各种异常检测任务中均表现良好。

5.2.2. GAD-NR中不同模块对不同类型异常检测的贡献是什么？

作者通过实验验证了GAD-NR中三种不同类型的重建损失（自属性重建、节点度重建、邻域特征分布重建）对模型性能的影响。为此作者分别移除这些重建损失项，并观察模型性能的变化：

实验设置：在实验中，作者通过将损失函数中的某个权重设置为0（即 $\lambda_x = 0$ 、 $\lambda_d = 0$ 或 $\lambda_n = 0$ ），来模拟移除该重建损失的效果，并观察模型性能的变化。实验结果列在表3中。
结果分析：
- 移除邻域重建损失 $\lambda_n = 0$ ：
  - 结果表明，移除邻域特征分布重建损失时，GAD-NR在检测两种异常类型（上下文异常和结构+联合类型异常）上的性能下降最为显著。这表明邻域重建损失在捕捉图中复杂的结构和联合异常时起到了关键作用。
- 移除自属性重建损失 $\lambda_x = 0$ ：
  - 当移除自属性重建损失时，GAD-NR在上下文异常检测中的性能下降较大。这符合预期，因为上下文异常主要依赖于节点的自身属性特征，当移除自属性重建后，模型难以准确捕捉到这种异常。
  - 对于结构+联合类型异常，性能下降较为适中，因为这种异常的检测不仅依赖于节点属性，还涉及邻域特征分布。
- 移除节点度重建损失 $\lambda_d = 0$ ：
  - 移除节点度重建损失后，GAD-NR的性能也有所下降，但程度较轻。这表明节点度信息对上下文和结构异常的检测贡献较小，单靠节点度不足以准确识别这些异常。
结论：
- 邻域重建损失：在检测结构和联合类型异常时尤为重要。
- 自属性重建损失：对上下文异常的检测效果显著，缺少该损失时性能会大幅下降。
- 节点度重建损失：对性能影响相对较小，但在一定程度上仍有助于结构异常的检测。

通过这些对比实验，作者证实了GAD-NR中各类重建损失在不同异常类型检测中的作用，为模型优化和权重设置提供了理论依据。

5.2.3. GAD-NR中的超参数对模型表现的影响如何？

作者通过调整GAD-NR模型中的三个关键超参数 $\lambda'_x$ 、 $\lambda'_d$ 和 $\lambda'_n$ ，分析了它们对不同类型异常检测性能的影响：

1. 自属性重建损失权重 $\lambda'_x$ 的影响

实验结果：在图3左上和图3左下（分别为Cora和Books数据集）中，当增加自属性重建损失的权重 $\lambda'_x$ 时，模型在检测上下文异常（Contextual Anomalies）和联合类型异常（Joint-Type Anomalies）上的AUC性能提升明显。
原因：自属性重建损失的增加会让解码器更关注节点的自身特征，从而对上下文异常和联合类型异常更加敏感。因为这些类型的异常依赖于节点特征的异常性，所以自属性重建对这类异常的检测起到了关键作用。

2. 节点度重建损失权重 $\lambda'_d$ 的影响

实验结果：在图3中间列显示，当调整节点度重建损失权重 $\lambda'_d$ 时，各种异常类型的检测性能变化不显著。
原因：度重建主要影响结构异常的检测，但对于上下文异常和结构异常而言，节点度的变化不大。同时，单靠度信息不足以有效区分异常和正常节点，因为某些正常节点也可能具有较高的度。因此，度重建损失的权重调整对检测性能的影响相对较小。

3. 邻域重建损失权重 $\lambda'_n$ 的影响

实验结果：图3右列显示，当增加邻域重建损失权重 $\lambda'_n$ 时，模型在联合类型异常（Joint-Type Anomalies）和结构+联合类型异常（Structural + Joint-Type Anomalies）检测上的性能提升显著。
原因：邻域重建损失能够捕捉到节点与其邻域之间的特征分布差异，对于联合类型异常，节点与邻居的整体分布差异较大。通过增加邻域重建损失权重，模型能更准确地检测到这类异常，从而提升在复杂异常结构上的检测性能。

总结

自属性重建损失 $\lambda'_x$ ：对于上下文和联合类型异常检测非常重要，增加该权重可以显著提升这些类型异常的检测性能。
节点度重建损失 $\lambda'_d$ ：对性能影响较小，特别是对上下文和结构异常的影响不显著，因为单靠度信息不足以准确识别这些异常。
邻域重建损失 $\lambda'_n$ ：对于检测联合类型和结构+联合类型异常至关重要，增加该权重有助于更好地捕捉节点与其邻域之间的复杂关系，从而有效检测复杂异常。

5.2.4. 高斯分布近似在邻域重建中的效率提升有多大？

比较了GAD-NR与NWR-GAE的性能与运行时间：

性能比较：
- GAD-NR 在所有六个数据集上的异常检测性能都显著优于NWR-GAE。
- NWR-GAE直接尝试匹配邻域表示的经验分布，这种方式虽然能更精确地捕捉邻居特征，但计算耗时。
由于直接匹配邻域特征，NWR-GAE可能更容易过拟合异常行为，而GAD-NR采用的高斯近似在重建时更具鲁棒性，能避免过拟合问题。
运行时间比较：
- GAD-NR 的高斯近似方法在计算 KL 散度时将邻域匹配的时间复杂度降低到 $O(d)$ ，而NWR-GAE使用的匈牙利算法的时间复杂度为 $O(d^3)$ 。
因此GAD-NR在处理相对较大的图时具有更好的扩展性，与NWR-GAE相比，能够更高效地检测异常。

总结：高斯分布近似使GAD-NR的运行效率显著提升，使其更适用于大规模图数据的异常检测。相比之下，NWR-GAE虽然在精确匹配邻域特征上有一定优势，但代价是更高的计算复杂度和潜在的过拟合问题。