DRew: Dynamically Rewired Message Passing with Delay

• URL: http://arxiv.org/abs/2305.08018v2
• Date: Thu, 18 May 2023 12:41:56 GMT
• Title: DRew: Dynamically Rewired Message Passing with Delay
• Abstract summary: We propose a framework 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.
• Score: 7.474662887810221
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Inference-Time Graph Engineering for Multi-Agent LLM Workflows [51.56038180639833]
  We introduce ReActNet, a training-free framework that compiles a query and a set of role-specialized agents into a sequence of directed communication graphs.<n>We show that ReActNet consistently improves over fixed-topology and learned-topology baselines while maintaining competitive inference cost.
  arXiv  Detail & Related papers  (2026-09-04T23:32:11Z)
• Asynchronous Message Passing for Addressing Oversquashing in Graph Neural Networks [21.49824162847618]
  Graph Neural Networks (GNNs) suffer from Oversquashing, which occurs when tasks require long-range interactions.<n>We propose an efficient model-agnostic framework that asynchronously updates node features, unlike traditional synchronous message passing GNNs.<n>Our framework is applied to six standard graph datasets and two long-range datasets to perform graph classification.
  arXiv  Detail & Related papers  (2025-09-08T15:03:05Z)
• Improving the Effective Receptive Field of Message-Passing Neural Networks [17.98720458446544]
  We show and theoretically explain the limited Effective Receptive Field problem in MPNNs.<n>We propose an Interleaved Multiscale Message-Passing Neural Networks architecture to address these problems.<n>Our method incorporates a hierarchical coarsening of the graph, enabling message-passing across multiscale representations.
  arXiv  Detail & Related papers  (2025-05-29T07:23:07Z)
• Graph Spring Neural ODEs for Link Sign Prediction [49.71046810937725]
  We propose a novel message-passing layer architecture called Graph Spring Network (GSN) modeled after spring forces. We show that our method achieves accuracy close to the state-of-the-art methods with node generation time speedup factors of up to 28,000 on large graphs.
  arXiv  Detail & Related papers  (2024-12-17T13:50:20Z)
• Towards Dynamic Message Passing on Graphs [104.06474765596687]
  We propose a novel dynamic message-passing mechanism for graph neural networks (GNNs) It projects graph nodes and learnable pseudo nodes into a common space with measurable spatial relations between them. With nodes moving in the space, their evolving relations facilitate flexible pathway construction for a dynamic message-passing process.
  arXiv  Detail & Related papers  (2024-10-31T07:20:40Z)
• Preventing Representational Rank Collapse in MPNNs by Splitting the Computational Graph [9.498398257062641]
  We show that operating on multiple directed acyclic graphs always satisfies our condition and propose to obtain these by defining a strict partial ordering of the nodes. We conduct comprehensive experiments that confirm the benefits of operating on multi-relational graphs to achieve more informative node representations.
  arXiv  Detail & Related papers  (2024-09-17T19:16:03Z)
• Probabilistic Graph Rewiring via Virtual Nodes [21.273828055299408]
  Message-passing graph neural networks (MPNNs) have emerged as a powerful paradigm for graph-based machine learning. MPNNs face challenges such as under-reaching and over-squashing, where limited receptive fields and structural bottlenecks hinder information flow in the graph. Here, we propose implicitly rewired message-passing neural networks (IPR-MPNNs), a novel approach that integrates implicit probabilistic graph rewiring into MPNNs.
  arXiv  Detail & Related papers  (2024-05-27T16:11:49Z)
• Recurrent Distance Filtering for Graph Representation Learning [34.761926988427284]
  Graph neural networks based on iterative one-hop message passing have been shown to struggle in harnessing the information from distant nodes effectively. We propose a new architecture to reconcile these challenges. Our model aggregates other nodes by their shortest distances to the target and uses a linear RNN to encode the sequence of hop representations.
  arXiv  Detail & Related papers  (2023-12-03T23:36:16Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• DiffWire: Inductive Graph Rewiring via the Lov\'asz Bound [1.0323063834827415]
  Graph Neural Networks (GNNs) have been shown to achieve competitive results to tackle graph-related tasks. MPNNs have been reported to suffer from over-smoothing, over-squashing and under-reaching. We propose DiffWire, a novel framework for graph rewiring in MPNNs that is principled, fully differentiable and parameter-free.
  arXiv  Detail & Related papers  (2022-06-15T08:22:07Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  Graph neural networks (GNNs) rely on the message passing paradigm to propagate node features and build interactions. Recent works point out that different graph learning tasks require different ranges of interactions between nodes. We study two common graph construction methods in scientific domains, i.e., emphK-nearest neighbor (KNN) graphs and emphfully-connected (FC) graphs.
  arXiv  Detail & Related papers  (2022-05-15T11:38:14Z)
• Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
  Graph Neural Networks (GNNs) perform learned message passing over an input graph. We train a deep GNN with up to 100 message passing steps and achieve several state-of-the-art results.
  arXiv  Detail & Related papers  (2021-06-15T08:50:10Z)
• Graph Highway Networks [77.38665506495553]
  Graph Convolution Networks (GCN) are widely used in learning graph representations due to their effectiveness and efficiency. They suffer from the notorious over-smoothing problem, in which the learned representations converge to alike vectors when many layers are stacked. We propose Graph Highway Networks (GHNet) which utilize gating units to balance the trade-off between homogeneity and heterogeneity in the GCN learning process.
  arXiv  Detail & Related papers  (2020-04-09T16:26:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.