2. GraphSAGE 核心思想：归纳式学习 vs 直推式学习、采样与聚合的核心动机、论文精读概览

本章是 GraphSAGE 的理论基石。我们将从学习范式、算法动机和论文核心贡献三个维度，拆解 GraphSAGE 为何能成为大规模图学习的里程碑。理解这些概念，是后续掌握阈值分层策略的前提。

2.1 归纳式学习 vs 直推式学习

在 GraphSAGE 出现之前，大多数图神经网络（如 GCN）采用 直推式学习（Transductive Learning）。GraphSAGE 则开创性地引入了 归纳式学习（Inductive Learning）。两者的核心区别在于模型是否依赖全局图结构。

对比维度 直推式学习（Transductive） 归纳式学习（Inductive）
训练与测试关系 训练和测试必须在同一张图上进行；测试节点在训练时已可见（但标签不可见）。 训练和测试图可以不同；模型在训练图上学习聚合函数，直接泛化到未见过的图或节点。
对图结构的依赖 强依赖：模型参数与图结构耦合，新节点加入需要重新训练或进行复杂的推断。 弱依赖：模型学习的是“如何聚合邻居信息”，而非特定节点的嵌入，天然支持新节点。
典型代表 GCN、GAT（标准版本） GraphSAGE、GIN
适用场景 静态图、节点数固定、全图已知（如引文网络分类）。 动态图、大规模图、需要泛化到新节点或新图的场景（如推荐系统、社交网络）。
核心洞察： 直推式学习本质上是“记忆”节点间的连接模式，而归纳式学习是“学习”一种通用的邻居信息组合规则。GraphSAGE 的归纳能力使其成为工业级大规模图系统的首选。
归纳式学习 vs 直推式学习范式对比 直推式学习（Transductive） 训练图 G_train 节点 A, B, C, D 边：A-B, B-C, C-D 测试图 G_test 节点 A, B, C, D （结构相同） 训练与测试图结构必须相同 新节点 E 加入 → 需重新训练 模型参数与图结构耦合 归纳式学习（Inductive） 训练图 G_train 节点 A, B, C, D 边：A-B, B-C 测试图 G_test 节点 A, B, C, E （结构不同） 训练与测试图结构可以不同 新节点 E 加入 → 直接推断 模型学习聚合函数，泛化性强

2.2 采样与聚合的核心动机

GraphSAGE 的设计动机源于两个现实挑战：计算爆炸和邻居异质性。传统的 GCN 需要聚合节点的全部邻居，这在社交网络等幂律分布图中会导致邻居数量指数级增长，且全图拉普拉斯矩阵的计算代价极高。

2.2.1 为什么需要采样？

  • 控制计算复杂度：固定采样邻居数量（如 S1=25, S2=10），将每个节点的计算复杂度从 O(N) 降低到 O(K * S)，其中 K 为层数，S 为采样数。
  • 支持小批量训练：采样使得模型可以基于 mini-batch 进行随机梯度下降，而非处理全图，这是大规模图学习的必要条件。
  • 减少过平滑：限制邻居数量可以避免深层网络中节点表示趋于一致的问题。

2.2.2 为什么需要聚合？

  • 处理邻居无序性：图数据没有空间顺序，聚合函数必须是对排列不变的（permutation invariant），如求和、平均、最大值。
  • 融合多跳信息：通过多层聚合，节点可以逐步融合 1-hop、2-hop 甚至更高阶邻居的信息，形成丰富的上下文表示。
  • 适应不同图结构：不同的聚合器（Mean、Pool、LSTM）对图结构的敏感性不同，提供了灵活的选择空间。
