0 提出背景

SDNE：Structural Deep Network Embedding

之前的DeepWalk、LINE、node2vec、struc2vec都使用了浅层结构，浅层模型往往不能捕获高度非线性的网络结构。

SDNE方法使用了多个非线性层来捕获节点的embedding。

1 预备知识

1阶相似度衡量的是：相邻的两个顶点对之间相似性。

2阶相似度衡量的是：两个顶点他们的邻居集合的相似程度。

2 主要思想

$$\begin{array}{rl}& 解释：\\ & Vertexi和Vertexi分别表示图i，j的邻接矩阵；\\ & x_i表示Vertexi第i行邻接矩阵值（节点i的连接关系），经过多层encoder编码y_i^{(1)}...y_i^{(K-1)}，得到压缩表示y_i^{(K)},经过多层dencoder解码{\widehat{y_i}}^{(K-1)}...{\widehat{y_i}}^{(1)}，得到最终预测输出{\hat{x}}_i\end{array}$$

3 结构误差

3.1 1阶相似度

1阶相似度，可以让图中相邻两个结点之间对应的embedding vector在隐藏空间更接近。定义如下：
$$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$$

3.2 2阶相似度

二阶相似度，可以让结构相似的节点的embedding vector在隐藏空间更接近。定义如下：
$$L_{2nd}=\sum _{i=1}^n||{\hat{x}}_i-x_i|{|}_2^2$$
上述定义存在的问题是：由于图的稀疏性（邻接矩阵中的0元素远多于非0元素），所以神经网络全部输出0也能取得一个不错的效果，但这不是我们想要的。

改进方法：带权损失函数，对非0元素具有更高的乘法系数（提高对非0元素的关注度）。修正后的损失函数为：
$$L_{2nd}=\sum _{i=1}^n||({\hat{x}}_i-x_i)\odot b_i|{|}_2^2=||(\hat{X}-X)\odot B|{|}_F^2$$
其中：
⊙ 表示逐元素积， 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 整体优化目标

联合优化损失函数为：
$$\begin{array}{rl}& 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{array}$$

$$\begin{array}{rl}& L_{mix}是联合损失，其中：\alpha 为控制1阶损失的参数，\mu 为控制正则化项的参数；\\ & L_{reg}是正则化项，是对k层encoder和decoder的L_2正则化。\end{array}$$

模型通过反向传播，不断减小L_mix，优化模型参数，求得节点的embedding。

4. 图嵌入算法小结

• DeepWalk：采用随机游走形成序列，采用skip-gram方式生成节点embedding；
• node2vec：不同的随机游走策略形成序列，类似skip-gram方式生成节点embedding；
• LINE：捕获节点的一阶、二阶相似度分别求解、拼接，作为节点embedding；
• struc2vec：对图的结构信息进行捕获，在结构标识大于邻居标识时效果好；
• SDNE：采用多个非线性层捕获节点一阶、二阶相似性。