亿展宏图 第三篇|如何高性能训练图神经网络

作者|王彦杰&闵薇编辑|林颖供稿|eBay支付风控团队本文共4399字，预计阅读时间10分钟更多干货请关注“eBay技术荟”公众号

导读

“亿展宏图”是eBay 支付风控团队推出的系列文章，分享了eBay风控团队工作在图算法方面的一些理解和研究。在上期的亿展宏图 第二篇|在eBay支付风控领域的应用里，我们分享了图算法在风控领域的实际应用案例，并对图神经网络算法进行了介绍。本期亿展宏图，本篇文章会介绍使用mini-batch模式训练图神经网络的三种图采样范式，以及eBay支付风控团队与其他学术机构合作研究的DeGNN算法，以此来更高性能地训练工业级别大规模图神经网络。

背景

近几年，深度学习方法在工业界多个领域均取得了不俗的表现，比如在图像处理领域广泛使用的卷积神经网络(Convolutional Neural Networks,CNN)以及在自然语言处理领域广泛使用的循环神经网络(Recurrent Neural Network,RNN), 它们相对于各个领域的传统方法均表现出明显的优势。

图像处理是对网格状数据进行处理，而自然语言处理是对序列化数据进行处理，这两种数据有一个共同点：它们都来自于欧式空间。而对于图(graph)这种非欧式数据，则无法直接运用CNN或RNN来处理。图神经网络(Graph Neural Networks,GNN)由于其特殊的计算和表征能力，可以用来挖掘图结构数据内部深层次的信息价值，而被学术界和工业界广泛关注，成为了最新的“网红”算法。目前，图神经网络中最常见的是图卷积网络(Graph Convolutional Network,GCN)。虽然GCN理论很完善，但是其计算复杂度非常高。现代工业数据通常会包含百万级到十亿级的节点和链接，这就会使GCN的训练开销极大。导致这一缺陷的主要原因是传统GCN训练时使用的是full-batch模式。这种模式的计算代价高，对存储要求大，且梯度更新效率很低。另外，GCN由于受到过平滑(Over-smoothing)问题的影响，不能堆叠多层，这就限制了其模型的容量和表达能力。目前，在主流研究中使用图采样(Graph Sampling)方法（如GraphSAGE、FastGCN、ClusterGCN）来解决训练效率低和网络深度不足的问题。但简单的增加深度并不一定能提升准确度，甚至还可能产生反向影响，因此提出了一种基于图的自动化联通性分解技术——DeGNN，使得叠加多层GCN变得可能。

一

大规模图训练的瓶颈

在工业级别的应用中，我们所处理的图都是大规模的图。如亚马逊，YouTube等推荐系统中，有数十亿的用户、数千万的商品/视频需要处理；在Facebook，Twitter等社交网络，用户节点个数也会达到数十亿；在我们eBay的用户交易图中，我们所需处理的实体大概有几亿，关联关系有几十亿（有效时间窗口内构建的异构交易图）。

（点击可查看大图）
而GCN^[1]作为空间方法(Spatial)图神经网络开山之作，虽然“如日中天”，但要在这么大规模的图上训练且产生实际应用价值，存在以下问题：

1、full-batch模式的局限性

GCN在训练时使用的是full-batch模式，来更新节点特征，即每次都更新所有节点的Embedding，如下图所示。这意味着它需要加载全图结构以及图上所有节点的特征矩阵，这基本上是无法应用在工业级别的图上的。首先，这么大体量的图和节点特征是无法放进显存的；其次，full-batch模式的梯度更新效率低，收敛速度极慢。

Full-Batch模式下GCN单层更新过程（点击可查看大图）
2、过平滑问题

卷积神经网络 (CNN) 在图像领域取得成功的原因之一就是通过使用多层网络把更深层的信息逐步聚合过来，见下图所示，模型层数越深，模型容量越大，模型推理能力越强，从而带来更广阔的的视野。

深度学习的趋势（点击可查看大图）
但是对于GCN模型，在层数增加的时，节点的邻居会出现大量的重叠节点，这就导致节点的表示向量趋于一致，因此深度GCN存在过平滑(Over-smoothing)的问题。所以，传统GCN会出现层数加深性能反而下降的情况，如下图所示。然而，在实际应用中，我们需要更深的GCN来得到更大的视野和模型容量，以获取足够的信息，来支持我们的后续任务。GCN层数越深模型预测能力下降（点击可查看大图）

