William L. Hamilton∗，Rex Ying∗，Jure Leskovec
NIPS 2017

Abstract

Low-dimensional embeddings of nodes in large graphs have proved extremely useful in a variety of prediction tasks, from content recommendation to identifying protein functions. However, most existing approaches require that all nodes in the graph are present during training of the embeddings; these previous approaches are inherently transductive and do not naturally generalize to unseen nodes. Here we present GraphSAGE, a general inductive framework that leverages node feature information (e.g., text attributes) to efficiently generate node embeddings for previously unseen data. Instead of training individual embeddings for each node, we learn a function that generates embeddings by sampling and aggregating features from a node’s local neighborhood. Our algorithm outperforms strong baselines on three inductive node-classification benchmarks: we classify the category of unseen nodes in evolving information graphs based on citation and Reddit post data, and we show that our algorithm generalizes to completely unseen graphs using a multi-graph dataset of protein-protein interactions.

事实证明，在大型图中，节点的低维嵌入在从内容推荐到识别蛋白质功能的各种预测任务中极为有用。但是，大多数现有方法都要求在训练嵌入过程中存在图中的所有节点。这些先前的方法本质上是转导的（transductive），不能自然地推广到看不见的节点。在这里，我们介绍GraphSAGE，这是一个通用的 归纳（inductive） 框架，它利用节点特征信息（例如，文本属性）为先前未见的数据有效生成节点嵌入。我们将学习一个函数，该函数通过对节点局部（local）邻居的特征进行采样和聚合来生成嵌入，而不是为每个节点训练单独的嵌入。我们的算法在三个归纳（inductive）节点分类基准上均优于强基准：我们基于引文和 Reddit 发布数据在不断发展的信息图中将看不见的节点分类，并显示我们的算法使用蛋白质-蛋白质相互作用的多图数据集将其概括为完全看不见的图。

• 现存的方法需要图中所有的顶点在训练embedding的时候都出现；这些前人的方法本质上是transductive，不能自然地泛化到未见过的顶点。
• 本文提出了GraphSAGE，是一个 inductive 的框架，可以利用顶点特征信息（比如文本属性）来高效地为没有见过的顶点生成 embedding。
• GraphSAGE是为了学习一种节点表示方法，即如何通过从一个顶点的局部邻居采样并聚合顶点特征，而不是为每个顶点训练单独的embedding。
• 这个算法在三个inductive顶点分类benchmark上超越了那些很强的baseline。文中基于citation和Reddit帖子数据的信息图中对未见过的顶点分类，实验表明使用一个PPI（protein-protein interactions）多图数据集，算法可以泛化到完全未见过的图上。

0 GCN

在大型图中，节点的低维向量embedding被证明了作为各种各样的预测和图分析任务的特征输入是非常有用的。顶点embedding最基本的基本思想是使用降维技术从高维信息中提炼一个顶点的邻居信息，存到低维向量中。这些顶点嵌入之后会作为后续的机器学习系统的输入，解决像顶点分类、聚类、链接预测这样的问题。
GCN虽然能提取图中顶点的embedding，但是存在一些问题：（1）GCN的基本思想： 把一个节点在图中的高纬度邻接信息降维到一个低维的向量表示；（2）GCN的优点： 可以捕捉graph的全局信息，从而很好地表示node的特征；（3）GCN的缺点： Transductive learning的方式，需要把所有节点都参与训练才能得到 node embedding，无法快速得到新node的embedding。

• transductive learning
  转导学习在训练模型的时候，其实已经遇见了训练集和测试集。为什么说GCN是转导学习呢？因为训练模型的时候需要将整个图输入，然后得到 node embedding .
• inductive learning
  归纳学习在训练模型时仅会遇到训练数据，并将学习到的模型应用于从未见过的数据集上。

