综述：基于图的异常检测

本文主要介绍了2018年的3篇顶会论文，它们的共同点都是针对图(graph)的异常检测，但是具体的任务并不相同。这3篇论文分别是：

• Wang, Haibo, et al. "Deep structure learning for fraud detection." 2018 IEEE International Conference on Data Mining (ICDM). IEEE, 2018.（利用相似性度量检测图结构中结点的异常）
• Eswaran, Dhivya, et al. "Spotlight: Detecting anomalies in streaming graphs." Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018.（检测的是动态图，且检测对象是整个宏观图结构）
• Yu, Wenchao, et al. "Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks." Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018.（检测对象是动态图上的异常结点）

目录

• 1 Deep structure learning for fraud detection

• 1.1 用户结点间的相似性度量
• 1.2 模型的构建
• 1.3 实验

• 2 SpotLight: Detecting Anomalies in Streaming Graphs

• 3 NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks

• 3.1 Network Walk的生成
• 3.2 学习网络的表示
• 3.3 边的嵌入
• 3.4 如何适应动态图
• 3.5 异常检测
• 3.6 实验速览

• 4 总结

1 Deep structure learning for fraud detection

背景：现有的基于属性的方法并不健壮，因为欺诈者可以采取一些伪装行动来掩盖他们的行为属性。此外，现有的基于结构信息的方法只考虑浅层拓扑结构，使其对 「可疑块的密度」 很敏感，因为异常的用户行为嵌入也可能非常紧密，基于密度的一些方法可能不再work。本文的交互网络是一个user-item的交互网络，分别用 ， 集合表示。

1.1 用户结点间的相似性度量

对于用户结点 和 之间的相似性，本文定义为：

其中 表示结点 的邻居集合。特别地，当 时， 当 时，

本文的思路是通过学习一个相似度的度量模型来拟合这个定义的相似度。

1.2 模型的构建

这里先放一张模型的框架图：

在建模的过程中，作者想通过搭建网络来进行学习。但是图结构中没有相关features信息，这该怎么办呢？作者使用了与用户 交互的所有items的multi-hot编码(0、1形式)表示features，并记为 。

如上图所示，根据得到的features，使用Auto-Encoder将特征进行嵌入，并得到重建误差： 由于对于某一个特定的用户来说，交互的items数量可能较少，因此特征向量 是稀疏的。为了解决这一问题，作者通过为非零元素设置较大的权重来修正损失函数，得到： 其中当 时， ; 时， 。

对于模型中间得到的latent representation，作者定义 和 latent representation之间的距离： 其中 表示 在Auto-Encoder的中间表示，也就是encoder部分的输出。文章所需要预测的相似度为： 其中 。

对于预测的用户间相似度 和作者定义的相似度之间存在误差： 最终可以得到模型的Loss： 其中 表示模型的参数的L2正则化项。

异常检测：根据Auto-Encoder得到的中间表示 ，本文采用了最常见的基于密度的聚类算法DBSCAN算法进行异常检测。

1.3 实验

这里摘取了部分的实验，可以看出作者对异常的嵌入相较于正常样本来说还是分隔地比较开的，并在以下指标上超越了现有的方法。

2 SpotLight: Detecting Anomalies in Streaming Graphs

这篇文章的核心是将整个图结构嵌入为一个vector，然后进行图级别的异常检测。我读完的感受是：simple but effective！

如上图所示，在这篇工作中，作者专注于检测涉及一个大型密集有向子图的突然出现或消失的异常。本文所提出的图是基于时间序列的，并且这是一个由发出者和接收者构成的有向二分图。观察到 的时候存在一个边数众多的子图，因此认定这是一个异常子图。

「方法」：本文为了辨识出这样的异常子图，将各个时刻的图随机抽样生成 个子图（上图中的例子用三种颜色表示子图）。其中，源节点集合 的每个样本被抽样的概率是 ，目标结点集合 的每个样本被抽样的概率是 。将上述的操作重复 次，即可得到 个子图。

在示例的图中， ，三次抽样得到的三个子图分别用红、绿、蓝三色表示。第一个子图边的总数是3，因此embedding的第一个维度是3；第二个子图边的总数是1，因此embedding的第二个维度是1；第三个子图没找到边，所以embedding的第三个维度是0。这就完成了从3个子图到3个dimension映射的过程。也就是说，将一整个图嵌入为了一个向量。

在子图中的边数越多，那么那么这个子图就越异常，那么这个映射出来的向量就与非异常的向量的欧氏距离就越大。在此基础上，可以采用RRCF、RS-Forest等流数据异常检测的算法进行检测。

从作者的idea上看，可以说每一步都是比较有可解释性的；同时，随机取样的方式可以减少时、空复杂度。本文的思路简单清晰，效果也很好，同时文中还有详细的理论分析，是一篇很好的文章。

3 NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks

作者称所提出的NetWalk方法很灵活：适用于 「有向和无向网络」，「带权图和非带权图」，可以检测网络中可能通过 「动态插入或删除顶点和边」 的异常顶点和边，此外可以做到实时检测。

3.1 Network Walk的生成

首先以一个结点 为研究对象，由它诱导的随机游走序列为： 其中当前结点向邻居结点随机游走的概率是均等的。

3.2 学习网络的表示

如下图所示，作者提出clique embedding的概念，并利用自编码器学习每个结点的向量表示，自编码器的输入输出都是one-hot的编码，最终得到每个向量的latent representation。

对于一个随机游走的序列，作者主要设计了3个部分的Loss：

• 「重建误差」 
• 「游走序列内的误差」：游走序列内的结点的embedding相似 
• 「KL散度」：由于输入和输出向量的稀疏性，作者使用了一个具有稀疏性参数 的稀疏自动编码器:
    其中：
   

「最终可以得到cost function」：

3.3 边的嵌入

给出结点 的表示 ，边 的向量可以由下面的公式计算：

也就是说，边的嵌入可以由它所连接的两个节点的哈达玛积得到。

3.4 如何适应动态图

如下图所示，针对每个结点 都维护了一个邻居结点的储藏池 。

当有一条新的边 加入后，执行以下操作：

• 、 结点的度数自增；
• 用新的 概率更换结点 的储藏池 的每个结点；
• 对 执行同样操作。

根据新加入的边，就可以通过这个储藏池 来对随机游走序列进行更新。对于删除的边，也有类似的操作。

3.5 异常检测

本文采用了streaming k-means聚类进行异常检测。每个点的异常分数为它与任何聚类中心的最近距离。聚类中心的更新公式为： 其中 是原来的聚类中心。

3.6 实验速览

作者在4个数据集上进行了验证，均取得了SOTA的效果。

4 总结

以上三篇文章都是来自于数据挖掘领域顶会上的文章(KDD、ICDM)，个人认为这几篇工作创新性强、可解释性足，是几篇很有启发性的文章。

以上内容如有谬误、欢迎指出！转载需经同意并请注明出处。

联系方式：xdu DOT lhchen AT gmail DOT com。