NIPS 2017 | GraphSAGE：大规模图上的归纳表示学习模型

论文标题 ｜ Inductive Representation Learning on Large Graphs
论文来源 ｜ NIPS 2017
论文链接 ｜ https://arxiv.org/abs/1706.02216
源码链接 ｜ https://github.com/williamleif/GraphSAGE

此文提出的方法叫 GraphSAGE，针对的问题是之前的网络表示学习的 transductive，从而提出了一个 inductive 的 GraphSAGE 算法。GraphSAGE 同时利用节点特征信息和结构信息得到 Graph Embedding 的映射，相比之前的方法，之前都是保存了映射后的结果，而 GraphSAGE 保存了生成 embedding 的映射，可扩展性更强，对于节点分类和链接预测问题的表现也比较突出。

概括

现存的方法需要图中所有的顶点在训练 embedding 的时候都出现；这些前人的方法本质上是 transductive，不能自然地泛化到未见过的顶点。

文中提出了 GraphSAGE，是一个 inductive 的框架，可以利用顶点特征信息（比如文本属性）来高效地为没有见过的顶点生成 embedding。

GraphSAGE 是为了学习一种节点表示方法，即如何通过从一个顶点的局部邻居采样并聚合顶点特征，而不是为每个顶点训练单独的 embedding。

这个算法在三个 inductive 顶点分类 benchmark 上超越了那些很强的 baseline。文中基于 citation 和 Reddit 帖子数据的信息图中对未见过的顶点分类，实验表明使用一个 PPI（protein-protein interactions）多图数据集，算法可以泛化到完全未见过的图上。

回顾 GCN 及其问题

在大型图中，节点的低维向量 embedding 被证明了作为各种各样的预测和图分析任务的特征输入是非常有用的。顶点 embedding 最基本的基本思想是使用降维技术从高维信息中提炼一个顶点的邻居信息，存到低维向量中。这些顶点嵌入之后会作为后续的机器学习系统的输入，解决像顶点分类、聚类、链接预测这样的问题。

GCN 虽然能提取图中顶点的 embedding，但是存在一些问题：
GCN 的基本思想： 把一个节点在图中的高纬度邻接信息降维到一个低维的向量表示。
GCN 的优点： 可以捕捉 graph 的全局信息，从而很好地表示 node 的特征。
GCN 的缺点： Transductive learning 的方式，需要把所有节点都参与训练才能得到 node embedding，无法快速得到新 node 的 embedding。

transductive vs inductive

前人的工作专注于从一个固定的图中对顶点进行表示，很多现实中的应用需要很快的对未见过的顶点或是全新的图（子图）生成 embedding。这种推断的能力对于高吞吐的机器学习系统来说很重要，这些系统都运作在不断演化的图上，而且时刻都会遇到未见过的顶点（比如 Reddit 上的帖子（posts），Youtube 上的用户或视频）。因此，一种 inductive 的学习方法比 transductive 的更重要。

transductive learning 得到新节点的表示的难处：
要想得到新节点的表示，需要让新的 graph 或者 subgraph 去和已经优化好的 node embedding 去“对齐（align）”。然而每个节点的表示都是受到其他节点的影响，因此添加一个节点，意味着许许多多与之相关的节点的表示都应该调整。这会带来极大的计算开销，即使增加几个节点，也要完全重新训练所有的节点。

GraphSAGE 基本思路：
既然新增的节点，一定会改变原有节点的表示，那么为什么一定要得到每个节点的一个固定的表示呢？何不直接学习一种节点的表示方法。去学习一个节点的信息是怎么通过其邻居节点的特征聚合而来的。 学习到了这样的“聚合函数”，而我们本身就已知各个节点的特征和邻居关系，我们就可以很方便地得到一个新节点的表示了。

GCN 等 transductive 的方法，学到的是每个节点的一个唯一确定的 embedding； 而 GraphSAGE 方法学到的 node embedding，是根据 node 的邻居关系的变化而变化的，也就是说，即使是旧的 node，如果建立了一些新的 link，那么其对应的 embedding 也会变化，而且也很方便地学到。

本文出自斯坦福 PinSAGE 的理论篇，关于第一个基于 GCN 的工业级推荐系统的 PinSAGE 可以看这篇：
PinSage：Graph Convolutional Neural Networks for Web-Scale Recommender Systems

Related work