（1）归纳学习的重要性：前人的工作专注于从一个固定的图中对顶点进行表示，很多现实中的应用需要很快的对未见过的顶点或是全新的图（子图）生成embedding。这种推断的能力对于高吞吐的机器学习系统来说很重要，这些系统都运作在不断演化的图上，而且时刻都会遇到未见过的顶点（比如Reddit上的帖子（posts），Youtube上的用户或视频）。因此，一种inductive的学习方法比transductive的更重要；（2）转导学习的局限：要想得到新节点的表示，需要让新的graph或者subgraph去和已经优化好的node embedding去“对齐（align）”。然而每个节点的表示都是受到其他节点的影响，因此添加一个节点，意味着许许多多与之相关的节点的表示都应该调整。这会带来极大的计算开销，即使增加几个节点，也要完全重新训练所有的节点。

GraphSage的基本思想

直接学习一种节点的表示方法。去学习一个节点的信息是怎么通过其邻居节点的特征聚合而来的。 学习到了这样的“聚合函数”，而我们本身就已知各个节点的特征和邻居关系，我们就可以很方便地得到一个新节点的表示了。
GCN等 transductive 的方法，学到的是每个节点的一个唯一确定的 embedding； 而 GraphSAGE 方法学到的 node embedding，是根据 node 的邻居关系的变化而变化的，也就是说，即使是旧的node，如果建立了一些新的 link，那么其对应的 embedding 也会变化，而且也很方便地学到。
[PinSage] Graph Convolutional Neural Networks for Web-Scale Recommender Systems 论文详解KDD2018

1 Introduction

大图中节点的低维向量嵌入已被证明非常有用，可以作为各种预测和图分析任务的特征输入[5、11、28、35、36]。节点嵌入方法背后的基本思想是使用降维技术将有关节点邻域的高维信息提取为密集的矢量嵌入。然后，可以将这些节点嵌入提供给下游的机器学习系统，并帮助完成诸如节点分类，聚类和链接预测之类的任务[11、28、35]。
但是，以前的工作集中于从单个固定图嵌入节点，并且许多实际应用程序要求为看不见的节点或全新（子）图快速生成嵌入。这种归纳能力对于高吞吐量的生产机器学习系统至关重要，该系统在不断变化的图形上运行并不断遇到看不见的节点（例如Reddit上的帖子，Y outube上的用户和视频）。一种用于生成节点嵌入的归纳方法还可以促进具有相同特征形式的图的泛化：例如，可以在源自模型生物的蛋白质-蛋白质相互作用图上训练嵌入生成器，然后使用经过训练的模型轻松生成节点嵌入，以收集在新生物上收集的数据。
与转导模式相比，归纳式节点嵌入问题尤其困难，因为要泛化到看不见的节点，需要将新观察到的子图“对齐”到算法已经优化的节点嵌入。归纳框架必须学会识别节点邻域的结构属性，这些结构属性既可以显示节点在图中的局部角色，也​​可以显示其全局位置。
大多数现有的生成节点嵌入的方法本质上都是转导的。这些方法大多数都使用基于矩阵分解的目标直接优化了每个节点的嵌入，并且自然不会泛化为看不见的数据，因为它们在单个固定图上对节点进行了预测[5、11、23、28， 35、36、37、39]。可以修改这些方法以在归纳模式下运行（例如[28]），但是这些修改在计算上趋于昂贵，需要在进行新的预测之前进行额外的梯度下降回合。最近也有一些使用卷积算子学习图结构的方法，它们提供了作为嵌入方法的前景[17]。到目前为止，图卷积网络（GCN）仅在具有固定图的转导设置中应用[17，18]。在这项工作中，我们都将GCN扩展到归纳无监督学习的任务，并提出了一个框架，该框架将GCN方法推广为使用可训练的聚合函数（除了简单的卷积）。
Present work 我们提出了一个通用的框架，称为GraphSAGE（SAmple和aggreGatE），用于归纳节点嵌入。与基于矩阵分解的嵌入方法不同，我们利用节点特征（例如，文本属性，节点配置文件信息，节点度）来学习可泛化到看不见节点的嵌入特征。通过将节点特征整合到学习算法中，我们可以同时学习每个节点邻域的拓扑结构以及节点特征在邻域中的分布。尽管我们专注于特征丰富的图（例如具有文本属性的引文数据，具有功能/分子标记的生物学数据），但我们的方法还可以利用所有图形中存在的结构特征（例如节点度）。因此，我们的算法也可以应用于没有节点特征的图。
我们没有训练每个节点的嵌入矢量，而是训练了一组聚合器函数，这些函数学习从节点的局部邻居中聚合特征信息（图1）。每个聚合器函数都聚合来自给定节点的不同跳数或搜索深度的信息。在测试或推断时，我们使用受过训练的系统，通过应用学习到的聚合函数，为完全看不见的节点生成嵌入。在先前生成节点嵌入的工作之后，我们设计了一种无监督的损失函数，该函数允许对GraphSAGE进行训练而无需执行特定于任务的监督。我们还展示了可以完全监督的方式训练GraphSAGE。

