DRew: Dynamically Rewired Message Passing with Delay
DRew: Dynamically Rewired Message Passing with Delay
复制标题
DOI：
10.48550/arxiv.2305.08018
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Benjamin Gutteridge;Xiaowen Dong;Michael M. Bronstein;Francesco Di Giovanni
中科院分区：
文献类型：
--
作者：
Benjamin Gutteridge;Xiaowen Dong;Michael M. Bronstein;Francesco Di Giovanni
消息传递神经网络（mpnn）已被证明存在过度压缩现象，导致依赖于远程交互的任务表现不佳。这在很大程度上归因于消息传递只在本地发生，而不是节点的直接邻居。重新布线的方法试图使图“更加连接”，并且更适合于远程任务，通常会失去图上距离提供的归纳偏差，因为它们使远程节点在每层上都能即时通信。在本文中，我们提出了一个适用于任何MPNN体系结构的框架，该框架执行层相关的重新布线以确保图的逐渐致密化。我们还提出了一种延迟机制，允许节点之间根据层和它们的相互距离跳过连接。我们在几个远程任务上验证了我们的方法，并表明它优于图转换器和多跳mpnn。
Message passing neural networks (MPNNs) have been shown to suffer from the phenomenon of over-squashing that causes poor performance for tasks relying on long-range interactions. This can be largely attributed to message passing only occurring locally, over a node's immediate neighbours. Rewiring approaches attempting to make graphs 'more connected', and supposedly better suited to long-range tasks, often lose the inductive bias provided by distance on the graph since they make distant nodes communicate instantly at every layer. In this paper we propose a framework, applicable to any MPNN architecture, that performs a layer-dependent rewiring to ensure gradual densification of the graph. We also propose a delay mechanism that permits skip connections between nodes depending on the layer and their mutual distance. We validate our approach on several long-range tasks and show that it outperforms graph Transformers and multi-hop MPNNs.