迄今为止，阻碍图神经网络在工业应用中得到广泛采用的挑战之一，是难以将其扩展到像 Twitter 关注图这样的大型图。节点之间的相互依赖性使得将损失函数分解为单个节点的贡献具有挑战性。在本文中，我们描述了 Twitter 开发的一个简单的图神经网络架构，它可以处理非常大的图。

前文回顾

《专栏 | 图深度学习：成果、挑战与未来》

本文最初发表于 TowardsDataScience 博客，经原作者 Michael Bronstein 授权，InfoQ 中文站翻译并分享。本文由Michael Bronstein和 Fabrizo Frasca、Emanuele Rossi 合著。

图神经网络是近年来兴起的用于学习图结构数据的一类机器学习模型。图神经网络已经成功应用于各种不同领域的关系和相互作用的模型系统，包括社会科学、计算机视觉和图形学、粒子物理学、化学和医学。直到最近，该领域的大多数研究都集中在开发新的图神经网络模型，并在小图上进行测试（如 CORA，它是一个仅包含约 5K 节点的引文网络，目前仍在广泛使用【1】）。另一方面，工业问题通常涉及到规模巨大的图，比如 Twitter 或 Facebook 社交网络，它们包含数亿个节点和数十亿条边。文献中阐述的大部分方法都不适用于这些环境。

简而言之，图神经网络是通过聚合来自局部邻居节点的特征来操作的。将 d 维节点特征排列成n × d维矩阵X此处 n 表示节点数），在流行的 GCN （图卷积网络）模型【2】中实现的对图最简单的卷积类操作，将节点方向的变换和跨相邻节点的特征扩散相结合：

Y= ReLU(AXW)

这里W是所有节点共享的可学习矩阵，A是线性扩散操作符，相当于邻域中特征的加权平均值【3】。这种形式的多层可以像传统的卷积神经网络中那样按顺序应用。图神经网络可以设计成在节点级（例如在社交网络中检测恶意用户）、边级（例如链接预测，这是推荐系统中的典型场景）或整个图（例如预测分子图的化学性质）上进行预测。节点分类任务可以由一个两层的 GCN 来执行，形式如下：

Y= softmax(AReLU(AXW)W’)

为什么扩展图神经网络具有挑战性？在前面提到的节点预测问题中，节点扮演样本的角色，对图神经网络进行训练。在传统的机器学习设置中，通常假设样本是以统计独立的方式从某个分布中提取的。这反过来又允许将损失函数分解为单独的样本贡献，并采用随机优化技术一次处理小子集（小批次）。事实上，几乎每个深度神经网络结构都是用小批次进行训练的。

另一方面，在图中，由于节点通过边相互关联，因此，在训练集中的样本之间产生了统计相关性。此外，由于节点之间的统计相关性，采样可能会引入偏差：例如，它可能会使一些节点或边比训练集中的其他节点或边出现的频率更高，这种“副作用”需要适当处理。最后但并非最不重要的是，必须保证采样子图保持图神经网络可以利用的有意义的结构。

在许多关于图神经网络的早期工作中，这些问题都被掩盖了：诸如 GCN 和 ChebNet【2】、MoNet【4】和 GAT【5】等架构都是使用全批次梯度下降法进行训练的。这就导致了必须在内存中保存整个图的邻接矩阵和节点特征。因此，例如，一个 L 层的 GCN 模型具有时间复杂度 𝒪(Lnd²) 和内存复杂度 𝒪(Lnd +Ld²) 【7】，即使对中等大小的图来说，这些复杂度也是令人望而却步的。

解决可扩展性问题的第一个工作是 GraphSAGE【8】，这是 Will Hamilton 和其他作者共同撰写的一篇开创性论文。GraphSAGE 使用邻域采样和小批次训练相结合的方法来训练大型图上的图神经网络（SAGE 是“Sample and aggregate”的首字母缩写，是该方案的参考）。其主要思想是，为了计算具有 L 层的 GCN 的单个节点的训练损失，只需要该节点的 L-跳邻居，因为图中较远的节点不参与计算。问题是，对于“小世界”类型的图，如社交网络，一些节点的 2 跳邻域可能已经包含了数百万个节点，这使得它太大而无法存储在内存中【9】。GraphSAGE 解决这个问题的方法是对第 L 跳邻居采样：从训练节点开始，它统一使用替换固定数量的 K 个 1 跳邻居进行采样，然后对这些邻居中的每一个再次采样 K 个邻居，以此类推，持续 L 次。这样，对于每个节点，我们都能保证有一个有边界的 L 跳采样邻域的 𝒪(kᴸ) 节点。如果我们再构造一批有 b 个训练节点，每个节点都有自己独立的 L 跳邻域，我们得到的内存复杂度为 𝒪(bkᴸ)，与图的大小 n 无关，GraphSAGE 的一批次计算复杂度为 𝒪(bLd²kᴸ)。

