六、Node2Vec

1. feature learning 的挑战是如何定义恰当的目标函数，这涉及计算效率和预测准确率之间的平衡。

   • 一方面可以直接优化下游监督任务的目标函数。

     • 优点：预测准确率高。
     • 缺点：需要估计的参数数量激增，训练时间复杂度较高；且学到的feature representation 是任务相关的，无法广泛应用于其它类型的任务。

   • 另一方面可以精心设计独立于下游监督任务的目标函数。

     • 优点：计算效率较高；且feature representation 是任务无关的，可以广泛应用于下游各种类型的任务。
     • 缺点：应用于下游监督学习任务时预测准确率稍低。

2. 当前的模型和方法无法为无监督学习 graph feature learning 定义一个合理目标函数。

   • 基于线性和非线性的经典无监督学习算法，如 PCA,MDS,IsoMap 及其扩展算法，它们最大化的目标函数为：原始数据在低维空间representation 的方差。

     这些算法具有两个主要缺点：

     • 算法涉及矩阵的特征分解，这对于大型Graph 代价太大，因此可扩展性很差。

     • 这些算法的目标函数隐含着对 Graph 结构的各种假设，如同质性 homophily 或者结构对等性 structural equivalence ，这些假设不一定适合各种类型的 Graph 。

       例如谱聚类的目标函数就有很强的同质假设：图的割cut 有助于分类。该假设在很多场景下是合理的，但是无法推广到所有的 Graph 。

   • 基于邻域关系的无监督学习算法，如 DeepWalk, LINE 及其扩展算法，它们最大化的目标函数为：尽可能在低维空间中保留原始空间中的顶点邻域关系 neighborhood ，即在低维空间中尽可能相似。

     不同的采样策略将导致不同的邻域关系，因此学到不同的顶点表达。实际上并没有一个明确的、更好的采样策略使得采样到的领域关系适合所有网络以及所有任务。这也是 DeepWalk,LINE 等工作的主要缺点：无法为采样过程提供任何的灵活性。

     如下图中顶点 和顶点 都属于同一个社区 community ，根据 DeepWalk,LINE 算法这两个顶点是相似的。

     事实上顶点 和顶点 虽然属于不同的社区，但是它们属于网络的同一种特殊连接模式，可以认为它们也是 ”相邻“的，因此它们也是相似的。

     因此必须要有一个灵活的算法来学到两种规则的顶点 representation，从而使得算法能够学到泛化能力更强的特征表达：

     • 将来自同一个社区的顶点映射的低维embedding 向量尽可能相似。
     • 将来自同一类特殊连接模式的顶点映射的低维embedding 向量尽可能相似。

     

3. 论文 《node2vec: Scalable Feature Learning for Networks》 提出了 node2vec 模型，该模型的目标函数也是：尽可能在低维空间中保留原始空间中的顶点邻域关系 neighborhood 。但是 node2vec 重新定义了邻居这一概念，认为灵活地探索顶点领居是学习更加丰富的顶点表达的关键。

   node2vec 通过一个有偏随机游走过程biased random walk procedure 来探索各种类型的邻居，从而能够灵活的根据顶点所属的社区或者顶点在网络中的角色来学习顶点表达。

   node2vec 是 DeepWalk,LINE 等算法的进一步扩展。与 DeepWalk,LINE 等死板的搜索方法相比，node2vec 可以通过调节超参数来控制搜索空间，从而产生更加灵活的算法。该超参数具有直观的解释，并决定了不同不同的搜索策略。

   • 在多标签分类任务中node2vec 优于最新的方法最高达 26.7%；在链接预测任务中 node2vec 优于最新的方法最高达 12.6% 。
   • 在计算效率上 node2vec 主要计算阶段很容易并行化，可以在几个小时内计算扩展到数百万个结点的大型网络。
4. node2vec 还将单个顶点的表达扩展到成对顶点的表达，即边的表达，使得node2vec 能够同时进行基于顶点的预测任务、基于边的预测任务。

6.1 模型