我们在三个节点分类基准上评估了我们的算法，测试了GraphSAGE在看不见的数据上生成有用的嵌入的能力。我们使用两个基于引文数据和Reddit发布数据的演化文档图（分别预测论文和文章类别），以及基于蛋白质-蛋白质相互作用数据集（预测蛋白质功能）的多图概括实验。使用这些基准，我们证明了我们的方法能够有效地生成看不见的节点的表示形式，并且可以显著地胜过相关的基准：在整个域中，与仅使用节点特征相比，我们的监督方法可使分类F1分数平均提高51％，并且GraphSAGE始终优于强大的转导基线[28]，尽管该基线在看不见的节点上运行需要花费约100倍的时间。我们还表明，与受图卷积网络启发的聚合器相比，我们提出的新聚合器体系结构可带来可观的收益（平均7.4％）[17]。最后，我们探究了我们方法的表达能力，并通过理论分析表明GraphSAGE能够学习关于节点在图中的角色的结构信息，尽管事实上它是基于特征的（第5节）。

2 Related work

我们的算法在概念上与先前的节点嵌入方法，用于学习图的常规监督方法以及将卷积神经网络应用于图结构数据的最新进展相关。

Factorization-based embedding approaches

一些node embedding方法使用随机游走的统计方法和基于矩阵分解学习目标学习低维的embeddings

Grarep: Learning graph representations with global structural information. In KDD, 2015
node2vec: Scalable feature learning for networks. In KDD, 2016
Deepwalk: Online learning of social representations. In KDD, 2014
Line: Large-scale information network embedding. In WWW, 2015
Structural deep network embedding. In KDD, 2016

Supervised learning over graphs

一些神经网络方法用于图结构上的监督学习，本文的方法在概念上受到了这些算法的启发

Discriminative embeddings of latent variable models for structured data. In ICML, 2016
A new model for learning in graph domains
Gated graph sequence neural networks. In ICLR, 2015
The graph neural network model

Graph convolutional networks

近年来，提出了几种用于图上学习的卷积神经网络结构

Spectral networks and locally connected networks on graphs. In ICLR, 2014
Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016
Convolutional networks on graphs for learning molecular fingerprints. In NIPS,2015
Semi-supervised classification with graph convolutional networks. In ICLR, 2016
Learning convolutional neural networks for graphs. In ICML, 2016

GraphSAGE可以看作是对transductive的GCN框架对inductive下的扩展。

3 Proposed method: GraphSAGE

我们方法背后的关键思想是，我们学习如何从节点的局部邻域（例如，附近节点的度数或文本属性）中汇总要素信息。我们首先描述GraphSAGE嵌入生成（即前向传播）算法，该算法假设已经学习GraphSAGE模型参数，就会为节点生成嵌入（第3.1节）。然后，我们描述如何使用标准的随机梯度下降和反向传播技术来学习GraphSAGE模型参数（第3.2节）。

3.1 Embedding generation (i.e., forward propagation) algorithm

