Deep Anomaly Detection on Attributed Networks

在说明这篇文章之前，首先说一下图卷积神经网络（GSN）

图卷积神经网络

  图是一种数据结构，相比于离散的点，更具有特征的是边带来的结构上的关系。普通的卷积神经网络处理的主要是结构性数据，类似图片或者nlp任务，这一类任务的输入数据是有迹可循的，结构不会发生变化，图片可以拆为像素进行卷积核操作，nlp可以将词进行词嵌入。

  而图不一样，图的拓扑结构是无迹可寻的，这也意味着普通的cnn无法满足在图上的搜索，但是我们可以参考cnn的公式$Y=XW+B$，结合图的规律探索出图的卷积神经网络。

  首先我们定义一个图，$\mathcal{G}=(\mathcal{V},\epsilon,X)$，（1）节点集合$\mathcal{V} = \mathcal{v_1},\mathcal{v_2},\ldots,\mathcal{v_n}$，其中$\left|\mathcal{V}\right|=\mathcal{n}$ （2）边集$\epsilon$，其中$\left|\epsilon\right|=\mathcal{m}$（3）节点属性$\mathrm{X}\in\Bbb{R}^{n \times d}$,其中第i行向量$\mathrm{x_i}\in\Bbb{R}^{d}(i=1,\ldots,n)$表示的是第i个节点的属性表示，d是属性的数量。举例如下：

  这里举例是有权图，如果是无权图那就都为0或者1，这张图的邻接矩阵A为：

v1 v2 v3 v4
v1 0 2 5 6
v2 2 0 0 0
v3 5 0 0 3
v4 6 0 3 0

  节点属性H，比如这四个点代表一个人，属性就可能是身高体重这类，举例如下：

姓名 性别 身高 体重
H1 239 2 175 120
H2 542 1 168 100
H3 937 2 188 150
H4 365 1 163 90

  如果我们取矩阵中的一行A1点乘H，即有：
$$
A_1 \cdot H=(0 \times H_1 +2 \times H_2 +5 \times H_3 + 6 \times H_4)
$$

  可以看出，这个结果是V1的邻居节点信号的加权求和，其中权重为关系强弱数值，由A提供，但是这个权重并没有进行归一化，也就是说，如果某个节点的邻居顶点越多，关系数值越强，这个结果就越大，为了避免这种情况，我们进行了归一化操作，即，让权重除以该节点所有边的关系数值的和，上这些边的关系数值成为真正意义上和为1的“权值”。那么我们所需要的数学过程即让A的每一行都除以该行的和。这是我们引入一个新的矩阵D，这个矩阵为对角矩阵，每行对角线上的元素为A的这行的元素和，也就是该顶点的度。

  D矩阵：
13 0 0 0
0 2 0 0
0 0 8 0
0 0 0 9

  接着执行$D^{-1}A$操作，即把A的每个关系数值都归一化了，变为权重，最后与H相乘，归一化后的表达式为：

$$
D_{1}^{-1}A_1 \cdot H=(1/13) \times (0 \times H_1 +2 \times H_2 +5 \times H_3 + 6 \times H_4)
$$

  所有行都进行同样的操作，$D^{-1}A \times\ H$，则每一行的量纲都一样了，不会出现某一行计算结果特别夸张。此时我们来考虑这个结果是什么，它相当于是某一个顶点周围所有顶点的信号按关系（权重）相加（聚合），那么这个结果就能表征出周围节点对自己的影响了，同时由于是通过矩阵进行运算，数据结构变得很规整，可以使用计算机来运算。

到这里为止有两个问题：

  • 首先是自身的因素没有考虑，就如上面的例子，没有考虑到$H_1$的影响，也就是自己，这是很不合理的，在传播过程中需要有“我”的参与，而不是都是客体。
  • 其次是没有考虑到邻居的影响，假如我的朋友只有一个大佬，那么我和大佬的关系网络如果用平均算法的话就等同了，所以直接把B的特征赋给A肯定是不合适的。

针对第一个问题：
把“我”的信息加进去
$$\tilde{A}=A+a \cdot I$$
这样A就不再是一个单位阵，在进行矩阵运算的时候就能考虑到自己的因素，因此D也要随之改变，D原本是表示出度，此时要变为出度+a
$$\tilde{D}=D+a \cdot I$$

针对第二个问题：
关系数值我们一般是通过两顶点信号之间的欧氏距离得到的，这只跟这两个顶点有关系，与其二阶邻居的信号是无关的，但是显然，邻居的邻居对我影响应该也是有的，我们怎样才能把二阶邻居的影响考虑进来呢？

