图神经网络_图嵌入_SDNE
0 提出背景
SDNE：Structural Deep Network Embedding
之前的DeepWalk、LINE、node2vec、struc2vec都使用了浅层结构，浅层模型往往不能捕获高度非线性的网络结构。
SDNE方法使用了多个非线性层来捕获节点的embedding。
1 预备知识
1阶相似度衡量的是：相邻的两个顶点对之间相似性。
2阶相似度衡量的是：两个顶点他们的邻居集合的相似程度。
2 主要思想
解释：
V
e
r
t
e
x
i
和
V
e
r
t
e
x
i
分别表示图
i
，
j
的邻接矩阵；
x
i
表示
V
e
r
t
e
x
i
第
i
行邻接矩阵值（节点
i
的连接关系），经过多层
e
n
c
o
d
e
r
编码
y
i
(
1
)
.
.
.
y
i
(
K
−
1
)
，得到压缩表示
y
i
(
K
)
,
经过多层
d
e
n
c
o
d
e
r
解码
y
i
^
(
K
−
1
)
.
.
.
y
i
^
(
1
)
，得到最终预测输出
x
^
i
\begin{aligned} & 解释：\\ & Vertex \ i和Vertex \ i分别表示图i，j的邻接矩阵；\\ & x_i 表示Vertex \ i \ 第\ i\ 行邻接矩阵值（节点i的连接关系），经过多层encoder编码y_i^{(1)}...y_i^{(K-1)}，得到压缩表示y_i^{(K)},经过多层dencoder解码\hat{y_i}^{(K-1)}...\hat{y_i}^{(1)}，得到最终预测输出\hat{x}_i \end{aligned}
解释：Vertex i和Vertex i分别表示图i，j的邻接矩阵；xi表示Vertex i 第 i 行邻接矩阵值（节点i的连接关系），经过多层encoder编码yi(1)...yi(K−1)，得到压缩表示yi(K),经过多层dencoder解码yi^(K−1)...yi^(1)，得到最终预测输出x^i
3 结构误差
3.1 1阶相似度
1阶相似度，可以让图中相邻两个结点之间对应的embedding vector在隐藏空间更接近。定义如下：
L
1
s
t
=
∑
i
,
j
=
1
n
s
i
,
j
∣
∣
y
i
(
K
)
−
y
j
(
K
)
∣
∣
2
2
=
∑
i
,
j
=
1
n
s
i
,
j
∣
∣
y
i
−
y
j
∣
∣
2
2
L_{1st} = \sum_{i,j=1}^n s_{i,j}||y_i^{(K)} - y_j^{(K)}||_2^2 = \sum_{i,j=1}^n s_{i,j}||y_i-y_j||_2^2
L1st=i,j=1∑nsi,j∣∣yi(K)−yj(K)∣∣22=i,j=1∑nsi,j∣∣yi−yj∣∣22
3.2 2阶相似度
二阶相似度，可以让结构相似的节点的embedding vector在隐藏空间更接近。定义如下：
L
2
n
d
=
∑
i
=
1
n
∣
∣
x
^
i
−
x
i
∣
∣
2
2
L_{2nd} = \sum_{i=1}^n ||\hat{x}_i-x_i||_2^2
L2nd=i=1∑n∣∣x^i−xi∣∣22
上述定义存在的问题是：由于图的稀疏性（邻接矩阵中的0元素远多于非0元素），所以神经网络全部输出0也能取得一个不错的效果，但这不是我们想要的。
改进方法：带权损失函数，对非0元素具有更高的乘法系数（提高对非0元素的关注度）。修正后的损失函数为：
L
2
n
d
=
∑
i
=
1
n
∣
∣
(
x
^
i
−
x
i
)
⊙
b
i
∣
∣
2
2
=
∣
∣
(
X
^
−
X
)
⊙
B
∣
∣
F
2
L_{2nd} = \sum_{i=1}^n||(\hat{x}_i-x_i)\odot b_i||_2^2 = ||(\hat{X}-X)\odot B||_F^2
L2nd=i=1∑n∣∣(x^i−xi)⊙bi∣∣22=∣∣(X^−X)⊙B∣∣F2
其中：
⊙
表示逐元素积，
b
i
=
{
b
i
,
j
}
j
=
1
n
，若
s
i
,
j
=
0
,
则
b
i
,
j
=
1
，否则
b
i
,
j
=
β
>
1
\odot表示逐元素积，b_i=\{b_{i,j}\}_{j=1}^n，若s_{i,j}=0,则b_{i,j}=1，否则b_{i,j}=\beta>1
⊙表示逐元素积，bi={bi,j}j=1n，若si,j=0,则bi,j=1，否则bi,j=β>1
3.3 整体优化目标
联合优化损失函数为：
L
m
i
x
=
L
2
n
d
+
α
L
1
s
t
+
μ
L
r
e
g
L
r
e
g
=
1
2
∑
(
∣
∣
W
(
k
)
∣
∣
F
2
+
∣
∣
W
^
(
k
)
∣
∣
F
2
)
\begin{aligned} & L_{mix} = L_{2nd} + \alpha L_{1st} + \mu L_{reg} \\ & L_{reg} = \frac{1}{2} \sum(||W^{(k)}||_F^2+||\hat{W}^{(k)}||_F^2) \end{aligned}
Lmix=L2nd+αL1st+μLregLreg=21∑(∣∣W(k)∣∣F2+∣∣W^(k)∣∣F2)
L m i x 是联合损失，其中： α 为控制 1 阶损失的参数， μ 为控制正则化项的参数； L r e g 是正则化项，是对 k 层 e n c o d e r 和 d e c o d e r 的 L 2 正则化。 \begin{aligned} & L_{mix}是联合损失，其中：\alpha为控制1阶损失的参数，\mu为控制正则化项的参数；\\ & L_{reg}是正则化项，是对k层encoder和decoder的L_2正则化。\\ \end{aligned} Lmix是联合损失，其中：α为控制1阶损失的参数，μ为控制正则化项的参数；Lreg是正则化项，是对k层encoder和decoder的L2正则化。
模型通过反向传播，不断减小L_mix，优化模型参数，求得节点的embedding。
4. 图嵌入算法小结
- DeepWalk：采用随机游走形成序列，采用skip-gram方式生成节点embedding；
- node2vec：不同的随机游走策略形成序列，类似skip-gram方式生成节点embedding；
- LINE：捕获节点的一阶、二阶相似度分别求解、拼接，作为节点embedding；
- struc2vec：对图的结构信息进行捕获，在结构标识大于邻居标识时效果好；
- SDNE：采用多个非线性层捕获节点一阶、二阶相似性。