八、GraphSage

1. 在大型Graph 中，顶点的低维embedding 在从内容推荐到蛋白质功能识别等各项任务中都非常有效。

   之前的工作都集中在从单个指定的图来学习顶点 embedding，这些方法都是 transductive 的。但是，很多实际应用需要为从未见过的顶点或者全新的图来快速生成 embedding ，即需要 inductive 能力。这种 inductive 能力对于生产中的机器学习系统至关重要，这些机器学习系统需要在不断变化的图上运行，并不断遇到从未见过的顶点（如 Youtube 上的新用户、新视频）。 另外这种 inductive 能力还可以促进图的泛化，例如我们在已知的分子结构图上训练模型，然后该模型可以为新的分子图产生顶点 embedding 。

   • 与 transductiv 相比，inductive 的顶点 embedding 更为困难，因为这需要泛化到从未就按过的顶点。而这需要将新观察到的子图 “对齐” 到模型已经训练过的旧的子图。inductive 框架必须学会识别顶点邻域的结构属性，从而识别每个顶点（包括新发现的顶点）在图的局部角色以及全局位置。

   • 大多数现有的顶点embedding 方法本质都是 transductive 的。这些方法都使用基于矩阵分解来直接优化每个顶点的 embedding 。因为它们是在单个固定的图上对顶点进行训练和预测，因此天然地无法推广到未见过的顶点。

     也可以修改这些方法来满足inductinve 的要求， 如针对新的未见过的顶点进行若干轮额外的梯度下降。但是这种方式的计算代价较高，也容易导致顶点 embedding 在重新训练期间发生漂移。

   最近也有通过图卷积（如Semi-Supervised GCN ）来学习图结构的方法，但是这些方法也是以 transductive 的方式在使用。论文《Inductive Representation Learning on Large Graphs》 提出了一个通用的、称作 Graph Sample and Aggregage:GraphSAGE 的学习框架，该框架将图卷积推广到 inductinve 无监督学习。

2. GraphSage 是一种inductive 的顶点 embedding 方法。与基于矩阵分解的embedding 方法不同，GraphSage 利用顶点特征（如文本属性、顶点画像信息、顶点的degree 等）来学习，并泛化到从未见过的顶点。

   • 通过将顶点特征融合到学习算法中，GraphSage 可以同时学习每个顶点的邻域拓扑结构，以及顶点特征在邻域中的分布。GraphSage 不仅可以应用于顶点特征丰富的图（如引文网络、生物分子网络），还可以应用到没有任何顶点特征的简单的图，此时可以采用顶点的结构属性来作为顶点特征（如顶点degree ）。
   • GraphSage 并没有为每个顶点训练一个 embedding，而是训练了一组聚合函数，这些聚合函数用于从顶点的局部邻域中聚合信息特征。在测试期间，我们使用训练好的模型的聚合函数来为从未见过的顶点生成 embedding 。

   

3. 和之前的 embedding 方法类似，GraphSage 设计了一个无监督损失函数。该损失函数允许对GraphSage 进行无监督训练，而无需任何特定于具体任务监督信息。论文还展示了以监督方式来训练 GraphSage 。

   论文在三个顶点分类 benchmark 上评估了GraphSave 方法，从而验证了GraphSage 在从未见过的数据上具有优秀的顶点 embedding 能力。

   最后论文研究了 GraphSave 的表达能力，并通过理论分析证明了：虽然GraphSage 是基于顶点特征的，但是它能够学得顶点在图中角色的结构信息。

4. GraphSave 方法和 Semi-Supervised GCN 密切相关。原始的 Semi-Supervised GCN 以 transductive 的方式进行半监督学习，这要求在训练过程中已知完整的图拉普拉斯算子。GraphSage 的一个简单变种可以视为 Semi-Supervised GCN 框架以 inductive 方式的扩展。

8.1 模型

1. GraphSage 的核心思想是：学习如何从顶点的局部邻域中汇聚特征信息，如邻域内顶点的文本特征或者顶点degree 特征。