GraphSAGE 邻域采样法。从完整图中对一批 b 节点进行下采样（在本例中，b=2，红色和浅黄色节点用于训练）。右边是以 k=2 采样的 2 跳邻域图，它独立地用于计算嵌入，从而计算出红色和浅黄色节点的的损失。

GraphSAGE 的一个显著缺点是采样节点可能会出现多次，因此可能会引入大量冗余计算。例如，在上图中，深绿色节点出现在两个训练节点的 L 挑邻域中，因此它的嵌入在批次中计算了两次。随着批次大小 b 和样本数量 k 的增加，冗余计算量也随之增加。此外，尽管每个批次的内存都有 𝒪(bkᴸ) 节点，但是损失只计算其中的 b，因此，对于其他节点的计算在某种意义上也是浪费的。

为了消除 GraphSAGE 的冗余计算，提高每个批次的效率，多项后续工作集中在改进小批次的采样。这方面的最新研究成果是 ClusterGCN【11】和 GraphSAINT【12】，它们采用了图采样的方法（而不是 GraphSAGE 的邻域采样）。在图采样方法中，对于每个批次，对原始图的子图进行采样，并在整个子图上运行一个完整的类似 GCN 模型。挑战在于确保这些子图保留大部分原始边，并且仍然呈现有意义的拓扑结构。

ClusterGCN 通过首先对图进行聚类来实现这一点。然后，在每个批次中，模型在一个聚类上进行训练。这允许每个批次中的节点尽可能紧密地连接起来。

GraphSAINT 提出了一种通用的概率图采样器，通过对原始图的采样子图来构造训练批次。图采样器可以根据不同的方案设计：例如，它可以执行均匀节点采样、均匀边采样，或者通过使用随机漫步来计算节点的重要性，并将其作为采样的概率分布，进行“重要性”采样。

同样重要的是要注意到，采样的优势之一是在训练过程中，它可以作为一种边级 Dropout，这可以使模型规范化，并有助于提高性能【13】。然而，边 Dropout 需要在推理时仍能看到所有的边，这在这里是不可行的。图采样可能产生的另一个效果是减少瓶颈【14】，以及由此产生的“过度挤压”现象，这种现象源于邻域的指数扩展。

在我们最近与 Ben Chamberlain、Davide Eynard 和 Federico Monti 合作的论文【15】中，我们研究了针对节点分类问题设计简单、无采样架构的可能性。你可能想知道，考虑到我们刚才强调的间接好处，为什么还会有人宁愿放弃采样策略？这其中有几个原因。首先，节点分类问题的实例彼此可能存在很大的不同，而且据我们所知，到目前为止还没有系统地研究采样实际上除了减轻计算复杂性之外还提供了积极效果的情况。其次，采样方案的实现引入了额外的复杂性，我们相信一个简单的、强大的、无采样的、可扩展的基准架构是很有吸引力的。

我们的方法是基于最近的一些实证研究结果。首先，简单的固定聚合器（如 GCN）在许多情况下往往比较复杂的聚合器性能更好，比如 GAT 或 MPNN【16】。其次，虽然深度学习的成功是建立在很多层的模型之上，但是在图深度学习中是否需要深度，仍然是一个有待研究的问题。特别是，Wu 和合著者【17】认为，具有单个多跳扩散层的 GCN 模型可以与多层模型具有同等的性能。

通过将不同的、固定的邻域聚合器结合在一个卷积层中，可以获得一个极易扩展的模型，而不需要借助图采样【18】。换句话说，所有与图相关的（固定的）操作都在架构的第一层，因此可以进行预计算；然后可以将预聚合的信息作为输入馈送到模型的其余部分，由于缺乏邻域聚合，该模型归结为多层感知器（Multi-layer perceptron，MLP）。重要的是，即使采用这样一个浅卷积方案，通过采用几个可能是专门的、更复杂的扩散操作符，仍然可以保留图过滤操作的表达力。例如，可以设计包括局部子结构计数【19】或图 Motif【20】的操作符。

SIGN 架构由一个类似于 GCN 的层组成，其多个线性扩散操作符可能作用域多跳邻域，然后是节点级应用 MLP。其效率的关键是对扩散特征（红色标记）的预计算。

