GNN 表达力极限与循环 GNN：2026 年新视角

引言

图神经网络（GNN）的表达力是图机器学习的核心理论问题。2026 年见证了三个重要突破：

Rosenbluth 2026 (AAAI 2026)：循环 GNN 通过迭代次数可达到消息传递 GNN 的表达力上界
Rosenbluth 2026 (arXiv:2603.14846)：消息传递 GNN 存在聚合的本质瓶颈——某些图函数无论怎么加深都无法学到
ICLR 2025：GNN 表达力的完整逻辑框架——超越 WL 测试的逻辑基础

这些结果重新定义了 GNN 表达力理论，统一了消息传递 GNN、循环 GNN、子图 GNN 的关系，并提供了实用设计原则。

核心洞察：

GNN 的”深度”不再是”消息传递次数”——它也可以是”循环次数”。循环 GNN 用更少的参数达到相同甚至更强的表达力。

这与 2025-2026 年 Transformer 架构理论中”循环 = 测试时学习”的精神一脉相承。¹

一、GNN 表达力研究回顾

1.1 经典：WL 测试

Weisfeiler-Leman (WL) 算法（1968）是一种图同构测试：

1-WL 迭代：

初始：每个节点标签 $c_{v}^{(0)} =$ 节点特征
更新： $c_{v}^{(t + 1)} = HASH (c_{v}^{(t)}, {c_{u}^{(t)} : u \in N (v)})$
终止：标签稳定的图同构

核心定理（Xu et al. 2019, Morris et al. 2019）：

消息传递 GNN（MPNN）的表达力 = 1-WL 测试

含义：

MPNN 能区分的图对 = 1-WL 能区分的图对
1-WL 不能区分（如正则图、某些非同构图）→ MPNN 也不能

1.2 超越 WL 的 GNN

方法	表达力	关键思想
k-WL GNN	k-WL	k 元组节点信息聚合
子图 GNN	3-WL	多个子图采样 + 池化
ID-GNN	>1-WL	注入节点身份信息
高阶 GNN	>1-WL	显式模拟高阶 WL
位置编码 GNN	>1-WL	加位置编码（PE）打破对称

1.3 已知局限

经验观察：

MPNN 在异质图、长程依赖任务上表现差
子图 GNN 表达力强但计算开销大
高阶 GNN 难以扩展

理论问题：

MPNN 的精确表达力界限？
循环 GNN 与 MPNN 的关系？
表达力 vs 复杂度的最优权衡？

二、消息传递 GNN 的本质聚合瓶颈

2.1 核心定理（Rosenbluth 2026）

定理（Lost in Aggregation）：

存在图函数 $f : G \to R$ ，使得：

任何消息传递 GNN（任意深度、任意宽度）无法学习
但循环 GNN（用相同参数，迭代 $T$ 次）可以学习

直观理解：

MPNN 的”深度”指层数（每层是不同参数）
循环 GNN 的”深度”指迭代次数（共享参数）
两种深度不等价

2.2 形式化

MPNN 的限制：

设 MPNN 有 $L$ 层，每层 $f_{l} : G \to R^{d}$ 。则：

h_{v}^{(L)} = f_{L} ({f_{L - 1} ({f_{L - 2} (\dots)})})

关键：每层的邻域聚合是局部 + 即时的——只看一步邻居。

循环 GNN 的能力：

设循环 GNN 用同一函数 $f$ 迭代 $T$ 次：

h_{v}^{(T)} = f (h_{v}^{(T - 1)}, u \in N (v) \sum h_{u}^{(T - 1)})

关键：每次迭代加深了”有效邻域”——第 $T$ 次迭代看到 $T$ 跳邻居。

2.3 具体反例：边计数函数

问题：给定图 $G$ ，预测特定节点子集 $S$ 中边数。

MPNN 失败：

第 1 层：每个节点聚合 1-跳邻居
第 2 层：每个节点聚合 2-跳邻居
但第 $L$ 层对 $S$ 内边数信息仍未充分聚合

循环 GNN 成功：

迭代 1：每个节点 1-跳信息
迭代 2：每个节点 2-跳信息
…
迭代 $T$ ：每个节点 $T$ -跳信息
当 $T$ 足够大（ $T =$ 图直径）， $S$ 内边数可被聚合

2.4 与 WL 的关系

经典 WL：

每轮迭代 = 一次”邻域聚合”
收敛的轮数 = 图直径

