DeepWalk: Online Learning of Social Representations
简介
DeepWalk是一种新的用于学习一个网络中的定点的向量表达的方法，它将一个一个独立的顶点映射到了一个连续的向量空间中，并且向量与向量之间的关系可以反映出这些顶点在整个网络中的关系。实际上这个方法是从word2vec的思想上发展而来，只不过它处理的是图上的顶点而非一个一个单词。 简单的说DeepWalk通过与传统类似的RandomWalk的方法将一个顶点变成了一个顶点的序列，然后再学习N这个这样的序列的向量表达方式。用word2vec的方式来类比的话，那么这个序列就是一个句子，学习N个这样的句子得到了句子中每一个单词的向量表达。 DeepWalk算法本身具有很好的扩展性，同时也是天然的支持在线学习以及并行处理，非常容易的应用在大规模的机器学习系统中。
DeepWalk方法具有以下的特点：
Adaptability- 可以应用于不断增长的社交图谱上而不需要反复的重新计算过去的社交关系Community aware- 学习到的顶点的向量表达之间的关系可以用于反应这两个顶点之间的社交相似程度（其实推广出去，这里并不单单适用于社交网络，向量捕捉到的实际上是拓扑相似度）Low dimensional- 学习到的向量具有低维向量的优点Continuous- 学习到的向量具有连续性的优点，这一点相比于直接输入每个顶点的编码方式优点显而易见了
原文里贴了两张图，是比较了YouTube Social Graph的Random walk之后的结构顶点的分布和Wikipedia Article Text的单词分布，非常非常的近似，这一点对于后文中使用类似语言模型的方法来建模向量非常的重要，建议大家找到原文看一下。
方法
随机游走（Random Walk）
Random Walk算法由来已久，简单的说就是在图中选择一个顶点，然后由这个顶点开始选择一个随机的相连的顶点访问，然后再随机选择一个这个访问的顶点的一个相连顶点……以此循环周而复始可以得到一个长度为N的顶点序列，这个序列就是以此随机游走的结果。
所以很明显的可以看到，这个随机游走的序列具有如下几个特点：
- 捕捉了图中的局部特点
- 容易的进行并行计算，同时选择N个节点开始遍历即可
- 在图的拓扑发生改变的时候，不需要重新计算整个图
语言模型
语言模型也是由来已久，最早的定义简单的说就是给定一个单词序列$W_1, W_2, …, W_n$，求$P(W_i|W_1, W_2, …, W_{i-1})$。
N-Gram、CBOW以及Skip-Gram：
N-Gram是最早出现的用于计算语言模型的方法，其应用了独立假设来简化以上的概率计算，其认为某一个单词出现的概率只和前n-1个单词有关，然后只要在语料上扫描一遍统计一下词频和条件概率即可。
CBOW(Continuous Bag-of-Words)何时提出的不记得了，其是给定了$W_{i-n}, …, W_{i-1}$以及$W_{i+1}, … W_{i+n}$这些词，预测$W_i$。
Skip-Gram与CBOW正好相反，其原理是给定单词$W_i$，预测$W_{i-n}, …, W_{i-1}$以及$W_{i+1}, … W_{i+n}$。
这篇论文里最后采用的是Skip-Gram的算法，因此整个算法流程如下：
算法过程
所以很明显的，这个算法分为两个部分：
- 随机游走采样 首先随机选择一个顶点，然后执行上文所述的随机游走方法。重复N次可以得到N个随机游走序列。
- 更新顶点向量 将随机游走序列变成一个窗口长度为W的Skip-Gram编码序列，然后进行梯度下降法更新权重。
优化
由于输出的空间是非常大的（整个顶点空间大小），因此训练一个这样的NN模型是非常效率底下的而且效果也存在问题，因此有如下两个方法来解决这个问题：
Hierarchical Softmax
顾名思义，就是把单个softmax输出变成一个分层次的softmax输出。简单的说就是构建一个二叉树，树的叶子节点对应于一个顶点，那么相应的每个中间简单都是一个二分类问题，也就可以用sigmoid函数来解决。那么每次训练输入一个单词时，只需要更新目标输出单词所在的叶子节点到根节点路径上的所有权重即可。
进一步优化就是用Huffman编码来生成这棵树，进而保证最频繁更新的节点路径最短。
Huffman树的构建方法还记得吗？首先统计叶节点的权重（可以是频率），然后建设一个最小堆，每次取出堆中前两个选择合并为一棵树（左节点、右节点），然后权重相加放回堆直到堆中只有一个元素，那么这个元素就是Huffman树的根节点。为什么这么做可以保证权重越大的元素路径越短？简单的说就是权重越大的叶子节点越后执行合并，那么其距离根节点也就越近。
Negative Sampling
Negative Sampling没有在论文中被提及，简单的说这是一种负采样算法。虽然只有一个softmax输出单元，但是每次只抽样N个负标签（即目标预测单词以外的单词）和目标标签一起进行权重更新，没有被采样的标签权重不计算。
这种方法在实际使用中效果还不错，但是有几个地方需要注意：
- 需要足够的样本和迭代轮数
- 负标签采样时需要考虑标签的分布特征
比较有名的zipfian采样方式，实验证明自然语言中的词频分布是比较符合zipfian分布的，当然也就可以应用于本文中的随机游走序列。但是在其他数据集上这个假设不一定都成立。
并行训练
当图谱非常大的时候，考虑到训练效率可以建设一个并行训练Pipeline，也就是并行的随机游走采样以及并行的权重更新。而对于一个动态变化中的图谱，只要图存储服务可以保证最终一致性那么不需要锁等手段来随机游走抽样，只要不停的运行即可。（譬如维护一个更新节点队列，服务每次从队列中获取需要重新计算的节点即可。）
非随机游走
随机游走某种程度上要求顶点之间具有很高的相似性。那么对于一些具有迥异不同顶点的图谱，随机游走所采样的队列并不一定最合适。 在这一点上就可以做到很灵活，从游走序列的产生到目标标签的产生之间都可以做非常多的基于特定数据集的优化。（譬如一个用户-商品购买情况图谱，可以选择从用户开始随机游走，但是只记录商品到游走的路径中。另一方面可以根据用户-用户之间的社交关系有优先级的进行游走等等。）