8.1.1 前向传播

1. 假设我们已经学到了 个聚合函数 ，这些聚合函数用于聚合顶点的邻域信息。假设我们也学到了 个权重矩阵 ，它们用于在不同层之间传递信息。 也称作搜索深度。

   GraphSage 的embedding 生成算法为：

   • 输入：

     • 图
     • 输入特征
     • 搜索深度
     • 权重矩阵
     • 非线性激活函数
     • 个聚合函数
     • 邻域函数

   • 输出：顶点的embedding 向量

   • 算法步骤：

     • 初始化：

     • 对每一层迭代，迭代条件为： 。迭代步骤：

       • 遍历每个顶点 ，执行：

         

       • 对每个顶点 的隐向量归一化：

         

     • 。

2. GraphSage 前向传播算法的基本思想是：在网络的每一层，顶点都会聚合来自其局部邻域的信息；并且随着层的逐渐加深，顶点将从图的更远范围逐渐获取越来越多的信息。

   在第 层，每个顶点 首先聚合其邻域顶点的信息 到一个向量 中，这个聚合过程依赖于第 层的顶点隐向量。然后每个顶点 拼接它的第 层 representation 和邻域信息 ，然后通过一个全连接层，并使用一个非线性激活函数 。

   最终在第 层， 有 。

3. 大多数顶点 embedding 方法将学到的 embedding 归一化为单位向量，这里我们也做类似处理。

8.1.2 邻域

1. 在GraphSage 中我们并没有使用完整的邻域，而是均匀采样一组固定大小的邻域，从而确保每个 batch 的计算代价是固定的。因此我们定义 为：从集合 中均匀采样的、固定大小的集合。

   • 对于每个顶点 , GraphSage 在每一层采样不同的邻域，甚至不同层的邻域大小都不同。
   • 如果对每个顶点使用完整的邻域，则每个 batch 的内存需求和运行时间是不确定的，最坏情况为 。如果使用采样后的邻域，则每个 batch 的时间和空间复杂度固定为 ，其中 表示第 层邻域大小。 以及 均为用户指定的超参数，实验发现 时的效果较好。

8.1.3 聚合函数

1. 和网格型数据（如文本、图像）不同，图的顶点之间没有任何顺序关系，因此算法中的聚合函数必须能够在无序的顶点集合上运行。理想的聚合函数是对称的，同时保持较高的表达能力。对称性是指：对于给定的一组顶点集合，无论它们以何种顺序输入到聚合函数，聚合后的输出结果不变。这种对称性可以确保我们的神经网络模型可以用于任意顺序的顶点邻域集合的训练和测试。

   聚合函数有多种形式，论文给出了三种主要的聚合函数：均值聚合函数mean aggregator、LSTM聚合函数LSTM aggregator 、池化聚合函数 pooling aggregator。

2. mean aggregator：简单的使用邻域顶点的特征向量的逐元素均值来作为聚合结果。这几乎等价于 Semi-Supervised GCN 框架中的卷积传播规则。

   如果我们将前向传播：

   

   替换为：

   

   则这得到 Semi-supervised GCN 的一个 inductive 变种，我们称之为mean-based aggregator convolutional 基于均值聚合的卷积。它是局部频域卷积的一个粗糙的线性近似。

3. LSTM aggregator ：和均值聚合相比，LSTM 具有更强大的表达能力。但是 LSTM 原生的是非对称的，它依赖于顶点的输入顺序。因此论文通过将 LSTM 应用于邻域顶点的随机排序，从而使得 LSTM 可以应用于无序的顶点集合。

