扩展图神经网络：暴力堆叠模型深度并不可取编译|MrBear编辑|陈大鑫目前

文章插图
编译 | Mr Bear
编辑 | 陈大鑫
目前，阻碍图神经网络在业界大规模应用的挑战之一是：图神经网络很难被扩展到 Twitter 的用户关注关系图这类大型图上。
节点之间的相互依赖关系使我们很难将损失函数分解为各个独立节点的影响。
在本文中，我们介绍了Twitter 研发的一种简单的图神经网络架构，该架构可以在大型图上有效工作。
1 图神经网络介绍
图神经网络（GNN）是一类近年来逐渐兴起的机器学习模型，它被用于学习图结构的数据。 GNN 已经被成功地应用于对各种不同领域（包括社会科学、计算机视觉和图形学、粒子物理学、化学、医学等）的关系和交互的系统进行建模。
直到最近，该领域内大多数的研究仍重点关注于研发新型 GNN 模型，并且在小型图（例如，仅仅包含大约 5K 节点的引用网络 Cora 仍然被广泛使用）上测试这些模型；相对来说，处理大规模应用的研究工作鲜有人涉足。
另一方面，工业界的实际问题往往需要处理超大规模的图（例如，包含数百万节点、数十亿条边的 Twitter 或 Facebook 的社交网络）。
文章插图
大多数现有的文献中描述的方法在这样的大规模应用场景下并不适用。
简而言之， GNN 通过聚合局部邻居节点的特征来进行操作。当下流行的图卷积网络（GCN）模型通过将 d 维节点特征组织在一个 n×d 的矩阵 X 中（其中， n 代表节点的个数），在图上实现了一种最简单的类似于卷积的操作，它将节点层面上的变换与相邻节点之间的特征传递融合了起来。
Y = ReLU(AXW).
在这里， W 是各节点之间共享的可学习的矩阵， A 是一个线性传播算子，相当于邻居节点特征的加权平均。正如在传统的卷积神经网络（CNN）中一样，我们可以将多层堆叠的这种形式应用在序列中。
GNN 可以被设计用于在节点层面上（例如，检测社交网络中的恶意用户）、边的层面上（例如，推荐系统中典型的场景——链接预测）、或整个图的层面上（例如，预测分子图的化学性质）进行预测。例如，我们可以使用如下所示的双层 GCN 执行节点级别的分类任务：
Y = softmax(A ReLU(AXW)W’).
2 扩展图神经网络的挑战性
为什么扩展图神经网络十分具有挑战性呢？
在上述节点级别的预测问题中， GNN 会在样本节点上进行训练。
在传统的机器学习环境下，通常假设样本是以统计上相独立的方式从某个分布中采样得到的。反过来，这样就可以将损失函数分解为独立样本的贡献，并采用随机优化技术。
然而，图中的节点是通过边相互关联的，这使得训练集中的样本在统计意义上相互依赖。此外，由于节点之间的统计依赖性，采样过程可能会引入偏置。
例如，这可能使得一些节点或边在训练集中比其它节点或边出现得更频繁，而我们需要恰当地应对这种「副作用」。
最后，同样重要的是，我们需要保证采样得到的子图能够保留 GNN 可以利用的有意义的结构。
在许多早期的图神经网络工作中，并未考虑上述问题：诸如 GCN（图卷积网络）、ChebNet、MoNet 和 GAT 等网络架构都是使用全批量梯度下降（full-batch gradient descent）算法训练的。
这使我们必须在内存中维持全部图的邻接矩阵以及节点特征。因此，一个 L 层的 GCN 模型就具有了 O(Lnd2) 的时间复杂度和 O(Lnd +Ld2) 的空间复杂度，即使对于大小适度的图来说，这也是无法接受的。
GraphSAGE 是研究图神经网路的可扩展性问题的第一项工作，它是 Will Hamilton 等人撰写的奠基性论文。 GraphSAGE 将邻居节点采样与 mini-batch 训练结合了起来，从而在大规模图上训练 GNN（「SAGE」指的是「采样与聚合」）。