Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective¶

会议: NeurIPS 2026
arXiv: 2610.04157
OpenReview: https://openreview.net/forum?id=jCWFiEFBxj
领域: 其他
关键词: 过挤压, 细胞滑轮, 滑轮有效电阻, 图神经网络, 平坦向量丛

一句话总结¶

本文提出滑轮有效电阻理论，证明消息传递的雅可比灵敏度受滑轮有效电阻上界控制，通过平坦向量丛模型 FlatNSD 在不改变图拓扑的前提下端到端学习限制映射，即可有效缓解过挤压。

研究背景与动机¶

图神经网络在处理复杂关系数据时展现出强大能力，但在捕获长距离节点依赖时普遍面临瓶颈。过度平滑（Over-smoothing）使深层节点表征趋于均一，而过度挤压（Over-squashing）则由于指数级扩张的邻域信息被迫压缩进固定维度的向量，造成跨多跳通信时的严重信息丢失与表征塌缩。以往研究主要将过挤压归咎于图的拓扑瓶颈，经典分析借助图有效电阻与负曲率边刻画结构阻碍，并发展出图重连（Rewiring）技术，通过添加或删除边来扩大谱隙并降低总有效电阻。

然而，修改图拓扑存在难以调和的矛盾：直接加边不仅破坏了原始图数据的物理与语义结构，而且往往会急剧加速过度平滑现象，使得深层模型在克服长程通信瓶颈的同时丧失区分邻域特征的能力。尽管近年来神经滑轮扩散（NSD）等细胞滑轮模型展示了通过代数拓扑结构抵抗过度平滑并建模异质图的潜力，但滑轮理论能否直接用于缓解过挤压、是否必须像 BuNN 等模型一样跳出经典消息传递范式，一直缺乏清晰的理论阐释与通用的数学工具。

本文的核心切入点是转变对通信瓶颈的归因视角：信息传递的阻碍并不必然源于图拓扑本身，而取决于依附在图上的代数结构。核心 idea：将经典图有效电阻推广为滑轮有效电阻，证明平坦向量丛下的消息传递雅可比灵敏度受滑轮有效电阻上界约束，从而无需改动图拓扑即可仅通过学习正交限制映射动态消除过挤压瓶颈。

方法详解¶

整体框架¶

本文的方法建立在细胞滑轮代数拓扑与消息传递框架的融合之上。整体计算流水线包含三个主要环节：首先为图的每个节点指派正交限制映射，构建平坦向量丛；接着基于滑轮拉普拉斯算子推导滑轮有效电阻，建立通信瓶颈与雅可比灵敏度之间的显式上界；最后在消息传递范式下实例化轻量模型 FlatNSD，利用局部邻域特征端到端优化正交群变换，实现自适应信道调制。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入图结构与节点特征"] --> B["1. 平坦向量丛正交映射参数化<br/>学习节点局部正交旋转群"]
    B --> C["2. 滑轮有效电阻显式调制<br/>闭式计算两点与全局电阻"]
    C --> D["3. 雅可比灵敏度上界约束<br/>理论绑定信息传递损失"]
    D --> E["4. FlatNSD 局部消息传递迭代<br/>多层图卷积特征更新与输出"]

关键设计¶

1. 平坦向量丛正交映射参数化：降低计算复杂度并规避数值不稳定

经典神经滑轮扩散（NSD）需要为每条入射的顶点-边对学习高维限制映射，参数量随边数线性增长且在深层训练中极易遭遇数值奇异性。为了兼顾计算扩展性与理论可解析性，本文将限制映射约束在平坦正交丛（Flat \(O(d)\)-bundles）范畴。对每个节点 \(v \in V\)，模型仅学习一个专属的正交矩阵 \(\mathcal{F}_v \in O(d)\)，并将该映射直接应用于所有与 \(v\) 关联的边。在这一几何约束下，全局滑轮拉普拉斯矩阵可显式正交分解为：

\[L_{\mathcal{F}} = \mathbf{O}^{\top} (L_G \otimes I_d) \mathbf{O}\]

其中 \(\mathbf{O} = \text{blockdiag}(\mathcal{F}_1, \dots, \mathcal{F}_n)\)。由于正交相似变换保持了图拉普拉斯算子 \(L_G\) 的谱结构，其伪逆算子具有简洁的闭式表达 \(L_{\mathcal{F}}^{+} = \mathbf{O}^{\top} (L_G^{+} \otimes I_d) \mathbf{O}\)，从而将全图求逆的计算代价严格限制在未重连图拉普拉斯伪逆的预计算中，避免了对任意滑轮做重复伪逆分解的开销。

2. 滑轮有效电阻显式调制：建立拓扑无关的代数信道阻抗度量