1. 给定网络 ，node2vec 的目标是学习映射 ，该映射将每个顶点 映射到低维空间表达 ，该低维空间表达用于下游任务，其中 。

   这里图 可以是有向图也可以是无向图，可以是无权图也可以是带权图。

   对于每个顶点 定义其基于采样策略 的网络邻居 network neighborhood 为 。类似 SkipGram，node2vec 的优化目标是：给定顶点 ，在低维空间中最大化其邻居 的对数似然函数。即：

   

   其中 。

   为求解该最优化问题，node2vec 做了两个关键假设：

   • 条件独立性：给定顶点 ，对于其邻居 内的任意两个顶点 ，假设 成为 的邻居和 成为 的邻居无关。即有：

     

   • 空间对称性：给定顶点 ，它作为源顶点和作为邻居顶点时共享同一个 embedding 向量。因此可以通过 softmax 函数来建模条件概率：

     

   因此node2vec 的目标函数为：

   

   其中 。

   对于大型网络 的计算代价很高，因此通常采用负采样策略。

2. SkipGram 架构是基于 NLP 开发的，由于文本的线性特点 SkipGram 可以直接基于文本上的连续滑动窗口来自然的得到单词 的邻居 。

   但是网络不是线性的，因此难以直接定义邻居。为解决该问题，node2vec 给出了一个随机采样过程，该过程对顶点 的许多不同类型的相关顶点进行采样得到邻居 。邻居中不仅包含直接相连的顶点，还包括那些根据采样策略 得到的不相邻的、结构类似的顶点。

   因此采样策略 决定了顶点 的邻居集合。为公平比较不同的采样策略，这里限制每个顶点的邻居集合大小不超过 。

   有两种极端的采样策略：

   • 广度优先采样策略 Breadth-first Sampling:BFS ：顶点 的邻居 来自于和顶点 直接相连的那些顶点。

     如下图中 时，顶点 的邻居为 。

   • 深度优先采样策略 Depth-first Sampling:DFS：顶点 的邻居 来自于以 为源点的随机游走序列。

     如下图中 时， 顶点 的邻居为 。

   

3. 网络中的顶点有两种相似性：同质性 homophily、结构对等性 structural equivalence。

   • 同质相似性：高度相连并且属于同一个社区的顶点必须紧密的 embed 在一起。

     如上图中的结点 和 高度相连且属于同一个社区，因此它们是同质相似的，因此它们的 embed 必须有很高的相似度。

   • 结构对等相似性：在网络中具有相似结构角色structural role 的顶点必须紧密的 embed 在一起。

     如上图中的结点 和 都作为对应社区的中心结点，它们是结构对等相似的，因此它们的 embed 必须有很高的相似度。

   与同质性不同，结构对等性并不强调连通性，网络中相隔很远的两个顶点仍然可能具有相同的结构角色。

   现实世界中这两个概念不是互斥的，网络通常同时表现出两种行为：某些结点表现出同质性，另一些结点表现出结构对等性。

4. 广度优先搜索 BFS 和深度优先搜索 DFS 在探索同质性和结构对等性起着关键作用：

   • 通过BFS 策略采样的邻居会导致产出的顶点表达具有结构对等性。

     我们注意到，通过准确的刻画局部邻域就可以确定结构对等性。例如，仅仅通过观察每个顶点的直接邻居就可以推断出该顶点的网络角色（如 bridge/hub），从而得到网络结构对等性。

     • 通过对搜索限制在源点附近的邻居顶点，BFS 能够得到每个顶点邻域的微观视图，并且导致产出的顶点表达具有结构对等性。

     • 在 BFS 中，直连的邻居顶点需要被重复采样很多次。这一点很关键，因为它降低了直连邻居顶点分布的方差。

       解释：如果仅采样一次，则每次采样结果中邻居顶点分布可能差异很大。

     • 对于任何给定的 ，对每个顶点 BFS 只会探索该顶点附近的一个很小区域。

   • 通过DFS 策略采样的邻居会导致产出的顶点表达具有同质性。

     和BFS 相反，对任何给定的 ，对每个顶点 DFS 能够探索该顶点附近一个很大的区域，因为 DFS 可以探索远离源点的区域。所以DFS 策略采样的邻居能够描绘邻域的宏观视图，而这对于基于同质性的社区推断至关重要。

     但是 DFS 存在两个问题：

     • 不仅要推断网络中那些结点之间存在依赖关系，还需要刻画这些依赖关系的准确特性。由于邻居规模不超过 ，而需要探索的区域太大，因此很难做到这一点，这就导致采样的结果方差很大：即每次采样结果中邻居顶点的分布差异很大。
     • 探索更深的顶点导致更复杂的依赖关系，因为采样的顶点可能距离源点很远因此和源点相关性不大，因此不具代表性。

