GCN 与图卷积

1. 为什么 GCN 是图神经网络的经典起点

GCN（Graph Convolutional Network，图卷积网络）由 Kipf 和 Welling 在 2017 年提出（Semi-Supervised Classification with Graph Convolutional Networks），是第一个真正意义上的可扩展、可端到端训练的图神经网络模型。

它的历史地位来自三个突破：

首次将卷积从欧氏空间迁移到图结构：在此之前，图上的特征聚合需要手工设计；GCN 通过谱图理论证明可以在图上定义局部、平移不变的卷积操作。
线性复杂度：每层只涉及邻接矩阵与节点特征的乘法，计算代价，可处理 millions 级节点的大规模图。
半监督节点分类的端到端框架：将图结构本身作为正则项，无需显式特征工程。

这三个特点让 GCN 成为此后几乎所有图神经网络研究的基线出发点——后续的 GAT、GraphSAGE、GIN 等模型，都是在 GCN 的框架上”打补丁”。

2. 从谱图理论到 GCN 公式：完整的逻辑链

2.1 图拉普拉斯矩阵：定义与直觉

给定无向图，邻接矩阵为，度矩阵，其中。

图拉普拉斯矩阵（归一化形式）定义为：

对称半正定矩阵，可以正交对角化：

其中是特征向量矩阵，是特征值对角矩阵，。

为什么它出现在图神经网络中？

拉普拉斯矩阵的物理含义是离散拉普拉斯算子在图上的推广——它描述了图中节点信号的”平滑梯度”。如果一个节点信号在相邻节点间变化剧烈，作用于它会得到较大的值。在谱域（frequency domain）分析图信号时，拉普拉斯矩阵的特征值对应不同频率：小 → 低频（平滑信号），大 → 高频（剧烈变化信号）。

2.2 图上的卷积：谱域定义

在欧氏 CNN 中，卷积定理告诉我们：卷积等于频域中的乘法。对于图结构，我们可以类似地定义谱域卷积。

设图信号（每个节点一个标量），其傅里叶变换为。那么图卷积操作定义为：

$谱域滤波器$

其中是谱域滤波器，是可学习参数。

关键问题：如果直接对每个特征值学习一个参数，复杂度是，且无法泛化到不同图结构。理想情况是让滤波器局部化（只看近邻），并且参数数量与图大小无关。

2.3 Chebyshev 多项式近似：走向局部卷积

Defferrard 等人在 2016 年提出的 ChebNet 解决了这个问题。其核心思想是：用 Chebyshev 多项式展开谱域滤波器，使其变为**-局部化**的——即每个节点的输出只依赖其阶邻居。

展开形式：

其中：

是缩放后的拉普拉斯矩阵（特征值映射到）
是 Chebyshev 多项式递归定义
是个可学习参数

展开后，卷积操作变为：

展开的每一项恰好对应** 阶邻居的信号传递**。当时，滤波器退化为只使用 1 阶邻居。

2.4 标准 GCN：一阶近似（K=1）

Kipf 和 Welling 的关键简化是取，即一阶 Chebyshev 近似，并做了两个额外的归一化处理。

从出发：

代入并对参数重命名（和合并为），得到：

注意：这里的，所以展开后会涉及。

进一步简化——将替换为，其中（加 self-loop），是对应的度矩阵。

这就是 GCN 传播公式：

其中：

：第层的节点特征矩阵
：第层的可学习权重矩阵
：加了自环的邻接矩阵（每个节点包含自己的信息）
：非线性激活函数（如 ReLU）

多层 GCN（2 层为例）：

2.5 归一化邻接矩阵为什么必要

有两个原因：

第一，度归一化保证了对称性。

使得矩阵行和列都归一化为 1。这意味着：

度大的邻居对节点的影响被适当削弱（不会因为某个节点邻居极多就主导整层输出）
拉普拉斯算子的特征值被限制在，条件数改善，梯度更稳定

如果直接用，度大的节点的特征会直接被压倒；如果用行归一化，则不对称，梯度更新不对称，不保证信息传递的平衡性。

第二，self-loop 让每个节点直接保留自身信息。

意味着每个节点在每轮聚合中至少保留自身特征的一部分。没有 self-loop 的 GCN 会丢失上一层的节点自身信息——这通常是一个 bug而非特性。

3. GCN 与传统 CNN：类比的成立与局限

3.1 类比成立的地方

维度	欧氏 CNN	图 GCN
信息聚合	每个卷积核聚合局部邻域像素	每个 filter 聚合局部邻居节点
参数共享	同一卷积核用于所有空间位置	同一权重矩阵用于所有节点
局部性	卷积感受野随层数指数增长	图上感受野随层数指数增长（阶邻居）
平滑效果	深层卷积使特征趋于平滑	深层 GCN 使节点表征趋于同质化

