DeepWalk: Online Learning of Social Representations（2014 ACM SIGKDD）

DeepWalk: Online Learning of Social Representations----《DeepWalk：用于图节点嵌入的在线机器学习算法》

DeepWalk 是将 word2vector 用到 GNN 上
DeepWalk： 将 Graph 的每个节点编码为一个 D 维向量（无监督学习），Embedding 中隐式包含了 Graph 中的社群、连接、结构信息，可用于后续节点分类等下游任务（监督学习）。
在这里插入图片描述

摘要

我们提出了 DeepWalk，一种学习网络中节点潜在表示的新方法。这些潜在表示在连续向量空间中对社会关系进行编码，很容易被统计模型利用。DeepWalk 概括了语言建模和无监督特征学习（或深度学习）从单词序列到图形的最新进展。
DeepWalk 使用从截断随机游走获得的局部信息，通过将游走视为句子的等价物来学习潜在表示。我们在 BlogCatalog、Flickr 和 YouTube 等社交网络的多个多标签网络分类任务上展示了 DeepWalk 的潜在表示。我们的结果表明，DeepWalk 的性能优于具有挑战性的基线，这些基线允许对网络进行全局视图，特别是在存在丢失信息的情况下。当标记数据稀疏时，DeepWalk 的表示可以提供比竞争方法高出 10% 的 F1 分数。在一些实验中，DeepWalk 的表示能够优于所有基线方法，同时使用的训练数据少 60%。
DeepWalk 也是可扩展的。它是一种在线学习算法，可以构建有用的增量结果，并且可以轻松并行化。这些品质使其适合广泛的现实世界应用，例如网络分类和异常检测。

引言

网络表示的稀疏性既是优点也是缺点。稀疏性使得设计高效的离散算法成为可能，但也使得统计学习中的泛化变得更加困难。网络中的机器学习应用（例如网络分类 [15, 37]、内容推荐 [11]、异常检测 [5] 和缺失链接预测 [22]）必须能够处理这种稀疏性才能生存。
在本文中，我们首次将深度学习（无监督特征学习）[2]技术引入网络分析中，该技术在自然语言处理中已被证明是成功的。我们开发了一种算法(DeepWalk)，通过建模短随机游走序列来学习图顶点的网络连接结构信息。网络连接结构信息是捕捉邻域相似性和社区成员关系的顶点的潜在特征。这些潜在表示将社会关系编码在连续低维稠密向量空间中。DeepWalk 概括了神经语言模型处理一组随机游走序列组成的特殊语言。这些神经语言模型已被用来捕获人类语言的语义和句法结构[6]，甚至逻辑类比[28]。
DeepWalk 将图作为输入并输出每个节点的潜在表示。将我们的方法应用于经过充分研究的空手道网络的结果如图 1 所示。图1a所示为图结构呈现形式。图1b显示了我们的方法输出的结果（二维embedding）。除了惊人的相似性之外，我们注意到（1b）的线性可分离部分对应于通过输入图（1a）中的模块化最大化找到的簇（显示为顶点颜色）。
在这里插入图片描述
为了展示 DeepWalk 在现实场景中的潜力，我们评估了其在大型异构图中具有挑战性的多标签网络分类问题的性能。在关系分类问题中，特征向量之间的链接违背了传统机器学习的独立同分布假设。解决此问题的技术通常使用近似推理技术 [31, 35] 来利用依赖性信息来改进分类结果。我们通过学习与标签无关的图的表示来远离这些方法。我们的嵌入向量的质量不受标记顶点选择的影响（但是受顺序影响），因此它们可以在任务之间共享。
DeepWalk 在创建社交维度方面优于其他潜在表示方法 [39, 41]，特别是当标记节点稀缺时。通过非常简单的线性分类器（例如逻辑回归），我们的表示可以实现出色的性能。我们的表示是通用的，可以与任何分类方法（包括迭代推理方法）结合。DeepWalk 实现了所有这些目标，同时也是一种可轻松并行化的在线算法。

我们的贡献如下：

