Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs¶

会议: AAAI 2026 (Oral)
arXiv: 2511.13010
代码: https://github.com/jeongwhanchoi/MPNN-FN
领域: 图神经网络 / 消息传递
关键词: 分形节点, MPNN, 长距离依赖, over-squashing, 图划分, MLP-Mixer, METIS

一句话总结¶

提出分形节点（Fractal Nodes）增强 MPNN 的长距离消息传递：通过 METIS 图划分生成子图级聚合节点，结合低通+高通滤波器（LPF+HPF）与可学习频率参数 $\omega$，使用 MLP-Mixer 实跨子图通信，在保持 $O(L(|V|+|E|))$ 线性复杂度的同时达到甚至超越图 Transformer 的性能，获 AAAI Oral。

研究背景与动机¶

GNN 面临局部与全局信息的根本矛盾：

MPNN 的 over-squashing 问题：信息通过多跳传播时，固定宽度节点向量形成"瓶颈"，远距离节点间的信号被指数级压缩。有效电阻（effective resistance）越高，信息流越受阻
图 Transformer 的代价：全局自注意力解决了长距离依赖，但 $O(|V|^2)$ 二次复杂度限制可扩展性，且忽略图的局部拓扑结构
虚拟节点的局限：单一全局虚拟节点是常用增强手段，但所有节点共享一个聚合点仍会成为信息瓶颈

核心问题：能否在 MPNN 框架内（线性复杂度）解决长距离依赖？ 本文的答案：用分形节点，灵感来自真实网络中的分形结构——图划分自然诱导分形结构，子图反映全图连接模式。

方法详解¶

整体框架¶

在原始图上添加"分形节点"层：(1) METIS 划分图为 C 个子图；(2) 每个子图生成一个分形节点，与子图内所有节点相连（单跳快捷连接）；(3) 每层先执行标准 MPNN 消息传递，再更新分形节点，再将分形节点信息传回原始节点；(4) 最终层可选用 MLP-Mixer 实现跨子图通信。

关键设计¶

分形节点的构造：不同于简单均值池化（仅保留 DC 分量/最低频信号），使用 LPF+HPF 双通道： $$f_c^{(\ell+1)} = \text{LPF}(\{h_{v,c}\}) + \omega_c^{(\ell)} \cdot \text{HPF}(\{h_{v,c}\})$$ LPF 为子图均值（全局信息），HPF = 节点特征 - LPF（局部细节），$\omega$ 为可学习参数控制高频贡献。分类任务倾向高频，回归任务倾向低频
阻力缩减定理（Theorem 4.1）：对原图 $\mathcal{G}$ 任意节点 u, v，增强图 $\mathcal{G}_f$ 中的有效电阻 $R_f(u,v) \leq R(u,v)$。分形节点通过单跳快捷连接直接降低有效电阻，从理论上保证改善 over-squashing
MLP-Mixer 跨子图通信（FN_M 变体）：在最终层对所有分形节点应用 MLP-Mixer（token-mixing + channel-mixing），不需构建粗化网络即可实现长距离子图间交互，复杂度仅 $O(Cd^2)$
两个变体：FN（仅逐层分形节点更新）和 FN_M（额外加 MLP-Mixer 跨子图通信）

损失函数¶

与基础 MPNN 相同的任务损失（分类用交叉熵，回归用 MAE/MSE）。分形节点作为可微附加结构端到端训练。

实验关键数据¶

主实验：6 个基准数据集性能对比¶

方法	Peptides-func AP↑	Peptides-struct MAE↓	MNIST Acc↑	CIFAR10 Acc↑
GCN	0.6328	0.2758	0.9269	0.5423
GINE	0.6405	0.2780	0.9705	0.6131
GraphGPS	0.6534	0.2509	0.9805	0.7230
GRIT	0.6988	0.2460	0.9811	0.7647
Graph-ViT/MLP-Mixer	0.6970	0.2449	0.9846	0.7158
GINE+FN_M	0.7018	—	0.9858	0.7459
GatedGCN+FN_M	0.7040	—	0.9862	0.7528

消融实验：表达能力（合成数据集）¶

方法	CSL Acc	SR25 Acc	EXP Acc
GCN	10.00	6.67	52.17
GCN+FN_M	39.67	100.0	86.40
GINE	10.00	6.67	51.35
GINE+FN_M	47.33	100.0	95.58
GatedGCN	10.00	6.67	51.25
GatedGCN+FN_M	49.67	100.0	96.50

关键发现¶

MPNN+FN 超越图 Transformer：GINE+FN_M 在 Peptides-func 上 0.7018 AP 超越 GraphGPS 的 0.6534（+7.4%），同时复杂度从 $O(L|V|^2)$ 降到 $O(L(|V|+|E|))$
SR25 达 100% 准确率：所有 MPNN 基线在 SR25 上仅 6.67%，加 FN_M 后跳至 100%，证明分形节点大幅提升表达能力（超越 1-WL）
Over-squashing 缓解：TreeNeighboursMatch 实验中，标准 MPNN 在 tree depth > 4 失败，MPNN+FN 能泛化到 depth = 7
HPF 至关重要：移除 HPF 后性能显著下降，高通信号对分类任务关键
METIS > Louvain > Random：METIS 生成的划分保持社区结构，分形节点更具代表性
分区数 C=32 最优：过少则粒度粗，过多则通信成本增加

亮点与洞察¶

"图 Transformer 是否必要？"：这个问题本身有很强的 community 影响力。答案："不一定"，MPNN+分形节点就够了——线性复杂度 + 可比/更优性能
分形几何 + GNN 的交叉：图划分自然诱导分形结构（子图反映全图连接模式），betweenness centrality 分布验证了这一点
均值池化的理论局限：Theorem 3.1 证明均值池化仅保留最低频（DC）分量，丢失所有高频信息——LPF+HPF 的设计有理论支撑
MLP-Mixer 在图领域的成功：注意力机制并非处理全局信息的唯一手段

局限性¶

METIS 划分是预处理步骤，对动态图或结构变化场景适应性差
分区数 C 是超参数，不同图可能需要不同最优 C——自适应分区策略待研究
仅一层分形节点，多层次分形（分形的分形）可能进一步提升
MLP-Mixer 引入的额外 $O(Cd^2)$ 在极大图上可能不可忽略

评分¶

新颖性: ⭐⭐⭐⭐⭐ 分形节点是全新概念，理论和直觉都有说服力
实验充分度: ⭐⭐⭐⭐ 多基准验证 + 合成数据表达能力 + 消融全面
写作质量: ⭐⭐⭐⭐ 问题和方法清晰，理论严谨
价值: ⭐⭐⭐⭐⭐ 可能改变 GNN 社区对图 Transformer 必要性的认知

方法类别	代表	复杂度	长距离能力	局部保持
标准 MPNN	GCN, GINE	$O(L	E	)$
虚拟节点	VN (Gilmer 2017)	$O(L(	V	+
图重布线	DIGL, FoSR	$O(L	E'	)$
图 Transformer	GraphGPS, Graphormer	$O(L	V	^2)$
分形节点（本文）	MPNN-FN/FN_M	**$O(L(	V	+