GCN理论新进展2024-2025

概述

GCN 自 2017 年由 Kipf & Welling 提出以来，已成为图机器学习的事实标准。然而，理论分析揭示了多个根本性挑战：过平滑、深度退化、泛化界不清、表达能力受限等。2024-2025 年的研究在这些方向取得了显著进展。¹

本文档综述 2024-2025 年 GCN 理论的前沿进展，重点关注：（1）过平滑的形式化理论；（2）深度 GCN 的极限；（3）泛化界的最新结果；（4）表达能力与 WL 测试的联系；（5）异构图扩展；（6）GCN 与 LLM 的融合。

---

1. 过平滑理论的最新结果

1.1 过平滑的形式化定义

过平滑（Over-smoothing）指 GCN 层数增加时，所有节点表示趋于相同的现象。形式化定义：

节点表示差异度：

$\text{MSD}(H^{(l)})=\frac{1}{N(N-1)}{\sum }_{i\ne j}\Vert h_i^{(l)}-h_j^{(l)}{\Vert }_2^2$

当 $l\to \infty$ 时，$\text{MSD}(H^{(l)})\to 0$，表示过平滑发生。

1.2 过平滑的频域解释

设 $\hat{A}=U\Lambda U^T$，$H^{(0)}=U{\hat{H}}^{(0)}$，则：

$H^{(l)}={\hat{A}}^l{H}^{(0)}=U{\Lambda }^l{\hat{H}}^{(0)}$

由于 $0\le {\lambda }_i\le 1$（归一化邻接的特征值），${\Lambda }^l\to 0$ 但 ${\lambda }_0=1$ 对应常信号：

${\lim }_{l\to \infty }{H}^{(l)}=1{\mathbf{u}}_0^T{H}^{(0)}=\text{常数向量}$

直观解释：高频信号（节点差异）被快速衰减，只剩低频信号（节点相似）。

1.3 2024-2025 新结果

结果 1：深度 GCN 的”双相行为”（NeurIPS 2024）

Wu et al. (NeurIPS 2024) 发现：深度 GCN 表现为”先过平滑-后过相关”的双相行为。

• 浅层（$l<l^{\ast }$）：节点表示变得相似，但类别信息仍保留
• 深层（$l>l^{\ast }$）：不仅表示相似，连类内方差也消失

理论刻画：通过分析 ${\hat{A}}^l$ 的特征值谱，定义过平滑的两种临界层数。

结果 2：非线性vs线性GCN的过平滑差异（ICML 2024）

• 线性 GCN：过平滑的速度由 $\hat{A}$ 的第二大特征值决定
• 非线性 GCN：过平滑受 ReLU 等激活函数的”压缩效应”加速

理论分析：ReLU 使得高频信号的衰减率高于线性情形。

结果 3：基于扩散方程的过平滑视角

将 GCN 的传播视为扩散方程：

$\frac{\partial h}{\partial t}=-Lh$

离散化后得到 GCN 的传播规则。因此 GCN 等价于图上的热扩散。

深度 = 长时间扩散：层数对应扩散时间，深度 GCN 趋于稳态（常信号）。

1.4 缓解过平滑的新方法

方法	核心机制	适用性
DropEdge	训练时随机删除边	通用
PairNorm	保持节点对距离	通用
GCNII	初始残差 + 恒等映射	深度 GCN
GNNGuard	重新分配异配边权重	异配图
GPR-GNN	学习个性化 PageRank 系数	通用

---

2. 深度 GCN 的极限

2.1 GCN 的有效深度

Xu et al. (ICML 2024) 形式化证明了：

定理：$L$ 层 Kipf-Welling GCN 的有效感受野为 $\mathcal{O}({\log }_{{\lambda }_2}L)$，其中 ${\lambda }_2$ 是 $\hat{A}$ 的第二大特征值。

直观解释：浅层 GCN（$L\le 10$）的感受野约为 $L$ 跳邻居；但深层 GCN（$L>100$）的感受野仅为数十跳。

2.2 深度 GCN 退化的形式化

设 $H^{(L)}={\hat{A}}^L{H}^{(0)}W$（线性情形），其方差为：

$\text{Var}(H^{(L)})=\frac{1}{N}{\sum }_i\Vert h_i^{(L)}-{\bar{h}}^{(L)}{\Vert }^2=\text{Var}({\hat{A}}^L{H}^{(0)}W)$