4. pooling aggregator ：邻域每个顶点的特征向量都通过全连接神经网络独立馈入，然后通过一个逐元素的最大池化来聚合邻域信息：

   

   其中 max 表示逐元素的 max 运算符。

   • 理论上可以在最大池化之前使用任意深度的多层感知机，但是论文这里专注于简单的单层网络结构。

     直观上看，可以将多层感知机视为一组函数，这组函数为邻域集合内的每个顶点representation 计算特征。通过将最大池化应用到这些计算到的特征上，模型可以有效捕获邻域集合的不同特点aspect。

   • 理论上可以使用任何的对称向量函数（如均值池化）来替代 max 运算符。但是论文在测试中发现最大池化和均值池化之间没有显著差异，因此论文专注于最大池化。

8.1.4 模型学习

1. 和 DeepWalk 等方法相同，为了在无监督条件下学习有效的顶点representation，论文定义了一个损失函数：

   

   其中 为顶点 的 representation， 是和顶点 在一个长度为 的 random walk 上共现的顶点， 为sigmoid 函数， 为负采样用到的分布函数， 为负采样的样本数。

   这个损失函数鼓励距离较近的顶点具有相似的 representation、距离较远的顶点具有不相似的 representation 。

   • 与之前的 embedding 方法不同，GraphSage 中的顶点 representation 不仅包含了顶点的结构信息（通过 embedding look-up 得到），还包含了顶点局部邻域的特征信息。
   • 模型参数通过损失函数的随机梯度下降算法来求解。
2. 以无监督方式学到的顶点 embedding 可以作为通用 service 来服务于下游的机器学习任务。但是如果仅在特定的任务上应用，则可以进行监督学习。此时可以通过具体任务的目标函数（如交叉熵损失）来简单的替换无监督损失，或者将监督损失加上无监督损失来融合二者。

8.1.5 GraphSage VS Weisfeiler-Lehman

1. GraphSage 算法在概念上受到图的同构性检验的经典算法的启发。在前向传播过程中，如果令 、，并选择合适的hash 函数来作为聚合函数，同时移除非线性函数，则该过程是 Weisfeiler-Lehman:WL 同构性检验算法的一个特例，被称作 naive vertex refinement 。

   如果算法输出的顶点 representation 在两个子图是相等的，则 WL 检验算法认为这两个子图是同构的。虽然在某些情况下该检验会失败，但是大多数情况下该检验是有效的。

2. GraphSage 是 WL test 算法的一个continous 近似，其中GraphSage 使用可训练的神经网络聚合函数代替了不连续的哈希函数。

   虽然 GraphSage 的目标是生成顶点的有效embedding 而不是检验图的同构性，但是GraphSage 和 WL test 之间的联系为我们学习顶点邻域拓扑结构算法的设计提供了理论背景。

3. 可以证明：即使我们提供的是顶点特征信息，GraphSage 也能够学到图的结构信息。证明见原始论文。

8.1.6 mini-batch 训练

1. 为了使用随机梯度下降算法，我们需要对GraphSage 的前向传播算法进行修改，从而允许mini-batch 中每个顶点能够执行前向传播、反向传播。即：确保前向传播、反向传播过程中用到的顶点都在同一个 mini-batch 中。

2. GraphSage mini-batch 前向传播算法：

   • 算法输入：

     • 图
     • 输入特征
     • 搜索深度
     • 权重矩阵
     • 非线性激活函数
     • 个聚合函数
     • 邻域函数

   • 输出：顶点的embedding 向量

   • 算法步骤：

     • 初始化：

     • 迭代 ，迭代步骤为：

       • 
       • 遍历 ，计算

     • 初始化：

     • 对每一层迭代，迭代条件为： 。迭代步骤：

       • 遍历每个顶点 ，执行：

         

       • 对每个顶点 的隐向量归一化：

         

     • 。

3. 在 mini-batch 前向传播算法中：

   • 首先计算mini-batch 需要用到哪些顶点。集合 包含了第 层计算 representation 的顶点所依赖的顶点集合。

     由于 ，所以在计算 时依赖的 已经在第 层被计算。另外第 层需要计算 representation 的顶点更少，这避免计算不必要的顶点。

   • 然后计算目标顶点的 representation，这一步和 batch 前向传播算法相同。

