🤖 machine learning

HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models

The paper introduces HOPPER, an end-to-end learnable framework that enhances Linearized Graph Sequence Models by adaptively extracting feature- and structure-aware hop sequences to overcome the limitations of fixed graph operators in long-range graph representation learning.

Original authors: Isuru Herath, Arin Gopakumar, Sharan Sahu

Published 2026-08-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Isuru Herath, Arin Gopakumar, Sharan Sahu

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

Imagine you are trying to teach a computer to understand a map of a city, but instead of a grid of streets, the map is a tangled web of connections between people, ideas, or atoms. This is the world of Graph Neural Networks (GNNs), a branch of artificial intelligence dedicated to learning from these messy, interconnected webs. The standard way these networks learn is by passing notes: a node (like a person) looks at its immediate neighbors, gathers their info, and passes a summary to its own neighbors. This is called "message passing."

The problem arises when the computer needs to understand connections that are far apart. To get a message from one side of the city to the other, the network has to pass the note through many, many layers of people. But here's the catch: every time the note is passed, it gets "processed" by a complex filter that changes its meaning. If you have to pass the note 20 times to cross the city, you also have to run it through 20 different filters. This tight coupling causes the message to get muddled, squashed, or smoothed out until it loses all its unique details. It's like trying to whisper a secret across a crowded stadium; by the time it reaches the other side, it's just a blur of noise. Scientists have been trying to untangle this knot to help AI see the "long-range" connections that matter, like how a single spark can start a forest fire miles away.

Enter HOPPER, a new approach that tries to solve this by changing the rules of the game. Instead of forcing the computer to process the message while it travels, HOPPER suggests a two-step strategy: first, let the message travel all the way across the map to gather all the raw information it needs, and then process that information. Think of it like a courier service. In the old way, the courier stops at every house to fill out a complicated form before moving to the next house. In HOPPER's way, the courier runs a fast, unfiltered sprint to collect a stack of raw data from every house along the route, and only after reaching the destination does a smart analyst sit down to read and interpret that stack.

The paper introduces HOPPER as a "learnable hop extraction" system. In previous attempts to use this "run first, analyze later" method (called Linearized Graph Sequence Models), the rules for how the courier ran were fixed. They always took the same path, regardless of whether the city was a grid, a tree, or a chaotic mess. HOPPER changes this by teaching the courier how to run. It uses a special "hypernetwork"—a tiny AI that acts like a coach—to watch the map and the data, then decides the best way to gather information for that specific situation. It can choose to skip certain houses, focus on specific types of neighbors, or adjust its speed based on the terrain.

The researchers found that this flexible approach works incredibly well. When tested on synthetic puzzles designed to be hard for AI to solve (like predicting the longest distance between any two points in a random network), HOPPER beat or matched the best existing models. Specifically, it achieved the best results for predicting "eccentricity" (how far a node is from the furthest point) and "single-source shortest paths" (the quickest route from one point to all others). On a physics-based benchmark called LRIM-16, which involves predicting energy changes in a grid of magnetic spins, the model's performance depended on how much "structural memory" it kept; the best results came when the model remembered the last 8 steps of its run.

The paper also proves mathematically that HOPPER doesn't break the fundamental rules of symmetry; it doesn't matter how you label the nodes, the result stays the same. Furthermore, it shows that HOPPER can mimic the old, fixed methods if it wants to, but it can also invent new ways of gathering information that are mathematically proven to be better at preserving long-distance details without losing stability. By separating the act of traveling from the act of thinking, HOPPER suggests that we can build AI that understands the big picture of a complex web without getting lost in the details or forgetting the beginning of the story.

Technical Summary: HOPPER – Learnable Hop Extraction for Linearized Graph Sequence Models

1. Problem Statement

Graph Neural Networks (GNNs), particularly Message-Passing Neural Networks (MPNNs), face fundamental challenges in modeling long-range dependencies. In standard MPNNs, the distance information travels (information depth) is tightly coupled with the number of nonlinear transformations applied (processing depth). To capture information from nodes $r$ hops away, a model requires at least $r$ layers. This coupling leads to optimization difficulties, over-smoothing (loss of node identity), and over-squashing (compression of large neighborhoods into fixed-dimensional vectors), which severely limits performance on tasks requiring global context.

Linearized Graph Sequence Models (LGSMs) were proposed to decouple these dimensions. LGSMs treat the successive propagation states of each node as a sequence over information depth, allowing a modern sequence model (e.g., a State-Space Model) to process these states independently of node ordering. However, existing LGSMs rely on fixed graph operators (such as normalized adjacency powers or non-backtracking recurrences) to construct these sequences. These fixed rules cannot adapt to specific graph structures, node features, or the varying utility of different neighborhood ranges across different tasks and information depths. Consequently, the downstream sequence model may be forced to compensate for suboptimal propagation strategies imposed by the fixed extractor.

2. Methodology: HOPPER

The authors introduce HOPPER, an end-to-end learnable extension of LGSM that learns how hop sequences are extracted before they are processed by a state-space model. HOPPER preserves the separation of information depth and processing depth while introducing adaptivity through four key components:

2.1 Permutation-Invariant Graph Summary

To condition propagation on the input graph without violating permutation equivariance, HOPPER first constructs a fixed-dimensional graph summary ( $h_{graph}$ ).

