Ch12 §03 图神经网络 · 讲解稿¶

章节定位: Ch12 核心。教"消息传递"统一框架 + 三大模型 (GCN / GraphSAGE / GIN) + READOUT / 池化 + over-smoothing 应对。承接: §01 GDL 范式 + §02 图论数学 → §03 在图上做深度学习走向: §04 GAT 加注意力, §05 在 3D 图上做等变网络篇幅: ~4500 字 / 阅读 14 分钟 / 讲解 30-35 分钟

一 · 一句话总览¶

GNN = 消息传递 (Message Passing): 每节点从邻居收集信息 → 置换不变聚合 → 更新自身表征。GCN / GraphSAGE / GIN 是同一框架的三种实现, 表达力递增。

二 · 心智模型¶

把 GNN 想成"局部去中心化计算":

每个节点是一个"小智能体"
每层做一次"邻区通讯"
K 层后, 节点"看见" K 跳邻居
最终 READOUT 得到图 / 节点 / 边的预测

类比: - 1 层 GNN ≈ 1 跳邻居 (CNN 1 个 3x3 卷积) - K 层 GNN ≈ K 跳邻居 (CNN K 层卷积) - 不同点: GNN 邻域大小因节点而异 (hub 节点邻域大)

三 · 章节主线 (5 段)¶

第 1 段 · 消息传递框架 (8 分钟)¶

3.1.1 三步走¶

每层 $l$ 每节点 $i$:

消息 (Message): 邻居 $j$ 计算消息 $\mathbf{m}_{j \to i}$
聚合 (Aggregate): 节点 $i$ 用置换不变函数合并所有邻居消息
更新 (Update): 节点 $i$ 把聚合消息与自身特征结合, 得新表征

\[\mathbf{m}_i^{(l)} = \bigoplus_{j \in \mathcal{N}(i)} \phi^{(l)}\left(\mathbf{h}_i^{(l)}, \mathbf{h}_j^{(l)}, \mathbf{e}_{ij}\right)\]

\[\mathbf{h}_i^{(l+1)} = \psi^{(l)}\left(\mathbf{h}_i^{(l)}, \mathbf{m}_i^{(l)}\right)\]

3.1.2 关键要求¶

聚合 $\bigoplus$ 必须置换不变 — 否则节点编号变了, 结果就变了。常见: SUM / MEAN / MAX。

3.1.3 感受野¶

K 层 GNN, 节点 $i$ 看到 K 跳邻居。类比 CNN: 深度 = 感受野扩展。区别: GNN 感受野因图拓扑而异, hub 大 / 边缘节点小。

第 2 段 · GCN: 谱卷积的简化 (10 分钟)¶

GCN (Kipf & Welling, ICLR 2017) 是 GNN 起点, 把谱图卷积 (§02) 用一阶 Chebyshev 多项式近似。

3.2.1 公式¶

\[H^{(l+1)} = \sigma\left(\hat{A} H^{(l)} W^{(l)}\right)\]

