Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling

• URL: http://arxiv.org/abs/2505.18728v1
• Date: Sat, 24 May 2025 14:53:07 GMT
• Title: Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling
• Authors: Andrea Ceni, Alessio Gravina, Claudio Gallicchio, Davide Bacciu, Carola-Bibiane Schonlieb, Moshe Eliasof,
• Abstract summary: We introduce a new perspective by embedding the key principles of modern SSM directly into the Message-Passing Neural Network framework.<n>Our approach, MP-SSM, enables efficient, permutation-equivariant, and long-range information propagation while preserving the architectural simplicity of message passing.
• Score: 19.10832920407789
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The recent success of State-Space Models (SSMs) in sequence modeling has motivated their adaptation to graph learning, giving rise to Graph State-Space Models (GSSMs). However, existing GSSMs operate by applying SSM modules to sequences extracted from graphs, often compromising core properties such as permutation equivariance, message-passing compatibility, and computational efficiency. In this paper, we introduce a new perspective by embedding the key principles of modern SSM computation directly into the Message-Passing Neural Network framework, resulting in a unified methodology for both static and temporal graphs. Our approach, MP-SSM, enables efficient, permutation-equivariant, and long-range information propagation while preserving the architectural simplicity of message passing. Crucially, MP-SSM enables an exact sensitivity analysis, which we use to theoretically characterize information flow and evaluate issues like vanishing gradients and over-squashing in the deep regime. Furthermore, our design choices allow for a highly optimized parallel implementation akin to modern SSMs. We validate MP-SSM across a wide range of tasks, including node classification, graph property prediction, long-range benchmarks, and spatiotemporal forecasting, demonstrating both its versatility and strong empirical performance.

Related papers

• Bridging Expressivity and Scalability with Adaptive Unitary SSMs [4.61803711540329]
  We introduce the Adaptive Unitary State Space Model (AUSSM)- a novel class of SSMs that skew-symmetric, input-dependent recurrence to achieve unitary evolution and high expressive power.<n>Our results demonstrate that adaptive unitary recurrence provides a powerful and efficient algorithmic bias for both symbolic and continuous sequence modeling.
  arXiv  Detail & Related papers  (2025-07-07T17:47:16Z)
• On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages [56.22289522687125]
  Selective state-space models (SSMs) are an emerging alternative to the Transformer.<n>We analyze their expressiveness and length generalization performance on regular language tasks.<n>We introduce the Selective Dense State-Space Model (SD-SSM), the first selective SSM that exhibits perfect length generalization.
  arXiv  Detail & Related papers  (2024-12-26T20:53:04Z)
• GG-SSMs: Graph-Generating State Space Models [18.718025325906762]
  State Space Models (SSMs) are powerful tools for modeling sequential data in computer vision and time series analysis domains.<n>We introduce Graph-Generating State Space Models (GG-SSMs), a novel framework that overcomes these limitations by dynamically constructing graphs based on feature relationships.<n>We validate GG-SSMs on 11 diverse datasets, including event-based eye-tracking, ImageNet classification, optical flow estimation, and six time series datasets.
  arXiv  Detail & Related papers  (2024-12-17T00:07:29Z)
• Deep Learning-based Approaches for State Space Models: A Selective Review [15.295157876811066]
  State-space models (SSMs) offer a powerful framework for dynamical system analysis.<n>This paper provides a selective review of recent advancements in deep neural network-based approaches for SSMs.
  arXiv  Detail & Related papers  (2024-12-15T15:04:35Z)
• Recursive Learning of Asymptotic Variational Objectives [49.69399307452126]
  General state-space models (SSMs) are widely used in statistical machine learning and are among the most classical generative models for sequential time-series data. Online sequential IWAE (OSIWAE) allows for online learning of both model parameters and a Markovian recognition model for inferring latent states. This approach is more theoretically well-founded than recently proposed online variational SMC methods.
  arXiv  Detail & Related papers  (2024-11-04T16:12:37Z)
• Mathematical Formalism for Memory Compression in Selective State Space Models [0.0]
  State space models (SSMs) have emerged as a powerful framework for modelling long-range dependencies in sequence data. We develop a rigorous mathematical framework for understanding memory compression in selective state space models. We show that selective SSMs offer significant improvements in memory efficiency and processing speed compared to traditional RNN-based models.
  arXiv  Detail & Related papers  (2024-10-04T05:45:48Z)
• DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs [59.434893231950205]
  Dynamic graph learning aims to uncover evolutionary laws in real-world systems. We propose DyG-Mamba, a new continuous state space model for dynamic graph learning. We show that DyG-Mamba achieves state-of-the-art performance on most datasets.
  arXiv  Detail & Related papers  (2024-08-13T15:21:46Z)
• Longhorn: State Space Models are Amortized Online Learners [51.10124201221601]
  State-space models (SSMs) offer linear decoding efficiency while maintaining parallelism during training. In this work, we explore SSM design through the lens of online learning, conceptualizing SSMs as meta-modules for specific online learning problems. We introduce a novel deep SSM architecture, Longhorn, whose update resembles the closed-form solution for solving the online associative recall problem.
  arXiv  Detail & Related papers  (2024-07-19T11:12:08Z)
• HOPE for a Robust Parameterization of Long-memory State Space Models [51.66430224089725]
  State-space models (SSMs) that utilize linear, time-invariant (LTI) systems are known for their effectiveness in learning long sequences. We develop a new parameterization scheme, called HOPE, for LTI systems that utilize Markov parameters within Hankel operators. Our new parameterization endows the SSM with non-decaying memory within a fixed time window, which is empirically corroborated by a sequential CIFAR-10 task with padded noise.
  arXiv  Detail & Related papers  (2024-05-22T20:20:14Z)
• Unleashing Network Potentials for Semantic Scene Completion [50.95486458217653]
  This paper proposes a novel SSC framework - Adrial Modality Modulation Network (AMMNet) AMMNet introduces two core modules: a cross-modal modulation enabling the interdependence of gradient flows between modalities, and a customized adversarial training scheme leveraging dynamic gradient competition. Extensive experimental results demonstrate that AMMNet outperforms state-of-the-art SSC methods by a large margin.
  arXiv  Detail & Related papers  (2024-03-12T11:48:49Z)
• Theoretical Foundations of Deep Selective State-Space Models [13.971499161967083]
  Deep SSMs demonstrate outstanding performance across a diverse set of domains.<n>Recent developments show that if the linear recurrence powering SSMs allows for multiplicative interactions between inputs and hidden states.<n>We show that when random linear recurrences are equipped with simple input-controlled transitions, then the hidden state is provably a low-dimensional projection of a powerful mathematical object.
  arXiv  Detail & Related papers  (2024-02-29T11:20:16Z)
• State space models can express n-gram languages [51.823427608117626]
  We build state space language models that can solve the next-word prediction task for languages generated from n-gram rules.<n>Our proof shows how SSMs can encode n-gram rules using new theoretical results on their capacity.<n>We conduct experiments with a small dataset generated from n-gram rules to show how our framework can be applied to SSMs and RNNs obtained through gradient-based optimization.
  arXiv  Detail & Related papers  (2023-06-20T10:41:23Z)

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.