DeepWalk: Online Learning of Social Representations（2014，Bryan Perozzi）

算法做什么的？

• 输入：一个 graph
• 输出：每个节点对应的向量

算法优点

• 信息缺失下表现良好
• 数据稀疏的情况下表现良好
• 可用于大规模计算（算法可以并行化）

social representations

我们想让 social representations 有这样的特点

• Adaptability：真实世界中，社交网络是不断演化的
• Community aware：向量距离，应当能代表网络成员的距离
• Low dimensional：向量应当是低纬的
• Continuous：值应当是连续的，如果这样，在此基础上的模型会更 robust。（例如分类模型会有一个稳定的分类平面）

1. Random Walks

在以往，Random walks，已经在对剑算法和社区检验中得到应用。
而且还有其它优点：

• 并行性。可以做多个 random walkers，在不同的线程、进程甚至机器上去跑。(in different threads, processes, or machines)
• 如果网络的少数节点改变，不需要全局重跑。

2. Connection: Power laws

如果度的分布服从 power law (is scale-free)，那么random walk 得到的节点，也服从 power law

然后下面这个图，说明社交网络和自然语言的相似性：The power-law distribution of vertices appearingin short random walks (a) follows a power-law, much like the distribution of words in natural language (b).

3. Language Modeling

算法就是类似 word2vec 的算法

\(\min -\log Pr(\{ v_{i-w},...,v_{i-1},v_{i+1},...,v_{i+w}\}\mid \Phi(v_i))\)

• 其中，$\Phi$是节点到向量的映射
• 顺序不重要。原文给出两个原因：有助于获取“距离近”的概念，增加速度。

文章在下文还写了一些细节，都是word2vec中的概念，不多讲。

• SkipGram
• Hierarchical Softmax

模型的变体

• decay learning rate 不再可能，不过有时候设置小一点儿还是值得的。
• 二叉树可以使 Huffman 树

  实验

• BlogCatalog：label是topic categories
• Flickr：这是个用户和照片分享网络，label是用户点了“喜欢”还是“不喜欢”
• YouTube：label是用户喜欢的流派

然后实验结果当然是很好啊（用labeled data验证，仅用20%数据，达到别的模型90%效果）