🤖 machine learning

From Message-Passing to Linearized Graph Sequence Models

This paper introduces Linearized Graph Sequence Models, a framework that recasts message-passing graph computation as sequence modeling to decouple processing depth from information propagation, thereby enabling the integration of modern sequence modeling advances to improve long-range information tasks in graphs.

Original authors: Joël Mathys, Basil Rohner, Saku Peltonen, Roger Wattenhofer

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joël Mathys, Basil Rohner, Saku Peltonen, Roger Wattenhofer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Telephone Game" on a Graph

Imagine you have a huge group of friends (a graph) connected by phone lines. You want to tell a secret to one person, but you want everyone in the group to eventually hear it.

In the current standard way of doing this (called Message-Passing or MPNNs), the process works like a game of "Telephone" where every time a person passes the message to a neighbor, they also have to rewrite the message in their own unique handwriting (applying a complex, non-linear transformation).

The Issue: If the group is huge, the message has to travel many hops to reach the person at the other end. Because every single hop involves rewriting the message, the original information gets distorted, lost, or "squashed" by the time it arrives. It's like trying to copy a drawing 50 times; by the 50th copy, you can't recognize the original picture anymore. Also, because you have to wait for one person to finish rewriting before passing it to the next, the whole process is slow and hard to speed up.

The New Solution: LGSM (Linearized Graph Sequence Models)

The authors propose a new framework called LGSM. They realized that the two main jobs in this process—moving the message (propagation) and rewriting the message (processing)—are being done at the same time, which causes the problems above.

The Analogy: The Assembly Line vs. The Courier Service

Think of the old method as a courier who stops at every house to write a new version of the letter before handing it to the next person.

LGSM changes the workflow into two distinct steps:

Step 1: The Linear Flow (The Courier Service)
First, the message travels across the entire network of friends without anyone rewriting it. It just flows through the connections. In the paper's language, this is linearizing the computation. The message travels from Person A to Person Z purely based on the connections, keeping the original information intact. This is like a high-speed train moving through stations without stopping to change the cargo.
Step 2: The Processing (The Assembly Line)
After the message has traveled all the way across the network, then we apply the complex "rewriting" (non-linear transformations). We take the full, clear message and process it.

Why is this better?

No Distortion: Because the message traveled without being rewritten at every step, the information from far away friends arrives clearly.
Speed: Because the message is just flowing linearly, we can use modern, super-fast computer tricks (called State-Space Models or SSMs, like the "Mamba" architecture) to process the whole chain at once, rather than waiting for one step to finish before starting the next.

The Secret Ingredient: How to Pack the Message

The paper also asks: How do we turn a messy web of friends into a neat list (sequence) for the computer to read?

The authors found that the way you list the friends matters.

The Old Way (Adjacency Powers): Imagine listing friends by saying, "Here is everyone I know, and here is everyone their friends know, and here is everyone their friends' friends know." The problem is, this list gets full of duplicates. You might list the same person three times because they can be reached via three different paths. This creates "noise" and confusion.
The New Way (Non-Backtracking): The authors suggest a smarter way to list them. Imagine walking through the network but never immediately turning back the way you came. If you walk from Alice to Bob, you don't immediately walk back to Alice. This "Non-Backtracking" method ensures that every step in your list brings you something new and unique, rather than repeating old information.

What Did They Prove?

Theory: They used math to show that by separating the "traveling" from the "rewriting," the model can actually "see" and learn from friends who are very far away, which older models struggle to do.
Experiments: They tested this on two types of tasks:
- Synthetic Graphs: Made-up networks designed to be very hard, requiring information to travel long distances (like finding the shortest path between two distant points). LGSM crushed these tasks.
- Real Molecules: They tested it on predicting properties of chemical molecules. Since atoms in a molecule can affect each other from far away, this is a perfect test. LGSM performed very well, showing it works on real-world data too.

Summary

The paper introduces LGSM, a new way to teach computers to understand networks (graphs). Instead of rewriting a message at every single step of the journey (which causes errors), LGSM lets the message travel cleanly across the whole network first, and then processes it. They also figured out a smarter way to organize the data (using "non-backtracking" paths) to avoid redundancy. The result is a system that is faster, clearer, and much better at understanding long-distance connections in data.

Technical Summary: From Message-Passing to Linearized Graph Sequence Models

1. Problem Statement

Message-Passing Neural Networks (MPNNs) have established themselves as the dominant architecture for learning on graph-structured data. However, they face fundamental limitations when scaling to capture long-range dependencies. In standard MPNNs, information propagation (gathering information from distant nodes) and non-linear processing (transforming that information) are tightly coupled; each layer advances information by one hop while simultaneously applying a non-linear transformation.

This coupling creates two critical issues:

Over-squashing and Information Loss: As network depth increases to reach distant nodes, fixed-size node embeddings must compress an exponentially growing receptive field, leading to information loss and the collapse of learned representations.
Optimization Difficulties: The repeated stacking of non-linearities in deep networks leads to vanishing gradients and instability, making the training of deep MPNNs challenging.

While modern deep learning has seen rapid advancements in sequence modeling (e.g., Transformers, State-Space Models like Mamba) which excel at capturing long-range dependencies efficiently, adapting these to graphs is non-trivial. Existing attempts often struggle to preserve graph inductive biases or reintroduce the very problem of accumulated non-linearities by stacking modules sequentially.

2. Methodology: Linearized Graph Sequence Models (LGSM)