我们引入深度学习作为分析图形的工具，以构建适合统计建模的鲁棒表示。DeepWalk 学习短随机游走序列中存在的结构规律。
我们广泛评估了我们在多个社交网络上的多标签分类任务的表示。我们发现，在标签稀疏的情况下，分类性能显着提高，在我们考虑的最稀疏问题上，比 Micro F1 提高了 5%-10%。在某些情况下，即使训练数据少 60%，DeepWalk 的表示也能优于竞争对手。
我们通过使用并行实现构建网络规模图（例如 YouTube）的表示来展示我们算法的可扩展性。此外，我们描述了构建我们方法的流处理版本所需的最小更改。

问题定义

我们考虑将社交网络的成员分为一个或多个类别的问题。更形式化来说， $G = (V, E)$ ，其中 $V$ 是节点， $E$ 是邻接矩阵， $\subseteq (V \times V)$ 。给定一个部分标记的社交网络 ${G_L} = (V,E,X,Y)$ ，其属性 $\in {R^{\left| V \right| \times S}}$ ，其中 $S$ 是每个节点向量的维度， $\in {R^{\left| V \right| \times \left| y \right|}}$ ， $y$ 是标签集（多标签）。
在传统的机器学习分类设置中，我们的目标是学习一个假设 $H$ ，它将 $X$ 中的元素映射到标签集 $y$ 中。在我们的例子中，我们可以利用 $G$ 结构中嵌入的示例依赖性的重要信息来实现卓越的性能。
在文献中，这被称为关系分类（或集体分类问题[37]）。传统的关系分类方法将问题作为无向马尔可夫网络中的推理，然后使用迭代近似推理算法（例如迭代分类算法[31]、吉布斯采样[14]或标签松弛[18]）来计算给定网络结构的标签的后验分布。
我们提出了一种不同的方法来捕获网络拓扑信息。我们提出了一种无监督方法，该方法不是将标签空间混合为特征空间的一部分，而是学习捕获独立于标签分布的图结构的特征（只用连接学习节点嵌入）。
结构表示和标签任务之间的这种分离避免了迭代方法中可能发生的级联错误（误差累积）[33]。此外，同样的表示可用于该网络的多个分类问题。
我们的目标是学习 ${X_E} \in {R^{\left| V \right| \times d}}$ ，其中 $d$ 是较小的潜在维度。这些低维表示是分布式的（分布式：各个维度都不为0）；这意味着每个向量都由维度的子集来表达，并且每个维度都对空间表达的社会概念的子集做出贡献。
利用这些结构特征，我们将扩大属性空间（反映连接信息的Embedding+反映节点本身的特征）以帮助分类决策。这些特征是通用的，可以与任何分类算法（包括迭代方法）一起使用。然而，我们相信这些功能的最大用途是它们可以与简单的机器学习算法轻松集成。正如我们将在第 6 节中展示的那样，它们在现实网络中可以适当扩展。

学习图节点嵌入表示

我们寻求学习具有以下特征的 embedding：

适应性（弹性扩容）：真实的社交网络在不断发展；新的社会关系不应该需要再次重复学习过程。
社群聚类信息：潜在维度之间的距离应该代表一个度量，用于评估网络中相应成员之间的社会相似性。这允许在具有同质性的网络中进行泛化。
低维：当标记数据稀缺时，低维模型可以更好地泛化（防止过拟合），并加快收敛和推理速度。
连续性：我们需要潜在的表示来模拟连续空间中的部分社区成员资格。除了提供社区成员的详细的视图之外，连续表示在社区之间具有平滑的决策边界，从而允许更鲁棒的分类。

为了满足这些要求，我们的方法使用最初为语言建模设计的优化技术，从短随机游动序列中学习顶点的表示。在这里，我们回顾 随机游走 和 语言建模 的基础知识，并描述它们的组合如何满足我们的需求。

随机游走