二

大规模图训练的改进

为了让 GCN 有能力处理大规模的图，针对GCN在训练过程中存在的效率低下和内存不足等问题，目前的一种解决方案是在每一次训练中只使用全图的一部分进行消息传递，这样每次只需要把采样出来的节点和边加载到GPU进行训练，从而实现mini-batch的梯度更新方式。

在图训练过程，每个节点并不是独立的，而且消息是沿着边进行传递的，如何进行采样非常重要，我们需要解决两个问题：① 如何高效采样；② 如何高质量采样。

研究者已经提出了3种不同的采样范式，分别是：基于节点的采样、基于层的采样和基于子图的采样，见下图所示。

三种采样范式图解（点击可查看大图）

1、基于邻居节点的采样方法 - GraphSage

从GCN的原理中，我们了解到GCN的核心是定义计算图和聚合邻居的信息。然而，前文也介绍到full batch模式下，GCN需要将全图放入显存中进行训练，即需要知道整个图的结构信息，包括待预测的节点。GCN实际上是直推式学习(Transductive Learning)，也就是说这种学习方式对于新节点是没有预测能力的。这就限制了其应用场景。

GraphSAGE^[2]
GraphSAGE^[3]作为基于邻居节点的采样方法，解决了上述两个问题。GraphSAGE在节点的每一跳上都随机采样固定个数的邻居，这使得邻居节点数量的扩张受到限制，从而限制了图的规模，支持了大图训练。同时，它不再关注于直接获得每个节点的Embedding，而是聚合函数。因此，对于新的节点，只需要知道它的点边关系后，使用训练出的聚合函数，即可得到新节点的Embedding，这就实现了归纳学习(Inductive Learning)，提升了其使用价值。GraphSAGE是目前几乎所有工业上图模型的雏形，其特点如下：① 在训练中引入mini-batch模式，提升了训练效率；② 更新梯度时不需要读入全图，对存储更友好；③ 实现了归纳学习，可以预测新节点；④ 随机采样邻居可能存在不稳定以及冗余计算问题。

2、基于层的采样方法 - FastGCN

使用GraphSAGE能够降低邻居节点数量，但是即便每跳固定采样数量，其邻居数量的增长仍然是指数级的。为了更进一步地降低计算复杂度，学者们提出了基于层的采样方法。这类方法将图卷积过程看作是积分变换(Integral Transformation)的过程，图上的每一个点都是从一个概率分布中采样得到的。为了简化计算，可以使用蒙特卡洛近似方法，即只采样部分点来近似整体结果，这样可以在不同层进行独立的采样，从而解决了邻居节点数量爆炸的问题，大大提高了计算速度。

FastGCN
其中，FastGCN^[4]是层采样的代表方法（如上图所示），即在GCN的每一层采样固定数量的节点。具体的采样过程如下：首先，使用节点的度来计算其重要性；接着，根据节点重要性，从概率分布中，定义采样出的节点数量，进行采样。其中，每一层的采样都是相互独立的。因此，在FastGCN中，每个节点参与聚合的邻居节点一定是前一层采样过的节点，这就完全限制住了邻居节点的数量，从而大大加快计算速度。

由此总结出FastGCN算法的特点，如下：

①优势：速度很快，每层只需采样一次，节点邻居数量也被限制；②局限：采样稀疏，由于各层独立采样，可能会导致层间节点连接不足。

3、基于子图的采样方法 - ClusterGCN

面对大图不能一次训练的问题，还有一个方法是：将其切分成若干个小图来训练。这一类方法称为基于子图的采样方法。

ClusterGCN^[2]（点击可查看大图）
ClusterGCN^[5]是这类方法中的代表。事实上，工业界的图都存在一定的社区(Community)结构。因此，ClusterGCN的核心思想是：首先使用聚类算法，在图上找到若干社区，每个社区都保留了与全图接近的局部联通性；在每次mini-batch的训练中，随机选择几个社区合并为一个训练图与基于邻居节点采样的方法相比，当图特别大的时候，这个简单有效的策略可以很好地提升训练效率。因此，ClusterGCN的主要特点如下：
① 优势：扩展性好，每次训练只需要采样子图，邻居节点的搜索不会超出子图；② 局限：子图的分割方法存在一定随机性，而且子图间的联系被切断，可能会和原图存在偏差。

