关于DeepWalk、LINE、node2vec的总结

背景

1. 动机：将图中的节点以低维向量进行表示。这些向量可以作为其他算法的输入特征进行训练。
2. 方法：通过在图中进行采样得到多个“节点序列”，该序列类似于NLP中的句子，因此可以使用NLP中的技术对节点进行embedding训练。
3. 应用：多标签分类任务、异常检测、语言网络、社交网络、引用网络、链接预测任务。
4. 优势：模型效果好、对内存开销要求小、更加适应稀疏数据、可并行化、可增量学习。
5. 相关工作：
   • 科研方面：之前已经有了很多论文，但是大多是基于python的demo(使用多线程进行训练),清华大学刘知远的团队也集成了工具包。但目前没有看到真正的分布式实现，在真实场景中，由于图规模巨大(e.g.社交网络)，需要分布式训练。
   • 工业界：2017年阿里凑单算法公布了其Graph Embedding细节。2018.6月Tencent-Angel在Spark on Angel上实现了LINE算法，千亿级网络。
6. 相关综述资料：1 2
7. 对象：本次主要对DeepWalk(2014)、LINE(2015)、node2vec(2016)进行简述，这三篇文章是递进关系,时间较早并且思想比较简单，各自的细节描述见其他三个PDF文件。

具体方法

1. DeepWalk：总体分为两个步骤，首先通过随机游走得到节点序列，然后使用word2vec进行训练。
2. LINE: 设计了新的边采样方法和损失函数。首先采样图中的边，然后使用每一个边对模型参数进行更新。
3. node2vec：基于DeepWalk，只是设计了灵活的随机游走策略(DFS和BFS结合)。

对比

1. 适用范围：DeepWalk只适用无向、无权重的图；LINE和node2vec适用任意类型的图。
2. 模型效果：按照论文的说法，三个模型呈递进关系。
3. 网络规模：DeepWalk(百万的点和百万的边)；LINE(百万的点和十亿的边)；node2vec(百万的点，每个点平均出度为10，它使用的数据集比较小)。

实现

1. 框架：
   • 基于Tencent-wuliang(C++、PS)进行实现。
   • 三种方法实现步骤类似：对图进行采样，使用word2vec进行训练。因此初步计划首先实现DeepWalk，然后逐步优化为LINE和node2vec。
   • 后续计划设计一个通用的Network Embedding框架,类似于OpenNE。
2. 实现步骤：
   • 为方便调试，首先实现word2vec。PS框架下word2vec对网络开销大，Yahoo2016论文专门针对PS架构设计了新的word2vec训练方法。
   • 实现随机游走策略。
   • 公开数据集评测，Tencent内部数据集评测。
   • 预计时间：一个月(2018.10.10)