Graph Learning Should Move Beyond Restrictive Views of Spectral and Message-Passing GNNs¶

会议: NeurIPS 2026
arXiv: 2602.10031
OpenReview: https://openreview.net/forum?id=82awBSyQDS
领域: 其他
关键词: 图神经网络, 谱图神经网络, 空间消息传递, 特征基不变性, 表达能力等价性

一句话总结¶

本文系统剖析了谱图神经网络（Spectral GNNs）与空间消息传递网络（MPNNs）的对称性根源，证明了在线性谱滤波与局部聚合图移位算子约束下两者的图区分与逼近能力等价性，并提出基于特征基不变性的广义谱学习范式与互补理论视角。

研究背景与动机¶

在图表示学习的发展历程中，图神经网络（GNNs）长期沿着两条各自独立的研究脉络并行演进：一条根植于机器学习社区，以消息传递神经网络（MPNNs）为核心，基于局部邻域排列等变性通过聚合与更新迭代传播节点表征；另一条则源于信号处理与应用数学，将图上节点特征视作图信号，借助邻接矩阵或图拉普拉斯矩阵等图移位算子（GSO）在谱域定义滤波算子。然而，由于学界长期缺乏对“何为谱图神经网络”的严格公理化定义，大多数谱 GNN 研究默认退化为多层线性对角滤波器结构，不仅导致大量关于稳定性、尺寸可迁移性（transferability）与泛化界的理论成果在两个领域被反复“重复发现”，也人为模糊了谱方法与空间方法的本质分野。

现存理论分析的核心矛盾在于：一方面，传统文献往往采用过于宽松的 GSO 假设或引入全局图信息，使得空间与谱方法的等价性或包含关系流于单向或平凡化；另一方面，现有谱 GNN 将设计空间严格限制在函数演算线性滤波器内，使其计算实质上可被局部多项式消息传递严格重写，从而掩盖了真正具备全局或非线性频率混合潜力的谱现象。同时，社区常将谱位置编码（SPE）与谱滤波架构深度绑定，混淆了结构输入增强与骨干网络计算算子的界限。

面对两大阵营在理论语义上的割裂与低水平重复，本文提出必须跳出“对角线性谱滤波”与“局部排列不变性”的狭义视界，从对称性群论视角重建两者的数学根基，并明确两者在离散逻辑表达力与连续平滑/瓶颈分析上的互补优势。核心 idea：将谱 GNN 重新公理化定义为满足特征基不变性（eigenbasis invariance）的映射类，证明在局部聚合 GSO 限制下线性谱滤波与标准 MPNN 在 1-WL 图区分力与紧支集逼近力上严格等价，并确立 MPNN 擅长离散同构与逻辑、谱方法擅长过平滑/过挤压/社区结构的互补理论分工。

方法详解¶

整体框架¶

本文作为定位与理论基础论文（Position & Theory Paper），提出了一套厘清 MPNN 与谱 GNN 本质关系与互补特性的理论框架。整体架构从对称性原理出发，推导两类模型所依附的群不变性，接着形式化定义了合理的局部聚合图移位算子（Aggregation GSO），随后构建出多项式逼近与误差传播链条以证明表达能力等价性，最后将谱位置编码解耦为正交的特征增强机制，并确立两者的理论分工。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["图数据与对称性原理<br/>邻域排列对称 vs 特征空间基对称"] --> B["对称性分立推导<br/>MPNN邻域置换不变 vs 广义谱GNN特征基不变"]
    B --> C["聚合移位算子限制<br/>排除全局信息泄漏的严格局部GSO定义"]
    C --> D["表达力等价性证明<br/>函数演算与多项式滤波↔1-WL与MPNN双向等价"]
    D --> E["谱位置编码解耦<br/>将特征级结构编码与骨干卷积算子彻底解耦"]
    E --> F["互补理论分析空间<br/>MPNN侧重离散逻辑同构 / 谱GNN侧重平滑瓶颈分析"]

