🤖 machine learning

Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks

本文提出了一种高效且与模型无关的框架，通过利用中心度引导的异步更新机制取代同步消息传递，来缓解图神经网络中的过度挤压问题，从而实现更有效的长程信息传播，并在图分类基准测试中取得了显著的性能提升。

原作者： Kushal Bose, Swagatam Das

发布于 2026-08-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Kushal Bose, Swagatam Das

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

想象一个城市，其中的每个人只能与他们的直接邻居交谈。如果你想把一条信息从城市的这一端传递到另一端，它必须像接力赛一样，通过一层又一层的传递。在人工智能领域，特别是被称为“图神经网络”的一个分支中，计算机的工作方式与之非常相似。它们通过在相互连接的点之间传递信息，来分析像社交网络或化学分子这样类似于地图的连接数据。对于简单的任务，这种局部的聊天工作得非常完美。但当计算机需要理解两个遥远点之间的关系时——比如分子中一个遥远的原子如何影响其整体形状——系统就会撞上一堵墙。随着信息传播得越来越远，计算机试图将不断增长的信息量挤进一个固定大小的容器中。最终，容器会溢出，细节会被挤压或丢失。这个被称为“过度挤压”（oversquashing）的问题，阻碍了这些智能系统去解决那些需要具备全局视野的复杂谜题。

研究人员曾尝试通过物理上重新布线地图来修复这个问题，即在遥远的点之间添加新的捷径，使信息不必走那么远。另一些人则尝试构建更大的容器来容纳更多信息。然而，这些解决方案通常伴随着代价：它们要么改变了数据的基本性质，要么需要如此庞大的额外计算能力以至于变得不切实际。Kushal Bose 和 Swagatam 最提出的一个新研究提出了另一种方法。他们没有改变地图或容器的大小，而是改变了对话的时机。他们引入了一个名为 CAMP 的系统，全称是“中心性感知异步消息传递”（Centrality-aware Asynchronous Message Passing）。该方法不再让网络中的每个节点都在同一时刻更新其信息，而是以一种特定的、交错的顺序进行更新。

其核心理念基于一个简单的观察：网络中的并非所有点都同样重要。有些节点充当着繁忙的枢纽，连接着许多其他节点，而有些节点则更为孤立。研究人员决定先处理这些枢纽。他们计算了每个节点的“中心性得分”以确定其重要性，然后按重要程度从高到低进行排序。随后，网络被划分为若干组，每组被分配到计算机处理步骤的不同层级中。在第一层，只有最关键的节点会更新其信息。在第二层，次关键的群体进行更新，并利用来自第一组的新鲜数据。这个过程持续进行，直到最不重要的节点轮到它们为止。通过这种交错更新的方式，系统避免了试图一次性压缩海量新信息的瓶颈。信息呈序列化流动，使得固定大小的容器能够处理负载而不会挤压细节。

为了测试这种“时机技巧”是否真的奏效，团队将该方法应用于六个用于训练此类网络的标准数据集，包括化学分子和社交网络，以及两个涉及多肽（一种小型蛋白质链）的专门数据集。他们将这种新的时序系统与两种常见的图神经网络类型相结合，并将结果与使用重构布线或更大容器的现有方法进行了对比。结果令人瞩目。在一个名为 REDDIT-BINARY 的数据集（涉及分类社交网络结构）上，新方法的准确率比标准方法提高了 5%。在一个需要理解分子三维结构的 Peptides-struct 数据集上，性能提升了 4%。这些增益足以让他们的算法在多个测试中位居排行榜前列，其表现往往优于那些改变图结构的复杂技术。

研究人员还探讨了为什么这种方法效果如此之好。他们发现，通过按特定顺序更新节点，系统防止了“平滑”效应——即在网络加深的过程中，不同节点的独特特征最终会变得模糊不清。在标准系统中，随着层级的堆叠，每个节点的独特身份会被冲淡。异步处理方法让信号保持清晰的时间更长，使网络能够维持对图中遥远部分差异的清晰感知。研究表明，当网络需要处理长程交互时，该方法特别有效，而这恰恰是传统系统容易失效的场景。

然而，研究也指出了一项局限性。计算每个节点的重要性得分需要大量的预先工作，特别是对于拥有数百万连接的海量网络。虽然这种预计算对于实验中使用的中等规模图谱来说尚可应付，但作者承认，面对现实世界应用中如全球社交平台那样的大规模网络，他们的方法可能会面临挑战。尽管如此，这项研究结果表明，仅仅改变处理信息的“何时”就可能与改变处理信息的“如何”一样强大。通过让网络中最重要的部分先发言，系统避开了导致信息丢失的交通拥堵，这证明了有时解决复杂问题的最佳方式不是建造更宽的道路，而是更明智地管理交通流量。

技术摘要：用于解决图神经网络中过度挤压问题的异步消息传递

问题陈述
图神经网络（GNNs）面临着一个被称为**过度挤压（oversquashing）**的基本限制，即结构瓶颈阻碍了远距离节点之间的有效消息传播。这种现象发生于：当来自多跳邻居的指数级增长的信息量必须被压缩进固定维度的特征向量时。现有的补救措施具有显著缺陷：