3.2 类比不成立的地方

问题	具体表现
平移不变性不成立	图没有自然的空间平移概念——节点没有”坐标”，邻居没有固定顺序。两个拓扑相似的局部图可能几何结构完全不同
邻居数量不固定	CNN 卷积核有固定的感受野大小（如 3×3）；GCN 每个节点的邻居数可以差异巨大（从 1 到 10000+），导致每次聚合的有效样本数不同
无法定义真正的卷积核	欧氏卷积核有明确的物理意义（边缘检测、纹理提取等）。GCN 的谱域滤波器是定义在图拉普拉斯谱上的，参数学习依赖于特定图结构，无法直接迁移到不同图上
池化操作难以定义	图像池化有清晰的下采样语义（图的空间缩放）；图的池化需要额外设计（Graclus、DiffPool 等），且目前没有统一方案

总结：GCN 本质上是一个邻居聚合器（neighborhood aggregator），而不是真正的卷积。它借鉴了卷积的思想（局部 + 参数共享），但缺乏欧氏卷积的核心数学性质——平移不变性和局部性在图上都只能近似实现。

4. GCN 是局部平滑模型：数学直觉与 over-smoothing

4.1 什么是局部平滑

从谱域看，GCN 每层的操作是对图信号的低通滤波：

的特征值越小，对应的傅里叶分量（对应图中变化缓慢的模式）受到的影响越小
拉普拉斯矩阵本身度量的是图的 Dirichlet 能量——即相邻节点特征差异的加权和

的特征值最大为 1，最小大于 0。每层迭代都让信号向低频方向移动——平滑的方向。

4.2 Over-smoothing：多层堆叠的核心问题

当层数增加时，GCN 的输出会趋向于所有节点收敛到相同的表征。原因：

从矩阵角度看，两层 GCN 的传播是：

执行层后，聚合矩阵的所有行趋向于相同（当时，如果图的特征值接近 1）。这意味着无论输入特征是什么，经过足够多层后，输出都会变得不可区分。

经验观察：

2-3 层 GCN 效果最好
超过 5 层后性能显著下降
这与”信息在图上传播需要一定距离”之间存在根本矛盾——你需要足够深的网络让远距离节点交换信息，但深网络又导致 over-smoothing

缓解方法：

Jump Knowledge Network（JKNet）：聚合每层输出而非只取最后一层
DropEdge：随机删除边，减缓信息同质化速度
残差连接（Residual connections）：，让每一层保留部分原始信息

5. 工程流程与实现注意事项

5.1 输入图的预处理

Step 1：构建邻接矩阵

import torch
import scipy.sparse as sp
 
# 原始邻接矩阵（有权或无权）
A = sp.csr_matrix(...)  # shape: (N, N)
 
# 添加 self-loop（几乎必做）
A_hat = A + sp.eye(A.shape[0])
 
# 度归一化
D_hat = sp.diags(A_hat.sum(axis=1).A1, format='csr')
D_half_inv = sp.diags(1.0 / np.sqrt(A_hat.sum(axis=1).A1))
A_norm = D_half_inv @ A_hat @ D_half_inv

Step 2：稀疏矩阵转换

对于大图（>10万节点），务必使用稀疏矩阵存储和计算：

A_norm_sparse = A_norm.tocsr()
# 前向传播时
def gcn_layer(X, W, A):
    return A_norm_sparse @ X @ W  # 稀疏 × 稠密

5.2 Self-loop：为什么常加

不加 self-loop 时，信息流严格遵循边方向传播。如果一个节点没有出边（或入边），它的特征永远不会更新。加 self-loop 后，即使某个节点完全孤立，它的自身特征也会在下一层被保留。

GCN 原论文的实现（伪代码）：

A = A + I  # 实际上在计算过程中使用 A' = A + I

这一步骤使拉普拉斯矩阵的条件数改善，收敛更稳定。

5.3 训练场景的差异

场景	特点	实现注意事项
小图（<10k 节点）	可以将整个图一次性加载到 GPU，邻接矩阵做密集计算	直接使用的稠密表示
大图（>100k 节点）	无法一次性加载，使用 mini-batch	只能用 GraphSAGE 风格的采样（NeighborSampler）或稀疏矩阵乘法。纯 GCN 在大图上直接全图训练不可行
中图（10k-100k）	单机可训练，但需注意显存	邻接矩阵用稀疏格式，每 epoch 可多次采样 mini-batch

mini-batch 训练的关键：由于 GCN 的聚合涉及整个邻接矩阵，无法像图像 CNN 那样做独立 mini-batch。需要用图采样算法（如 GraphSAGE 的邻居采样）将每个 batch 的节点限制在局部子图内。