我们将以顶点 ${v_i}$ 为起始节点的随机游走表示为 ${W_{{v_i}}}$ 。这是一个随机过程，随机变量为 $W_{{v_i}}^1,W_{{v_i}}^2,...,W_{{v_i}}^k$ 使得 $W_{{v_i}}^{k + 1}$ 是从顶点 ${{v_k}}$ 的邻居中随机选择的顶点。随机游走已被用作内容推荐 [11] 和社区检测 [1] 中各种问题的相似性度量。它们还是一类 output sensitive（至少要遍历一遍全图）算法的基础，这些算法使用它们来计算时间复杂度小于输入图大小的局部社区结构信息。
正是这种与局部结构的联系促使我们使用短随机游走序列作为从网络中提取信息的基本工具。除了捕获社区信息之外，使用随机游走作为我们算法的基础还为我们提供了另外两个理想的属性。首先，局部探索很容易并行化。多个随机游走器（在不同的线程、进程或机器中）可以同时探索同一图的不同部分。其次，依靠从短随机游走获得的信息，可以适应图结构的微小变化（在线增量学习），而无需全局重新计算。我们可以使用新的随机游走迭代更新学习模型，从时间变化区域次线性地更新到整个图。

连接：幂律

（幂律通常描述节点度的分布，表明少数节点具有非常高的度，而大多数节点的度较低。这种分布特征是具有长尾部分的）
在选择了在线随机游走作为捕获图结构的原语之后，我们现在需要一种合适的方法来捕获这一信息。如果连通图的度分布遵循幂律分布（无标度），我们观察到顶点在短随机游走中出现的频率也将遵循幂律分布。
自然语言中的词频遵循类似的分布，语言建模技术可以解释这种分布行为。为了强调这种相似性，我们在图 2 中展示了两种不同的幂律分布。第一个来自无标度图上的一系列短随机游走，第二个来自英文维基百科的 100,000 篇文章的文本。
在这里插入图片描述
我们工作的核心贡献是这样的想法：用于模拟自然语言的技术（其中符号频率遵循幂律分布（或Zipf定律））可以重新用于模拟网络中的社区结构。 我们在本节的其余部分中回顾了语言建模方面不断发展的工作，并将其转换为满足我们标准的顶点表示。

语言模型

语言建模的目标是估计特定词序在语料库中出现的可能性。更形式化地说，给定一个单词序列：

$W_1^n = ({w_0},{w_1},...,{w_n})$

其中， ${w_i} \in V$ （ $V$ 是词汇表），我们希望在所有训练语料库上最大化 $Pr ({w_n}|{w_0},{w_1},...,{w_{n - 1}})$ 。
表示学习的最新工作重点是使用概率神经网络来构建单词的一般表示，从而将语言建模的范围扩展到超出其原始目标。
在这项工作中，我们提出了语言建模的概括，以通过一系列短随机游走来探索图。这些游走序列可以被认为是特殊语言中的短句和短语。直接的模拟是根据随机游走中迄今为止访问过的所有先前顶点来估计顶点 ${v_i}$ 的可能性：

$Pr ({v_i}|{v_1},{v_2},...,{v_{i - 1}})$ （用前i-1个节点预测第i个节点）

我们的目标是学习潜在表示，而不仅仅是节点共现的概率分布，因此我们引入映射函数 $\Phi :v \in V \mapsto {R^{\left| V \right| \times d}}$ 。该映射 $\Phi$ 表示与图中每个顶点 $v$ 相关的潜在社会表征。（实际上，我们用没有大小限制的参数 ${\left| V \right| \times d}$ 矩阵表示 $\Phi$ ，该矩阵稍后将用作我们的 ${X_E}$ ）接下来的问题是估计可能性：

$\Pr ({v_i}|(\Phi ({v_1}),\Phi ({v_2}),...,\Phi ({v_{i - 1}})))$ （用前i-1个节点的Embedding预测第i个节点， $\Phi$ 是查表操作）