三

DeGNN算法

正如前文所述，尽管GCN广泛应用，但是由于过平滑的问题，GCN的深度受到极大的限制，影响了模型性能的提升。简单的增加深度并不一定能提升准确度，甚至还可能产生反向影响，比如GCN、GraphSAGE和ResGCN在深度增大时准确度反而显著下降。基于此问题，我们与其他学术机构和学者提出了DeGNN的算法框架^[6]（如下图所示）。这个算法从理论上解决了GCN过深带来的训练问题，并提出了一种基于图的自动化联通性分解技术，使得叠加多层GCN变得可能。

DeGNN（点击可查看大图）
使用DeGNN算法时，对于给定的图，若需要分解为K个子图，将会首先使用METIS进行图分解，再使用生成树算法得到各个能访问图中所有顶点的树。以所有生成树作为每个子图的骨架，剩余的边依次循环分配给K个子图，所以分解出的K个子图存在共有的骨架部分。算法的形式化描述如下：
在我们支付欺诈检测的实验案例中，我们构建了基于交易数据的异构图（如下图所示），即交易记录和其相连的实体都是图上的节点，交易记录与实体之间的关系为边。我们将交易分成欺诈交易和正常交易两种标签，然后通过3-hop的方式过滤出一个有关联关系的交易图，其含有约13万个节点，500多万条边，每个节点上有400余个表征风险的特征。异构交易图
在这张交易图上，我们使用直推式(Transductive)的交易节点标签分类模型，即模型的训练集/测试集/验证集都可见全图结构，但是每个划分范围只能访问本划分范围内节点的标签，如下图所示：直推式模式的节点分类^[2]
在这种实验设置下，我们分别使用原始算法以及结合DeGNN图分解方法后的算法进行了对比实验，结果如下图所示，可以看出DeGNN对模型的效果有非常明显的提升。DeGNN在交易图数据集上预测欺诈交易的模型性能（点击可查看大图）

总结

本期的主题是如何高性能训练大规模图神经网络。图神经网络作为处理非欧空间数据的利器，其能力已在很多实验数据集上得到证明。但是，在真实的工业应用中，数据规模过大的事实限制了图神经网络的应用，而且其训练所需的“开销”（如时间、存储要求等）大得令人无法接受。针对这一情况，我们通常会使用采样方法来降低训练规模，使用mini-batch的训练方式。因此，本文梳理了采样方法的主要研究进展，分别介绍节点级采样代表方法GraphSAGE、层级采样代表方法FastGCN以及子图分割代表方法ClusterGCN，他们的特征及解决的问题如下表所示^[7]：

（点击可查看大图）
随后，我们主要介绍了eBay支付风控团队和其他学术机构合作的DeGNN算法，这一算法改进了子图采样方法，可以有效增加GCN的深度从而提升模型表达力。我们通过使用DeGNN在eBay交易图上进行的实验，表明了这一算法有明显的提升效果。下一期将分享我们eBay支付风控团队在图算法遇到海量数据（即图太大问题）时的处理思路，敬请期待！
参考文献[1]Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks." arXiv preprint arXiv: 1609.02907 (2016).[2]Stanford CS224W: Machine Learning with Graphs, http://web.stanford.edu/class/ cs224w/[3]Hamilton, William L., Rex Ying, and Jure Leskovec. "Inductive representation learning on large graphs." arXiv preprint arXiv: 1706.02216 (2017).[4]Chen, Jie, Tengfei Ma, and Cao Xiao. "Fastgcn: fast learning with graph convolutional networks via importance sampling." arXiv preprint arXiv: 1801.10247 (2018).[5]Chiang, Wei-Lin, etal. "Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks." Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & DataMining. 2019.[6]Miao, Xupeng, etal. "DeGNN: Characterizing and Improving Graph Neural Networks with Graph Decomposition." arXiv preprint arXiv: 1910.04499 (2019).[7]Liu, Xin, etal. "Sampling methods for efficient training of graph convolutional networks: A survey." arXiv preprint arXiv: 2103.05872 (2021).

往期推荐

亿展宏图 第一篇|两张图入门图算法

亿展宏图 第二篇|图算法在eBay支付风控领域的应用

点击阅读原文，一键投递

       eBay大量优质职位虚席以待       我们的身边，还缺一个你