循环 GNN = WL 视角：

循环 GNN 的迭代 = WL 的轮数
因此循环 GNN ≈ WL 算法的”软”实现

但 MPNN 严格弱于 WL？ 不！MPNN 严格 = WL。

关键澄清：

MPNN 在深度 $L$ 充分大时 = WL 的 $L$ 轮
但参数独立（每层不同）
循环 GNN 在迭代 $T$ 充分大时 = WL 的 $T$ 轮
且参数共享

问题：在固定参数量下，MPNN vs 循环 GNN 谁更强？

2.5 反例的严格构造

定理 2（Rosenbluth 2026 严格反例）：

存在图族 ${G_{n}}$ 和目标函数 $f$ ，使得：

MPNN 用 $p$ 参数需要 $L = Ω (lo g n)$ 层才能学习 $f$
循环 GNN 用 $p$ 参数迭代 $T = O (lo g n)$ 次即可学习 $f$
关键：MPNN 在深度 $L < c lo g n$ 时学习失败

证明概要：

构造对偶图：两个不同图对 MPNN 的所有 $L$ 层输出相同
循环 GNN 通过迭代打破这种对称性

2.6 实际意义

架构选择：

任务需要长程依赖 → 循环 GNN 更优
任务局部且层异质 → MPNN 更优
资源极度受限 → 循环 GNN 更优（参数共享）

三、循环 GNN 的新突破

3.1 AAAI 2026 论文：Repetition Makes Perfect

标题：Repetition Makes Perfect: Recurrent GNNs Match Message Passing Limit

作者：Rosenbluth, Grohe

核心定理：

循环 GNN 通过迭代次数 = MPNN 深度表达力上界

严格陈述：

设 $f^{*}$ 是任何 $L$ 层 MPNN 能计算的图函数
则存在 $L$ 次迭代的循环 GNN 计算 $f^{*}$

反之：

设 $g^{*}$ 是任何 $T$ 次迭代的循环 GNN 能计算的图函数
则存在 $L = T$ 层 MPNN 计算 $g^{*}$

结论：循环 GNN 严格 = MPNN 表达力，但用指数少的参数。

3.2 形式证明

方向 1：循环 GNN ⊆ MPNN

循环 GNN 第 $t$ 迭代 ≈ MPNN 第 $t$ 层（不同参数）

设循环函数 $f$ ，迭代 $T$ 次。构造 MPNN：

第 1 层： $f$
第 2 层： $f$
…
第 $T$ 层： $f$

参数独立 = 总参数量 $\times T$

但：循环 GNN 的 $T$ 次迭代只用了一份参数！

方向 2：MPNN ⊆ 循环 GNN

设 MPNN $L$ 层。构造循环 GNN：

迭代 1：MPNN 第 1 层
迭代 2：MPNN 第 2 层
…

但 MPNN 每层参数不同 → 循环 GNN 需要”切换”参数

关键构造：循环 GNN 用门控决定是否”切换”参数。

class RecurrentGNNBlock(nn.Module):
    """循环 GNN 块（可模拟 MPNN）"""
    def __init__(self, d, n_layers):
        super().__init__()
        self.d = d
        self.n_layers = n_layers
        # 共享参数：消息函数
        self.W_msg = nn.Linear(2 * d, d)
        # 切换门控：决定使用哪个"层"
        self.W_switch = nn.Linear(d, n_layers)
 
    def forward(self, x, adj, T):
        """
        x: (N, d) 节点特征
        adj: (N, N) 邻接矩阵
        T: 迭代次数
        """
        for t in range(T):
            # 聚合
            agg = adj @ x  # (N, d) 邻居聚合
            # 消息
            msg = self.W_msg(torch.cat([x, agg], dim=-1))
            # 切换门控
            switch = F.softmax(self.W_switch(x), dim=-1)  # (N, n_layers)
            # 多"层"参数混合
            update = msg * switch[:, 0:1]
            # 更新
            x = x + update
        return x

3.3 表达能力严格匹配

定理 3（Repetition Makes Perfect 严格版）：

设 $M_{L}$ = 所有 $L$ 层 MPNN 的表达力， $R_{T}$ = 所有 $T$ 次迭代的循环 GNN 的表达力。

则： $M_{L} = R_{L}$ （表达力相等）

推论：

循环 GNN 用 $O (d^{2})$ 参数（共享）实现 MPNN 的 $O (L d^{2})$ 参数
参数效率： $L \times$ 提升
深度效率：相同的有效深度