5.4 训练中的常见问题

过拟合（Overfitting）：

图数据通常节点数有限、边更稀疏，容易在小节点集合上过拟合
缓解：dropout（GCN 原论文即使用）、图增强（GraphAugmentation）、early stopping

梯度消失/爆炸：

GCN 层间传播涉及矩阵乘法，如果图结构不均匀（度分布极偏），梯度可能不稳定
缓解：层归一化、BatchNorm（在图上应用时需要小心，因为 batch 内图结构可能不同）

训练不稳定：

归一化不当导致特征值接近 1，深层 GCN 矩阵连乘后梯度爆炸
缓解：添加残差连接，限制网络深度

6. GCN 在不同任务中的应用方式

6.1 节点分类（Node Classification）

GCN 最经典的任务。模型输出每个节点的类别预测：

# 2层 GCN
H1 = ReLU(A_norm @ H0 @ W0)
H2 = A_norm @ H1 @ W1  # 无激活（用于 softmax）
logits = F.log_softmax(H2, dim=1)
 
# 半监督场景：只对有标签节点计算 loss
loss = F.nll_loss(logits[labeled_mask], y[labeled_mask])

适用场景： Cora、CiteSeer、PubMed 引文网络；社交网络用户分类。

6.2 链路预测（Link Prediction）

GCN 本身不是为链路预测设计的，但可以通过以下方式应用：

节点嵌入方法：用 GCN 编码得到节点表征，链路的得分用或计算
编码器-解码器框架：GCN 作为编码器，内积作为解码器

z_i = gcn_layer_i(node_i)
z_j = gcn_layer_j(node_j)
score = sigmoid(z_i @ z_j.T)  # 链路预测分数

6.3 图分类（Graph Classification）

需要聚合整张图的表征：

Readout 操作：将所有节点表征汇总为图级表征（sum/mean/max + readout）
层次化池化：用 DiffPool 或 ASAP 动态构建层次结构

# 简单的方式：平均 readout
graph_embedding = torch.mean(H_last, dim=0)  # shape: (F,)
output = MLP(graph_embedding)

6.4 使用 GCN 的典型陷阱

陷阱	说明
只看最后一层输出	对于浅层 GCN 来说没问题，但多层 GCN 存在 over-smoothing，应用 JKNet 或类似聚合
忽视度分布不均	高度节点的特征会在单次聚合中压倒其他节点，考虑 GAT 或采样策略
所有节点用同一批邻居	小 batch 训练时，如果不采样邻居而是用全局邻接矩阵，GPU 显存会爆炸
用 GCN 做深网络	超过 3-4 层时 GCN 通常退化，优先选择有残差连接的变体

7. GCN 公式速查

拉普拉斯矩阵：

GCN 单层前向传播：

其中，

简化形式（无激活函数前）：

参数数量：对于输入维度和输出维度，权重矩阵包含个参数（不含偏置）

2 层 GCN（节点分类）：

其中

8. GCN 使用注意事项

加 Self-loop 是默认选项：几乎所有场景都应使用，除非有明确的领域知识认为节点不应包含自身信息
层数控制在 2-3 层：除非使用残差连接或 JKNet，否则超过 4 层极易出现 over-smoothing
度归一化不可或缺：D^{-1/2} A D^{-1/2} 形式的对称归一化比 D^{-1} A 的行归一化效果更好、更稳定
大图训练必须用稀疏矩阵：对的稠密矩阵在大图上是行不通的，使用 scipy.sparse 或专门的图引擎（如 DGL、PyG）
图采样是 mini-batch 训练的关键：纯 GCN 无法对节点做独立 mini-batch，必须用邻居采样（如 NeighborLoader）将计算限制在局部子图
Overfitting 是小图的主要风险：图结构本身是一种强正则，dropout + early stopping 是必要的
GCN 不擅长捕捉高阶结构：它的聚合是对邻居的线性/平均操作，无法区分不同拓扑模式（如三角结构）。如果任务高度依赖拓扑，选择 GIN（Graph Isomorphism Network）等更表达能力强的模型
链路预测任务需要额外的解码器：GCN 编码 + 内积解码是最简单的组合，但往往需要更复杂的评分函数（如 DeepWalk、LINE 的思路）
异构图需要扩展：GCN 只适用于同构图。异构图需要针对不同节点/边类型分别设计聚合路径（R-GCN、HAN 等）

参考文献

Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR.
Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. NeurIPS.
Wu, F., et al. (2019). Simplifying Graph Neural Networks. ICML.
Li, Q., Han, Z., & Wu, X.-M. (2018). Deeper Insights into Graph Convolutional Networks. AAAI.

Huajishe Notes

Explorer

3-GCN与图卷积