Graph Neural Networks (GNN / GAT): 解释 GNN 在大规模图上的训练策略。

Core Concept: 邻居采样（GraphSAGE/邻居爆炸）、子图采样（Cluster-GCN）、以及分布式训练与图分区。

数学机理：<strong>问题一：邻居爆炸（neighbor explosion）</strong>——L 层 GNN 需聚合 L 跳邻域；若每层平均度数为 d，则一个节点的 L 跳邻域大小约 d^L（指数增长）；对 10 亿节点的图，全邻域聚合完全不可行（显存与计算都爆炸）。<strong>问题二：图分区与跨分区边</strong>——大图需分布到多机，但图的<strong>边会跨分区</strong>（cut edges），导致大量跨机通信。<strong>训练策略</strong>：<strong>(1) 邻居采样（neighbor sampling，GraphSAGE）</strong>——每层对每个节点<strong>只采样固定数量 K 个邻居</strong>（而非全部）；则 L 层的计算量约 O(K^L)（可控，因为 K 是常数）；代价是采样的方差（不同 batch 采到不同邻居）。<strong>(2) 子图采样（subgraph sampling，Cluster-GCN）</strong>——先用社区检测算法（如 Metis）把图切成<strong>簇（cluster）</strong>，每批训练只用<strong>少数簇组成的子图</strong>；优点——(a) <strong>跨分区边少</strong>（因为簇内边密集、簇间边稀疏），故子图内的计算可<strong>避免大量跨分区通信</strong>；(b) 显存只需装下子图；(c) 计算效率高（子图内的邻接矩阵可高效稀疏乘）。<strong>(3) 分布式训练</strong>——把图按分区放在多机（每机一个子图），用'采样 + 跨机通信'或'子图复制 + 边界节点同步'；代表系统有 DistDGL、PGL、Euler 等。<strong>(4) 图分区优化</strong>——用 METIS 等算法最小化 cut edges（减少通信）；或用'哈希分区 + 复制热点节点'（牺牲存储换通信）。<strong>(5) 其他技巧</strong>——(a) <strong>历史嵌入（historical embedding）</strong>（如 PinSAGE）：缓存上次计算的邻居表示，避免重复计算；(b) <strong>层间采样</strong>（只在第一层采样、深层用全邻域）；(c) <strong>图预计算</strong>（把多跳邻居预先聚合）。<strong>选择逻辑</strong>——小图全批量、中图邻居采样、大图子图采样 + 分布式。

深度剖析与工程权衡：① <strong>'子图采样优于邻居采样'的原因</strong>——邻居采样会产生'采样膨胀'（每个节点的邻居又需采样其邻居，导致计算图随层数指数增长）；子图采样只需处理子图内的边（无膨胀），且<strong>稀疏矩阵乘效率高</strong>（可利用稀疏算子）。故大图训练倾向子图采样。② <strong>采样偏差问题</strong>——采样会引入<strong>邻居分布的偏差</strong>（采到的邻居不代表全部）；对策是 (a) 增加采样数 K、(b) 用'重要性采样'加权、(c) 用全邻域做最后一层。③ <strong>与工业推荐的关系</strong>——工业图（用户-物品二部图）常有数十亿节点、数百亿边；PinSAGE（Pinterest）用随机游走采样 + 历史嵌入在 30 亿节点上训练；阿里/腾讯用类似的'采样 + GNN'做召回与排序。④ <strong>'图神经网络 vs 图嵌入'的工程选择</strong>——若只需'节点表示'（如召回），轻量的图嵌入（Node2Vec、LightGCN）可能比完整 GNN 更实用（更便宜、易上线）；GNN 的价值在'利用节点特征 + 归纳式泛化'。⑤ <strong>与图数据库/图计算引擎的关系</strong>——大规模 GNN 训练常需与图存储（如 Neo4j、Neptune）或图计算框架（GraphX、PGL）集成。⑥ <strong>面试要点</strong>——被问'大图怎么训练'，应给出'<strong>邻居采样（GraphSAGE）/ 子图采样（Cluster-GCN）/ 分布式分区</strong>'三类并说明'子图采样避免采样膨胀、跨分区边少故通信省'；能提到'历史嵌入（PinSAGE）'与'工业推荐的实践'是深度理解的标志。