5. 基于以上观察node2vec 设计了一种灵活的邻居采样策略，该策略使得我们能够平滑的在 BFS 和 DFS 之间采样。

   给定源点 我们采样一个长度为 的随机游走序列，序列起始顶点为 ， 的采样策略为：

   

   其中 为非归一化的、从顶点 转移到顶点 的概率， 为归一化常数。

   最简单的采样策略为：根据边的权重来采样下一个顶点，即 。如果是无向图则有 。这种采样策略的缺点是没有考虑网络结构。

   考虑到 BFS 和 DFS 分别对应于结构对等性和同质性这两种极端采样方式，我们的采样策略必须考虑以下事实：结构对等性和同质性不是互斥的，现实世界网络通常会同时存在这两者。

   我们通过超参数 和 来定义了一个二阶随机游走过程来采样。考虑从顶点 转移到顶点 并且当前停留在顶点 ，限制决定下一个采样的顶点 。

   定义未归一化的概率 ，其中：

   

   其中 表示顶点 和 之间的最短路径，它必须是在 之间，即： 的取值范围是有限的，必须在顶点 本身、顶点 的一阶邻居、顶点 的二阶邻居之间选择。

   通过设置 为前一个结点 的函数，随机游走过程成为一个二阶马尔科夫链。

   超参数 和 控制了随机游走的方向和速度，它们允许我们的搜索过程在 BFS 和 DFS 之间插值，从而反应结点的不同类型的相似性。

   • 返回参数 Return Parameter ：参数 控制了重新访问上一步已访问顶点的概率。

     • 一个较大的值 将使得接下来访问的顶点 不大可能是上一步已访问的顶点 （除非顶点 除了 之外再也没有其它邻居）。

       这种策略鼓励适当的进行探索新结点，并避免采样过程中的冗余2-hop （即：经过两步转移又回到了结点本身）。

     • 一个较小的值 将使得接下来访问的顶点 很可能是上一步已访问的顶点 。

       这种策略使得随机游走序列尽可能地留在源点 的局部区域。

   • 内外参数 In-out parameter ：参数 控制了探索的方向是向内搜索还是向外搜索。

     • 如果 则 倾向于向 靠拢。这种策略将采样局限在一个很小的范围，从而获得网络的一个局部视图，类似于 BFS 的行为。
     • 如果 则 倾向于远离 。这种策略将鼓励采样向外拓展，从而获得网络的一个宏观视图，类似于 DFS 的行为。

     但是这种策略和BFS、DFS 本质上是不同的：我们的策略采样的结点与源点的距离并不是严格相等的（BFS）、也不是严格递增的 （DFS ）。另外我们的策略易于预处理，且采样效率很高。

   

6. 与单纯的BFS、DFS 策略相比，我们的二阶马尔科夫随机游走策略的计算效率和空间效率较高。

   • 空间复杂度：存储所有结点的邻居的空间复杂度为 。另外对于二阶随机游走过程，缓存每个顶点的邻居之间的关联是有益的，其空间复杂度为 ，其中 为所有顶点的平均度degree 且相对于 通常很小。

     单个顶点的邻居之间的关联的复杂度为 ，考虑所有顶点则空间复杂度为

   • 时间复杂度：由于我们的策略采样的结点与源点的距离并不是严格相等的、也不是严格递增的，因此不同源点采样的序列之间可以复用从而提高了采样效率。

     由于随机游走的马尔可夫性，通过一次性生成长度为 的随机游走序列，我们可以一次性为 个顶点各自生成长度为 的随机游走序列。因此每条随机游走序列的平均算法复杂度为 ，每个采样点的平均算法复杂度为 。

     如下图中我们采样了一条长度 的随机游走序列 ，当 时这会产生三组邻居：

     

     注意：这种采样重用机制会给整个采用过程引入某些 bias，但是我们观察到这种采样方式能够极大提升采样效率。这就是效果和效率之间的折衷。

     

