图采样技术 (GraphSAINT, ShaDow-GNN)

邻域采样，如GraphSAGE等方法中实现的，通过处理节点及其采样邻居的迷你批次，提供了一种扩展性方案。然而，为每个迷你批次逐层构建这些计算图仍然会涉及相当大的开销和可能存在的冗余，特别是对于深层GNN。另一种做法是图采样，我们从原始大图中采样整个子图，并在这些较小的、易于处理的结构内执行GNN计算。

核心思想很有吸引力：将每个采样的子图视为独立的训练样本。与加载完整的图邻接矩阵相比，这大幅减少了内存占用。然而，随机采样节点或边以形成子图的简单做法可能导致梯度估计有偏或训练期间方差过高。采样子图内的连接可能无法准确反映完整图的属性，可能妨碍收敛和模型表现。GraphSAINT和ShaDow-GNN等方法正是为应对这些难题而出现，提供了更精细的子图采样或局部结构采样方式，同时控制了偏差和方差。

GraphSAINT：高效采样子图

GraphSAINT (基于图采样的归纳学习) 直接处理简单子图采样中固有的方差问题。GraphSAINT不逐节点采样邻居，而是使用多种方法通过采样子图来构建迷你批次。其主要贡献在于如何处理采样过程中引入的可能偏差。

子图采样方法

GraphSAINT提出了几种采样节点或边的方法，这些方法进而生成子图：

1. 随机节点采样器： 均匀采样固定数量的节点，并根据这些节点及其之间的边来生成子图。
2. 随机边采样器： 均匀采样边，并包含关联节点以形成子图。这自然会使度数较高的节点获得更高的概率。
3. 随机游走采样器： 从随机选择的节点开始进行多次随机游走。访问的节点集合生成子图。这比均匀采样能更好地保留局部社群结构。

通过归一化 (normalization)减少方差

GraphSAINT处理的主要问题是，在采样子图上计算的损失期望值可能不等于在完整图上的真实损失。同样，从子图获得的梯度可能是完整梯度的有偏或高方差估计。

为了纠正这一点，GraphSAINT在GNN的聚合步骤中引入了特定的归一化方法。设$A$是完整邻接矩阵，$\hat{A}$是采样子图的邻接矩阵。设$p_i$是节点$i$被包含在采样子图中的概率。使用$\hat{A}$的简单聚合会有偏差。GraphSAINT修改了聚合过程。例如，GCN层聚合特征$X$：

$$Z = \sigma(\hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2} X W)$$

GraphSAINT根据采样概率进行调整。如果使用节点采样器，其中每个节点$i$以概率$p_i$被采样，则采样图$g$中节点$i$的聚合可以被归一化。一种简化的看法是重新加权损失贡献或基于这些概率的聚合消息。精确的归一化取决于使用的特定采样器（节点、边、随机游走），以保证归一化聚合的期望值与完整图聚合相匹配，从而使随机梯度成为真实梯度的无偏估计。

例如，聚合步骤可能包含根据采样概率获得的归一化因子以调整消息权重 (weight)：

$$\tilde{h}_i = \text{AGGREGATE} \left( \left\{ \alpha_{ij} \cdot h_j \mid j \in \mathcal{N}(i) \cap V_g \right\} \right)$$

其中$V_g$是采样子图$g$中的节点集合，$\mathcal{N}(i)$是$i$的邻居，$h_j$是邻居$j$的特征，$\alpha_{ij}$是根据采样概率$p_i$、$p_j$以及可能存在的边采样概率$p_{ij}$计算得到的归一化系数。这种归一化融入GNN层（通常通过边权重），以保证训练期间的无偏估计。

训练流程

训练循环包括：

1. 采样： 选择采样器（节点、边或随机游走）并采样一个子图$g$。
2. 传播： 只在子图$g$上运行GNN前向传播，并在聚合期间应用对应的归一化 (normalization)（通常由专门的数据加载器和层处理）。
3. 损失计算： 根据子图$g$内的节点标签计算损失。
4. 反向传播 (backpropagation)： 计算梯度并更新GNN参数 (parameter)。

这避免了在训练迭代期间将完整的图邻接矩阵加载到内存中，使其具有很强的扩展性。

GraphSAINT采样的视图。一个子图（绿色节点）从完整图（蓝色节点）中采样得到。GNN计算和损失计算在此子图内部进行，使用根据采样过程获得的归一化因子来保证梯度的无偏估计。

ShaDow-GNN：局部感知采样

