Graph Mamba: Towards Learning on Graphs with State Space Models
Top Cited Papers
Open Access
- 24 August 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 119-130
Abstract
Graph Neural Networks (GNNs) have shown promising potential in graph representation learning. The majority of GNNs define a local message-passing mechanism, propagating information over the graph by stacking multiple layers. These methods, however, are known to suffer from two major limitations: over-squashing and poor capturing of long-range dependencies. Recently, Graph Transformers (GTs) emerged as a powerful alternative to Message-Passing Neural Networks (MPNNs). GTs, however, have quadratic computational cost, lack inductive biases on graph structures, and rely on complex Positional Encodings (PE). In this paper, we show that while Transformers, complex message-passing, and PE are sufficient for good performance in practice, neither is necessary. Motivated by the recent success of State Space Models (SSMs), we present Graph Mamba Networks (GMNs), a framework for a new class of GNNs based on selective SSMs. We discuss the new challenges when adapting SSMs to graph-structured data, and present four required steps to design GMNs, where we choose (1) Neighborhood Tokenization, (2) Token Ordering, (3) Architecture of SSM Encoder, and (4) Local Encoding. We provide theoretical justification for the power of GMNs, and experimentally show that GMNs attain an outstanding performance in various benchmark datasets. The code is available in this link.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks2022
- Global Self-Attention as a Replacement for Graph Convolution2022
- Simplifying approach to node classification in Graph Neural NetworksJournal of Computational Science, 2022
- FirmCore Decomposition of Multilayer Networks2022
- Swin Transformer: Hierarchical Vision Transformer using Shifted Windows2021
- Random Features Strengthen Graph Neural Networks2021
- A Comprehensive Survey on Graph Neural NetworksIEEE Transactions on Neural Networks and Learning Systems, 2020
- Weisfeiler and Leman Go Neural: Higher-Order Graph Neural NetworksProceedings of the AAAI Conference on Artificial Intelligence, 2019
- Graph Neural Networks for Social Recommendation2019
- A measure of centrality based on network efficiencyNew Journal of Physics, 2007