4. 我们使用 的 来表明：不同层之间使用独立的 random walk 采样。这里我们使用均匀采样，并且当顶点邻域顶点数量少于指定数量时采用有放回的采样，否则使用无放回的采样。

5. 和 batch 算法相比，mini-batch 算法的采样过程在概念上是相反的：

   • 在 batch 算法中，我们在 时对顶点邻域内的 个顶点进行采样，在 时对顶点邻域内 个顶点进行采样。
   • 在 mibi-batch 算法中，我们在 时对顶点领域内的 个顶点进行采样，然后在 时对顶点领域内 个顶点进行采样。这样才能保证我们的目标 中包含 mibi-batch 所需要计算的所有顶点。

8.2 实验

1. 我们在三个 benchmark 任务上检验 GraphSage 的效果：Web of Science Citation 数据集的论文分类任务、Reddit 数据集的帖子分类任务、PPI 数据集的蛋白质分类任务。

   前两个数据集是对训练期间未见过的顶点进行预测，最后一个数据集是对训练期间未见过的图进行预测。

2. 数据集：

   • Web of Science Cor Collection 数据集：包含 2000 年到 2005 年六个生物学相关领域的所有论文，每篇论文属于六种主题类别之一。数据集包含 302424 个顶点，顶点的平均degree 为 9.15 。其中：Immunology 免疫学的标签为NI，顶点数量 77356 ；Ecology 生态学的标签为 GU，顶点数量 37935 ；Biophysics 生物物理学的标签为DA，顶点数量 36688 ；Endocrinology and Metabolism 内分泌与代谢的标签为 IA ，顶点数量 52225 ；Cell Biology 细胞生物学的标签为 DR，顶点数量84231；Biology(other) 生物学其它的标签为 CU，顶点数量 13988 。

     任务目标是预测论文主题的类别。我们根据 2000-2004 年的数据来训练所有算法，并用 2005 年的数据进行进行测试（其中 30% 用于验证）。

     我们使用顶点degree 和文章的摘要作为顶点的特征，其中顶点摘要根据Arora 等人的方法使用 sentence embedding 方法来处理文章的摘要，并使用Gensim word2vec 的实现来训练了300 维的词向量。

   • Reddit 数据集：包含2014 年 9 月Reddit 上发布帖子的一个大型图数据集，顶点为帖子所属的社区。我们对 50 个大型社区进行采样，并构建一个帖子到帖子的图。如果一个用户同时在两个帖子上发表评论，则这两个帖子将链接起来。数据集包含 232965 个顶点，顶点的平均degree 为 492 。

     为了对社区进行采样，我们按照每个社区在 2014 年的评论总数对社区进行排名，并选择排名在 [11,50]（包含）的社区。我们忽略了最大的那些社区，因为它们是大型的、通用的默认社区，会严重扭曲类别的分布。我们选择这些社区上定义的最大连通图largest connected component 。

     任务的目标是预测帖子的社区community。我们将该月前20 天用于训练，剩下的天数作为测试（其中 30% 用于验证）。

     我们使用帖子的以下特征：标题的平均embedding、所有评论的平均 embedding、帖子评分、帖子评论数。其中embedding 直接使用现有的 300 维的 GloVe CommonCral 词向量，而不是在所有帖子中重新训练。

   • PPI 数据集：包含Molecular Signatures Dataset 中的图，每个图对应于不同的人类组织，顶点标签采用gene ontology sets ，一共121 种标签。平均每个图包含 2373 个顶点，所有顶点的平均 degree 为 28.8 。

     任务的目的是评估模型的跨图泛化的能力。我们在 20 个随机选择的图上进行训练、2 个图进行验证、 2 个图进行测试。其中训练集中每个图至少有 15000 条边，验证集和测试集中每个图都至少包含 35000 条边。注意：对于所有的实验，验证集和测试集是固定选择的，训练集是随机选择的。我们最后给出测试图上的 micro-F1 指标。

     我们使用positional gene sets、motif gene sets 以及 immunological signatures 作为顶点特征。我们选择至少在 10% 的蛋白质上出现过的特征，低于该比例的特征不被采纳。最终顶点特征非常稀疏，有 42% 的顶点没有非零特征，这使得顶点之间的链接非常重要。

