Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching

• URL: http://arxiv.org/abs/2312.16560v2
• Date: Wed, 20 Mar 2024 10:10:33 GMT
• Title: Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching
• Authors: Federico Errica, Henrik Christiansen, Viktor Zaverkin, Takashi Maruyama, Mathias Niepert, Francesco Alesiani,
• Abstract summary: Long-range interactions are essential for the correct description of complex systems in many scientific fields. Most deep graph networks cannot really model long-range dependencies due to intrinsic limitations of (synchronous) message passing. This work proposes a general framework that learns to mitigate these limitations.
• Score: 23.487431014596556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Long-range interactions are essential for the correct description of complex systems in many scientific fields. The price to pay for including them in the calculations, however, is a dramatic increase in the overall computational costs. Recently, deep graph networks have been employed as efficient, data-driven surrogate models for predicting properties of complex systems represented as graphs. These models rely on a local and iterative message passing strategy that should, in principle, capture long-range information without explicitly modeling the corresponding interactions. In practice, most deep graph networks cannot really model long-range dependencies due to the intrinsic limitations of (synchronous) message passing, namely oversmoothing, oversquashing, and underreaching. This work proposes a general framework that learns to mitigate these limitations: within a variational inference framework, we endow message passing architectures with the ability to freely adapt their depth and filter messages along the way. With theoretical and empirical arguments, we show that this simple strategy better captures long-range interactions, by surpassing the state of the art on five node and graph prediction datasets suited for this problem. Our approach consistently improves the performances of the baselines tested on these tasks. We complement the exposition with qualitative analyses and ablations to get a deeper understanding of the framework's inner workings.

Related papers

• Topological Neural Networks: Mitigating the Bottlenecks of Graph Neural Networks via Higher-Order Interactions [1.994307489466967]
  This work starts with a theoretical framework to reveal the impact of network's width, depth, and graph topology on the over-squashing phenomena in message-passing neural networks. The work drifts towards, higher-order interactions and multi-relational inductive biases via Topological Neural Networks. Inspired by Graph Attention Networks, two topological attention networks are proposed: Simplicial and Cell Attention Networks.
  arXiv  Detail & Related papers  (2024-02-10T08:26:06Z)
• TimeGraphs: Graph-based Temporal Reasoning [64.18083371645956]
  TimeGraphs is a novel approach that characterizes dynamic interactions as a hierarchical temporal graph. Our approach models the interactions using a compact graph-based representation, enabling adaptive reasoning across diverse time scales. We evaluate TimeGraphs on multiple datasets with complex, dynamic agent interactions, including a football simulator, the Resistance game, and the MOMA human activity dataset.
  arXiv  Detail & Related papers  (2024-01-06T06:26:49Z)
• Multi-Scene Generalized Trajectory Global Graph Solver with Composite Nodes for Multiple Object Tracking [61.69892497726235]
  Composite Node Message Passing Network (CoNo-Link) is a framework for modeling ultra-long frames information for association. In addition to the previous method of treating objects as nodes, the network innovatively treats object trajectories as nodes for information interaction. Our model can learn better predictions on longer-time scales by adding composite nodes.
  arXiv  Detail & Related papers  (2023-12-14T14:00:30Z)
• Network Alignment with Transferable Graph Autoencoders [79.89704126746204]
  We propose a novel graph autoencoder architecture designed to extract powerful and robust node embeddings. We prove that the generated embeddings are associated with the eigenvalues and eigenvectors of the graphs. Our proposed framework also leverages transfer learning and data augmentation to achieve efficient network alignment at a very large scale without retraining.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• CIN++: Enhancing Topological Message Passing [3.584867245855462]
  Graph Neural Networks (GNNs) have demonstrated remarkable success in learning from graph-structured data. They face significant limitations in expressive power, struggling with long-range interactions and lacking a principled approach to modeling higher-order structures and group interactions. We propose CIN++, an enhancement of the topological message passing scheme introduced in CINs.
  arXiv  Detail & Related papers  (2023-06-06T10:25:10Z)
• Taming Local Effects in Graph-based Spatiotemporal Forecasting [28.30604130617646]
  Stemporal graph neural networks have shown to be effective in time series forecasting applications. This paper aims to understand the interplay between globality and locality in graph-basedtemporal forecasting. We propose a methodological framework to rationalize the practice of including trainable node embeddings in such architectures.
  arXiv  Detail & Related papers  (2023-02-08T14:18:56Z)
• TIDE: Time Derivative Diffusion for Deep Learning on Graphs [31.01454180524729]
  A prominent paradigm for graph neural networks is based on the message-passing framework. In this framework, information communication is realized only between neighboring nodes. We present a novel method based on time derivative graph diffusion (TIDE) to overcome these structural limitations.
  arXiv  Detail & Related papers  (2022-12-05T18:42:55Z)
• 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)
• Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
  A dataset of inter-dependent signals is defined as a matrix whose columns demonstrate strong dependencies. A neural network is employed to act as structure prior and reveal the underlying signal interdependencies. Deep unrolling and Deep equilibrium based algorithms are developed, forming highly interpretable and concise deep-learning-based architectures.
  arXiv  Detail & Related papers  (2022-03-29T21:00:39Z)
• Learning Long-term Visual Dynamics with Region Proposal Interaction Networks [75.06423516419862]
  We build object representations that can capture inter-object and object-environment interactions over a long-range. Thanks to the simple yet effective object representation, our approach outperforms prior methods by a significant margin.
  arXiv  Detail & Related papers  (2020-08-05T17:48:00Z)

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.