GraphSAGE 是 2017 年提出的一种图神经网络算法，解决了 GCN 网络的局限性: GCN 训练时需要用到整个图的邻接矩阵，依赖于具体的图结构，一般只能用在直推式学习 Transductive Learning。GraphSAGE 使用多层聚合函数，每一层聚合函数会将节点及其邻居的信息聚合在一起得到下一层的特征向量，GraphSAGE 采用了节点的邻域信息，不依赖于全局的图结构。
1.前言
在之前的文章《图神经网络 GNN 之图卷积网络 (GCN)》和《GAT 图注意力网络 Graph Attention Network》分别介绍了 GCN 和 GAT，不熟悉的童鞋可以参考一下。
图神经网络的任务一般有 Transductive (直推式) 和 Inductive (归纳式)。Transductive 通常指要预测的节点在训练时已经出现过， 例如有一个作者关系网络，知道部分作者的类别，用整个网络训练 GCN，最后预测未知类别的作者。Inductive 指要预测的节点在训练时没有出现，例如用今天的图结构训练，预测明天的图。
GCN 利用了图的整个邻接矩阵和图卷积操作融合相邻节点的信息，因此一般用于 Transductive 任务而不能用于处理 Inductive 任务。因此 2017 年 GraphSAGE 算法被提出，用于解决 GCN 的问题，《Inductive Representation Learning on Large Graphs》。
2.GraphSAGE
GraphSAGE 包含采样和聚合 (Sample and aggregate)，首先使用节点之间连接信息，对邻居进行采样，然后通过多层聚合函数不断地将相邻节点的信息融合在一起。用融合后的信息预测节点标签。下图展示了 GraphSAGE 的聚合过程，采用了两层聚合层。
GraphSAGE 聚合示意图
上图中的包括两层聚合，对应的聚合函数为 aggregator1 和 aggregator2。通过 k 层聚合之后，可以得到节点最终的表示向量，GraphSAGE 的伪代码如下：
GraphSAGE 伪代码
伪代码中的 h0 表示节点 v 的初始特征向量，包含 K 层聚合操作。在第 k 次聚合生成 v 节点特征向量时，会采用聚合函数把 v 节点的邻居信息融合在一起。这一操作也可改成 minibatch 的，伪代码如下：
GraphSAGE minibatch 伪代码
上面的伪代码中，B = BK 为要生成向量的节点集合， Bk-1 是深度为 1 的邻域，
B0 为深度为 K 的邻域，B0 包含的节点最多。Nk(v) 表示 v 节点在第 k 次聚合时的邻域，节点在每一层的邻域数量都不同，通过采样得到。2.1 GraphSAGE 聚合函数
GraphSAGE 提供了四种聚合节点的函数：
Mean aggregator: 对节点 v 进行聚合时，对节点 v 和邻域的特征向量求均值。
Mean aggregator
GCN aggregator: 采用了类似 GCN 卷积的方式进行聚合，公式和 Mean aggregator 类似：
GCN aggregator
LSTM aggregator: 作者任务 LSTM 有比较好的抽取特征能力，因此也使用了 LSTM 进行聚合，但是因为节点之间没有明显的顺序关系，因此会打乱之后放入 LSTM。
Pooling aggregator: 先把所有邻居节点的特征向量传入一个全连接层，然后使用 max-pooling 聚合。
Pooling aggregator
2.2 GraphSAGE 训练
GraphSAGE 可以采用无监督训练或者有监督训练。无监督训练采用负采样算法，公式如下：
无监督损失函数
公式中的 zu 是经过 GraphSAGE 聚合之后的特征向量，节点 v 是节点 u 邻域内的节点，而 Q 表示负采样次数。
对于有监督训练可以使用任务相关的目标函数，例如节点分类时采用交叉熵损失函数。
3.实验结果
作者对比了不同算法的性能，也对比了 GraphSAGE 四种聚合方式的效果，如下表所示。
不同算法的性能
下图 A 是训练和测试时间的实验结果，B 是采样邻域大小对性能影响的结果。
4.参考文献
Inductive Representation Learning on Large Graphs
