Question

1. 网络分析中的许多重要任务涉及对节点和边的预测。

   • 在典型的节点分类任务中，我们需要预测网络中每个节点最可能的标签。例如，在社交网络中我们预测用户的兴趣标签，在 protein-protein interaction 网络中我们预测蛋白质的功能标签。
   • 类似地，在链接预测中，我们希望预测网络中的一对节点之间是否应该存在一条边。链接预测在各个领域都很有用。例如，在基因组学 genomics 中它可以帮助我们发现基因之间的、新的 interaction ，在社交网络中它可以识别现实世界中的朋友。

   任何有监督的机器学习算法都需要一组信息丰富informative 的、有区分力discriminating 的、独立 independent的特征。在网络的预测问题中，这意味着必须为节点和边构建特征的向量 representation 。典型的解决方案涉及基于专家知识的、人工的、领域特定domain-specific 的特征。即使不考虑特征工程所需的繁琐工作，这些特征通常也是为特定任务设计的，并且不会在不同的预测任务中泛化。另一种方法是通过解决优化问题来学习 feature representation 。feature learning 的挑战在于定义目标函数，这涉及计算效率和预测准确性的 trade-off ：

   • 一方面，人们可以致力于找到一种直接优化下游预测任务性能的 feature representation 。虽然这种监督的过程具有良好的准确性，但是由于需要估计的参数数量激增，因此需要以高的训练时间复杂度为代价。
   • 另一方面，目标函数可以定义为独立于下游预测任务，并且可以通过纯粹的无监督的方式学习 representation。这使得优化过程的计算效率较高，并且具有精心设计的目标函数。但是该目标函数产生了与任务无关的特征，这些特征无法达到 task-specific 方法的预测准确性。

   然而，当前的技术未能令人满意地定义和优化网络中的合理目标函数，从而支持可扩展的无监督 feature learning 。

   • 基于线性降维技术和非线性降维技术的经典方法，例如主成分分析 Principal Component Analysis: PCA、多维缩放 Multi-Dimensional Scaling: MDS 及其扩展方法，它们优化一个目标函数，该目标函数变换 transform 网络的代表性的数据矩阵 representative data matrix 从而最大化 data representation 的方差（原始数据在低维空间representation 的方差，即数据尽可能分散）。因此，这些方法总是涉及对应矩阵的特征分解 eigen decomposition ，而特征分解对于大型现实世界网络而言是代价昂贵的。此外，所得到的潜在 representation 在网络上的各种预测任务中表现不佳。

   • 或者，我们可以设计一个旨在保留节点的局部邻域 local neighborhood 的目标函数（最大化保留节点的网络邻域 network neighborhood 的可能性）。我们可以使用随机梯度下降 stochastic gradient descent: SGD 来有效优化目标函数。最近一些工作在这个方向上进行了尝试，但是它们依赖于网络邻域network neighborhood 的严格概念，这导致这些方法在很大程度上对网络特有的连接模式 connectivity pattern 不敏感。具体而言，网络中的节点可以根据它们所属的社区community （即同质性 homophily）进行组织，也可以根据它们的结构角色structural role （即结构相等性 structural equivalence）来组织。

     例如，下图中，我们观察到节点 $ u $ 和 $ s_1 $ 都属于同一个紧密结合的节点社区，而两个不同社区中的节点 $ u $ 和 $ s_6 $ 共享相同的结构角色（即中心节点 hub node 的角色）。现实世界的网络通常表现出这种相等性的混合体。因此，重要的是允许灵活的算法从而可以学习遵守这两个准则的 node representation：能够学习将来自同一个网络社区的节点紧密地嵌入在一起的 representation，也能够学习共享相似结构角色的节点具有相似 embedding 的 representation。这将允许 feature learning 算法在广泛的领域和预测任务中推广。

     

   为此，论文《node2vec: Scalable Feature Learning for Networks》 提出了node2vec，一种用于网络中可扩展的 feature learning 的半监督算法。论文使用 SGD 优化 graph-based 自定义的目标函数，其灵感来自于自然语言处理的先前工作（ 《Efficient estimation of word representations in vector space》）。直观而言，论文的方法返回的 feature representation 可以最大化在低维特征空间中保留节点的网络邻域的可能性。论文使用二阶随机游走方法为节点生成（或采样）网络邻域。

   论文的主要贡献是定义了节点的网络邻域network neighborhood 的灵活概念。通过选择适当的邻域概念，node2vec 可以学习根据节点的网络角色、和/或它们所属的社区而组织的 representation 。论文通过开发一系列有偏biased 的随机游走来实现这一点，它可以有效地探索给定节点的多样化 diverse 的邻域。与先前工作中的严格搜索过程相比，由此产生的算法是灵活的，可以对超参数进行调优。因此，论文的方法推广了先前的工作，并且可以对网络中观察到的所有相等性 equivalence 进行建模。控制搜索策略的超参数有一个直观的解释，并且使得随机游走偏向于不同的网络探索策略。这些超参数也可以通过半监督的方式使用一小部分标记数据直接学习。

   论文还展示了如何将单个节点的 feature representation 扩展到节点pair 对（即 edge ）。为了生成边的 feature representation ，论文使用简单的 binary operator 组合学习到的各个节点的 feature representation 。这种组合性 compositionality 使得 node2vec 可用于涉及节点预测任务和边预测任务。

   论文的实验聚焦于网络中的两个常见预测任务上：多标签分类任务，其中每个节点都被分配一个或者多个类别标签；链接预测任务，在给定一对节点的情况下预测边是否存在。作者将 node2vec 的性能与 state-of-the-art 的 feature learning 算法进行了对比。作者对来自不同领域的几个真实世界的网络进行了实验，例如社交网络 social network 、信息网络information network 、以及来自系统生物学的网络。实验表明：

   • node2vec 在多标签分类任务上的性能优于 state-of-the-art 的方法高达 26.7%，在链接预测任务上的性能优于 state-of-the-art 的方法高达 12.6% 。
   • node2vec 即使在 10% 的标记数据下也表现出有竞争力的性能，并且对噪声或者链接缺失的扰动也具有鲁棒性。

   在计算上，node2vec 的主要阶段是可并行化的，它可以在几个小时内扩展到具有数百万个节点的大型网络。

   总体而言，论文做出了以下贡献：

   • 论文提出了 node2vec，这是一种用于网络中 feature learning 的高效可扩展算法，可使用 SGD 有效优化新颖的、网络感知network-aware的、邻域保留neighborhood preserving 的目标函数。
   • 论文展示了 node2vec 如何符合网络科学中的既定准则，为发现符合不同相等性equivalence 的 representation 提供了灵活性。
   • 论文扩展了 node2vec 和其它基于邻域保留的目标函数的 feature learning 方法，从节点到节点 pair 对，从而用于 edge-based 预测任务。
   • 论文根据经验评估了 node2vec 在几个真实世界数据集上的多标签分类和链接预测任务。