在本节中，我们描述了嵌入生成或前向传播算法（算法1），该算法假定模型已经过训练并且参数是固定的。尤其是，我们假设我们已经了解了 $K$ 个聚合函数的参数（表示为 $AGGREGATE_{k}, ∀k∈{1，...，K}$），这些参数聚合了来自节点邻居的信息以及一组权重矩阵 $W^k, ∀k∈{1，...，K}$，用于在模型的不同层或“搜索深度”之间传播信息。 3.2节介绍了我们如何训练这些参数。

算法1的直觉是，在每次迭代或搜索深度处，节点都会聚合来自其局部邻居的信息，并且随着此过程的反复进行，节点将从图的更远范围逐渐获取越来越多的信息。
算法1描述了在将整个图形 $\mathcal {G =(V，E)}$ 并提供所有节点的特征 $\mathbf x_v，∀v∈\mathcal V$ 作为输入的情况下的嵌入生成过程。我们将在下面介绍如何将其推广到 minibatch 模式。算法1外循环中的每个步骤如下进行，其中 $k$ 表示外循环中的当前步骤（或搜索的深度），并且 $h^k$ 在此步骤中表示节点的表示形式：首先，每个节点 $v∈\mathcal V$ 汇总表示形式将其相邻节点 ${\mathbf h^{k-1}_u，u∈\mathcal N(v)}$ 中的所有节点都放入单个向量 $\mathbf h^{k-1}_{N(v)}$。注意，该聚合步骤取决于在外循环的先前迭代（即，$k-1$）处生成的表示，并且将 $k ＝ 0$（“初始情况”）表示定义为输入节点特征。聚合相邻的特征向量后，然后，GraphSAGE 将节点的当前表示 $\mathbf h^{k-1}_v$ 与聚合的邻域向量 $\mathbf h^{k-1}_{N(v)}$ 串联在一起，并将此串联的向量馈送给具有非线性激活函数 $σ$ 的完全连接层，它转换了算法下一步要使用的表示形式（即 $\mathbf h^k_v，∀v∈\mathcal V$）。为了方便表示，我们将深度 $K$ 处的最终表示形式表示为 $\mathbf z_v≡\mathbf h^K_v，∀v∈\mathcal V$。相邻表示的集合可以通过各种聚合器体系结构（在算法1中由 AGGREGATE 占位符表示）完成，我们将在下面的第3.3节中讨论不同的体系结构选择。
Relation to the Weisfeiler-Lehman Isomorphism Test. GraphSAGE 算法在概念上受到测试图同构性的经典算法的启发。如果在算法1中，我们（i）设置 $K = | V |$，（ii）将权重矩阵设置为恒等，并且（iii）使用适当的哈希函数作为聚合器（没有非线性），则算法图1是Weisfeiler-Lehman（WL）同构测试的一个实例，也称为“朴素顶点细化” [32]。如果算法1为两个子图输出的表示集 $\{\mathbf z_v，∀v∈\mathcal V\}$ 相同，则 WL 测试将两个子图声明为同构。已知该测试在某些情况下会失败，但对于广泛的图类型来说是有效的[32]。 GraphSAGE 是 WL 测试的连续近似，其中我们用可训练的神经网络聚合器替换了哈希函数。当然，我们使用GraphSAGE生成有用的节点表示，而不是测试图形同构。尽管如此，GraphSAGE 和经典的WL测试之间的联系为我们的算法设计提供了理论背景，以学习节点邻域的拓扑结构。
Neighborhood definition. 在这项工作中，我们统一采样一组固定大小的邻居，而不是在算法1中使用完整邻域集，以使每个批次的计算足迹保持固定，即使用重载符号定义 $N(v)$ 作为集合 $\{u∈\mathcal V:(u，v)∈\mathcal E\}$ 的固定大小的均匀绘制，我们在算法1中的每次迭代 $k$ 上绘制了不同的均匀样本。单批次是不可预测的，最坏的情况是 $O(| \mathcal V |)$。相反，GraphSAGE的每个批处理空间和时间复杂度固定为 $O(\prod^K_{i = 1}S_i)$，其中 $S_i，i∈{1，...，K}$，$K$ 是用户指定的常数。实际上，我们发现我们的方法可以在 $K = 2$ 且 $S1·S2≤500$ 时实现高性能（有关详细信息，请参见第4.4节）。

