深度学习-GNN（3）node2vec
Node2Vec
【Graph Embedding】node2vec：算法原理，实现和应用 - 浅梦的文章 - 知乎 https://zhuanlan.zhihu.com/p/56542707
DeepWalk的思路非常直接，就是结合随机游走和Skip-gram模型。尽管DeepWalk利用完全随机的游走，得到了相对小的游走时的时空复杂度，==但是这种游走的策略显然没有考虑到图中节点间的连接"强度"，同时也无法很好的考虑到图中节点的结构等价性(structural equivalence)和同质性(homophily)，生成的游走序列完全"听天由命"==。
Node2Vec[2]是一篇16年文章，它修改了DeepWalk中的游走策略，使其能够更灵活的捕捉图中节点的结构等价性和同质性。
2.1 Overview of the Model
二阶随机游走（二阶马尔科夫）
具体来说，如上图，我们可以说节点s1和节点u具有同质性，因为它们都属于图中同一个community/cluster；我们也会说节点u和节点s6具有结构等价性，因为它们在网络中扮演的角色十分类似，都是簇的中心。
Node2Vec的作者们宣称：
- 倘若随机游走倾向于BFS，那么生成的序列会更倾向于在起点的附近进行探索，这样能够更好的捕捉节点间的同质性；
- 若随机游走倾向于DFS，那么生成的序列会探索图中更大的区域，使得模型有机会捕捉到节点间的结构相似性。
以上陈述中，BFS能更好的捕捉同质性应该是比较直观的，毕竟它只会在起点附近震荡，也就意味着它能确保与起点近邻的节点均能习得近似的表达。但是DFS只是捕捉节点间结构等价性的必要条件而非充分条件。如果没有DFS，模型可能根本无法跳出起点的簇中，那么节点的结构等价性的捕捉也无从谈起。但是如果只是DFS，那么我们只能知道这两个距离很远的节点有某种依赖性，但我们无从得知这是怎样的依赖性，比如，它们都是簇的中心吗？还是它们都是各个簇的成员而已？
因此作者们提出了一个biased 2nd order random walk，其引入了两个额外的参数p和q，以在游走中控制和融合BFS与DFS。这个游走被称作二阶随机游走的原因是：游走的下一步不仅取决于当前的节点，也取决于当前节点的上一步的节点。这和二阶马科夫假设是类似的。
具体来说，上图为游走的一个例子。其中，节点v是当前节点，节点t是游走的上一步的节点，而我们现在要决定节点v的下一步x是哪一个节点。此时的游走概率由α决定，其公式为：
- 其中dtx指节点x与节点t之间的距离。有了α后，游走的（未经归一化的）转移概率可计算为\(π_{vx}=α_{pq}(t,x)⋅w_{vx}\)，其中\(w_{vx}\)是节点v与节点x之间的权重。
- 直观来说，若p越大，越不容易返回上一步游走到的节点，这能鼓励模型游走的更远，若p越小，则更容易返回上一步节点，使得模型倾向于在起点周围进行探索；若q越大，游走会更倾向于在上一步节点t的周围进行探索，若q越小，游走会更倾向于探索距离上一步节点t更远的节点。在p和q之间trade off，可以控制随机游走的倾向性，从而达到更好的效果。特别的，当p=q=1时，Node2Vec等价于DeepWalk。
Node2Vec中提出的随机游走，若结合Alias Sampling策略，在额外引入O(2|E|)的时空复杂度后，也可以在O(1)内完成一步游走的采样，因此整个游走的复杂度是 \(O(lk|V|+2|E|)\)。基本上这就是Node2Vec这篇文章的核心了，后续同DeepWalk一样基于采样得到的序列训练Skip-gram模型即可。
2.2 Alias Sampling
4. Summary
DeepWalk和Node2Vec的思路都非常简单直接，也能取得可观的效果。它们与那些矩阵分解算法在同一时期被提出，但由于基于随机游走的算法有着更好的可扩展性，并且也能更好的泛化到新节点上，DeepWalk和Node2Vec远远比GraRep、HOPE这些模型流行的多。
但是，随着GCN的出现，无法共享参数的这些基于随机游走的模型也渐渐不再火热，如今的图机器学习领域已将重点放在了图神经网络的研究之中。
总体来说，DeepWalk和Node2Vec这类模型的优点有：
- 相比于矩阵分解模型来说，可扩展性更强
- 虽然本身不是inductive的，但也能很容易的在训练中加入新的节点
该类模型的局限性有：
- 随机游走的代价事实上是极大的
- Embedding lookup矩阵后直接跟损失函数，模型表达能力有限、节点间无参数共享
- 无法对k阶邻居进行区分，只能知道两两节点是否在同一个窗口中出现过，这样事实上丢失了图中部分拓扑信息，可能导致模型效果受限;
- 无法直接利用节点的特征
- Transductive