2. 相关工作：机器学习社区在各种领域对特征工程 feature engineering 进行了广泛的研究。在网络中，为节点生成特征的传统范式paradigm 基于特征提取技术 feature extraction technique ，该技术通常涉及一些基于网络属性的、手工制作的特征。相比之下，我们的目标是通过将特征提取作为 representation learning 问题来自动化整个过程。在这种情况下，我们不需要任何手工设计的特征。

   无监督 feature learning 方法通常利用图的各种矩阵 representation 的谱特性 spectral property ，尤其是图拉普拉斯矩阵 Laplacian matrix 和图邻接矩阵 adjacency matrix 。在这种线性代数的视角下，这些方法可以被视为降维技术。人们已经提出了几种线性降维技术（如 PCA）以及非线性降维技术（如 IsoMap）。这些方法同时存在计算性能缺陷和统计statistical 性能缺陷。

   • 首先，在计算效率方面，数据矩阵的特征分解 eigen decomposition 是代价昂贵的，因此这些方法很难扩展到大型网络。
   • 其次，这些方法优化的目标函数对于网络中观察到的多样化模式diverse pattern （例如同质性homophily 和结构相等性 structural equivalence ）不是鲁棒的，并且对底层网络结构和预测任务之间的关系做出假设。例如，谱聚类 spectral clustering 做出了一个强烈的同质性假设，即图割graph cut 对分类有用。这种假设在许多场景下都是合理的，但是在有效地推广到不同的网络方面并不令人满意。

   自然语言处理中 representation learning 的最新进展为离散对象（如单词）的 feature learning 开辟了新途径。具体而言，SkipGram 模型旨在通过优化邻域保留 neighborhood preserving 的似然目标函数likelihood objective 来学习单词的 continuous feature representation 。该算法的过程如下：首先扫描文档的单词，然后 embedding 每个单词使得该单词的特征能够预测附近的单词（即，该单词某个上下文窗口内的其它单词）。单词的 feature representation 是通过使用带负采样的 SGD 来优化似然目标函数 likelihood objective 来学习的。SkipGram 的目标函数基于分布式假设 distributional hypothesis，该假设指出：相似上下文中的单词往往具有相似的含义。即，相似的单词往往出现在相似的 word neighborhood 中。

   受 SkipGram 模型的启发，最近的研究通过将网络表示为文档 document 来建立网络的一个类比 analogy 。就像文档是一个有序的单词序列一样，我们可以从底层网络中采样节点序列，并将网络变成一个有序的节点序列。然而，节点有多种可能的采样策略，导致学到的 feature representation 不同。事实上，正如我们将要展示的，没有明确的、最好的采样策略从而适用于所有网络和所有预测任务。这是先前工作的一个主要缺点：无法为网络中的节点采样提供任何灵活性。 node2vec 算法通过设计一个灵活的目标函数来克服这个限制，这个目标函数不依赖于特定的采样策略，并提供超参数来调整探索的搜索空间。

   最后，对于 node-based 预测任务和 edge-based 预测任务，最近有大量基于现有的 graph-specific 深度网络架构的监督feature learning 工作，和新颖的 graph-specific 深度网络架构的监督feature learning 工作。这些架构使用多层非线性变换直接最小化下游预测任务的损失函数，从而获得高准确性，但是由于高训练时长的要求从而以可扩展性scalability 为代价。

6.1 模型