3. Baseline 模型：随机分类器、基于顶点特征的逻辑回归分类器（完全忽略图的结构信息）、代表因子分解方法的 DeepWalk 算法+逻辑回归分类器（完全忽略顶点的特征）、拼接了 DeepWalk 的 embedding 以及顶点特征的方法（融合图的顶点特征和结构特征）。

   我们使用了不同聚合函数的 GraphSage 的四个变体。由于卷积的变体是 Semi-Supervised GCN 的 inductive 扩展，因此我们称其为 GraphSage-GCN 。

   我们使用了 GraphSage 的无监督版本，也直接使用分类交叉熵作为损失的有监督版本。

4. 模型配置：

   • 所有GraphSage 模型都在 Tensorflow 中使用 Adam 优化器实现， DeepWalk 在普通的随机梯度优化器中表现更好。

   • 为公平比较，所有模型都采样相同的 mini-batch 迭代器、损失函数（当然监督损失和无监督损失不同）、邻域采样器。

   • 为防止 GraphSage 聚合函数的效果比较时出现意外的超参数hacking，我们对所有 GraphSage 版本进行了相同的超参数配置：根据验证集的性能为每个版本提供最佳配置。

   • 对于所有的 GraphSage 版本设置 K=2 以及邻域采样大小 。

   • 对于所有的 GraphSage ，我们对每个顶点执行以该顶点开始的 50 轮长度为 5 的随机游走序列，从而得到pair 顶点对。我们的随机游走序列生成完全基于 Python 代码实现。

   • 对于原生特征模型，以及基于无监督模型的 embedding 进行预测时，我们使用 scikit-learn 中的 SGDClassifier 逻辑回归分类器，并使用默认配置。

   • 在所有配置中，我们都对学习率和模型的维度以及batch-size 等等进行超参数选择：

     • 除了 DeepWalk 之外，我们为监督学习模型设置初始学习率的搜索空间为 ，为无监督学习模型设置初始学习率的搜索空间为 。

       最初实验表明 DeepWalk 在更大的学习率下表现更好，因此我们选择它的初始学习率搜索空间为 。

     • 我们测试了每个GraphSage模型的big 版本和 small 版本。 对于池化聚合函数，big 模型的池化层维度为 1024，small 模型的池化层维度为 512 ；对于 LSTM 聚合函数，big 模型的隐层维度为 256，small 模型的隐层维度为 128 。

     • 所有实验中，我们将GraphSage 每一层的 的维度设置为 256。

     • 所有的 GraphSage 以及 DeepWalk 的非线性激活函数为 ReLU 。

     • 对于无监督 GraphSage 和 DeepWalk 模型，我们使用 20 个负采样的样本，并且使用 0.75 的平滑参数对顶点的degree 进行上下文分布平滑。

     • 对于监督 GraphSage，我们为每个模型运行 10 个 epoch 。

     • 我们对 GraphSage 选择 batch-size = 512。对于 DeepWalk 我们使用 batch-size=64，因为我们发现这个较小的 batch-size 收敛速度更快。

5. 硬件配置：DeepWalk 在CPU 密集型机器上速度更快，它的硬件参数为 144 core 的 Intel Xeon CPU(E7-8890 V3 @ 2.50 GHz) ，2T 内存。其它模型在单台机器上实验，该机器具有 4 个 NVIDIA Titan X Pascal GPU( 12 Gb 显存, 10Gbps 访问速度)， 16 core 的Intel Xeon CPU(E5-2623 v4 @ 2.60GHz)，以及 256 Gb 内存。

   所有实验在共享资源环境下大约进行了3 天。论文预期在消费级的单 GPU 机器上（如配备了 Titan X GPU ）的全部资源专用，可以在 4 到 7 天完成所有实验。