7. Node2Vec 算法主要包含两个过程：Learn Feature 过程、node2vecWalk 过程。

   Learn Feature 过程：

   • 输入：

     • 图
     • 维度
     • 每个源顶点开始的随机游走序列数量
     • 每个随机游走序列长度
     • 上下文尺寸
     • 参数

   • 输出：每个顶点的低维representation

   • 步骤：

     • 预处理权重 ，重新构造新的图

       一个问题，这里预处理是如何做的？论文未说明，得看代码。

     • 初始化列表 为空：

     • 迭代 次，对每个顶点生成以该顶点为起点、长度为 的 条随机游走序列。迭代过程为：：

       对每个顶点 执行：

       

     • 执行随机梯度下降 。

     • 返回求解到的每个顶点的 representation

   node2vecWalk 过程：

   • 输入：

     • 修改后的图
     • 开始顶点
     • 随机游走序列长度

   • 输出：长度为 的一条随机游走序列

   • 步骤：

     • 初始化列表

     • 迭代 ，迭代过程为：

       • 获取当前顶点

       • 获取当前顶点的邻居顶点

         该邻居理论上就是 的前一个顶点 ？论文未说明，得看代码

       • 采样下一个顶点

       • 将 添加到序列：

     • 返回列表

8. Node2Vec 算法的node2vecWalk 过程中，由于源点 的选择导致引入了隐式的 bias。由于我们需要学习所有顶点的 representation，因此我们通过模拟从每个顶点开始的、长度固定为 的 个随机游走序列来抵消该 bias 。

   另外在 node2vecWalk 过程中，我们根据转移概率 来采样。由于二阶马尔可夫转移概率 可以提前计算好，因此可以通过 AliasTable 技术在 时间内高效采样。

9. Node2Vec 算法的三个计算阶段：预处理从而计算转移概率、生成随机游走序列、使用随机梯度下降优化目标函数。

   这三个计算阶段依次执行，且每个阶段可以并行且异步执行，从而使得Node2Vec 算法整体有很好的可扩展性。

10. 尽管搜索模型的超参数，如 需要额外的开销，但是正如实验表明：node2vec 是半监督的。因此可以通过少量的标记数据来有效学习这些参数。

6.2 边的representation

1. 有时候我们会对顶点pair 对感兴趣，如链接预测任务中，我们需要预测给定的两个顶点之间是否存在链接。

   由于我们的随机游走序列是基于网络的连接结构来生成的，因此可以将顶点的 representation 扩展到顶点对。

2. 给定两个顶点 ，我们在它们的representation 上定义一个二元操作 从而生成边的representation ，其中 ， 为顶点对 的 representation 的维度。

   我们希望二元操作符 在所有顶点对之间都有定义，而不仅仅是只有在存在边的顶点对之间有定义，因为预测时顶点对之间可能不存在边。

   因此这里选择了一些二元操作符，且令 ：

   • 均值操作符：

     

   • Hadamard 操作符：

     

   • L1 操作符：

     

   • L2 操作符：

     

     .

6.3 实验

6.3.1 人物关系可视化

1. 我们用一个网络来描述小说《悲惨世界》中的角色，边代表角色之间是否共同出现过。网络共有 77 个顶点和 254 条边。

   我们设置维度 并利用 node2vec 学习每个顶点的representation 向量，然后通过k-means 算法对这些向量聚类。最后我们将representation 向量及其聚类结果在二维空间可视化，相同的颜色代表相同的聚类类别，顶点大小代表顶点的degree 。

   • 上半图给出了 的结果，可以看到node2vec 挖掘出小说中的社区community：有密切交互关系的人的相似度很高。即representation 结果和同质性有关。

   • 下半图给出了 的结果，可以看到 node2vec 挖掘出小说中的角色：角色相同的人的相似度很高。即representation 结果和结构对等性有关。

     如：node2vec 将蓝色顶点embed 在一起，这些顶点代表了小说不同场景之间切换的桥梁bridge ；黄色顶点代表小说中的边缘角色。

   