1. 我们将网络中的 feature learning 形式化为最大似然优化问题。令 $ G=(V,E) $ 为一个给定的网络。我们的分析是通用的，适用于任何有向/无向、加权/无权的网络。

   令 $ f: V\rightarrow \mathbb R^d $ 是一个从节点到 feature learning 的映射函数，其中 feature learning 用于下游预测任务。这里 $ d $ 为一个超参数，指定我们的 feature representation 的维度。换个说法， $ f $ 是一个大小为 $ |V|\times d $ 的参数矩阵，记作 $ \mathbf F\in \mathbb R^{|V|\times d} $ 。即 $ f(\cdot) $ 和 $ \mathbf F $ 是同一个函数的不同表现形式。给定节点 $ u\in V $ ， $ \mathbf{\vec f}_u = f(u)\in \mathbb R^d $ 为 $ \mathbf F $ 的第 $ u $ 行。

   对于每个源节点 $ u\in V $ ，我们将 $ \mathcal N_S(u)\sub V $ 定义为通过邻域采样策略neighborhood sampling strategy $ S $ 生成的节点 $ u $ 的网络邻域network neighborhood。我们继续将 SkipGram 框架扩展到网络。我们寻求优化以下目标函数，该目标函数最大化在给定节点 $ u $ 的 feature representation 的条件下，观察到一个网络邻域 $ \mathcal N_S(u) $ 的对数概率：

   $ \max_{\mathbf F} \sum_{u\in V} \log\text{Pr}\left(\mathcal N_S(u)\mid \mathbf{\vec f}_u\right) $

   为了使优化问题易于处理，我们做出两个标准假设：

   • 条件独立conditional independence：我们假设在给定源节点的 feature representation 的条件下， 观察到一个邻域节点的可能性独立于其它任何邻域节点。即：

     $ \text{Pr}\left(\mathcal N_S(u)\mid \mathbf{\vec f}_u\right) = \prod_{v\in \mathcal N_S(u)} \text{Pr}\left(v\mid \mathbf{\vec f}_u\right) $

   • 特征空间中的对称性symmetry ：源节点source node 和邻域节点neighborhood node 在特征空间中相互对称。因此，我们将每个 source-neighborhood 节点 pair 的条件似然建模为一个 softmax 单元，通过其特征向量的内积来参数化：

     $ \text{Pr}\left(v\mid \mathbf{\vec f}_u\right) = \frac{\exp\left(\mathbf{\vec f}_v\cdot \mathbf{\vec f}_u\right)}{\sum_{v^\prime\in V} \exp\left(\mathbf{\vec f}_{v^\prime}\cdot \mathbf{\vec f}_u\right)} $

   通过上述假设，则我们的最优化方程简化为：

   $ \max_\mathbf F \sum_{u\in V}\left[- \log Z_u + \sum_{v\in \mathcal N_S(u)} \mathbf{\vec f}_v\cdot \mathbf{\vec f}_u\right] $

   其中 $ Z_u = \sum_{v\in V} \exp\left(\mathbf{\vec f}_u\cdot \mathbf{\vec f}_v\right) $ 为逐节点的分区函数 per-node partition function 。对于大型网络， $ Z_u $ 计算代价昂贵，为此我们使用负采样来近似它。我们使用随机梯度上升来优化上述方程。

   $ Z_u $ 本质上是一个期望，是否可以通过均匀采样来近似？这是与负采样近似不同的另一种近似方法。

2. 基于 SkipGram 框架的 feature learning 方法最初是在自然语言的背景下开发的。鉴于文本的线性特性，邻域的概念可以使用连续单词上的滑动窗口sliding window 自然地定义。然而，网络不是线性的，因此需要更丰富的邻域概念。为了解决这个问题，我们提出了一个随机程序，它对给定源节点 $ u $ 的许多不同的邻域进行采样。邻域 $ \mathcal N_S(u) $ 不仅局限于直接邻域，还可以根据采样策略 $ S $ 得到截然不同的各种邻域结构。

6.1.1 经典搜索策略

1. 我们将源节点的邻域采样sampling neighborhood问题视为一种局部搜索形式local search form 。下图展示了一个graph，其中给定一个源节点 $ u $ ，我们的目标是采样其邻域 $ \mathcal N_S(u) $ 。更重要的是，为了能够公平地比较不同的采样策略 $ S $ ，我们将邻域 $ \mathcal N_S(u) $ 的大小限制为 $ k $ 个节点，然后为单个节点 $ u $ 采样多个邻域。

   通常，生成 $ k $ 个节点的邻域 $ \mathcal N_S(u) $ 有两种极端的采样策略：

   • 广度优先采样 Breadth-first Sampling: BFS：邻域 $ \mathcal N_S(u) $ 仅限于与源节点 $ u $ 直接相邻的节点。例如在图中，对于节点 $ u $ 的大小为 $ k=3 $ 的邻域，BFS 采样节点为 $ s_1,s_2,s_3 $ 。
   • 深度优先采样 Depth-first Sampling: DFS ：通过以距离递增顺序采样的节点组成了邻域。

   广度优先采样和深度优先采样代表了搜索的极端场景，对学到的 representation 产生了有趣的影响。具体而言，网络中节点的预测任务经常在两种相似性之间切换：同质性homophily 和结构相等性structural equivalence 。

   • 在同质性的假设下，高度互联且属于相似的网络簇network cluster 或网络社区network community 的节点应该紧密地嵌入在一起。例如，图中的节点 $ s_1 $ 和 $ u $ 属于同一个网络社区。

   • 相比之下，在结构相等性的假设下，在网络中具有相似结构角色 structural role 的节点应该紧密地嵌入在一起。例如，图中的节点 $ u $ 和 $ s_6 $ 作为各自社区的 hub 角色。

     重要的是，与同质性不同，结构相等性并不强调连通性 connectivity ：节点可以在网络中相距很远，但是仍然具有相同的结构角色structural role 。

   在现实世界中，这些相等性概念equivalence notion 并不是互斥的：网络通常表现出两种行为，其中一些节点表现出同质性，而另一些节点则表现出结构相等性。

   