ShaDow-GNN为可扩展的GNN训练提供了不同的思路，侧重于高效构建迷你批次内节点所需的计算上下文 (context)。与GraphSAINT采样单个大型子图不同，ShaDow-GNN旨在为正在更新的目标节点创建定制的、局部化的计算图，称之为“影子子图”。

构建影子子图

考虑一个$K$层GNN。为了计算目标节点$v$的最终嵌入 (embedding)，我们需要其$K$跳邻域的信息。为大型迷你批次中的所有节点加载完整的$K$跳邻域，仍然可能导致计算成本高昂且内存消耗大，特别是在图密集区域或$K$值较大时。

ShaDow-GNN通过为每一层采样固定大小的邻域来应对此问题，这与GraphSAGE的理念相似，但其着眼于构建一个用于计算的特定子图结构。对于迷你批次中的目标节点$v$，ShaDow-GNN通过从$v$向外迭代采样邻居来构建其影子子图。目的是获取节点$v$进行$K$层GNN计算所需的关键局部结构，可能采用优先考虑重要邻居的采样方法。

ShaDow-GNN并非像标准GraphSAGE实现那样在前向传播期间逐层扩展，而是可以看作是为批次中的每个节点预采样所需的$K$跳结构。然后，它在来源于这些影子子图联合体的图结构上执行GNN计算，确保每个目标节点都能从其采样上下文 (context)接收传播来的消息。“影子”这一术语表明，这些采样子图充当了GNN所需完整邻域结构的计算替代物。

训练过程

1. 迷你批次选择： 为迷你批次选择一组目标节点。
2. 影子子图构建： 对于批次中的每个目标节点$v$，采样其$K$跳影子子图$\mathcal{G}_v$。这通常包括从$v$向外逐层采样邻居，可能采用重要性采样等方法。
3. GNN计算： 执行$K$层GNN前向传播。节点$v$的计算使用从其采样影子子图$\mathcal{G}_v$传播来的信息。实现上通常在包含所有所需采样节点和边的组合图上执行计算，并在影子子图重叠时共享计算。
4. 损失计算与更新： 根据目标节点的最终嵌入 (embedding)计算损失并更新GNN参数 (parameter)。

优势与考虑

ShaDow-GNN旨在通过控制每个目标节点处理的信息量来提高效率。通过着眼于采样必要的$K$跳上下文 (context)，它有助于避免像GraphSAINT那样构建单个可能非常大的子图所带来的更大开销，或避免完整的逐层扇出扩展。

ShaDow-GNN的有效性取决于采样影子子图近似真实局部邻域的质量以及采样实现的效率。它代表了一种设计选择，即优先考虑对批次中每个目标节点进行定制化的局部计算，在平衡计算成本和模型准确性方面，为大规模环境提供了另一种途径。

比较图采样方法

GraphSAINT和ShaDow-GNN都提供了有效的机制，使GNN训练能够克服全图方法或基本邻域采样的限制。它们在构建迷你批次训练的计算单元方面根本区别在于：

• GraphSAINT： 每个迷你批次采样一个单独的、较大的子图，并在其内部执行GNN计算。其优势在于严格的归一化 (normalization)方法，以确保无偏的梯度估计，从而减轻与子图采样相关的方差。采样器的选择（节点、边、随机游走）使其采样能适应图的特性。
• ShaDow-GNN： 构建以迷你批次中每个目标节点为中心的小型局部“影子”子图。它着眼于高效捕获$K$层GNN所需的$K$跳上下文 (context)，可能通过避免冗余邻居处理来实现计算节约，尤其是在影子子图高效构建的情况下。

邻域采样（GraphSAGE），前面讨论过，在GNN前向传播过程中逐层采样邻居。如果控制不当，这可能导致涉及节点数量的指数增长（扇出），但它在动态定义计算图方面提供了灵活性。

这些方法之间的选择通常取决于具体的图结构、GNN架构深度以及可用的计算资源。当无偏梯度非常重要，或者其特定采样器（如随机游走）能有效捕捉重要图属性时，GraphSAINT可能更适合。如果构建聚焦的$K$跳邻域比采样和归一化大型子图更快或使用更少内存，那么ShaDow-GNN可能更具效率，尤其对于更深的GNN而言。

“这些方法的实现通常需要使用PyTorch Geometric或DGL等库提供的专门数据加载器。这些库处理子图采样、索引、归一化和高效批次构建的复杂方面。对于将GNN应用于大规模图数据集，其中将整个图及其中间激活加载到内存中根本不可行的情况，图采样方法是不可或缺的工具。它们是让GNN训练变得实用高效的重要进步。”