DRew：带有延迟的动态重连消息传递

消息传递神经网络（Message Passing Neural Networks, MPNNs）已被证实存在“过度挤压”（over-squashing）现象，该现象导致其在依赖长程相互作用的任务中表现不佳。这一问题主要源于消息传递仅在节点的局部邻域内进行，即仅限于相邻节点之间的信息交换。一些重连（rewiring）方法试图通过使图结构“更连通”来提升性能，从而更适用于长程任务，但这类方法通常会破坏图结构中固有的距离归纳偏置（inductive bias），因为在每一层中，远距离节点之间都实现了瞬时通信。本文提出一种通用框架，可应用于任意MPNN架构，通过执行与层相关的重连策略，实现图结构的渐进式稠密化。此外，我们还引入一种延迟机制（delay mechanism），允许节点间根据其所在层及相互距离建立跳跃连接（skip connections）。我们在多个长程任务上对所提方法进行了验证，结果表明，该方法在性能上优于图注意力网络（graph Transformers）和多跳MPNNs。