2. 我们观察到 BFS 策略和 DFS 策略在生成反映上述任何一个相等性的 representation 中起着关键作用。具体而言：

   • BFS 采样的邻域导致 embedding 与结构相等性密切对应。直观地，我们注意到，为了确定结构相等性，准确地刻画局部邻域通常就足够了。例如，仅通过观察每个节点的直接邻域就可以推断出基于网络角色（例如 bridge 和 hub）的结构相等性。通过将搜索限制在附近节点，BFS 实现了这种刻画并获得了每个节点邻域的微观视图 microscopic view 。此外，在 BFS 中，被采样邻域中的节点往往会重复多次。这也很重要，因为它减少了源节点 1-hop 邻域的方差。

     然而，对于任何给定的邻域大小 $ k $ ，BFS 仅探索了图中的很小一部分。

   • DFS 的情况正好相反，它可以探索网络的更大部分，因为它可以远离源节点。在 DFS 中，被采样的节点更准确地反映了邻域的宏观视图macro-view ，这对于基于同质性的社区推断inferring community 至关重要。

     然而，DFS 的问题在于：

     • 首先，不仅要推断网络中存在哪些 node-to-node 的依赖关系，而且还要刻画这些依赖关系的确切性质（比如 1-hop、2-hop 等等）。鉴于我们限制了邻域规模，并且探索的邻域空间很大，这会导致高方差，因此这很难。

       高方差的意思是：从源节点 $ u $ 的每次 DFS 采样都可能得到不同的结果。

     • 其次，切换到更大的深度（即更大的邻域大小 $ k $ ）会导致复杂的依赖关系，因为被采样的节点可能远离源节点并且可能不太具有代表性less representative 。

6.1.2 node2vec

1. 鉴于上述观察，我们设计了一个灵活的邻域采样策略 neighborhood sampling strategy ，使得我们能够在 BFS 和 DFS 之间平滑地进行插值interpolate 。我们通过开发一个灵活的有偏随机游走biased random walk 程序来实现这一点，该程序可以通过 BFS 的方式和 DFS 的方式探索社区。

2. 随机游走：正式地，给定一个源节点 $ u $ ，我们模拟一个固定长度为 $ l $ 的随机游走。令 $ c_i $ 为随机游走中的第 $ i $ 个节点，其中 $ c_0 = u $ 为随机游走的起始节点。节点 $ c_i $ 根据以下概率分布生成：

   $ P(c_i = x\mid c_{i-1} = v) = \begin{cases} \pi_{v,x}/Z,& (v,x)\in E\\ 0,&\text{else} \end{cases} $

   其中：

   • $ \pi_{v,x} $ 为节点 $ v $ 和 $ x $ 之间的未归一化的转移概率 unnormalized transition probability 。
   • $ Z $ 为归一化常数。

3. search bias $ \alpha $ ：有偏随机游走最简单的方法是根据静态的边权重 $ w_{v,x} $ 对下一个节点进行采样，即 $ \pi_{v,x} = w_{v,x} $ 。在无权图中， $ w_{v,x} = 1 $ 。然而，这不允许我们考虑网络结构并指导我们的搜索过程来探索不同类型的网络邻域。此外，与分别适用于结构相等性、同质性的极端采样范式 BFS 和 DFS 不同，我们的随机游走应该适应这样一个事实，即：这些相等性概念 equivalence notation 不是相互竞争的、也不是互斥的，现实世界的网络通常表现出二者的混合。

   我们使用两个超参数 $ p $ 和 $ q $ 定义了一个二阶随机游走，它指导游走过程：考虑一个刚刚经过边 $ (t,v) $ ，并且现在停留在节点 $ v $ 处的随机游走（如下图所示）。游走过程现在需要决定下一步，因此它评估从 $ v $ 开始的边 $ (v,x) $ 上的非归一化转移概率 $ \pi_{ v,x } $ 。

   我们将非归一化的转移概率设置为 $ \pi_{v,x} = \alpha_{p,q}(t,x)\times w_{v,x} $ ，其中：

   $ \alpha_{p,q}(t,x) = \begin{cases} 1/p,& d_{t,x} = 0\\ 1,& d_{t,x} = 1\\ 1/q,&d_{t,x} = 2 \end{cases} $

   其中 $ d_{t,x} $ 表示从节点 $ t $ 到节点 $ x $ 的最短路径距离 shortest path distance 。注意： $ d_{t,x} $ 的取值必须为 {0, 1, 2}，因此这两个超参数 $ p,q $ 对于指导随机游走是必要且充分的。如下图所示，edge 上的文字表示 search biases $ \alpha $ 。

   

   直观而言，超参数 $ p $ 和 $ q $ 控制着游走过程探索和离开起始节点 $ u $ 的邻域的速度。具体而言，这些超参数允许我们的搜索过程在 BFS 和 DFS 之间进行近似approximately 地插值，从而反映对节点的不同相等性概念的 affinity 。

   • 返回参数 return parameter $ p $ ：超参数 $ p $ 控制在游走过程中立即重访已有节点的可能性。

     • 将其设为较高的值（ $ \gt \max(q,1) $ ）可以确保我们在接下来的两步中不太可能对已经访问过的节点进行采样（除非游走过程中的下一个节点没有其它邻居）。该策略鼓励适度探索并避免采样中的 2-hop 冗余redundancy 。
     • 另一方面，如果 $ p $ 值较低（ $ \lt \min(q,1) $ ），则它将导致游走过程回退一步，这将使得游走过程局部地local 靠近起始节点 $ u $ 。

     $ 1/p $ 控制着返回上一个已访问节点 $ t $ 的概率。 $ p $ 越小，则返回的概率越大。

   • in-out parameter $ q $ ：超参数 $ q $ 允许搜索区分向内 inward 的节点和向外 outward 的节点。如上图所示：

     • 如果 $ q\gt 1 $ ，则随机游走偏向于靠近节点 $ t $ 的节点。此时我们的 samples 由小的局部 small locality 内的节点组成，这种游走过程获得了近似于 BFS 行为（以起始节点开始）的、底层图的局部视图local view 。
     • 相反，如果 $ q\lt 1 $ ，则随机游走更偏向于远离节点 $ t $ 的节点。这种行为反映了鼓励向外探索的 DFS。然而，这里的一个本质区别是：我们在随机游走框架内实现了类似于 DFS 的探索。因此，采样节点与给定源节点 $ u $ 的距离并不是严格增加的。但是反过来，我们受益于易于处理的 preprocessing 、以及随机游走的卓越采样效率。

     $ 1/q $ 控制着远离上一个已访问节点 $ t $ 的概率。 $ q $ 越小，则远离的概率越大。

   注意，通过将 $ \pi_{v,x} $ 设置为游走过程中前一个节点 $ t $ 的函数，随机游走过程是二阶马尔科夫的。

