Twitter团队最新研究：快速高效的可扩展图神经网络SIGN

字幕组双语原文：Twitter团队 新研究:快速高效的可扩展图神经网络SIGN

英语原文：Simple scalable graph neural networks

翻译：雷锋字幕组（季一帆、何月莹）

前言：迄今为止，阻碍图神经网络在行业应用中被广泛采用的挑战之一是难以将其缩放到大型图（例如Twitter跟随图）。 之间的相互依赖性使损失函数分解成单个 的贡献具有挑战性。在这篇文章中，我们描述了Twitter开发的一种简单的图神经网络架构，该架构可以处理大量的图。

So far, one of the challenges hindering the wide application of graph neural network in industry is that it is difficult to scale it to large graph (such as twitter following graph). The interdependence between nodes makes it challenging to decompose the loss function into the contribution of a single node. In this article, we describe a simple graph neural network architecture developed by twitter, which can handle a large number of graphs.

本文由Fabrizo Frasca和Emanuele Rossi合著。

图神经网络（GNN）是一种新型的ML模型，专门用于处理图数据。在不同领域，GNN可成功实现领域内关系及相互作用建模，如社会 ，计算机图形与视觉，粒子物理学，化学和医学。但是令人失望的是，对GNN模型的研究和应用都是在规模较小的图上进行的(比如被广泛使用的引用网络数据集-Cora，该数据集仅仅包含约5K [1])，大规模图数据的研究却很少受到关注。与之矛盾的是，在实际工业场景中，需要处理的确实超大规模的图，例如包含数亿 和数十亿边的Twitter或Facebook社交网络，先前的研究工作很难用于这些图的处理分析。

简单来说，图神经网络的核心就是邻域聚合，即整合邻居 的特征。将特征维数为d的n个 表示为n×d的矩阵X，经典的GCN模型[2]就是通过整合邻居 的特征实现某一 的表示，这就是图神经网络中的卷积操作：

Y=ReLU(AXW)

其中，W是所有 共享的可学习参数矩阵，A是线性扩散算子，等于邻域中特征的加权平均值[3]。与传统CNN类似，可以将这种模式依序排列实现多层网络。图神经网络可用于 预测（如检测社交网络中的恶意用户），边预测（如推荐系统中的链接预测），整个图的预测（如预测分子图的化学性质）。另外，通过以下形式构架一个两层的GCN，可实现 分类任务：

Y=softmax(A ReLU(AXW)W’)

那么，将图神经网络扩展到大规模图难在哪里呢？在上述 预测问题中， 作为GNN的训练样本。传统的机器学习通常假设样本是服从某一分布的、相互独立的。这样，可以根据单个样本分解损失函数，并采用随机优化技术批次处理训练数据（mini-batches）。现今几乎每个深度神经网络都是用mini-batches批次训练。

然而在图中， 通过边相互连接，这使得训练集中的样本并不完全独立。此外，由于 间的依赖性，采样可能会引入偏差（例如，可能会使某些 或边被采样的概率更大），需要对此“副作用”进行处理。还有很重要的一点，采样过程中必须保证采样子图的有效结构，确保GNN可以处理。

但之前的许多研究工作忽略了这些问题，如GCN、ChebNet[2]、MoNet[4]和GAT[5]等直接使用全批次数据进行梯度下降，这就导致必须将图的整个邻接矩阵和 特征保存在内存中。即使中等大小的图，L层GCN模型的时间复杂度为?（Lnd2）和空间复杂度为?（Lnd+Ld2）[7]，更不必说大规模图了。

Will Hamilton及其合作者提出GraphSAGE[8]，这是 次考虑到GNN的扩展性问题。GraphSAGE结合邻域采样以及小批次训练在大型图上训练GNN（首字母缩写SAGE即代表“样本和集合”）。论文的主要思想是，为了在L层GCN中计算单个 的训练损失，可以只考虑该 的L跳邻居，因为更远的 不参与计算。但问题是，符合“小世界”特征的图（如社交网络）的某些 的2跳邻域可能已经包含数百万个 ，这样巨大数据无法存储在内存中[9]。GraphSAGE通过对L跳内的邻居采样来解决该问题：对于初始 ，在其1跳邻居 中采样k个 ，然后再对采样 进行类似操作，直至采样到L跳的邻域 。通过这样的方式，每个 有?（k?）个 ，这些 分布在L跳邻域内。如果用b个训练 批次训练，由于每个训练 都有自己独立的L跳邻域，得到与图大小n无关的空间复杂度为?（bk?），计算时间复杂度则为?（bLd2k?）。