传统有效电阻仅由图邻接和度数决定，无法反映特征空间内的方向性信息传导。本文提出滑轮有效电阻（Sheaf Effective Resistance），定义任意两节点 \(u, v\) 间的滑轮电阻为 \(R_{\mathcal{F}}(u, v) = (\mathbbm{1}_u - \mathbbm{1}_v)^{\top} L_{\mathcal{F}}^{+} (\mathbbm{1}_u - \mathbbm{1}_v)\)。在平坦向量丛下，该度量可进一步拆解为几何旋转夹角与图伪逆的显式代数表达式：

\[R_{\mathcal{F}}(u, v) = d \big((L_G^{+})_{uu} + (L_G^{+})_{vv} - 2 \cos(\theta_{uv}) (L_G^{+})_{uv}\big)\]

其中 \(\theta_{uv}\) 表示节点 \(u, v\) 在正交群变换后全 1 向量方向的夹角。当图拉普拉斯伪逆交叉项 \((L_G^{+})_{uv} < 0\) 时，只要正交映射使得两者方向相反（\(\cos \theta_{uv} = -1\)），即可实现滑轮有效电阻的大幅缩减。进一步地，全图总滑轮有效电阻 \(R_{\mathcal{F}}\) 满足严格不等式 \(\frac{R_{\mathcal{F}}}{d} \leq R\)，且只要限制映射非平凡常数即可实现严格降低。这表明通信信道的瓶颈无需通过添加几何边来打通，仅靠在节点内部特征流向中注入正交相位旋转即可完成去瓶颈。

3. 雅可比灵敏度上界约束：严格绑定长程传播敏感度与滑轮阻抗

为了将代数度量与 GNN 实际信息压缩建立因果联系，本文对多层消息传递中节点状态 \(h_u^{(r)}\) 对远端初始特征 \(x_v\) 的雅可比矩阵二范数 \(\|\partial h_u^{(r)} / \partial x_v\|\) 展开边界分析。定理证明在平坦向量丛下，当激活与消息函数导数有界时，雅可比敏感度满足以下严格上界：

\[\left\|\frac{\partial h_u^{(r)}}{\partial x_v}\right\| \leq (2\alpha\beta)^r \frac{d_{\max}}{2} \left(\frac{2}{d_{\min}} \left(r + 1 + \frac{\mu^{r+1}}{1 - \mu}\right) + 4\max\{(L_G^{+})_{uv}, 0\} - \frac{R_{\mathcal{F}}(u, v)}{d}\right)\]

全图节点对求和后，总敏感度上界直接由总滑轮有效电阻项 \(-\frac{R_{\mathcal{F}}}{d}\) 主导。该理论不仅适用于非二分图，还被拓展到了二分图结构。当模型学习优化正交限制映射使得 \(R_{\mathcal{F}}(u, v)\) 降低时，雅可比敏感度上界随之抬升，信息在长程传递过程中的急剧衰减与压缩被有效阻断。

4. FlatNSD 局部消息传递迭代：纯局部机制兑现全局长程抗挤压

在模型落地层面，本文不采用昂贵的全局核方法，而是将平坦滑轮严格实现为标准消息传递层（FlatNSD）。节点更新方程由下式控制：

\[h_v^{(t+1)} = \phi_t\left(h_v^{(t)}, \sum_{u \in N_v} \hat{A}_{uv} \psi_t(h_u^{(t)})\right)\]

其中消息函数简化为局部线性正交变换 \(\psi_t(h_u) = -\mathcal{F}_u h_u\)（结合权重矩阵），而在更新函数 \(\phi_t\) 中施加转置变换 \(\mathcal{F}_v^{\top}\)。限制映射由轻量级局部图卷积（如 GraphSAGE 骨干）端到端生成。这种构造使 FlatNSD 完全保留了局部稀疏图卷积的高效性与线性复杂度，同时凭借正交约束隐式协同全局滑轮电阻下降。

实验关键数据¶

主实验¶

主实验在专门评估长程信息流与过挤压的合成基准 ECHO-Synth 以及图分类基准（Enzymes, IMDB, Mutag, Proteins）上全面对比了 FlatNSD 与经典图重连算法（SDRF, FOSR, BORF, DR, GTR, LASER, GOKU）及图变换器模型。

表 1 展示了在 ECHO-Synth 拓扑任务上的长程属性预测平均绝对误差（MAE）：

数据集/任务	指标	FlatNSD-SAGE	CSNN (并发SOTA)	GCN	GPS (图变换器)	提升/领先
ECHO-Synth (ecc)	MAE ↓	3.138 ± 0.052	4.527 ± 0.022	5.233 ± 0.034	4.758 ± 0.021	相比次优降低 30.7%
ECHO-Synth (sssp)	MAE ↓	0.198 ± 0.082	0.044 ± 0.036	2.102 ± 0.094	0.472 ± 0.050	相比 GCN 降低 90.6%
ECHO-Synth (diam)	MAE ↓	1.132 ± 0.095	1.001 ± 0.068	3.832 ± 0.262	2.160 ± 0.098	相比 GCN 降低 70.5%

