🤖 machine learning

Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges

本文通过总结其公式化表达、对缓解方法进行分类、分析其与表达能力及过度平滑的关系、回顾经验基准，并概述未来研究的开放性挑战，对图神经网络中的过度挤压问题进行了全面的阐述。

原作者： Dai Shi, Andi Han, Lequan Lin, Yi Guo, Junbin Gao

发布于 2026-08-17

📖 1 分钟阅读☕ 轻松阅读

原作者： Dai Shi, Andi Han, Lequan Lin, Yi Guo, Junbin Gao

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一个计算机通过与邻居交谈来学习的世界。这就是**图神经网络（Graph Neural Networks, GNNs）**的核心——这是一个将数据视为社交网络的分支人工智能领域。GNN 不仅仅是观察单张照片或一组数字，它观察的是事物是如何连接在一起的。把 GNN 想象成一个试图通过倾听朋友发言来理解复杂话题的学生。如果这个学生只和坐在旁边的同学说话，他们能学到很多关于即时课堂的内容。但如果他们需要理解从教室后排传来的悄悄话，他们就必须让信息沿线传递下去：“嘿，告诉下一个人……”

在这个数字版的“传声筒”游戏中，网络将信息从一个节点传递到另一个节点（从一个人传给另一个人）。目标是让每个节点都能收集到足够的上下文信息，从而做出明智的决策。然而，这里有一个陷阱。如果信息必须传递得太远，或者如果太多人试图把他们的故事挤进一张小小的纸条里，原始含义就会被压碎。信息会变成一团模糊、无法分辨的浆糊。这种由于长距离信息被挤压进一个微小且无用的数据包而导致的问题，科学家称之为过度挤压（Over-squashing）。这就像试图把一座巨大图书馆的全部历史塞进一张便利贴里；细节消失了，计算机也因此变得困惑。

这篇题为《论 GNN 的过度挤压问题》（Exposition on Over-squashing Problem of GNNs）的论文，是为那些试图解决这个“便利贴问题”的研究人员编写的一本庞大的指南手册。作者 Dai Shi 及其团队扮演着侦探的角色，他们收集了迄今为止所有的线索、理论和尝试过的解决方案。他们不仅指出了问题，还整理了这些混乱。他们解释了过度挤压发生的具体原因，对人们尝试解决问题的不同方式进行了分类，并且最重要的一点是，他们承认我们目前还没有一把完美的尺子来衡量过度挤压到底有多严重。他们绘制出了战场地图，向我们展示了哪些武器有效，哪些可能会适得其反，以及谜团仍然存在于何处。

信息的伟大挤压

要理解这篇论文，你首先需要想象这种“挤压”。在深度神经网络中，信息通过许多层进行传输。想象一条信息从一条长而窄的走廊的一端开始移动。随着它沿着线路向下移动，它必须经过一系列越来越窄的门。当它到达尽头时，信息已经被压缩得如此紧密，以至于很难辨认出它最初说了什么。论文在数学上将其定义为过度挤压（OSQ）得分。它衡量了一个节点的最终理解在多大程度上依赖于一个远处节点的初始信息。如果得分很低，说明连接断裂了；远处节点的声音太微弱，无法被听到。

作者解释说，这不仅仅是一个理论上的担忧。它的发生是由图本身的形状决定的。有些图具有“瓶颈”——连接两个繁忙大岛屿的狭窄桥梁。当信息试图穿过这些桥梁时，就会发生拥堵。论文强调，虽然我们有很好的方法来衡量另一个被称为“过度平滑”（Over-smoothing，即所有人的声音听起来都一样）的问题，但衡量过度挤压要困难得多。这就像试图测量在一场飓风中丢失了多少特定的耳语；我们有一些工具，比如有效电阻（Effective Resistance）（一个借鉴自电学的概念，衡量电流在两点之间流动的难易程度）和通勤时间（Commute Time）（一个随机游走者从 A 到 B 再回到 A 所需的时间），但它们只是上界，并不是完美的尺子。

三大家族解决者

这篇论文最大的贡献在于将各种修复过度挤压的尝试组织成了三个截然不同的家族。把它们想象成三种不同的拓宽那条狭窄走廊的策略。

