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的损失函数与优化
  • 总结

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算法中有介绍。

Second-order 损失函数

SDNE的输入为$x_i = s_i$,通过输出重构(自编码器)可以使得邻域结构近似的节点获得相近的embedding向量。然而由于图结构的稀疏性,$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$。

参考文献

[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.