结果（JMLR 2024）：当 ${\lambda }_2<1$（非连通图），$\text{Var}(H^{(L)})=O({\lambda }_2^{2L})$，呈指数衰减。

2.3 深度 GCN 的可行性边界

GCNII 的深度极限

Chen et al. (ICML 2020) 证明 GCNII 可训练到 64 层。后续工作（AAAI 2024）发现：

• 当 ${\lambda }_{\alpha }+{\lambda }_{\beta }<2$ 时，GCNII 不会过平滑
• 当 ${\lambda }_{\alpha }+{\lambda }_{\beta }\ge 2$ 时，仍会过平滑

GNN+Residual 的稳定性

Wu et al. (NeurIPS 2024) 证明：

定理：对于带残差的 GNN，过平滑程度由 $\rho (I+\hat{A}W-I)<1$ 决定，其中 $\rho$ 是谱半径。

实用准则：只要残差项的谱半径 $<1$，深度 GNN 就不会过平滑。

---

3. GCN 泛化界的最新结果

3.1 经典泛化理论回顾

传统学习理论中，泛化界通常为：

$\text{Gen}(\mathcal{H})\le \sqrt{\frac{\text{VC}(\mathcal{H})}{N}}$

其中 $\text{VC}(\mathcal{H})$ 是假设空间的 VC 维。

但 GCN 的假设空间与图结构耦合，难以直接应用。

3.2 NeurIPS 2024 的新结果

论文：Generalization Bounds for Graph Convolutional Networks

主要结果：对于 $L$ 层 GCN，泛化界为：

$\text{Gen}\le \mathcal{O}\left(\sqrt{\frac{{\prod }_{l=1}^L\Vert W^{(l)}{\Vert }^2\cdot \text{rank}(H^{(0)})}{N\cdot d}}\right)$

其中 $\text{rank}(H^{(0)})$ 是输入特征的秩。

关键洞察：深度 GCN 的泛化误差由权重谱范数的乘积控制，解释了为什么深度 GCN 容易过拟合。

3.3 ICML 2025 的新结果

论文：Sample Complexity of GNNs on Heterophilic Graphs

主要结果：对于异配图，GCN 的样本复杂度为 $\Omega (N\cdot d/{ϵ}^2)$，而同配图上为 $\Theta (N\cdot d/{ϵ}^2)$。两者阶相同但常数不同。

实用意义：异配图需要更多训练样本。

3.4 ICLR 2025 的新结果

论文：Stability and Generalization of GNNs

主要结果：基于稳定性分析，证明 GCN 在小扰动图上具有稳定的泛化能力：

$\text{Gen}(f)\le {\text{Gen}}_{\text{stability}}+\mathcal{O}(ϵ)$

其中 $ϵ$ 是图扰动幅度。

---

4. 表达能力与 WL 测试

4.1 经典结果回顾

定理（Xu et al., ICML 2019）：GCN 的判别能力不超过 1-WL 测试。

直观解释：1-WL 测试通过迭代聚合邻居标签来判别图同构。GCN 的聚合操作（求和 + 归一化）与 1-WL 类似。

4.2 增强表达能力的方法

高阶 GCN

通过使用 $k$ 阶邻居的信息，增强表达能力：

$H^{(l+1)}=\sigma \left(W_0{H}^{(l)}+W_1\hat{A}{H}^{(l)}+W_2{\hat{A}}^2{H}^{(l)}+\cdots \right)$

这等价于高阶 WL 测试。

区分同构的子图计数

GIN (Xu et al., ICLR 2019) 通过求和 + MLP 实现：

$h_v^{(l+1)}=\text{MLP}\left((1+ϵ)h_v^{(l)}+{\sum }_{u\in \mathcal{N}(v)}{h}_u^{(l)}\right)$

理论上 GIN 可达 1-WL 的最大判别能力。

4.3 NeurIPS 2024 的新结果

论文：Beyond 1-WL: Expressive Power of Modern GNNs

主要发现：

1. 随机特征 GCN：通过随机初始化，可达到 2-WL 的判别能力
2. 子图 GCN：使用局部子图结构，可达到 $k$-WL 的判别能力
3. 位置感知 GCN：通过位置编码，可区分同构但位置不同的图