4. 随机游走的好处：和单纯的 BFS/DFS 方法相比，随机游走同时在空间复杂度和时间复杂度方面的效率较高。

   • 对于图中的所有节点，存储它们直接邻域的空间复杂度为 $ O(|E|) $ 。对于二阶随机游走，存储所有节点的邻居之间的互联 interconnection 是有帮助的，这会产生 $ O(a^2|V|) $ 的空间复杂度，其中 $ a $ 为图的平均 degree 并且在现实世界中通常很小。

   • 与经典的基于搜索的BFS/DFS 采样策略相比，随机游走的另一个关键优势是它的时间复杂度。具体而言，通过在 sample generation过程中施加了图的连通性graph connectivity ，随机游走提供了一种方便的机制，通过跨不同源节点 reuse samples 来提高采样效率：由于随机游走的马尔科夫性质，通过模拟长度为 $ L\gt l $ 的随机游走，我们可以一次性为 $ L-l $ 个源节点生成随机游走序列，即 $ L-l $ 条随机游走序列，每条随机游走序列的长度为 $ l $ 。因此，每个采样节点的有效时间复杂度为 $ O(L/(l\times (L-l))) $ 。

     例如，下图中，我们采样了一条长度为 $ L=6 $ 的随机游走序列 $ \{u,s_4,s_5,s_6,s_8,s_9\} $ ，这将导致 $ \mathcal N_S(u) = \{s_4,s_5,s_6\},\mathcal N_S(s_4) = \{s_5,s_6,s_8\}, \mathcal N_S(s_5)=\{s_6,s_8,s_9\} $ ，其中 $ l=3 $ 。注意，sample reusing 可能会在整个过程中引入一些 bias，但是我们发现它大大提高了效率。

     

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

   Learn Feature 过程：

   • 输入：

     • 图 $ G=(V,E,W) $
     • 维度 $ d $
     • 每个源节点开始的随机游走序列数量 $ r $
     • 每条随机游走序列长度 $ l $
     • 上下文尺寸 $ k $
     • 超参数 $ p,q $

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

   • 步骤：

     • 预处理权重 $ \pi = \text{PreprocessModifiedWeights(G,p,q)} $ ，重新构造新的图 $ G^\prime = (V,E,\pi) $

       这是计算转移概率，并将转移概率设置为边的权重。但是这里转移概率是二阶马尔科夫的，如何设置为一阶的边权重？具体可能要看源代码。

     • 初始化列表 $ \text{walks} $ 为空： $ \text{walks}=[] $

     • 迭代 $ r $ 次，对每个节点生成以该节点为起点、长度为 $ l $ 的 $ r $ 条随机游走序列。迭代过程为： $ \text{iter} = 1,2,\cdots,r $ ：

       对每个节点 $ u\in V $ 执行：

       $ \text{walk} = \text{node2vecWalk}(G^\prime,u,l)\\\text{walks.append(walk)} $

     • 执行随机梯度下降 $ \text{SGD(k,d,walks)} $ 。

     • 返回求解到的每个节点的 representation 。

   node2vecWalk 过程：

   • 输入：

     • 修改后的图 $ G^\prime(V,E,\pi) $
     • 源节点 $ u $
     • 随机游走序列长度 $ l $

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

   • 步骤：

     • 初始化列表 $ \text{walk} = [u,] $

     • 迭代 $ \text{iter2} = 1,2,\cdots,l-1 $ ，迭代过程为：

       • 获取当前节点 $ \text{curr} = \text{walk}[-1] $
       • 获取当前节点的邻居节点 $ V_\text{curr} = \text{GetNeighbors}(\text{curr},G^\prime) $
       • 采样下一个节点 $ s= \text{AliasSample}(V_\text{curr},\pi) $
       • 将 $ s $ 添加到序列： $ \text{walk.append(s)} $

     • 返回列表 $ \text{walk} $

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

   另外在 node2vecWalk 过程中，我们根据转移概率 $ \pi_{v,x} $ 来采样。由于二阶马尔可夫转移概率 $ \pi_{v,x} $ 可以提前计算好，因此可以通过 AliasTable 技术在 $ O(1) $ 时间内高效采样。