6. 对于 Reddit 和引文数据集，我们按照 Perozzi 等人的描述对 DeepWalk 执行 oneline 训练。对于新的测试顶点，我们进行了新一轮的 SGD 优化，从而得到新顶点的 embedding 。

   现有的 DeepWalk 实现仅仅是 word2vec 代码的封装，它难以支持 embedding 新顶点以及其它变体。这里论文根据 tensorflow 中的官方 word2vec 教程实现了 DeepWalk 。为了得到新顶点的 embedding，我们在保持已有顶点的 embedding 不变的情况下，对每个新的顶点执行 50 个长度为 5 的随机游走序列，然后更新新顶点的 embedding 。

   • 论文还测试了两种变体：一种是将采样的随机游走“上下文顶点”限制为仅来自已经训练过的旧顶点集合，这可以缓解统计漂移；另一种是没有该限制。我们总数选择性能最强的那个。

   • 尽管 DeepWalk 在 inductive 任务上的表现很差，但是在 transductive 环境下测试时它表现出更强的竞争力。因为在该环境下 DeepWalk 可以在单个固定的图上进行持续的训练。

     我们观察到在 inductive 环境下 DeepWalk 的性能可以通过进一步的训练来提高。并且在某种情况下，如果让它比其它方法运行的时间长 1000 倍，则它能够达到与无监督 GraphSage （而不是 有监督 GraphSage ）差不多的性能。但是我们不认为这种比较对于 inductive 是有意义的。

7. 在 PPI 数据集中我们无法应用 DeepWalk，因为在不同的、不相交的图上运行 DeepWalk 算法生成的 embedding 空间可以相对于彼此任意旋转。参考最后一小节的证明。

8. 由于顶点 degree 分布的长尾效应，我们将 GraphSage 算法中所有图的边执行降采样预处理。经过降采样之后，使得没有任何顶点的 degree 超过 128 。由于我们每个顶点最多采样 25 个邻居，因此这是一个合理的权衡。

9. GraphSage 及 baseline 在这三个任务上的表现如下表所示。这里给出的是测试集上的 micro-F1 指标，对于 macro-F1 结果也有类似的趋势。其中 Unsup 表示无监督学习，Sup 表示监督学习。

   • GraphSage 的性能明显优于所有的 baseline 模型。
   • 根据 GraphSage 不同版本可以看到：与GCN 聚合方式相比，可训练的神经网络聚合函数具有明显的优势。
   • 尽管LSTM 这种聚合函数是为有序数据进行设计而不是为无序集合准备的，但是通过随机排列的方式，它仍然表现出出色的性能。
   • 和监督版本的 GraphSage 相比，无监督 GraphSage 版本的性能具有相当竞争力。这表明我们的框架无需特定于具体任务就可以实现强大的性能。

   

10. 通过在 Reddit 数据集上不同模型的训练和测试的运行时间如下表所示，其中 batch size = 512，测试集包含 79534 个顶点。

    这些方法的训练时间相差无几，其中 GraphSage-LSTM 最慢。除了 DeepWalk 之外，其它方法的测试时间也相差无几。由于 DeepWalk 需要采样新的随机游走序列，并运行多轮SGD 随机梯度下降来生成未见过顶点的 embedding，这使得 DeepWalk 在测试期间慢了 100~500 倍。

    

11. 对于 GraphSage 变体，我们发现和 相比，设置 使得平均准确率可以一致性的提高大约 10%~15% 。但是当 增加到 2 以上时会导致性能的回报较低（0~5%） ，但是运行时间增加到夸张的 10~100 倍，具体取决于采样邻域的大小。

    另外，随着采样邻域大小逐渐增加，模型获得的收益递减。因此，尽管对邻域的采样引起了更高的方差，但是 GraphSage 仍然能够保持较强的预测准确率，同时显著改善运行时间。下图给出了在引文网络数据集上 GraphSage-mean 模型采用不同邻域大小对应的模型性能以及运行时间，其中 以及 。

    