• 设需要的邻居数量，即采样数量为 $S$，若顶点邻居数少于 $S$, 则采用有放回的抽样方法，直到采样出 $S$ 个顶点。若顶点邻居数大于 $S$，则采用无放回的抽样；
• 采样的方式获得的信息是有损的；
• 统一采样一个固定大小的邻域集，以保持每个batch的计算占用空间是固定的；
• 固定size的采样，每个节点和采样后的邻居的个数都相同，可以把每个节点和它们的邻居拼成一个batch送到GPU中进行批训练；
• 每一层的node的表示都是由上一层生成的，跟本层的其他节点无关，这也是一种基于层的采样方式；
• 没有这种采样，单个batch的内存和预期运行时是不可预测的，在最坏的情况下 $O(|\mathcal{V}|)$；
• 实验发现，$K$ 不必取很大的值，当 $K=2$ 时，效果就很好了。至于邻居的个数，文中提到 $S_1 \cdot S_2 \leq 500$，即两次扩展的邻居数之积小于500，大约每次只需要扩展 20 来个邻居时获得较高的性能；
• 本文提到的固定长度的随机游走其实就是随机选择了固定数量的邻居。

3.2 Learning the parameters of GraphSAGE

为了在完全无监督的情况下学习有用的预测表示，我们将基于图的损失函数应用于输出表示 $\mathbf z_u，∀u∈\mathcal V$，并调整权重矩阵 $W^k，∀k∈{1, ..., K}$ 和聚合函数的参数通过随机梯度下降来实现。基于图的损失函数鼓励附近的节点具有相似的表示形式，同时强制要求不同节点的表示形式非常不同：
$J_{\mathcal{G}}\left(\mathbf{z}_{u}\right)=-\log \left(\sigma\left(\mathbf{z}_{u}^{\top} \mathbf{z}_{v}\right)\right)-Q \cdot \mathbb{E}_{v_{n} \sim P_{n}(v)} \log \left(\sigma\left(-\mathbf{z}_{u}^{\top} \mathbf{z}_{v_{n}}\right)\right)\tag{1}$

其中 $v$ 是在固定长度随机游动上在 $u$ 附近共同出现的一个节点，$σ$ 是 sigmoid 函数，$P_n$ 是负采样分布，$Q$ 定义负采样的数量。重要的是，与以前的嵌入方法不同，我们提供给此损失函数的表示形式 $\mathbf z_u$ 是从节点局部邻域内包含的要素生成的，而不是为每个节点训练唯一的嵌入（通过嵌入查找）。

• 负采样分布指某种分布类型，一般采用均匀分布；
• 负采样的数量 $Q$ 一般等于 $总的样本数/正样本数$；
• embedding之间相似度通过向量点积计算得到。

此不受监督的设置模拟了将节点功能作为服务或静态存储库提供给下游机器学习应用程序的情况。如果仅在特定的下游任务上使用表示形式，则可以通过任务特定的目标（例如，交叉熵损失）简单地替换或增加无监督损失（等式1）。

3.3 Aggregator Architectures

与通过 N-D 格 lattices （例如句子，图像或 3-D volumes）进行机器学习不同，节点的邻居没有自然的顺序；因此，算法1中的聚合函数必须在无序向量集合上运行。理想情况下，聚合函数应该是对称的（即，对其输入的排列不变），同时仍可训练并保持较高的表示能力。聚合函数的对称性确保我们的神经网络模型可以被训练并应用于任意排序的节点邻域特征集。我们测试了三个候选聚合器函数：

