Deepwalk: Online learning of social representations

[eleveyuan]

reference:

1. Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014: 701-710.

[eleveyuan]

Deep Walk是一种graph embedding 的方法，通过truncated random walk的方式对graph学习到向量空间中节点的向量表示。首次将deep learning引入节点表示学习，并使用无监督的方式进行学习。

论文中提到Deep Walk主要结合random walk和语言模型，来指导算法学习

简而言之，懂了语言模型就可以很快的了解deepwalk模型了

[eleveyuan]

random walk

被广泛的应用于内容推荐，社区探测(相似度计算)以及output sensitive(以计算局部社区结构信息)

random walk被应用的优势：

局部的random walk可以被并行化 局部的短的random walk，可以规避graph在发生修改时，更好的适应。

[eleveyuan]

Language model

语言模型的目标就是通过已知词语去预测下一个词语，也即，预测一个最大后验概率。论文注意到类似于word2vec的概率神经网络去学习词的向量表征。论文则是通过泛化语言模型应用到random walk上，即，

其中w为词，v为图上的节点 作者不仅仅需要模型学习到节点之间同时发生的分布，而且还要学习潜在的表示（个人理解：考虑到节点之间不同于词与词之间一样带有时序性质。），引入了一个映射函数：

同时作者发现语言模型中使用一个单词去预测其上下文(skip-gram模型)，可以很好地应用至节点预测中，消除节点顺序的关系，所以优化目标也可以很好地给出来了，同时作者发现消除顺序可以更好的捕捉节点之间的关系以及加快训练速度:

[eleveyuan]

那么联系语言模型与图节点嵌入呢？

作者发现short random walk和语言模型一样具有相同的幂律分布。如下图：

[eleveyuan]

算法思想比较简单，就是先使用均匀分布采样root节点，然后用均匀分布取采样后续节点， 然后对节点进行embedding，也即 Φ ，然后使用word2vec中的skip-gram模型一样进行训练。由于模型涉及的计算量比较大，所以作者使用了word2vec中用的hierarchical-softmax进行加速。 算法在其第二步就构建了节点二分树。