[Graph Embedding] DeepWalk 论文笔记
[Graph Embedding] DeepWalk
Introduction
图表示学习是将图(Graph/Network)中节点在一个低维的连续的向量空间中表示出来，这种表示能够保留节点与邻居的相似性、节点的社区成员属性等。得到节点的向量表示就可以喂给下游的学习模型进行节点分类，边预测等任务。
DeepWalk作为图表示学习的经典方法之一，核心方法就是通过对一定数量的节点做RandomWalk（随机游走），然后将得到的节点序列作为顶点的向量输入表示，通过使用skip-gram model 进行学习，得到最终的表示。下图为对一个空手道俱乐部成员的social relationship Graph表示到一个二维空间。
Random Walks
所谓随机游走（random walk）就是从一个节点开始随机的选择下一个与当前的节点相邻的节点（提前设定随机游走结束的条件），最终形成一条节点序列。截断随机游走（truncated random walks）就是指长度固定的随机游走。使用随机游走的好处有：
- 并发性。随机游走可以同时在图上的多个节点上同时进行。
- 适应性。由于图的结构是随时间动态变化的，所以当图变化的时候，不需要对所有节点重新进行随机游走，只需要对与图中变化了的子图有关的节点重新进行随机游走得到新的向量表示就可以。
Graph Embedding 与 NLP
作者发现了对graph上的节点进行随机游走的节点频率与NLP（自然语言处理）中word在文章中的出现频率都满足一样的power-law（幂律分布）。如下图所示：
既然网络（Graph/Network）的特征特性与自然语言处理那么相近，那么我们是否可以将NLP中的词向量的模型用在Graph Embedding中，这就是本文的核心观念。
要想了解DeepWalk的算法原理，需要提前了解NLP中Word Embedding 和 Word2Vec的基本内容，并且要理解其中的一种算法——SkipGram。
DeepWalk 算法原理
DeepWalk算法主要由2部分组成，第一部分是产生节点的随机游走序列，第二部分是参数的更新。算法的流程图如下图所示。
第2步是在构造Hierarchical Softmax（层次Softmax）所需的二叉树，算法中使用到Hierarchical Softmax加速算法的学习，这里不多加阐述。第3步是总的迭代次数，共γ次。每一次迭代（第4步到8步）中，对Graph中的每一个节点进行一次random walk，然后将生成的节点序列作为输入向量，输入SkipGram算法中进行参数的学习。
参数更新如下图所示：
第3步是需要优化的函数，即使得当顶点为 v j v_j vj时，它所在的random walk序列中的 [ j − w : j + w ] [j - w : j + w] [j−w:j+w]中除了 v j v_j vj的顶点出现的条件概率最大化（这里使用到的是NLP中的SkipGram算法）。
第4步采用SGD（随机梯度下降）进行参数的迭代更新.
在计算 P r ( u k ∣ Φ ( v j ) ) P_r(u_k | \Phi(v_j)) Pr(uk∣Φ(vj))时，为了减少算法的时间复杂度，作者使用到的是Hierarchical Softmax（层次Softmax），这也是NLP中词向量用到的一个重要方法，这里不做过多阐述，如果感兴趣，可以阅读原论文4.2.2节。