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社交网络，先前的研究工作很难用于这些图的处理分析。

简言之，图神经网络的核心是邻域聚合，即整合邻居节点的特征。n个节点的特征维数为d，表示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-wisedropout)，从而规范了模型，提高了模型性能[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.

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