Node features are augmented with one-hop neighborhood information ( $H_{nbr} = A_{rw}H$ ).
A set of learnable seed queries ( $Q_s$ ) cross-attends to these augmented node representations.
The resulting latent representation is vectorized to form $h_{graph}$ . This summary is invariant to node ordering and independent of graph size.

2.2 Hop-Conditioned Coefficient Generation

A hypernetwork generates propagation coefficients conditioned on both the global graph summary ( $h_{graph}$ ) and a specific hop embedding ( $e_k$ ).

The hypernetwork outputs scalars ( $\alpha_A, \alpha_D, \alpha_I, \beta$ ) that determine the linear combination of structural operators at each hop.
This allows the propagation rule to vary across different graphs and adapt dynamically as information depth increases.

2.3 Linear Structural-State Recurrence

The core of the extractor is a linear recurrence that accumulates a structural state $U^{(k)}$ over a finite memory window of size $M$ :
$U^{(k)} = \sum_{j=1}^{M} \left( \alpha_A^{(k)}[j]A + \alpha_D^{(k)}[j]D + \alpha_I^{(k)}[j]I \right) U^{(k-j)}$

$U^{(0)} = H$ (initial features).
The recurrence uses unnormalized adjacency ( $A$ ) and degree ( $D$ ) matrices to maintain exact polynomial structure, though normalized variants are used for numerical stability in deep sequences.
Crucially, normalization and non-linearities are kept outside the recurrence to preserve the algebraic properties required to recover fixed LGSM extractors.

2.4 Feature-Attention Correction

To enrich the extracted sequence without introducing non-linearities into the structural recurrence, a feature-attention term is applied only to the output state:
$S^{(k)} = \text{LayerNorm}\left( U^{(k)} + \beta_k F_k U^{(k)} \right)$
where $F_k$ is an attention matrix computed from the original node features. This allows the model to correct or weight the structural state based on feature content.

The resulting sequence $S$ is processed by a stack of Mamba2-based State-Space Model (SSM) blocks, which operate independently on each node's sequence.

3. Key Contributions and Theoretical Properties

The paper establishes several theoretical guarantees regarding HOPPER:

Permutation Equivariance: Despite conditioning propagation on a learned graph summary, HOPPER remains permutation equivariant. Relabeling the input graph results in the same permutation applied to the extracted node sequences, ensuring the model does not depend on arbitrary node orderings.
Graph-Adaptive Polynomial Structure: The structural states correspond to finite-degree non-commutative polynomials in $A$ and $D$ . Conditional on the hypernetwork coefficients, the $k$ -th state propagates information over at most $k$ hops. However, the coefficients themselves adapt to the graph and features, allowing the propagation rule to change dynamically.
Recovery of Fixed Extractors: HOPPER is a generalization of existing LGSMs. By setting specific coefficients, it can exactly recover:
- Normalized-adjacency propagation ( $S = A_{sym}$ ).
- Non-backtracking propagation.
- Stable Chebyshev propagation (which is non-expansive).
Optimal Long-Range Sensitivity: Under a uniform spectral stability constraint (where the propagator norm is $\le 1$ ), the paper proves that Chebyshev propagation (realizable by HOPPER) achieves the maximal possible first-arrival sensitivity ( $2^{r-1}$ times that of standard power propagation) for nodes at distance $r$ .
Mitigation of Over-Smoothing: Theoretical analysis shows that while repeated adjacency propagation causes non-stationary spectral information to vanish (over-smoothing), the Chebyshev sequence preserves a non-vanishing fraction of this information across the sequence depth.

4. Experimental Results

HOPPER was evaluated on two benchmarks:

ECHO-SYNTH (Synthetic Graph Properties):
- Tasks: Graph diameter (DIAM), node eccentricity (ECC), and single-source shortest-path (SSSP) prediction.
- Results: HOPPER achieved state-of-the-art performance on ECC (MSE: 6.571 vs. LGSM's 13.549) and SSSP (MSE: 0.021 vs. LGSM's 0.040). It remained competitive on DIAM, slightly trailing the best LGSM variant but outperforming all other baselines including Graph Transformers and rewiring methods.
LRIM-16 (Physics-Based Long-Range Dependency):
- Task: Node-level energy regression on 16x16 periodic Ising grids with long-range interactions.
- Results: Performance varied with the structural memory window size $M$ . A window size of $M=8$ yielded the best results (log10 MSE: -3.505), demonstrating that the amount of structural memory retained during extraction significantly impacts performance on physics-based tasks.

5. Significance and Claims

The paper claims that HOPPER provides a flexible and effective approach to long-range graph representation learning by making the sequence extraction process learnable.

Decoupling: It successfully decouples information depth from processing depth, allowing deep propagation without the compounding non-linearities that cause over-smoothing and over-squashing in traditional GNNs.
Adaptivity: Unlike fixed LGSMs, HOPPER adapts its propagation strategy to the specific graph structure, node features, and information depth, avoiding the suboptimal sequences that fixed operators might produce.
Theoretical Grounding: The framework is not just empirically effective but theoretically grounded, showing that it can recover established propagation schemes while offering a richer class of graph polynomials that optimize long-range sensitivity and preserve spectral information.
Future Work: The authors note that extending HOPPER to real-world molecular domains is a natural direction for future work, but they do not claim current success in that specific domain.

In summary, HOPPER demonstrates that learnable sequence extraction, combined with modern state-space models, offers a superior alternative to fixed propagation rules for capturing long-range dependencies in graphs.