文章链接：http://www.public.asu.edu/~kding9/pdf/SDM2019_Deep.pdf
源码链接：https://github.com/kaize0409/GCN_AnomalyDetection
TL;DR
目前属性网络中的异常检测方法都是使用浅层的学习机制或者子空间特征，但现实中属性网络非常稀疏并且数据是非线性的。论文中提出一种基于图自编码器的异常检测模型 DOMINANT (Deep Anomaly Detection on Attributed Networks)，同时考虑了结构特征和属性特征，实验在真实网络中取得了较好的效果；
Problem Definition
- Attributed Networks: 属性网络 G = ( V , E , X ) \mathcal{G}=(\mathcal{V}, \mathcal{E}, \mathbf{X}) G=(V,E,X)， 节点集合 ∣ V ∣ = n |\mathcal{V}| =n ∣V∣=n， 边集合 ∣ E ∣ = m |\mathcal{E}| =m ∣E∣=m，节点属性 X ∈ R n × d \mathbf{X} \in \mathbf{R} ^{n×d} X∈Rn×d，邻接矩阵 A \mathbf{A} A；
- Anomaly Ranking on Attributed Networks：属性网络中的异常检测形式化转化为 图中所有节点的异常度排序；
Model / Algorithm
整个模型的架构图如下所示，主要包含三部分：
- attributed network encoder： 使用GCN架构来进行node embedding；
- structure reconstruction decoder: 使用 node embedding 来重构图结构；
- attribute reconstruction decoder：使用 node embedding 来重构图中节点属性；
综合考虑属性和结构的重构误差来判定节点的异常；
Attributed Network Encoder
采用 GCN 模型来embedding，每层的计算公式如下：
H
(
l
+
1
)
=
f
(
H
(
l
)
,
A
∣
W
(
l
)
)
=
σ
(
D
~
−
1
2
A
~
D
~
−
1
2
H
(
l
)
W
(
l
)
)
\mathbf{H}^{(l+1)}=f\left(\mathbf{H}^{(l)}, \mathbf{A} \mid \mathbf{W}^{(l)}\right)=\sigma\left(\widetilde{\mathbf{D}}^{-\frac{1}{2}} \widetilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{H}^{(l)} \mathbf{W}^{(l)}\right)
H(l+1)=f(H(l),A∣W(l))=σ(D
−21A
D~−21H(l)W(l))
文章中采用了三层图卷积架构，
H
(
1
)
=
f
R
e
l
u
(
X
,
A
∣
W
(
0
)
)
H
(
2
)
=
f
R
e
l
u
(
H
(
1
)
,
A
∣
W
(
1
)
)
Z
=
H
(
3
)
=
f
R
e
l
u
(
H
(
2
)
,
A
∣
W
(
2
)
)
\begin{aligned} \mathbf{H}^{(1)} &=f_{R e l u}\left(\mathbf{X}, \mathbf{A} \mid \mathbf{W}^{(0)}\right) \\ \mathbf{H}^{(2)} &=f_{R e l u}\left(\mathbf{H}^{(1)}, \mathbf{A} \mid \mathbf{W}^{(1)}\right) \\ \mathbf{Z}=\mathbf{H}^{(3)} &=f_{R e l u}\left(\mathbf{H}^{(2)}, \mathbf{A} \mid \mathbf{W}^{(2)}\right) \end{aligned}
H(1)H(2)Z=H(3)=fRelu(X,A∣W(0))=fRelu(H(1),A∣W(1))=fRelu(H(2),A∣W(2))
Structure Reconstruction Decoder
用于判定图结构异常：
R
S
=
A
−
A
^
\mathbf{R}_{S}=\mathbf{A}-\widehat{\mathbf{A}}
RS=A−A
，可以根据两个节点间是否存在边来计算
A
^
\widehat{\mathbf{A}}
A
，类似于链路预测过程；所以添加了一个 link prediction layer：
p
(
A
^
i
,
j
=
1
∣
z
i
,
z
j
)
=
sigmoid
(
z
i
,
z
j
T
)
p\left(\widehat{\mathbf{A}}_{i, j}=1 \mid \mathbf{z}_{i}, \mathbf{z}_{j}\right)=\operatorname{sigmoid}\left(\mathbf{z}_{i}, \mathbf{z}_{j}^{\mathrm{T}}\right)
p(A
i,j=1∣zi,zj)=sigmoid(zi,zjT)
对于所有节点转化为矩阵的形式为：
A
^
=
sigmoid
(
Z
Z
T
)
\widehat{\mathbf{A}}=\operatorname{sigmoid}\left(\mathbf{Z Z}^{\mathrm{T}}\right)
A
=sigmoid(ZZT)
Attribute Reconstruction Decoder
用于判定节点属性异常：
R
A
=
X
−
X
^
\mathbf{R}_{A}=\mathbf{X}-\widehat{\mathbf{X}}
RA=X−X
；根据节点embedding重构；
X
^
=
f
R
e
l
u
(
Z
,
A
∣
W
(
3
)
)
\widehat{\mathbf{X}}=f_{R e l u}\left(\mathbf{Z}, \mathbf{A} \mid \mathbf{W}^{(3)}\right)
X
=fRelu(Z,A∣W(3))
Anomaly detection
综上模型优化的目标函数是：
L
=
(
1
−
α
)
R
S
+
α
R
A
=
(
1
−
α
)
∥
A
−
A
^
∥
F
2
,
+
α
∥
X
−
X
^
∥
F
2
\begin{aligned} \mathcal{L} &=(1-\alpha) \mathbf{R}_{S}+\alpha \mathbf{R}_{A} \\ &=(1-\alpha)\|\mathbf{A}-\widehat{\mathbf{A}}\|_{F}^{2},+\alpha\|\mathbf{X}-\widehat{\mathbf{X}}\|_{F}^{2} \end{aligned}
L=(1−α)RS+αRA=(1−α)∥A−A
∥F2,+α∥X−X
∥F2
模型训练收敛之后需要计算每个节点的异常分数，计算公式为
score
(
v
i
)
=
(
1
−
α
)
∥
a
−
a
^
i
∥
2
+
α
∥
x
i
−
x
^
i
∥
2
\operatorname{score}\left(\mathbf{v}_{i}\right)=(1-\alpha)\left\|\mathbf{a}-\widehat{\mathbf{a}}_{i}\right\|_{2}+\alpha\left\|\mathbf{x}_{i}-\widehat{\mathbf{x}}_{i}\right\|_{2}
score(vi)=(1−α)∥a−a
i∥2+α∥xi−x
i∥2
Experiments
数据集
实验结果对比；