1. 空间重构者（局部建筑师）
这些方法观察图的局部形状，并尝试在瓶颈处建造新的桥梁。它们使用了一个叫做**曲率（Curvature）**的概念。在几何学中，曲率告诉你一个表面是向内弯曲还是向外弯曲。在图中，“负曲率”边就像是连接两个拥挤岛屿的狭窄桥梁。作者解释说，这些负曲率桥梁正是导致挤压的元凶。

修复方案： 这些方法，如 SDRF 和 SJLR，会识别出这些狭窄的桥梁并添加额外的边来拓宽它们。它们也可能移除“正曲率”边（这些边就像拥挤且冗余的环路），以防止信息变得过于浑浊（过度平滑）。
代价： 这是一种微妙的平衡。如果你添加了太多的桥梁，图就会变得过于密集，每个人都开始和所有人交谈，从而导致过度平滑。论文指出，虽然这些方法有效，但它们的计算成本很高，就像是在汽车仍在行驶时重新设计城市的交通地图一样。

2. 谱重构者（全局规划师）
当空间团队关注局部邻域时，谱团队则从远处观察图的“氛围”。他们使用与图的谱间隙（Spectral Gap）（衡量整个图连接程度的一个指标）相关的数学知识。

修复方案： 这些方法，例如 FOSR 和 GOKU，试图优化图的全局结构。它们添加边的目的是改善整个网络的信息流，而不一定专注于某个特定的瓶颈。它们希望确保图的“声音”在各处都能清晰共鸣。
代价： 有时，在试图修复全局流动时，它们可能会无意中破坏局部邻域结构。这就像是把高速公路拓宽得太宽，以至于通往高速公路的小巧温馨的小街都被吞噬了。

3. 隐式重构者（魔术师）
这是最令人着迷的一组。这些方法实际上并不改变图的结构，而是改变了信息如何传输。

修复方案： 想象一个信使，他不仅能在走廊里行走，还能瞬间移动，或者能携带关于他走过的每一步的“记忆”。像图 Transformer（Graph Transformers）这样的方法使用“注意力机制”让每个节点都能直接与所有其他节点交谈，从而有效地绕过了瓶颈。其他方法，如扩散模型（Diffusion models），让信息像热量或水一样扩散，自然地填补空白。有些甚至使用“虚拟节点（Virtual Nodes）”，它们充当中心枢纽，在不物理添加边的前提下连接图的遥远部分。
代价： 虽然功能强大，但这些方法对计算资源的要求很高。此外，由于它们不改变可见的图，有时很难解释它们为什么有效。

伟大的权衡与缺失的尺子

论文最重要的见解之一是权衡（Trade-off）。作者指出，修复过度挤压往往会使过度平滑变得更严重，反之亦然。这是一个跷跷板。如果你添加过多的连接来解决挤压，你就有可能让所有人都听起来一样。如果你修剪掉过多的连接以保持差异性，你就有可能丢失长距离的消息。论文建议，最好的方法是那些能够走好这条钢丝绳的方法，例如通过使用“曲率”来准确知道在哪里加桥，在哪里筑墙。

然而，论文以一种诚实的不确定性结束。尽管有所有这些聪明的策略，我们仍然缺乏一种完美的、通用的方式来衡量过度挤压。我们拥有上界（估计情况可能有多糟），但我们没有一个精确的数字来告诉我们究竟丢失了多少信息。作者认为，如果没有一把更好的尺子，很难判断一种新方法是真的更好，还是仅仅运气好。他们还指出，目前用于证明这些方法有效的许多“测试”数据集其实太简单了；它们依赖于局部信息，并没有真正测试长距离处理能力。他们呼吁建立新的、更严苛的基准测试，迫使 AI 真正展现其长距离处理的实力。

开放性问题

最后，论文为未来的研究留下了一系列谜题。

多深才算够深？ 我们知道增加层数有助于消息传播得更远，但最终它们会被挤压。是否存在一个完美的层数？
这些方法真的有效吗？ 一些研究表明，这些重构方法的“魔力”可能仅仅是参数调优的结果，而非方法本身。我们需要确保这一点。
超图（Hypergraphs）又如何？ 大多数这项工作都是针对标准图的。但如果连接更加复杂，比如三个人同时进行的群聊呢？论文暗示，过度挤压在超图中可能更加严重，我们需要新的工具来修复它。

