🤖 machine learning

Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Survey

本综述全面回顾了旨在通过修改图拓扑以增强信息传播从而缓解图神经网络中过度挤压和过度平滑挑战的图重连技术，涵盖其理论基础、实现方式及性能权衡。

原作者： Hugo Attali, Nathalie Pernelle, Davide Buscaldi, Fragkiskos D. Malliaros

发布于 2026-05-05

📖 1 分钟阅读☕ 轻松阅读

原作者： Hugo Attali, Nathalie Pernelle, Davide Buscaldi, Fragkiskos D. Malliaros

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

想象一下，你正试图在一个挤满人的嘈杂房间里传递一条秘密消息。在人工智能领域，特别是**图神经网络（GNN）**中，“人”是数据点（如网络中的节点），而它们之间的“握手”则是允许它们共享信息的连接（边）。

本文是一篇关于一种名为**图重连（Graph Rewiring）**的新策略的综述（大型综述）。不妨将其视为人工智能的“房间重组者”。这种方法不仅仅是教导人工智能如何更好地交流，而是物理上改变房间的布局，使沟通变得更加顺畅。

以下是他们所要解决的问题及其提供的解决方案的分解说明，并辅以简单的类比。

两大核心问题：“挤压”与“模糊”

该论文指出了这些人工智能模型有时无法学习长距离连接的两个主要原因：

1. 过度挤压（The "Squeeze"）
想象一条狭窄的走廊，100 个人正试图将秘密 whispered 给走廊尽头的那个人。随着消息在人群中传递，它被挤压成微小的、压缩的低语。当消息到达尽头时，细节已经丢失。

在人工智能术语中： 当来自遥远节点的信息试图到达中心节点时，它被压缩进一个固定大小的内存槽中。人工智能会忘记遥远节点的具体细节，因为连接它们的少数路径上“交通”过于拥堵。

2. 过度平滑（The "Blur"）
想象一群人围成一圈，不断地与邻居混合他们的油漆桶。如果他们这样做的时间过长，最终，每个人的油漆都会变成完全相同的浑浊棕色。你再也无法分辨谁原本是红色、蓝色或绿色。

在人工智能术语中： 随着人工智能在邻居之间来回传递信息，每个节点独特的“身份”被冲刷殆尽。它们开始看起来都一样，使得人工智能无法将它们区分开来。

解决方案：图重连

与其强迫人工智能在一个布局破碎的房间里工作，图重连直接改变房间本身。它添加新的捷径或移除令人困惑的死胡同，以帮助消息更好地流动。

该论文将这些“房间重组者”分为三种主要风格：

1. 结构修复（The Architect，架构师）

这种方法仅关注连接的形状，而忽略人们穿着什么（它们的数据特征）。它利用数学来寻找“瓶颈”（狭窄的走廊）和“死胡同”。

工作原理： 它使用诸如曲率（衡量连接有多“崎岖”）或电阻（衡量从 A 到 B 有多困难）等工具。
类比： 如果架构师看到一条太窄的走廊（高电阻），他们会敲掉一堵墙以创造一扇新门。如果他们看到一个房间里人们混合油漆过于拥挤（高正曲率），他们会移除一些连接以停止混合。
优缺点： 这种方法非常合乎逻辑且易于理解，但计算成本可能很高（速度慢），有时需要大量的“微调”（超参数）才能将门的位置安排得恰到好处。

2. 特征感知修复（The Matchmaker，红娘）

这种方法在重组房间之前，会先观察人们是谁（它们的数据特征）。

工作原理： 它会问：“这两个人实际上有什么共同点吗？”如果两个遥远的节点拥有非常相似的数据（比如两个穿着相同颜色衬衫的人），人工智能可能会在它们之间画一条新线，即使它们最初并没有连接。
类比： 红娘不仅仅是看走廊，而是观察客人。如果两个客人穿着匹配的服装，却位于房间的两侧，红娘会在他们之间建立一座直接桥梁，以便他们能立即交谈。
优缺点： 这通常效果更好，因为它使用了更多信息，但更难解释人工智能为何做出特定改变。这就像说“我移动墙壁是因为颜色匹配”，这比“我移动墙壁是因为走廊太窄”要抽象一些。

