【图神经网络】GraphSAGE

一、Address

发表于NIPS 2017的一篇论文

地址：https://arxiv.org/pdf/1706.02216v4.pdf

二、Introduction

首先介绍以下什么是Inductive learing

在训练过程中，已知testing data（unlabelled data）是transductive learing

在训练过程中，并不知道testing data（训练的时候只用训练样本） 是inductive learing

GraphSAGE是一个通用的inductive框架，

GraphSAGE不是为每个节点训练一个不同的嵌入向量，而是训练一组聚合器函数，这些函数学习从节点的局部邻域递归地聚合特征信息（figure 1）每个聚合器函数从给定节点以外的不同跳数或搜索深度聚合信息。在测试或推理时，GraphSAGE使用经过训练的系统通过应用学习的聚合函数为未知的节点生成嵌入。

三、Model

GraphSAGE背后的关键思想是，学习如何从节点的局部邻域聚合特征信息。

首先描述GraphSAGE embedding生成（即前向传播）算法，该算法在假定GraphSAGE模型参数已经学习的情况下为节点生成embedding

3.1 Embedding生成

其中为一个图，为网络的层数，也代表着每个顶点能够聚合的邻接点的跳数，同时也是聚合器的数目，权重矩阵的数目。

3.2 Learning the parameters of GraphSAGE

本文提了有监督和无监督两种学习方式

无监督学习

基于图的损失函数期望临近节点具有相似的向量表示，同时强制要求分离的节点的表示不同：

其中是在固定长度的随机游动中在u附近出现的节点，是负采样分布，是负样本数量，是sigmoid函数。这个损失函数的表示zu是从节点的局部邻域中包含的特征生成的，而不是为每个节点训练一个唯一的嵌入（通过嵌入查找）。

有监督学习

监督学习形式根据任务的不同直接设置目标函数即可，如最常用的节点分类任务使用交叉熵损失函数。

3.3 Aggregator架构

图上的节点的邻居是无序列，因此，聚合器函数必须在无序的向量集上操作。所以理想情况下，聚合函数应该是对称的（即即改变输入的顺序，函数的输出结果不变）

Mean aggregator

文章介绍第一个聚合函数是平均算子，这里我们只取中向量的元素平均值。Mean aggregator聚合器几乎等同于在跨导GCN框架中使用的卷积传播规则。特别是，可以通过将算法1中的第4行和第5行替换为以下为GCN方法的inductive变体：

上式对应于伪代码中的第4-5行，直接产生顶点的向量表示，而不是邻居顶点的向量表示。mean aggregator将目标顶点和邻居顶点的第k-1层向量拼接起来，然后对向量的每个维度进行求均值的操作，将得到的结果做一次非线性变换产生目标顶点的第k层表示向量。

LSTM aggregator

LSTMs具有更大的表达能力。然而，需要注意的是，lstm不是固有对称的（即，它们不是置换不变的），因为它们以顺序方式处理它们的输入。我们通过简单地将LSTMs应用于节点邻居的随机排列，使LSTMs适应于在无序集上操作

“

LSTM相比简单的求平均操作具有更强的表达能力，然而由于LSTM函数不是关于输入对称的，所以在使用时需要对顶点的邻居进行一次乱序操作。

”

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

Pooling aggregator

Pooling aggregator是对称的和可训练的。在这种池方法中，每个邻居的向量通过完全连接的神经网络独立地馈送（进行一次非线性变换）；在这种转换之后，进行过pooling操作来聚合邻居集中的信息，然后将结果与目标节点的embedding进行拼接，再进行一次非线性变换，最后得到第k层表示向量

四、Experiments

五、Conclusion

1.GraphSAGE是一个通用的inductive学习框架，核心是学习为每一个node生成表示向量的映射，而不用在数据更新之后重新训练一次。

2.GraphSAGE的采样机制有效提高了gcn的扩展性和有效解决了训练难度的问题。