参考知乎： node2vec
原文链接： node2vec: Scalable Feature Learning for Networks
复现代码见： Colab
Introduction
复杂网络主要有两种任务，一网络节点的分类，通俗点说就是将网络中的节点进行聚类，我们关心的是哪些节点具有类似的属性，就将其分到同一个类别中。二是链接预测，就是预测网络中哪些顶点有潜在的关联。
前面的DeepWalk借鉴了词嵌入模型skip-gram的思想，node2vec也是如此，最重要的不同就是在游走的方式上有了改进，在得到序列后的处理方式和DeepWalk是一致的。下面主要探讨的就是这样的序列是怎样得到的，又是怎么有利于网络嵌入的。
模型
目标函数
原文中介绍了对于优化目标函数的推导，和skipgram中的思想是类似的，首先要尽可能使得节点与周围邻居节点同时出现的概率尽可能大，也就是最大化下函数（其中
表示从节点
映射到嵌入向量，
表示
的邻居节点）：
同时假设观察一个邻居节点的概率独立于观察其他邻居节点的概率，这样就有：
综合起来所有节点后，优化的目标函数就为：
这和skipgram中介绍的有很大的相似性，且
的计算量太大，故也是采用负采样的方法，这也是为什么说这篇论文也借鉴了skipgram的思想。其创新点主要在下面要讲的游走方式上。这样创新的游走方式能够捕捉到网络连接的多样性。
游走方式
在学习了前面的LINE模型后，会有这样一种感觉，图中的节点信息主要蕴含两种，一种是同质性信息，一种是结构相似性的信息。第一种很好理解，就是聚集在一个社群之中的节点之间有着相似的特征，因此在向量表示中也就更加贴近，而第二种就好像下图中的u节点和s6节点，都是各自社群的中心，理应具有某种程度上的相似的向量表示信息。
图的游走方式有两种，深度优先DFS和广度优先BFS，学习得到的向量表示也就更能蕴含节点的同质性和结构相似性特征，这其实也和LINE中的一阶二阶相似性有异曲同工的感觉。BFS倾向于在初始节点的周围游走，可以反映出一个节点的邻居的微观特性；而DFS一般会跑的离初始节点越来越远，可以反映出一个节点邻居的宏观特性。具体为什么这样两种游走方式可以得到这样的效果可以参考
node2vec添加了p和q两个参数，来控制游走的方式。
具体来说，如图所示，当前节点是v，是由t节点走来，并在每条与v直接相连的边上定义了往四个方向的跳转概率（也即右边的公式）。
对于参数p
- 如果
也即
，那么采样会尽量不往回走，对应上图的情况，就是下一个节点不太可能是上一个访问的节点t，而应当是其他的x123节点。 - 如果
也即
，那么采样会更倾向于返回上一个节点，这样就会一直在起始点周围某些节点来回转来转去。
对于参数q
- 如果
也即
，也就是说在x1和x23之间选择更倾向于选择x1，x1所代表的时节点t周围的节点，也就是说游走会倾向于在起始点周围的节点之间跑，可以反映出一个节点的BFS特性。 - 如果
也即
，也就是说在x1和x23之间选择更倾向于选择x23，那么游走会倾向于往远处跑，反映出DFS特性
当p=1，q=1时，游走方式就等同于DeepWalk中的随机游走。
代码复现
node2vec论文源码中主要包含了main.py和node2vec.py，下图是对整个架构的概括：
伪代码：
LearnFeatures需要传入图G，每个节点向量表示的维度d，每个节点要生成r条walk，每条walk长度为l，窗口大小k（类似于word2vec中的上下文窗口大小），参数p和q。
根据图G（节点，边，权重）和参数p，q生成一个Π，Π中存的是图中每个节点以及对应的下一节点概率，将该信息加在原图G上，形成一个新图G'。
接下来，迭代r此，并调用node2vecWalk对每个节点生成一个长度为l的walk（形成walk时要借助G'来决定怎么找到下一个节点），形成的r×|V|个walk整合成一个walks序列，将其输入到类似于w2v中，输出一个矩阵，即我们需要的矩阵。
node2vecWalk，需要输入带有G'信息的图，需要生成walk的节点u，需要生成的walk的长度l。
walk的list第一个是u，接下来迭代l词，每次迭代都先将walk的最后一个元素作为当前节点curr，再得到当前节点curr的周围节点以及对应的概率信息，得到最大的一个概率对应的下一个节点，将节点添加到walk并进行下一次迭代。
具体的复现：
（参考Github）
复现效果
micro-F1
（文中图，最上面的是node2vec）
使用0.9的数据集BlogCatalog得到的Micro-F1=0.4009
可视化
使用数据量较小的wiki数据集可视化效果：（代码见：Colab）
已经可以看到部分颜色的点有明显的聚集现象。（可视化以及micro-F1的方法在deepwalk中已经介绍）
其他问题
如果是带权图：
需要采用alias_table的方法，在采样节点的时候，需要采用此方法来既考虑到边权的影响，又不至于耗费太大内存，这部分在前面学习LINE的时候已经有所说明。别名采样。应用到这里的时候，则需要先对所有的边进行一轮别名采样，将采样完成后的图再输入到模型中，此时输入的图应当视为无权无向图。
