NIPS: Advances in neural information processing systems 2018
William L. Hamilton Rex Ying Jure Leskovec
Abstract
大型图中节点的低维嵌入已被证明在各种预测任务中非常有用，从内容推荐到识别蛋白质功能。然而，大多数现有的方法要求在训练嵌入时图中的所有节点都存在；这些以前的方法本质上是直推性的，不能自然地推广到未见过的节点。在这里，我们提出了GraphSAGE，这是一个通用的归纳框架，利用节点特征信息（如文本属性）来为以前未见过的数据有效地生成节点嵌入。我们不是为每个节点训练单独的嵌入，而是学习一个函数，通过从节点的本地邻域采样和聚合特征来生成嵌入。我们的算法在三个归纳的节点分类基准上优于强大的基线：我们根据引文和Reddit帖子数据对不断发展的信息图中未见过的节点类别进行分类，并且我们表明我们的算法可以利用蛋白质-蛋白质相互作用的多图数据集推广到完全未见过的图。
1 Introduction
事实证明，大型图形中节点的低维向量嵌入作为各种预测和图形分析任务的特征输入非常有用。节点嵌入方法背后的基本思想是使用降维技术将节点邻域的高维信息提取为密集向量嵌入。然后，这些节点嵌入可以反馈给下游机器学习系统，并帮助完成节点分类、聚类和链接预测等任务。
然而，以前的工作都集中在嵌入单一固定图的节点上，而许多现实世界的应用需要为未见过的节点或全新的（子）图快速生成嵌入。这种归纳能力对于高吞吐量的生产型机器学习系统是至关重要的，这些系统在不断变化的图上运行，并不断遇到未见过的节点（例如Reddit上的帖子，Youtube上的用户和视频）。生成节点嵌入的归纳法也有利于在具有相同特征形式的图之间进行归纳：例如，我们可以在从一个模型生物体得到的蛋白质-蛋白质相互作用图上训练一个嵌入生成器，然后使用训练好的模型为在新的生物体上收集的数据轻松生成节点嵌入。
归纳式节点嵌入问题与直推式设置相比特别困难，因为对未见过的节点进行归纳需要将新观察到的子图与算法已经优化过的节点嵌入 "对齐"。归纳框架必须学会识别节点邻域的结构属性，这些属性既揭示了节点在图中的局部作用，也揭示了其全局位置。
大多数现有的生成节点嵌入的方法本质上是直推性的。这些方法中的大多数直接使用基于矩阵因子的目标对每个节点的嵌入进行优化，并且不能自然地推广到未见过的数据，因为它们对单一的、固定的图中的节点进行预测。这些方法可以被修改为在归纳环境中操作，但这些修改往往计算成本很高，需要在做出新的预测之前进行额外的梯度下降。最近还有一些使用卷积算子在图结构上学习的方法，这些方法有望成为一种嵌入方法。到目前为止，图卷积网络（GCNs）只被应用于固定图的过渡设置中。在这项工作中，我们将GCN扩展到归纳式无监督学习的任务中，并提出了一个框架，将GCN方法推广到使用可训练的聚合函数（超越简单的卷积）。
目前的工作。我们提出了一个通用框架，称为GraphSAGE（采样和聚合），用于归纳节点嵌入。与基于矩阵分解的嵌入方法不同，我们利用节点特征（如文本属性、节点概况信息、节点度数）来学习嵌入函数，该函数可推广到未见过的节点。通过在学习算法中加入节点特征，我们同时学习每个节点邻域的拓扑结构，以及邻域中节点特征的分布。虽然我们专注于特征丰富的图（例如，具有文本属性的引文数据，具有功能/分子标记的生物数据），但我们的方法也可以利用所有图中存在的结构特征（例如，节点度）。因此，我们的算法也可以应用于没有节点特征的图。
我们不是为每个节点训练一个不同的嵌入向量，而是训练一组聚合函数，学习从节点的本地邻域聚合特征信息（图1）。每个聚合函数都会聚合来自于距离一个给定节点的不同跳数，或搜索深度的信息。在测试或推理时，我们使用我们训练好的系统，通过应用学到的聚合函数为完全未见过的节点生成嵌入。根据之前关于生成节点嵌入的工作，我们设计了一个无监督的损失函数，允许GraphSAGE在没有特定任务监督的情况下被训练。我们还表明，GraphSAGE可以以完全监督的方式进行训练。
我们在三个节点分类基准上评估了我们的算法，这些基准测试了GraphSAGE在未见过的数据上生成有用嵌入的能力。我们使用了两个基于引文数据和Reddit帖子数据的不断发展的文档图（分别预测论文和帖子类别），以及一个基于蛋白质-蛋白质相互作用数据集的多图概括实验（预测蛋白质功能）。使用这些基准，我们表明我们的方法能够有效地生成未见过的节点的表征，并以显著的幅度超过相关的基线：在不同的领域，我们的监督方法与单独使用节点特征相比，平均提高了51%的分类F1分数，GraphSAGE始终超过了强大的、归纳的基线，尽管这个基线在未见过的节点上运行的时间要长100倍∼。我们还表明，与受图卷积网络启发的聚合器相比，我们提出的新聚合器架构提供了显著的收益（平均7.4%）。最后，我们探究了我们方法的表达能力，并通过理论分析表明GraphSAGE能够学习关于节点在图中的作用的结构信息，尽管它本身是基于特征的（第5节）。
2 Related work
我们的算法在概念上与以前的节点嵌入方法、图上学习的一般监督方法以及将卷积神经网络应用于图结构数据的最新进展有关 。
基于因子化的嵌入方法。最近有一些节点嵌入方法，使用随机行走统计和基于矩阵因子化的学习目标来学习低维嵌入。这些方法也与谱系聚类、多维缩放以及PageRank算法等更经典的方法有着密切的关系。由于这些嵌入算法直接为单个节点训练节点嵌入，它们本质上是直推性的，至少需要昂贵的额外训练（例如，通过随机梯度下降）来对新节点进行预测。此外，对于许多这些方法来说，目标函数对嵌入的正交变换是不变的，这意味着嵌入空间在图之间不能自然地泛化，在重新训练时可能会漂移。这种趋势的一个明显的例外是Yang等人提出的$Planetoid-I$算法，它是一种归纳的、基于嵌入的半监督学习方法。然而，$Planetoid-I$在推理过程中不使用任何图形结构信息；相反，它在训练过程中使用图形结构作为一种正则化形式。与之前的这些方法不同，我们利用特征信息来训练一个模型，为未见过的节点产生嵌入。
图上的监督学习。除了节点嵌入方法，还有大量关于图结构数据的监督学习的文献。这包括各种基于核的方法，其中图的特征向量是由各种图核派生出来的。最近还有一些神经网络方法用于图结构的监督学习。我们的方法在概念上受到这些算法中的一些启发。然而，以前的这些方法试图对整个图（或子图）进行分类，而这项工作的重点是为单个节点生成有用的表示。
**图卷积网络。**近年来，已经提出了几种用于图上学习的卷积神经网络架构。这些方法大多不能扩展到大型图上，或者是为整个图的分类而设计的（或者两者都是）。然而，我们的方法与Kipf等人介绍的图卷积网络（GCN）密切相关。我们算法的一个简单变体可以被看作是GCN框架在归纳环境下的扩展，这一点我们将在第3.3节重新讨论。
3 Proposed method: GraphSAGE
我们的方法背后的关键思想是，我们学习如何从节点的本地邻域（如附近节点的度数或文本属性）聚合特征信息。我们首先描述GraphSAGE嵌入生成（即前向传播）算法，该算法为节点生成嵌入，假设GraphSAGE模型参数已被学习（第3.1节）。然后我们描述了如何使用标准的随机梯度下降和反向传播技术来学习GraphSAGE模型参数（第3.2节）。
3.1嵌入生成（即前向传播）算法
在这一节中，我们描述了嵌入生成，或前向传播算法（算法1），它假定模型已经被训练过，并且参数是固定的。特别是，我们假设我们已经学会了$K$个聚合函数（表示$AGGREGATE_k$，$∀k∈{1，...，K}$）的参数，这些函数聚合来自节点邻居的信息，以及一组权重矩阵$W^k，∀k∈{1，...，K}$，这些矩阵用于在模型的不同层或 "搜索深度 "之间传播信息。第3.2节描述了我们如何训练这些参数。
算法1背后的原理是，在每个迭代或搜索深度，节点从其本地邻居那里汇总信息，随着这个过程的迭代，节点从图的更远处逐步获得越来越多的信息。
note:随着迭代次数的增加，每个节点的聚合的信息几乎都是全局的，这点和CNN中感受野的思想类似。
算法1描述了在整个图$G=(V，E)$和所有节点$x_v，∀v∈V$的特征被作为输入的情况下的嵌入生成过程。我们将在下面描述如何将其推广到小批设置中。算法1的外循环的每一步进行如下，其中$k$表示外循环的当前步骤（或搜索的深度），$h^k$表示节点在这一步的表示。首先，每个节点$v∈V$将其紧邻的节点的表征$h^{k-1}u , ∀u∈N (v)$汇总为一个单一的向量$h^{k-1}{N (v)}$。请注意，这个聚合步骤取决于外循环前一次迭代产生的表征（即$k-1$），而$k=0$（"基本情况"）的表征被定义为输入节点特征。在聚合相邻的特征向量后，GraphSAGE将节点的当前表征$h^{k-1}v$与聚合的相邻向量$h^{k-1}{N (v)}$连接起来，这个连接的向量被送入具有非线性激活函数$σ$的全连接层，该层将表征转换为算法的下一步使用（即，$h^k_v，∀v∈V$）。为了便于标注，我们将深度$K$处的最终表示输出表示为$z_v≡h^K_v，∀v∈V$. 邻居表示的聚合可以通过各种聚合器体系结构来完成（在算法1中由聚合占位符表示），我们将在下面的第3.3节中讨论不同的体系结构选择。
note:将节点自身的属性特征与采样的邻居节点特征分别做一次线性变换（也就是乘一个W参数矩阵，一般还会加个relu激活增强表示），然后将两者concat，再进行一次线性变换得到目标节点的特征表示。最后可利用得到的目标节点表示进行下游的任务
为了将算法1扩展到小批量设置，给定一组输入节点，我们首先对所需的邻域集进行前向采样（直到深度$K$），然后我们运行内循环（算法1中的第3行），但不是在所有节点上迭代，而是只计算满足每个深度递归所需的表示.
与Weisfeiler-Lehman同构性测试的关系。GraphSAGE算法在概念上受到一种测试图形同构性的经典算法的启发。如果在算法1中，我们(i)设置$K=|V|$，(ii)将权重矩阵设置为恒等式，以及(iii)使用适当的哈希函数作为聚合器（没有非线性），那么算法1就是Weisfeiler-Lehman（WL）同构测试的一个实例，也被称为 "原始顶点细化 " 。如果算法1为两个子图输出的表示集${z_v,∀v∈V}$是相同的，那么WL测试就宣布这两个子图是同构的。众所周知，这个测试在某些情况下是失败的，但对一大类图是有效的。GraphSAGE是WL测试的连续近似，我们用可训练的神经网络聚合器取代哈希函数。当然，我们使用GraphSAGE来生成有用的节点表示，而不是测试图的同构性。尽管如此，GraphSAGE和经典的WL测试之间的联系为我们学习节点邻域拓扑结构的算法设计提供了理论背景。
邻域定义。在这项工作中，我们统一采样一个固定大小的邻域集，而不是在算法1中使用完整的邻域集，以保持每个批次的计算足迹固定。也就是说，使用重载表示法，我们将$N(v)$定义为从${u∈V:(u，v)∈E}$集合中抽取一个固定大小的统一样本，我们在算法1的每个迭代$k$中抽取不同的统一样本。 没有这种采样，单个批处理的内存和预期运行时间是不可预测的，在最坏的情况下是$O(| V |)$。相比之下，GraphSAGE的每批空间和时间复杂度固定为$O(\prod^K_{i=1}S_i)$，其中$S_i，i∈{1，...，K}$和$K$是用户指定的常数。实际上，我们发现我们的方法可以在$K=2$和$S_1 \sdot S_2≤500$的情况下实现高性能（详见4.4节）。
3.2学习GraphSAGE的参数
为了在完全无监督的情况下学习有用的预测性表征，我们对输出表征$z_u,∀u∈V$应用基于图的损失函数，并通过随机梯度下降法调整权重矩阵$W^k,∀k∈{1，...，K}$和聚合器函数的参数。基于图的损失函数希望附近的节点有类似的表示，同时强制要求不同节点的表示有很大区别:
$$\mathcal{J}\mathcal{G} (z_u)=−log(σ(z_u^T z_v))−\mathcal{Q}·E{{v_n}∼P_n(v)}log(σ(z_u^T z_{v_n}))~~~~~~(1)$$
其中$v$是在固定长度的随机行走中$u$附近共同出现的节点，$σ$是$sigmoid$函数，$P_n$是一个负采样分布，$Q$定义了负采样的数量。重要的是，与以前的嵌入方法不同，我们送入这个损失函数的表示$z_u$是从一个节点的本地邻居中包含的特征产生的，而不是为每个节点训练一个独特的嵌入（通过嵌入查找）。
**这种无监督的设置模拟了节点特征作为一种服务或在静态资源库中提供给下游机器学习应用的情况。**在表征只用于特定的下游任务的情况下，无监督损失（公式1）可以简单地被特定任务的目标（如交叉熵损失）所取代，或增加。
3.3聚合器结构
与$N-D$格（例如句子、图像或三维体积）上的机器学习不同，节点的邻居没有自然的顺序；因此，算法1中的聚合器函数必须在无序向量集上运行。理想情况下，聚合器函数将是对称的（即，对其输入的置换不变），同时仍然可以训练并保持较高的表示能力。聚合函数的对称性保证了我们的神经网络模型可以训练并应用于任意顺序的节点邻域特征集。我们研究了三个候选聚合器函数：
**平均聚合器。**我们的第一个候选聚合器函数是平均算子，我们简单地取${h^{k-1}_u , ∀u∈Nv)}$中的向量元素的平均。平均聚合器几乎等同于反演式GCN框架中使用的卷积传播规则。特别是，我们可以通过将算法1中的第4行和第5行替换为以下内容，得出GCN方法的归纳变体。
$$h_v^k \leftarrow σ(W \sdot MEAN({h^{k-1}_v} \cup {h^{k-1}_v,∀u∈N(v)}))~~~~(2) $$
我们把这个修改过的基于平均的聚合器称为卷积，因为它是对局部频谱卷积的一个粗略的、线性的近似。这个卷积聚合器与我们提出的其他聚合器之间的一个重要区别是，它不执行算法1的第5行的连接操作，即卷积聚合器确实连接了节点的前一层表示$h^{k-1}v$与聚合的邻域向量$h^k{N(v)}$。这种连接可以看作是GraphSAGE算法的不同 "搜索深度 "或 "层 "之间的一种简单的 "跳连接 "形式，它导致了性能的显著提高（第4节）。
LSTM聚合器。我们还研究了一个基于LSTM架构的更复杂的聚合器。与平均聚合器相比，LSTM的优势在于更大的表达能力。然而，需要注意的是，LSTM本身不是对称的（即，它们不是互换不变的），因为它们以顺序的方式处理它们的输入。我们通过简单地将LSTM应用于节点邻居的随机排列，使LSTM能够在无序的集合上操作。
池化聚合器。我们研究的最后一个聚合器既是对称的又是可训练的。在这种集合方法中，每个邻居的向量都独立地通过一个全连接的神经网络；在这种转换之后，一个元素最大集合操作被应用于集合整个邻居集的信息。
$$AGGREGATE^{pool}k = max({σ(W{pool}h^k_{u_i} + b),∀u_i∈N(v)})~~~~~(3)$$
其中，$max$表示元素的最大运算符，$σ$是一个非线性激活函数。原则上，在最大集合之前应用的函数可以是一个任意深度的多层感知器，但我们在这项工作中专注于简单的单层架构。这种方法的灵感来自于最近在应用神经网络架构在一般点集上学习方面的进展。直观地说，多层感知机可以被认为是一组计算邻居集中每个节点表示的特征的函数。通过对每个计算出的特征应用最大集合算子，该模型有效地捕捉了邻域集的不同方面。还要注意的是，原则上，任何对称的向量函数都可以用来代替最大运算符（例如，一个元素的平均值）。我们发现，在开发测试中，最大集合和平均集合之间没有明显的区别，因此，在我们其余的实验中，重点是最大池化。
$ \begin{bmatrix} u_1(1) & u_1(2) & \ldots & u_1(N) \ u_2(1) & u_2(2) & \ldots & u_2(N) \ \ldots \ u_N(1) & u_N(2) & \ldots & u_N(N) \end{bmatrix} $
4实验
我们在三个基准任务上测试了GraphSAGE的性能：(i)使用Web of Science引文数据集将学术论文分类为不同的主题，(ii)将Reddit帖子分类为属于不同的社区，以及(iii)在各种生物蛋白-蛋白相互作用（PPI）图中对蛋白质功能进行分类。第4.1和4.2节总结了这些数据集，补充材料包含了更多信息。在所有这些实验中，我们对训练期间没有看到的节点进行预测，在PPI数据集的情况下，我们对完全没有看到的图进行测试。
**实验设置。**为了对我们的归纳基准的经验结果进行背景分析，我们与四个基线进行了比较：一个随机分类器、一个基于逻辑回归特征的分类器（忽略了图结构）、DeepWalk算法作为基于因子化的代表性方法，以及原始特征和DeepWalk嵌入的连接。我们还比较了使用不同聚合器函数的GraphSAGE的四个变体（第3.3节）。由于GraphSAGE的 "卷积"变体是Kipf等人的半监督GCN的扩展、归纳版本，我们将这个变体称为GraphSAGE-GCN。我们测试了根据公式(1)中的损失训练的GraphSAGE的无监督变体，以及直接根据分类交叉熵损失训练的有监督变体。对于所有的GraphSAGE变体，我们使用整流线性单位作为非线性，并设置$K=2$，邻域样本量$S1=25，S2=10$（敏感性分析见4.4节）。
对于Reddit和引文数据集，我们使用Perozzi等人描述的DeepWalk的 "在线 "训练，在预测之前，我们运行新一轮的SGD优化来嵌入新的测试节点（详见附录）。在多图设置中，我们不能应用DeepWalk，因为在不同的不相交图上运行DeepWalk算法所产生的嵌入空间可以任意地相互旋转（附录D）。
所有的模型都是在TensorFlow中用Adam优化器实现的（除了DeepWalk，它用vanilla梯度下降优化器表现更好）。我们设计实验的目的是：（1）验证GraphSAGE比基线方法（即原始特征和DeepWalk）的改进；（2）提供不同GraphSAGE聚合器架构的严格比较。为了提供一个公平的比较，所有的模型都共享一个相同的迷你批迭代器、损失函数和邻域采样器（适用时）的实现。此外，为了防止在GraphSAGE聚合器之间的比较中出现无意的 "超参数入侵"，我们对所有GraphSAGE变体的超参数集进行了扫描（根据验证集的性能为每个变体选择最佳设置）。可能的超参数值集是在早期验证测试中确定的，使用的是引文和Reddit数据的子集，然后我们从分析中舍弃了这些子集。附录中包含进一步的实施细节。
4.1进化图的归纳学习：引文和Reddit数据
我们的前两个实验是对进化信息图中的节点进行分类，这项任务与高通量生产系统尤其相关，因为这些系统经常遇到看不见的数据。
**引文数据。**我们的第一个任务是在一个大型引文数据集上预测论文的主题类别。我们使用一个来自汤森路透科学网核心库的无定向引文图数据集，对应于2000-2005年六个生物学相关领域的所有论文。这个数据集的节点标签与六个不同领域的标签相对应。总的来说，这个数据集包含302,424个节点，平均度数为9.15。**我们在2000-2004年的数据上训练所有的算法，并使用2005年的数据进行测试（其中30%用于验证）。**对于特征，我们使用节点度，并根据Arora等人的句子嵌入方法处理论文摘要，使用GenSim word2vec实现训练的300维单词向量。
Reddit数据。在我们的第二个任务中，我们预测不同的Reddit帖子属于哪个社区。Reddit是一个大型的在线讨论论坛，用户在这里发布和评论不同主题社区的内容。我们从2014年9月的Reddit帖子中构建了一个图数据集。在这种情况下，节点标签是一个帖子所属的社区，或 "subreddit"。我们对50个大型社区进行了抽样调查，并建立了一个帖子-帖子图，如果同一用户在两个帖子上都有评论，则将帖子连接起来。这个数据集总共包含232,965个帖子，平均程度为492。我们使用前20天进行训练，其余天数进行测试（其中30%用于验证）。对于特征，我们使用现成的300维 GloVe CommonCrawl词向量；对于每个帖子，我们把（i）帖子标题的平均嵌入，（ii）所有帖子评论的平均嵌入（iii）帖子的分数，以及（iv）对帖子的评论数量连接起来。
表1的前四列总结了GraphSAGE以及基线方法在这两个数据集上的表现。我们发现GraphSAGE比所有的基线方法都要好很多，与GCN方法相比，可训练的神经网络聚合器提供了巨大的收益。例如，无监督变体GraphSAGE-pool在引文数据和Reddit数据上分别比DeepWalk嵌入和原始特征的连接好13.8%和29.1%，而监督版本则分别提供了19.7%和37.2%的收益。有趣的是，**基于LSTM的聚合器显示出强大的性能，尽管它是为顺序数据而不是无序集合设计的。**最后，我们看到无监督的GraphSAGE的性能与完全监督的版本相比具有合理的竞争力，表明我们的框架可以在没有特定任务微调的情况下获得强大的性能。
表1：三个数据集的预测结果（微观平均F1分数）。显示了无监督和完全监督图形图像的结果。宏观平均得分也有类似的趋势。
4.2 跨图概括：蛋白质-蛋白质相互作用
我们现在考虑跨图概括的任务，这需要学习节点规则而不是社区结构。我们根据基因本体论中的细胞功能对各种蛋白质-蛋白质相互作用（PPI）图中的蛋白质角色进行分类，每个图对应一个不同的人体组织。我们使用位置基因组、主题基因组和免疫学特征作为特征，使用基因本体组作为标签（共121个），这些标签从分子特征数据库中收集。平均图包含2373个节点，平均度为28.8。我们在20个图上训练所有算法，然后在两个测试图上平均预测F1分数（另外两个图用于验证）。
表1的最后两栏总结了各种方法在该数据上的准确性。我们再次看到GraphSAGE明显优于基线方法，基于LSTM和集合的聚合器比基于平均和GCN的聚合器有很大的提升。
4.3运行时间和参数敏感性
图2.A总结了不同方法的训练和测试运行时间。这些方法的训练时间是相当的（GraphSAGE-LSTM是最慢的）。然而，由于需要对新的随机行走进行采样，并运行新一轮的SGD来嵌入未见过的节点，使得DeepWalk在测试时慢了100-500倍。
图2：A：Reddit数据的计时实验，训练批次大小为512，在完整的测试集（79,534个节点）上进行推理。B：模型性能与采样邻域的大小有关，其中 "邻域采样大小 "指的是$K=2、S1=S2$时在每个深度采样的邻域数量（在引文数据上使用GraphSAGE-mean）。
对于GraphSAGE变体，我们发现，与$K = 1$相比，设置$K = 2$能持续提高准确率，平均约为10-15%；然而，将K增加到2以上，性能会有边际回报（0-5%），同时运行时间会增加10-100倍，这取决于邻域样本大小，令人望而却步。我们还发现，对大的邻域进行抽样的回报也在减少（图2.B）。因此，尽管次抽样邻域引起了更高的变异，GraphSAGE仍然能够保持强大的预测精度，同时显著改善运行时间。
4.4 不同聚合器架构之间的总结比较
总的来说，我们发现基于LSTM和池化的聚合器表现最好，无论是从平均性能还是从它们是表现最好的方法的实验设置的数量来看（表1）。为了对这些趋势有更多的定量了解，我们将六个不同的实验设置（即（3个数据集）×（无监督与有监督））中的每一个都视为试验，并考虑哪些性能趋势可能会被概括。特别是，我们使用非参数的Wilcoxon Signed-Rank Test来量化不同试验中不同聚合器之间的差异，在适用的情况下报告T统计量和P值。请注意，这种方法是基于等级的，本质上是测试我们是否会期望一种特定的方法在新的实验环境中胜过另一种。鉴于我们的样本量很小，只有6个不同的环境，这种显著性测试有点力量不足；尽管如此，T统计量和相关的P值是评估聚合器相对性能的有用的定量措施。
我们看到，基于LSTM、池化和平均的聚合器都比基于GCN的方法提供了统计学上的显著收益（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理论分析
在本节中，我们探究了GraphSAGE的表达能力，以便深入了解GraphSAGE如何学习图的结构，尽管它本身是基于特征的。 作为一个案例，我们考虑GraphSAGE是否能够学习预测一个节点的聚类系数，即在该节点的1跳邻域内封闭的三角形的比例。 聚类系数是衡量一个节点的本地邻域的聚类程度的常用指标，它可以作为许多更复杂的结构图案的构建块。我们可以证明，算法1能够以任意的精度近似聚类系数。
定理1. 令$x_v∈U，∀v∈V$表示图$G=(V，E)$上算法1的特征输入，其中$U$是$R^d$的任何紧凑子集。假设存在一个固定的正常数$C∈R^+$，使得所有节点对的$||x_v-x_{v^\prime}||_2>C$。那么我们就有，$∀ \epsilon >0$，存在一个算法1的参数设置$Θ^∗$，使得在$K = 4$次迭代之后。
$$|z_v − c_v| < \epsilon, ∀v ∈ V$$，其中$z_v∈R$是算法1生成的最终输出值，$c_v$是节点聚类系数。
定理1指出，对于任何图来说，如果每个节点的特征都是不同的（而且模型是足够高维的），那么算法1存在一个参数设置，它可以在该图中以任意的精度近似聚类系数。定理1的完整证明在附录中。请注意，作为定理1的一个推论，GraphSAGE可以学习局部图结构，即使节点特征输入是从绝对连续的随机分布中采样的（详见附录）。该证明背后的基本想法是，如果每个节点都有独特的特征表示，那么我们可以学习将节点映射到指标向量并识别节点邻域。定理1的证明依赖于池化聚合器的一些属性，这也让我们了解到为什么GraphSAGE-pool优于GCN和基于平均值的聚合器。
6结论
我们引入了一种新的方法，允许为未见过的节点有效地生成嵌入。 GraphSAGE的性能一直优于最先进的基线，通过对节点邻域的采样，有效地交换了性能和运行时间，我们的理论分析提供了关于我们的方法如何学习局部图结构的见解。一些扩展和潜在的改进是可能的，比如将GraphSAGE扩展到有向图或多模式图。未来工作的一个特别有趣的方向是探索非均匀邻域采样函数，甚至可能将这些函数作为GraphSAGE优化的一部分来学习。