《经典论文阅读2》Deepwalk算法—基于随机游走的节点表示学习

word2vec使用语言天生具备序列这一特性训练得到词语的向量表示。而在图结构上，则存在无法序列的难题，因为图结构它不具备序列特性，就无法得到图节点的表示。deepwalk 的作者提出：可以使用在图上随机游走的方式得到一串序列，然后再根据游走得到的序列进行node2vec的训练，进而获取得到图节点的表示。本质上deepwalk和word2vec师出同门（来自同一个思想），deepwalk算法的提出为图结构学习打开了新的天地。

1. 前言

walk-basedGE，Graph Emebddingmessage-passing-basedGNN

deepwalk、metapath2vec

因为内容过多，本期讲解分两期，第一期首先介绍GE类算法，第二期介绍图神经网络算法。GE类的算法经典的还属deepwalk，所以本期首先围绕deepwalk这篇论文进行介绍。

one-hot

但是如果想得到图结构中顶点表示该怎么办呢？毕竟图结构与语言序列不同，图上的一个顶点可能有很多个连接点，而文本序列则是单线条，如下图所示，可以看出图结构与文本序列有着非常大的差异。

那就没有办法去解决图节点的表示学习了吗？

当然不是！而且方法还有很多，聪明的前辈们提出了一种叫做『deepwalk』的算法，这个算法着实让我惊艳。本质上说，deepwalk算法是基于图上的word2vec，而启发作者的其实是：由于二者数据分布（自然语言的词频和随机游走得到子图的节点的频率）存在一定的相似性。

所以说，很多精妙的想法不是凭空造出来的，背后其实是有数据统计支撑的。

2. 思想

文本序列虽然只是一个序列，但是我们可以想象有一张巨大的由各个单词组成的图，我们随机从图上连接几个顶点就组成了一句话。例如『论文解析之deepwalk』其实就是从一张偌大的图中挑选出这么几个单词组成的一句话，如下图所示：

那么对于其它的图，我们也可以这么做。即：从一张大图上随机游走，这样便得到了一串序列。将这得到的序列便可以利用word2vec的方法来学习节点的表示了。

想法是不是很精妙？真的很精妙！其实我们自己在解决问题的时候，也需要抱着这样的『转换』思想，如果直接求A不成，那么能否利用已有的知识求A？这再次说明问题的转化能力是一个非常重要的能力。

embedding

3. 模型

3.1 模型构造

deepwalkrandom walk generator

• 采样方法
  deepwalk中的采样方法其实是非常简单的均匀采样。下文中介绍到了这一采样算法：
  
  step1. 首先随机采样一个节点作为此次walk的根节点。
  step2. 接着从采样序列的最后一个节点的邻居中再随机选一个节点
  step3. 直到采样序列的最大长度达成。

t

word2vecembeddingdeepwalkSkipGramHierarchical softmax

3.2 Skip Gram

有兴趣的请翻前文。

3.3 Hierarchical softmax

Hierarchical softmax

例如：假设一部词典一共有8个单词，那么就可以构建一个如下所示的二叉树。

其中：

{0，1}mO(v)O(logV)Hierarchical softmax

优化算法

deepwalkstochastic gradient descent

3. 实际效果

deepwalk论文作者给出了一个效果示例图，如下图所示：

左侧是一个图结构信息，右侧是根据学习到的embedding得到的一个二维展示，可以看出图结构和节点表示几乎能够一一对应起来（顶点的颜色表示输入图对一个基于模块的聚类）。

4. 发现

zipf's laws

4.1 zipf’s law

zipfs'law

y=1/x

（齐夫定律的图像要稍微直一些）。作者发现，如果原始图的顶点服从齐夫定律，那么根据随机游走选出来的子图的频次也会满足齐夫定律。

这个时候作者就想到，如果满足齐夫定律的自然语言可以用语言模型建模，那么用随机游走方式得到的子图是否也可以通过语言模型来建模呢？于是接着有了后面使用SkipGram算法训练embedding，才有了这篇论文的诞生。

5. 实验效果

deepwalk

好了，到此第二期的经典论文阅读的第一部分工作已经结束，后面再围绕metapath2vec进行介绍。高质量分享实属不易，期待各位同学们的评论哟。