第 110 题：大规模图的分区训练，GraphSAGE的minibatch实现细节？
题目
大规模图的分区训练，GraphSAGE的minibatch实现细节？
完整讲解
一、大规模图与分区
图规模大时无法单机存整图或单 batch 全图训练，需要分区：将节点或边划分到多机/多 GPU，每部分只存子图，训练时通过通信或采样子图组成 mini-batch。分区策略影响负载均衡、通信量与收敛。
二、GraphSAGE 的 Mini-batch 思路
GraphSAGE 本身是按节点 mini-batch：每 batch 采样一组目标节点，再对每个目标节点采样其 k-hop 邻域（如 2 层：先采 25 邻居、再每邻居采 10），形成子图。前向时从外向内逐层聚合（先 2-hop 再 1-hop 再目标节点），只在该子图上计算，无需全图。因此天然适合「分区 + 按节点采样」：分区后每分区存局部邻接，采样时在分区内或跨分区取邻居。
三、分区训练的实现细节
- 节点分区：按节点 ID 或图划分算法（如 Metis）将节点分到若干分区，每分区存「节点及其出边」或「节点 + 其邻接表」。采样时，若目标节点在分区 A，则 1-hop 可能跨到分区 B，需远程拉取邻居特征或嵌入。
- 采样子图：对每个 batch 的目标节点，在各自分区内做 k-hop 采样，得到多个子图；若邻居在它分区，由该分区本地采样并返回节点 ID 与特征，中心节点所在分区做聚合。需通信：拉取它分区节点特征、或推送梯度。
- 负载均衡：高度节点被采样到的概率大，若分区按度划分不均会导致部分分区热点。可按时度或随机划分、或对高度节点做复制/缓存，减少跨分区访问。
- 层数与邻居数：k 层 GNN 每节点需 k-hop 邻域；每层采样邻居数 $S_1, S_2$ 控制子图大小。$S_1 \times S_2$ 过大则单 batch 显存与计算大，过小则信息不足。常用 2 层、每层 10～25 邻居。
四、工程要点
- 分布式时邻接与特征可存图引擎（如 DGL、PyG 分布式），采样与 mini-batch 由框架封装。
- 梯度与嵌入更新：若用 DGL 等，梯度按子图反传后由框架同步或异步聚合到全局参数；嵌入表可分区存储、按需拉取。
面试要点
- 能说明大规模图需分区、GraphSAGE 按节点 mini-batch + k-hop 采样子图。
- 能说清分区后采样如何跨分区、需拉取邻居特征/嵌入与通信。
- 能提及负载均衡（高度节点、分区策略）、每层邻居数 $S_1,S_2$ 与层数 k 的权衡。
记忆要点
- 大规模图：节点/边分区；GraphSAGE mini-batch = 采样目标节点 + k-hop 邻域子图。
- 实现：分区内存邻接；采样可能跨分区→拉取邻居特征、通信；负载均衡注意高度节点。
- 层数 k、每层邻居数 $S_1,S_2$ 控制子图大小与显存；常用 2 层、每层 10～25。