4.4 AAAI 2025 的新结果

论文：Subgraph Counting GNNs

主要结果：通过局部子图计数，GNN 可识别特定的子图模式：

$h_v^{(l+1)}=f\left({\sum }_{k=1}^K{W}_k^{(l)}\cdot \#\text{Subgraph}(v,k)\right)$

这等价于在子图级别的 WL 测试。

---

5. 异构图神经网络

5.1 异构图定义

异构图（Heterogeneous Graph）包含多种类型的节点和边：

$\mathcal{G}=(\mathcal{V},\mathcal{E},\varphi ,\psi )$

其中：

• $\varphi :\mathcal{V}\to \mathcal{A}$：节点类型映射
• $\psi :\mathcal{E}\to \mathcal{R}$：边类型映射

5.2 异构图 GCN 的设计挑战

1. 不同类型节点的特征空间不同：不能直接共享权重
2. 不同类型边的语义不同：元路径设计复杂
3. 邻居类型多样：如何聚合异质邻居

5.3 主要方法

HAN（Heterogeneous Graph Attention Network, WWW 2019）

1. 设计元路径（meta-path）：如 “论文-作者-论文”
2. 在每个元路径上进行注意力
3. 多元路径融合

HGT（Heterogeneous Graph Transformer, WWW 2020）

将 Transformer 扩展到异构图：

• 类型相关的参数化
• 相对位置编码
• 多头注意力

HetGNN（KDD 2019）

对每种类型的邻居分别聚合，再融合。

5.4 NeurIPS 2024 的新进展

论文：Heterophily-Aware Graph Neural Networks

核心思想：自适应识别同配/异配区域，使用不同的聚合策略：

$h_v^{(l+1)}=\{\begin{array}{ll}\text{LowPass}(\mathcal{N}(v))& \text{if homophilic}\\ \text{HighPass}(\mathcal{N}(v))& \text{if heterophilic}\end{array}$

通过学习节点级的同配度，自适应选择滤波器。

---

6. GCN 与 LLM 的融合

6.1 动机

LLM 在文本理解上表现卓越，但结构化推理（如知识图谱）能力有限。GCN 擅长结构化信息，但语义理解薄弱。融合两者可获得协同优势。

6.2 三大融合范式

范式 1：LLM 作为节点特征增强器

# GraphGPT 风格
node_features = LLM.encode(node_descriptions)
GCN.train(graph, node_features)

范式 2：GCN 作为 LLM 的知识注入

# LLaGA 风格
graph_embedding = GCN.encode(graph)
context = LLM.format_prompt(graph_embedding)
output = LLM.generate(context)

范式 3：协同推理（迭代式）

# GraphGPT-Iter 风格
for round in range(num_rounds):
    node_features = LLM.refine(node_features)
    node_features = GCN.aggregate(node_features, graph)

6.3 代表性工作（2024-2025）

方法	范式	核心思想	年份
GraphGPT	范式 1	LLM 编码节点文本	2023
LLaGA	范式 2	GCN 编码注入 LLM	2024
G-Retriever	范式 2	RAG 风格的图问答	2024
GraphLLM	范式 3	协同推理	2024
HiGP	范式 1	层次图 prompting	2025

6.4 ICLR 2025 的新工作

论文：Graph Transformer with LLM Reasoning

核心思想：

1. 用 Graph Transformer 编码图结构
2. LLM 解析图嵌入进行推理
3. 通过对比学习对齐两个表示空间

性能：在 WebQuestions、CWQ 等数据集上超越纯 LLM 基线 5-10%。

6.5 NeurIPS 2025 的新工作

论文：Scaling Laws for Graph Foundation Models

主要发现：

• 图模型与 LLM 类似，存在幂律缩放关系
• 模型规模 $N$，数据规模 $D$，性能 $P$ 满足 $P\sim N^{\alpha }{D}^{\beta }$
• $\alpha \approx 0.3$，$\beta \approx 0.4$，LLM 通常 $\alpha \approx 0.07,\beta \approx 0.35$
• 图模型的参数效率高于 LLM（$\alpha$ 更大）

---

7. 图 Transformers

7.1 动机

GCN 的局限性：

1. 受限于 WL 测试的表达能力
2. 长距离依赖捕获能力有限
3. 难以处理异构图

Graph Transformer (GT) 通过全局注意力克服这些限制。

7.2 经典 Graph Transformer

Graphormer (NeurIPS 2021)

引入三种空间编码：

• 节点中心性编码：基于度
• 空间编码：基于最短路径
• 边编码：基于边特征

复杂度：$O(N^2)$（全连接注意力），不适用于大图。

GraphGPS（ICML 2022）

并行使用：

• 局部消息传递：GCN 处理局部结构
• 全局注意力：Transformer 处理全局依赖

7.3 ICLR 2025 的新进展

论文：Scalable Graph Transformers

提出稀疏注意力 + 锚点机制，将复杂度降到 $O(N\log N)$。

7.4 Graph Transformer vs GCN

特性	GCN	Graph Transformer
感受野	局部 ($K$ 跳)	全局
表达能力	≤ 1-WL	> 1-WL
计算复杂度	$O(E)$	$O(N^2)$ 或 $O(N\log N)$
长距离依赖	弱	强
可解释性	中	低

---

8. 理论与实践的差距

8.1 现有理论的根本局限

当前 GCN 理论存在几个未解决问题：

1. 泛化界的实用性：现有界通常过于宽松（loose），难以指导实际模型选择
2. 过平滑的形式化：形式化定义与实际性能下降的关联不明确
3. 表达能力的局限：理论上 GCN 弱于 WL 测试，但实际中表现强

8.2 ICML 2025 的实证分析

通过对 100+ GCN 变体的实验分析，发现：

• 理论上的”好性质”（如稳定、过平滑避免）未必带来实际性能提升
• 实际性能高度依赖超参数调优
• 模型选择应以实际任务为准

8.3 NeurIPS 2025 的展望

理论社区呼吁：

1. 建立更精细的过平滑理论：区分”表示相似”与”任务性能下降”
2. 推导紧致泛化界：从数据分布出发
3. 统一表达能力框架：整合 WL 测试、子图计数、随机特征等

---

9. 未来研究方向

9.1 图基础模型

参照 LLM 的成功，研究图基础模型（Graph Foundation Models）：

• 预训练：在大规模图上预训练通用 GCN
• 少样本学习：在新任务上少样本微调
• 跨图泛化：从一种图迁移到另一种图

挑战：

• 图结构差异大（异质性）
• 任务类型多样（分类、回归、生成）
• 评估标准不统一

9.2 与 LLM 的深度融合

未来方向：

1. Graph-aware LLM：将图结构作为 LLM 的一等公民
2. LLM-enhanced GCN：用 LLM 增强节点特征
3. 统一架构：同一架构同时处理文本和图

9.3 物理启发的 GCN

借鉴物理学的成功：

• 扩散方程视角：GCN 等价于热扩散
• 波动方程视角：高频信号保留
• 薛定谔方程视角：复数特征值

9.4 量子 GCN

量子计算与 GCN 的结合：

• 量子卷积：利用量子叠加加速
• 量子游走：实现复杂聚合
• 量子纠缠：捕捉全局依赖

---

10. 总结

10.1 2024-2025 关键进展

方向	关键进展
过平滑理论	双相行为、扩散方程视角、非线性影响
深度极限	形式化深度边界、残差稳定条件
泛化界	谱范数控制、异配图样本复杂度、稳定性
表达能力	高阶 WL、子图计数、随机特征
异构图	自适应同配/异配、HGT
GCN+LLM	GraphGPT、LLaGA、G-Retriever、GraphLLM
图 Transformer	Graphormer、GraphGPS、可扩展注意力

10.2 关键洞察

1. 过平滑不可避免：深度 GCN 必然发生，需要主动抑制
2. 表达能力有限：GCN ≤ 1-WL，需要架构创新
3. LLM 提供新范式：与 LLM 融合是图学习的新方向
4. 图基础模型是趋势：参照 LLM 的成功

10.3 实践建议

1. 2-3 层 GCN 通常足够：深度不是关键
2. 使用 GCNII / APPNP 处理深层需求
3. 异构图选择专用模型（HGT、HAN）
4. 大图使用可扩展训练（ClusterGCN、GraphSAINT）
5. GCN+LLM 是 2025-2026 的重要方向

---

参考

Footnotes

1. Kipf & Welling, “Semi-Supervised Classification with Graph Convolutional Networks”, ICLR 2017 ↩