文献解读：Deep Anomaly Detection on Attributed Networks

原文地址：https://epubs.siam.org/doi/epdf/10.1137/1.9781611975673.67.

Introduction

属性网络无处不在，是现代信息基础设施的一个关键组成部分，其中额外的节点属性补充了知识发现中的原始网络结构。近年来，属性网络上的异常节点的检测受到了越来越多的研究关注，在网络安全、金融、医疗保健等各种高影响领域得到了广泛的应用。

过去的图节点异常检测经常存在网络稀疏性和数据非线性问题，无法捕捉到不同信息模式之间的复杂交互，从而对异常检测的性能产生负面影响。为了解决上述问题，本文通过开发一种新的深度模型来研究归属网络上的异常检测问题。

这篇文章提出的深度模型：

1. 明确地对拓扑结构和节点属性进行无缝建模，以便使用流行的图卷积网络(GCN)进行节点嵌入学习；
2. 通过深度自动编码器来解决异常检测问题，深度自动编码器利用学习到的嵌入来重建原始数据。GCN和自编码器之间的协同作用使我们能够通过从结构和属性的角度测量节点的重构误差来发现异常。在真实属性网络数据集上的大量实验证明了我们提出的算法的有效性。

一般来说，属性图节点异常检测中，属性网络上节点的异常不仅取决于它们与其他节点的相互作用(拓扑结构)，还取决于它们的内容不一致(节点属性)。

该领域之前是有一些方法被提出的，但都不是很适合，因为属性图异常检测存在下面的特性：

1. 网络稀疏性：网络结构在真实世界的属性网络上可能非常稀疏；因此，一些高度依赖于观察到的节点交互的方法很难运行；
2. 数据非线性：节点交互和节点属性在本质上是高度非线性的，而现有的主要是基于子空间选择的异常检测器用线性机制建模属性网络；
3. 复杂模态相互作用：由于两个信息源的混乱组合，属性网络很难处理，这需要一个统一的特征空间来捕获它们之间复杂的交互以进行异常检测。

为了解决上述挑战，本文提出用图卷积网络 (GCN) 来建模属性网络。GCN以拓扑结构和节点属性为输入，能够通过叠加多层线性单元和非线性激活函数来学习节点嵌入。尽管GCN在图节点分类和图分类中获得很不错的乘积，但如何将其应用于异常检测呢？因此本文提出了模型DOMINANT，即Deep Anomaly Detection on Attributed Networks，尝试解决这一问题。

Model

DOMINANT模型分成三个组件：

1. 属性网络编码器：建模网络结构和节点属性，用GCN进行节点嵌入表示学习；
2. 结构重构解码器：其目的是用学习到的节点嵌入来重建原始的网络拓扑结构；
3. 属性重构解码器：它试图用所获得的节点嵌入来重建所观察到的节点属性。

然后，利用节点的重构误差来标记属性网络上的异常。结构如下图所示：

编码器使用了三层的图卷积，激活函数为ReLU。我们在之前的文章中介绍了GCN的基本型，设输入属性图的邻接矩阵为$\pmb{A}$，属性矩阵为$\pmb{X}$，那么属性网络编码器就是

其中$\tilde{\pmb{A}}=\pmb D^{-\frac12}\pmb{AD}^{-\frac12}$为归一化的邻接矩阵。得到了属性图表示$\pmb Z$后，接下来的任务是重建结构和属性。重建结构等价于判断两个节点间存在连接的概率，等价于预测邻接矩阵：

至于重建属性，DOMINANT是再用一个图卷积，使图表示的维数和原数据维数相同。通过优化结构和属性的重构误差来优化网络：

其中$\Vert\cdot\Vert_F$为矩阵的Frobenius范数。类似的，每个节点的异常得分为：

Experiment

本文的实验部分用到了BlogCatalog，Flickr和ACM三个数据集，这些都是属性图异常检测方面的常用数据集了，前两个偏向于社交网络，而ACM是一个引文网络，将每篇论文视为网络上的一个节点，链接是不同论文之间的引文关系。每个数据集都是一张图：

值得注意的是，原数据集是没有异常标签的，上表所谓的异常数，其实是作者人为注入的异常。属性图节点的异常检测中，异常注入是一个固定的方法，即分别注入结构异常和属性异常：

1. 结构异常注入：选择$n\times m$个节点，每$m$个节点进行全连接，形成一个团 (clique)，团中的点就是异常点；

2. 属性异常注入：选择$n\times m$个节点（这是为了使两种异常在数量上相同），对于每个节点$i$，随机选择$k$个节点，选择$k$个节点中属性欧氏距离与$i$最远的节点的属性作为$i$的新属性，$i$就是异常点，即

   $$\begin{aligned} j&=\arg\max_{k}\Vert\pmb x_i-\pmb x_k\Vert_2\\ \pmb x_i&\gets\pmb x_j \end{aligned}$$

   文中将$k$的值设为50。

以下模型为baseline：

• LOF：异常检测的老方法了；
• SCAN：图结构的异常检测；
• AMEN：使用拓扑信息和结构信息来寻找异常邻居；
• Radar：SOTA的属性网络无监督异常检测框架。它通过表征属性信息的残差及其与网络信息的相干性来检测行为与大多数异常不同的异常；
• ANOMALOUS：基于CUR分解和残差分析，通过联合异常检测和属性选择对属性网络进行异常检测。

模型的ROC曲线：

DOMINANT达到了最佳效果，验证了模型的可靠性和优异性。可以看到三个数据集对应模型的参数$\alpha$是不同的，所以显然作者是进行了细致的调参。$\alpha$代表了DOMINANT对结构异常和属性异常的权衡，对不同$\alpha$进行的实验AUC值如下：

• Previous
  静态属性图上的异常节点检测
• Next
  文献解读：Learning with Feature Evolvable Streams