深度学习-GNN（2）DeepWalk
- DeepWalk【图神经网络论文精读】：https://www.bilibili.com/video/BV1o94y197vf/?spm_id_from=pageDriver&vd_source=29387dc08d18f642078183a6816e93e8
- https://www.zhihu.com/column/c_1322582255018184704
- 图神经网络—基于随机游走的早期研究（一）：DeepWalk & Node2Vec：https://zhuanlan.zhihu.com/p/343041065
一、DeepWalk
DeepWalk[1]是一篇14年的文章，它极大的受到word2vec[4]的启发。
在图机器学习的早期研究中，人们主要希望模型能够捕捉到节点之间的连接关系。那在word2vec中人们希望模型学习的是什么呢？没错，就是token与token之间的"连接性"。word2vec的skip-gram (with negative sampling) 模型本质上在回答：给定两个token，它们是否有在同一个context window中出现过？从图的角度来说，word2vec的任务目标可以翻译为：给定两个节点，判断它们是否有任意k阶内的连接关系，其中k即为context window的大小。
因此，一个自然的想法就是，能不能利用word2vec训练模型，来捕捉图数据结构中节点之间的连接关系呢？出于此intuition，研究者们提出了DeepWalk。
1.1 Overview of the Model
DeepWalk非常简单粗暴，它基本上就是以下两个模块的结合，甚至各个模块都没有太大的改动：
- 基于随机游走在图上进行游走采样，将节点邻接结构映射成序列结构。
- 利用采样得到的序列，训练Skip-gram模型，使习得的表达能够捕捉节点间的连接性。
第一部分：原论文提出在进行随机游走时，每次从给定起点出发，不停的利用uniform sampling来采样邻居进行游走，直到该采样序列长度达到给定最大长度。因为每步游走仅需做一次uniform sampling，所以DeepWalk可以在不需要额外存储计算的情况下，在O(1)的时间内采样一步随机游走。
假设给定模型l的walk length，并且以每个节点为起点进行k次游走，那么总计会生成k|V|个长度为l的序列。最终完成整张图的随机游走的时间复杂度为O(lk|V|)。
第二部分：原论文提出基于Hierarchical Softmax (HS) 来训练一个Skip-gram模型。但从今天的眼光来看，HS已经逐步退出历史的舞台。人们现在往往直接在GPU上计算softmax，并不再特别需要HS加速softmax计算。并且，若softmax计算量难以接受，人们也往往利用Noise Contractive Estimation (NCE) or Negative Sampling (NS)，来规避softmax的使用。因此，今天人们更常利用skip-gram with negative sampling训练DeepWalk/Node2Vec模型。
