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

• RelGNN: Composite Message Passing for Relational Deep Learning [56.48834369525997]
  We introduce RelGNN, a novel GNN framework specifically designed to capture the unique characteristics of relational databases. At the core of our approach is the introduction of atomic routes, which are sequences of nodes forming high-order tripartite structures. RelGNN consistently achieves state-of-the-art accuracy with up to 25% improvement.
  arXiv  Detail & Related papers  (2025-02-10T18:58:40Z)
• Contextual Reinforcement in Multimodal Token Compression for Large Language Models [0.0]
  token compression remains a critical challenge for scaling models to handle increasingly complex and diverse datasets. A novel mechanism based on contextual reinforcement is introduced, dynamically adjusting token importance through interdependencies and semantic relevance. This approach enables substantial reductions in token usage while preserving the quality and coherence of information representation.
  arXiv  Detail & Related papers  (2025-01-28T02:44:31Z)
• DeltaGNN: Graph Neural Network with Information Flow Control [5.563171090433323]
  Graph Neural Networks (GNNs) are designed to process graph-structured data through neighborhood aggregations in the message passing process. Message-passing enables GNNs to understand short-range spatial interactions, but also causes them to suffer from over-smoothing and over-squashing. We propose a mechanism called emph information flow control to address over-smoothing and over-squashing with linear computational overhead. We benchmark our model across 10 real-world datasets, including graphs with varying sizes, topologies, densities, and homophilic ratios, showing superior performance
  arXiv  Detail & Related papers  (2025-01-10T14:34:20Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs) This framework provides a standardized setting to evaluate GNNs across diverse datasets. We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• Verbalized Graph Representation Learning: A Fully Interpretable Graph Model Based on Large Language Models Throughout the Entire Process [8.820909397907274]
  We propose a verbalized graph representation learning (VGRL) method which is fully interpretable. In contrast to traditional graph machine learning models, VGRL constrains this parameter space to be text description. We conduct several studies to empirically evaluate the effectiveness of VGRL.
  arXiv  Detail & Related papers  (2024-10-02T12:07:47Z)
• Towards Graph Prompt Learning: A Survey and Beyond [38.55555996765227]
  Large-scale "pre-train and prompt learning" paradigms have demonstrated remarkable adaptability. This survey categorizes over 100 relevant works in this field, summarizing general design principles and the latest applications.
  arXiv  Detail & Related papers  (2024-08-26T06:36:42Z)
• 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)
• 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)
• 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)

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.