From Message-Passing to Linearized Graph Sequence Models
Joël Mathys, Basil Rohner, Saku Peltonen, Roger Wattenhofer · 2026
Read From Message-Passing to Linearized Graph Sequence Models by Joël Mathys, Basil Rohner, Saku Peltonen, Roger Wattenhofer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-12358.txt.
Introduction
Mathys and three colleagues recast graph learning as sequence modelling, borrowing the rapid progress of sequence architectures. Their Linearized Graph Sequence Models separate how deep the computation runs from how far information travels across the graph, turning core graph design choices into sequence design choices. The paper studies, in theory and in tests, which sequence properties preserve the graph's built-in bias toward local structure. Results show improved handling of long-range information tasks, offering a principled bridge between graph and sequence methods.
Catalog record
| CREATOR | Joël Mathys, Basil Rohner, Saku Peltonen, Roger Wattenhofer |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80730 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.12358
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
From Message-Passing to Linearized Graph Sequence Models Joël Mathys, Basil Rohner, Saku Peltonen, Roger Wattenhofer Abstract Message-passing based approaches form the default backbone of most learning architectures on graph-structured data. However, the rapid progress of modern deep learning architectures in other domains, particularly sequence modeling, raises the question of how graph learning can benefit from these advances. We introduce Linearized Graph Sequence Models, a framework that recasts message-passing graph computation from the perspective of sequence modeling to simplify architectural choices. Our approach systematically separates the computational processing depth from the information propagation depth, allowing core graph architectural decisions to be treated as sequence modeling choices. Specifically, we analyze, both empirically and theoretically, what sequence properties make methods effective for learning and preserving the graph inductive bias. In particular, we validate our findings, demonstrating improved performance on long-range information tasks in graphs. Our findings provide a principled way to integrate modern sequence modeling advances into message-passing based graph learning. Beyond this, our work demonstrates how the separation of processing and information depth can recast central architectural questions as input modeling choices. † † affiliationnotice: Equal contribution 1 Introduction Message-passing neural networks (MPNNs) ( 16 ) have emerged as the dominant architecture for learning on graph-structured data, achieving remarkable success by iteratively aggregating information from local neighborhoods. To incorporate sufficient information from distant nodes in the graph, this sequential aggregation scheme must be repeated many times, resulting in deep networks. Unfortunately, as network depth increases, fixed-sized node embeddings have to keep track of an ever-expanding, exponentially growing receptive field, which ultimately leads to information loss and the collapse of learned representations ( 2 ; 3 ; 12 ) . Moreover, these phenomena are closely related to the difficulty of properly optimizing deep networks due to vanishing gradients ( 5 ) . Meanwhile, modern deep learning has witnessed rapid architectural innovation, particularly in sequence modeling, where Transformers ( 43 ) and State-Space Models ( 11 ) excel at capturing complex long-range dependencies while maintaining computational efficiency and hardware-friendly designs. This raises the question how graph learning can benefit from architectural advances in modern sequence modeling without losing the inductive bias which makes GNNs effective. Figure 1 : LGSM decouples information propagation (horizontal) from non-linear processing (vertical). Unlike MPNNs that advance both dimensions simultaneously, LGSM enables information to flow across the graph through linearized computation before applying non-linear transformations. This shifts graph architectural focus to the impact of the input sequences. Adapting modern sequence modeling techniques for graph learning is not straightforward due to the question on how best to preserve the graph modality and its inductive biases. One line of work attempts to directly model graphs as sequences by casting the graph itself into a sequence based representation. This includes graph transformers ( 30 ; 37 ; 40 ) that model nodes as tokens, or sequence extraction through random walks ( 42 ; 6 ; 28 ; 44 ; 8 ) . Often these approaches struggle to fully preserve graph inductive biases and rely on auxiliary message-passing mechanisms or graph positional encodings to retain necessary structural information ( 19 ) . An alternative direction focuses on the unrolled computation of message-passing neural networks itself, viewing the iterative updates as a sequential process. These include more sophisticated aggregation schemes ( 13 ) that leverage modern sequence models, focusing on the recurrent update and their ability to retain information over a prolonged time while maintaining trainability ( 5 ) or casting the architecture directly as a sequence first process ( 7 ; 15 ) . However, particularly the latter requires stacking their derived modules sequentially, reintroducing the very problem of accumulated non-linearities that limits the depth and optimization. In this work, we introduce Linearized Graph Sequence Models (LGSM), a framework that formulates message-passing based graph learning from the perspective of sequence modeling by explicitly decoupling two dimensions of computation: information depth, how information propagates through the graph, and processing depth, how many non-linear transformations are applied. In standard MPNNs, these two dimensions are tightly intertwined: each sequential layer propagates information one hop further and applies a transformation. LGSM separates these aspects by viewing the unrolled computation of message-passing as a sequence. Crucially, we linearize the computation along the sequence, both ensuring information flow and enabling efficient parallel computation through modern SSM implementations such as Mamba ( 22 ) . This allows core architectural decisions in graph learning to be reframed as sequence modeling choices. We analyze the computation within LGSM and directly relate the sensitivity of node embeddings ( 12 ) to the design of the input sequence. This naturally leads to the question of what makes a sequence extraction mechanism effective for graph learning. We study both empirically and theoretically how the choice of sequence affects important properties such as stability, sensitivity, or influence, and how they can be improved. Motivated by these insights, we propose a sequence extraction method based on non-backtracking message exchange, which reduces the broadcasting of already known information. We further validate our framework empirically on the ECHO and LRIM benchmark ( 34 ; 31 ) on both synthetic graph property prediction tasks as well as real-world molecular datasets, where LGSM achieves strong performance, demonstrating that the separation of information and processing depth is an effective framework for graph learning. Our main contributions are as follows: • We introduce Linearized Graph Sequence Models (LGSM), a framework that decouples information propagation depth from processing depth and allows to recast core message-passing architectural decisions as sequence modeling choices instead. • We provide a thorough theoretical analysis connecting the choice of sequence extraction to node sensitivity and information flow, establishing how different extraction mechanisms impact learning on graphs. Further, we propose to use a sequence extraction method based on non-backtracking walks with favorable properties for information propagation. • We empirically validate our framework, confirming the effectiveness of our approach on both synthetic graph tasks as well as real-world molecular datasets. 2 Background 2.1 Notation Let \mathcal{G}=(\mathcal{V},\mathcal{E}) be an undirected graph with vertex set \mathcal{V} and edge set \mathcal{E} , where |\mathcal{V}|=n and |\mathcal{E}|=m denote the number of nodes and edges in the graph. The degree of a node v is \deg(v) and \mathcal{N}^{\leq k}(v) denotes the set of all neighbors of v within distance k . Similarly, we denote with \mathcal{N}^{k}(v) the set of nodes for which there exists a path of length exactly k . We use \mathbf{A}_{\mathcal{G}}\in\mathbb{R}^{n\times n} to denote the adjacency matrix defined by (\mathbf{A}_{\mathcal{G}})_{u,v}=1 if and only if \{u,v\}\in\mathcal{E} . The degree matrix \mathbf{D}_{\mathcal{G}} is diagonal with (\mathbf{D}_{\mathcal{G}})_{v,v}=\deg(v) . We denote a multiset with \{\!\!\{\cdot\}\!\!\} . For a matrix A\in\mathbb{R}^{n\times n} , \|A\|=\max_{\|v\|_{2}=1}\|Av\|_{2} denotes the spectral norm, unless otherwise specified. 2.2 Graph Neural Networks Graph Neural Networks that are based on message-passing ( 16 ) learn node representations through iterative neighborhood aggregation. Given initial node features \mathbf{H}^{(0)}=\mathbf{X}\in\mathbb{R}^{d\times n} , each layer t updates the node representations by aggregating information from neighbors, while also applying a learnable transformation: \displaystyle\mathbf{h}_{v}^{(t+1)}=\sigma\left(\mathbf{h}_{v}^{(t)},\varphi\left(\{\!\!\{\mathbf{h}^{(t)}_{u}:u\in\mathcal{N}(v)\}\!\!\}\right)\right), where \varphi is a permutation-invariant aggregation function (e.g., sum, mean) and \sigma is a learnable non-linear function, typically an MLP. For many common architectures, such as GCN ( 29 ) , the update can be expressed in matrix notation. \mathbf{H}^{(t+1)}=\sigma\left(\mathbf{H}^{(t)}\mathbf{A}_{\mathcal{G}}\right) Here,