关键设计¶

1. 对称性分立推导：从排列不变性到特征基不变性

传统观点仅泛泛地将 MPNN 与谱 GNN 均归为节点排列等变（permutation equivariant）模型，这无法阐明两者的结构分歧。本文明确指出两类架构源于不同的对称性约束： - MPNN 的邻域置换不变性：MPNN 每一层将节点邻域视为多重集（multiset）。由于将多重集转化为输入序列时的顺序是任意的，处理局部邻域的聚合更新算子必须对对称群 $\mathcal{S}_K$ 保持置换不变。根据 DeepSets 理论，单层求和消息传递是紧支集上连续对称函数的通用逼近器。 - 谱 GNN 的特征基不变性：自伴图移位算子 $\mathbold{S} = \mathbold{V}\bm{\Lambda}\mathbold{V}^\top$ 的特征分解并不唯一——特征向量存在符号模糊性（即 $\mathbold{v}_j$ 与 $-\mathbold{v}_j$ 均有效），且当特征值存在多重度时同一特征子空间内任意正交基均成立。因此，一个合格的谱 GNN 层必须独立于具体选取的特征基，即对任意两个有效特征基 $\mathbold{V}$ 与 $\mathbold{V}'$ 恒满足： $$\forall \mathbold{X} \in \mathbb{R}^{N \times d}, \quad \psi(\mathbold{S}, \mathbold{V}, \mathbold{X}) = \psi(\mathbold{S}, \mathbold{V}', \mathbold{X})$$ 经典函数演算线性谱滤波 $H(\mathbold{S})\mathbold{X} = \sum_{i=1}^N \mathbold{v}_i \mathbold{v}_i^\top \mathbold{X} H(\lambda_i)^\top$ 仅是利用正交投影子空间和 $\sum_{i:\lambda_i=\lambda} \mathbold{v}_i \mathbold{v}_i^\top$ 保证基无关性的一种特例，且欠缺全空间通用逼近能力。真正的广义谱 GNN 应探索非对角、非线性的全频段交互映射（如基于归一化投影解析与合成的非线性滤波）。

2. 聚合移位算子与表达力等价性：函数演算谱 GNN 与 1-WL 的双向闭包

以往研究往往允许任意 $N \times N$ 矩阵充当 GSO，甚至允许对角线直接编码图同构类别，导致谱模型表达力虚高。本文提出聚合图移位算子（Aggregation GSO）概念：若对于任意图信号 $\mathbold{f} \in \mathbb{R}^N$，映射 $\mathbold{f} \mapsto \mathbold{S}\mathbold{f}$ 均能被有限层求和聚合 MPNN 精确实现，则称 $\mathbold{S}$ 为聚合 GSO。邻接矩阵 $\mathbold{A}$、度矩阵 $\mathbold{D}$、组合拉普拉斯 $\mathbold{L}$、对称归一化拉普拉斯 $\mathbold{L}_{\text{sym}}$ 以及 Jacobi 截断的 Cayley 算子均严格满足此定义。在此约束下，本文给出了线性谱 GNN 与 MPNN 的完整等价性定理： - 图区分能力等价（Theorem 3）：定义在聚合 GSO 上的任意连续函数演算谱 GNN $\mathcal{F}_{\text{C}}(\mathbold{S})$，其在图级分离能力上严格受限于 1 维 Weisfeiler-Leman (1-WL) 测试；反之，采用邻接矩阵的多项式谱 GNN 即可完全达到 1-WL 的区分上限，两者在图同构判别上严格等价。 - 一致逼近能力等价与发散（Propositions 19 & 20）：若数据分布中图移位算子的谱被一致有界区间 $[-B, B]$ 包含，由 Weierstrass 逼近定理，连续频响可被多项式在谱上一致逼近，此时函数演算谱 GNN 与多项式 MPNN 的函数逼近能力完全等价；但对于完全图等最大特征值随节点数无界增长的分布，多项式谱 GNN（及 MPNN）无法在下确界范数意义下逼近正弦函数频响 $f(\lambda)=\sin\lambda$ 的谱 GNN，揭示出有界假设在逼近理论中的关键临界作用。