3. 虚拟节点（The Central Hub，中央枢纽）

有时，房间实在太大。

工作原理： 这种方法添加一个“超级节点”（像一个中央扩音器或主开关），它连接到所有人。
类比： 与其在巨大的体育场里人与人地传递消息，不如让每个人都向中央广播员低语，然后广播员将消息喊给其他人。这极大地缩短了信息需要传播的距离。

我们如何知道它有效？

该论文认为，我们不应仅仅关注最终测试分数（人工智能是否得出了正确答案？）。我们需要检查房间本身的“健康状况”：

我们是否解决了瓶颈？（走廊是否变宽了？）
我们是否阻止了油漆混合？（颜色是否仍然 distinct？）
消息传播得更快了吗？（“通勤时间”是否缩短了？）

结论

这篇综述得出结论，图重连是一个强大的工具，但它并非适用于所有情况的“万能魔杖”。

如果你的数据充满噪声或连接很弱，关注特征（节点是谁）会有所帮助。
如果你的数据很干净但结构糟糕，关注几何结构（连接的形状）会有所帮助。
作者警告说，我们需要小心，不要仅仅为了在某个特定数据集上获得幸运的胜利而“调整”设置。我们需要理解为什么新的布局有助于人工智能学习。

简而言之：不要只教导人工智能更好地说话；要修复房间，以便对话能够真正发生。

技术摘要：图神经网络中的图重连以缓解过挤压与过平滑

1. 问题陈述

图神经网络（GNN）虽然在从图结构数据中学习方面表现出色，但面临两个关键局限性，这些局限性会损害性能，特别是在异配图（heterophilic graphs）和涉及长程依赖的任务中：

过挤压（Over-Squashing）： 当来自远端节点的信息被过度压缩到固定大小的节点表示中时，就会发生这种现象。当图拓扑结构迫使许多不同的长程信号通过少量路径（结构瓶颈）传递时，就会产生过挤压，导致远端节点的雅可比（Jacobian）敏感度随距离迅速衰减。
过平滑（Over-Smoothing）： 当重复的消息传递导致节点表示变得无法区分时，就会发生这种情况。随着层数加深，聚合过程类似于扩散过程，逐渐减少节点嵌入之间的差异，直到它们坍缩为同质状态。

这两个问题都源于消息传递算子与输入图拓扑之间的相互作用。虽然现有的解决方案包括边重加权（这仍受限于原始图的支持）和多跳聚合（由于图稠密化，这可能会加剧过挤压并加速过平滑），但这些方法通常无法从根本上改变连接结构以促进高效的长程信息流。

2. 方法论：图重连

本文综述了图重连（graph rewiring），这是一类显式修改图拓扑（ $G \to G^+$ ）以促进信息传播，同时减弱诱导过度混合或压缩的结构模式的方法。

2.1 核心定义

重连操作被定义为映射 $R: G \to G^+$ ，其中 $G^+ = (V^+, E^+)$ 是修改后的图。这可以是：

静态的： 在训练前应用一次。
动态的： 在训练过程中基于可学习参数演化（ $G^+ = R_\theta(G)$ ）。
其目标是获得一种比原始图更有利于消息传递神经网络（MPNN）的拓扑结构。

2.2 拓扑与连通性度量

重连策略依赖特定指标来识别瓶颈并指导结构修改：

离散曲率（Discrete Curvature）： 衡量局部结构分散度。
- Ollivier 曲率： 基于邻域上概率测度之间的最优传输（Wasserstein 距离）。
- Forman 曲率（增强型/平衡型）： 结合三角形和各种长度循环的组合度量。
- Jost-Liu 曲率： 利用局部聚类（三角形）细化基于边的度量。
- 作用： 高度负曲率通常指示瓶颈（过挤压），而高度正曲率可能指示冗余的局部混合（过平滑）。
有效电阻（Effective Resistance）： 考虑所有不相交路径的两个节点之间连通性的全局度量。高电阻指示瓶颈；低电阻指示通信顺畅。
基于随机游走的度量： 通过通勤时间（随机游走往返节点所需的期望步数）或游走计数来量化连通性。连接游走越少，过挤压风险越高。
谱间隙（Spectral Gap）： 与 Cheeger 常数及拉普拉斯矩阵的第二小特征值（ $\lambda_2$ ）相关。小的谱间隙指示近乎不连通的组件（瓶颈）。