3.4 实验验证

实验设置：

任务：图分类、节点分类、链接预测
数据集：ZINC、PROTEINS、Cora、CiteSeer
模型：MPNN vs 循环 GNN

结果：

数据集	MPNN (24层)	循环 GNN (4次迭代)	差异
ZINC	0.32 ± 0.04	0.31 ± 0.03	不显著
PROTEINS	73.5%	74.2%	循环略优
Cora	81.5%	82.0%	循环略优
CiteSeer	70.2%	70.5%	循环略优
OGB-Arxiv	71.2%	72.5%	循环优

观察：

循环 GNN 用 6× 更少参数 达到 相同或更好 性能
长程任务（图直径大）上循环 GNN 优势更明显
训练更稳定（共享参数 → 更平滑优化）

3.5 与 Neural ODE GNN 的关系

Neural ODE GNN：

状态 $h (t)$ 由 ODE 决定： $\frac{d h}{d t} = f (h, A)$
等价于连续深度循环 GNN

与循环 GNN 关系：

离散迭代 = Euler 离散化
Neural ODE = 极限情形

理论：

Neural ODE GNN ⊆ 循环 GNN ⊆ MPNN
但实践中 Neural ODE GNN 通常更稳定

四、完整逻辑框架（ICLR 2025）

4.1 论文：Towards a Complete Logical Framework for GNN Expressiveness

核心贡献：

提出用描述逻辑（Description Logic）刻画 GNN 表达力

关键思想：

每个图 = 数据库（事实集合）
每个 GNN = 逻辑查询
GNN 表达力 = 能回答的查询类

4.2 描述逻辑简介

描述逻辑 (DL) 是 OWL（Web Ontology Language）的基础：

构造器：

$⊤$ ：所有节点
$⊥$ ：空集
$\neg C$ ：补
$C ⊓ D$ ：交
$C ⊔ D$ ：并
$\exists r . C$ ：存在 $r$ 关系且满足 $C$
$\forall r . C$ ：所有 $r$ 关系都满足 $C$

例子：

“红色节点” = Red ⊤
“与红色节点相邻” = ∃adj.Red

4.3 GNN 与 DL 的对应

定理 4（逻辑框架）：

设 GNN 类型 $G$ ，对应的逻辑类 $L_{G}$ 。则：

$G 能识别 L ⟺ L \in L_{G}$

GNN 类型	逻辑类 $L$
MPNN	$A LC Q$ (Att. Lin. Concep. Qual.)
k-WL GNN	$C^{k}$ ( $k$ -variable counting)
循环 GNN	$A LC Q$ （同 MPNN，但迭代可达更深的概念）
子图 GNN	扩展的 $C^{k}$

关键洞察：

MPNN = 固定深度的”概念查询”
循环 GNN = 任意深度的”迭代概念查询”
两者表达力相同（逻辑类相同），但深度不同

4.4 表达力层级

层级	逻辑	例子
0	命题逻辑	单节点属性
1	$A LC$	邻域查询
2	$A LC Q$	数量限制
3	$A LC Q I O$	逆关系、传递
4	$S HO I N$	OWL 完整
$\infty$	FOL	一阶逻辑

对应 GNN：

MPNN ≈ 层级 2
循环 GNN ≈ 层级 2（但可表达层级 3 内的查询）
子图 GNN ≈ 层级 3
Transformer with PE ≈ 层级 3+

4.5 应用：图神经网络设计

逻辑框架的实际应用：

任务分析：识别任务需要哪些”逻辑查询”
架构选择：根据查询类型选择合适 GNN
数据生成：合成针对特定逻辑查询的图

示例：

任务：“预测节点 A 是否在三角形中”
- 逻辑：∃edge.∃edge.∃edge
- 适合：MPNN（局部）
任务：“预测图是否包含 k-clique”
- 逻辑：复杂组合
- 适合：子图 GNN

五、其他 2026 年进展

5.1 GNN 在 SAT 问题上的表达力（ICLR 2026）

论文：On the Expressive Power of GNNs for Boolean Satisfiability

核心结果：

MPNN 可以学习 SAT 问题的某些子类，但不能学习一般 SAT。

含义：

SAT 是 NP-complete 问题
GNN 不能解决所有 NP 问题
但可以近似 / 学习 SAT 的子集

5.2 节点标识符存在下的表达力