GraphSAGE 算法在概念上与以前的节点 embedding 方法、一般的图形学习监督方法以及最近将卷积神经网络应用于图形结构化数据的进展有关。

node embedding

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

这些 embedding 算法直接训练单个节点的节点 embedding，本质上是 transductive，而且需要大量的额外训练（如随机梯度下降）使他们能预测新的顶点。

此外，Yang et al. 的 Planetoid-I 算法，是一个 inductive 的基于 embedding 的半监督学习算法。然而，Planetoid-I 在推断的时候不使用任何图结构信息，而在训练的时候将图结构作为一种正则化的形式。

不像前面的这些方法，本文利用特征信息来训练可以对未见过的顶点生成 embedding 的模型。

Supervised learning over graphs

Graph kernel

除了节点嵌入方法，还有大量关于图结构数据的监督学习的文献。这包括各种各样的基于内核的方法，其中图的特征向量来自不同的图内核（参见 Weisfeiler-lehman graph kernels 和其中的引用）。

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

• 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 下的扩展。

GraphSAGE

GraphSAGE 的核心：GraphSAGE 不是试图学习一个图上所有 node 的 embedding，而是学习一个为每个 node 产生 embedding 的映射。

文中不是对每个顶点都训练一个单独的 embeddding 向量，而是训练了一组 aggregator functions，这些函数学习如何从一个顶点的局部邻居聚合特征信息（见图 1）。每个聚合函数从一个顶点的不同的 hops 或者说不同的搜索深度聚合信息。测试或是推断的时候，使用训练好的系统，通过学习到的聚合函数来对完全未见过的顶点生成 embedding。

GraphSAGE 是 Graph SAmple and aggreGatE 的缩写，其运行流程如上图所示，可以分为三个步骤：

• 对图中每个顶点邻居顶点进行采样，因为每个节点的度是不一致的，为了计算高效， 为每个节点采样固定数量的邻居
• 根据聚合函数聚合邻居顶点蕴含的信息
• 得到图中各顶点的向量表示供下游任务使用

文中设计了无监督的损失函数，使得 GraphSAGE 可以在没有任务监督的情况下训练。实验中也展示了使用完全监督的方法如何训练 GraphSAGE。

Embedding generation

生成节点 embedding 的前向传播算法。

GraphSAGE 的前向传播算法如下，前向传播描述了如何使用聚合函数对节点的邻居信息进行聚合，从而生成节点 embedding：

在每次迭代（或搜索深度），顶点从它们的局部邻居聚合信息，并且随着这个过程的迭代，顶点会从越来越远的地方获得信息。PinSAGE 使用的前向传播算法和 GraphSAGE 一样，GraphSAGE 是 PinSAGE 的理论基础。

算法 1 描述了在整个图上生成 embedding 的过程，其中

• $\mathcal{G} = \left( \mathcal{V}, \mathcal{E} \right)$ 表示一个图
• $K$​ 是网络的层数，也代表着每个顶点能够聚合的邻接点的跳数，因为每增加一层，可以聚合更远的一层邻居的信息
• $x_v, \forall v \in \mathcal{V}$ 表示节点$v$ 的特征向量，并且作为输入
• $\lbrace \mathbf{h}^{k-1}_u, \forall u \in \mathcal{N}(v)\rbrace$表示在$k - 1$ 层中节点$v$ 的邻居节点$u$ 的 embedding；
• $\mathbf{h}^{k}_{\mathcal{N}(v)}$表示在第$k$ 层，节点$v$​ 的所有邻居节点的特征表示；
• $\mathbf{h}^k_v, \forall v \in \mathcal{V}$ 表示在第$k$ 层，节点$v$​ 的特征表示；
• ${\mathcal{N}(v)}$​ 定义为从集合$\{u \in v: (u, \mathcal{V}) \in \mathcal{E}\}$​​ 中的固定 size 的均匀取出，即 GraphSAGE 中每一层的节点邻居都是是从上一层网络采样的，并不是所有邻居参与，并且采样的后的邻居的 size 是固定的；

为了将 算法 1 扩展到 minibatch 环境上，给定一组输入顶点，先采样采出需要的邻居集合（直到深度$K$），然后运行内部循环（算法 1 的第三行）（附录 A 包括了完整的 minibatch 伪代码）。

Relation to the Weisfeiler-Lehman Isomorphism Test

和同构测试的相关性

GraphSAGE 算法从概念上受到测试图同构的经典算法的启发。对于算法 1, 如果