2.3 重连策略

本文根据结构修改、信号源和效率对方法进行分类：

A. 结构修复式重连（Structural-Fix Rewiring）

这些方法仅基于拓扑描述符（ $S_G$ ）修改图，不使用节点特征或标签。

基于曲率的方法： 根据曲率阈值添加或删除边。高度负曲率的边（瓶颈）通过添加捷径来桥接；高度正曲率的边（冗余团簇）被移除以防止过平滑。
基于电阻的方法： 迭代地在具有高有效电阻的节点对之间添加边，以最小化全局电阻。
基于游走的方法： 在连接游走较少（低 $\Omega_k$ ）的节点对之间添加边，以增加路径多样性。
谱间隙方法： 构建具有最大化谱间隙的图（例如扩张子图），以确保快速混合且无瓶颈。
虚拟节点： 用辅助节点（例如“主节点”或分形节点）增强图，这些节点连接到原始节点的子集，以创建多尺度捷径，从而减小直径和有效电阻。

B. 特征感知重连（Feature-Aware Rewiring）

这些方法利用节点属性来指导重连，这在观测到的拓扑结构存在噪声或与任务不对齐时至关重要。

几何方法： 在特征空间中利用 Delaunay 三角剖分重建图（例如 DR, TRIGON），以强制实施任务相关的连通性，同时避免负曲率。
特征相似性： 基于特征亲和力（例如余弦相似度）对边的添加/删除进行排序，通常受社区结构约束（例如 ComFy）。
谱对齐： 通过将邻接矩阵的特征向量与节点特征的奇异向量对齐，强制图拓扑与特征几何之间的一致性（例如 JDR）。

3. 主要贡献与综述范围

本文提供了以方法为中心的先进重连方法综述，通过与以往综述（例如仅关注过挤压的综述）区分开来，具有以下特点：

全面分类： 按结构算子、信息源（结构 vs. 特征）和计算权衡系统地组织方法。
理论基础： 明确将重连技术与过挤压的数学形式化（雅可比敏感度衰减）和过平滑（渐近坍缩）联系起来。
权衡的关键分析：
- 归因： 结构修复式方法对性能提升归因于拓扑变化的因果归因更清晰，而特征感知方法可能会将拓扑改进与特征建模混淆。
- 超参数敏感性： 许多结构方法（例如基于曲率的方法）对编辑预算和阈值高度敏感，通常需要有利的配置才能显示出增益。
- 计算复杂度： 曲率和有效电阻的计算可能呈二次或三次方缩放，而基于游走或谱的近似方法为大型图提供了更好的可扩展性。

4. 评估与结果

本文强调，重连不应仅根据下游准确性进行评估。相反，它提倡采用多维评估协议：

结构级诊断： 验证重连后的图 $G^+$ 是否确实降低了有效电阻、通勤时间，或将曲率分布从诱导瓶颈的值移开。
模型级诊断： 测量长程敏感性的改进（例如通过基于雅可比的方法）。
基准测试： 性能通常在异配数据集和长程交互基准上进行验证，在这些场景中标准 GNN 表现不佳。
基线： 比较应包括与图无关的基线（例如 DeepSets），以区分关系收益与仅特征效应，以及匹配预算的控制组（例如随机重连），以确保收益不仅仅是由于边数增加所致。

5. 意义与未来方向

本文认为，图重连代表了一种干预图结构以改进学习的原则性方法。其意义在于将焦点从纯粹的建筑结构变化转移到修改传播基质本身。

确定的未来方向：

结构与特征的相互作用： 阐明何时需要重连，何时特征侧机制足以进行长程学习，以及如何在匹配约束下将它们结合起来。
泛化与稳定性： 利用结构代理（例如度异质性、谱属性）来预测拓扑何时会损害泛化，指导重连以控制传播放大，而不仅仅是优化准确性。
严格的评估： 转向更清晰的问题表述和评估协议，使不同设置下的主张更加稳健、可比较且可解释。

作者总结道，该领域的进步将取决于更明确的假设和评估协议，这些协议能够稳健地将性能提升归因于特定的拓扑干预。