比如，我叫V2，是个自闭症患者，班里一共四个人，我们自己的信号为社交能力值，我只认识V1，认识V1也不是因为我和他聊得来，纯纯是因为V1是个社牛， V1谁都认识。在这个例子中，如果考虑V2经过一次传播后形成的新V2，是通过$\tilde{D_2^{-1}}\tilde{A_2}H$计算的，结果为$\tilde{D_2^{-1}}\tilde{A_2}H$=(1/3)×(2×H1 + 1×H2 + 0×H3 + 0×H4) =2/3 H1 + 1/3H2 ,可以看出，此时新的V2的信号绝大部分来源于原来V1的信号，这当然不行，怎么经过一次传播后，把我一个社恐变成了社牛，这显然传播仍然存在问题，我希望能把二阶邻居和一阶邻居都考虑进去，二阶邻居和一阶邻居数量差别较大的时候，我希望能衰减这种影响，尽可能让自己的信号和别人的信号尽可能的分开来，那么就容易得到两种思路了，一是传播中我尽可能保留自己的权重，削减别人的权重，即$\tilde{A}$对做处理，第二是让“我”的信号根据传播产生某种线性变化，即随着二阶邻居和一阶邻居数量差别越大我信号越小，这样也可以把我和别人区分出来，也可以有我自己单独的特征，就是信号特别小嘛。GCN中是按照第二个思路来的，在数学上新的传播过程表示为：

$$
\tilde{D^{-\frac{1}{2}}}\tilde{A}\tilde{D^{-\frac{1}{2}}}H
$$
为什么是开根号，因为在衰减的时候还是要尽量满足归一化。可以看作对$\tilde{A_{i,j}}$做了如下操作：

$$
\tilde{A_{ij}} = \frac{A_{ij}}{\sqrt{D_{ii}} \sqrt{D_{jj}}}
$$

这样，当一阶邻居顶点j的度（边数量，也就是它的一阶邻居数量）很大，那么传播一次后信号就会变得很小，比如对V2来讲：

$$
\tilde{D_{22}^{-\frac{1}{2}}}\tilde{A_2}\tilde{D_{11}^{-\frac{1}{2}}}H=\frac{1}{\sqrt{3} \sqrt{14}}(2H_1+H_2)
$$

最后再通过一个激活函数，以及一个阈值b，就可以类似cnn得到一个前向传播公式：

$$
H^{l+1}=\sigma (\tilde{D^{-\frac{1}{2}}}\tilde{A}\tilde{D^{-\frac{1}{2}}}H^{l}W^{l}+b^{l})
$$

其中$\tilde{D^{-\frac{1}{2}}}\tilde{A}\tilde{D^{-\frac{1}{2}}}$是固定不变的，其余的工作就是构建全连接层，损失函数，反向传播，更新参数。

模型架构

前面铺垫了这么多，那么这个模型是什么呢，说白了就是类似transformer的编码器解码器，基于重构的方法。

  • 编码器：将输入的属性矩阵通过前面所述的图卷积神经网络提取特征，得到了一个杂糅属性和结构关系的低维向量表示。
  • 解码器：根据这个得到的中间表示重构，结构通过结构解码器进行重构，属性通过属性编码器进行重构。然后计算重构结果与实际结果，完成损失函数最小化。原文这里的结构解码器非常简单暴力，就用中间低维特征提取的内积完成，$\sigma(Z*Z^{T})$，属性用另一层GSN进行映射。

那么是怎么判断出异常的？

通过以上步骤重建拓扑网络结构，将结构和属性的重构误差共同学习，可以表示为：
$$
\mathcal{L}=(1-\alpha)R_S+\alpha R_A=(1-\alpha){\Vert A-\hat{A} \Vert}_F^2+\alpha {\Vert X-\hat{X} \Vert}_F^2
$$
式中，是用来平衡结构重建和属性重建影响的一个重要参数。

通过最小化目标函数，自编码器可以基于编码的潜在表示迭代地近似输入的属性网络，直至收敛。最后，使用两项重构误差之和来评估节点的异常性。 也就是，得分越高的实例越是被认为异常。再由该分数来计算属性网络的异常排名

带带锐评

  • 优点：结构新颖，基于图卷积神经网络，特征提取考虑了结构和点属性两方面特征，更能检测出异常，对稀疏图数据的处理有优势。
  • 缺点：重构本身具有一定的局限性，只适用于异常数据占比比较小的数据集进行训练，否则通过重构方法后的误差较大，还有前文所说的解码器构造有一点暴力了，因为Z不止有结构还有属性，直接内积会有干扰，改进措施应该可以剔除这部分因素进行单纯的结构重构。