图重连（Graph Rewiring）： 通过添加边（例如快捷路径）来改善连通性的方法改变了原始图的拓扑结构，这可能会损害归纳偏置并导致信息丢失。
特征扩展（Feature Expansion）： 像 PANDA 这样增加高中心性节点特征维度的方法，会增加模型参数，并存在在特征选择过程中丢弃有价值信息的风险。
全局注意力（Global Attention）： 图 Transformer 实现了全局消息传递，但对于大规模图而言，其计算复杂度极高。

方法论：CAMP 框架
作者提出了 CAMP（中心性感知异步消息传递），这是一个与模型无关的框架，旨在不修改图结构或增加参数量的情况下解决过度挤压问题。与所有节点特征在每一层都同时更新的标准同步 GNN 不同，CAMP 采用了异步更新策略：

通过中心性进行节点选择： 框架预先计算节点中心性得分（使用度中心性、介数中心性、紧密中心性、负载中心性或 PageRank 等度量指标）。
逐层划分： 将节点集划分为 $L$ 个不相交的子集，其中 $L$ 是 GNN 的层数。节点的排序（升序或降序）决定了哪个子集被分配到哪一层。
异步更新： 在每一层 $l$ ，只有被分配到的节点子集 $C^{(l)}_n$ 通过聚合其邻居的信息来更新其特征。不在当前批次中的节点保留其来自前一层（或初始化）的特征，并且不参与该特定步骤的聚合。
变跳数聚合： 该机制允许信息进行顺序传播。高中心性节点（潜在的瓶颈）可以根据数据集的信息流向被提前或延迟处理，从而使它们的更新表示能够在后续层中流向低中心性节点，而不会同时饱和固定容量的通道。

理论见解
论文通过理论分析证明，CAMP 通过改变消息传播的敏感度界限来缓解过度挤压。

在同步 GNN 中，敏感度界限随网络深度 $L$ （层数）呈指数级衰减，导致远距离节点的梯度消失。
在 CAMP 中，衰减由节点间的有效异步行走（ $K(s, v)$ ）长度决定，该长度受限于最短路径距离 $d_G(s, v)$ 而非总网络深度 $L$ 。
因此，对于深层网络，CAMP 的界限保持在 $(\alpha\beta)^{d_G(s,v)}$ 以下方，而同步界的界限在 $L \to \infty$ 时趋于零。这种将收缩深度与网络深度解耦的机制是缓解过度挤压的核心原理。

实验结果
该框架在六个标准图分类基准测试（ENZYMES, MUTAG, PROTEINS, COLLAB, IMDB-BINARY, REDDIT-BINARY）和两个长程基准测试（Peptides-func, Peptides-struct）上使用 GCN 和 GIN 骨干网络进行了评估。

性能提升： CAMP 取得了显著的改进，特别是在具有结构瓶颈的数据集上。
- REDDIT-BINARY： 实现了 ~24.5% 的提升（GCN 准确率为 84.96%，而基准为 68.25%）。
- Peptides-struct： 实现了 ~10.2% 的 MAE 降低（0.3138 对比 0.3496 基准）。
- 总体趋势： 在大多数数据集上，CAMP 在不增加模型参数的情况下，表现持续优于或匹配了最先进的重连方法（SDRF, FoSR, BORF, GTR）和特征扩展方法（PANDA）。
过度平滑缓解： 对狄利克雷能量（Dirichlet energy）的分析表明，与重连方法相比，CAMP 在更深的层中保持了更高的能量值，这表明节点特征保持了可区分性，且过度平滑得到了减少。
信号传播： 相对于归一化有效电阻（ $R_{total}$ ），CAMP 展示了更优越的信号传播能力，有效地克服了信息流中的障碍。
中心性敏感度： 最优的中心性度量（如紧密中心性对比 PageRank）和排序（升序对比降序）因数据集而异，这表明选择取决于特定的信息流拓扑（例如树状结构对比基于枢纽的网络）。

意义与局限性
论文声称 CAMP 提供了一种即插即用、与模型无关的解决方案，通过异步更新而非修改结构来管理信息流，从而解决过度挤压问题。其重要性在于：

高效性： 它避免了全局注意力的计算成本和特征扩展的参数开销。
保持归纳偏置： 通过不对图进行重连，它保留了原始的结构归纳偏置。
理论保证： 它为为什么异步更新能防止深层网络中敏感度指数级衰减提供了数学证明。

局限性：
作者承认，由于在预处理阶段计算某些中心性指标（如介数中心性）计算成本高昂，CAMP 目前无法扩展到超大规模图（如 OGB 数据集）。目前的实验局限于中小规模的分子和社交网络图。此外，CAMP 在 Peptides-func 上的表现低于基准，这归因于该任务依赖于局部模体（local motifs）而非长程相互作用，在这种情况下，延迟更新并不能带来收益。

技术摘要：用于解决图神经网络中过度挤压问题的异步消息传递

类似论文