GraphSAGE的邻域采样过程。对图中b个 批量采样进行训练（图示中b=2，见浅黄色 和红色 ）；右侧图表示在初始 的2跳领域内的k 采样过程（k=2，按图显示应该是k=5），这些采样 用于GNN的嵌入训练，避免了初始 领域过大的消耗。

GraphSAGE的一个显著缺点是：某些 会被采样多次，从而引入大量的冗余计算。例如，在上图中，深绿色 在两个训练 的单跳邻域中均有出现，这就导致批次处理时对其进行两次嵌入。随着批量大小b和样本数量k的增加，冗余计算量也随之增加。此外，尽管训练每个batch时内存中有?（bk?）个 ，但仅对其中的b个 计算了损失，从某种意义上讲，其他 没有被充分利用。

针对这样的问题，后续工作重点关注对小批次数据的采样，以消除GraphSAGE的冗余计算，提高批次训练效率。典型的工作包括ClusterGCN[11]和GraphSAINT[12]，采用了图采样的方法，这与GraphSAGE的邻域抽样正好相反。具体而言，在图采样方法中，每批次训练数据会对原始图的一个子图进行采样，然后在整个子图上运行类似GCN的模型。该方法的关键在于这些子图保留大多数原始边信息，并且保留了拓扑结构。

ClusterGCN通过对图进行聚类实现此目的，然后，批次训练过程中，模型都在一个集群上训练。这就保证了每批次中的 的紧密连接。

GraphSAINT则是提出了一种通用概率图采样器，通过采样原始图的子图来构造训练批次。进一步，可以根据任务设计不同的图形采样器，例如通过随机游走来计算 的重要性并将其用作采样的概率分布，从而执行统一 采样、边采样或“重要性采样”。

另外，在训练过程中，采样还起到某种边随机失活的作用（edge-wise dropout），从而正则化模型，提高模型性能[13]。但是，在推理阶段则要求看到所有边，这种情况下不需要失活。另外，图采样还可以避免邻域的指数扩展而导致的“过度挤压”现象，突破过去的研究瓶颈[14]。

在我们与Ben Chamberlain，Davide Eynard和Federico Monti发表的新论文中[15]，我们针对 分类问题，探究了设计简洁、无采样架构的可能性。你也许会问，既然采样方法有上文提到的诸多优点，为什么要研究无采样的方法。有以下两个原因： ， 分类问题的具体实例之间存在很大差异，据我们所知，除了降低复杂度外，目前为止没有任何研究表明采样策略有其他积极的意义；其次，采样会带来额外的复杂性。因此，我们认为研究简单、强大、无采样、可扩展的基准架构是有必要的。

我们的研究基于以下发现。首先，在许多情况下，简单的固定聚合器（如GCN）通常都优于GAT或MPNN等复杂模型[16]；其次，虽然深度学习的成功取决于更深的层，但是在图深度学习中，是否需要无脑增加深度仍然是一个悬而未决的问题。特别是Wu等人[17]认为单个多跳扩散层的GCN模型不逊于具有多个层的模型。

通过在单个卷积层中组合不同的、确定的邻域聚合器，可以在不依靠图采样的情况下获得可扩展性良好的模型[18]。换句话说，所有与图相关的操作都在模型的 层中，因此可以预计算；然后将预先聚合的信息作为其余部分的输入。由于不再受邻域聚合影响，因此可以使用多层感知器（MLP）。值得注意的是，通过采用若干专门的、更复杂的扩散算子，即使浅层卷积也可以实现图采样的表达能力。例如，可以设置扩散算子为local substructure counting[19]或graph motifs[20]。

SIGN结构包括一个具有多个线性扩散算子的类GCN层，根据这些扩散算子作用于多跳邻域，然后在 层次上应用MLP。通过对扩散特征（红色标记）进行预计算可极大提升模型效率。