然而，随着游走长度的增加，计算这个目标函数变得不可行（概率相乘使值越来越小）。
最近语言模型的放松 [26, 27] 彻底改变了预测问题。首先，它不是使用上下文来预测缺失的单词，而是使用一个单词来预测上下文。其次，上下文由出现在给定单词右侧和左侧的单词组成。最后，它消除了问题的排序约束。相反，该模型需要在不知道单词与给定单词的偏移量的情况下，最大化任何单词出现在上下文中的概率。
就顶点表示建模而言，这会产生优化问题：

$\mathop {\min }\limits_\Phi - \log \Pr (\{ {v_{i - w}},...,{v_{i - 1}},{v_{i + 1}},...,{v_{i + w}}\} |\Phi ({v_i}))$ （2）

我们发现这些放松对于社区表征学习特别理想。首先，顺序无关假设更好地捕捉了随机游走提供的“近似”感。此外，这种松弛对于通过构建小模型来加快训练时间非常有用，因为一次给出一个顶点。
从式（2）中解决优化问题的方法是建立表示方法，捕捉顶点之间在局部图结构中的共享相似性。具有相似邻域的顶点将获得相似的表示(编码相似性)，并允许在机器学习任务中进行泛化。
通过结合截断的随机游走和神经语言模型，我们制定了一种方法，满足所有我们想要的性质。该方法生成了低维的、存在于连续向量空间中的社交网络的表示。它的表示方法编码了潜在的社群成员形式，并且由于该方法输出有用的中间表示，它可以适应不断变化的网络拓扑。

方法

在本节中，我们将讨论算法的主要组成部分。我们还介绍了几种方法的变体，并讨论了它们的优点。

回顾

与任何语言建模算法一样，唯一需要的输入是语料库和词汇 $V$ 。DeepWalk 将一组短截断随机游走视为自己的语料库，并将图顶点视为自己的词汇表 ( $v = V$ )。虽然在训练之前了解随机游走中的 $V$ 和顶点频率分布是有益的，但并不是算法正常工作所必需的，正如我们将在4.2.2中展示的那样。

算法:DeepWalk

该算法由两个主要部分组成；第一个是随机游走生成器，第二个是更新过程。
随机游走生成器采用图 $G$ 并均匀采样随机顶点 ${v_i}$ 作为随机游走序列 ${W_{{v_i}}}$ 的起始节点。游走从当前访问的顶点的邻居节点中均匀采样，直到达到最大长度 ( $t$ )。虽然在实验中我们将随机游走的长度固定为特定值，但并没有限制随机游走必须具有相同的长度。这些随机游走可以具有重新启动（即返回到其根的跳转概率），但我们的初步结果没有显示使用重新启动会带来任何优势。实际上，我们的实现指定了从每个顶点开始的多个长度为 $t$ 的随机游走 $y$ 。
在这里插入图片描述
算法 1 中的第 3-9 行显示了我们方法的核心。外循环指定我们应该在每个顶点开始随机游走的次数 $y$ 。我们认为每次迭代都是对数据进行“传递”，并在传递过程中对每个节点进行一次遍历。在每次传递开始时，我们都会生成一个随机顺序来遍历顶点。这不是严格要求的，但众所周知可以加速随机梯度下降的收敛。
在内部循环中，我们迭代图的所有顶点。对于每个顶点 ${v_i}$ ，我们生成一个随机游走 $\left| {{W_{{v_i}}}} \right| = t$ ，然后用它来更新我们的表示（第 7 行）。我们使用 SkipGram 算法 [26] 根据方程中的目标函数来更新这些表示。
在这里插入图片描述

SkipGram

SkipGram 是一种语言模型，可最大化句子中窗口 $w$ 内出现的单词之间的共现概率 [26]。算法 2 迭代出现在窗口 $w$ 内的随机游走中的所有可能的搭配（第 1-2 行）。对于每个顶点，我们将每个顶点 ${v_j}$ 映射到其当前表示向量 $\Phi ({v_j}) \in {R^d}$ （见图 3b）。对于给定 ${v_j}$ 的表示，我们希望最大化其邻居在随机游走中的概率（第 3 行）。我们可以使用多种分类器选择来学习这种后验分布。例如，使用逻辑回归对前面的问题进行建模将产生大量等于 $\left| V \right|$ 的标签，这可能是数百万或数十亿。此类模型需要大量的计算资源，这些资源可能跨越整个计算机集群 [3]。为了加快训练时间，可以使用 Hierarchical Softmax [29,30] 来近似概率分布。
在这里插入图片描述

