From Message-Passing to Linearized Graph Sequence Models
Joël Mathys 1 * Basil Rohner 1 * Saku Peltonen 1 Roger Wattenhofer 1
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.
σ(·)
+
+
.. .
.. .
.. .
σ(·)
σ(·)
σ(·)
+
σ(·)
+
σ(·)
+
.. . σ(·)
+
σ(·)
+
···
σ(·)
+
+
···
...
+
Processing Depth
arXiv:2605.12358v1 [cs.LG] 12 May 2026
Abstract
σ(·)
+
···
σ(·)
+
Information Depth
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.
nentially growing receptive field, which ultimately leads to information loss and the collapse of learned representations (Alon & Yahav, 2020; Arnaiz-Rodriguez & Errica, 2025; Di Giovanni et al., 2023). Moreover, these phenomena are closely related to the difficulty of properly optimizing deep networks due to vanishing gradients (Arroyo et al., 2025). Meanwhile, modern deep learning has witnessed rapid architectural innovation, particularly in sequence modeling, where Transformers (Vaswani et al., 2017) and State-Space Models (Dao & Gu, 2024) 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.
1. Introduction Message-passing neural networks (MPNNs) (Gilmer et al., 2017) 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, expo-
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
* Equal contribution 1 ETH Zurich, Switzerland. Correspondence to: Joël Mathys <[email protected]>.
Preprint. May 13, 2026.
1
From Message-Passing to Linearized Graph Sequence Models
representation. This includes graph transformers (Ma et al., 2023; Rampasek et al., 2022; Stoll et al., 2025) that model nodes as tokens, or sequence extraction through random walks (Tönshoff et al., 2023; Behrouz & Hashemi, 2024; Kim et al., 2024; Wang & Cho, 2024; Chen et al., 2024). 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 (Grötschla et al., 2026). 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 (Ding et al., 2024) that leverage modern sequence models, focusing on the recurrent update and their ability to retain information over a prolonged time while maintaining trainability (Arroyo et al., 2025) or casting the architecture directly as a sequence first process (Ceni et al., 2025; Eliasof et al., 2025). However, particularly the latter requires stacking their derived modules sequentially, reintroducing the very problem of accumulated non-linearities that limits the depth and optimization.
performance, demonstrating that the separation of information and processing depth is an effective framework for graph learning. Our main contributions are as follows:
In this work, we introduce Linearized Graph Sequence Models (LGSM), a framework that formulates messagepassing 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 (Gu & Dao, 2024). This allows core architectural decisions in graph learning to be reframed as sequence modeling choices.
2. Background
• 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.1. Notation Let G = (V, E) be an undirected graph with vertex set V and edge set E, where |V| = n and |E| = m denote the number of nodes and edges in the graph. The degree of a node v is deg(v) and N ≤k (v) denotes the set of all neighbors of v within distance k. Similarly, we denote with N k (v) the set of nodes for which there exists a path of length exactly k. We use AG ∈ Rn×n to denote the adjacency matrix defined by (AG )u,v = 1 if and only if {u, v} ∈ E. The degree matrix DG is diagonal with (DG )v,v = deg(v). We denote a multiset with {{·}}. For a matrix A ∈ Rn×n , ∥A∥ = max∥v∥2 =1 ∥Av∥2 denotes the spectral norm, unless otherwise specified. 2.2. Graph Neural Networks
We analyze the computation within LGSM and directly relate the sensitivity of node embeddings (Di Giovanni et al., 2023) 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 (Miglior et al., 2025; Mathys et al., 2025) on both synthetic graph property prediction tasks as well as real-world molecular datasets, where LGSM achieves strong
Graph Neural Networks that are based on messagepassing (Gilmer et al., 2017) learn node representations through iterative neighborhood aggregation. Given initial node features H(0) = X ∈ Rd×n , each layer t updates the node representations by aggregating information from neighbors, while also applying a learnable transformation: (t) (t) h(t+1) = σ h , φ { {h : u ∈ N (v)} } , v v u where φ is a permutation-invariant aggregation function (e.g., sum, mean) and σ is a learnable non-linear function, typically an MLP. For many common architectures, such as GCN (Kipf & Welling, 2017), the update can be expressed in matrix notation. H(t+1) = σ H(t) AG 2
From Message-Passing to Linearized Graph Sequence Models
Here, the residual connection to the previous state is modeled as additional self-loops of G. Crucially, each MPNN layer simultaneously propagates information exactly one hop further in the graph and applies a non-linear transformation. To incorporate information from node features at distance r, at least r rounds of message-passing are required, tightly coupling the depth of non-linear processing to the information flow within the graph.
of the aggregation function (Ding et al., 2024), but otherwise do not consider the full architecture. Some works consider SSMs to process the output of sequential non-linear MPNN (Eliasof et al., 2025; Arroyo et al., 2025) or even linearized variants (Ceni et al., 2025). However, they do not consider the separation of processing and information gathering and stack the blocks sequentially. This reintroduces non-linearities and prevents fully parallelizable processing and complete theoretical analysis along the full information depth. We refer to Appendix A for an in depth discussion of related works.
2.3. State-Space Models State-Space Models (SSMs) are formulated to capture continuous linear dynamical systems. In order to apply them for sequence models, one considers a discretization of the system over time, essentially mapping the input sequence x(1) , . . . , x(ℓ) ∈ RdI to an output sequence y(1) , . . . , y(ℓ) ∈ RdO via the linear recurrence
4. Method We propose the Linearized Graph Sequence Model (LGSM) framework, to reformulate message passing based graph learning with a focus on sequence modeling. This perspective explicitly decouples two fundamental dimensions: processing depth, how much compute we spend on transforming information, and information depth, how information propagates throughout the graph. Before presenting our model in detail, we provide a motivating example showing how graph computation can be viewed as unrolled sequence computation.
h(t+1) = Ah(t) + Bx(t+1) y(t+1) = Ch(t+1) where A ∈ RdH ×dH , B ∈ RdH ×dI , and C ∈ RdO ×dH are the system matrices, and h(t) ∈ RdH is the hidden state. Interestingly, instead of naively unrolling the linear recurrence, it can be computed much more efficiently on modern hardware. Either by unrolling the recurrence to give an explicit convolution kernel or alternatively by leveraging the associativity of the update with a parallel scan computation (Gu & Dao, 2024). Moreover, it is possible to switch between the formulation to balance speed and memory requirements during training and inference respectively.
The key observation is that stacking L MPNN layers can be viewed as a recurrent graph update. Consider a GCN-based update rule with skip connection from the input features X, with initial H(0) = 0. Each layer propagates information one hop and then applies a non-linearity. As such, the computational structure resembles that of a recurrent neural network, where the sequence corresponds to successive rounds of neighborhood aggregation. However, unlike standard RNNs that receive an external input at each step, the GCN derives an input implicitly. As we show next, linearizing this recurrence results in a sequence structure.
A key property of modern SSMs is their ability to capture long-range dependencies through appropriate initializations such as the HiPPO framework (Gu et al., 2020; 2021). These enable the SSM to closely approximate the history of the input sequence using orthogonal polynomials. Moreover, with the introduction of Mamba (Gu & Dao, 2024) that incorporates an input dependent selective update, SSMs achieve performances comparable to the transformer architecture.
(t) (t) H(t+1) = σ H , U |{z} |{z} next previous hidden state input H(t+1) = X + σ(H(t) AG )
3. Related Work
RNN formulation
GCN formulation
Where U corresponds to the input sequence of the RNN. We visualize this unrolled computation as a grid in Figure 2a, where the horizontal axis represents information depth and the vertical axis represents processing depth. The MPNN advances both dimensions simultaneously at each step. This leads to a diagonal, staircase-like computational path. Unfortunately, this exhibits two inherent drawbacks. First, the computation has to be done in sequential order, which is hard to parallelize on modern hardware. Second, due to the repeated stacking of non-linearities, it can be hard to properly optimize these networks due to instability or vanishing gradients. Following modern state-space approaches
There exist different lines of work to include modern architectures for graph learning, however, they do differ quite a bit in the modeling perspective. Random walk based approaches, model the graph modality as a collection of sequences (Behrouz & Hashemi, 2024; Chen et al., 2024) and then use the SSM to process the walk sequence. As such, these approaches are orthogonal to our investigation into message-passing centric computation. On the other hand Huang et al. (2024) translates the convolution view of the SSM from linear sequences to graph topologies. Closely related are the approaches that include SSMs in the design 3
From Message-Passing to Linearized Graph Sequence Models
σ(·)
σ(·)
Processing Depth
+
σ(·)
σ(·)
+
σ(·)
+
σ(·)
σ(·)
σ(·)
σ(·)
σ(·)
σ(·)
σ(·)
σ(·)
Information Depth
(a) MPNN
σ(·)
σ(·)
σ(·)
σ(·)
+
σ(·)
σ(·)
Information Depth
σ(·)
+
σ(·)
+
σ(·)
+
σ(·)
+
σ(·)
σ(·)
+
σ(·)
+
+
σ(·)
+
σ(·)
σ(·)
+
σ(·)
+
+
+
+
σ(·)
σ(·)
σ(·)
+
+
+
+
σ(·)
+
σ(·)
σ(·)
+
σ(·)
+
σ(·)
+
+
+
σ(·)
+
σ(·)
σ(·)
+
σ(·)
+
+
σ(·)
+
σ(·)
σ(·)
+
σ(·)
+
σ(·)
+
σ(·)
+
+
σ(·)
+
+
σ(·)
σ(·)
+
+
+
+
+
+
σ(·)
+
σ(·)
σ(·)
σ(·)
+
+
+
+
σ(·)
+
σ(·)
σ(·)
σ(·)
+
+
+
+
σ(·)
+
Processing Depth
σ(·)
+
Processing Depth
+
σ(·)
+
σ(·)
+
Information Depth
(b) Linear MPNN
(c) LGSM (our method)
Figure 2. Visualization of computation in graph neural networks with respect to information depth and processing depth. Standard MPNNs couple both dimensions, propagating and updating information through non-linear transformations at the same time, advancing diagonally. Linear MPNNs propagate information without any non-linearities, but have limited transformation capabilities. Our method, stacks the linearized rows to combine both well-conditioned linear information flow with non-linear processing capabilities.
4.1. Linearized Graph Sequence Model
(Gu et al., 2021), we address these concerns by linearizing the update along the information axis. Removing the nonlinearity, akin to Ceni et al. (2025), allows information to propagate without accumulating non-linear transformations.
H(t+1) = AH(t) + BU(t) =
t X
linearized RNN
We now describe the LGSM architecture in detail. Given an input graph G = (V, E) with node features X ∈ Rd×n , an LGSM transforms these features through four components: sequence extraction, SSM processing, a feed-forward network, and graph mixing. In favor of clarity we omit some of the common optimization techniques such as skip connections and normalizations in the mathematical definition. A conceptual overview is shown in Figure 3.
linearized GCN
Sequence Extraction: The Graph Sequence Encoder gets the input graph with its node features and converts them into a (i) sequence of L node embeddings Sin ∈ Rd×n .
Ak BU(t−k)
k=0
H(t+1) = BX + AH(t) AG =
t X
(0)
(1)
(L−1)
Sin , Sin , . . . , Sin
Ak B XAkG | {z } k=0
= S EQ(X, AG )
U(t−k)
In the next section, we discuss how to extract an appropriate sequence in more detail. A simple choice could be powers (i) of the adjacency matrix: Sin = XAiG .
Where A, B ∈ Rd×d are learnable matrices. Through this lens, the linearized MPNN is equivalent to applying an SSM to a graph-based input sequence, where each sequence element contains node features propagated through the graph: UL:0 = X, XAG , XA2G , . . . , XAL G . In the grid of Figure 2b, this corresponds to only traversing the horizontal axis, information flows through the graph without any non-linear transformations. We use this perspective to build our framework. Similarly to the architectural design of modern SSMs, we stack multiple such linearized horizontal blocks on top of each other and connect them with non-linear transformations along the processing depth. The resulting model architecture depicted in Figure 2c now precisely separates information and processing depth.
SSM Layer: The sequence is then processed by a statespace model, which operates independently on each node’s sequence. We use Mamba2 (Dao & Gu, 2024) as the SSM module. The node dimension is viewed as a batch dimension and the SSM processes L sequence elements of dimension d. (0)
(1)
(L−1)
SSSM , SSSM , . . . , SSSM
(0)
(1)
(ℓ)
= SSM(Sin , Sin , . . . , Sin )
This enables information to flow along the sequence dimension efficiently via parallel scan computation. Afterwards, each node embedding is fed through a feed-forward network σ1 for non-linear processing. (i)
(i)
SFFN = σ1 (SSSM ) 4
From Message-Passing to Linearized Graph Sequence Models
Graph Mixing: Finally, to have information mixing between different nodes, we update the sequence elements with the graph-propagated features of the preceding element before we apply another FFN and feed the output to the next block. Note that because the previous state is mixed between nodes this does not further increase the information depth. (0)
(0)
(i)
(i)
(i−1)
SMIX = σ2 SFFN + SFFN AG
SMIX = SFFN
Output
Graph Decoder
n×d
Add & Norm
A complete LGSM model stacks D such blocks, where the output of one block becomes the input to the next. The final node representations are obtained from the last sequence (ℓ) element Sout and passed to a graph decoder to predict node or graph level embeddings.
Graph Mixing (0)
(1)
SFFN
The linearization along the information depth provides flexibility in how computation is performed. The only location, where the sequence elements all depend on each other is within the SSM module. Note, that efficient SSM implementations give the option to compute row-wise, using efficient and fast parallel scans processing the entire sequence length at once. Alternatively, the computation can be unrolled column-wise, processing all nodes for a given sequence position before advancing to the next. This allows for flexibility and balancing memory and speed depending on hardware constraints and sequence length.
SFFN
···
(L−1)
SFFN
Add & Norm FFN
D× (0)
(1)
SSSM
SSSM
···
(L−1)
SSSM
Add & Norm SSM (0)
(1)
Sin
Sin
···
(L−1)
Sin
5. Theoretical Evaluation n×L×D
In this section, we analyze the LGSM architecture to understand how its computation makes use of the information depth. For traditional MPNNs, prior work by Di Giovanni et al. (2023) gives an upper bound for local node sensitivity:
Graph Sequence Encoder
n×d
Input (m)
∂hv
(0) ∂hu
≤ (cσ wp)m (Sm r,a )vu , | {z } | {z } model
Figure 3. Overview of the LGSM architecture. The Graph Sequence Encoder converts graph input into a sequence. Then, each block applies an SSM for each node along the sequence dimension with additional non-linear transformations and graph mixing. The number of stacked blocks controls the processing depth while the length of the sequence controls information depth.
topology
where Sr,a := cr I + ca A ∈ Rn×n is the graph shift operator and cσ , w, p are parameters of the models non-linearity. For nodes at least distance d apart, this bound implies that sensitivity decays with d. We now characterize sensitivity for LGSM. Consider a single LGSM block with sequence length L. We quantify the dependence of the final output embedding yv on the input feature xw .
respectively, and that A is normal with spectral radius ρ(A) ≈ 1. Then, for any vertex v ∈ V: (L)
∂Sout ∂xv
Theorem 5.1 (Local Sensitivity for 1-Block LGSM). Consider a 1-block LGSM of sequence length L with an SSM defined by system matrices (A, B, C). Denote the input (L) and output features by X, Sout ∈ Rn×d , respectively, where xv = (X)v,: , is the feature vector of vertex v ∈ V. Suppose that the FNNs σSSM , σMIX are µSSM - and µMIX -regular,
≤γ
L L−1 (k) X X ∂S(k) ∂Sin in + γ∥AG ∥ ∂xv ∂xv
k=0
k=0
where γ is a constant in ∥B∥, ∥C∥, µSSM , and µMIX . The bound reveals two complementary mechanisms which are at play. The first term (weighted by AG ) captures sensi5
From Message-Passing to Linearized Graph Sequence Models ∂s(k)
tivity through graph mixing, which propagates information between nodes via the adjacency structure. The second term captures sensitivity through the SSM dynamics, which processes the sequence regardless of graph topology. Therefore, the SSM ensures that there is a direct sensitivity contribution between the nodes that depends on the initial extracted sequence. This ensures sensitivity is maintained as long as there is at least one sequence element j which is sufficiently dependent on the pair v, w ∈ V so that
∂s(j) v ∂xw
weighted sum over ∂xvw . Crucially, it suffices for at least one sequence element to capture strong interaction between the nodes to effectively capture dependencies between them. This motivates a more systematic analysis of what properties make a sequence extraction mechanism effective for graph learning. In the following, we identify five desirable properties for effective sequences:
is large.
• Efficiency The sequence should be computable through preprocessing or have an efficient nonsequential formulation that leverages modern hardware. This is to avoid sequence extraction becoming a bottleneck for the overall architecture.
We extend our analysis to the full LGSM model with stacked blocks. For clarity, we present the bound without graph mixing here. For the complete bound and proof we refer to the Appendix. Note that the graph mixing component only contributes additional gradient flows, thus improving the bound in Theorem 5.2.
• Stability Sequence elements should be numerically bounded to avoid destabilizing the computation, particularly as sequence length increases.
Theorem 5.2 (Local Sensitivity for LGSM). Consider a D-block LGSM without graph mixing layers and of sequence length L, with an SSM defined by system matrices (A, B, C). Denote the input and output features by (L,D) X, Sout ∈ Rn×d , respectively, where xv = (X)v,: , is the feature vector of vertex v ∈ V. Suppose that the FFN σSSM is µSSM -regular and that A is normal with spectral radius ρ(A) ≈ 1. Then, for any vertex v ∈ V: (L,D)
∂Sout ∂xv
• Informativeness Each sequence element should contain meaningful information and be sufficiently distinct from other elements. • Sensitivity For any pair of nodes v, w ∈ V the node ∂s(k)
sensitivity ∂xvw should be greater than zero for at least one sequence element k.
L (k,1) X L−k+D−1 ∂Sin ≤γ ∂xv D−1 D
• Relative Influence The signal from relevant node pairs should be sufficiently strong considering other nodes in the graph. More specifically consider " # " # ! (k) (k) . X ∂s ∂s v v Iv,k (w) = eT e eT e ∂xw ∂xu
k=0
where γ is a constant in ∥B∥, ∥C∥, and µSSM . The bound separates into two components consisting of the architectural term δ d and the sequence dependent sensitiv-
u∈V
∂s(k)
ities ∂xvw . The binomial coefficients count the number of distinct computational paths from input to output across the processing and information depth dimension depicted in Figure 2c.
as the relative influence of w on v on the kth sequence element, following the influence distribution of (Xu et al., 2018). Here e is the all ones vector.
This contrasts with standard MPNNs, where the sensitivity is bounded by the powers of the graph operator. Although LGSM also incorporates graph-dependent propagation through graph mixing layers, the SSM component ensures that sensitivity is not only determined by it. Instead, the bound depends on all input sequence elements, relying on the fact that at least one element captures the node pair relationship. Therefore, the LGSM framework allows us to shift key graph learning questions toward the appropriate modeling of the sequence extraction.
The most natural choice for sequence extraction is perhaps (i) using the powers of the adjacency1matrix S1A = AiG X or its −2 −2 i (i) normalized version SÂ = (DG AG DG ) X. These correspond closely to the message passing scheme incorporated in standard MPNN architectures, where the t-th iteration aggregates information along all walks of length t. Considering the properties above, both sequences can in principle be computed efficiently through direct powers or preprocessing of the adjacency powers. Recall, that in both variants the t-th element of the sequence corresponds to the aggregation along all walks of length t. This can quickly (i) lead to instabilities in SA as the number of walks increases exponentially, but can be addressed with proper degree normalization. If a pair of nodes is connected, eventually there will be a sequence element which ensures non-zero sensitivity. Note that this interaction might still be small as it is
6. Sequence Extraction Mechanisms Our theoretical analysis reveals that the sensitivity of the final node embeddings has a direct dependence on all elements of the extracted sequence. Specifically, for a pair ∂yv of nodes v, w ∈ V the sensitivity ∂x depends on a w 6
From Message-Passing to Linearized Graph Sequence Models B tially faster with distance k compared to Iv,k (w):
proportional to the ratio of paths of length t between u and v over all possible paths of length t originating from them.
A (w) Iv,k
While the adjacency powers satisfy efficiency, stability, and sensitivity, let us consider the following scenario for the last two criteria. The adjacency powers always considers all paths of length t. This includes paths that immediately ”backtrack”, immediately traverse an edge in the other direction again, and therefore contain a short two cycle. As a consequence, if a node v can be reached at time t0 from v, then for all t′ > 0 the entry will always be non-zero ′ for (AtG0 +2t )uv . Each following sequence element will contain not only new information about nodes reachable at distance t but also redundant information about nodes reachable at shorter distances through backtracking paths. This redundancy undermines the informativeness of the sequence and also its relative influence, as the set of nodes that have non-zero sensitivity becomes increasingly larger.
B (w) Iv,k
See Appendix G for the proof. We also validate these insights empirically by testing the different sequence methods on the ECHO eccentricity task. In Figure 4, we train LGSM models with different sequence lengths and the considered sequence types. While the performance increases for all sequence types the longer the sequences are, using naive adjacency powers leads to numerical instabilities for longer sequences. Moreover, the BG exhibit better performance compared to the adjacency matrices across all considered sequence lengths.
To address this limitation of the adjacency powers, we propose to use an alternative sequence extraction mechanism based on non-backtracking walks. Instead of considering all paths of length k at step k, we only consider paths of length k which at no point immediately reverse direction. Thus, eliminating the two-cycle amplification that causes excessive redundant information. We refer to the non-backtracking (NBT) matrix as BG , where (BG )uv contains the number of non-backtracking walks from u to v. We remark that Park et al. (2024) have also considered nonbacktracking message-passing and its sensitivity, although solely by replacing them in the standard MPNN formulation.
Validation MSE
35
Definition 6.1 (Non-Backtracking Matrix). Let G = (V, E) be an undirected simple graph. The non-backtracking matrix BG ∈ Rn×n is defined by the recurrence (0) (1)
BG = AG (2)
(t+2)
BG
(t+1)
= AG BG
30 25
Sequence Type NBT 20 NBT normalized ADJ 15 ADJ symmetric 8 16 24 Sequence Length
32
40
Figure 4. Comparison of sequence extraction mechanisms on the ECHO eccentricity task with graphs of diameter up to 40. We evaluate non-backtracking (NBT) and adjacency powers, both original and normalized. Each datapoint represent the mean of three trained models of a specific sequence length using four LGSM blocks. Therefore the number of trainable parameters is the same for all sequence lengths. We observe that the performance consistently improves for longer sequences. Moreover, non-backtracking sequences are more informative and lead to consistently better performance across all considered sequence lengths. The unnormalized adjacency sequence causes numerical instabilities, leading to NaN values in computation.
BG = I BG = A2G − DG
≤ ck−1 ,
(t)
− (DG − I)BG
While the computation is sequential, we can still precompute the sequence of I, BG , B2G , ...BlG if necessary or directly multiply with the feature matrix to avoid large multiplications between adjacency matrices. The key benefit of non-backtracking walks over the regular adjacency powers lies in their improved relative influence for distant nodes by reducing the amount of redundant backtracking information.
7. Empirical Evaluation After investigating the design and theoretical properties of LGSM, we evaluated its empirical performance. We consider the recently proposed ECHO benchmark (Miglior et al., 2025), LRIM Graph Benchmark (Mathys et al., 2025) as well as the Peptides tasks from the LRGB collection (Dwivedi et al., 2022). On Peptides we find that LGSM performs similarly to standard message-passing, meaning that the impact of processing and information depth seems negligible. This is perhaps not as surprising considering that
Theorem 6.2 (Relative Influence of NBT). Let c < 1 and A B let Iv,k (w) (resp. Iv,k (w)) denote the influence of w on the kth sequence element of v captured using the adjacency sequence A (resp. non-backtracking B). There exists an A infinite family of graphs G where Iv,k (w) decays exponen7
From Message-Passing to Linearized Graph Sequence Models Table 1. Performance on synthetic graph property prediction tasks from ECHO-Synth, which are designed to be challenging for long-range information exchange. Results show MSE and MAE for diameter (DIAM), eccentricity (ECC), and single-source shortest path (SSSP) prediction. LGSM demonstrates strong performance across all datasets, particularly on the eccentricity prediction. DATASET
DIAM
ECC
SSSP
MSE ↓
MAE ↓
MSE ↓
MAE ↓
MSE ↓
MAE ↓
A-DGN DR EW GCN GCNII GIN GPS GRIT G RAPH CON PH-DGN SWAN
4.818 ± 0.108 3.756 ± 0.170 22.872 ± 2.766 9.696 ± 0.568 7.238 ± 1.153 10.454 ± 0.610 3.877 ± 0.295 16.427 ± 1.419 6.699 ± 2.728 4.950 ± 0.265
1.151 ± 0.038 1.243 ± 0.047 3.832 ± 0.262 2.005 ± 0.093 1.630 ± 0.161 2.160 ± 0.098 1.014 ± 0.046 2.969 ± 0.189 1.627 ± 0.398 1.121 ± 0.070
35.967 ± 0.492 32.247 ± 0.148 39.706 ± 0.460 39.911 ± 0.518 34.454 ± 1.201 33.346 ± 0.226 38.667 ± 1.903 43.505 ± 0.017 37.510 ± 1.416 34.208 ± 0.578
4.981 ± 0.037 4.651 ± 0.020 5.233 ± 0.034 5.241 ± 0.030 4.869 ± 0.092 4.758 ± 0.021 5.091 ± 0.158 5.474 ± 0.001 5.068 ± 0.126 4.840 ± 0.045
4.425 ± 0.879 6.589 ± 0.015 9.743 ± 0.757 10.369 ± 3.575 11.868 ± 2.689 1.255 ± 0.113 0.147 ± 0.083 52.104 ± 0.016 4.656 ± 3.013 2.905 ± 1.556
1.176 ± 0.140 1.279 ± 0.011 2.102 ± 0.094 2.128 ± 0.429 2.234 ± 0.271 0.472 ± 0.050 0.121 ± 0.013 5.734 ± 0.011 1.323 ± 0.485 0.896 ± 0.232
LGSM ( OURS )
3.089 ± 0.389
0.859 ± 0.044
13.549 ± 0.539
2.430 ± 0.070
0.040 ± 0.008
0.076 ± 0.009
Table 2. Performance on molecular property prediction tasks from ECHO-Chem. Results show MSE and MAE for atomic partial charge (CHARGE) and total molecular energy (ENERGY) prediction. LGSM exhibits strong performance on both tasks, demonstrating its applicability beyond synthetic settings for real-world prediction which require capturing non-local atomic interactions. DATASET
CHARGE
our desired model properties and capabilities apply beyond synthetic settings. Moreover, the baselines provided encompass a wide range of common graph learning benchmarks, including classic MPNNs, more sophisticated multi-hop and differential equation inspired message-passing as well as graph transformers. For more details on the details of our training setup and dataset details, we refer to Appendix E.
ENERGY
MSE ↓ ×104
MAE ↓ ×103
MSE ↓ ×10−3
MAE ↓
A-DGN DR EW GCN GCNII GIN GPS GRIT G RAPH CON PH-DGN SWAN
1.456 ± 0.032 3.669 ± 0.459 3.126 ± 0.263 3.490 ± 0.147 5.750 ± 0.239 1.620 ± 0.065 1.765 ± 0.071 13.250 ± 0.265 2.562 ± 0.144 1.251 ± 0.029
6.543 ± 0.146 9.086 ± 0.473 8.421 ± 0.512 8.829 ± 0.021 10.784 ± 0.059 6.182 ± 0.219 7.134 ± 6.090 19.629 ± 0.195 7.915 ± 0.269 6.109 ± 0.103
1.415 ± 0.799 1.281 ± 0.733 4.561 ± 0.176 1.560 ± 0.653 12.215 ± 2.878 0.180 ± 0.045 0.512 ± 0.149 0.975 ± 0.242 1.359 ± 0.408 2.652 ± 2.257
12.486 ± 1.621 11.325 ± 2.394 28.112 ± 1.239 13.235 ± 2.630 47.851 ± 10.154 5.257 ± 0.842 25.508 ± 2.507 14.295 ± 0.807 16.080 ± 1.123 12.629 ± 1.157
LGSM ( OURS )
1.411 ± 0.038
5.556 ± 0.068
0.152 ± 0.022
3.272 ± 0.186
Following the recommended setup, we train all our models to minimize logMSE during training and report both the MSE and MAE score metric in Table 2 and Table 1, respectively. We report the baseline scores directly from the ECHO benchmark, all our model results are averaged over three random seeds. Note that the models are not trained to minimize MAE directly and only the MSE metric is optimized during training. LGSM surpasses the baselines across most tasks in the ECHO benchmark. The model demonstrates particularly strong performance on the synthetic graph property prediction tasks. In the ablation presented in Figure 4, we evaluate the performance of the model with respect to the sequence length. The processing depth and, as a consequence, the parameter budget stay fixed. Nevertheless, we observe that, with increasing sequence length, performance consistently improves. This confirms that the ability to properly handle large information depths through sequence modeling is one of the key elements for the performance of LGSM on these datasets. In addition, the framework achieves good performance on real-world molecular property prediction tasks. Moreover, we evaluate on the LRIM-16-hard dataset, which is a dataset specifically designed to contain provable long-range interactions which require information gathering throughout the graph. In Figure 5 we observe that when we ablate over the LGSM configurations both the sequence length (information) and the number of blocks (processing) are indeed beneficial for the task, especially since for longer sequences the increase in pure information depth yields diminishing returns. We refer to the Appendix for the
recent techniques within two layers have achieved strong performances (Adamczyk et al., 2025) leveraging inductive bias. We refer to Appendix E for more details. Therefore, to properly evaluate if LGSM can provide sufficient information and processing depth, we focus on more recent, specialized benchmarks, which were designed to evaluate these capabilities: ECHO-Synth, ECHO-Chem, and LRIM. ECHO-Synth evaluates models on synthetic graph property prediction tasks consisting of predicting graph diameter (DIAM), node eccentricity (ECC), and single-source shortest paths (SSSP). Note that these tasks should require information depth, especially for graph families which exhibit a high graph diameter. As such the synthetic datasets provide an ideal testbeds to evaluate LGSM’s information depth capabilities. On the other hand, ECHO-Chem provides realworld molecular property prediction tasks, including atomic partial charge prediction (ECHO-Charge) and total molecular energy prediction (ECHO-Energy). These tasks require models to capture non-local atomic interactions. This is particularly interesting because we can evaluate whether 8
From Message-Passing to Linearized Graph Sequence Models
Num Blocks 1 blocks 2 blocks 4 blocks 8 blocks
1 best_val/logMSE
0 1 2 3 4 12
4
8
16 Sequence Length
24
32
Figure 5. Reporting validation logMSE (lower is better) on the LRIM-16-hard dataset. We ablate the impact of scaling either information depth or processing depth with LGSM. We validate that both increasing the sequence length and the model depth has a positive effect. This underscores the ability of the LGSM architecture to incorporate both axis in a principled and effective manner.
complete results on the LRIM Benchmark. This includes an in-depth ablation study on the individual components of LGSM and a discussion on empirical runtime.
sequence extraction. Our theoretical analysis fully characterizes the architecture and directly connects node sensitivity to the choice of sequence extraction. Based on this insight, we leverage non-backtracking walk sequences, which offer favorable properties, especially for long-range information propagation. Our empirical evaluation on the ECHO benchmark demonstrates that LGSM achieves strong performance on both synthetic tasks for graph property prediction and on real-world molecular tasks. Our work demonstrates how the simplification of the architecture and the clear separation of information and processing depth can shift key architectural questions into input modeling choices, providing a principled way for integrating modern deep learning techniques into graph learning.
8. Limitations While LGSM is designed with computational efficiency in mind, such as linearization and parallel scan algorithms, sequence preprocessing, row or columnwise forward passes to balance resources, we do not systematically explore these computational trade-offs in this work. We also acknowledge that there are other factors which can impact the performance of graph architectures such as regularization or domain inductive-bias besides the information and processing depth. We do not claim our framework to be universally optimal, instead, we aim to provide a theoretically based and principled understanding of the design principles of message-passing-based architectures.
References Adamczyk, J., Ludynia, P., and Czech, W. Molecular Fingerprints Are Strong Models for Peptide Function Prediction, October 2025. URL http://arxiv.org/ abs/2501.17901. arXiv:2501.17901 [q-bio] version: 2.
9. Conclusion We introduce Linearized Graph Sequence Models, a framework that views message-passing based graph learning from the perspective of sequence modeling by explicitly decoupling two fundamental dimensions of computation: information depth and processing depth. Unlike standard messagepassing networks where these dimensions advance simultaneously, LGSM linearizes propagation along the information axis, enabling information to flow across arbitrary graph distances while confining non-linear transformations to the processing dimension. This separation allows leveraging modern state-space model implementations for efficient parallel computation. Moreover, it enables proper information and gradient flow throughout and as a consequence reframes architectural choices in graph learning as questions about
Alon, U. and Yahav, E. On the Bottleneck of Graph Neural Networks and its Practical Implications. October 2020. URL https://openreview.net/forum? id=i80OPhOCVH2. Arnaiz-Rodriguez, A. and Errica, F. Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning, June 2025. URL http://arxiv.org/abs/2505. 15547. arXiv:2505.15547 [cs]. Arnaiz-Rodrıiguez, A., Begga, A., Escolano, F., and Oliver, N. M. DiffWire: Inductive Graph Rewiring via the 9
From Message-Passing to Linearized Graph Sequence Models
Lovász Bound. In Proceedings of the First Learning on Graphs Conference, pp. 15:1–15:27. PMLR, December 2022. URL https://proceedings.mlr.press/ ISSN: v198/arnaiz-rodri-guez22a.html. 2640-3498.
Di Giovanni, F., Giusti, L., Barbero, F., Luise, G., Liò, P., and Bronstein, M. On over-squashing in message passing neural networks: the impact of width, depth, and topology. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of ICML’23, pp. 7865– 7885, Honolulu, Hawaii, USA, July 2023. JMLR.org.
Arroyo, A., Gravina, A., Gutteridge, B., Barbero, F., Gallicchio, C., Dong, X., Bronstein, M. M., and Vandergheynst, P. On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning. October 2025. URL https: //openreview.net/forum?id=N4cyRMuLyl& referrer=%5Bthe%20profile%20of% 20Federico%20Barbero%5D(%2Fprofile% 3Fid%3D˜Federico_Barbero1).
Ding, Y., Orvieto, A., He, B., and Hofmann, T. Recurrent Distance Filtering for Graph Representation Learning. In Proceedings of the 41st International Conference on Machine Learning, pp. 11002–11015. PMLR, July 2024. URL https://proceedings.mlr.press/ v235/ding24d.html.
Behrouz, A. and Hashemi, F. Graph Mamba: Towards Learning on Graphs with State Space Models. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’24, pp. 119– 130, New York, NY, USA, August 2024. Association for Computing Machinery. ISBN 979-8-4007-0490-1. doi: 10.1145/3637528.3672044. URL https://dl.acm. org/doi/10.1145/3637528.3672044. Ceni, A., Gravina, A., Gallicchio, C., Bacciu, D., Schonlieb, C.-B., and Eliasof, M. Message-Passing State-Space Models: Improving Graph Learning with Modern Sequence Modeling, May 2025. URL http://arxiv. org/abs/2505.18728. arXiv:2505.18728 [cs]. Chen, D., Schulz, T. H., and Borgwardt, K. Learning Long Range Dependencies on Graphs via Random Walks. October 2024. URL https://openreview.net/ forum?id=kJ5H7oGT2M. Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and Deep Graph Convolutional Networks. In Proceedings of the 37th International Conference on Machine Learning, pp. 1725–1735. PMLR, November 2020. URL https://proceedings.mlr.press/ v119/chen20v.html.
Dwivedi, V. P., Rampávsek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, pp. 22326–22340, Red Hook, NY, USA, November 2022. Curran Associates Inc. ISBN 978-1-7138-7108-8. Eliasof, M., Gravina, A., Ceni, A., Gallicchio, C., Bacciu, D., and Schönlieb, C.-B. Graph Adaptive Autoregressive Moving Average Models. In Proceedings of the 42nd International Conference on Machine Learning, pp. 15232–15265. PMLR, October 2025. URL https://proceedings.mlr.press/ v267/eliasof25a.html. Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for Quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, pp. 1263–1272, Sydney, NSW, Australia, August 2017. JMLR.org. URL https://dl.acm.org/doi/10. 5555/3305381.3305512. Gravina, A., Bacciu, D., and Gallicchio, C. Anti-Symmetric DGN: a stable architecture for Deep Graph Networks. September 2022. URL https://openreview. net/forum?id=J3Y7cgZOOS.
Cohen, S. and Agmon, N. Convexified Graph Neural Networks for Distributed Control in Robotic Swarms. volume 3, pp. 2307–2313, August 2021. doi: 10.24963/ ijcai.2021/318. URL https://www.ijcai.org/ proceedings/2021/318. ISSN: 1045-0823.
Gravina, A., Eliasof, M., Gallicchio, C., Bacciu, D., and Schönlieb, C.-B. On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 39 (16):16906–16914, April 2025. ISSN 2374-3468. doi: 10. 1609/aaai.v39i16.33858. URL https://ojs.aaai. org/index.php/AAAI/article/view/33858.
Dao, T. and Gu, A. Transformers are SSMs: generalized models and efficient algorithms through structured state space duality. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of ICML’24, pp. 10041–10071, Vienna, Austria, July 2024. JMLR.org.
Grover, A. and Leskovec, J. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pp. 855–864, New York, NY, USA, August 2016. Association for Computing Machinery. ISBN 978-1-4503-4232-2. doi: 10
From Message-Passing to Linearized Graph Sequence Models
10.1145/2939672.2939754. URL https://dl.acm. org/doi/10.1145/2939672.2939754. Grötschla, F., Xie, J., and Wattenhofer, R. Benchmarking Positional Encodings for GNNs and Graph Transformers, January 2026. URL http://arxiv.org/abs/ 2411.12732. arXiv:2411.12732 [cs].
Kipf, T. N. and Welling, M. Semi-Supervised Classification with Graph Convolutional Networks. February 2017. URL https://openreview.net/forum? id=SJU4ayYgl. Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P. H., and Lim, S.-N. Graph inductive biases in transformers without message passing. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of ICML’23, pp. 23321– 23337, Honolulu, Hawaii, USA, July 2023. JMLR.org.
Gu, A. and Dao, T. Mamba: Linear-Time Sequence Modeling with Selective State Spaces. August 2024. URL https://openreview.net/forum? id=tEYskw1VY2.
Mathys, J. and Wattenhofer, R. A New Perspective for Graph Learning Architecture Design: Linearize Your Depth Away. October 2025. URL https:// openreview.net/forum?id=lybxAx4Msq.
Gu, A., Dao, T., Ermon, S., Rudra, A., and Ré, C. HiPPO: recurrent memory with optimal polynomial projections. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, pp. 1474–1487, Red Hook, NY, USA, December 2020. Curran Associates Inc. ISBN 978-1-7138-29546. URL https://dl.acm.org/doi/10.5555/ 3495724.3495849.
Mathys, J., Christiansen, H., Errica, F., Maruyama, T., and Alesiani, F. LRIM: a Physics-Based Benchmark for Provably Evaluating Long-Range Capabilities in Graph Learning. October 2025. URL https://openreview. net/forum?id=IAZXEX1dVV.
Gu, A., Goel, K., and Re, C. Efficiently Modeling Long Sequences with Structured State Spaces. October 2021. URL https://openreview.net/forum? id=uYLFoz1vlAC.
Micheli, A. Neural network for graphs: a contextual constructive approach. Trans. Neur. Netw., 20(3):498–511, March 2009. ISSN 1045-9227. doi: 10.1109/TNN.2008. 2010350. URL https://doi.org/10.1109/TNN. 2008.2010350.
Gutteridge, B., Dong, X., Bronstein, M., and Di Giovanni, F. DRew: dynamically rewired message passing with delay. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of ICML’23, pp. 12252– 12267, Honolulu, Hawaii, USA, July 2023. JMLR.org.
Miglior, L., Tolloso, M., Gravina, A., and Bacciu, D. Can You Hear Me Now? A Benchmark for LongRange Graph Propagation. May 2025. URL https: //openreview.net/forum?id=PcKkRJdX4n.
Heilig, S., Gravina, A., Trenta, A., Gallicchio, C., and Bacciu, D. Port-Hamiltonian Architectural Bias for LongRange Propagation in Deep Graph Networks. October 2024. URL https://openreview.net/forum? id=03EkqSCKuO.
Park, S., Ryu, N., Kim, G., Woo, D., Yun, S.-Y., and Ahn, S. Non-backtracking Graph Neural Networks. Transactions on Machine Learning Research, June 2024. ISSN 28358856. URL https://openreview.net/forum? id=64HdQKnyTc. Perozzi, B., Al-Rfou, R., and Skiena, S. DeepWalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’14, pp. 701– 710, New York, NY, USA, August 2014. Association for Computing Machinery. ISBN 978-1-4503-2956-9. doi: 10.1145/2623330.2623732. URL https://dl.acm. org/doi/10.1145/2623330.2623732.
Huang, Y., Miao, S., and Li, P. What Can We Learn from State Space Models for Machine Learning on Graphs? October 2024. URL https://openreview.net/ forum?id=xAM9VaXZnY. Keriven, N. Not too little, not too much: a theoretical analysis of graph (over)smoothing. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, pp. 2268–2281, Red Hook, NY, USA, November 2022. Curran Associates Inc. ISBN 978-1-7138-7108-8.
Rampasek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a General, Powerful, Scalable Graph Transformer. October 2022. URL https: //openreview.net/forum?id=lMMaNf6oxKM.
Kim, J., Zaghen, O., Suleymanzade, A., Ryou, Y., and Hong, S. Revisiting Random Walks for Learning on Graphs. October 2024. URL https://openreview.net/ forum?id=SG1R2H3fa1.
Rusch, T. K., Chamberlain, B., Rowbottom, J., Mishra, S., and Bronstein, M. Graph-Coupled Oscillator Networks. In Proceedings of the 39th International Conference 11
From Message-Passing to Linearized Graph Sequence Models
on Machine Learning, pp. 18888–18909. PMLR, June 2022. URL https://proceedings.mlr.press/ v162/rusch22a.html. Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1):61–80, January 2009. ISSN 1941-0093. doi: 10.1109/TNN. 2008.2005605. URL https://ieeexplore.ieee. org/document/4700287.
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S. Representation Learning on Graphs with Jumping Knowledge Networks. In Proceedings of the 35th International Conference on Machine Learning, pp. 5453–5462. PMLR, July 2018. URL https://proceedings.mlr.press/v80/ xu18c.html. ISSN: 2640-3498.
Stoll, T., Müller, L., and Morris, C. Generalizable Insights for Graph Transformers in Theory and Practice. October 2025. URL https://openreview. net/forum?id=ROfYsQ2KNV&referrer= %5Bthe%20profile%20of%20Timo%20Stoll% 5D(%2Fprofile%3Fid%3D˜Timo_Stoll1). Tönshoff, J., Ritzert, M., Wolf, H., and Grohe, M. Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing. Transactions on Machine Learning Research, April 2023. ISSN 28358856. URL https://openreview.net/forum? id=vgXnEyeWVY. Tönshoff, J., Ritzert, M., Rosenbluth, E., and Grohe, M. Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark. Transactions on Machine Learning Research, January 2024. ISSN 2835-8856. URL https: //openreview.net/forum?id=Nm0WX86sKv. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is All you Need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https://papers. nips.cc/paper_files/paper/2017/hash/ 3f5ee243547dee91fbd053c1c4a845aa-Abstract. html. Wang, Y. and Cho, K. Non-convolutional graph neural networks. November 2024. URL https:// openreview.net/forum?id=JDAQwysFOc. Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Weinberger, K. Simplifying Graph Convolutional Networks. In Proceedings of the 36th International Conference on Machine Learning, pp. 6861–6871. PMLR, May 2019. URL https://proceedings.mlr.press/v97/ wu19e.html. ISSN: 2640-3498. Xu*, K., Hu*, W., Leskovec, J., and Jegelka, S. How Powerful are Graph Neural Networks? September 2018. URL https://openreview.net/forum? id=ryGs6iA5Km. 12
From Message-Passing to Linearized Graph Sequence Models
A. Extended Related Work Message-passing With the establishment of message-passing (Micheli, 2009; Scarselli et al., 2009) as the core component to incorporate the graph bias, several different architectures have been proposed (Xu* et al., 2018; Gilmer et al., 2017). Most of them consider message-passing on the adjacency or a normalized version of it (Kipf & Welling, 2017). As such, all share the inherent mechanism that leads to loss of information due to repeated deep aggregations (Alon & Yahav, 2020; Di Giovanni et al., 2023; Arnaiz-Rodriguez & Errica, 2025). This has motivated considering complementary mechanisms such as virtual compute structures Arnaiz-Rodrıiguez et al. (2022) or entirely different approaches, such as graph transformers Ma et al. (2023); Stoll et al. (2025). However, in particular the latter often requires additional modeling of inductive bias by positional embeddings (Grötschla et al., 2026) or re-incorporating in the message-passing (Rampasek et al., 2022). Alternatively, the connection to discretizing differential equations has led to insights for mitigating vanishing node sensitivity and proper optimization by restricting the weight spaces (Gravina et al., 2022; 2025; Heilig et al., 2024; Arroyo et al., 2025). Finally, different linearization approaches have been considered for mathematical analysis (Keriven, 2022), ease of optimization (Cohen & Agmon, 2021) or efficiency considerations (Ceni et al., 2025; Wu et al., 2019; Mathys & Wattenhofer, 2025). Non-backtracking Walk based methods (Grover & Leskovec, 2016; Perozzi et al., 2014) for graph learning have seen a resurgence in recent years (Behrouz & Hashemi, 2024; Chen et al., 2024; Wang & Cho, 2024; Kim et al., 2024), due to leveraging powerful sequence processing architectures. Most of these make use of non-backtracking walks and further employ some kind of local memory to incorporate neighboring nodes and edges as sliding windows (Tönshoff et al., 2023). Moreover, modeling the same behavior for message-passing architectures by explicitly changing the aggregation to be edge state dependent has favorable properties, such as better sensitivity and spectral properties (Park et al., 2024).
B. Detailed Architecture A detailed specification of the LGSM architecture is provided in Algorithm 1. The model operates on graph-structured data by first transforming the input graph features X ∈ Rd×n and adjacency matrix AG ∈ Rn×n into a latent sequence (0) (L−1) representation. Specifically, a sequence extractor (S EQ) maps the inputs (X, AG ) to an initial sequence Sin , . . . , Sin . This sequence is subsequently processed through a stack of D blocks, each comprising three components: a State-Space Model (SSM), a Feed-Forward Network (σ1 ), and a Graph Mixing layer. (0)
(L−1)
In the first step of each layer, the SSM processes the input sequence Sin , . . . , Sin to an output sequence. The output is (0) (L−1) stabilized via a residual connection and layer normalization (L AYER N ORM) to obtain SSSM , . . . , SSSM . Subsequently, the sequence are passed through a element-wise non-linear FFN, followed by a second residual connection and normalization (0) (L−1) step to produce SFFN , . . . , SFFN . Finally, the Graph Mixing layer updates the sequence elements with the graph-propagated features of the preceding element. This combined representation is processed by a second non-linearity (σ2 ), refined with a skip connection, and normalized.
13
From Message-Passing to Linearized Graph Sequence Models
Algorithm 1 Pseudocode of LGSM Architecture 1: Input: X ∈ Rd×n , AG ∈ Rn×n , L ∈ N, D ∈ N 2: Output: Sout ∈ Rd×n 3: ▷ Initial sequence extraction (0) (L−1) 4: Sin , . . . , Sin ← S EQ(X, AG ) 5: for d = 1, . . . , D do 6: ▷ SSM Layer (0) (L−1) (0) (L−1) 7: SSSM , . . . , SSSM ← SSM(Sin , . . . , Sin ) 8: for ℓ = 0, . . . , L − 1 do (ℓ) (ℓ) (ℓ) 9: SSSM ← L AYER N ORM(SSSM + Sin ) 10: ▷ FFN layer (ℓ) (ℓ) 11: SFFN ← σ1 (SSSM ) (ℓ) (ℓ) (ℓ) 12: SFFN ← L AYER N ORM(SFFN + SSSM ) 13: end for 14: ▷ Graph mixing layer (0) (0) 15: SMIX ← SFFN 16: for ℓ = 0, . . . , L − 1 do (ℓ−1) (ℓ) (ℓ) 17: SMIX ← σ2 (SFFN + AG SFFN ) (ℓ) (ℓ) (ℓ) 18: SMIX ← L AYER N ORM(SMIX + SFFN ) 19: end for (L−1) (0) (L−1) (0) 20: Sin , . . . , Sin ← SMIX , . . . , SMIX 21: end for 22: ▷ Final graph decoder (L−1) 23: Sout ← D EC(Sin ) 24: return Sout
14
From Message-Passing to Linearized Graph Sequence Models
C. Theoretical Results Pt (t−k) Let αt := C k=0 Ak BSin be the closed-form expression for Y(t) in the SSM recurrence (1)-(2) with initial condition (−1) X = 0, which follows by induction on t:
(t)
X(t) = AX(t−1) + BSin Y
(t)
(t)
= CX
(1) (2)
In particular, αt = Y(t) . We begin with a helper lemma that bounds the sensitivity of a single SSM block in the absence of graph mixing. This will serve as a building block for the subsequent proofs. Lemma C.1. Consider a 1-block LGSM of sequence length L with an SSM defined by the system matrices (A, B, C), input features xv and output features Sout . Suppose that the FFN σSSM is µSSM -regular, and that A is normal with spectral radius ρ(A) ≈ 1. Then: L
(k)
X ∂S ∂σSSM (αL ) in ≤γ ∂xv ∂xv k=0
Where γ := µSSM ∥B∥∥C∥. Proof. By a direct computation: ∂σSSM (αL ) ∂σSSM (αL ) ≤ ∂xv ∂αL ∂αL ≤ µSSM ∂xv
∂αL ∂xv
(submultiplicativity of ∥ · ∥) (µSSM -regularity of σSSM )
L
≤ µSSM
X ∂ (L−k) Ak BSin C ∂xv
≤ µSSM C
L X
(L−k)
Ak B
k=0
≤ µSSM ∥C∥ ≤ µSSM ∥C∥
L X
k=0
(A, B, C independent of xv )
(L−k)
k=0 L X
∂Sin ∂xv
Ak B
∂Sin ∂xv
(submultiplicativity and triangle inequality) (L−k)
∥Ak ∥∥B∥
≤ µSSM ∥C∥∥B∥ ≤ µSSM ∥C∥∥B∥ ≤γ
(def. αL )
k=0
L X k=0
∂Sin ∂xv
(submultiplicativity)
(L−k)
ρ(A)k
∂Sin ∂xv
(A normal)
L (L−k) X ∂Sin ∂xv
(ρ(A) ≈ 1)
k=0
L (k) X ∂Sin ∂xv
(re-indexing, k 7→ L − k)
k=0
Which concludes this proof.
15
From Message-Passing to Linearized Graph Sequence Models
We now extend this result to a full 1-block LGSM by additionally incorporating the graph mixing layer. We use this lemma to show the following theorems. Next we show: Theorem 5.1 (Local Sensitivity for 1-Block LGSM). Consider a 1-block LGSM of sequence length L with an SSM defined (L) by system matrices (A, B, C). Denote the input and output features by X, Sout ∈ Rn×d , respectively, where xv = (X)v,: , is the feature vector of vertex v ∈ V. Suppose that the FNNs σSSM , σMIX are µSSM - and µMIX -regular, respectively, and that A is normal with spectral radius ρ(A) ≈ 1. Then, for any vertex v ∈ V: (L)
∂Sout ∂xv
≤γ
L L−1 (k) X X ∂S(k) ∂Sin in + γ∥AG ∥ ∂xv ∂xv
k=0
k=0
where γ is a constant in ∥B∥, ∥C∥, µSSM , and µMIX . Proof. Let βL := σSSM (αL ) + AG σSSM (αL−1 ) denote the value of the LGSM output before the application of the FFN (L) σMIX , such that Sout = σMIX (βL ). Then: (L)
∂Sout ∂xv
≤
∂σMIX (βL ) ∂βL ∂βL ∂xv
(def. 1-block LGSM)
∂σMIX (βL ) ∂βL ∂βL ∂xv ∂βL ≤ µMIX ∂xv ∂σSSM (αL ) ∂σSSM (αL−1 ) ≤ µMIX + AG ∂xv ∂xv ∂σSSM (αL ) ∂σSSM (αL−1 ) ≤ µMIX + ∥AG ∥ ∂xv ∂xv ! L L−1 (k) X ∂S X ∂S(k) ′ ′ in in ≤ µMIX γ + ∥AG ∥γ ∂xv ∂xv ≤
k=0
≤γ
(µMIX -regularity of σMIX ) (def. βL ) (triangle ineq. and submult.) (Lemma C.1)
k=0
L L−1 (k) X X ∂S(k) ∂Sin in + γ∥AG ∥ ∂xv ∂xv
k=0
(submultiplicativity)
(γ := µMIX γ ′ )
k=0
Before extending to a general D-block LGSM, we first analyze the sensitivity of a D-block LGSM without graph mixing layers. That is, a D-fold stack of alternating SSM layers and an FFN σMIX . Theorem 5.2 (Local Sensitivity for LGSM). Consider a D-block LGSM without graph mixing layers and of sequence (L,D) length L, with an SSM defined by system matrices (A, B, C). Denote the input and output features by X, Sout ∈ Rn×d , respectively, where xv = (X)v,: , is the feature vector of vertex v ∈ V. Suppose that the FFN σSSM is µSSM -regular and that A is normal with spectral radius ρ(A) ≈ 1. Then, for any vertex v ∈ V: L (L,D) (k,1) X ∂Sout L−k+D−1 ∂Sin ≤ γD ∂xv D−1 ∂xv k=0
where γ is a constant in ∥B∥, ∥C∥, and µSSM . Proof. Define the shorthand (L,D)
G(L, D) :=
16
∂Sout ∂xv
From Message-Passing to Linearized Graph Sequence Models (k,D)
By Lemma C.1 and the identity Sin
(k,D−1)
= Sout
, for D > 0 we obtain the recurrence
G(L, D) ≤ γ
L X k=0
G(k, D − 1)
(3)
where γ = µSSM ∥B∥∥C∥. Base cases.
(L,0)
If D = 0 we apply no SSM blocks, thus we have Sout
(L,1)
∂Sin ∂xv
G(L, 0) =
≤ γ0
(L,1)
= Sin
and
L (k,1) X ∂Sin L−k−1 −1 ∂xv
k=0
Let L = 0 and D > 0. By repeatedly applying (3) and then (4) we obtain:
G(0, D) ≤ γ D G(0, 0) ≤ γ D Inductive step.
0 (0,1) X ∂Sin 0−k−1 −1 ∂xv
k=0
= γD
0 (0,1) X ∂Sin 0−k−1 ∂xv D−1
k=0
Let D > 0, L > 0, then:
G(L, D) ≤ γ
L X k=0
(3)
k (j,1) X ∂Sin k−j+D−2 ∂xv D−2 j=0 k=0 (j,1) X ∂Sin k−j+D−2 ≤ γD D−2 ∂xv
≤γ
L X
G(k, D − 1) γ D−1
(IH)
0≤j≤k≤L
≤ γD ≤ γD ≤ γD
L L (j,1) X X ∂Sin k−j+D−2 ∂xv D−2 j=0 k=j
L X
(j,1) ∂Sin
j=0
∂xv
L X
(j,1) ∂Sin
j=0
∂xv
L−j X k=0
k+D−2 D−2
L−j+D−1 D−1
L (j,1) X ∂Sin L−j+D−1 ≤γ D−1 ∂xv j=0 D
Establishing the claim.
17
(Hockey-Stick Lemma)
(4)
From Message-Passing to Linearized Graph Sequence Models
Finally we generalize the statement to general D-block LGSM. Theorem C.2 (Local Sensitivity for entire LGSM). Consider a D-block LGSM of sequence length L, with an SSM defined (L,D) by system matrices (A, B, C). Denote the input and output features by X, Sout ∈ Rn×d , respectively, where xv = (X)v,: , is the feature vector of vertex v ∈ V. Suppose that the FFNs σSSM , σMIX are µSSM - and µMIX -regular, respectively, and that A is normal with spectral radius ρ(A) ≈ 1. Then, for any vertex v ∈ V: (L,D)
∂Sout ∂xv
≤ γD
L (L−k,1) X ∂Sin ∂xv
min{k,D}
X
m=0
k=0
k−m+D−1 D ∥AG ∥m D−1 m
where γ is a constant in ∥B∥, ∥C∥, µSSM , and µMIX . (L,D)
Proof. We use G(L, D) := ∥∂Sout
/∂xv ∥ from earlier. By Theorem 5.1 we have:
L X
G(L, D) ≤ γ
k=0
G(k, D − 1) + γ∥AG ∥
(L,0)
If D = 0 we apply no SSM blocks, thus we have Sout
Base cases.
(L,1)
G(L, 0) =
∂Sin ∂xv
≤ γ0
L (L−k,1) X ∂Sin ∂xv
L−1 X k=0
(L,1)
= Sin
min{k,0}
X
m=0
k=0
G(k, D − 1)
(5)
and
k−m−1 −1
0 ∥AG ∥m m
Let L = 0 and D > 0. By repeatedly applying (5) and then (6) we obtain:
G(0, D) ≤ γ D G(0, 0) ≤ γ D
L X k=0
≤ γD
k=0
min{k,D}
X
m=0
k−m+D−1 D ∥AG ∥m D−1 m
Let D > 0, L > 0, then:
Inductive step.
G(L, D) ≤ γ
0 (0−k,1) X ∂Sin ∂xv
G(k, D − 1) + γ∥AG ∥
L X k (k−j,1) X ∂Sin ∂xv j=0
k=0 D
+ γ ∥AG ∥
L−1 k XX k=0 j=0
k=0
k=0
G(k, D − 1)
(5)
min{j,D−1}
X
m=0 (k−j,1)
∂Sin ∂xv
L X k (k−j,1) X ∂Sin =γ ∂xv j=0 D
L−1 X
j−m+D−2 D−2
min{j,D−1}
X
m=0
m=0
D−1 ∥AG ∥m m
j−m+D−2 D−2
min{j,D−1}
X
j−m+D−2 D−2 18
D−1 ∥AG ∥m m
D−1 ∥AG ∥m m
(IH)
(6)
From Message-Passing to Linearized Graph Sequence Models
+ γD
min{j,D−1}
L k−1 X X ∂S(k−1−j,1) in ∂xv j=0
X
m=0
k=1
min{j,D−1}
L X k (k−j,1) X ∂Sin =γ ∂xv j=0
j−m+D−2 D−2
X
D
m=0
k=0
min{j−1,D−1}
L X k (k−j,1) X ∂Sin +γ ∂xv j=1
X
D
m=0
k=1
L X k (k−j,1) X ∂Sin ∂xv j=0
min{j,D−1}
L X k (k−j,1) X ∂Sin +γ ∂xv j=1
min{j,D}
L X k (k−j,1) X ∂Sin ∂xv j=0
min{j,D−1}
= γD
m=0
X
D
m=1
k=1
+γ
m=0
D
k=0 j=0
min{j,D}
(k−j,1)
∂Sin ∂xv
X
m=0
L X k (k−j,1) X ∂Sin =γ ∂xv j=0
min{j,D}
L X k (k−j,1) X ∂Sin ∂xv j=0
min{j,D}
D
X
m=0
k=0
= γD
X
m=0
k=0
L (L−k,1) X ∂Sin =γ ∂xv
min{k,D}
L (L−k,1) X ∂Sin =γ ∂xv
min{k,D}
D
k=0
D
k=0
X
m=0
X
m=0
D−1 ∥AG ∥m+1 m
(j 7→ j −1)
D−1 ∥AG ∥m m
D−1 ∥AG ∥m m−1
(k 7→ k−1)
(m 7→ m−1)
D−1 ∥AG ∥m m
D−1 ∥AG ∥m m−1
(extend;
D−1 −1
= 0)
D−1 D−1 + ∥AG ∥m m m−1
(merge;
D−1 D
= 0)
j−m+D−2 D−2
j −m+D−2 D−2
D−1 ∥AG ∥m+1 m
D−1 ∥AG ∥m m
j−m+D−2 D−2
X
k=0
L X k X
j−m+D−2 D−2
j −m+D−3 D−2
j−m+D−2 D−2
X
k=0
≤ γD
j−m+D−2 D−2
j−m+D−2 D−2
D ∥AG ∥m m
k−m X s + D − 2 D m ∥AG ∥ m D−2 s=0 k−m+D−1 D ∥AG ∥m D−1 m
Establishing the claim.
19
(Pascal’s identity)
(re-index; swap sums)
(Hockey-Stick)
From Message-Passing to Linearized Graph Sequence Models
Remark. We want to comment on the assumptions made in Theorem 5.1, Theorem 5.2, and Theorem C.2. The µSSM and µMIX -regularity of σSSM and σMIX respectively, are justified since we initialize the σSSM and σMIX FFN with MLPs consisting of dense hidden layers with GELU activations. Since GELU is smooth and Lipschitz on bounded domains, each such MLP has bounded Jacobian norm, ensuring µ-regularity for a finite constant µ > 0 determined by the network weights. The assumption that A is normal with spectral radius ρ(A) ≈ 1 is standard in structured SSM architectures. In practice, A is initialized as a diagonal matrix (e.g., via the HiPPO framework), which is trivially normal. The condition ρ(A) ≈ 1 reflects the design choice of placing eigenvalues near the unit circle to enable long-range information propagation without exponential growth or decay of the hidden state across sequence steps.
D. Dataset Details ECHO (Miglior et al., 2025) (Evaluating Communication over long HOps) is a comprehensive benchmarke designed to evaluate the long-range modeling capabilities of GNNs. The benchmark is categorized into two collections of datasets ECHO-Synth and ECHO-Chem. ECHO-Synth evaluates GNNs on the synthetic graph property prediction tasks ECHO-DIAM graph diameter, ECHO-ECC node eccentricity and ECHO-SSSP single-source shortest path. ECHO-Chem provides real-world challenges derived from computational chemistry, requiring GNNs to capture non-local atomic interactions. The dataset ECHO-Charge is focused on predicting atomic charge distributions while ECHO-Energy is centered around predicting total molecular energy. Statistics for all datasets used are listed in Table 3 and 4. Table 3. Summary of ECHO datasets, taken from Miglior et al. (2025).
Dataset ECHO-Synth ECHO-Chem
Node Features
Edge Features
Target
Random scalar, source indicator for sssp Atomic number, distance from center of mass
None Bond type, bond length
diam, sssp, ecc Partial charges, Total energy
Table 4. Statistics of the ECHO datasets, taken from. Dataset ECHO-Synth line ladder grid tree caterpillar lobster
# Graphs
Avg Nodes
Avg Deg.
Avg Edges
Avg Diam
# Node Feat
# Edge Feat
# Tasks
10,080
83.69±66.24
2.53±1.19
211.63±209.39
28.50±6.92
2
None
3
1,680 1,680 1,680 1,680 1,680 1,680
75.60±27.32 56.52±13.82 193.10±93.10 60.42±17.17 34.71±7.96 81.79±25.46
2.37±0.10 2.92±0.02 2.95±0.12 1.96±0.01 1.94±0.02 1.97±0.01
90.10±33.89 82.54±20.72 288.32±145.29 59.42±17.17 33.71±7.96 80.79±25.46
28.50±6.92 28.50±6.92 28.50±6.92 28.50±6.92 28.50±6.92 28.50±6.92
2 2 2 2 2 2
None None None None None None
3 3 3 3 3 3
170,367 196,528
72.49±12.48 73.73±13.22
2.09±0.04 2.09±0.04
151.32±25.16 153.84±26.58
23.54±2.54 23.61±2.59
2 2
2 2
1 1
ECHO-Chem ECHO-Charge ECHO-Energy
E. Experimental Details All models are implemented using PyTorch and PyTorch Geometric (PyG). We use the official Mamba2 (Dao & Gu, 2024) implementation for the SSM backbone. We will release the codebase upon acceptance of the paper. We report the key architectural hyperparameters in Table 8. The Feed-Forward Networks (FFN) throughout the model consist of two-layer MLPs with hidden dimension 4× the input dimension and GeLU activation. We apply LayerNorm after each component (SSM, FFN, Graph Mixing) following standard practice. For graph-level tasks, the graph decoder pools node representations using max, sum, and mean pooling, concatenates these representations, and projects them linearly to the hidden dimension before applying the decoder MLP. For node-level tasks, the decoder operates directly on node representations. We use the AdamW optimizer with no weight decay, and gradient clipping with maximum norm 1.0. All models are trained to minimize log MSE. Following the ECHO benchmark convention, we normalize the labels during training for ECHO-Synth tasks and use original labels for ECHO-Chem tasks. For ECHO-Energy predictions, we report 10prediction as specified in the ECHO benchmark repository. 20
From Message-Passing to Linearized Graph Sequence Models Table 5. Overview of the used LRIM Graph Benchmark taken from (Mathys et al., 2025)
Dataset
σ easy
σ hard
Graphs
Nodes
Edges
Avg. Eff. Resistance
Avg. Short. Path
Diameter
LRIM-16
1.5
0.6
10,000
256
512
0.49
8.03
16
Table 6. Statistics of the Peptides LRGB datasets taken from (Dwivedi et al., 2022). Dataset
Total Graphs
Total Nodes
Avg Nodes
Mean Deg.
Peptides Func Peptides Struct
15,535 15,535
2,344,859 2,344,859
150.94 150.94
2.04 4,773,974 2.04 4,773,974
Total Edges
Avg Avg Edges Short.Path.
Avg Diameter
307.30 307.30
56.99±28.72 56.99±28.72
20.89±9.79 20.89±9.79
Baseline Comparisons. We take the baselines reported by the ECHO benchmark (Miglior et al., 2025): namely A-DGN (Gravina et al., 2022), DREW (Gutteridge et al., 2023), GCN (Kipf & Welling, 2017), GCNII (Chen et al., 2020), GIN (Xu* et al., 2018), GPS (Rampasek et al., 2022), GRIT (Ma et al., 2023), GraphCON (Rusch et al., 2022), PH-DGN (Heilig et al., 2024), SWAN (Gravina et al., 2025). E.1. LGSM Component Ablation We ablate the impact of key design choices of the LGSM blocks, baseline refers to the best performing methods as reported in Table 8. Recall, that models are trained to minimize logMSE (and MAE is an eval metric). We vary the sequence lengths, number of blocks, graph mixing amongst other components. Further, we ablate replacing the Mamba architectures with as simplified SSM, which consists of learnable matrices A,B,C. The results in Table 7 indicate that both the sequence length and processing depth, but also the graph mixing and role of the SSM are important for the final performances on the ECHO Synth Datasets. E.2. Evaluation on LRIM Graph Benchmark In order to further evaluate the capabilities of our LGSM method, we evaluate on the LRIM Graph Benchmark (Mathys et al., 2025), a benchmark specifically tailored to the precise assessment of long-range capabilities. We evaluate and report the performance in Table 10, where LGSM performs better than the message-passing baselines and comparable to the computationally more expensive transformer based approaches. Further, we ablate the impact of the information and processing depth, which are central parts of the LGSM design. Figure 6 illustrates that both dimensions contribute towards better performance, however, solely increasing processing depth without also increasing the information depth yields diminishing returns. E.3. Evaluation on Peptides Datasets We follow the setup from Tönshoff et al. (2024): AdamW with cosine scheduling for 250 epochs, decoder head, batch size 200 and ran a small selection of hyperparameters (seq. type, length, num blocks). We did not observe a similar improvement with longer sequences. Instead, on Peptides it seemed to matter most to have choices which implicitly regularize more (shorter sequences, adj) in order to incentivize good generalization. Moreover, we observed consistent (and significant) gaps between train and validation performances which might suggest that regularization is more important for this task compared to the impact of the architecture.
F. Empirical Runtime Measurement We quantitatively evaluate our method on sparse ER graph (connectivity log n /n) of size 256 for various sequence lengths (layers respectively). Moreover, we provide results for fixed sequence/layers=16 for variously sized sparse ER graphs. We also consider a simple GCN and GPS baseline based on the pyg modules with FFNs. We also provide LGSM baselines with 1,2 blocks as well as the simplified SSM variant (learned A,B,C matrices instead of Mamba). Note that as mentioned in our limitations the empirical efficiency was not our main focus. As such, we recompute the sequences each forward pass and compute row-wise (which requires more memory than columnwise). Therefore, memory grows proportional to the sequence 21
From Message-Passing to Linearized Graph Sequence Models Table 7. Model component ablation for LGSM on the ECHO-Synth Datasets. We report both logMSE, which is optimized as a loss during training as well as the mean absolute error. The ablated components are either part of the sequence design (length, normalization) or of the block design. There we also ablate either using a simplified SSM with learnable matrices A,B,C or not using the ssm module at all. All values are reported over 3 seeds and are evaluated on the validation split. Variant
DIAM
SSSP
ECC
logMSE ↓
MAE ↓
logMSE ↓
MAE ↓
logMSE ↓
MAE ↓
baseline
0.450 ± 0.025
0.829 ± 0.033
-1.405 ± 0.184
0.077 ± 0.013
1.122 ± 0.008
2.381 ± 0.053
seq length 1 seq length 5 seq length 10 seq length 20 seq normalization none seq normalization row
0.943 ± 0.006 0.538 ± 0.022 0.567 ± 0.076 0.462 ± 0.011 0.549 ± 0.041 –
1.839 ± 0.065 0.855 ± 0.028 0.916 ± 0.092 0.867 ± 0.023 0.911 ± 0.069 –
1.738 ± 0.000 1.545 ± 0.000 1.231 ± 0.001 0.380 ± 0.006 – -0.538 ± 0.073
5.970 ± 0.001 4.338 ± 0.015 2.494 ± 0.019 0.601 ± 0.020 – 0.167 ± 0.031
1.640 ± 0.000 1.573 ± 0.002 1.538 ± 0.002 1.386 ± 0.018 1.201 ± 0.013 –
5.497 ± 0.000 5.068 ± 0.011 4.848 ± 0.012 3.807 ± 0.065 2.613 ± 0.023 –
num blocks 1 num blocks 2 use graph mixing False use simple ssm True
0.430 ± 0.028 0.429 ± 0.052 0.521 ± 0.007 0.551 ± 0.105
0.830 ± 0.029 0.816 ± 0.072 0.928 ± 0.048 1.023 ± 0.144
-0.119 ± 0.094 -0.713 ± 0.161 -1.224 ± 0.153 -1.280 ± 0.008
0.457 ± 0.064 0.181 ± 0.030 0.079 ± 0.009 0.075 ± 0.012
1.191 ± 0.016 1.155 ± 0.009 1.128 ± 0.002 1.627 ± 0.000
2.721 ± 0.071 2.507 ± 0.028 2.423 ± 0.025 5.413 ± 0.003
Table 8. Best LGSM hyperparameter configurations per task on the ECHO benchmark, selected by validation logMSE. Task
Seq. Type
ECHO-Charge ECHO-Diam ECHO-Ecc ECHO-Energy ECHO-Sssp
NBT NBT NBT NBT NBT
Length 40 40 40 32 40
Seq. Normalization
Hidden Dim
Blocks
Batch Size
Learning Rate ×10−4
Max Epochs
64 64 64 64 64
4 4 4 2 4
32 32 32 32 32
3 3 3 3 3
200 200 200 200 200
row row row none none
length and graph size. Measurements are taken over 200 graphs and measured on an RTX 3090 with 24 GB VRAM. In Figure 7 we measure timing and memory requirements for a fixed graph of size 256 for multiple sequence lengths. Similarly, in Figure 8 we report time and memory measurements for a fixed sequence length (or number of layers) of 16 across graphs up to size 8192.
22
From Message-Passing to Linearized Graph Sequence Models
Table 9. Results for Peptides-func and Peptides-struct averaged over 3 training seeds. Baseline results are taken from (Dwivedi et al., 2022), (Gutteridge et al., 2023) and Eliasof et al. (2025). Note that all MPNN-based methods include structural and positional encoding, whereas ours does not. Model
Peptides-func AP ↑
Peptides-struct MAE ↓
64.69±00.19 68.30±00.26 65.92±00.36 68.43±00.49 69.96±00.76 71.50±0.44 69.40±0.74 71.26±0.45 67.33±0.94 69.77±0.26
0.3173±0.0007 0.2616±0.0018 0.2921±0.0023 0.2614±0.0023 0.2781±0.0028 0.2536±0.0015 0.2799±0.0016 0.2606±0.0014 0.2699±0.0018 0.2539±0.0007
63.26±1.26 63.84±1.21 65.35±0.41
0.2529±0.0016 0.2683±0.0043 0.2500±0.0005
68.60±0.50 66.21±0.67 67.65±0.47 69.45±0.21 65.34±0.91 72.61 ±0.11 70.59 ±0.89 70.06 ±0.33
0.2460±0.0007 0.2473±0.0017 0.2477±0.0009 0.2517±0.0011 0.2509±0.0014 0.2421 ±0.0016 0.2429 ±0.0019 0.2431 ±0.0020
57.89±0.62 60.22±0.68 59.75±0.44 67.51±0.39 67.39±0.87 70.96±0.78 70.71±0.83 70.49±0.51
0.3418±0.0015 0.2778±0.0018 0.2874±0.0021 0.2485±0.0009 0.2478±0.0016 0.2463±0.0005 0.2473±0.0025 0.2459±0.0020
66.85±1.36
0.2470 ±0.0019
Multi-hop GNNs DIGL+MPNN DIGL+MPNN+LapPE MixHop-GCN MixHop-GCN+LapPE DRew-GCN DRew-GCN+LapPE DRew-GIN DRew-GIN+LapPE DRew-GatedGCN DRew-GatedGCN+LapPE Transformers Transformer+LapPE SAN+LapPE GraphGPS+LapPE Modified and Re-evaluated‡ GCN GINE GatedGCN DRew-GCN+LapPE GraphGPS+LapPE GCN+ GIN+ GatedGCN+ GNNs GRAND GraphCON A-DGN SWAN Graph-Mamba Neural Walker GMN GRAMAG ATED GCN Ours LGSM (ours)
Table 10. Evaluation of LGSM on the LRIM Graph Benchmark. We report both asymptotic runtime which is dependent on if the input sequence is preprocessed or not as well as the performance metric in logMSE. The LGSM uses 8 blocks with sequence length 32 and surpasses the message-passing based baselines while being very close in performance to the computationally more expensive transformer based approaches.
Preprocessing
Computation
GIN GatedGCN
-
GatedGCN-VNG
O(N )
O(L · E) O(L · E)
GPS-Base GPS-RWSE GPS-LapPE
O(k · N 2 ) O(k 2 · E)
LGSM
O(L · E + L · N )
O(L · E)† or O(1)‡
23
O(L · N 2 ) O(L · N 2 ) O(L · N 2 )
O(D · L · E)
LRIM-16-hard ↓ -2.406 ± 0.148 -3.919 ± 0.223
-3.756 ± 0.063
-4.340 ± 0.101 -4.345 ± 0.065 -4.248 ± 0.110
-4.284 ± 0.133
1.336
1.336
1.336
1
2
0.633
0.633
0.633
0.633
0
Sequence Length 16 8 4
-0.423
-0.440
-0.439
-0.435
-1.582
-1.658
-1.664
-1.647
-2.259
-3.110
-3.506
-3.639
24
-2.235
-3.213
-3.394
-3.910
-2.242
-3.234
-3.549
-4.225
1
2 4 Number of Blocks
8
best_val/logMSE
1
1.336
32
From Message-Passing to Linearized Graph Sequence Models
1 2 3 4
Figure 6. Ablation of the impact of scaling either information depth or processing depth with LGSM evaluated on the LRIM Graph Benchmark. We see that increasing either dimension has a positive effect, while solely increasing processing depth without incorporating additional information yields diminishing returns.
Figure 7. Measurements for varying number of layers on ER graphs of size 256. LGSM memory grows roughly linearly with L. Memory use is clearly driven by sequence length rather than number of blocks. The timing of LGSM stays almost constant over a range of small to medium graphs. For large graphs, the forward pass time of GPS blows up the most due to global attention, while LGSM stays between GCN and GPS.
24
From Message-Passing to Linearized Graph Sequence Models
Figure 8. Measurements for fixed number of layers (16) across multiple graph sizes. The timing of LGSM stays almost constant over a range of small to medium graphs. For large graphs, the forward pass time of GPS blows up the most due to global attention, while LGSM stays between GCN and GPS. LGSM memory use increases steadily with graph size, scaling linearly and better than GPS for large graphs.
25
From Message-Passing to Linearized Graph Sequence Models
G. Sequence Extraction −1
−1
We consider two different sequence extraction mechanisms. Let ÃG = DG 2 AG DG 2 be the normalized adjacency matrix, and let BG be the non-backtracking matrix as defined in Definition 6.1. Depending on the choice of matrix, the kth sequence (k) element is given by S(k) = ÃkG X and S(k) = BG X, respectively. We analyze the influence of different nodes in the sequence extraction. The influence of node w on the kth sequence element of v is defined as # # ! " " (k) (k) . X T ∂sv T ∂sv e e (7) Iv,k (w) = e e ∂xw ∂xu u∈V
where e is the all ones vector. Note that this definition is similar to the definition of influence distributions in (Xu et al., 2018), which analyzes influence distribution in a GNN, whereas we focus on the sequence extraction part. (k)
Proposition G.1. Let Z(k) be either BG or ÃkG . The influence of node w on the kth sequence element of v is given by (k) P (k) Iv,k (w) = Zvw / u∈V Zvu . Proof. Since feature dimensions are independent, we have # ( " (k) (k) ∂(sv )i Zvw i = j = ∂(xw )j 0 i ̸= j h (k) i (k) P (k) (k) ∂s Hence eT ∂xvw e = d · Zvw . After normalizing, Iv,k (w) = Zvw / u∈V Zvu We show that there can be an exponential difference between the influence of a node w on v, depending on which matrix is used for sequence extraction. A B Theorem 6.2 (Relative Influence of NBT). Let c < 1 and let Iv,k (w) (resp. Iv,k (w)) denote the influence of w on the kth sequence element of v captured using the adjacency sequence A (resp. non-backtracking B). There exists an infinite family A B of graphs G where Iv,k (w) decays exponentially faster with distance k compared to Iv,k (w): A Iv,k (w) B (w) Iv,k
≤ ck−1 ,
A Lemma G.2. Suppose v, w satisfy dist(v, w) = k and the radius-k neighborhood of v is a d-regular tree. Let Iv,k (w) (resp. B (k) k Iv,k (w)) denote the influence of w on the kth sequence element at v induced by adjacency extraction S = ÃG X (resp. (k) non-backtracking extraction S(k) = BG X). Then k−1 A Iv,k (w) d−1 = , B (w) d Iv,k A B and in particular Iv,k (w) is exponentially smaller than Iv,k (w) in k. (k)
Proof. Since dist(v, w) = k, there is exactly one path from v to w, which means (AkG )vw = 1 = (BG )vw . We have (ÃkG )vw = d−k , since for d-regular graphs, ÃkG = d−k AkG . To compute the influence distributions, we need to compute P the denominators. In Pa d-regular graph, the number of different walks of length k from v is dk , which is also given by u∈V (AkG )vu . Hence, u∈V (ÃkG )vu = dk /dk = 1. P (k) For the non-backtracking matrix, normalization is done by u∈V (BG )vu = d · (d − 1)k−1 , since a walk from node v can first use any of d edges and then only has d − 1 options for the next steps. Putting these together, we have A Iv,k (w)
d−k = = B (w) 1/d(d − 1)k−1 Iv,k
26
d−1 d
k−1