总之，这篇论文是一张复杂景观的地图。它告诉我们，过度挤压是一个真实存在的、顽固的问题，限制了基于图的 AI 的智能化程度。它展示了人们解决该问题的三条主要路径，警告了其中的陷阱（如与过度平滑的权衡），并承认我们仍需更好的工具来衡量我们的进步。这是对下一代研究人员的行动召唤：去建造更好的尺子，设计更智能的桥梁，并最终让信息在数字世界中自由流动。

技术总结：关于图神经网络（GNN）过度挤压（Over-squashing）问题的阐述

1. 问题陈述

本文探讨了图神经网络（GNN）中的**过度挤压（Over-squashing, OSQ）问题，特别是在消息传递神经网络（MPNN）中。尽管 MPNN 在节点和图级任务中取得了成功，但在处理需要节点对之间存在长程依赖（long-range dependencies）**的任务时却表现不佳。

OSQ 现象发生在随着网络深度的增加，来自远处节点的丰富信息被压缩进固定大小的特征向量时。这种压缩是由图的连通性和 MPNN 架构引起的，导致产生了一个“瓶颈”，使得来自远端节点的消息发生畸变或丢失。与过度平滑（Over-smoothing, OSM）——即节点特征变得难以区分——不同，OSQ 特指模型由于信息畸变而无法维持对长程交互的学习准确性。

识别出的关键挑战包括：

量化问题： 不同于可以通过狄利克雷能量（Dirichlet energy）测量的 OSM，OSQ 缺乏具体的数值度量。现有的界限（例如 Jacobian 范数）通常是上界，并不一定反映“实际”的 OSQ 行为。
基准测试： 许多标准数据集（如 ZINC, ogbg-molpcba）严重依赖局部信息，因此不适合验证 OSQ 的缓解效果。论文指出，尽管**长程图基准测试（Long Range Graph Benchmark, LRGB）**是为此目的设计的，但目前仍未得到充分利用。

2. 方法论与框架

本文对 OSQ 问题进行了系统的阐述，对现有解决方案进行了分类，并分析了它们的理论与实证属性。

A. 公式化与界限

作者使用 OSQ 分数对 OSQ 进行了形式化定义，该分数定义为第 $\ell$ 层节点的表示与另一个节点初始特征之间的 Jacobian 矩阵的谱范数（ $\|\frac{\partial h^{(\ell)}_i}{\partial x_s}\|$ ）。

界限： 该分数受拓扑指标的约束。
- 局部界限： 与归一化邻接矩阵的幂次（ $\hat{A}^{r+1}$ ）相关。
- 全局界限： 与**有效电阻（Effective Resistance, $R_{i,s}$ ）和通勤时间（Commute Time, $Com(i,s)$）**相关。较低的有效电阻意味着更好的连通性和更少的挤压。
表达能力： OSQ 与模型的“混合能力（mixing power）”相关联，即从不同节点混合特征的能力。高混合能力与低 OSQ 相关。

B. 缓解策略的分类

论文将目前的缓解方法分为三类：

空间重连（Spatial Rewiring）：
- 机制： 通过基于拓扑指标（主要是 Ricci 曲率：Ollivier-Ricci, Forman, Balanced Forman, Jost-Liu）添加或删除边，在局部修改图结构。
- 逻辑： 高度负曲率的边充当瓶颈（导致 OSQ），而高度正曲率的边则会导致 OSM。诸如 SDRF（随机离散 Ricci 流）和 SJLR 等方法通过在负曲率区域添加边并移除正曲率区域的边来处理。
- 权衡： 使图稠密化可以缓解 OSQ，但存在加剧 OSM 的风险。
谱重连（Spectral Rewiring）：
- 机制： 优化全局图扩张属性，例如谱间隙（spectral gap）、总有效电阻或通勤时间。
- 逻辑： 诸如 FOSR（一阶谱重连）等方法通过最大化谱间隙来提高全局连通性，而不一定在局部增加图的密度。**扩张图传播（Expander Graph Propagation, EGP）**利用 Cayley 图提供补充连通性。
- 权衡： 改善了长程连通性，但可能会削弱局部保持能力。
隐式重连（Implicit Rewiring）：
- 机制： 不显式修改输入图，而是通过传播机制本身创建更稠密或替代的通信通道。
- 示例：
  - 基于扩散的模型： GRAND 和 BLEND 等模型使用注意力机制或热扩散来动态增加连接密度。
  - Transformer 类： Graphormer 和 Difformer 对所有节点对分配注意力（全局感受野），从而有效地绕过拓扑瓶颈。
  - 虚拟节点： S2GNN 和 IPR-MPNN 等方法引入虚拟节点或谱滤波器，以促进不同簇之间信息的流动。
  - 多轨道传播： 将特征传播分离到不同的轨道（例如按标签或中心性），以防止导致挤压的信息混合。