7. node2vec 的三个阶段：即计算转移概率的预处理、随机游走模拟、以及使用 SGD 的优化，按顺序依次进行。每个阶段都是可并行化和异步执行的，有助于 node2vec 的整体可扩展性。

6.1.3 边的representation

1. node2vec 算法提供了一种半监督方法来学习网络中节点的丰富特征 representation。 然而，我们经常对涉及节点 pair ，而不是单个节点的预测任务感兴趣。例如，在链接预测中，我们预测网络中两个节点之间是否存在链接。由于我们的随机游走天然地基于底层网络中节点之间的连接结构 connectivity structure，因此我们在单个节点的特征 representation 上使用 bootstrapping 的方法从而将它们扩展到节点 pair 。

   node2vec 的训练是无监督的，但是可以使用下游任务的、少量的监督样本来选择最佳的超参数 $ p,q $ ，从而实现半监督学习。

2. 给定两个节点 $ u $ 和 $ v $ ，我们在相应的特征向量 $ \mathbf{\vec f}_u $ 和 $ \mathbf{\vec f}_v $ 上定义二元算子 $ \circ $ ，从而生成 representation $ \mathbf{\vec g}_{u,v} $ 使得 $ g:V\times V\rightarrow \mathbb R^{d^\prime} $ ，其中 $ d^\prime $ 为 $ (u,v) $ pair 的 representation 维度。

   我们希望我们的算子可以为任何一对节点进行定义，即使这对节点之间不存在边，因为这样做使得 representation 对于链接预测有用，其中我们的测试集同时包含 true edge （即存在边）和 false edge（即不存在边）。我们考虑了算子 $ \circ $ 的几种选择，使得 $ d^\prime = d $ ，如下所示：

   • 均值操作符Average ： $ \oplus: \mathbf{\vec g}_{u,v}= \mathbf{\vec f}_u\oplus\mathbf{\vec f}_v = \frac{\mathbf{\vec f}_u+\mathbf{\vec f}_v}{2} $
   • Hadamard 操作符： $ \odot: \mathbf{\vec g}_{u,v}= \mathbf{\vec f}_u\odot\mathbf{\vec f}_v = (f_{u,1}\times f_{v,1},\cdots,f_{u,d}\times f_{v,d})^\top $
   • L1 操作符Weighted-L1： $ ||\cdot||_1: \mathbf{\vec g}_{u,v}= ||\mathbf{\vec f}_u-\mathbf{\vec f}_v||_1 = (|f_{u,1}- f_{v,1}|,\cdots,|f_{u,d}- f_{v,d}|)^\top $
   • L2 操作符Weighted-L2 ： $ ||\cdot||_2: \mathbf{\vec g}_{u,v}= ||\mathbf{\vec f}_u-\mathbf{\vec f}_v||_2 = (f_{u,1}- f_{v,1}|^2,\cdots,|f_{u,d}- f_{v,d}|^2)^\top $

6.1.4 总结

1. 本文中我们将网络中的 feature learning 作为 search-based 优化问题进行研究。这种观点为我们提供了多种优势：

   • 它可以在 exploration-exploitation trade-off 的基础上解释经典的搜索策略。

   • 此外，当应用于预测任务时，它为学到的 representation 提供了一定程度上的可解释性。

     • 例如，我们观察到 BFS 只能探索有限的邻域，这使得 BFS 适用于刻画依赖于节点直接局部结构 immediate local structure 的网络中的结构相等性。
     • 另一方面，DFS 可以自由探索网络邻域，这对于以高方差为代价发现同质社区homophilous community 很重要。

2. DeepWalk 和 LINE 都可以视为严格的网络搜索策略。

   • DeepWalk 提出使用均匀的随机游走进行搜索。这种策略的明显限制是它使得我们无法控制已经探索的邻域 explored neighborhood 。

     即倾向于 exploration 。

   • LINE 主要提出了BFS 策略，并且独立地在 1-hop 邻域和 2-hop 邻域上采样节点和优化似然likelihood 。这种探索的效果更容易刻画，但是它的限制是：无法灵活地探索更深的节点。

     即倾向于 exploitation 。

   相比之下，通过超参数 $ p $ 和 $ q $ 探索网络邻域，node2vec 中的搜索策略既灵活又可控。虽然这些搜索超参数具有直观的解释，但是当我们可以直接从数据中学习它们时，我们在复杂网络上获得了最佳结果。从实用角度来看，node2vec 具有可扩展性并且对扰动具有鲁棒性。

3. 未来工作：

   • 探索 Hadamard 算子比其它算子效果更好的背后原因。
   • 基于搜索超参数为边建立可解释的相等性概念。
   • 将 node2vec 应用到特殊结构的网络，如异质信息网络 heterogeneous information network、具有节点特征的网络、具有边特征的网络。

6.2 实验

6.2.1 案例研究：悲惨世界网络