所提出的可扩展架构，我们称之为可扩展初始类图网络（Scalable Inception-like Graph Network，SIGN），对于节点分类任务，其形式如下：

Y= softmax(ReLU(XW₀ | A₁XW₁ | A₂XW₂ | … | AᵣXWᵣ) W’)

这里Aᵣ 是线性扩展矩阵（例如归一化邻接矩阵、其幂或 Motif 矩阵），Wᵣ 和W’是可学习的参数。如上图所示，通过附加的节点层，可以使网络变得更深：

Y= softmax(ReLU(…ReLU(XW₀ | A₁XW₁ | … | AᵣXWᵣ) W’)… W’’)

最后，当对同一个扩散操作符采用不同的幂级数时（如A₁=B¹，A₂=B²等），图操作有效地从邻域中越跳越多地聚合，类似于在同一网络层中拥有不同感受野的卷积滤波器。这种与经典 CNN 中流行的初始模块的类比解释了所提出的架构的名称【21】。

如前所述，上述方程中的矩阵乘积A₁X，……，AᵣX并不依赖于可学习的模型参数，因此可以预计算。特别是，对于非常大的图，这种预计算可以使用 Apache Spark 这样的分布式计算基础设施有效地进行扩展。这有效地降低了整个模型的计算复杂度，达到了 MLP 的水平。此外，通过将扩展转移到预计算步骤，我们可以聚合来自所有邻居的信息，从而避免采样以及随之而来的可能信息损失和偏差。

SIGN 的主要优点在于它的可扩展性和效率，因为它可以使用标准的小批次梯度下降法进行训练。我们发现，我们的模型在推理时比 ClusterGCN 和 GraphSAINT 快了两个数量级，而且在训练时也快得多（所有这些都保持了正确率与非最先进的 GraphSAINT 接近）。

OGBN-Products 数据集上不同方法的收敛性。与 GraphSaint 和 ClusterGCN 相比，SIGN 的变体收敛速度更快，验证 F1 得分也更高。

OGBN-Products 数据集上不同方法的预处理、训练和推理时间（以秒为单位）。虽然 SIGN 预处理速度较慢，但它的训练速度较快，推理时间比其他方法快近两个数量级。

此外，我们的模型支持任何扩散操作符。对于不同类型的图，可能需要不同的扩散操作符，而且我们发现一些任务可以从基于 Motif 的操作符（如三角形技术）中受益。

SIGN 和其他可扩展方法在一些流行数据集的节点分类任务上的性能。基于三角形 Motif 的扩散操作符在 Flickr 上获得了有趣的性能提升，并在 PPI 和 Yelp 上提供了一些改进。

尽管只有单个图卷积层和线性扩散操作符的限制，但 SIGN 在实践中表现得非常好，取得了与更复杂的模型相当甚至更好的结果。鉴于它的速度和实现的简单性，我们设想 SIGN 将成为大规模应用的简单基线图学习方法。也许更重要的是，这样一个简单模型的成功，引出了一个更基本的问题：我们真的需要深度图神经网络吗？我们猜想，在许多关于社交网络和“小世界”图的学习问题中，我们应该使用更丰富的局部结构，而不是求助于蛮力式的深度架构。有趣的是，传统的卷积神经网络架构是按照相反的趋势发展的（更深的网络，更小的过滤器），因为有计算优势，并且能够将简单的特征组成复杂的特征。我们不确定同样的方法是否适用于图，因为在图中，组成性要复杂得多（例如，某些结构不能通过消息传递来计算，无论网络有多深）。但可以肯定的是，还需要更精细的实验来检验这一猜想。

参考文献

【1】最近引入的Open Graph Benchmark现在提供了包含数百万个节点的大型图。社区可能需要一段时间才能转向它。

【2】《半监督分类与图卷积网络》（Semi-supervised classification with graph convolutional networks，T.Kipf、M.Welling，2017 年）。Proc.ICLR 引入了流行的 GCN 架构，该架构是基于 Defferrard 等人提出的 ChebNet 模型的简化而衍生的。《具有快速局部光谱过滤功能的图上卷积神经网络》（Convolutional neural networks on graphs with fast localized spectral filtering），Proc.NIPS，2016 年。

【3】作为扩散操作符，Kipf 和 Wling 使用了带有自环的图邻接矩阵（即节点本身参与其特征更新），但也有其他可能的选择。扩散操作可以像 MoNet【4】或 GAT【5】模型一样，做成特征依赖型的A(X)X（即仍然是节点特征的线性组合，但权重取决于特征本身），也可以像消息传递神经网络（Message-passing neural networks，MPNN）【6】一样，做成完全非线性的 𝒜(X)。为简单起见，我们将重点讨论应用于节点分类的 GCN 模型。