6.3.2 多标签分类任务

1. 多标签分类任务中，每个顶点属于一个或者多个标签。训练集上每个顶点的所有标签是已知的，我们需要预测测试集每个顶点的所有标签。当标签集合 很大时，多标签分类任务非常有挑战性。

2. 数据集：

   • BlogCatalog：该数据集包含 BlogCatalog 网站上博客作者之间的社交关系，标签代表通过元数据推断出来的博客兴趣。网络包含 10312 个顶点、333983 条边、39 种不同标签。
   • Protein-Protein Interactions:PPI：该数据集包含蛋白质和蛋白质之间的关联，标签代表基因组。网络包含 3890个顶点，76584条边，50种不同标签。
   • 维基百科：该数据集包含维基百科dump 文件的前一百万字节中的单词共现，标签代表单词的词性 Part-of-Speech:POS （由 Standford POS-Tagger 生成）。网络包含 4777 个结点，184812 条边，40 种不同标签。

   所有这些网络都同时呈现同质性和结构对等性。如：

   • 博客作者的社交网络呈现出很强的同质性，但是可能还有一些 “熟悉的陌生人”：博客作者之间没有关联但是兴趣相同。因此它们在结构上是等效的顶点。
   • 蛋白质-蛋白质的相互作用中，当蛋白质和邻近蛋白质功能互补时，它们呈现出结构对等性；当相邻蛋白质功能相似时，它们呈现出同质性。
   • 在单词共现网络中，当相邻的单词具有相同 POS 标签时，它们呈现出同质性；当相邻单词呈现某种语法模式，如 限定词+名词、标点符号 + 名词 ，它们呈现结构对等性。

3. 对比模型：

   • 谱聚类：这是一种矩阵分解方法，它对图 的归一化拉普拉斯矩阵进行分解，最后选取 top d 个特征向量作为顶点的表达。

   • DeepWalk：它可以视为 node2vec 中 的特例。

   • LINE：它可以视为两阶段的特征学习：

     • 第一阶段通过 BFS 从直接邻居中学到前面 维的表达。
     • 第二阶段通过BFD 从二阶邻居中学到剩下 维的表达。

   我们排除了那些已被证明不如 DeepWalk 的其它矩阵分解方法。我们还排除了 GraRep 方法，该方法虽然扩展了 LINE 算法但是无法有效的推广到大型Graph 。

4. 参数配置：

   • 之前的评估方式仅仅使用同样的Graph 作为训练集，而并没有考虑不同算法的采样规模。这里为每个算法执行相同次数的采样。

     令 为总的采样次数，因此对于 node2vec 需要满足 。

   • 所有方法都使用 SGD 进行优化，但是这里有两个改动：

     • DeepWalk 使用分层softmax，计算量太大，这里我们切换到负采样。

     • Node2Vec 和 DeepWalk 都用一个参数 来配置上下文邻居顶点的数量，数量越大则需要进行迭代的step 越多；对于LINE 该参数为1，因此 LINE 每个epoch 很快结束，因此我们训练LINE 个 epoch 。与此对比，Node2Vec/DeepWalk 训练一个 epoch 。

       这里需要看 LINE 源码

   • 所有模型的参数值为：

   • 每组实验重复10次，使用10 折交叉验证搜索超参数 。

5. 每个模型输出的顶点 representation 输入到一个 正则化的one-vs-rest 逻辑回归分类器中，采用Macro-F1 作为评估指标。Micro-F1 和准确率的趋势与 Macro-F1 类似，因此并未给出。

   数据集被拆分为 50% 训练集和 50% 测试集，随机拆分十次取其平均结果。

   结论：

   • node2vec 探索邻居时的灵活性使得它超越了其它算法。

     • 在 BlogCatalog 中，可以设置较低的 值来较好的融合同质性的结构对等性。

       LINE 的效果低于预期，这可能是因为它无法重用采样点，而基于随机游走的策略可以重用采样点。

     • 在 PPI 中，最佳策略 的表现和 DeepWalk 的 相差无几。

       node2vec 通过较大的 值来避免重复访问刚才已访问的顶点来获取一定的性能提升。

   

