邻居采样概述

在之前的教程中，您学习了如何通过计算图上所有节点的表示来训练 GNN。然而，有时您的图太大，无法在单个 GPU 中进行所有节点的计算。

在本教程结束时，您将能够

消息传递回顾

回顾 Gilmer 等人提出的消息传递公式如下：

\[m_{u \to v}^{(l)} = M^{(l)}\left(h_v^{(l-1)}, h_u^{(l-1)}, e_{u \to v}^{(l-1)}\right)\]

\[m_{v}^{(l)} = \sum_{u \in \mathcal{N}(v)} m_{u \to v}^{(l)}\]

\[h_v^{(l)} = U^{(l)}\left(h_v^{(l-1)}, m_v^{(l)}\right)\]

其中 DGL 将其称为 - 消息函数: \(M^{(l)}\) - 归约函数: \(\sum\) - 更新函数: \(U^{(l)}\)

注意，这里的 \(\sum\) 可以代表任何函数，不一定表示求和。

本质上，单个节点的第 \(l\) 层表示依赖于该节点本身的第 \((l-1)\) 层表示，以及其邻居节点的第 \((l-1)\) 层表示。这些第 \((l-1)\) 层表示又依赖于这些节点的第 \((l-2)\) 层表示及其邻居的表示。

以下动画展示了 2 层 GNN 如何计算节点 5 的输出

您可以看到，要计算节点 5 的第二层表示，您需要其直接邻居的第一层表示（黄色），而这又需要这些邻居的直接邻居（即节点 5 的二跳邻居）的表示（绿色）。

从前面的例子中您还可以看到，计算少量节点的表示通常需要显著多得多的节点的输入特征。将所有邻居都用于消息聚合通常开销太大，因为输入特征所需的节点很容易覆盖图的大部分区域，特别是对于通常是无标度网络的现实世界图。

邻居采样通过选择邻居的一个子集来执行聚合，从而解决了这个问题。例如，要计算 \({h}_5^{(2)}\)，您可以选择两个邻居而不是全部邻居来进行聚合，如下面的动画所示

您可以看到，这种方法在单个小批量消息传递中所需的节点数量大大减少。

您还可以在上面的动画中注意到，计算依赖关系可以描述为一系列二分图。输出节点（称为目标节点）在一侧，而输入所需的所有节点（称为源节点）在另一侧。箭头表示采样的邻居如何将消息传播到节点。DGL 将此类图称为消息流图 (MFG)。

请注意，某些 GNN 模块，例如 SAGEConv，需要使用目标节点在前一层的特征来计算输出。为了不失一般性，DGL 总是将目标节点本身包含在源节点中。