3. 邻居采样策略：固定大小邻居采样、均匀采样、重要性采样、采样效率分析
在 GraphSAGE 中，邻居采样是控制计算复杂度和模型泛化能力的关键环节。由于真实图数据往往具有高度倾斜的度分布（少数节点拥有大量邻居），直接对所有邻居进行聚合会导致计算爆炸。本章深入剖析四种主流采样策略的原理、实现与效率权衡。
3.1 固定大小邻居采样（Fixed-Size Neighbor Sampling）
GraphSAGE 原始论文提出的核心策略：对每个节点的邻居集合，无放回或可放回地采样固定数量 k 个邻居。若节点度 d < k，则进行有放回采样补足；若 d > k，则无放回采样 k 个。
核心公式：
采样邻居数 = min(k, d) + max(0, k - d) 次有放回补足
最终邻居张量形状始终为 [batch_size, k, feature_dim]
采样邻居数 = min(k, d) + max(0, k - d) 次有放回补足
最终邻居张量形状始终为 [batch_size, k, feature_dim]
| 特性 | 说明 |
|---|---|
| 优点 | 计算图大小固定，内存可预测；适合批训练和 GPU 并行 |
| 缺点 | 低度节点重复采样引入偏差；高度节点丢失信息 |
| 典型 k 值 | 一层 25，二层 10（论文默认） |
3.2 均匀采样（Uniform Sampling）
均匀采样是固定大小采样的特例：当 k 设置为节点度时，即为全邻居聚合；当 k 固定且小于度时，每个邻居被选中的概率相等。均匀采样在实现上最为简单，但存在以下问题：
- 信息丢失不均衡：高度节点丢失大量信息，低度节点信息冗余。
- 方差较大：每次采样结果差异大，模型训练不稳定。
- 无偏但高方差：期望等于真实邻居均值，但单次估计方差高。
实践建议：均匀采样适合度分布较均匀的图（如社交网络中的小圈子）。对于幂律分布图（如引文网络），建议配合重要性采样使用。
3.3 重要性采样（Importance Sampling）
重要性采样通过非均匀概率选择邻居，使得采样结果更关注对聚合贡献大的节点。常见策略包括：
| 策略 | 采样概率 | 适用场景 |
|---|---|---|
| 度归一化 | p(v) ∝ 1/deg(v) | 抑制高度节点，增强低度节点影响力 |
| 特征相似度 | p(v) ∝ exp(cos(h_u, h_v)) | 关注与中心节点特征相似的邻居 |
| PageRank 权重 | p(v) ∝ PR(v) | 优先采样全局重要节点 |
| 学习型采样 | p(v) = softmax(MLP(h_u, h_v)) | 端到端学习采样策略（如 LADIES） |
重要性采样的核心在于权重校正：聚合时需用 1/p(v) 对邻居特征加权，以保证期望无偏。
# 重要性采样伪代码
def importance_sample(center_feat, neighbor_feats, neighbor_deg, k):
# 计算采样概率：度归一化
prob = 1.0 / (neighbor_deg + 1e-8)
prob = prob / prob.sum()
# 按概率采样 k 个邻居（可放回）
indices = np.random.choice(len(neighbor_feats), size=k, replace=True, p=prob)
sampled_feats = neighbor_feats[indices]
sampled_weights = 1.0 / (prob[indices] * k) # 重要性权重
# 加权聚合
agg_feat = (sampled_feats * sampled_weights.reshape(-1,1)).sum(axis=0)
return agg_feat
3.4 采样效率分析
采样效率直接影响 GraphSAGE 的训练速度和可扩展性。我们从时间复杂度、空间复杂度和信息保留率三个维度对比：
| 采样策略 | 时间复杂度（每层） | 空间复杂度（每 batch） | 信息保留率 | 方差 |
|---|---|---|---|---|
| 固定大小采样 | O(k × d) | O(b × k × L) | 低（高度节点） | 中 |
| 均匀采样 | O(k × d) | O(b × k × L) | 中 | 高 |
| 重要性采样 | O(k × d + d × log d) | O(b × k × L) | 高（按重要性） | 低 |
| 全邻居（无采样） | O(d²) | O(b × d × L) | 100% | 0 |
关键指标解释：
- b：batch 大小；k：采样邻居数；d：平均节点度；L：层数。
- 信息保留率：采样邻居携带的信息占全部邻居信息的比例。重要性采样通过加权校正，理论上可接近全邻居效果。
- 方差：多次采样之间聚合结果的波动程度。低方差意味着训练更稳定。
3.5 采样策略选择指南
避坑提醒：不要盲目使用固定大小采样！当图具有强同配性（同类节点相连）时，均匀采样可能丢失关键结构信息。建议先分析图的度分布和同配系数，再选择采样策略。
- 小图（节点数 < 10⁴）：优先全邻居聚合，避免采样偏差。
- 中图（10⁴ ~ 10⁶）：固定大小采样 + 适度 k 值（如 10~25）。
- 大图（> 10⁶）：重要性采样或 LADIES 分层采样，平衡效率与精度。
- 流式/动态图：使用蓄水池采样（Reservoir Sampling）维护固定大小的邻居缓存。
在实际工程中，固定大小采样因其实现简单、内存可控，仍是工业界最广泛使用的方案。但若模型精度要求高且计算资源充足，重要性采样能带来 5%~15% 的 AUC 提升（在 ogbn-arxiv 等基准上验证）。