介绍
图神经网络的开山之作
DeepWalk：一种用于学习网络中顶点的潜在表示的新方法，使用随机行走中获得的局部信息，通过将序列视为句子，节点视为单词
通过随机游走可以采样出一个序列，序列好比一句话，节点好比一个单词。
随机游走的假设是类似word2vec的，假设相邻单词应该相似。于是可以构造skip-gram问题，输入中心节点，预测周围邻近节点。这样就能完全套用word2vec。
Cool idea：随机游走=句子优势：
可扩展，可以使用自然语言模型，处理稀疏标注的图效果很好
目标：
Adaptability，Community aware，Low dimensional，Continous
1、灵活可变，适应能力强。这是因为图网络往往伴随着动态变化，如果我们对当前时刻训练出来的词嵌入模型只能对当前时刻有效，那么无时无刻更新的网络就没办法进行词嵌入编码了。因此，首先这个编码过程必须是一个训练好一个模型，然后来新的，就在旧模型基础上更新，无需对整张图进行重新学习。
2、社群信息，反应聚类关系。这点其实就和Fig1对应，即embedding出来的节点向量把他映射到空间部分时应该保持和原图网络相类似的空间信息。
3、低维度。由于他训练出来的是一个稠密的矩阵，即每一个数值都有一定的客观意义，因此如果维度过高，则会过量抽取图节点信息，低维度是为了避免过拟合。
4、连续。这一点说明embedding出来的节点向量在空间的分布应该有一个平滑的决策边界，我们进一步去说，应该是一个非凸、低维、平滑的决策边界。关于凹凸性，数学证明的过程非常繁琐，在数学推论部分会补充这部分的推论，这里直接说结论，凸函数是只要沿着梯度方向走到底，就一定是最优解，大部分传统机器学习的问题都是凸函数；非凸更符合实际的情况，意味着沿着梯度方向走到底，只能说明是局部最优，不一定是全局最优，大部分深度学习都是非凸。这里我想要强调非凸主要是给后续讲到图深度学习埋下一个伏笔。
实例：
DeepWalk
随机游走
首先选择一个点，然后随机选择它的邻接节点，移动一步之后，再次选择移动后所在节点的邻接节点进行移动，重复这个过程。记录经过的节点，就构成了一个随机游走序列。
Question：为什么要随机游走？
Answer：一个网络图实际上可能是非常庞大的，通过无穷次采样的随机游走（实际上不可能无穷次），就可以”管中窥豹，可见一斑“。从无数个局部信息捕捉到整张图的信息。
Random Walk的假设和Word2Vec的假设保持一致，即当前节点应该是和周围节点存在联系。所以可以构造一个Word2Vec的skip-gram问题。
幂律分布
幂律分布广泛存在于自然界和社会生活中，如网络科学、地球与行星科学、物理学等领域。它通常与不平均性、无标度现象相关，例如帕累托法则（或二八定律）所描述的那样，即少部分原因、人群或资源集中大部分的效果。在现实生活中，这种分布可以体现在财富分配、城市规模、互联网网络的连接度等方面。
语言模型
在NLP领域，有一个现象，称为“word frequency”：有一些词出现的特别频繁，有一些不频繁。
在图里，特别是无标度图网络里，也有类似的现象：“Vertex frequency”：有一些网站被访问的特别频繁，有一些不频繁。
举个具体的例子，假如这是一个门户网站的图，那么Google，baidu等是不是拥有绝大多数的访问量，一些小网站则鲜有访问。在文本中也是一样的道理，例如a the and这类词，他们出现的频率会远远大于power-law这种词汇。正是节点和文本有这种相似性，因此把NLP的编码思路套用在图编码中是存在可行性的。
实现过程
Step1: 输入一个图
Step2: 采样一个随机游走序列
Step3: 训练Node2Vec模型（构造skip-gram任务）
Step4: 霍夫曼编码（一种softmax方式，解决分类过多的问题，一种工程trick，并不算DeepWalk的理论核心）
Step5: 得到最终每个节点的图嵌入向量
伪代码