12. 总体而言我们发现就平均性能和超参数而言，基于 LSTM 聚合函数和池化聚合函数的表现最好。为了定量的刻画这种比较优势，论文将三个数据集、监督学习和无监督学习两种方式一共六种配置作为实验，然后使用 Wilcoxon Signed-Rank Test 来量化不同模型的性能。

    结论：

    • 基于 LSTM 聚合函数和池化聚合函数的效果确实最好。
    • 基于LSTM 聚合函数的效果和基于池化聚合函数的效果相差无几，但是由于 GraphSage-LSTM 比 GraphSage-pool 慢得多（大约2 倍），这使得基于池化的聚合函数总体上略有优势。

8.3 DeepWalk embedding 旋转不变性

1. DeepWalk,node2vec 以及其它类似的顶点 embedding 方法的目标函数都有类似的形式：

   

   其中 为平滑、连续的函数， 为直接优化的顶点的 embedding （通过 embedding 的 look up 得到）， 为满足某些条件的顶点 pair 对。

   事实上这类方法可以认为是一个隐式的矩阵分解 ，其中 的每一列代表一个顶点的 embedding ， 是一个包含某些随机游走统计量的矩阵。

   这类方法的一个重要结果是：embedding 可以通过任意单位正交矩阵变换，从而不影响矩阵分解：

   

   其中 为任意单位正交矩阵。所以整个embedding 空间在训练过程中可以自由旋转。

2. embedding 矩阵可以在 embedding 空间可以自由旋转带来两个明显后果：

   • 如果我们在两个单独的图 A 和 B 上基于 来训练 embedding 方法，如果没有一些明确的惩罚来强制两个图的顶点对齐，则两个图学到的 embedding 空间将相对于彼此可以任意旋转。因此，对于在图 A 的顶点 embedding 上训练的任何顶点分类模型，如果直接灌入图 B 的顶点 embedding ，这这等效于对该分类模型灌入随机数据。

     如果我们有办法在图之间对齐顶点，从而在图之间共享信息，则可以缓解该问题。研究如何对齐是未来的方向，但是对齐过程不可避免地在新数据集上运行缓慢。

     而 GraphSage 完全无需做额外地顶点对齐，它可以简单地为新顶点生成 embedding 信息。

   • 如果在时刻 对图 A 基于 来训练 embedding 方法，然后在学到的 embedding 上训练分类器。如果在时刻 ，图 A 添加了一批新的顶点，并通过运行新一轮的随机梯度下降来更新所有顶点的 embedding ，则这会导致两个问题：

     • 首先，类似于上面提到的第一点，如果新顶点仅连接到少量的旧顶点，则新顶点的 embedding 空间实际上可以相对于原始顶点的 embedding 空间任意旋转。
     • 其次，如果我们在训练过程中更新所有顶点的 embedding，则相比于我们训练分类模型所以来的原始 embedding 空间相比，我们新的 embedding 空间可以任意旋转。

3. 这类embedding 空间旋转问题对于依赖成对顶点距离的任务（如通过 embedding 的点积来预测链接）没有影响。

4. 缓解这类统计漂移问题（即embedding 空间旋转）的一些方法为：

   • 为新顶点训练 embedding 时，不要更新已经训练的 embedding 。
   • 在采样的随机游走序列中，仅保留旧顶点为上下文顶点，从而确保 skip-gram 目标函数中的每个点积操作都是一个旧顶点和一个新顶点。

   在 GraphSage 论文中，作者尝试了这两种方式，并始终选择效果最好的 DeepWalk 变体。

5. 从经验来讲，DeepWalk 在引文网络上的效果要比 Reddit 网络更好。因为和引文网络相比，Reddit 的这种统计漂移更为严重：Reddit 数据集中，从测试集链接到训练集的边更少。在引文网络中，测试集有 96% 的新顶点链接到训练集；在 Reddit 数据集中，测试集只有 73% 的新顶点链接到训练集。