图异常检测即在图结构上进行异常检测任务。随着图神经网络在实际应用中受到欢迎，图异常检测也在诈骗预防等领域收到重视。A Comprehensive Survey on Graph Anomaly Detection with Deep Learning是一篇图异常检测领域的综述，内容丰富且齐全。由于笔者最近的研究需要，本文针对其中属性图节点的异常检测部分进行解读和总结。
在图神经网络的异常检测领域中，针对的图数据结构主要分为三种：
- Plain Graph：一个静态的plain graph $G=\{V,E\}$是只有拓扑结构的图，只需要一个$n\times n$邻接矩阵$A=[a_{i,j}]$就可以描述，其中$a_{i,j}=1$如果节点$v_i$和$v_j$存在连接，否则$a_{i,j}=0$；
- Attributed Graph：一个静态的属性图$G=\{V,E,X\}$，除了拓扑结构外，每个节点还存在一个属性。属性矩阵$X=[\pmb x_i]_{n\times k}$包含了每个节点的属性向量；
- Dynamic Graph：一个动态图$G(t)=\{V(t),E(t),X_v(t),X_e(t)\}$中，节点、边以及对应的属性都会随时间变化。
而图结构中的异常节点，也大体分为三种：
- Global anomalies，即全局异常，只考虑节点的属性。它们中的节点具有与图中所有其他节点有显著不同的属性；
- Structural anomalies，即结构异常，只考虑图的结构信息。它们是具有不同连接模式的异常节点（例如，连接不同的社区，与其他社区形成密集的连接）；
- Community anomalies，即社区异常、群落异常，同时考虑了节点属性和图的结构信息。它们被定义为与同一社区中的其他节点相比具有不同属性值的节点。
静态属性图是应用场景最多的，它兼具了结构信息和特征信息，同时不像动态图那样复杂。静态属性图上的图异常检测大体分为三种：
- 基于深度网络的；
- 基于图卷积网络的；
- 基于强化学习的。
我们会依次介绍这些方法。
基于深度学习的方法
值得注意的是，这里的深度学习不包括GCN。
Bandyopadhyay等人提出了DONE模型，用于检测全局、结构和社区异常。具体来说，这个模型对每个节点考量三个异常得分，分别对应节点符合下面三种情形的程度：
- 它与不同社区的节点有相似的属性($o_i^a$)；
- 它与其他社区相连($o_i^s$)；
- 它在结构上属于一个社区，但属性符合另一个社区的模式($o_i^{com}$)。
如果一个节点显示这些特征，那么它被分配更高的异常得分。为了获取这些得分，DONE采用了两个独立的自编码器，即一个结构自编码器和一个属性自编码器：
两个自编码器都是通过最小化重建误差和保持假设连接节点在图中具有相似表示的同质性来训练的。在训练自编码器时，具有预定义特征的节点难以重构，因此由于其结构或属性模式不符合标准行为，会引入更大的重构误差。因此，应减轻异常的不利影响，以实现误差最小化。
DONE设计了一个对异常敏感的损失函数，它由5项组成：结构和属性重构误差$\mathcal L_{str}^{Recs},\mathcal L_{attr}^{Recs}$，保持同质性的两项$\mathcal L_{str}^{Hom},\mathcal{L}_{attr}^{Hom}$，以及一个$\mathcal{L}^{Com}$，它对两个自编码器中每个节点生成的表示进行进一步的限制，让图结构和节点属性“互补”：
\[\begin{aligned} \mathcal{L}_{str}^{Recs}&=\frac1N\sum_{i=1}^N\log(\frac1{o_i^s})\Vert\pmb t_i-\pmb {\hat{t}}_i\Vert_2^2\\ \mathcal{L}_{attr}^{Recs}&=\frac1N\sum_{i=1}^N\log(\frac1{o_i^a})\Vert\pmb x_i-\pmb {\hat{x}}_i\Vert_2^2\\ \mathcal{L}_{str}^{Hom}&=\frac1N\sum_{i=1}^n\log(\frac1{o_i^s})\frac1{\vert N(i)\vert}\sum_{j\in N(i)}\Vert\pmb h_i^s-\pmb h_j^s\Vert_2^2\\ \mathcal{L}_{attr}^{Hom}&=\frac1N\sum_{i=1}^n\log(\frac1{o_a^s})\frac1{\vert N(i)\vert}\sum_{j\in N(i)}\Vert\pmb h_i^a-\pmb h_j^a\Vert_2^2\\ \mathcal{L}^{Com}&=\frac1N\sum_{i=1}^N\log(\frac1{o_i^{com}})\Vert\pmb h_i^s-\pmb h_i^a\Vert_2^2\\ \mathcal{L}&=\mathcal{L}_{str}^{Recs}+\mathcal{L}_{attr}^{Recs}+\mathcal{L}_{str}^{Hom}+\mathcal{L}_{attr}^{Hom}+\mathcal{L}^{Com} \end{aligned}\]其中$N$是图的节点数，$\pmb t_i$和$\pmb x_i$分别是节点$i$的结构信息和属性信息，$\hat{\pmb t}_i$和$\hat{\pmb x}_i$是两个自编码器对结构和属性的重构向量。$\pmb h_i^s$和$\pmb h_i^a$是从结构编码器和属性编码器中学出的隐变量表示，也就是中间层的表示，$N(i)$表示节点$i$的邻居节点集合。我们是通过优化$\mathcal{L}$获取节点的异常得分，选出异常得分的前$k$个作为异常节点。
基于GCN的方法
图卷积神经网络 (GCN) 由于能够在图结构和节点属性中捕获全面的信息，在许多图数据挖掘任务（如链接预测、节点分类和推荐）中都取得了不错的成功。因此，许多异常节点检测技术都开始研究GCN。下图是这类异常检测方法的框架：
图卷积操作将图的结构和属性综合考虑，相比于前面基于深度学习的方法将两者分开处理，笔者认为基于图卷积的方法更加“有道理”。
DOMINANT模型是利用结构和属性的重构误差来计算每个节点的异常得分。DOMINANT，即Deep Anomaly Detection on Attributed Networks（这个命名…）由三个部分组成：图卷积编码器、结构解码器和属性解码器：
图卷积编码器通过多个图卷积层生成节点嵌入。结构解码器倾向于从学习到的节点嵌入中重构网络结构，而属性重构解码器重构节点属性矩阵。整个模型试图最小化下面的加权损失：
\[\begin{aligned} \mathcal{L}_{DOMINANT}&=(1-\alpha)\mathcal{R}_S+\alpha\mathcal{R}_A\\ &=(1-\alpha)\Vert{A-\hat{A}}\Vert_F^2+\alpha\Vert{X-\hat{X}}\Vert_F^2 \end{aligned}\]其中$\alpha$是权重系数，用来表示异常检测器更偏向于检测结构异常还是属性异常。$\hat{A}$和$\hat{X}$分别是结构解码器和属性解码器的输出，表示对邻接矩阵$A$和属性矩阵$X$的重构。$\Vert\cdot\Vert_F$为Frobenius范数。当网络训练完成后，节点$i$的异常得分：
\[score(i)=(1-\alpha)\Vert{\pmb a_i-\hat{\pmb a}_i}\Vert_2^2+\alpha\Vert{\pmb x_i-\hat{\pmb x}_i}\Vert_2^2\]即该节点的结构和属性的重构误差。同样的，对异常得分进行排序，分数最高的$k$个节点为异常。
为了提高异常节点检测的性能，Peng等人进一步从多个属性视图中探索节点属性来检测异常。多个属性视图（Multiple attributes views）用于描述对象的不同视图。例如，在社交网络中，用户的人口统计信息和发布的内容是两种不同的属性观点，它们分别是个人信息和社会活动的特征。所以存在这样一种情况：一个节点在视图A中正常，但在视图B中异常。
为了捕获这些信息，ALARM方法采用多个GCN对不同视图中的信息进行编码，并对它们进行加权聚合，生成节点表示。该模型的训练策略与DOMIANT相似，其目的是最小化网络重构损失和属性重构损失：
\[\begin{aligned} \mathcal{L}_{ALARM}&=\sum_{i=1}^n\sum_{j=1}^n-[\gamma A_{ij}\log\hat{A}_{ij}+(1-A_{ij})\log(1-\hat{A}_{ij})]+\Vert{X-\tilde{X}}\Vert_F^2 \end{aligned}\]其中$\gamma$是一个权重参数，$A_{ij}$是邻接矩阵第$i$行第$j$列元素，$\hat{A}_{ij}$是重构的邻接矩阵第$i$行第$j$列元素，$X$是原属性，$\hat{X}$是重构属性。ALARM中的异常得分函数和DOMINANT的相同。
SpecAE方法没有像前面那样通过重构误差发现异常，它用高斯混合模型（GMM）来探测全局异常和社区异常。仅考虑节点属性即可识别全局异常。对于社区异常，由于结构和属性的特殊性，需要共同考虑结构和属性。因此，SpecAE研究了一个图卷积编码器来学习节点表示，并通过反卷积解码器重构节点属性。然后使用节点表示来估计GMM中的参数。由于全局异常和群落异常的偏离属性模式，正常节点在GMM中会应该表现出更大的能量，而概率最低的$k$个节点被认为是异常。
静态属性图的异常检测的应用往往是识别网络诈骗和恶意用户，比如Fdgars模型便是将用户作为节点，用户的评论和浏览过的项目作为特征进行异常检测。
基于强化学习的方法
笔者不是很懂RL这个领域，所以对文章该部分进行了机翻。
Ding等人研究了使用强化学习进行属性图中的异常节点检测。他们提出的算法GraphUCB同时对属性信息和结构信息进行了建模，并继承了上下文多臂老虎机的优点来输出潜在的异常。GraphUCB根据节点的特征将其分组为$k$个簇，形成了一个$k$臂老虎机模型，并衡量了选择一个特定节点作为潜在异常进行专家评估的收益。通过专家对预测异常情况的反馈，不断优化决策策略。最终可以选择最可能的异常。
Reference
上文重点提及的模型所对应的论文：
- DONE在Outlier Resistant Unsupervised Deep Architectures for Attributed Network Embedding中提出；
- DOMINANT在Deep Anomaly Detection on Attributed Networks中提出；
- ALARM在A Deep Multi-View Framework for Anomaly Detection on Attributed Networks中提出；
- SpecAE在SpecAE: Spectral AutoEncoder for Anomaly Detection in Attributed Networks中提出。