优化

模型参数集为 $\{ \Phi ,T\}$ ，其中每个参数的大小为 $O(d\left| V \right|)$ 。随机梯度下降 (SGD) [4] 用于优化这些参数（第 4 行，算法 2）。使用反向传播算法来估计导数。SGD 的学习率 $\alpha$ 在训练开始时最初设置为 2.5%，然后随着迄今为止看到的顶点数量线性下降。

并行

如图 2 所示，社交网络随机游走中的顶点频率分布和语言中的单词都遵循幂律。这会导致不频繁顶点的长尾，因此，影响 Φ 的更新本质上是稀疏的。这允许我们在多工作人员的情况下使用异步版本的随机梯度下降（ASGD）。鉴于我们的更新是稀疏的，并且我们没有获取访问模型共享参数的锁，ASGD 将实现最佳收敛速度 [36]。当我们使用多线程在一台机器上运行实验时，已经证明该技术具有高度可扩展性，并且可以用于超大规模机器学习[8]。图 4 显示了并行化 DeepWalk 的效果。它表明，当我们将工作线程数量增加到 8 时，BlogCatalog 和 Flickr 网络的处理速度是一致的（图 4a）。它还表明，相对于串行运行的 DeepWalk，预测性能没有损失（图 4b）。
在这里插入图片描述

算法变体

在这里，我们讨论我们提出的方法的一些变体，我们认为这些变体可能会令人感兴趣。

流式方法

这种方法的一个有趣的变体是流式方法，它可以在不了解整个图的情况下实现。在这个变体中，图中的小步直接传递到表示学习代码，并且模型直接更新。对学习过程进行一些修改也是必要的。首先，使用衰减的学习率将不再可能。相反，我们可以将学习率 $\alpha$ 初始化为一个小的常数值。这将需要更长的时间来学习，但在某些应用程序中可能是值得的。其次，我们不一定再构建参数树。如果 $V$ 的基数已知（或可以有界），我们可以为该最大值构建分层 Softmax 树。当第一次看到顶点时，可以将它们分配给剩余的叶子之一。如果我们有能力先验地估计顶点频率，我们仍然可以使用霍夫曼编码来减少频繁的元素访问时间。

非随机游走

一些图是由与一系列元素进行交互的代理创建的（例如，用户在网站上导航页面）。当图由这样的非随机游走流创建时，我们可以直接利用这个过程来提供给建模阶段。以这种方式采样的图不仅可以捕捉与网络结构相关的信息，还可以捕捉路径被遍历的频率。
我们认为，这种变体还包含语言建模。句子可以被视为通过适当设计的语言网络的有目的的行走，而像 SkipGram 这样的语言模型就是为了捕捉这种行为而设计的。
这种方法可以与流变体（第 4.4.1 节）结合起来，在不断发展的网络上训练特征，而无需显式构建整个图。使用这种技术维护表示可以实现网络规模分类，而无需处理网络规模图的麻烦。

实验设计

在本节中，我们概述了我们将在实验中使用的数据集和方法。用于重现我们结果的代码和数据将在第一作者的网站上提供。

数据集

实验使用了三个数据集：BlogCatalog、Flickr 和 YouTube
在这里插入图片描述

基线方法

为了验证我们方法的性能，我们将其与许多基线进行比较：SpectralClustering、Modularity、EdgeCluster、wvRN、Majority。

实验

在本节中，我们将对我们的方法进行实验分析。我们在许多多标签分类任务上对其进行了全面评估，并分析了其在多个参数上的敏感性。

多标签分类

