SDNE 算法 主页                                            博客   留言 

我们之前已经介绍过了常见的图表示学习方法,包括Deepwalk, Node2Vec, LINE 等方法。今天我们介绍一种将深度学习应用于graph embedding的方法:SDNE。

在SDNE之前,几乎所有的graph embedding方法都采用浅层网络。然而,由于图结构的复杂性,浅层网络很难捕捉到高度非线性的图结构,因此会得到次优的embedding结果。为了解决上述问题,SDNE提出了一种半监督的深度网络,同时联合优化first-order 和second order来学习图表示

首先,图结构的表示学习面临以下挑战:

  1. 非线性:如参考文献[1]所说,图结构具有复杂的非线性结构。因此需要网络有着较强的特征提取能力。
  2. 感知结构的复杂性:需要网络同时感知局部和整体的结构。
  3. 稀疏性:现实中的图结构通常是稀疏连接。

为了解决上述问题,SDNE被提出,其深层的网络结构可以更好地感知高度非线性的图结构。同时网络通过联合优化first-order 和second-order约束来同时感知图中局部和整体的结构,并缓解图结构中稀疏性的负面影响。

本文约含1.3K字,阅读时长约8分钟。主要分为以下部分:

  • SDNE的网络结构
  • SDNE的损失函数与优化
    • Second-order 损失函数
    • First-order 损失函数
    • 整体损失函数
  • 总结

SDNE的网络结构

SDNE的网络结构如图1所示:对于一个图结构,邻接矩阵为$S \in R^{n \times n}$, 其中$n$为节点的数目。以图1左边的单个节点为例,我们令网络的输入$x_i = s_i$,其中$s_i$即为邻接矩阵$S$的第$i$行,反映了节点$v_i$的邻域信息。输出为重构后的$x_i$:$\hat{x_i}$。如图1所示,利用自编码器的思想,我们通过重构输入$x_i$获取其低维稠密的embedding表示$y_i^{(K)}$(中间层特征)。

图1 SDNE的网络结构

SDNE的损失函数与优化

SDNE的损失函数由三部分组成,first-order,second-order和正则项。first-order 与 second-order相关概念我们在LINE算法中有介绍。

Note: First-order 约束指的是相连接的节点之间有着相似的embedding。 Second-order 约束指的具有共同邻域的节点具有相似的embedding,其中邻域结构相似的节点有着近似的$s_i$,该距离可以通过cos余弦距离来度量。

Second-order 损失函数

对于Second-order 约束,SDNE的输入为$x_i = s_i$,通过输出重构(自编码器)可以使得邻域结构近似的节点获得相近的embedding向量(Second-order)。然而由于图结构的稀疏性,$s_i$有很多的零元素。因此我们在损失函数层面加大对非零元素的惩罚:

\[L_{2}=\sum_{i=1}^n ||(\hat{x_i} - x_i) \odot b_i||_2^2\]

其中$\odot$为哈达玛积 (Hadamard product), $b_i = {b_{ij}}{j=1}^n$。当$s{ij}=0$时,$b_{ij}=1$,否则$b_{ij}=\beta > 1$。

First-order 损失函数

对于 First-order 约束,我们令相连接的节点具有相似的embedding。因此损失函数定义如下: \(L_1 = \sum_{i,j=1}^n s_{ij}||y_i^{(K)} - y_j^{(K)}||_2^2 = \sum_{i,j=1}^n s_{ij}||y_i - y_j||_2^2 = 2tr(Y^TLY).\) 当$s_{ij}=1$时,即代表节点相连。其中$L$对应图中的拉普拉斯矩阵,$L=D-S$,$D$是图中顶点的度矩阵,$S$是邻接矩阵,$D_{ii}=\sum_j s_{ij}$。

整体损失函数

在引入参数正则化后,损失函数的定义如下: \(L = L_2 + \alpha L_1 + v L_{reg}.\) 其中,$\alpha,v$ 为超参,$L_{reg}$ 为正则项损失函数,定义如下: \(L_{reg} = \frac{1}{2} \sum_{i=1}^K (||W^{(k)}||^2_{F} + ||\hat{W}^{(k)}||^2_{F})\) 为了得到全局最优,论文中使用深度信念网络对网络进行初始化,随即使用梯度下降法更新网络的参数。

总结

SDNE使用了自编码器结构来对图结构进行表示,同时在损失函数中引入了First-order 约束和 Second-order 约束来感知图中局部和整体的结构,来得到了更好的图表示。

参考文献

[1]:D. Luo, F. Nie, H. Huang, and C. H. Ding. Cauchy graph embedding. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pages 553–560, 2011.

[2]: https://mp.weixin.qq.com/s/RXXIPh2sv8Pr2Fuxypdn3w

[3]: https://zhuanlan.zhihu.com/p/56637181