论文：How Expressive Are GNNs in the Presence of Node Identifiers?

核心结果：

有节点 ID（如唯一编号）→ GNN 表达力 = 1-WL（标准）
无节点 ID（匿名图）→ GNN 表达力 < 1-WL

含义：

实践中使用节点 ID 是常见做法
这是 GNN 比理论表达力强的原因之一
但带来过拟合风险

5.3 路径-邻居聚合（AAAI 2026）

论文：Enhancing Logical Expressiveness in GNNs via Path-Neighbor Aggregation

核心思想：

传统 MPNN 只看直接邻居
路径聚合：考虑邻居之间的路径

结果：

表达力 = 2-WL（强于 1-WL）
但计算开销接近 MPNN

实现：

class PathNeighborGNN(nn.Module):
    def __init__(self, d, n_paths=3):
        super().__init__()
        self.W_msg = nn.Linear(3 * d, d)  # 路径消息
        self.W_update = nn.Linear(2 * d, d)
        self.n_paths = n_paths
 
    def forward(self, x, adj):
        # x: (N, d)
        # adj: (N, N) 邻接矩阵
        for _ in range(self.n_paths):
            # 1-跳邻居
            n1 = adj @ x
            # 2-跳邻居
            n2 = adj @ n1
            # 路径消息
            msg = self.W_msg(torch.cat([x, n1, n2], dim=-1))
            # 更新
            x = self.W_update(torch.cat([x, msg], dim=-1))
        return x

5.4 逻辑学家视角的 GNN（Kostylev 2025）

论文：Foundations of GNNs (A Logician’s View)

贡献：

用模态逻辑统一分析 GNN
给出 GNN 表达力的完整分类
与描述逻辑框架互补

六、循环 GNN 的设计与实践

6.1 架构设计原则

原则 1：参数共享

循环层必须完全共享参数
不共享 → 不是循环 GNN，是普通 MPNN

原则 2：迭代次数 vs 任务

局部任务： $T = 3 - 5$ 足够
长程任务： $T =$ 图直径
推荐：从 $T = 5$ 开始调整

原则 3：稳定性

循环 GNN 容易过平滑（oversmoothing）
需要残差连接 + 归一化

原则 4：门控机制

加门控自适应停止迭代
例如 Gated Recurrent GNN

6.2 现代循环 GNN 架构

class ModernRecurrentGNN(nn.Module):
    """现代循环 GNN：融合多种最佳实践"""
    def __init__(self, d, n_iterations, n_heads=4, dropout=0.1):
        super().__init__()
        self.d = d
        self.n_iterations = n_iterations
        self.n_heads = n_heads
 
        # 共享的消息函数
        self.W_msg = nn.Linear(2 * d, d)
        # 门控
        self.W_gate = nn.Linear(2 * d, d)
        # 归一化
        self.norm = nn.LayerNorm(d)
        # 注意力头（用于多关系图）
        self.attn_heads = nn.ModuleList([
            nn.Linear(d, d) for _ in range(n_heads)
        ])
        self.W_combine = nn.Linear(d * n_heads, d)
        # Dropout
        self.dropout = nn.Dropout(dropout)
        # 输出
        self.W_out = nn.Linear(d, d)
 
    def forward(self, x, adj, edge_attr=None):
        """
        x: (N, d)
        adj: (N, N) or list of (N, N) for multi-relational
        edge_attr: optional edge features
        """
        h = x
        for t in range(self.n_iterations):
            # 多头注意力
            head_outs = []
            for attn in self.attn_heads:
                head_out = adj @ attn(h)  # 邻接矩阵 × 变换后特征
                head_outs.append(head_out)
            attn_out = self.W_combine(torch.cat(head_outs, dim=-1))
 
            # 消息
            msg = self.W_msg(torch.cat([h, attn_out], dim=-1))
            msg = self.dropout(msg)
 
            # 门控更新
            gate = torch.sigmoid(self.W_gate(torch.cat([h, attn_out], dim=-1)))
            h = h + gate * msg
 
            # 归一化
            h = self.norm(h)
 
        return self.W_out(h)

6.3 训练技巧

1. 迭代次数的退火

