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

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

英语原文： Simple scalable graph neural networks

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

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

本文由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模型的时间复杂度为?（Lnd²）和空间复杂度为?（Lnd +Ld²）[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ᴸ），计算时间复杂度则为?（bLd²kᴸ）。

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₁=B¹, A₂=B²）时，相当于从节点更多跳范围内聚合信息，这样类似于在一层网络中具有不同接收场的卷积滤波器。类比经典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，阿里，百度等知名企业，北大，清华，港大，中科院，南卡罗莱纳大学，早稻田大学等海内外高校研究所。

如果，你也是位热爱分享的AI爱好者。欢迎与雷锋字幕组一起，学习新知，分享成长。

雷锋网 (公众号：雷锋网) 雷锋网

雷锋网版权文章，未经授权禁止转载。详情见 转载须知 。