Deepwalk

random wlak：就是在网络上不断重复地随机选择游走路径，最终形成一条贯穿网络的路径。从某个特定的端点开始，游走的每一步都从与当前节点相连的边中随机选择一条，沿着选定的边移动到下一个顶点，不断重复这个过程。截断随机游走(truncated random walk)实际上就是长度固定的随机游走，如下图中的绿色路径即为一条random walk

random walk
random wlak的两个优点：

1. Parallelize: Several random walkers can simultaneously explore different parts of the same graph.
2. Adaptable: Accommodate small changes in the graph structure without the need for global recomputation.

顶点出现在short random walk中的频率分布和word出现在句子中的频率分布有着类似的幂律分布，因此将nlp中的模型重用于社交网络图。

幂律分布
于是我们可以做如下类比

将单词对应成网络中的节点vi ，句子序列对应成网络的随机游走(v0, v1, …, vi)，那么对于一个随机游走 ，要优化的目标就是Pr，也就是当知道(v0, v1, …, vi-1)游走路径后，游走的下一个节点是vi的概率是多少；

但是顶点本身是不可计算的，所以引入映射函数，将顶点映射成向量（这其实就是我们要求的），转化成向量后就可以对顶点vi进行计算了，这个参数就是我们要学习的 Graph Embedding

此时优化函数就为

然后借用词向量中的模型来计算这个概率即（理解：在一个随机游走中，当给定一个顶点vi时，出现在它的w窗口范围内顶点的概率）


往下直接用skip-gram模型来训练：输入是一个V维的向量，其中只有一个是1，其余都是0(one-hot encoder), 所以隐藏层输出只需要copy 参数矩阵W的第k行即可，最大的问题在于从隐藏层到输出的softmax层的计算量很大(分母要把所有单词加起来)，因此用 Hierarchical Softmax