C. 实证策略

论文回顾了用于验证这些方法的基准测试：

合成图： Dumbbell 图、Ring-of-cliques 以及 RingTransfer 数据集，旨在测试长程信息传递。
现实世界基准： 引用网络（Cora, Citeseer）和分子数据集（ZINC, QM9）。
长程基准（LRGB）： PascalVOC-SP, COCO-SP, Peptide-func 等，这些数据集专门要求捕捉长程交互。
复杂度分析： 论文总结了这些方法的计算复杂度，指出基于曲率的方法通常涉及高昂的预处理成本（ $O(|E|d_{max}^2)$ 或更高），而谱方法和隐式方法在每层成本与预计算之间各不相同。

3. 主要贡献

统一阐述： 论文综合了 OSQ 的各种公式化表达，将 Jacobian 敏感性、有效电阻和通勤时间整合到一个连贯的理论框架中。
分类法： 系统地将缓解策略分为空间、谱和隐式重连，并强调了它们之间的联系与权衡。
理论见解：
- 建立了 OSQ 与 MPNN 表达能力（混合能力）之间的关系。
- 讨论了 OSQ 与 OSM 的权衡，指出缓解其中一个往往会加剧另一个（例如，使图稠密化有助于 OSQ 但不利于 OSM）。
- 利用拓扑指标提供了 OSQ 分数的界限。
实证综述： 总结了用于验证这些方法的基准测试现状，指出了许多研究中缺乏合适数据集以及 LRGB 未被充分利用的问题。同时，它还提供了现有方法计算复杂度的详细表格。

4. 结果与发现

曲率局限性： 最近的研究表明，基于曲率重连（如 SDRF）带来的实证收益可能并不总是与识别瓶颈的理论标准一致，且超参数调优往往起着重要作用。
虚拟节点： 理论分析（引理 2）表明，添加一个连接到所有其他节点的虚拟节点会降低社区间节点的通勤时间，从而在理论上缓解 OSQ。
隐式方法： 虽然并非总是被明确界定为 OSQ 的解决方案，但像 Graph Transformer 和扩散模型这样的方法本质上创建了更稠密的连通性，从而提供了对 OSQ 的鲁棒性。
复杂度： 方法的有效性与其计算成本之间存在明显的张力。基于曲率的方法计算成本通常很高，而谱方法则需要特征分解或近似计算。

5. 意义与开放问题

该论文声称其意义在于为 OSQ 提供了严谨的公式化与界限、对缓解策略进行了全面概述，并对理论与实证挑战进行了批判性讨论。它旨在通过识别以下开放问题来指导未来的研究：

测量问题： 建立 OSQ 分数（Jacobian 敏感性）可靠的下界仍然是一个开放性问题。目前的文献大多仅提供上界。
OSQ 与 OSM 的权衡： 需要对过度挤压与过度平滑之间的权衡建立统一的理论理解。论文提出了一个类似于物理学中“不确定性原理”的类比。
深度问题： 如何确定捕获长程依赖所需的最佳层数而不引发 OSM，目前尚未解决。
方法等价性： 空间重连与谱重连方法之间的关系（例如，空间重连如何影响谱间隙）尚未完全明晰。
超图： 将 OSQ 分析扩展到超图是未来的必要方向。
实证隔离： 开发能够从 OSM 及其他因素（如梯度消失）中实证隔离出 OSQ 效应的协议，对于公平评估至关重要。

总之，本文作为一项基础性综述，推动了该领域从对 OSQ 的零散观察向结构化理论与实证研究的转变，强调了对更好的基准测试、统一的定义以及对 GNN 设计中固有权衡进行更深层理解的需求。