论文：

论文题目：《Inductive Representation Learning on Large Graphs》

论文地址：https://arxiv.org/pdf/1706.02216.pdf

利用图信息的推荐我们在之前的文章里面也介绍了几篇，SRGNN，node2vec，deepwalk等等，这些论文都是利用了图结构的邻域关系来对node进行建模学习。而今天我们要介绍的这篇论文是用邻域聚合(aggregate)的方式来学习的，跟item2vec，node2vec不同的是，i2v直接生成了node的embedding信息，而在Graphsage中，embedding信息是动态聚合生成的，下面一起来看看Graphage是怎么生成embedding的吧。

假设读这篇文章的你已经知道了 deepwalk，node2vec等生成item embedding的方法，那么接下来你将更容易的理解为什么GraphSAGE的方法较这些方法来得好。

一 、背景

本文是斯坦福大学发表在2017年nips的一篇文章，不同于deepwalk等文章通过图结构信息，在训练之前需要所有节点的embedding信息，这种方法对于那些没有见过的node节点是没办法处理的，概括的说，这些方法都是transductive的。此文提出的方法叫GraphSAGE，针对的问题是之前的网络表示学习的transductive，从而提出了一个inductive的GraphSAGE算法。GraphSAGE同时利用节点特征信息和结构信息得到Graph Embedding的映射，相比之前的方法，之前都是保存了映射后的结果，而GraphSAGE保存了生成embedding的映射，可扩展性更强，对于节点分类和链接预测问题的表现也比较突出。

GraphSAGE是为了学习一种节点表示方法，即如何通过从一个顶点的局部邻居采样并聚合顶点特征，而不是为每个顶点训练单独的embedding。这一点就注定了它跟其他方法不同的地方，对于新的节点信息，transdutive结构不能自然地泛化到未见过的顶点，而GraphSAGE算法可以动态的聚合出新节点的embeddinng信息。

回顾一下GCN的问题：

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

GCN虽然能提取图中顶点的embedding，但是存在一些问题：

GCN的基本思想： 把一个节点在图中的高纬度邻接信息降维到一个低维的向量表示。

GCN的优点： 可以捕捉graph的全局信息，从而很好地表示node的特征。

GCN的缺点： Transductive learning的方式，需要把所有节点都参与训练才能得到node embedding，无法快速得到新node的embedding。

回想一下deepwalk这些文章，他们学习的是固定的图结构，当有新的节点或者新的子图加入到整个图中，需要让新的graph或者subgraph去和已经优化好的node embedding去“对齐（align）”。然而每个节点的表示都是受到其他节点的影响，因此添加一个节点，意味着许许多多与之相关的节点的表示都应该调整。这会带来极大的计算开销，即使增加几个节点，也要完全重新训练所有的节点。

为了能够动态的生成node节点的embedding信息，GraphSAGE直接学习来一种节点的表示方法，去学习一个节点的信息是怎么通过其邻居节点的特征聚合而来的。 学习到了这样的“聚合函数”，而我们本身就已知各个节点的特征和邻居关系，我们就可以很方便地得到一个新节点的表示了。

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

二 、Proposed method: GraphSAGE

前面已经说到了GraphSAGE学习的不是node的embedding，而是生成node embedding的映射，这个方法跟其他方法不同：

观察上面三张图，第一张图表示的是k=2 hop的时候的领域关系图。第二张图表示的是通过对邻居节点进行聚合的方式来生成node embedding的过程，其中绿色的聚合表示的是第二跳邻居的聚合，蓝色的聚合表示第一跳邻居的聚合。第三张图表示的是，测试或是推断的时候，使用训练好的系统，通过学习到的聚合函数来对完全未见过的顶点生成embedding。

可以看到GraphSAGE的方法分为三个步骤：

1.对图中每个顶点邻居顶点进行采样，因为每个节点的度是不一致的，为了计算高效， 为每个节点采样固定数量的邻居

2.根据聚合函数聚合邻居顶点蕴含的信息

3.得到图中各顶点的向量表示供下游任务使用

2.1 Embedding generation

这一部分是本篇论文的重头戏，也是本文的核心部分。

首先，我们先明确一下算法1里面各个符号的定义。

1. G=(V,E)表示一个图

2. K是网络的层数，也代表着每个顶点能够聚合的邻接点的跳数，因为每增加一层，可以聚合更远的一层邻居的信息

3. ​,∀v∈V表示节点v的特征向量，并且作为输入

4. {​,∀u∈N(v)}表示在k−1层中节点v的邻居节点u的embedding