1. $K=|\mathcal{V}|$​
2. 设置权重矩阵为单位矩阵
3. 使用一个适当的哈希函数作为一个聚合器、（没有非线性、)

那么算法 1 是 Weisfeiler-Lehman 的实例、(WL) 同构测试，也称为“naive vertex refinement”[Weisfeiler-lehman graph kernels]。

如果对两个子图通过算法 1 的特征表示的集合$\forall v \in \mathcal{V}$ 输出是相同的，那么 ML 测试就认为这两个子图是同构的。如果用可训练的神经网络聚合器替换了哈希函数，那么 GraphSAGE 就是 WL 测试的一个连续近似。当然，文中使用 GraphSAGE 是为了生成有用的节点表示—而不是测试图的同构。然而，GraphSAGE 与经典的 WL 检验之间的联系为算法设计学习节点邻域的拓扑结构提供了理论基础。

Neighborhood definition

采样邻居顶点

出于对计算效率的考虑，对每个顶点采样一定数量的邻居顶点作为待聚合信息的顶点。设需要的邻居数量，即采样数量为$S$​，若顶点邻居数少于$S$​​, 则采用有放回的抽样方法，直到采样出$S$ 个顶点。若顶点邻居数大于$S$，则采用无放回的抽样。(即采用有放回的重采样/负采样方法达到$S$​)

当然，若不考虑计算效率，完全可以对每个顶点利用其所有的邻居顶点进行信息聚合，这样是信息无损的。

文中在较大的数据集上实验。因此，统一采样一个固定大小的邻域集，以保持每个 batch 的计算占用空间是固定的（即 graphSAGE 并不是使用全部的相邻节点，而是做了固定 size 的采样）。

这样固定 size 的采样，每个节点和采样后的邻居的个数都相同，可以把每个节点和它们的邻居拼成一个 batch 送到 GPU 中进行批训练。

• 这里需要注意的是，每一层的 node 的表示都是由上一层生成的，跟本层的其他节点无关，这也是一种基于层的采样方式。
• 在图中的“1 层”，节点 v 聚合了“0 层”的两个邻居的信息，v 的邻居 u 也是聚合了“0 层”的两个邻居的信息。到了“2 层”，可以看到节点 v 通过“1 层”的节点 u，扩展到了“0 层”的二阶邻居节点。因此，在聚合时，聚合 K 次，就可以扩展到 K 阶邻居。
• 没有这种采样，单个 batch 的内存和预期运行时是不可预测的，在最坏的情况下是$O(|V|)$。相比之下，GraphSAGE 的每个 batch 空间和时间复杂度是固定的$O\left(\prod_{i=1}^{K} S_{i}\right)$，其中$S_i, i\in\{1,...,K\}$和$K$是可以指定的参数。
• 实验发现，K 不必取很大的值，当$K=2$ 时，效果就很好了。至于邻居的个数，文中提到$S_1·S_2\leq 500$，即两次扩展的邻居数之际小于 500，大约每次只需要扩展 20 来个邻居时获得较高的性能。
• 论文里说固定长度的随机游走其实就是随机选择了固定数量的邻居

聚合函数的选取

在图中顶点的邻居是无序的，所以希望构造出的聚合函数是对称的（即也就是对它输入的各种排列，函数的输出结果不变），同时具有较高的表达能力。 聚合函数的对称性（symmetry property）确保了神经网络模型可以被训练且可以应用于任意顺序的顶点邻居特征集合上。

Mean aggregator

mean aggregator 将目标顶点和邻居顶点的第$k-1$ 层向量拼接起来，然后对向量的每个维度进行求均值的操作，将得到的结果做一次非线性变换产生目标顶点的第$k$ 层表示向量。

文中用下面的式子替换算法 1 中的 4 行和 5 行得到 GCN 的 inductive 变形：

$$\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)$$

原始第 4,5 行是

$$\begin{aligned} \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.\\ \mathbf{h}_{v}^{k} \leftarrow \sigma\left(\mathbf{W}^{k} \cdot \operatorname{CONCAT}\left(\mathbf{h}_{v}^{k-1}, \mathbf{h}_{\mathcal{N}(v)}^{k}\right)\right) \end{aligned}$$

