DeepWalk的输入是一张图或者网络，输出为网络中顶点的向量表示。DeepWalk通过截断随机游走(truncated random walk)学习出一个网络的社会表示(social representation)

image.png

前提假设

随机游走的分布规律与NLP中句子序列在语料库中出现的规律有着类似的幂律分布特征。那么既然网络的特性与自然语言处理中的特性十分类似，那么就可以将NLP中词向量的模型用在网络表示中。

image.png

优化目标

image.png
image.png
image.png

• 映射函数选取

image.png

忽视顶点顺序，更好地表达顶点临近关系，只需要计算一个顶点的向量。

skip-gram

image.png

Hierarchical Softmax解决迭代计算量庞大的问题。
Huffman编码是一种熵编码方式，对于出现频率高的符号用较短的编码表示，出现频率较低的符号用较长的编码表示，从而达到编码压缩的目的。Hierarchical Softmax树也可以采用Huffman编码的方式生成，高频词用较短的路径到达，低频词用较长的路径到达，可以进一步降低整个训练过程的计算量。

image.png

伪代码

image.png

截断随机游走

image.png

随机游走长度固定。根结点vi，随机路径Wvi。

注意的点

• 适应性，网络表示必须能适应网络的变化。
  网络是一个动态的图，不断地会有新的节点和边添加进来，网络表示需要适应网络的正常演化。
• 属于同一个社区的节点有着类似的表示。网络中往往会出现一些特征相似的点构成的团状结构，这些节点表示成向量后必须相似。
• 低维。
  代表每个顶点的向量维数不能过高，过高会有过拟合的风险，对网络中有缺失数据的情况处理能力较差。
• 连续性。
  低维的向量应该是连续的。

参考

w2v: https://www.jianshu.com/p/3217e8c00549
文献：https://arxiv.org/pdf/1403.6652.pdf
https://zhuanlan.zhihu.com/p/45167021
slide：http://www.perozzi.net/publications/14_kdd_deepwalk-slides.pdf