其中: - $H^{(l)} \in \mathbb{R}^{n \times d}$ 是节点特征矩阵 - $W^{(l)} \in \mathbb{R}^{d \times d'}$ 可学习权重 - $\hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ 对称归一化邻接 - $\tilde{A} = A + I$ 加自环 - $\sigma$ = ReLU

3.2.2 三步拆解¶

聚合 $\hat{A} H^{(l)}$: 每个节点取邻居加权平均 (含自身, 因自环)
变换 $W^{(l)}$: 学习线性映射
激活 $\sigma$: 非线性

3.2.3 消息传递视角¶

Message: $\phi(\mathbf{h}_j) = \mathbf{h}_j$
Aggregate: 加权求和 (按度归一化)
Update: 线性 + ReLU

3.2.4 归一化的关键¶

不用归一化直接 $\tilde A H W$, 度大节点 (hub) 特征会被放大, 训练不稳定。

度归一化 $\tilde D^{-1/2} \tilde A \tilde D^{-1/2}$: 让所有节点的"接收信号能量"相近。

3.2.5 PyG 实现¶

import torch
from torch_geometric.nn import GCNConv

class GCN(torch.nn.Module):
    def __init__(self, in_dim, hid_dim, out_dim):
        super().__init__()
        self.conv1 = GCNConv(in_dim, hid_dim)
        self.conv2 = GCNConv(hid_dim, out_dim)

    def forward(self, x, edge_index):
        x = torch.relu(self.conv1(x, edge_index))
        x = torch.dropout(x, p=0.5, train=self.training)
        x = self.conv2(x, edge_index)
        return torch.log_softmax(x, dim=1)

Cora 上 2 层 GCN ≈ 81% 精度。

第 3 段 · GraphSAGE: 归纳式邻居采样 (10 分钟)¶

GCN 是直推 (transductive) — 训练时需要全图, 新节点加入需重训。GraphSAGE (Hamilton 2017) 用邻居采样解决。

3.3.1 公式¶

\[\mathbf{h}_i^{(l+1)} = \sigma\left(W^{(l)} \cdot \text{CONCAT}\left(\mathbf{h}_i^{(l)}, \text{AGG}\left(\{\mathbf{h}_j^{(l)} : j \in \mathcal{S}(i)\}\right)\right)\right)\]

$\mathcal{S}(i)$ = 采样邻居子集 (固定大小, e.g., 10 个)。

3.3.2 CONCAT 的关键¶

自特征 vs 邻居特征分两条路 — 让网络学习不同的 $W$ 处理"自己"和"邻居"。比 GCN 加法更灵活。

3.3.3 三种聚合器¶

聚合器	公式	特点
MEAN	$\frac{1}{	\mathcal{S}
LSTM	LSTM($\{h_j\}$ 排序后)	表达力强, 但引入顺序
POOL	$\max(\sigma(W_{\text{pool}} h_j + b))$	非线性 max

3.3.4 采样策略¶

每层采样固定数 (e.g., $k_1 = k_2 = 10$): 1 层 10 邻居, 2 层每邻居 10 邻居 = 总计 $10 + 10 \times 10 = 110$ 节点。计算量与全图大小无关 — 可扩展到亿级图。

3.3.5 工业应用¶

Pinterest 推荐 (PinSage = GraphSAGE 变种)
Uber Eats 配送
大规模生产环境标准

第 4 段 · GIN: WL 测试最优 (8 分钟)¶

GIN (Xu et al., ICLR 2019) 是理论上表达力最强的 GNN — 与 Weisfeiler-Lehman (WL) 测试 等价。

3.4.1 公式¶

\[h_v^{(l+1)} = \text{MLP}\left((1 + \epsilon) h_v^{(l)} + \sum_{u \in \mathcal{N}(v)} h_u^{(l)}\right)\]

用 SUM 聚合 (而不是 MEAN / MAX)
$(1 + \epsilon)$ 是关键 — 区分"自身"与"邻居求和", 避免信息丢失
MLP 后置提升表达力

3.4.2 为什么 SUM + MLP¶

MEAN: 节点数被稀释, 表达力受限
MAX: 选取最大值, 信息丢失
SUM: 节点数信息保留 + 多跳可微

3.4.3 WL 最优性定理¶

定理: GIN 的判别能力 = Weisfeiler-Lehman 测试。GIN 能区分 WL 能区分的所有图, 反之亦然。

应用: 分子性质预测 (OGB-mol) — GIN/GINE 是 SOTA 基线。

3.4.4 PyG 实现¶

from torch_geometric.nn import GINConv, global_add_pool

def mlp():
    return torch.nn.Sequential(
        torch.nn.Linear(d, d),
        torch.nn.ReLU(),
        torch.nn.Linear(d, d)
    )

class GIN(torch.nn.Module):
    def __init__(self):
        super().__init__()
        self.conv1 = GINConv(mlp())
        self.conv2 = GINConv(mlp())
        self.readout = global_add_pool

    def forward(self, x, edge_index, batch):
        h = torch.relu(self.conv1(x, edge_index))
        h = torch.relu(self.conv2(h, edge_index))
        g = self.readout(h, batch)  # SUM pool
        return g

第 5 段 · 池化、READOUT 与过平滑 (10 分钟)¶

3.5.1 READOUT: 图级预测¶

节点分类不需要, 图分类必须。READOUT 把 $n$ 个节点表征聚合成 1 个图表征。

\[h_G = \bigoplus_{v \in V} h_v^{(L)}\]

三种 READOUT: - SUM: $\sum_v h_v$ — 保留节点数信息 - MEAN: $\frac{1}{n} \sum h_v$ — 节点数不敏感 - MAX: $\max_v h_v$ — 只保留最显著特征

所有都置换不变 — 节点重排结果相同。

3.5.2 池化层 (Pooling)¶

READOUT 是一次性聚合; 池化层是中间降采样 — 类似 CNN max-pool。

方法	思路
DiffPool	学习软分配 $S^{(l)} = \text{softmax}(\text{GNN}(A, X))$, 节点聚类
TopK Pool	取 top-k 节点 (按学习分数)
SAGPool	自注意力池化
MinCutPool	谱聚类 + GNN

3.5.3 Over-smoothing 问题¶

现象: 多层 GNN 后, 所有节点表征趋同, 失去区分度。

原因: 每次聚合, 节点"吸收"邻居信息。K 跳后, 全图信息混入每个节点, 个性消失。

缓解:

方法	思路
残差	$H^{(l+1)} = H^{(l)} + \text{GNN}(H^{(l)})$ (类比 ResNet)
DropEdge	训练时随机删边, 减少信息传播
PairNorm	节点对距离正则, 保持分散
初始残差	$H^{(l+1)} = H^{(0)} + \text{GNN}(H^{(l)})$ 保留初始
浅层 GCN	≤ 2 层 (Cora SOTA)

3.5.4 三种任务¶

任务	输出	损失
节点分类	$h_v$ 直接分类	CrossEntropy
链接预测	$f(h_u, h_v) = \sigma(h_u^T h_v)$	BCE
图分类	READOUT($h_v$) 后接 MLP	CrossEntropy

3.5.5 实战代码: Cora 节点分类¶

import torch
from torch_geometric.datasets import Planetoid
from torch_geometric.nn import GCNConv

dataset = Planetoid(root='/data/Cora', name='Cora')
data = dataset[0]

class GCN(torch.nn.Module):
    def __init__(self):
        super().__init__()
        self.conv1 = GCNConv(dataset.num_features, 64)
        self.conv2 = GCNConv(64, dataset.num_classes)

    def forward(self, data):
        x, edge_index = data.x, data.edge_index
        x = torch.relu(self.conv1(x, edge_index))
        x = torch.dropout(x, p=0.5, train=self.training)
        x = self.conv2(x, edge_index)
        return torch.log_softmax(x, dim=1)

model = GCN()
opt = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

for epoch in range(200):
    model.train()
    opt.zero_grad()
    out = model(data)
    loss = torch.nn.functional.nll_loss(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    opt.step()

四 · 易错点 (6 条)¶

直推 vs 归纳: GCN 直推, SAGE/GIN 归纳。新节点直推需重训, 归纳不需要。
感受野大小: 1 层 = 1 跳, K 层 = K 跳 (注意图直径限制)。
SUM vs MEAN: MEAN 丢节点数信息, SUM 保留。分子性质预测用 SUM。
WL 表达力上限: 即使 GIN, 也有反例图对无法区分 (边染色等)。
过平滑: 多层 (>3) GCN 常出现, 必须有残差或 DropEdge。
READOUT 必须置换不变: 不能用 concatenation 或 stack (节点数变化)。

五 · 三大模型对比¶

维度	GCN	GraphSAGE	GIN
聚合	加权求和	MEAN/MAX/LSTM	SUM
表达力	中	中	最高 (WL)
直推/归纳	直推	归纳	归纳
可扩展	小图	亿级图	中等图
典型任务	节点分类	工业大规模	分子性质
代表论文	Kipf 2017	Hamilton 2017	Xu 2019

六 · 跨章连接¶

章节	关联
Ch06 §03 CNN	卷积 = 平移等变, GNN 卷积 = 邻居置换等变
Ch07 §04 Transformer	自注意力的全连接图视角
Ch11 §05 VLA	状态空间是图, GNN 可编码
Ch14 §04 图算法	Dijkstra, BFS 用于 GNN 推理

七 · 自测 5 题¶

消息传递三步? 为什么聚合要置换不变?
GCN 为什么要加自环 + 归一化?
GraphSAGE 为什么能处理亿级图?
GIN 与 WL 测试的关系?
Over-smoothing 的 3 种缓解方法?

八 · 一句话总结¶

GNN = 消息传递: 邻居聚合 + 置换不变 + 节点更新。GCN (归一化求和) / GraphSAGE (采样) / GIN (SUM, WL 最优) 是三种主流实现, 各有所长。READOUT + 池化把节点特征升到图级。Ch12 §04 将在此基础上加注意力 (GAT/Graphormer)。

九 · 板书建议¶

[板书 1: 消息传递]
   Message: φ(h_i, h_j, e)
   Aggregate: ⊕ (sum/mean/max, 置换不变)
   Update: ψ(h_i, m)

[板书 2: GCN]
   H^(l+1) = σ( Â H^(l) W^(l) )
   Â = D̃^{-1/2} (A+I) D̃^{-1/2}

[板书 3: SAGE]
   h^(l+1) = σ(W [h_i; AGG(S(i))])
   邻居采样 k 个, 2 层最多 k² 节点

[板书 4: GIN]
   h^(l+1) = MLP((1+ε) h + Σ_{u∈N(v)} h_u)
   SUM, WL 最优

[板书 5: Over-smoothing]
   多层后节点趋同
   解: 残差 / DropEdge / PairNorm / 浅层

十 · 参考资料¶

Kipf & Welling, "Semi-Supervised Classification with GCN", ICLR 2017
Hamilton, Ying, Leskovec, "Inductive Representation Learning on Large Graphs", NeurIPS 2017
Xu et al., "How Powerful are GNNs?", ICLR 2019
Gilmer et al., "Neural Message Passing for Quantum Chemistry", ICML 2017
PyTorch Geometric 文档: pyg.org
Wu et al., "A Comprehensive Survey on GNNs", IEEE TNNLS 2020

方法	思路
DiffPool	学习软分配 \(S^{(l)} = \text{softmax}(\text{GNN}(A, X))\), 节点聚类
TopK Pool	取 top-k 节点 (按学习分数)
SAGPool	自注意力池化
MinCutPool	谱聚类 + GNN

方法	思路
残差	\(H^{(l+1)} = H^{(l)} + \text{GNN}(H^{(l)})\) (类比 ResNet)
DropEdge	训练时随机删边, 减少信息传播
PairNorm	节点对距离正则, 保持分散
初始残差	\(H^{(l+1)} = H^{(0)} + \text{GNN}(H^{(l)})\) 保留初始
浅层 GCN	≤ 2 层 (Cora SOTA)

任务	输出	损失
节点分类	\(h_v\) 直接分类	CrossEntropy
链接预测	\(f(h_u, h_v) = \sigma(h_u^T h_v)\)	BCE
图分类	READOUT(\(h_v\)) 后接 MLP	CrossEntropy