5. ​表示在第k层，节点v的所有邻居节点的特征表示

6. ​,∀v∈V表示在第k层，节点v的特征表示

7. N(v)定义为从集合{u ∈ v : ( u , V ) ∈ E}中的固定size的均匀取出，即GraphSAGE中每一层的节点邻居都是是从上一层网络采样的，并不是所有邻居参与，并且采样的后的邻居的size是固定的

介绍完了这些节点的定义后，我们就可以来讲解下算法一的工作流程了，这里我用简单的几句话来讲解一下吧，我相信看完算法一和符号定义的你已经知道这个算法的流程来。

首先，对于所有的顶点v，我们都赋予一个初始的特征表示，这里的特征表示可以是节点的各种特征的组合信息。

然后对于每一层，聚合生成这一层的每一个v的embedding，聚合的方式如下：

最后，我们通过k次聚合，得到了所有v的embedding表示。

看着是挺简单的，接下来我们讲一下几个细节。

2.2 邻居节点的采样

前文已经说到了，对于节点v的邻居节点，我们采用的是固定数量的采样方式来聚合生成v的embedding表示的，设需要的邻居数量，即采样数量为S，若顶点邻居数少于S,则采用有放回的抽样方法，直到采样出S个顶点。若顶点邻居数大于S，则采用无放回的抽样。(即采用有放回的重采样/负采样方法达到S)

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

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

2.3 聚合函数

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

2.3.1 Mean aggregate

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

这里表示的不是concate的意思，而是将v在第k-1层的embedding表示和v在k-1成的所有邻居节点的embedding进行avg pooling的意思。

跟算法一4，5不同的地方在于，mean aggrate操作没有conncate操作，而是用上面这个式子直接替换了算法一中的4，5这两步。

2.3.2 Lstm aggregate

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

2.3.3 Pooling（Max） aggregate

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

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

聚合完v的第k-1层的邻居节点后，还要将这部分的向量跟v在第k-1层的embedding表示concate后送到非线性变换函数后得到最终的embedding表示。

介绍完这三个聚合函数后，聪明的你已经想到了一个可以水论文的方式了，你想到的是：v的邻居节点对于聚合函数的作用是不同的，每一个邻居都应该对应一个weight，没错，就是往这里面加attention，可惜，这篇文章是2017年的文章，而attention也确实在后面的改进中被广泛的加入。

2.4 目标函数

其中u，v是可以通过随机游走方式确定的两个邻居，也就是说u可以通过游走达到v，这个相当于是pos样本，在看看另一边，其中Q是负采样的样本数量，Pn(v)是负采样的概率分布，vn是负样本，E是期望。与DeepWalk不同的是，这里的顶点表示向量是通过聚合顶点的邻接点特征产生的，而不是简单的进行一个embedding lookup操作得到。

从直观上来看这个函数，很容易就能理解：让邻居节点更相近，让非邻居节点更相远，这么训练后，可以用内积表示节点之间的相似度。

负采样参考word2vec，按平滑degree进行，对每个节点采样20个。

三、实验

实验结果1：分类准确率（micro-averaged F1 scores）

如图一所示：

1. 三个数据集上的实验结果表明，一般是LSTM或pooling效果比较好，有监督都比无监督好

2. 尽管LSTM是为有序数据而不是无序集设计的，但是基于LSTM的聚合器显示了强大的性能

实验结果2：运行时间和参数敏感性

如图2所示:

1.计算时间：GraphSAGE中LSTM训练速度最慢，但相比DeepWalk，GraphSAGE在预测时间减少100-500倍（因为对于未知节点，DeepWalk要重新进行随机游走以及通过SGD学习embedding）

2.邻居采样数量：图B中邻居采样数量递增，F1也增大，但计算时间也变大。 为了平衡F1和计算时间，将S1设为25

3.聚合K跳内信息：在GraphSAGE， K=2 相比K=1 有10-15%的提升；但将K设置超过2，效果上只有0-5%的提升，但是计算时间却变大了10-100倍

实验结果3：不同聚合器之间的比较

1.LSTM和pool的效果较好

2.为了更定量地了解这些趋势，实验中将设置六种不同的实验，即(3个数据集)×(非监督vs.监督))

3.GraphSAGE-LSTM比GraphSAGE-pool慢得多(≈2×)，这可能使基于pooling的聚合器在总体上略占优势

4.LSTM方法和pooling方法之间没有显著差异

5.文中使用非参数Wilcoxon Signed-Rank检验来量化实验中不同聚合器之间的差异，在适用的情况下报告T-statistic和p-value。