论文笔记----node2vec: Scalable Feature Learning for Networks（可扩展的网络特性学习）
论文链接
论文链接：https://arxiv.org/pdf/1607.00653.pdf
简介
- node2vec的思想同DeepWalk一样：生成随机游走，对随机游走采样得到（节点，上下文）的组合，然后用处理词向量的方法对这样的组合建模得到网络节点的表示。不过在生成随机游走过程中做了一些创新。
论文为node2vec: Scalable Feature Learning for Networks（可扩展的网络特性学习），是为了解决目前的特征学习方法不足以表达网络中观察到的连接模式的多样性的问题。
在node2vec中描述了一种将节点映射到低维特征空间的方法（半监督），这种方法可以最大限度地保留节点的网络邻域。论文定义了一个灵活的节点网络邻域概念，并设计了一个有效地探索不同邻域的有偏随机游走过程。
- 首先介绍了复杂网络面对的几种任务：
一种是网络节点的分类，通俗点说就是将网络中的节点进行聚类，我们关心的是哪些节点具有类似的属性，就将其分到同一个类别中。另一种是链接预测，就是预测网络中哪些顶点有潜在的关联。
要学习网络特征，一种学习特征表达的方法是通过定义目标函数然后解决优化问题（相当于优化目标函数）。本文尝试解决的工作：设计出又能保持节点邻居信息而且又容易训练的模型。
- 一个灵活的节点表示学习算法需要具备两个条件：
- 能够将相同网络社区的节点映射到相近的位置；
- 对于扮演相似角色的节点有相似的映射方式；
本篇文章的四个主要贡献：
- 提出node2vec算法，基于邻居留存的特征学习优化算法，使用SGD，计算高效，拓展性强；
- 展示了node2vec符合网络科学的原则；
- 基于邻居留存目标，拓展了node2vec和其他的特征学习方法，从节点到节点对；
- 在真实数据集上测试了node2vec进行多分类和连接预测的性能；
两个预测任务：
1.多标记的分类任务：每个结点有一个或多个标签；
2.连接的预测(link prediction)任务：给定一组结点，预测是否有边存在。
Node2vec使用Skip-Gram模型来解决网络表示学习问题（与DeepWalk类似的）。这些架构使用若干层非线性转换，直接将下游预测任务的损失函数最小化，从而获得高精度，但由于训练时间要求较高，因此需要以牺牲可扩展性为代价。
算法
文章将网络中的特征学习表述为一个极大似然优化问题。
设f->Rd为结点到特征表示的映射函数，这里的d为特征表示的维度，f是一个大小为|V|×d的矩阵，目标函数为：
- 为了让优化问题易于求解，给出了两个标准的假设：
1.条件独立性：假设给定了一个源结点的特征表达后，发现一个该原点的邻居与发现该邻居结点的其他结点的概率相互独立；所以目标函数中的NS(u)是源节点u的邻居结点；
2.特征空间对称性：一个源结点与它的邻居结点再特征空间内有对称性，定义每一对源结点与其邻居结点的条件概率作为一个softmax单元，且用它们的特征进行参数化。
一般网络结点的预测任务会有两种状态：
1.同质性(homophily)：处于高度连通状态，属于相似的网络聚类或紧密嵌入；
2.结构等价性(structural equivalence)：不强调连通性，但有相同的结构角色；这两种状态并不是排他性的，网络经常同时表现出这两种行为，其中一些表现出同质性，另一些表现出结构等价性。
文章分析了两种图的遍历方式：深度优先搜索(DFS)和广度优先搜索(BFS)；其中DFS倾向于在一条搜索路径上越走越远，可以反映出一个结点邻居的宏观特性；BFS倾向于在初始结点走位游走，可以反映出一个结点的邻居的微观特性。
- 本文设计了一种随机游走方式，改进了DeepWalk中的随机游走的方式，且使它综合了DFS和BFS的特性。
随机游走
给定一个源节点u，随机游走的固定长度l,ci为随机游走中的第i个节点，起点为c0=u，节点ci由以下分别产生，其中πuv是结点u和v之间的转移概率，Z为归一化常数：
对于随机游走，一般的做法是直接用边的权重来转化成概率，本文作者在权重之前乘上一个系数α，从而在一定程度上调节随机游走的走向。
在本文的随机游走中，作者定义了p和q两个参数变量来调节游走，假设游走路径已从t->v，现在游走到节点v，首先计算其邻居节点xi与上一节点t的距离d，从而得到α:
也就是说：
1.若t与x相等，则α=1/p；
2.若t与x相连，则α=1；
3.若t与x不相连，则α=1/q；
通过调节参数p和q，可以控制随机游走的方向，两个极端的方向就是BFS和DFS；
- 其中参数p和q的意义及设定为：
-
返回参数p：
1.若p > max(q,1)，那么接下来的两次采样大概率不会访问已经访问过的节点，除非遍历中的下一个节点没有其他邻居（避免采样中的2-跳冗余）；
2.若p < min(q,1)，那么接下来的采样会更倾向于返回上一个节点，这样会一直在起始点走位转来转去； -
出入参数q：
1.若q > 1，那么游走会倾向于起始点周围游走，类似于BFS；
2.若q < 1，那么游走hi更倾向于往远处游走，类似于DFS；
当p=1，q=1时，这里的游走方式就等同于DeepWalk中的随机游走。
这里的随机游走与纯BFS/DFS有几个好处：就空间和时间要求而言，随机游走的计算效率比较高。
算法伪代码：
现按照步骤来进行说明解释：
-
LearnFeatures参数：图G、表示向量维度d、每个节点生成的游走个数r，游走长度l，上下文的窗口长度k，以及之前提到的p、q参数。
1.得到πuv，即结点u和v之间的转移概率；
2.将这个概率修改原图G中的权重W，得到G’；
3.将存储随机游走的Walks初始化为空；
4.外循环中r表示每个节点作为初始节点都要循环r次，生成r个随机游走；
5.内循环图G中的每一个结点；
6.调用node2vecWalk生成一条随机游走walk；
7.将新生成的walk加入walks；
8.用StochasticGradientDescent(k, d, walks)对walks、k、l进行训练从而优化目标函数f。（随机梯度下降） -
node2vecWalk参数：修改后的图G’，初始节点u，随机游走长度l。
1.将初始结点u添加进入随机游走路径；
2.随机游走walk的长度为l，循环添加剩下的l-1个结点进去；
3.将当前遍历到的节点设为walk最后添加的节点；（？）
4.找出当前结点的所有邻居节点；
5.根据上面提及的偏移概率取样选择某个邻居节点s;
6.将s加入随机游走walk；
7.循环结束后返回得到的随机游走walk。 -
总结下来就是三个阶段：
1.预处理时，转移概率的计算，也就是π的获取；
2.随机游走的执行；
3.通过随机梯度下降（SGD）优化目标函数。
Node2vec是一种半监督的学习方法，它将单个结点的特征表达预测拓展为一对结点的特征表达；比如在链路预测中，我们对两个结点之间是否存在一条链路。
实验
- 文献将node2vec与下列算法进行比较：
1.谱聚类（Spectral clustering）：这是一种矩阵分解方法，我们选择top d个图的标准Laplacian矩阵作为结点的特征向量。
2.深度游走（DeepWalk）：可视为当node2vec算法选择p=1,q=1时的情况，也就是一种均匀随机游走的情况。
3.LINE：分为两个阶段学习一个d维的特征表达。第一阶段：通过BFS获得直接相连的邻居结点，学到d/2维；第二阶段：获取与源结点2跳距离的结（2-hop），学到接下来的d/2维。
随后进行了多标签分类的实验，每个结点由一个或多个标签组成，该任务时为了预测剩余结点的标签。对BlogCatelog、Protein-Protein Interaction(PPI)及Wikipedia数据集进行了实验。
其他的实验不做赘述。