图异常检测丨异常节点检测算法综述

大纲

根据算法模型的检测级别图异常检测任务大体上分为三类：

在上述分类下可以根据图数据类型可以进一步区分，主要包括：① 静态图：简单图，属性图 ② 动态图

针对静态图中的异常节点检测，主要从节点或者边属性进行区分。异常节点主要可以分为以下三种类型：

不同异常类型的节点如下所示：

异常点检测方法主要分类，点击查看~

主要是利用图谱或者节点的统计特征（出/入度等）来检测异常点。

主要是利用网络表示学习技术 (Network Representation Learning) 将图的结构信息嵌入向量表示中，然后用于下游的节点分析任务中。

[ICDE 2016] Embed ^[3]
首次提出一个有效地嵌入表示方法来检测结构异常点。首先使用图划分算法 METIS 将图中节点分为 $d$ 个社团，然后设计一种可以捕获节点和 $d$ 个社团连接强度的嵌入方法来学习节点表示。如果节点与多个社团有较强的连接关系那么该节点很可能是异常点。
基于 Deepwalk，Node2Vec，LINE 技术改进的算法。

KNN
matrix factorization (MF)
[IJCAI 2017] ALAD ^[4]
Accelerated local anomaly detection 主要检测社团异常点，主要基于非负矩阵分解的方法计算节点属性特征的相似性来判定节点异常程度。主要架构如下所示
[IJCAI 2017] Radar ^[5]
基于假设：异常不符合大多数属性模式，会导致更大的属性重构残差。模型架构如下：
[IJCAI 2018] Anomalous ^[6]
利用 CUR 矩阵分解技术来选择与网络结构密切相关的属性，然后通过 Radar 的残差分析发现异常。模型架构如下：

主要是利用 AE(autoencoder) 和 DNN(Deep Neural Network) 来学习图中节点属性表示。

[WSDM 2020] DONE ^[7]
无监督的神经网络模型来检测属性图中的全局异常点，结构异常点和社团异常点。主要认为异常点包含三个特征：1. 与不同社团中的节点有相似的属性 2. 连接不同的社团 3. 结构上属于某个社团但属性与另一社团模式相同。
模型结构如下图所示，主要是使用两个 AE 来学习节点属性和结构表示。

主要是将 GCN 图表示学习方法用于图中异常节点检测任务中。

普遍的模型框架如下图所示，在节点表示学习的部分融入了 GCN 模块。

主要模型如下：

[SDM 2019] DOMINANT^[8]
主要基于属性重构误差和结构重构误差来判断异常点。
详情参考另一篇博文：【2019/SDM】Deep Anomaly Detection on Attributed Networks
[TKDE 2020] ALARM^[9]
大体上和 DOMINANT 架构相同。创新点是考虑了节点多个属性视角下的异常情况，即节点在某个维度下表现出异常状态。
[CIKM 2019] SpecAE ^[10]
基于高斯混合模型 GMM 来检测全局异常点和社团异常点，利用节点表示来估计 GMM 参数，而且异常节点对应的 GMM 概率较小。
[WWW 2019] Fdgars ^[11]
基于半监督学习的 GCN 来学习诈骗者的评价和浏览记录等特征，训练数据中带有标签。。
[SIGIR 2020] GraphRfi ^[12]
主要用于推荐系统中，目标是利用异常检测来识别恶意用户，并通过减轻这些不可信用户的影响，为良性用户提供更准确的服务建议。

主要将强化学习 (RL，reinforcement learning) 的交互用于图异常检测任务中的节点分类任务中。

[WSDM 2019] GraphUCB ^[14]
主要优势在于专家知识反馈使模型不断优化。首先将节点分为 K 个簇，采用 K-armed 模型来度量选择一个特定节点作为潜在异常点的收益，然后采用专家反馈来优化模型。

[IJCAI 2020] AEGIS ^[15]
该模型首先通过 GNN 来生成输入属性图生成节点嵌入，然后训练能识别异常的生成器和判别器。模型架构如下图所示

动态图中异常检测的主要挑战是：动态图会引入大量的数据，同时需要捕捉时序信号来进行异常检测。

假设：正常节点的进化行为(即生成或移除与其他节点的连接)通常遵循稳定的模式，与异常节点相比它们的变化对图结构的影响较小。

[WSDM 2013] DBMM ^[16]
dynamic behavioral mixed-membership model (DBMM)
[TKDD 2019] LPD-MPA ^[17]
link prediction detection (LPD) + matrix perturbation assessment (MPA)
[CIKM 2017] MTHL ^[18]
MTHL（Multi-view Time-Series Hypersphere Learning）基于节点属性和边属性两个视角进行特征编码，学习具有软约束的正常样本超球体空间。

[KDD 2018] NetWalk ^[19]
仅考虑网络结构信息，采用自动编码器学习初始图上的节点表示，并在添加新边或删除现有边时增量更新。对于异常检测，NetWalk 采用流式 k-means 聚类算法，将当前时间戳内的现有节点进行分簇，然后以每个节点距离聚类最近的距离来衡量其异常得分。

将 GAN 模型融入图异常检测任务中，

[AAAI 2019] OCAN^[20]
基本思想是捕获正常的活动模式，并检测行为明显不同的异常情况。假设：良性用户和恶意用户在特性空间中处于不同的区域。基于 LSTM-AutoEncoder 从良性用户的历史社会行为中提取其内容特征，然后训练 one-class adversarial net。