def curriculum_iterations(model, epoch, max_iter):
    """课程学习：从少到多"""
    t = min(epoch // 100 + 1, max_iter)
    model.n_iterations = t

2. 残差连接的深度

循环 GNN 必须有残差（避免过平滑）
推荐： $h_{t + 1} = h_{t} + f (h_{t}, A)$

3. 学习率调度

循环 GNN 训练更稳定 → 可用更高学习率
推荐：比 MPNN 高 1.5-2 倍

4. 多迭代共享 vs 多层独立

完全共享：参数少、训练快
块共享：每 $K$ 次迭代切换参数（折中）

七、表达力基准测试

7.1 合成基准

基准	测试能力	适用 GNN
四色问题	节点特征组合	MPNN
子图计数	局部结构	MPNN + PE
同构测试	全局结构	子图 GNN
长程依赖	远距离关系	循环 GNN
动态图	时序结构	Temporal GNN

7.2 实际基准

图分类：

ZINC：分子图，测试化学性质预测
PROTEINS：蛋白质结构
OGB-MolPCBA：大规模分子
PCQM4Mv2：量子化学

节点分类：

Cora / CiteSeer：引文网络
OGB-Arxiv / OGB-Products：大图
MAG / OAG：异质图

链接预测：

OGB-DDI：药物相互作用
Amazon Co-purchase

7.3 表达力评估工具

def evaluate_expressivity(model, dataset):
    """评估 GNN 表达力"""
    # 1. 同构图识别
    iso_acc = evaluate_isomorphism(model, dataset.iso_pairs)
 
    # 2. 距离预测
    dist_acc = evaluate_distance_prediction(model, dataset.distance_pairs)
 
    # 3. 子图计数
    count_acc = evaluate_subgraph_counting(model, dataset.triangles, dataset.squares)
 
    return {
        'isomorphism': iso_acc,
        'distance': dist_acc,
        'subgraph': count_acc,
    }

八、现代 GNN 设计原则

8.1 何时用什么

任务	推荐 GNN	理由
短程 + 局部	MPNN	简单高效
长程 + 远距离	循环 GNN	迭代打破局部性
全局结构	子图 GNN	强表达力
异质图	RGCN / HAN	关系感知
动态图	TGN / DyRep	时序建模
大规模	GraphSAGE	邻居采样
注意力	GAT / Transformer	软注意力

8.2 架构混合

最佳实践：

基础层：MPNN（捕获局部）
全局层：循环 GNN 或 Attention（捕获全局）
跳跃连接：缓解过平滑
PE 增强：位置编码提升表达力

class HybridGNN(nn.Module):
    """混合 GNN：MPNN + 循环 + 注意力"""
    def __init__(self, d, n_layers, n_iterations):
        super().__init__()
        self.mpnn = MPNNLayer(d, d)
        self.recurrent = RecurrentLayer(d, n_iterations)
        self.attn = GATLayer(d, d, n_heads=4)
        self.norm = nn.LayerNorm(d)
 
    def forward(self, x, adj):
        # 局部
        h1 = self.mpnn(x, adj)
        # 全局
        h2 = self.recurrent(x, adj)
        # 注意力
        h3 = self.attn(x, adj)
        # 融合
        h = h1 + h2 + h3
        return self.norm(h)

8.3 与 Transformer 的关系

统一视角：

标准 GNN = 消息传递 = 局部 Attention
Graph Transformer = 全连接 Attention + 位置编码
循环 GNN = 共享参数的多层

Graph Transformer 的新趋势：

加结构编码（如 Laplacian PE）
用子图采样提升扩展性
与SSM 结合（如 Graph Mamba）

九、完整 PyTorch 实现

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import MessagePassing
from torch_geometric.utils import add_self_loops, degree
 
 
class RecurrentGNNLayer(MessagePassing):
    """循环 GNN 层（共享参数）"""
    def __init__(self, d, aggr='add'):
        super().__init__(aggr=aggr)
        self.d = d
        self.W_msg = nn.Linear(2 * d, d)
        self.W_update = nn.Linear(2 * d, d)
        self.W_gate = nn.Linear(2 * d, d)
        self.norm = nn.LayerNorm(d)
 
    def forward(self, x, edge_index, edge_attr=None):
        # x: (N, d)
        # edge_index: (2, E)
        # 计算度数归一化
        row, col = edge_index
        deg = degree(col, x.size(0), dtype=x.dtype)
        deg_inv_sqrt = deg.pow(-0.5)
        deg_inv_sqrt[deg_inv_sqrt == float('inf')] = 0
        norm = deg_inv_sqrt[row] * deg_inv_sqrt[col]
 
        # 消息传递
        msg = self.propagate(edge_index, x=x, norm=norm, edge_attr=edge_attr)
 
        # 更新
        gate = torch.sigmoid(self.W_gate(torch.cat([x, msg], dim=-1)))
        update = self.W_update(torch.cat([x, msg], dim=-1))
        x_new = x + gate * update
        return self.norm(x_new)
 
    def message(self, x_i, x_j, norm, edge_attr=None):
        # x_i: 中心节点, x_j: 邻居节点
        msg_input = torch.cat([x_i, x_j], dim=-1)
        if edge_attr is not None:
            msg_input = torch.cat([msg_input, edge_attr], dim=-1)
        return norm.view(-1, 1) * self.W_msg(msg_input)
 
 
class RecurrentGNN(nn.Module):
    """完整循环 GNN"""
    def __init__(self, in_d, hidden_d, out_d, n_iterations, dropout=0.1):
        super().__init__()
        self.in_proj = nn.Linear(in_d, hidden_d)
        # 关键：单一 GNN 层被循环使用
        self.gnn_layer = RecurrentGNNLayer(hidden_d)
        self.n_iterations = n_iterations
        self.dropout = nn.Dropout(dropout)
        self.out_proj = nn.Linear(hidden_d, out_d)
 
    def forward(self, x, edge_index, edge_attr=None, batch=None):
        """
        x: (N, in_d)
        edge_index: (2, E)
        batch: (N,) 节点到图的映射（用于图级任务）
        """
        # 输入投影
        h = self.in_proj(x)
        h = self.dropout(h)
 
        # 循环迭代（关键：参数共享）
        for t in range(self.n_iterations):
            h = self.gnn_layer(h, edge_index, edge_attr)
            h = self.dropout(h)
 
        # 输出
        if batch is not None:
            # 图级任务：池化
            from torch_geometric.utils import scatter
            h = scatter(h, batch, dim=0, reduce='mean')
        return self.out_proj(h)
 
 
class MPNNBaseline(nn.Module):
    """MPNN 基线（用于对比）"""
    def __init__(self, in_d, hidden_d, out_d, n_layers, dropout=0.1):
        super().__init__()
        self.in_proj = nn.Linear(in_d, hidden_d)
        # 关键：多层，每层独立参数
        self.gnn_layers = nn.ModuleList([
            RecurrentGNNLayer(hidden_d) for _ in range(n_layers)
        ])
        self.dropout = nn.Dropout(dropout)
        self.out_proj = nn.Linear(hidden_d, out_d)
 
    def forward(self, x, edge_index, edge_attr=None, batch=None):
        h = self.in_proj(x)
        h = self.dropout(h)
        for layer in self.gnn_layers:
            h = layer(h, edge_index, edge_attr)
            h = self.dropout(h)
        if batch is not None:
            from torch_geometric.utils import scatter
            h = scatter(h, batch, dim=0, reduce='mean')
        return self.out_proj(h)
 
 
# 训练和比较
def train_and_compare():
    """训练循环 GNN 和 MPNN 并比较"""
    from torch_geometric.datasets import ZINC
    from torch_geometric.loader import DataLoader
 
    train_dataset = ZINC(root='./data/ZINC', subset=True, split='train')
    train_loader = DataLoader(train_dataset, batch_size=128, shuffle=True)
 
    # 循环 GNN（参数少）
    recurrent = RecurrentGNN(in_d=1, hidden_d=64, out_d=1, n_iterations=8)
    n_params_recurrent = sum(p.numel() for p in recurrent.parameters())
    print(f"循环 GNN 参数: {n_params_recurrent}")
 
    # MPNN（参数多）
    mpnn = MPNNBaseline(in_d=1, hidden_d=64, out_d=1, n_layers=8)
    n_params_mpnn = sum(p.numel() for p in mpnn.parameters())
    print(f"MPNN 参数: {n_params_mpnn}")
 
    print(f"参数效率: {n_params_mpnn / n_params_recurrent:.1f}x")
 
    # 训练循环
    opt = torch.optim.Adam(recurrent.parameters(), lr=1e-3)
    for epoch in range(50):
        for batch in train_loader:
            opt.zero_grad()
            pred = recurrent(batch.x, batch.edge_index, batch.edge_attr, batch.batch)
            loss = F.l1_loss(pred.view(-1), batch.y)
            loss.backward()
            opt.step()
        if epoch % 10 == 0:
            print(f"Epoch {epoch}, loss {loss.item():.4f}")
 
 
if __name__ == "__main__":
    # 简单测试
    N, E, d = 10, 30, 64
    x = torch.randn(N, 1)
    edge_index = torch.randint(0, N, (2, E))
 
    recurrent = RecurrentGNN(in_d=1, hidden_d=d, out_d=1, n_iterations=5)
    mpnn = MPNNBaseline(in_d=1, hidden_d=d, out_d=1, n_layers=5)
 
    out_rec = recurrent(x, edge_index)
    out_mpnn = mpnn(x, edge_index)
    print(f"循环 GNN 输出: {out_rec.shape}")
    print(f"MPNN 输出: {out_mpnn.shape}")

总结

2026 年 GNN 表达力理论的三个关键突破：

Rosenbluth 2026 (AAAI)：循环 GNN 严格 = MPNN 表达力，参数效率 $L$ × 提升
Rosenbluth 2026 (arXiv)：MPNN 存在聚合瓶颈，某些函数学不到
ICLR 2025：完整逻辑框架，用描述逻辑刻画 GNN 表达力

关键洞察：

GNN 的”深度”不再只是”消息传递层数”——它也可以是”循环迭代次数”。循环 GNN 用更少的参数达到相同甚至更强的表达力。

实践建议：

局部任务：MPNN 仍是最优
长程任务：循环 GNN 是新选择
资源受限：循环 GNN 用 $L$ × 更少参数
全局结构：子图 GNN + 位置编码

未来方向是统一架构：MPNN + 循环 + 注意力 + 位置编码的深度融合。¹

参考资料

主要参考：Rosenbluth & Grohe 2026 “Repetition Makes Perfect: Recurrent GNNs Match Message Passing Limit” (AAAI 2026, https://ojs.aaai.org/index.php/AAAI/article/view/39707)；Rosenbluth 2026 “Lost in Aggregation” (arXiv:2603.14846)；ICLR 2025 “Towards a Complete Logical Framework for GNN Expressiveness”。其他相关工作：Xu et al. 2019 “How Powerful are Graph Neural Networks?” (ICLR)；Morris et al. 2019 “Weisfeiler and Leman Go Neural” (ICLR)；Hao et al. 2020 “The Logical Expressiveness of Graph Neural Networks” (ICLR)；Peltonen & Wattenhofer 2026 (ICLR 2026) “On the Expressive Power of GNNs for Boolean Satisfiability”；Soeteman, Benedikt, Grohe 2026 “How Expressive Are GNNs in the Presence of Node Identifiers?”；Kostylev 2025 “Foundations of GNNs (A Logician’s View)” 等。 ↩ ↩²

Metaphor

探索

GNN 表达力极限与循环 GNN：2026 年新视角

GNN 表达力极限与循环 GNN：2026 年新视角

引言

一、GNN 表达力研究回顾

1.1 经典：WL 测试

1.2 超越 WL 的 GNN

1.3 已知局限

二、消息传递 GNN 的本质聚合瓶颈

2.1 核心定理（Rosenbluth 2026）

2.2 形式化

2.3 具体反例：边计数函数

2.4 与 WL 的关系

2.5 反例的严格构造

2.6 实际意义

三、循环 GNN 的新突破

3.1 AAAI 2026 论文：Repetition Makes Perfect

3.2 形式证明

3.3 表达能力严格匹配

3.4 实验验证

3.5 与 Neural ODE GNN 的关系

四、完整逻辑框架（ICLR 2025）

4.1 论文：Towards a Complete Logical Framework for GNN Expressiveness

4.2 描述逻辑简介

4.3 GNN 与 DL 的对应

4.4 表达力层级

4.5 应用：图神经网络设计

五、其他 2026 年进展

5.1 GNN 在 SAT 问题上的表达力（ICLR 2026）

5.2 节点标识符存在下的表达力

5.3 路径-邻居聚合（AAAI 2026）

5.4 逻辑学家视角的 GNN（Kostylev 2025）

六、循环 GNN 的设计与实践

6.1 架构设计原则

6.2 现代循环 GNN 架构

6.3 训练技巧

七、表达力基准测试

7.1 合成基准

7.2 实际基准

7.3 表达力评估工具

八、现代 GNN 设计原则

8.1 何时用什么

8.2 架构混合

8.3 与 Transformer 的关系

九、完整 PyTorch 实现

总结

参考资料

Footnotes

关系图谱

目录

反向链接