为了便于我们的方法和相关基线之间的比较，我们使用与[39, 40]中完全相同的数据集和实验程序。具体来说，我们随机采样标记节点的一部分（ ${T_R}$ ），并将它们用作训练数据。其余节点用作测试。我们重复此过程 10 次，并报告 Macro-F1 和 Micro-F1 的平均性能。如果可能的话，我们直接在此处报告原始结果 [39, 40]。
对于所有模型，我们使用 LibLinear [10] 实现的一对剩余逻辑回归进行分类。我们给出 DeepWalk 的结果（ $y$ = 80， $w$ = 10， $d$ = 128）。（SpectralClustering、Modularity、EdgeCluster）的结果使用 Tang 和 Liu 的首选维度 $d$ = 500。
在这里插入图片描述

表2所示，DeepWalk 的性能始终优于 EdgeCluster、Modularity 和 wvRN。当仅使用 20% 的标记节点进行训练时，DeepWalk 比提供 90% 的数据时的其他方法表现更好。当标记数据在 Macro-F1 (TR ≤ 20%) 和 Micro-F1 (TR ≤ 60%) 上稀疏时，DeepWalk 仍然表现出色。DeepWalk 可以扩展到大型图，并且在这种稀疏标记的环境中表现得非常好。（一句话：DeepWalk比其他方法好）

参数灵敏度

为了评估 DeepWalk 参数化的变化如何影响其在分类任务上的性能，我们在两个多标签分类任务（Flickr 和 BlogCatalog）上进行了实验。对于此测试，我们将窗口大小和行走长度固定为合理值（ $w$ = 10， $t$ = 40），这应该强调局部结构。然后，我们改变潜在维度的数量 ( $d$ )、每个顶点开始的行走次数 ( $y$ ) 以及可用训练数据量 ( ${T_R}$ )，以确定它们对网络分类性能的影响。

维度 $d$ 的影响

在这里插入图片描述
图 5a1 和 5a3 检查了改变维度和训练率的影响。Flickr 和 BlogCatalog 之间的性能非常一致，并且表明模型的最佳维度取决于训练示例的数量。（请注意，1% 的 Flickr 的标记示例大约与 10% 的 BlogCatalog 一样多）。
图 5a2 和 5a3 检查了改变维度和每个顶点的行走次数的影响。在不同的 $y$ 值下，维度之间的相对性能相对稳定。首先，在两个图中，每个节点执行 $y$ = 30步可以获得大部分的信息。第二，不同 $y$ 值之间的相对差异在两幅图之间是相当一致的。
他们还表明，模型的性能取决于它所经历的随机游走的数量，并且模型的适当维度取决于可用的训练示例。

随机游走次数 $y$ 的影响

图 5a 显示了增加 $y$ （我们从每个顶点开始的随机游走次数）的效果。对于不同维度（图5b1，图5b3）和训练数据量（图5b2，图5b4），结果非常一致。最初，增加 $y$ 对结果有很大影响，但这种影响很快就会减慢（ $y$ > 10）。这些结果表明，我们只需进行少量的随机游走就能够学习有意义的顶点潜在表示。
在这里插入图片描述

结论

我们提出了 DeepWalk，一种学习顶点潜在社会表征的新方法。使用截断随机游走的局部信息作为输入，我们的方法学习编码结构规律的表示。对各种不同图的实验说明了我们的方法在具有挑战性的多标签分类任务上的有效性。
作为一种在线算法，DeepWalk 也具有可扩展性。我们的结果显示，我们可以为图创建有意义的表示，这些图对于运行谱方法来说太大了。在这样大的图上，我们的方法在显著优于其他设计用于处理稀疏性的方法。我们还展示了我们的方法是可并行的，允许多个工作进程同时更新模型的不同部分。
除了有效和可扩展之外，我们的方法也是语言建模的一种有吸引力的概括。这种联系是互惠互利的。语言建模的进步可能会继续为网络产生改进的潜在表示。在我们看来，语言建模实际上是从不可观察的语言图中进行采样。我们相信，从可观察图建模中获得的见解反过来可能会改进不可观察图建模。
在这个领域，我们未来的工作将重点研究这种二元性，利用我们的结果来改进语言建模，并加强该方法的理论基础。