• 均值聚合近似等价在 transductive GCN 框架中的卷积传播规则；
• 文中称这个修改后的基于均值的聚合器是 convolutional 的，这个卷积聚合器和文中的其他聚合器的重要不同在于它没有算法 1 中第 5 行的 CONCAT 操作——卷积聚合器没有将顶点前一层的表示$\mathbf{h}_v^{k-1}$和聚合的邻居向量$\mathbf{h}_{\mathcal{N}(v)}^k$ 拼接起来
• 拼接操作可以看作一个是 GraphSAGE 算法在不同的搜索深度或层之间的简单的 skip connection 的形式，它使得模型获得了巨大的提升
• 举个简单例子，比如一个节点的 3 个邻居的 embedding 分别为$[1,2,3,4],[2,3,4,5],[3,4,5,6]$​按照每一维分别求均值就得到了聚合后的邻居 embedding 为$[2,3,4,5]$

LSTM aggregator

文中也测试了一个基于 LSTM 的复杂的聚合器。和均值聚合器相比，LSTMs 有更强的表达能力。但是，LSTMs 不是 symmetric 的，也就是说不具有排列不变性（permutation invariant），因为它们以一个序列的方式处理输入。因此，需要先对邻居节点随机顺序，然后将邻居序列的 embedding 作为 LSTM 的输入。

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

Pooling aggregator

pooling 聚合器，它既是对称的，又是可训练的。Pooling aggregator 先对目标顶点的邻居顶点的 embedding 向量进行一次非线性变换，之后进行一次 pooling 操作(max pooling or mean pooling)，将得到结果与目标顶点的表示向量拼接，最后再经过一次非线性变换得到目标顶点的第$k$ 层表示向量。

一个 element-wise max pooling 操作应用在邻居集合上来聚合信息：

$$\begin{array}{r} \mathbf{h}_{\mathcal{N}(v)}^{k}=\text { AGGREGATE }_{k}^{\text {pool }}=\max \left(\left\{\sigma\left(\mathbf{W}_{p o o} \mathbf{h}_{u}^{k-1}+\mathbf{b}\right), \forall u \in \mathcal{N}(v)\right\}\right) \\ \mathbf{h}_{v}^{k} \leftarrow \sigma\left(\mathbf{W}^{k} \cdot \operatorname{CONCAT}\left(\mathbf{h}_{v}^{k-1}, \mathbf{h}_{\mathcal{N}(v)}^{k}\right)\right) \end{array}$$

其中

• $\mathrm{max}$ 表示 element-wise 最大值操作，取每个特征的最大值
• $\sigma$ 是非线性激活函数
• 所有相邻节点的向量共享权重，先经过一个非线性全连接层，然后做 max-pooling
• 按维度应用 max/mean pooling，可以捕获邻居集上在某一个维度的突出的／综合的表现。

Learning the parameters of GraphSAGE

（有监督和无监督）参数学习

在定义好聚合函数之后，接下来就是对函数中的参数进行学习。文章分别介绍了无监督学习和监督学习两种方式。

基于图的无监督损失

基于图的损失函数倾向于使得相邻的顶点有相似的表示，但这会使相互远离的顶点的表示差异变大：

$$J \mathcal{G}\left(\mathbf{z}_{u}\right)=-\log \left(\sigma\left(\mathbf{z}_{u}^{T} \mathbf{z}_{v}\right)\right)-Q \cdot \mathbb{E}_{v_{n} \sim P_{n}(v)} \log \left(\sigma\left(-\mathbf{z}_{u}^{T} \mathbf{z}_{v_{n}}\right)\right)$$

其中

• $\mathbf{z}_u$ 为节点$u$ 通过 GraphSAGE 生成的 embedding
• 节点$v$是节点$u$​ 随机游走到达的“邻居”
• $\sigma$是 sigmoid 函数
• $P_n$是负采样的概率分布，类似 word2vec 中的负采样
• $Q$ 是负样本的数目
• embedding 之间相似度通过向量点积计算得到

文中输入到损失函数的表示$\mathbf{z}_u$ 是从包含一个顶点局部邻居的特征生成出来的，而不像之前的那些方法（如 DeepWalk），对每个顶点训练一个独一无二的 embedding，然后简单进行一个 embedding 查找操作得到。

基于图的有监督损失

无监督损失函数的设定来学习节点 embedding 可以供下游多个任务使用。监督学习形式根据任务的不同直接设置目标函数即可，如最常用的节点分类任务使用交叉熵损失函数。

参数学习

