NIPS 2017 | 斯坦福GraphSAGE：改进的GCN

导读

论文：

Inductive Representation Learning on Large Graphs

任务：

对GCN进行改进，完成在大图上的归纳表示学习(inductive)

本文：

提出GraphSAGE模型

机构：

斯坦福大学

代码：

https://github.com/cenyk1230/GATNE

官方介绍链接：

http://snap.stanford.edu/graphsage/

发表：

NIPS 2017

一、动机

动机一：

大型图中节点的embedding在机器学习中有许多应用（例如，节点分类、聚类、链接预测）。

然而大多数embedding框架本质上是推导式的(transductive)，并且只能为单个的固定的图生成embedding表示。

如GCN，利用了图的整个邻接矩阵和图卷积操作融合相邻节点的信息，因此一般用于 Transductive 任务，而不能用于处理 Inductive 任务。（后面有解释）

这些方法不能有效地推广到模型训练中没见过的节点，如演化图(evolving graphs)中。并且这些方法不能在不同的图中学习推广。

动机二：

现有的GCN模型是全图训练方式，即只有一轮迭代。这意味着所有数据的损失只能贡献一次梯度，无法做到DNN常见的小批量更新，且效率低下。这对大规模的图结构来说并不友好。

因此：本文提出 GraphSAGE 模型。

相比之下，

GraphSAGE是一个归纳(inductive)框架，可以利用节点属性信息高效地生成以前未见过的数据的表示。

GraphSAGE也通过对邻居的采样控制达到了小批量训练，高效的完成大图上的归纳表示学习。

它需要在一个示例图或一组图上进行训练。

训练后，该模型可用于为「以前未见过的节点」或「全新的输入图」生成节点embedding，只要这些图与训练数据具有相同的属性模式(have the same attribute schema as the training data)。

该模型对GCN主要的改动在两方面：

1. 将GCN的全图训练方法改为小批量训练方式，使大规模图数据的分布式训练成为可能
2. 对聚合邻居的操作进行拓展，提出了替换原有聚合操作的几种新方式

二、简介

截止目前(2017年)，图卷积网络（GCN）仅应用于固定的图与transductive任务。

本文将GCN扩展到可归纳的(inductive)无监督学习的任务，并提出了一个框架。

该框架将GCN方法推广到使用可训练的（除了简单的卷积外的）其他聚合函数。

本论文提出了一个通用的框架：GraphSAGE（SAmple and aggreGatE，采样和聚合），用于归纳(inductive)节点embedding。

与基于矩阵分解的embedding方法不同，本文利用节点特征（例如，文本属性、节点配置文件信息、节点度）来学习可推广到不可见节点embedding的函数。

通过在学习算法中加入节点特征，模型可以同时学习每个节点邻域的拓扑结构以及节点特征在邻域中的分布。

虽然该方法关注特征丰富的图，但也可以利用所有图形中存在的结构特征（例如，节点的度）。

因此，该算法也适用于没有节点特征的图。

在训练阶段：

该模型不是为每个节点训练一个不同的embedding向量，而是训练一组聚合器函数，学习从节点的局部邻域聚合特征信息（如下图1）。

每个聚合器函数聚合来自给定节点的不同跳数或搜索深度的信息。

在infer阶段：

使用经过训练的模型，通过应用学到的聚合函数，可以为完全没见过的节点生成embedding向量。

👉 推导式 transductive 与 归纳式 inductive：

- Transductive：

通常指要预测的节点在训练时已经出现过， 例如有一个作者关系网络，知道部分作者的类别，用整个网络训练 GCN，最后预测未知类别的作者。

- Inductive：

指要预测的节点在训练时没有出现，或用今天的图结构训练，预测明天的图。

图1: GraphSAGE采样和聚合方法的直观说明

三、模型具体方法

本论文的方法 背后的关键思想是：学习如何从节点的局部邻域（例如，附近节点的度或文本属性）聚合特征信息。

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

第3.2节，我们描述如何使用标准随机梯度下降和反向传播技术学习GraphSAGE模型的参数。

3.1、前向传播：embedding生成

在模型已经过训练且参数固定的情况下进行预测

其前向传播的方法为：

如上图所示，2～6行我们可以看到该算法的遍历操作：

该过程为：

1. 在每一层k，对于每个节点v，会使用第4行的聚合函数，聚合该节点的邻居节点的信息，其中邻居节点为k-1层上采样得到；
2. 在第5行，将聚合得到的邻居信息与将上一层的自身信息进行融合，得到该节点v在当前层k上的信息表示；
3. 在第7行，对每一层上得到的节点特征向量进行归一化处理，统一到单位尺度上；
4. 在第9行，即完成了对所有节点特征向量的提取。

3.2、反向传播：学习模型参数

无监督训练方式

我们设置无监督损失函数应用于模型的输出表示Zu，∀U∈V；并调整权重矩阵Wk，∀K∈ {1，…，K}，和通过随机梯度下降的聚合函数的参数。

该损失函数鼓励附近的节点具有相似的表示，同时强制要求不同节点的表示具有高度不同性：

其中：

v是在固定长度随机游走中，在u附近共现的节点，σ是sigmoid函数，Pn是负采样分布，Q定义了负样本的数量。

重要的是：

与以前的embedding方法不同，我们提供给该损失函数的表示是从节点的局部邻域中包含的特征生成的，而不是为每个节点训练唯一的embedding。

有监督训练方式

监督学习的loss根据任务的不同直接设置目标函数即可；

如，节点分类损失函数使用交叉熵等。

3.3、聚合函数

由于节点的邻居没有自然顺序，因此算法1中的聚合器函数必须在无序向量集上运行。

因此理想情况下，聚合器函数需要保证以下几点

1. 自适应：对节点数量做到自适应，输出维度不受邻居节点的数量变化的影响，输出维度一致。
2. 对称的：即具有排列不变性。对其输入的排列不变，置换不变的；聚合函数的对称性保证了我们的神经网络模型可以训练并应用于任意有序的节点邻域特征集。
3. 可导的：从模型优化的角度上，聚合函数要求可导，并能够保持较高的表示能力。

本文推广的聚合器函数：

• Pooling aggregator: 类似于Pool的操作，非线性感知机+取最大值。
• Mean Aggregator：将邻居节点的特征取平均，GCN是取邻居节点的总和。
• LSTM Aggregator: 将邻居节点随机排序，然后通过LSTM得到邻居节点的信息。

四、实验结果

数据集及任务：

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

Baselines：

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

本文实验结果：