通过曲率理解图上的过挤压现象与瓶颈问题

大多数图神经网络（GNNs）采用消息传递范式，即在输入图上传播节点特征。近期研究指出，远距离节点间信息流动的失真现象是限制消息传递在依赖长距离交互任务中效率的一个关键因素。这一现象被称为“过挤压”（over-squashing），以往常被经验性地归因于图结构中的瓶颈区域——随着跳数 $k$ 的增加，$k$-跳邻居的数量迅速增长。本文对 GNN 中的过挤压现象提供了精确的描述，并分析了其在图结构瓶颈中的产生机制。为此，我们引入了一种基于边的组合曲率新定义，并证明了负曲率边是导致过挤压问题的根源。此外，我们提出了一种基于曲率的图重布线方法，并通过实验验证了该方法在缓解过挤压问题上的有效性。