3. 谱位置编码解耦与理论分工重塑

本文澄清了长期以来将谱位置编码（SPE，如取拉普拉斯特征向量前 $k$ 维 $\mathbold{V}[i, :]$）与谱 GNN 绑定的概念误区。SPE 本质上是一种正交的输入表征增广手段，无论后端挂接 MPNN 还是谱滤波骨干，其引入的全局坐标系才是打破 1-WL 限制的真正推手。更进一步，标准 GCN/GIN 迭代更新 $\mathbold{X}^{(l)} = \rho(\sum_{k=0}^{K-1} \mathbold{S}^k \mathbold{X}^{(l-1)} \mathbold{H}_k^{(l)})$ 自身在数学上即可被改写为作用于 GSO 特征向量的非线性参数化映射，证明标准空间卷积自身即可隐式构造数据自适应的谱位置信息。因此，理论研究与模型设计应将谱位置信息构建与下游处理模块模块化解耦，并在分析时严格控制 PE 变量。

损失函数 / 训练策略¶

作为理论与定位文献，本文未设计单一可训参数网络，而是为后续基准测试（Controlled Benchmarks）与理论推演规定了数学约束策略： 1. 谱收缩与过平滑判据：通过 Dirichlet 能量 $\mathcal{E}(\mathbold{X}) = \frac{1}{2}\text{tr}(\mathbold{X}^\top \mathbold{L} \mathbold{X})$ 跟踪特征坍缩。谱滤波下的狄利克雷收缩率直接由频响上限控制：$\mathcal{E}(\mathbold{X}^{(t+1)}) \leq (\max_{i \geq 2}|h_t(\lambda_i)|^2) \mathcal{E}(\mathbold{X}^{(t)})$，显式指导热核 $e^{-\tau \lambda}$、预解核 $(1+\beta \lambda)^{-1}$ 等低通滤波器的通带设计。 2. 过挤压（Over-squashing）谱诊断：利用代数连通度（拉普拉斯矩阵第二小特征值 $\lambda_2$）、有效电阻与节点雅可比矩阵范数界分析信息瓶颈，采用保留中频的谱滤波或增加谱间隙的重布线（rewiring）替代盲目加深网络。

实验关键数据¶

主实验¶

为了验证理论推导的核心论点，本文梳理并形式化对比了 MPNN 与谱 GNN 在不同理论假设下的表达能力等价界限与计算边界：

理论评估维度	传统认知 / 窄口径线性谱 GNN	本文统一视角 / 广义谱理论框架	核心数学结论 / 差异判定
对称性源头	节点排列等变（过于泛化）	局部邻域置换不变 vs 算子特征基不变	确立不同群不变性下的归纳偏置
图分离能力	谱滤波弱于或无法直接对比 MPNN	聚合 GSO 下连续谱滤波与 1-WL 严格等价	Theorem 3：双向等价，同构判别界限一致
紧谱逼近力	经验性多项式截断拟合	紧谱集合上多项式与连续频响完全等价	Proposition 20：有界谱上 MPNN 逼近力等价
无界谱逼近力	普遍假设多项式能够充分表达	离散完整图大谱上存在确定性逼近下界失效	Proposition 19：多项式谱滤波出现本质逼近断层
谱位置编码 (SPE)	归属于谱 GNN 专属架构优势	输入端特征增强，与骨干卷积形式完全正交	控制变量下两类骨干均从显式/隐式 SPE 获益

消融实验¶

针对理论证明中涉及的算子构造条件与收敛假设，本文通过构造性命题反例与引理消融分析了边界条件的必要性：