Mean aggregator. 我们的第一个候选聚合函数是均值算子，在这里我们简单地取 ${h^{k-1}_u，∀u∈\mathcal N(v)}$ 中向量的元素均值。平均聚合器几乎等同于转导 GCN 框架中使用的卷积传播规则[17]。特别是，我们可以通过将算法1中的第4行和第5行替换为以下内容来得出 GCN 方法的归纳变量：
$\mathbf{h}_{v}^{k} \leftarrow \sigma\left(\mathbf{W} \cdot \operatorname{MEAN}\left(\left\{\mathbf{h}_{v}^{k-1}\right\} \cup\left\{\mathbf{h}_{u}^{k-1}, \forall u \in \mathcal{N}(v)\right\}\right)\right.\tag{2}$

我们称其为修正的基于均值的聚集器卷积，因为它是局部频谱卷积的粗略线性近似[17]。该卷积聚合器与我们提出的其他聚合器之间的重要区别在于，它不执行算法1第5行中的级联(concatenation)操作-即，卷积聚合器确实将节点的前一层表示 $h^{k-1}_v$ 与聚合的邻域矢量 $h^k_{N(v)}$ 进行了级联。可以将这种级联(concatenation)看作是GraphSAGE算法的不同“搜索深度”或“层”之间的“跳跃连接（ skip connection ）” [13]的简单形式，它可以显著提高性能（第4节）。
LSTM aggregator. 我们还研究了基于LSTM架构的更复杂的聚合器[14]。与平均聚合器相比，LSTM具有更大的表达能力的优势。但是，必须注意，LSTM并不是天生对称的（即它们不是排列不变的（permutation invariant）），因为它们以顺序方式处理其输入。我们只需将LSTM应用于节点邻居的随机排列，即可使LSTM适应无序集合。

• 排列不变性（permutation invariance）：指输入的顺序改变不会影响输出的值。

Pooling aggregator. 我们研究的最终聚合器既对称又可训练。在这种合并方法中，每个邻居的向量都通过全连接（fully-connected ）的神经网络独立地馈送；进行此转换之后，将逐元素最大池化操作（elementwise max-pooling operation）应用于跨邻居集的聚合信息：
$\text { AGGREGATE }_{k}^{\text {pool }}=\max \left(\left\{\sigma\left(\mathbf{W}_{\text {pool }} \mathbf{h}_{u_{i}}^{k}+\mathbf{b}\right), \forall u_{i} \in \mathcal{N}(v)\right\}\right)\tag{3}$

其中 $max$ 表示元素方式的 $max$ 运算符，而 $σ$ 是非线性激活函数。简言之，Pooling aggregator 先对目标顶点的邻居顶点的embedding向量进行一次非线性变换，之后进行一次pooling操作(max pooling or mean pooling)，将得到结果与目标顶点的表示向量拼接，最后再经过一次非线性变换得到目标顶点的第 $k$ 层表示向量。
原则上，在最大池化之前应用的功能可以是任意深度的多层感知器，但是在此工作中，我们专注于简单的单层体系结构。这种方法的灵感来自于应用神经网络体系结构学习通用点集的最新进展[29]。直观地，可以将多层感知器视为一组函数，这些函数为邻居集中的每个节点表示计算特征。通过将最大池运算符应用于每个计算出的特征，模型可以有效地捕获邻域集的不同方面。还应注意，原则上，可以使用任何对称向量函数代替 $max$ 运算符（例如，按元素的均值）。在开发测试中，我们发现最大池化和平均池化之间没有显着差异，因此在其余的实验中，我们将重点放在最大池化上。

4 Experiments

我们在以下三个基准任务上测试了GraphSAGE的性能：（i）使用Web of Science引文数据集将学术论文分类为不同的主题，（ii）将Reddit帖子归为不同社区的成员，以及（iii）跨各种生物蛋白质-蛋白质相互作用（PPI）图对蛋白质功能进行分类。第4.1节和第4.2节概述了数据集，补充材料中包含其他信息。在所有这些实验中，我们对训练期间看不到的节点进行预测，对于PPI数据集，我们对完全看不见的图进行测试。
Experimental set-up. 为了将我们的归纳基准上的经验结果进行情境化，我们将与四个基准进行比较：随机分类器，基于逻辑回归特征的分类器（忽略图结构），作为代表因数分解方法的DeepWalk算法[28]以及 Raw features 和DeepWalk嵌入的串联。我们还比较了使用不同聚合函数的GraphSAGE的四个变体（第3.3节）。由于GraphSAGE的“卷积”变体是Kipf等人的半监督GCN的扩展，归纳版本[17]，因此我们将其称为GraphSAGE-GCN。我们测试了根据等式（1）中的损失训练的GraphSAGE的无监督变体，以及对分类交叉熵损失进行了直接训练的有监督变体。对于所有的GraphSAGE变体，我们使用校正的线性单位作为非线性，并设置 $K = 2$，邻域样本大小为 $S1 = 25$ 和 $S2 = 10$（有关灵敏度分析，请参见第4.4节）。
对于Reddit和引文数据集，我们按照Perozzi等人的描述对DeepWalk使用“在线”训练。 [28]，我们进行了新一轮的SGD优化，以在进行预测之前嵌入新的测试节点（有关详细信息，请参见附录）。在多图设置中，我们无法应用DeepWalk，因为在不同的不相交图上运行 DeepWalk 算法生成的嵌入空间可以相对于彼此任意旋转（附录D）。
所有模型均在TensorFlow [1]中使用Adam优化器[16]实现（DeepWalk除外，DeepWalk在普通梯度下降优化器中表现更好）。我们设计实验的目的是（i）验证GraphSAGE相对于基线方法（即Raw features 和 DeepWalk）的改进，以及（ii）严格比较不同GraphSAGE聚合器体系结构。为了提供公平的比较，所有模型都共享其最小批量迭代器，损失函数和邻域采样器（如果适用）的相同实现。此外，为了防止在GraphSAGE聚合器之间进行比较时出现意外的“超参数骇客（hyperparameter hacking）”，我们对所有GraphSAGE变体进行了相同的超参数设置（根据验证集的性能为每个变体选择最佳设置）。在早期的验证测试中，使用引文和Reddit数据的子集确定了可能的超参数值，然后从分析中将其丢弃。附录包含更多实现细节。

4.1 Inductive learning on evolving graphs: Citation and Reddit data

我们的前两个实验是在不断发展的信息图中对节点进行分类，这一任务尤其与不断遇到未知数据的高通量生产系统有关。
表1的前四列概述了GraphSAGE的性能以及这两个数据集的基线方法。我们发现GraphSAGE的性能大大优于所有基线，并且与GCN方法相比，可训练的神经网络聚合器可提供明显的收益。例如，无监督变体GraphSAGE-pool在引用数据上的表现优于DeepWalk嵌入和原始特征的串联，分别为13.8％和Reddit数据的29.1％，而受监督版本则分别增加19.7％和37.2％ 。有趣的是，尽管基于LSTM的聚合器是为顺序数据而不是无序集设计的，但它仍显示出出色的性能。最后，我们看到无监督的GraphSAGE的性能与完全受监督的版本具有相当的竞争力，这表明我们的框架无需特定于任务的微调就可以实现强大的性能。

4.2 Generalizing across graphs: Protein-protein interactions

现在，我们考虑跨图概括的任务，这需要了解节点角色而不是社区结构。我们根据蛋白质在基因本体中的细胞功能，将蛋白质的作用分类为各种蛋白质-蛋白质相互作用（PPI）图，每个图对应于不同的人体组织[41]。我们使用位置基因集，基序基因集和免疫学特征作为特征，并使用基因本体论集合作为标记（共121个），这些标记是从分子特征数据库中收集的[34]。平均图包含2373个节点，平均度为28.8。我们在20张图上训练所有算法，然后在两张测试图上平均预测F1分数（另外两张图用于验证）。
表1的最后两列总结了此数据的各种方法的准确性。再次，我们看到GraphSAGE明显优于基线方法，基于LSTM和基于池的聚合器比基于均值和GCN的聚合器具有可观的收益。

4.3 Runtime and parameter sensitivity

图2.A总结了不同方法的训练和测试运行时。这些方法的培训时间相当（GraphSAGE-LSTM最慢）。但是，需要采样新的随机游走并运行新的SGD轮来嵌入看不见的节点，这会使DeepWalk在测试时慢100-500倍。
对于GraphSAGE变体，我们发现，与K = 1相比，设置K = 2可使平均精度持续提高约10-15％。但是，将K增加到2以上会导致性能的边际回报（0-5％），同时将运行时间增加到令人难以置信的10-100倍，这取决于邻域样本大小。我们还发现，对大型社区进行采样的收益递减（图2.B）。因此，尽管子采样邻域引起较高的方差，但GraphSAGE仍然能够保持强大的预测准确性，同时显着改善运行时间。

4.4 Summary comparison between the different aggregator architectures

总体而言，我们发现，就平均性能和实验设置数量而言，基于LSTM和池的聚合器是表现最佳的方法（表1）。为了更定量地了解这些趋势，我们将六个不同的实验设置（即（3个数据集）×（无监督与有监督））视为试验，并考虑了哪些性能趋势可能会普遍存在。特别是，我们使用非参数Wilcoxon Signed-Rank检验[33]来量化各个试验中不同聚合器之间的差异，并在适用的情况下报告T统计量和p值。请注意，该方法是基于等级的，实质上测试了在新的实验环境中我们是否期望一种特定的方法优于另一种方法。鉴于我们只有6个不同设置的小样本量，此显着性检验的功能有些不足。尽管如此，T统计量和相关的p值是评估聚合器相对绩效的有用的量化指标。
我们看到，与基于GCN的方法相比，基于LSTM的，基于池的和基于均值的聚合器均提供了统计上显着的收益（所有这三种方法的T = 1.0，p = 0.02）。但是，与基于均值的聚合器相比，LSTM和合并方法的收益更为微不足道（T = 1.5，p = 0.03，将LSTM与平均值进行比较； T = 4.5，p = 0.10，将池与平均值进行比较）。 LSTM和合并方法之间没有显着差异（T = 10.0，p = 0.46）。但是，GraphSAGE-LSTM比GraphSAGE-pool慢得多（约2倍），这可能使基于池的聚合器总体上略有优势。

5 Theoretical analysis

6 Conclusion

我们引入了一种新颖的方法，可以有效地为看不见的节点生成嵌入。 GraphSAGE 始终优于最新的基准，通过对节点邻域进行采样有效地权衡了性能和运行时间，并且我们的理论分析提供了关于我们的方法如何学习局部图结构的见解。许多扩展和潜在的改进都是可能的，例如扩展 GraphSAGE 以合并有向图或多峰图。未来工作的一个特别有趣的方向是探索非均匀邻域采样函数，甚至可能作为GraphSAGE优化的一部分来学习这些函数。

本文所谓学习一个 “聚合器函数”，主要是学习聚合器的参数，如 $W,b$ ，待有新的节点需要预测时，直接用这个聚合函数即可。个人感觉，和GCN的区别是，GCN在预测节点时，需要将整个图训练一遍（即待预测的节点和原来的节点），捕获拓扑结构；而GraphSage则无需这样，只需要将新的节点输入到训练好的聚合器函数里即可实现预测。当然，GraphSage在一定程度上是一种有损的方法。

推荐阅读：
[论文笔记]：GraphSAGE：Inductive Representation Learning on Large Graphs 论文详解 NIPS 2017
GraphSAGE NIPS 2017 代码分析（Tensorflow版）
【Graph Neural Network】GraphSAGE: 算法原理，实现和应用
网络表示学习: 淘宝推荐系统&&GraphSAGE