3.大规模图神经网络

真实世界的图可能具有非常大的规模，因此让 GNN 有能力处理大规模图是非常重要的研究课题。

基本的 GNN 通常无法处理大规模图，因为其通常无法满足巨大的内存需求，而且梯度更新的效率也很低。

为了让 GNN 有能力处理大规模图，研究者已经提出了三种不同的采样范式：基于节点的采样、基于层的采样和基于子图的采样。

其中，逐节点采样是根据目标节点执行采样，而逐层采样是基于卷积层来执行采样，逐图采样则是从原图采样子图，然后使用子图进行模型推理。

根据这三种范式，可以知道为了实现大规模 GNN，我们需要解决两个问题：如何设计高效的采样算法？如何保证采样质量？

近些年在构建大规模 GNN 方面已经出现了一些成果，下图给出了这些成果的时间线：

接下来我们将按这一时间线简要介绍这些研究成果。

首先来看 GraphSAGE，其可被视为原始 GCN 的一种扩展：在 GCN 的平均聚合器的基础上增加了许多广义上的聚合器，包括池化聚合器和 LSTM 聚合器。不同的聚合器也会对模型产生不同的影响。此外，在聚合之后，不同于 GCN 使用的求和函数，GraphSAGE 使用了连接函数来结合目标节点机器邻近节点的信息。这两大改进是基于对 GCN 的空间理解得到的。

为了实现大规模 GNN，GraphSAGE 首先采用了 mini-batch 的训练方法，这样可以降低训练期间的通信成本。在每次迭代中，仅会考虑用于计算表征的节点。但是，mini-batch 训练可能出现邻近节点扩张的问题，使得 mini-batch 在层数较多时需要采用图的大部分乃至全部节点！

为了解决这一问题并进一步提升性能，GraphSAGE 采用了固定采样个数的的邻近采样方法，即每层都采样固定大小的邻近节点集合。

从上右图可以看到，采用固定采样个数的采样方法后，采样节点的数量降低了。当图的规模很大时，这一差距会更加显著。不过，GraphSAGE 在网络层数较大时依然无法避免邻近节点扩张问题，采样质量上也无法得到保证。

为了进一步降低采样规模和得到一些理论上的质量保证，VR-GCN 整合了基于控制变量的估计器（CV 采样器）。其可以维持历史隐藏嵌入（historical hidden embedding）来获得更好的估计，这个历史隐藏嵌入可用于降低方差，进而消除方差，实现更小的采样规模。VR-GCN 的数学形式如下：

不过，VR-GCN 也有一个缺点：需要额外的内存来存储所有的历史隐藏嵌入，这使得我们难以实现大规模扩展。

上面我们可以看到，基于节点的采样方法并不能彻底解决邻近节点扩张问题。接下来看基于层的采样方法。

FastGCN 提出从Functional generalization的角度来理解 GCN，并为 GCN 给出了基于层的估计形式：

基于此，我们可以在每层都采样固定数量的节点。更进一步，FastGCN 还提出了基于重要度的采样模式，从而降低方差。在采样过程中，每一层的采样都是相互独立的，而且每一层的节点采样概率也保持一致。下图是 GCN 与 FastGCN 的对比：

可以看出，FastGCN 的计算成本显著更低，而且研究表明，这种采样模式从期望上并不会丢失太多信息，因为其在执行重要度采样时会进行随机化处理，通过足够多epoch的训练，每个节点和链接都有期望被采样。

可以看出，基于层采样的FastGCN 彻底解决了邻近节点扩张问题，而且采样方法有质量保证。但是该方法的缺点是无法获得层之间的相关性，模型的表现也可能受到负面影响。

为了更好地获得层之间的相关性，ASGCN 提出了自适应层式采样方法，即根据高层采样结果动态调整更低层的采样概率。如下左图所示，在对底层采样的时候ASGCN会考虑采样高层采样的邻居节点，使得层之间的相关性得到很好的保留。如下右图所示，整个采样过程是自上而下的。我们首先采样输出层的目标节点，然后根据其采样结果采样中间层的节点，然后重复这个过程直到输入层。在采样过程中，每层采样节点的数目也会保持一个固定值。

另外，为了降低采样方差，ASGCN 还引入了显式方差下降法（explicit variance reduction），以优化损失函数中的采样方差。

总体来说，ASGCN 能获得更好的性能，方差控制也更好，但由于采样过程有额外的层间依赖关系需要考虑，采样效率会受到一些影响。

接下来出现了基于子图的采样方法。ClusterGCN 首先使用图分割算法将图分解为更小的聚子图，然后在子图层面上组成随机的分批，再将其输入 GNN 模型，从而降单次计算需求。

通过限制子图的大小，这种方法也可以有效避免邻近节点扩张问题，因为在每一层中，采样的范围都不会超过聚类子图。

不过，ClusterGCN 的论文并没有对这种方法的采样质量进行实证研究。

GraphSAINT 则并未在采样过程中使用聚类算法（这会引入额外的偏差和噪声），而是直接通过子图采样器来采样用于mini-batch 训练的子图。其给出了三种采样器的构建方式，分别为基于节点的采样、基于边的采样和随机游走采样，如下所示：

GraphSAINT 还从理论上分析了控制采样器的偏差和方差的方法，其中包括用于消除采样偏差的损失归一化和聚合归一化方法：

另外，该论文还提出通过调整边采样概率来降低采样方差。作为当前最佳的方法，GraphSAINT 的表现也在实验中得到了证明。具体详情请浏览 ICLR 2020 论文《GraphSAINT: Graph Sampling Based Inductive Learning Method》。

很显然，大规模图神经网络方面还有很大的进一步研究空间，比如更高效的采样技术、适用于异构图或动态图的架构等等。

专栏文章内容及配图由作者撰写发布，仅供工程师学习之用，如有侵权或者其他违规问题，请联系本站处理。 联系我们