通过前向传播得到节点$u$ 的 embedding$z_u$, 然后梯度下降（实现使用 Adam 优化器） 进行反向传播优化参数和$\mathbf{W}^k$ 合函数内的参数。

新节点 embedding 的生成

这个$\mathbf{W}^{k}$ 就是所谓的 dynamic embedding 的核心，因为保存下来了从节点原始的高维特征生成低维 embedding 的方式。现在，如果想得到一个点的 embedding，只需要输入节点的特征向量，经过卷积（利用已经训练好的$\mathbf{W}^k$ 及特定聚合函数聚合 neighbor 的属性信息），就产生了节点的 embedding。

Experiments

实验目的

• 比较 GraphSAGE 相比 baseline 算法的提升效果
• 比较 GraphSAGE 的不同聚合函数

数据集及任务

• Citation 论文引用网络（节点分类）
• Reddit 帖子论坛 （节点分类）
• PPI 蛋白质网络 （graph 分类）

baselines

• Random，随机分类器
• Raw features，手工特征（非图特征）
• deepwalk（图拓扑特征）
• DeepWalk + features， deepwalk+手工特征

除此以外，还比较了 GraphSAGE 四个变种 ，并无监督生成 embedding 输入给 LR 和端到端有监督。因为，GraphSAGE 的卷积变体是一种扩展形式，是 Kipf et al. 半监督 GCN 的 inductive 版本，称这个变体为GraphSAGE-GCN。分类器均采用 LR

在所有这些实验中，预测在训练期间看不到的节点，在 PPI 数据集的情况下，实验在完全看不见的图上进行了测试。

实验设置

• $K=2$，聚合两跳内邻居特征
• $S1=25，S2=10$： 对一跳邻居抽样 25 个，二跳邻居抽样 10 个
• RELU 激活单元
• Adam 优化器（除了 DeepWalk，DeepWalk 使用梯度下降效果更好）
• 文中所有的模型都是用 TensorFlow 实现
• 对每个节点进行步长为 5 的 50 次随机游走
• 负采样参考 word2vec，按平滑 degree 进行，对每个节点采样 20 个
• 保证公平性：所有版本都采用相同的 minibatch 迭代器、损失函数、邻居采样器
• 实验测试了根据式 1 的损失函数训练的 GraphSAGE 的各种变体，还有在分类交叉熵损失上训练的可监督变体
• 对于 Reddit 和 citation 数据集，使用”online”的方式来训练 DeepWalk
• 在多图情况下，不能使用 DeepWalk，因为通过 DeepWalk 在不同不相交的图上运行后生成的 embedding 空间对它们彼此说可能是 arbitrarily rotated 的（见文中附录 D）

数据集介绍

Inductive learning on evolving graphs: Citation and Reddit data

前两个实验是在演化的信息图中对节点进行分类，这是一个与高吞吐量生产系统特别相关的任务，该系统经常遇到不可见的数据。

Citation data

第一个任务是在一个大的引文数据集中预测论文主题类别。文中使用来自汤姆森路透科学核心数据库（Thomson Reuters Web of Science Core
Collection）的无向的引文图数据集（对应于 2000-2005 年六个生物相关领域的所有论文）。这个数据集的节点标签对应于六个不同的领域的标签。该数据集共包含 302,424 个节点，平均度数为 9.15。文中使用 2000-2004 年的数据集对所有算法进行训练，并使用 2005 年的数据进行测试、(30%用于验证、)。对于特征，文中使用节点的度。此外，按照 Arora 等人的 sentence embedding 方法处理论文摘要（使用 GenSim word2vec 实现训练的 300 维单词向量）。

Reddit data

第二个任务预测不同的 Reddit 帖子（posts）属于哪个社区。Reddit 是一个大型的在线论坛，用户可以在这里对不同主题社区的内容进行发布和评论。作者在 Reddit 上对 2014 年 9 月发布的帖子构建了一个图形数据集。本例中的节点标签是帖子所属的社区或“subreddit”。文中对 50 个大型社区进行了抽样，并构建了一个帖子-帖子的图，如果同一个用户评论了两个帖子，就将这两个帖子连接起来。该数据集共包含 232965 个帖子，平均度为 492。文中将前 20 天的用于训练，其余的用于测试、(30%用于验证）。对于特征，文中使用现成的 300 维 GloVe CommonCrawl 词向量对于每一篇帖子，将下面的内容连接起来：

• 帖子标题的平均 embedding
• 所有帖子评论的平均 embedding
• 该帖子的得分
• 该帖子的评论数量

Protein-protein interactions

考虑跨图进行泛化的任务，这需要了解节点的角色，而不是社区结构。文中在各种蛋白质-蛋白质相互作用、(PPI) 图中对蛋白质角色进行分类，每个图对应一个不同的人体组织。并且使用从 Molecular
Signatures Database 中收集的位置基因集、motif 基因集和免疫学 signatures 作为特征，gene ontology 作为标签（共 121 个、)。图中平均包含 2373 个节点，平均度为 28.8。文中将所有算法在 20 个图上训练，然后在两个测试图上预测 F1 socres（另外两个图用于验证）。