1. 如前所述，我们观察到 BFS 和 DFS 策略代表了节点嵌入的两个极端：基于同质性（即网络社区）、以及基于结构相等性（即节点的结构角色）。我们现在的目标是凭经验证明这一事实，并表明 node2vec 实际上可以发现同时符合这两个准则的 embedding 。

   我们用一个网络来描述小说《悲惨世界》中的角色，边代表角色之间是否共同出现过。网络共有 77 个节点和 254 条边。我们设置 $ d=16 $ 并利用 node2vec 学习网络中每个节点的feature representation ，然后通过k-means 算法对这些feature representation聚类。最后我们在二维空间可视化原始网络，节点根据它们的 cluster 分配相应的颜色，节点大小代表节点的degree 。

   • 上半图给出了 $ p=1,q=0.5 $ 的结果，可以看到node2vec 挖掘出小说中的社区community：有密切交互关系的人的相似度很高。即representation 结果和同质性 homophily 有关。
   • 下半图给出了 $ p=1,q=2 $ 的结果，可以看到 node2vec 挖掘出小说中的角色：角色相同的人的相似度很高。即representation 结果和结构相等性有关。如：node2vec 将蓝色节点嵌入在一起，这些节点代表了小说不同场景之间切换的桥梁bridge 的角色；黄色节点代表小说中的边缘角色。

   人们可以为这些节点 cluster 解释以不同的语义，但关键是 node2vec 不依赖于特定的相等性概念。正如我们通过实验表明的那样，这些相等性概念通常出现在大多数现实世界的网络中，并且对预测任务学到的 representation 的性能产生重大影响。

   

6.2.2 实验配置

1. baseline ：我们的实验在标准的监督学习任务上评估了 feature representation （通过 node2vec 获得的）：节点的多标签分类任务multilabel classification 、边的链接预测 link prediction 任务。对于这两个任务，我们将 node2vec 和下面的算法进行对比：

   • 谱聚类 spectral clustering：这是一种矩阵分解方法，其中我们将图 $ G $ 的归一化拉普拉斯矩阵normalized Laplacian matrix 的 top d 特征向量 eigenvector 作为节点的 feature vector representation 。

   • DeepWalk：这种方法通过模拟均匀随机游走来学习 $ d $ 维 feature representation 。DeepWalk 中的采样策略可以视为 $ p=1,q=1 $ 的 node2vec 的一个特例。

   • LINE：这种方法在两个独立的 phase 中学习 $ d $ 维的 feature representation 。

     • 在第一种 phase ，它保持节点的一阶邻近性来学习 $ d/2 $ 维的 representation。
     • 在第二种 phase ，它保持节点的二阶邻近性来学习另一个 $ d/2 $ 维的 representation 。

   我们剔除了其它已经被证明不如 DeepWalk 的矩阵分解 matrix factorization 方法。我们还剔除了最近的一种方法 GraRep，它将 LINE 推广为保持节点的高阶邻近性，但是它无法有效地扩展到大型网络。

2. 配置：与先前工作中用于评估 sampling-based 的 feature learning 算法的配置相比，我们为每种方法生成相同数量的 samples ，然后在预测任务中评估获得的特征的质量。因此，在采样阶段sampling phase ，DeepWalk, LINE, node2vec 的参数设置为：在 runtime 时生成相同数量的 samples 。例如，如果 $ \mathcal K $ 是总的采样预算，那么 node2vec 的超参数满足： $ \mathcal K = r\times l\times |V| $ 。

   在优化阶段 optimization phase，所有这些算法都使用 SGD 进行了优化，其中我们纠正了两个关键性差异：

   • 首先，DeepWalk 使用 hierarchical softmax 来近似 softmax 概率，其目标函数类似于 node2vec 使用的目标函数。然而，与负采样相比，hierarchical softmax 效率低下。因此对于 DeepWalk 我们切换到负采样并保持其它一切不变，这也是 node2vec 和 LINE 中实际使用的 approximation 。
   • 其次，node2vec 和 DeepWalk 都有一个超参数，用于优化上下文邻域节点的数量，数量越大则需要迭代的轮次越多。对于 LINE，该超参数设置为单位数量（即 1），但是由于 LINE 比其它方法更快地完成单个 epoch，我们让它运行 $ k $ 个 epoch 。

   node2vec 使用的超参数设置与 DeepWalk 和 LINE 使用的典型值一致。具体而言，我们设置 $ d=128, r= 10, l=80, k=10 $ ，并且优化了一个 epoch。我们选择 10 个随机数种子初始化并重复我们的实验，并且我们的结果在统计上显著，p-value 小于 0.01 。

   最佳的 in-out 超参数 $ q $ 和 return 超参数 $ p $ 是在 10% 标记数据上使用 10-fold 交叉验证进行网格搜索来找到的，其中 $ p,q\in \{0.25,0.50,1,2,4\} $ 。

6.2.3 多标签分类任务

1. 多标签分类任务中，每个节点属于一个或者多个标签，其中标签来自于集合 $ \mathbb L $ 。在训练阶段，我们观察到一定比例的节点上的所有标签。任务是预测剩余节点上的标签。当标签集合 $ \mathbb L $ 很大时，多标签分类任务非常有挑战性。

2. 数据集：

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

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

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