6. 为进一步分析效果，我们将train-test 拆分比例从 10%~90% ，参数 如前所述。结果表明：

   • 所有方法都明显超越了谱聚类。
   • node2vec 始终超越了 LINE ，并且最差情况也等价于DeepWalk 、最好情况相比 DeepWalk 有巨大提升。

   

7. node2vec 涉及很多超参数，我们在 BlogCatalog 数据集上评估这些超参数的影响。

   其中：训练集、测试集拆分比例为 50%~50%，除了待评估的参数外其它参数均为默认值（ 的默认值均为 1 ）。

   结论：

   • 随着 的减小 node2vec 性能将有所提高，这是因为更小的 将达到预期的同质性和结构对等性。

     低 虽然鼓励向外探索，但是由于 低 的平衡作用可以确保游走里源点不会太远。

   • 提高维度 可以提升性能，但是一旦维度达到 100 左右，性能提升将趋于饱和。

   • 增加源点的游走序列数量 可以提升性能，增加序列的长度 也可以提升性能。

     这两个参数表明更大的预算 ，因此它们对于性能有较大的影响。

   • 上下文大小 以优化时间的增加为代价来提升性能，但是性能提升不明显。

   

8. 真实世界中我们因为各种原因无法获得Grap 的完整的、准确的信息，因此数据是有噪音的。这里我们针对 BlogCatalog 数据集进行摄动研究。

   • 第一种情况：我们分析不同比例的边的缺失对于性能的影响。如上半图所示，随着边的缺失比例上升网络性能大致呈现线性下降，但是下降的斜率较小。
   • 第二种情况：我们分析增加不同比例的随机边（噪音）对于性能的影响。如下半图所示，与缺失边相比这种情况的下降速度稍快，但是斜率趋于放缓。

   

9. 为测试可扩展性我们用 node2vec 学习 Erdos-Renyi 网络的结点表示。所有参数为默认值，网络规模从 100 到 一百万，每个结点的平均 degreee 为 10 。

   可以看到：node2vec 随着结点数量的增加，其收敛时间基本呈线性关系，在不到四个小时即可生成一百万顶点的representation 。

   在 node2vec 的训练过程我们采用了很多优化技巧，如随机游走过程中采用采样点的重用技巧、Alias Table 技巧；在优化时采用负采样和异步随机梯度下降。

   

6.3.3 连接预测

1. 在连接预测任务中，我们给定一个删除了一定比例边的网络，希望模型能够预测这些被删除的边。

   数据集的生成方式为：

   • 网络中随机删除 50% 的边，剩下的所有边的顶点pair 对作为正样本。
   • 随机选择网络中的 n 对不存在边的顶点 pair 对作为负样本。

   由于暂时还没有针对连接预测的特征学习算法，因此我们将node2vec 和一些流行的启发式方法进行对比。这些启发式方法通过评估顶点 的邻居集合 和顶点 的邻居集合 的某种得分，然后根据该得分来判断 之间是否存在边。

   

2. 数据集：

   • FaceBook 数据集：包含FaceBook 用户之间的社交关系，顶点代表用户、边代表好友关系。网络一共包含 4039 个顶点和 88234 条边。
   • Protein-Protein Interactions：PPI 数据集：包含蛋白质和蛋白质之间的关联。网络一共包含 19706个顶点、390633 条边。
   • arXiv ASTRO-PH 数据集：包含 arXiv 网站上发表论文的作者之间的关联，顶点代表作者、边代表两个作者共同参与同一篇论文写作。网络一共包含 18722个顶点、198110 条边。

3. 我们经过超参数优化选择最佳的 ，优化过程这里不做讨论。下图给出了node2vec 的不同operator，以及不同启发式算法的结果，指标为 auc 。

   图中a 表示均值算子，b 表示 Hadamard 积算子，c 表示 WeightedL1 算子，d 表示 WeightedL2 算子。

   结论：

   • 通过feature learning 学习定点对特征（如node2vec,LINE,DeepWalk,谱聚类 等等）的效果明显优于启发式方法。
   • 在所有特征学习的算法中，node2vec 的效果最佳。