What Can We Learn from State Space Models for Machine Learning on Graphs - Abstract

Aug 5, 2026

Machine learning on graphs enables broad real-world applications, yet Message Passing Neural Networks (MPNNs) remain limited in expressiveness and struggle with long-range dependencies. Graph transformers mitigate these issues via global attention, but incur substantial computational overhead on large graphs. State Space Models (SSMs) offer an efficient replacement for full attention in sequential modeling by combining RNN- and CNN-like strengths, including long-range capability and strong generalization. Extending SSMs to graphs is challenging because graphs lack a canonical node order. This work introduces Graph State Space Convolution (GSSC), preserving SSM advantages through permutation-equivariant set aggregation and factorizable graph kernels using relative node distances. Experiments show provably stronger expressiveness than MPNNs in counting substructures and improved results on 6 of 11 benchmarks.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages23

Reading Time58 min

AccessFree to download

Introduction

Limits of MPNNs on graphs

Graph transformers and computational cost

Motivation for State Space Models

Extending SSMs to graph-structured data

Proposed Method: Graph State Space Convolution

WHAT CAN WE LEARN FROM STATE SPACE MODELS FOR MACHINE LEARNING ON GRAPHS? Yinan Huang∗ Georgia Institute of Technology [yhuang903@gatech.edu](yhuang903@gatech.edu) Siqi Miao∗ Georgia Institute of Technology [siqi.miao@gatech.edu](siqi.miao@gatech.edu) arXiv :2406 .058 15v2 [ cs .LG] 4 Oct 2024 Pan Li Georgia Institute of Technology [panli@gatech.edu](panli@gatech.edu) ABSTRACT Machine learning on graphs has recently found extensive applications across domains. However, the commonly used Message Passing Neural Networks (MPNNs) suffer from limited expressive power and struggle to capture long-range dependencies. Graph transformers offer a strong alternative due to their global attention mechanism, but they come with great computational overheads, especially for large graphs. In recent years, State Space Models (SSMs) have emerged as a compelling approach to replace full attention in transformers to model sequential data. It blends the strengths of RNNs and CNNs, offering a) efficient computation, b) the ability to capture long-range dependencies, and c) good generalization across sequences of various lengths. However, extending SSMs to graph-structured data presents unique challenges due to the lack of canonical node ordering in graphs. In this work, we propose Graph State Space Convolution (GSSC) as a principled extension of SSMs to graph-structured data. By leveraging global permutation-equivariant set aggregation and factorizable graph kernels that rely on relative node distances as the convolution kernels, GSSC preserves all three advantages of SSMs. We demonstrate the provably stronger expressiveness of GSSC than MPNNs in counting graph substructures and show its effectiveness across 11 real-world, widely used benchmark datasets. GSSC achieves the best results on 6 out of 11 datasets with all significant improvements compared to the state-of-the-art baselines and second-best results on the other 5 datasets. Our findings highlight the potential of GSSC as a powerful and scalable model for graph machine learning. Our code is available at [https://github.com/Graph-COM/GSSC](https://github.com/Graph-COM/GSSC). 1 INTRODUCTION Machine learning for graph-structured data has numerous applications in molecular graphs (Duvenaudet al., 2015; Wang et al., 2021), drug discovery (Xiong et al., 2021; Stokes et al., 2020), and social networks (Fan et al., 2019; Guo & Wang, 2020) . In recent years, Message Passing Neural Networks (MPNNs) have been arguably the most popular neural architecture for graphs (Kipf & Welling, 2016; Fung et al., 2021; Velikovi et al., 2018; Xu et al., 2018; Corso et al., 2020; Zhou et al., 2020), but they also suffer from many limitations, including restricted expressive power (Xu et al., 2018; Morris et al., 2019), over-squashing (Di Giovanni et al., 2023; Topping et al., 2022; Nguyen et al., 2023), andover-smoothing (Rusch et al., 2023; Chen et al., 2020a; Keriven, 2022) . These limitations could harm the models’ performance. For example, MPNNs cannot capture long-range dependencies (Dwivediet al., 2022) or detect subgraphs like cycles that are important in forming ring systems of molecular graphs (Chen et al., 2020b) . Adapted from the vanilla transformer in sequence modeling (Vaswani et al., 2017), graph transformers have attracted growing research interests because they may alleviate these fundamental limitations of ∗Equal contribution, listed in alphabetical order MPNNs (Kreuzer et al., 2021; Kim et al., 2022; Rampášek et al., 2022; Chen et al., 2022a; Dwivedi & Bresson, 2020) . By attending to all nodes in the graph, graph transformers are inherently able to capture long-range dependencies. However, the global attention mechanism ignores graph structures and thus requires incorporating positional encodings (PEs) of nodes (Rampášek et al., 2022) that encode graph structural information. For example, the information of relative distance between nodes has been leveraged in attention

FAQs

Why do message passing neural networks (MPNNs) have limitations for graph machine learning?

They offer limited expressive power and tend to miss long-range dependencies, and they can also fail to capture certain substructures important for downstream tasks.

How do graph transformers address some MPNN shortcomings, and what is their drawback?

Graph transformers use global attention to capture long-range dependencies, but their full attention computation scales poorly, creating heavy computational overhead on large graphs.

What is Graph State Space Convolution (GSSC) and how does it extend state space models to graphs?

GSSC adapts SSM ideas to graph-structured data by using permutation-equivariant set aggregation and factorizable graph kernels based on relative node distances, enabling SSM advantages without relying on a canonical node ordering.

Aug 5, 2026

Upload by Valentina