构造条件消融配置	理论推导有效性 / 表达力评定	关键机制与证明依据说明
允许全局非局部 GSO（例如含全局同构标签）	理论失效：谱 GNN 表达力异常凌驾于任意 WL 阶数	破坏局部性假设，全局信息泄漏使等价性证明平凡崩溃
引入聚合 GSO 限制 (Definition 2)	理论成立：谱 GNN 区分力严格闭包于 1-WL	保证每个 GSO 频响项均能被有限层求和 MPNN 精确实现
无界谱分布 $\sigma(\mathbold{S}) \to \infty$ (Proposition 19)	多项式逼近失败：$\text{ess\,sup} \\|f - p\\| > \varepsilon$ 恒成立	外推区域多项式发散，无法逼近周期性连续正弦频响
一致有界谱分布 $\sigma(\mathbold{S}) \subseteq [-B, B]$	理论成立：多项式与连续频响可任意精度一致逼近	由 Weierstrass 逼近定理保证有限区间内的一致收敛性
隐式 SPE 构造 (Proposition 22)	空间 MPNN 无需特征分解即可隐式表达特征向量	证明双层卷积在数学上等价于对特征基应用单层感知机

关键发现¶

分离能力与逼近能力的解耦：在图同构分离（Separation Power）层面上，即使频响是任意连续函数，只要移位算子是局部的，线性谱 GNN 就无法超越 1-WL；但在函数逼近层面上，一旦特征值谱无界，多项式谱网络（及 MPNN）相较于连续谱滤波会暴露理论盲区。
稳定性分析工具的表象差异：MPNN 传统上采用逐层扰动分析，误差界往往随深度呈指数放缩；谱方法基于算子摄动理论得到依赖于多项式阶数或 Lipschitz 常数的线性界。本文指出这主要是由于 MPNN 默认每层插入非线性所致，一旦 MPNN 采用模块化延后激活机制，两者的稳定性保证完全一致。

亮点与洞察¶

划定谱图学习的真正边界：指出当前绝大多数所谓的“谱 GNN”本质上只是空间消息传递的一种低效或特定重参数化形式，为领域指明了发展“非对角、非线性全频特征基不变谱滤波”的新方向。
建立互补分工的理论地图：打破了“谁终将取代谁”的单一竞争思维，明确指出离散算法推理、逻辑复杂性分析天然适配 MPNN，而连续信息传播、过平滑衰减控制与瓶颈诊断则必须借助谱分析的数学工具。
解开谱位置编码的认知混淆：把 SPE 从“谱架构专属属性”还原为“通用的结构特征注入机制”，证明了许多经验收益并非源于谱卷积算子本身，而是源于位置编码打破了对称性盲区。

局限与展望¶

理论聚焦于函数演算线性体系：本文的主体等价性证明严格针对最广泛采用的对角线性滤波架构；对于最新涌现的非线性特征基不变谱网络（如 NLSF 等），其具体的 WL 表达力层级与逼近边界尚待建立完备理论。
缺乏超大规模经验基准实测：作为 Position Paper，本文未在大规模工业级图基准（如 OGB-LSC 或大型异质图）上展开全量消融比对，后续亟需构建针对瓶颈、平滑和有向图的受控隔离评测集。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从特征基不变性公理化重构谱 GNN，终结了谱与空间等价性的长期含混争论。
实验充分度: ⭐⭐⭐⭐☆ 理论推导完备自洽，反例构造与命题证明严谨，虽为 Position Paper 但数学论证极为扎实。
写作质量: ⭐⭐⭐⭐⭐ 论述逻辑严密，文献脉络梳理清晰，立场鲜明且富有前瞻启发性。
价值: ⭐⭐⭐⭐⭐ 为图学习领域指明了摆脱狭隘线性滤波的理论路径，对模型设计与基准制定具有里程碑式的指导意义。