消融与分析实验¶

为了验证茎空间维度（Stalk Dimension \(d\)）与限制映射参数化网络对缓解过挤压的影响，论文在二叉树匹配任务 TreeNeighborsMatch 以及图分类任务上进行了消融分析。

表 2 展示了不同骨干网络、茎空间维度及消融配置在长程匹配与分类任务上的表现：

配置 / 变体	树匹配准确率 (r=8)	图分类相对平均增益	阻抗-准确率相关性 (Spearman)	说明
FlatNSD-SAGE (\(d=4\))	100.0% (25步收敛)	+23.05%	-0.82 (强负相关)	完整模型：高维正交映射协同低电阻与高精度
FlatNSD-SAGE (\(d=2\))	100.0% (143步收敛)	+18.42%	-0.45 (中等负相关)	维度受限：收敛变慢，限制映射优化空间受阻
FlatNSD-MLP (\(d=4\))	12.5%	+5.12%	-0.15 (弱相关)	去除 SAGE 结构感知映射后，无法学到最优滑轮
经典 GCN 基线 (\(d=1\))	3.1%	基线 (0.00%)	不适用 (常数拓扑电阻)	无滑轮结构，深层严重挤压致使长程信息归零
平凡滑轮 (全恒等映射)	4.5%	-1.20%	不适用 (达到最大滑轮电阻)	理论验证：平凡滑轮无法降低电阻，依然崩溃

关键发现¶

茎空间维度决定优化自由度：将茎空间维度从 \(d=2\) 提升到 \(d=4\)，不仅大幅加快了树匹配任务的收敛速度（步数由 143 缩短至 25），而且使得各网络层间的滑轮有效电阻与训练准确率呈现更稳定的强负相关性。
滑轮电阻与预测精度严格负相关：在 TreeNeighborsMatch、Graph Transfer 及真实图分类基准中，斯皮尔曼相关系数均显示总滑轮有效电阻的下降伴随着准确率的稳步上升，且与雅可比敏感度负相关趋势高度吻合，强力印证了理论机制。
同时兼顾过平滑与过挤压：狄利克雷能量（Dirichlet Energy）监测表明，FlatNSD 在学习降低滑轮有效电阻以克服过挤压的同时，保持了显著高于普通 GCN 的狄利克雷能量，从理论与实验两方面打破了传统重连“减挤压必增平滑”的困境。

亮点与洞察¶

拓扑瓶颈的代数重定位视角：传统工作认为通信瓶颈是图几何结构的固有缺陷，只能靠重连边来弥补；本文首次从理论上证明瓶颈可以通过赋予图合适的细胞滑轮结构并在正交纤维丛中调整限制映射来解构。
纯局部计算驱动全局电阻下降：FlatNSD 仅依赖稀疏邻域聚合与本地生成的正交矩阵，运行复杂度与普通 GNN 一致，却能隐式引导全图有效电阻下降，兼具了高表现力与极低推理时延。
打破挤压与平滑的内在张力：通过在特征信道中引入正交相位旋转（而非添加旁路边），模型能够在不使相邻节点特征趋同的前提下扩宽通信带宽，为深层 GNN 架构设计提供了全新思路。

局限与展望¶

限制映射对生成骨干的依赖性：实验表明使用简单 MLP 参数化正交映射时模型难以学到电阻最优滑轮，必须依赖 GraphSAGE 等具备结构聚合能力的子网络，增加了超参数调试的复杂度。
正交群表达能力的上界：为了保证计算可控性，模型限制在平坦正交群 \(O(d)\)，无法表达非正交或有向滑轮中的非对称信息流动，在处理复杂有向图任务时仍有扩展空间。
未来方向：探索定义在滑轮流形上的离散曲率度量（如滑轮 Ricci 曲率），建立滑轮曲率与滑轮有效电阻之间的微分几何联系，进一步发展自适应图拓扑-代数混合增强技术。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出滑轮有效电阻概念，将代数拓扑结构与 GNN 过挤压敏感度雅可比边界严密联结。
实验充分度: ⭐⭐⭐⭐⭐ 覆盖控制合成树、长程拓扑、异质图分类以及真实图分类，辅以雅可比相关性与干预消融。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严密清晰，几何直觉形象，问题阐述与实验论证逻辑连贯。
价值: ⭐⭐⭐⭐⭐ 为解决 GNN 基础通信瓶颈提供了免改图拓扑的全新理论工具与高效可复用的通用设计范式。