3. 实验结果：每个模型输出的节点 representation 输入到一个 $ L_2 $ 正则化的one-vs-rest 逻辑回归分类器中，采用Macro-F1 作为评估指标。Micro-F1 和准确率的趋势与 Macro-F1 类似，因此并未给出。训练数据和测试数据均拆分为 10 个随机实例。

   结论：node2vec 探索邻域时的灵活性使得它超越了其它算法。

   • 在 BlogCatalog 中，可以设置较低的 $ p $ 和 $ q $ 值来较好的融合同质性的结构相等性，在 Macro-F1 分数中比 DeepWalk 提高 22.3%、比 LINE 提高 229.2%。LINE 的表现低于预期，这可能是因为它无法 reuse samples ，而基于随机游走的策略可以reuse samples 。

   • 即使在我们的其它两个网络中（这两个网络也存在混合的相等性），node2vec 的半监督特性也可以帮助我们推断 feature learning 所需的适当的探索程度。

     • 在 PPI 网络中，最佳探索策略 （ $ p=4,q=1 $ ） 结果证明与 DeepWalk 的均匀探索（ $ p=1, q=1 $ ） 几乎没有区别，但是 node2vec 通过高 $ p $ 值避免了重复访问已访问节点的冗余性，使得 node2vec 相比 DeepWalk 略有优势。而 node2vec 在 Macro-F1 分数上相比 LINE 高出 23.8%。
     • 然而，通常而言，均匀随机游走可能比 node2vec 的探索策略差得多。正如我们在 Wikipedia 单词共现网络中看到的那样，均匀随机游走不能导致最佳的采样，因此node2vec 比 DeepWalk 提高了 21.8%，比 LINE 提高了 33.2% 。

   

4. 数据稀疏性：为了进行更细粒度的分析，我们将train-test 拆分比例从 10%~90% ，超参数 $ p,q $ 在 10% 的数据上学习。结果表明：

   • 所有方法都明显超越了谱聚类，DeepWalk 优于 LINE。
   • node2vec 始终超越了 LINE ，并且最差情况也等价于DeepWalk 、最好情况相比 DeepWalk 有巨大提升。例如在 70% 的标记数据中，我们在 BlogCatalog 上相比 DeepWalk 提升了 26.7%。

   

5. 参数敏感性：node2vec 算法涉及许多超参数，我们在 BlogCatalog 数据集上评估这些超参数的影响。我们使用标记数据和未标记数据之间的 50 - 50 拆分。除了待评估的参数外其它参数均为默认值（ $ p,q $ 的默认值均为 1 ）。我们的评估指标为 Macro-F1 。结论：

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

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

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

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

     这两个参数表明更大的采样预算sampling budget $ \mathcal K $ ，因此它们对于性能有较大的影响。

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

   

6. 扰动分析：对于许多现实世界的网络，我们无法获得有关网络结构的准确信息。我们进行了一项扰动研究，分析了 node2vec 在 BlogCatalog 网络中的、边结构edge structure 的两个不完美信息场景imperfect information scenario 下的性能。

   • 第一个场景：我们评估缺失边missing edge 比例（相对于完整网络）对性能的影响。缺失边是随机选择的，但是存在连接的节点总数是固定的。如上半图所示，随着缺失边比例上升网络性能大致呈现线性下降，但是下降的斜率较小。

     在图随时间演变的情况下（例如，引文网络）或网络建设成本较高的情况下（例如，生物网络），网络对于缺失边的鲁棒性尤其重要。

   • 第二个场景：我们在网络中随机选择的节点对之间添加噪声边noisy edge 。如下半图所示，与缺失边相比这种情况的网络性能下降速度稍快，但是斜率趋于放缓。

     同样地，node2vec 对假边 false edge 的鲁棒性在多种情况下很有用，例如传感器网络 sensor network 其中传感器的值有噪声。

   

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

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

   采样过程包括：为我们随机游走计算转移概率的预处理 perprocessing （时间成本小到可以忽略不计）、以及随机游走的模拟simulation 。我们使用负采样和异步 SGD 使得优化阶段变得高效。

   在 node2vec 的训练过程我们采用了很多优化技巧：如随机游走过程中的sample reusing重用技巧、Alias Table 技巧。虽然我们可以根据底层任务和领域自由地设置搜索超参数，但是学习搜索超参数的最佳设置会增加开销。然而，正如我们的实验所证实的，这种开销很小，因为 node2vec 是半监督的，因此可以用很少的标记数据有效地学习这些超参数。

   

6.2.4 链接预测任务

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

   • 网络中随机删除 50% 的边，剩下的所有边的节点pair 对作为正样本。但是，要确保删除边之后的残差网络是连通的。
   • 从网络中随机选择相同数量的、不存在边的节点 pair 对作为负样本。

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

   

2. 数据集：

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

3. 实验结果：我们经过超参数优化选择最佳的 $ p,q $ ，优化过程这里不做讨论。下图给出了node2vec 的不同operator，以及不同启发式算法的结果，指标为 auc 。图中：a 表示均值算子operator ，b 表示 Hadamard 积算子，c 表示 WeightedL1 算子，d 表示 WeightedL2 算子。

   结论：

   • 通过feature learning 学习节点pair 对特征（如node2vec, LINE, DeepWalk, Spectral Clustering 等等）的效果明显优于启发式方法。

   • 在所有feature learning 的算法中，node2vec 的效果最佳。

   • 当我们单独查看算子时，除了 Weighted-L1 和 Weighted-L2 之外（这两种算子中 LINE 最佳），其它算子中 node2vec 超越了 DeepWalk 和 LINE 。

     Hadamard 算子与 node2vec 一起使用时非常稳定stable ，在所有网络中平均提供最佳性能。