文章背景
题目：《DeepWalk:Online Learning of Social Representations》
来源：ACM SIGKDD2014
作者：Bryan Perozzi、Rami AI-Rfou、Steven Skiena
Abstract
- 动机：对网络中每个节点进行低维向量表示。
- 一句话概括思路：首先在节点之间进行有截断的随机游走获得节点序列，这时节点可以看作是单词，序列可以看作是句子；然后用NLP的方式对随机游走的输出进行训练，最终获得每个节点的低维向量表示。
因此对于该框架：输入是图，输出是每个节点的低维向量表示。 - 适用场景：多标签网络分类任务——BlogCatalog、Flickr、Youtube。文章说它还可以用于异常检测。
- 特点:
- 稀疏性: 针对稀疏场景，可以提升10%的F1；在一些实验中，DeepWalk仅适用60%的数据就超过了已有方法。
- 可扩展性：在线学习、增量学习、可并行化。
- 无监督。
1.Introduction
贡献点：
- 利用了深度学习(DL)对图进行表示。学习到了图的结构规律的表达。
- 效果：针对稀疏场景，可以提升10%的F1；在一些实验中，DeepWalk仅适用60%的数据就超过了已有方法。
- 并行性：算法是并行实现的。
3.Learning social representations
- 适应性：增量学习
- 低维向量之间的距离应该表示为两个节点的相似性，这样可以用于社团发现。
- 低维表示泛化能力更强，加速训练和预测。
- 低维向量表示是连续表示。因此对于社团之间的边界区分比较平滑，增强了分类的鲁棒性。
3.1 Random Walks
优势：
- 易于并行化：不同线程读入同一个图，但是异步可以输出不同的线路。
- 增量学习：图发生小变化时，只需要对改动区域进行随机游走即可，不必重新计算整个图。迭代地进行增量学习，最终即使整个图发生变化，训练也不受影响。
3.2 Connection: Power laws
- 一条没有被证明的结论：如果连通图的度分布遵循幂律（即无标度），我们观察到顶点出现在短随机游走中的频率也将遵循幂律分布。
我自己理解的幂律分布：多数词被提及的次数很少，很少的词被提及了很多次。 - 一条可能已经被证明了的贡献：因为NLP符合幂律分布，网络结构也符合幂律分布，因此适用于NLP的方法同样可以用于处理网络结构。
4.Method
4.1Overview
语料集：随机游走序列的集合。
单词表：节点集合。
4.2Algorithm
####4.2.1 skipgram
skipgram最大化了一个窗口中单词共现的概率。
####4.2.2 hierarchical softmax
文章真正使用的方法。
4.3Parallelizability
- 可以并行化的理由：低频词是稀疏的。
- 并行化方法：因此使用ASGD，多线程单机器。
- 效果：线性加速，模型效果基本不受到影响。
4.4Algorithm variants
两种：streaming和non-random walks
- streaming:不必看到整个图，局部图直接可以用来更新。
- non-random walks:有的网络不必使用random walk,直接利用本来的顺序更好，比如句子中本来是有顺序的，skipgram是可以利用到这种顺序信息的。
5.Experimental design
代码和数据都开源了。
介绍了数据集和baseline。
6.Experiments
6.1Multi-label classification
使用了one-vs-other logistic regression
6.2Parameter sensitivity
6.2.1Effect of dimensionality
- 最优维度d依赖于训练数据大小。
- 模型效果依赖于迭代次数(最少30次)。
6.2.2Effect of sampling frequency
开始迭代次数越高越好，后来增加迭代次数不能带来更明显的收益。
8.Conclusion
- 只利用局部信息，不必看到完整的图
适用于多标签分类任务 - 可输入更大规模的图
可并行化 - Deepwalk得到的结论反过来可以用于优化NLP
我自己的一些想法
- 4.2中提及随机游走的长度不必都相同(虽然实验中它是固定的)，那长度是否会影响训练效果呢，又如何判断什么时候结束随机游走？（路线：长度是否会影响训练效果—>如何选取每次的长度，即什么时候应该结束）
- 4.2中提及restart没有用，但好像node2vec中提及了这个作用，后续注意一下吧。
- word2vec中为什么窗口中单词的顺序不重要？
- deepwalk利用word2vec的skipgram和hierarchical softmax是否有区别？我猜应该有。
- deepwalk和word2vec的本质目的到底是否相同？deepwalk是探寻节点之间的相似性，用于社团发现。word2vec是去寻找近义词或者反义词。如果是这样的话，两个方法之间还是有一点不同的呀！
- 4.3中我承认
的分布是稀疏的，但是
也是稀疏的吗？为什么可以同时使用无锁更新？