【4】《使用混合模型卷积神经网络在图和流形上进行几何深度学习》（Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs），F.Monti 等人，2017 年，Proc.CVPR。

【5】《图注意力网络》（Graph Attention Networks），P. Veličković 等人，2018 年，Proc.ICLR。

【6】《量子化学中的神经信息传递》（Neural message passing for quantum chemistry），J. Gilmer 等人，2017 年，Proc.ICML。

【7】此处为简单起见，我们假设图具有边数 |ℰ|=𝒪(n) 的稀疏性。

【8】《大型图的归纳表示学习》（Inductive Representation Learning on Large Graphs），W. Hamilton 等人，2017 年，Proc.NeurIPS。

【9】这类图的邻居数量随着邻域的扩散而呈指数级增长。

【10】替换采样意味着某些相邻节点可以出现多次，特别是当相邻节点的数目小于 k 时。

【11】《Cluster-GCN：一种训练深度大型图卷积网络的有效算法》（Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks），W.-L. Chiang 等人，2019 年，Proc.KDD。

【12】《GraphSAINT：基于图采样的归纳学习方法》（GraphSAINT: Graph Sampling Based Inductive Learning Method），H.Zeng 等人，2020 年，Proc. ICLR。

【13】《DropEdge：基于深度图卷积网络的节点分类》（DropEdge: Towards deep graph convolutional networks on node classification），Y. Rong 等人，2020 年，Proc.ICLR。一种类似于 DropOut 的想法，在训练过程中使用随机的边子集。

【14】《论图神经网络的瓶颈及其实践意义》（On the bottleneck of graph neural networks and its practical implications），U. Alon、E. Yahav，2020 年，arXiv:2006.05205。该论文确定了图神经网络中的过度挤压现象，这与序列递归模型中观察到的现象相似。

【15】《SIGN：可扩展的初始图神经网络》（SIGN: Scalable Inception Graph Neural Networks），Frasca 等人，2020 年。图表示学习及其它方面的 ICML 研讨会。

【16】《图神经网络评估的缺陷》（Pitfalls of graph neural network evaluation），O. Shchur 等人，2018 年，关系表征学习研讨会。论文表明了简单的图神经网络模型与更为复杂的图神经网络模型具有同等的性能。

【17】《简化图神经网络》（Simplifying graph neural networks），F. Wu 等人，2019 年，Proc.ICML。

【18】虽然我们强调 SIGN 不需要采样来提高计算效率，但图下采样还有其他原因可以解释它为什么是有用的。《扩散改进图学习》（Diffusion improves graph learning），J. Klicpera 等人，2020 年，Proc.NeurIPS 表明，采样扩散矩阵提高了图神经网络的性能。我们在早期的 SIGN 实验中也观察到了同样的现象。

【19】《通过子图同构计数提高图神经网络的表达能力》（Improving graph neural network expressivity via subgraph isomorphism counting），G. Bouritsas 等人，2020 年，arXiv:2006.09252。论文说明了如何通过结构节点编码阔的可证明强大的图神经网络。

【20】《MotifNet：基于 Motif 的有向图卷积网络》（MotifNet: a motif-based graph convolutional network for directed graphs），F. Monti、K. Otness、M. M. Bronstein，2018 年，arXiv:1802.01572。论文使用了基于 Motif 的扩散操作符。

【21】《深入了解卷积》（Going deeper with convolution），C. Szegedi 等人，2015 年，Proc.CVPR 在已经很经典的 Google LeNet 架构提出了初始模块。公平地说，我们并不是第一个想到图初始模块的人。我们的合作者，来自慕尼黑理工大学（TU Munich）的 Anees Kazi，去年是伦敦帝国学院（Imperial College）的访问学生，是她首先给我们介绍了图初始模块。

【22】请注意，到达高阶领域通常是通过深度堆叠图卷积层与直接邻域的操作来实现的；在我们的架构中，这是在第一层通过图操作符的幂来直接实现的。

作者介绍：

Michael Bronstein，伦敦帝国理工学院教授，Twitter 图机器学习研究负责人，CETI 项目机器学习主管、研究员、教师、企业家和投资者。

原文链接：

https://towardsdatascience.com/simple-scalable-graph-neural-networks-7eb04f366d07

创作场景

简单且可扩展的图神经网络