Exp1

分类准确率（micro-averaged F1 scores）

• 可以看到 GraphSAGE 的性能显著优于 baseline 方法
• 三个数据集上的实验结果表明，一般是 LSTM 或 pooling 效果比较好，有监督都比无监督好
• 无监督版本的 GraphSAGE-pool 对引文数据和 Reddit 数据的连接（concatenation）性能分别比 DeepWalk embeddings 和 raw features 的连接性能好 13.8%和 29.1%，而有监督版本的连接性能分别提高了 19.7%和 37.2%
• 尽管 LSTM 是为有序数据而不是无序集设计的，但是基于 LSTM 的聚合器显示了强大的性能
• 最后，可以看到无监督 GraphSAGE 的性能与完全监督的版本相比具有相当的竞争力，这表明文中的框架可以在不进行特定于任务的微调（task-specific fine-tuning）的情况下实现强大的性能

Exp2

运行时间和参数敏感性

• 计算时间：GraphSAGE 中 LSTM 训练速度最慢，但相比 DeepWalk，GraphSAGE 在预测时间减少 100-500 倍（因为对于未知节点，DeepWalk 要重新进行随机游走以及通过 SGD 学习 embedding）
• 邻居采样数量：图 B 中邻居采样数量递增，F1 也增大，但计算时间也变大。 为了平衡 F1 和计算时间，将 S1 设为 25
• 聚合 K 跳内信息：在 GraphSAGE， K=2 相比 K=1 有 10-15%的提升；但将 K 设置超过 2，效果上只有 0-5%的提升，但是计算时间却变大了 10-100 倍

Exp3

不同聚合器之间的比较

• LSTM 和 pool 的效果较好
• 为了更定量地了解这些趋势，实验中将设置六种不同的实验，即 (3 个数据集）×（非监督 vs. 监督）
• GraphSAGE-LSTM 比 GraphSAGE-pool 慢得多、(≈2×)，这可能使基于 pooling 的聚合器在总体上略占优势
• LSTM 方法和 pooling 方法之间没有显著差异
• 文中使用非参数 Wilcoxon Signed-Rank 检验来量化实验中不同聚合器之间的差异，在适用的情况下报告 T-statistic 和 p-value。

总结

GraphSAGE 的核心：GraphSAGE 不是试图学习一个图上所有 node 的 embedding，而是学习一个为每个 node 产生 embedding 的映射

改进方向：扩展 GraphSAGE 以合并有向图或者多模式图；探索非均匀邻居采样函数

为什么 GCN 是 transductive，为啥要把所有节点放在一起训练？

不一定要把所有节点放在一起训练，一个个节点放进去训练也是可以的。无非是如果想得到所有节点的 embedding，那么 GCN 可以把整个 graph 丢进去，直接得到 embedding，还可以直接进行节点分类、边的预测等任务。

其实，通过 GraphSAGE 得到的节点的 embedding，在增加了新的节点之后，旧的节点也需要更新，这个是无法避免的，因为，新增加点意味着环境变了，那之前的节点的表示自然也应该有所调整。只不过，对于老节点，可能新增一个节点对其影响微乎其微，所以可以暂且使用原来的 embedding，但如果新增了很多，极大地改变的原有的 graph 结构，那么就只能全部更新一次了。从这个角度去想的话，似乎 GraphSAGE 也不是什么“神仙”方法，只不过生成新节点 embedding 的过程，实施起来相比于 GCN 更加灵活方便了。在学习到了各种的聚合函数之后，其实就不用去计算所有节点的 embedding，而是需要去考察哪些节点，就现场去计算，这种方法的迁移能力也很强，在一个 graph 上学得了节点的聚合方法，到另一个新的类似的 graph 上就可以直接使用了。

---