实践要点：采样数量并非越大越好。过大的采样数会引入噪声和计算开销；过小则可能导致信息不足。通常第一层采样 25 个邻居，第二层采样 10 个邻居是一个良好的起点。
GraphSAGE 采样与聚合核心动机 采样动机 全图邻居爆炸 O(N) 复杂度 固定采样 K 个 O(K) 可控复杂度 支持 mini-batch 训练 减少过平滑风险 适应幂律分布图 聚合动机 邻居无序性 排列不变性要求 聚合器设计 Mean / Pool / LSTM 融合多跳邻居信息 生成节点上下文表示 灵活适应不同图结构 聚合流程（以 Mean 聚合器为例） h_v^(k) = σ( W · MEAN( { h_v^(k-1) } ∪ { h_u^(k-1), ∀u ∈ N(v) } ) ) 步骤：采样邻居 → 聚合邻居特征 → 拼接自身特征 → 非线性变换 输出：节点 v 在第 k 层的嵌入表示

2.3 GraphSAGE 论文精读概览

论文《Inductive Representation Learning on Large Graphs》（Hamilton, Ying, Leskovec, 2017）是 GraphSAGE 的原始出处。以下是对论文核心贡献的概览。

2.3.1 论文核心贡献

  1. 提出归纳式图学习框架：首次将归纳学习引入图神经网络，解决了直推式模型无法泛化到新节点的问题。
  2. 设计可学习的聚合函数：提出了 Mean、LSTM、Pooling 三种聚合器，并证明其排列不变性。
  3. 实现高效的邻居采样策略：通过固定大小的邻居采样，将计算复杂度从 O(N) 降低到 O(K * S)，使模型可扩展到百万级节点图。
  4. 无监督损失函数：设计了基于负采样的无监督损失，使模型可以在没有标签的情况下学习节点表示。

2.3.2 算法伪代码与关键步骤

论文中的核心算法可以概括为以下步骤：

# GraphSAGE 前向传播伪代码
# 输入：图 G(V, E)，特征矩阵 X，层数 K，权重矩阵 W^k，聚合函数 AGG_k
# 输出：所有节点的最终嵌入 z_v

# 初始化：h_v^0 = x_v, ∀v ∈ V
for k = 1 to K:
    for v in V:
        # 1. 采样邻居
        N_sample(v) = SAMPLE(N(v), S_k)
        # 2. 聚合邻居特征
        h_N(v)^k = AGG_k( { h_u^(k-1), ∀u ∈ N_sample(v) } )
        # 3. 拼接自身特征与聚合特征
        h_v^k = σ( W^k · CONCAT( h_v^(k-1), h_N(v)^k ) )
        # 4. 归一化（可选）
        h_v^k = h_v^k / || h_v^k ||_2

# 最终嵌入
z_v = h_v^K, ∀v ∈ V

2.3.3 三种聚合器的对比

聚合器 核心思想 排列不变性 计算效率 适用场景
Mean 聚合器 对邻居特征逐元素取平均 ✅ 是 高 通用场景，图结构相对均匀
LSTM 聚合器 将邻居随机排序后输入 LSTM ✅ 是（通过随机排序） 中 序列化邻居信息，适合有顺序偏好的图
Pooling 聚合器 对每个邻居特征进行 MLP 变换后取最大值 ✅ 是 中 捕捉邻居中最显著的特征
注意： LSTM 聚合器虽然理论上可以学习更复杂的邻居关系，但由于需要随机排序来保证排列不变性，其训练稳定性不如 Mean 和 Pooling 聚合器。在实际工程中，Mean 聚合器通常是首选。

2.3.4 无监督损失函数

论文中使用的无监督损失函数基于负采样，旨在使相邻节点的表示相似，而远离节点的表示不同：

J_G(z_u) = -log( σ( z_u^T z_v ) ) - Q * E_{v_n ~ P_n(v)} [ log( σ( -z_u^T z_{v_n} ) ) ]

其中：
- v 是 u 的邻居（通过随机游走定义）
- v_n 是从负采样分布 P_n 中采样的负样本
- Q 是负样本数量
- σ 是 sigmoid 函数

这个损失函数使得模型可以在没有标签的情况下学习到有意义的节点嵌入，为后续的下游任务（如分类、聚类）提供高质量的初始化。

← 上一章 📖 返回目录 下一章 →