论文标题：DeepWalk: Online Learning of Social Representations

论文链接：https://arxiv.org/abs/1403.6652

论文来源：KDD 2014

一、概述

本文提出DeepWalk方法，来学习图节点的社会表示（social representation），学习到的表示处于较低维度的连续空间中。DeepWalk采用自然语言处理中的语言模型来建模一系列图上的随机游走节点序列，这些随机游走序列可以看做一种特殊的语言。模型的输入是一张图，输出是节点的隐表示，下图展示了一个例子，可以看到表示空间中线性可分的部分对应于原图根据模块最大化（modularity maximization）得到的划分：

                                               example

二、社会表示的学习

1. 问题陈述

本文提出的方法用来捕获网络的拓扑信息。DeepWalk没有混合标签空间作为特征空间的一部分，而是采用无监督的方法来捕捉图的结构信息，忽略标签的分布。DeepWalk的目标是学习隐表示， 是隐表示的维度，学习到的特征向量可以与任何分类算法相结合，即使是简单算法也可以得到好的性能。

我们希望算法学习到的节点表示能够具备以下特性：

①可适应性（adaptability）：真实的网络是一直在变化的，新的社会关系（social relation）的出现不应该要求重复算法的学习过程；

②社区感知（community aware）：隐表示之间的距离应该代表一种度量，用来评估网络相应成员节点之间的相似性，这允许在具有同质性（homophily）的网络中进行泛化；

③低维（low dimensional）：当标注数据稀缺时，低维模型泛化地更好（可能是因为高维具有维度灾难），并且能够加速收敛和推断；

④连续（continuous）：除了提供社区成员的细致入微的视图外，连续表示在社区之间有平滑的决策边界，这允许更具鲁棒性的分类。

2. 随机游走

3. 幂律分布

如下图，节点在随机游走序列中出现的频率与自然语言中的词频同样满足幂律分布（power law）：

                                                  幂律分布

而语言建模技术解释了这种分布。我们的一个核心想法是应用于语言建模的技术（语言中的符合频率满足幂律分布，而随机游走序列中节点出现的频率也满足）也能够用来建模网络中的社区结构。

4. 语言模型

语言建模的目的是估计特定的词序列出现在语料库中的似然。具体的，给定一个词序列：

然而，随着随机游走序列长度的增加，该目标函数的计算变得不可行。语言模型对于这个问题的解决方案是将这个概率的预测反过来（其实就是指 SkipGram），其实是一种对原有问题的松弛。具体的做法是：

①使用一个词来预测其上下文；

②上下文既包含这个词左边的词也包含右边的词；

③移除了词的顺序限制，也就是说模型需要最大化任何在上下文中出现的词的似然，忽略这些词与该词的偏移。

将上述方法应用到节点表示学习上，要优化的问题就变成了：

解决上述问题能够捕获图结构中节点之间的相似性，具有相似邻域的节点会获得相似的表示。通过结合截断的随机游走与语言模型，可以满足前面提到的需要满足的表示的特性。

三、方法

                                              DeepWalk

第3行代表整个过程迭代 次，每次为每个节点采样一个随机游走。第4行代表对节点进行随机排列，这不是必须的，但是可以加速随机梯度下降的收敛。对于每个随机游走，使用第7行的SkipGram进行参数的更新。

• SkipGram

SkipGram是一种语言模型，它最大化句子中 大小的窗口内出现的词的共现概率。下面的算法展示了SkipGram在DeepWalk中的应用：

                                                    SkipGram

下图展示了DeepWalk的大致过程，其中(c)表示Hierarchical Softmax的过程：

                                                    DeepWalk

我们也可以通过统计随机游走中节点出现的频率来构建哈弗曼树，从而进一步加速训练过程，降低复杂度。

• 优化

                                       多个worker的影响

四、实验

1. 数据集

在BlogCatalog,Flickr和YouTube三个数据集上进行实验，进行节点的分类任务，数据集统计情况如下：

                                                    数据集统计

2. 实验结果

下面展示了三个数据集上对比不同baseline的效果：

                                             BlogCatalog

                                                   Flickr

                                                YouTube

3. 超参数敏感性

以下实验探究了不同超参数的敏感性：

                                               超参数敏感性