我们将上述可扩展模型称为Scalable Inception-like Graph Network（SIGN），通过下式可直接用于 分类：

Y=softmax(ReLU(XW?|A?XW?|A?XW?|…|A?XW?)W’)

其中，A?是线性扩散矩阵（如归一化的邻接矩阵或其幂，基序矩阵等），W?和W'是可学习的参数。如上图所示，通过附加的 层可以加深网络：

Y=softmax(ReLU(…ReLU(XW?|A?XW?|…|A?XW?)W’)…W’’)

后，当对同一个扩散算子采用不同的幂（如A?=B1,A?=B2）时，相当于从 更多跳范围内聚合信息，这样类似于在一层网络中具有不同接收场的卷积滤波器。类比经典CNN中的inception模块[21]可以更好的理解我们的模型。

如上所述，等式中的矩阵乘积A?X，…，A?X不依赖于模型参数，因此可以预计算。特别是对于超大规模的图，可以使用分布式计算结构（如Apache Spark）高效执行该计算。通过这样的方式，整个模型的计算复杂度仅仅取决于MLP。此外，将扩散转移到预计算步骤，可以聚集所有邻居的信息，避免采样可能导致的信息丢失偏差[22]。

可扩展性和高效率是的优势，由于可以使用小批量梯度下降法进行训练，SIGN可扩展性良好，效率高。试验表明我们的模型在推理时比ClusterGCN和GraphSAINT快两个数量级，同时在确保精度与 新的GraphSAINT一致的情况下，训练速度也明显更快。

不同方法在OGBN-Products数据集上的收敛情况。与GraphSaint和ClusterGCN相比，SIGN收敛速度更快，同时具有更高的F1得分。

不同方法在OGBN-Products数据集上的预处理、训练和推理时间（以秒为单位）。相比其他方法，尽管SIGN的预处理速度较慢，但其在训练中的速度更快，在推理时的速度甚至快了将近两个数量级。

此外，我们的模型支持任何扩散算子。不同类型的图形可能需要不同的扩散算子，我们发现三角形基序这样的算子很适合某些任务。

SIGN和其他可扩展方法在不同数据集上进行 分类任务的表现。基于三角形基序的扩散算子在Flickr上获得明显的性能提升，对PPI和Yelp数据集也有改进。

尽管仅具有单个图卷积层以及线性扩散算子存在局限性，在实际应用中SIGN表现出色，达到甚至超过同等或更复杂模型的结果。鉴于其高效性和简便性，SIGN可作为基线图学习方法应用于不同大规模图数据。更重要的是，这种简单模型的成功引起我们的思考：是否真的需要深度图神经网络？我们发现在社交网络和“小世界”图学习的许多问题中，应该使用更丰富的本地结构，而不是野蛮的堆积深度架构。不过值得注意的是，由于计算迅速。可用简单结构抽取复杂特征，传统的CNN架构越堆越深，用更小的滤波器组成更深的网络。我们不确定相同的方法是否适用于图，因为图的组成要复杂得多，无论网络多深，某些结构都无法通过消息传递来计算。不过可以肯定的是，究竟将来会是哪个方向都需要更多、更复杂的实验来进行检验。

雷锋字幕组是一个由AI爱好者组成的翻译团队，汇聚五五多位志愿者的力量，分享 新的海外AI资讯，交流关于人工智能技术领域的行业转变与技术创新的见解。

团队成员有大数据专家，算法工程师，图像处理工程师，产品经理，产品运营，IT咨询人，在校师生；志愿者们来自IBM，AVL，Adobe，阿里，百度等知名企业，北大，清华，港大，中科院，南卡罗莱纳大学，早稻田大学等海内外高校研究所。

Team members include big data experts, Algorithm Engineers, image processing engineers, product managers, product operations, it consultants, teachers and students; The volunteers come from IBM, AVL, adobe, Ali, Baidu and other well-known enterprises, as well as research institutes of universities at home and abroad, such as Peking University, Tsinghua University, Hong Kong University, Chinese Academy of Sciences, University of South Carolina, Waseda University, etc.

本文转自雷锋网，如需转载请至雷锋网 申请授权。