The authors introduce Linearized Graph Sequence Models (LGSM), a framework that recasts graph learning from the perspective of sequence modeling by explicitly decoupling two fundamental dimensions of computation:

Information Depth: How far information propagates through the graph topology.
Processing Depth: How many non-linear transformations are applied to the data.

Core Architecture

Unlike standard MPNNs where these dimensions advance diagonally (simultaneously), LGSM linearizes the propagation along the information axis. The architecture consists of four main components:

Sequence Extraction: The input graph features $X$ and adjacency matrix $A_G$ are converted into a sequence of node embeddings $S^{(0)}_{in}, \dots, S^{(L-1)}_{in}$ . This sequence represents the state of information at different "hops" or steps of propagation.
SSM Layer: The extracted sequence is processed by a State-Space Model (specifically Mamba2). Crucially, the SSM operates independently on each node's sequence, allowing information to flow along the sequence dimension (information depth) via efficient parallel scan computations without accumulating non-linearities.
Feed-Forward Network (FFN): Non-linear transformations are applied to the sequence elements after the SSM processing, confined to the processing depth dimension.
Graph Mixing: To ensure information mixing between different nodes, the sequence elements are updated with graph-propagated features from the preceding element before the next block. This step reintroduces topological mixing without increasing the information depth.

The model stacks $D$ such blocks. The separation allows the use of modern SSM implementations to handle long sequences (large information depth) efficiently, while non-linearities are applied in a controlled manner.

Sequence Extraction Mechanisms

The paper analyzes what makes a sequence extraction mechanism effective. It identifies five desirable properties: efficiency, stability, informativeness, sensitivity, and relative influence.

Adjacency Powers: Using powers of the adjacency matrix ( $A_G^k$ ) is a natural choice but suffers from "backtracking" (immediately traversing an edge in reverse), which introduces redundant information and causes numerical instability for long sequences.
Non-Backtracking (NBT) Walks: The authors propose using the non-backtracking matrix $B_G$ , which counts paths that do not immediately reverse direction. Theoretical analysis shows that NBT sequences maintain stronger relative influence for distant nodes compared to adjacency powers, as they avoid the exponential decay of signal caused by redundant backtracking paths.

3. Key Contributions

Framework Introduction: The proposal of LGSM, which decouples information propagation depth from processing depth, allowing core graph architectural decisions to be reframed as sequence modeling choices.
Theoretical Analysis: A rigorous theoretical characterization of node sensitivity in LGSM. The authors prove that the sensitivity of the final output to input features depends on the weighted sum of all sequence elements. This establishes that effective learning relies on the sequence extraction mechanism capturing node pair relationships, rather than solely on the depth of non-linear stacking.
Novel Extraction Method: The proposal and validation of non-backtracking walk sequences, which theoretically and empirically offer superior properties for long-range information propagation compared to standard adjacency powers.
Empirical Validation: Comprehensive evaluation on synthetic and real-world benchmarks demonstrating that LGSM effectively handles long-range tasks.

4. Experimental Results

The authors evaluated LGSM on the ECHO benchmark (ECHO-Synth and ECHO-Chem) and the LRIM Graph Benchmark.

Synthetic Graph Tasks (ECHO-Synth): LGSM demonstrated strong performance on tasks requiring long-range information exchange, such as predicting graph diameter, node eccentricity, and single-source shortest paths. Notably, LGSM significantly outperformed standard MPNNs (GCN, GIN) and other advanced baselines (GPS, GRIT) on eccentricity prediction, a task known to be difficult for deep MPNNs due to over-squashing.
Molecular Property Prediction (ECHO-Chem): On tasks predicting atomic partial charges and total molecular energy, LGSM achieved strong performance, comparable to or better than baselines, demonstrating its applicability to real-world datasets requiring non-local atomic interactions.
LRIM Benchmark: On the LRIM-16-hard dataset, designed to test provable long-range interactions, LGSM surpassed message-passing baselines and approached the performance of computationally expensive Transformer-based approaches.
Ablation Studies: Experiments confirmed that increasing sequence length (information depth) consistently improves performance on long-range tasks, whereas increasing only processing depth yields diminishing returns without sufficient information depth. The use of non-backtracking sequences consistently outperformed adjacency powers.
Peptides Dataset: On the Peptides LRGB datasets, LGSM performed similarly to standard message-passing methods. The authors note this is likely because recent techniques on these datasets already achieve strong performance with shallow architectures, suggesting that the specific benefits of LGSM are most pronounced in scenarios requiring deep information propagation.

5. Significance and Claims

The paper claims to provide a principled way to integrate modern sequence modeling advances into message-passing based graph learning. By separating processing and information depth, LGSM reframes central architectural questions (such as how to handle over-squashing) as input modeling choices (specifically, how to extract the sequence).

The authors emphasize that their work demonstrates how this separation:

Enables information to flow across arbitrary graph distances while confining non-linear transformations to the processing dimension.
Leverages efficient parallel computation via State-Space Models.
Ensures proper information and gradient flow throughout the network.
Shifts the focus of graph learning design toward the modeling of sequence extraction, offering a theoretically grounded alternative to the traditional stacking of deep MPNN layers.

The paper concludes modestly, acknowledging that while LGSM is designed for efficiency, the specific computational trade-offs (e.g., preprocessing vs. runtime) were not the primary focus, and that other factors like regularization also impact performance. However, the framework offers a new perspective for understanding and designing graph neural networks.