HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models

HOPPER is an end-to-end learnable extension of Linearized Graph Sequence Models (LGSMs) that learns how hop sequences are extracted before they are processed by a state-space model. LGSMs address the coupling of information depth and processing depth in message-passing neural networks by treating the successive propagation states of each node as a sequence, but they construct these sequences using fixed graph operators. HOPPER replaces this fixed extractor with a learnable, permutation-equivariant map that supports feature-conditioned, structure-aware, graph- and hop-adaptive propagation mechanisms while preserving permutation equivariance.

The framework introduces four key ideas: a linear structural state accumulated across hops that is never normalized within the recurrence, a hypernetwork that produces hop-dependent propagation coefficients conditioned on a permutation-invariant graph summary and hop embedding, a finite memory window of size M, and a feature-attention term applied only to the output. The permutation-invariant graph summary is constructed by augmenting each initial node representation with one-hop neighborhood information, then using learnable seed queries to cross-attend to the node representations, producing a fixed-dimensional summary independent of graph size. The hypernetwork emits 3M+1 scalars per hop, conditioning the propagation rule on both the graph and information depth. The linear structural-state recurrence uses a window of the M previous structural states with combinations of adjacency, degree, and identity matrices, and the feature-attention correction modifies only the extracted state without introducing nonlinearities into the structural recurrence.

The theoretical analysis establishes four main results. First, HOPPER remains permutation equivariant despite conditioning its propagation rule on the input graph. Second, its structural states admit graph-adaptive finite-degree polynomial representations that retain finite-hop locality and contain standard LGSM propagators as special cases. Third, this richer polynomial family can achieve optimal long-range sensitivity under a common spectral stability constraint, with Chebyshev propagation improving first-arrival sensitivity by a factor of 2(r-1) over power propagation while remaining non-expansive. Finally, it can preserve nonstationary spectral information across information depth that vanishes under repeated adjacency propagation, with the Chebyshev sequence maintaining a nonvanishing fraction of nonstationary spectral content on average across hops.

Standard adjacency-based and non-backtracking LGSM sequences arise as special cases of the proposed extractor family. The paper proves that normalized-adjacency propagation, non-backtracking propagation, and Chebyshev propagation are all recovered as special cases of the HOPPER recurrence with appropriate coefficient choices.

Experimental evaluation on the ECHO-SYNTH benchmark shows HOPPER achieves the best performance on eccentricity and single-source shortest-path prediction while remaining competitive on diameter. On eccentricity, HOPPER achieves MSE of 6.571 ± 2.656 and MAE of 1.820 ± 0.386, compared to LGSM's 13.549 ± 0.539 MSE and 2.430 ± 0.070 MAE. On single-source shortest-path, HOPPER achieves MSE of 0.035 ± 0.002 and MAE of 0.021 ± 0.008, compared to LGSM's 0.040 ± 0.008 MSE and 0.076 ± 0.009 MAE. On diameter, HOPPER achieves MSE of 3.200 ± 0.528 and MAE of 0.973 ± 0.040, while LGSM achieves 3.089 ± 0.389 MSE and 0.859 ± 0.044 MAE.

On the LRIM-16 physics-based long-range dependency benchmark, the paper evaluates different memory window sizes M ∈ 2, 4, 8, 16, finding that M = 8 yields the best performance with log10(MSEtest) of −3.505 ± 0.063, compared to −3.451 ± 0.069 for M = 2, −3.440 ± 0.040 for M = 4, and −3.502 ± 0.081 for M = 16. This demonstrates that varying the maximum neighborhood size of message backtracking cancellation (structural memory window) can optimize accuracy.

The paper concludes that HOPPER achieves state-of-the-art or competitive results on the ECHO-SYNTH benchmark and that learnable sequence extraction provides a flexible and effective approach to long-range graph representation learning. The authors note that extending HOPPER to real-world molecular domains remains a natural direction for future work.

Improvements to AI systems:

1. Graph neural networks (GNNs) for long-range dependency tasks – Replace fixed propagation operators (e.g., adjacency, non-backtracking) with HOPPER’s learnable, hop-adaptive extractor. The improved system can dynamically adjust information propagation depth per node and per graph, avoiding over-smoothing and preserving long-range signals (e.g., in social network analysis, biological pathway modeling, or citation networks).

2. Sequence models on graphs – Integrate HOPPER’s linear structural-state recurrence with a finite memory window (M) into existing state-space models (e.g., Mamba, S4) for graph-structured data. The improved system can process graph sequences with bounded memory, enabling efficient training on large graphs while retaining sensitivity to distant nodes (e.g., in traffic forecasting or protein interaction networks).

3. Permutation-equivariant feature-conditioned propagation – Use HOPPER’s hypernetwork to generate propagation coefficients conditioned on a permutation-invariant graph summary and hop embedding. The improved system can adapt its message-passing rules to the local graph topology and node features, improving performance on tasks where structure varies widely (e.g., molecular property prediction, 3D point cloud segmentation).

4. Chebyshev-based propagation for spectral stability – Adopt HOPPER’s Chebyshev polynomial propagation as a drop-in replacement for power-based adjacency propagation in any GNN. The improved system can achieve exponentially better first-arrival sensitivity (factor 2(r-1)) while remaining non-expansive, making it robust to noise and better at capturing nonstationary spectral content (e.g., in recommendation systems or anomaly detection on graphs).

5. Memory-window optimization – Use HOPPER’s finding that M=8 outperforms other window sizes on LRIM-16 to design adaptive memory mechanisms. The improved system can automatically tune the structural memory window per task or dataset, balancing computational cost and accuracy (e.g., in real-time graph analytics or streaming graph processing).

6. Hybrid feature-attention output correction – Apply HOPPER’s feature-attention term only at the output layer, without introducing nonlinearities into the structural recurrence. The improved system can combine linear, stable propagation with expressive feature-based attention, reducing training instability and improving generalization (e.g., in semi-supervised node classification or link prediction).

Graph neural networks typically propagate information through repeated message-passing layers, coupling the distance over which information travels with the number of nonlinear transformations applied. This coupling can make deep architectures difficult to optimize and can lead to over-smoothing, over-squashing, and the loss of long-range information. Linearized Graph Sequence Models (LGSMs) address this issue by separating information depth from processing depth and treating the successive propagation states of each node as a sequence. However, existing LGSMs construct these sequences using fixed graph operators, limiting their ability to adapt propagation to the input graph, node features, and downstream task. We introduce HOPPER, an end-to-end learnable extension of LGSM that learns how hop sequences should be extracted before they are processed by a modern state-space model. Our framework supports feature-conditioned, structure-aware, graph- and hop-adaptive propagation mechanisms while preserving permutation equivariance. Standard adjacency-based and non-backtracking LGSM sequences arise as special cases of our proposed extractor family. We show that HOPPER is state-of-the-art or competitive across the ECHO-Synth benchmark, and that varying the maximum neighborhood size of message backtracking cancellation (i.e. structural memory window) can optimize accuracy on the LRIM physics-based long-range dependency benchmark. These results demonstrate that learnable sequence extraction provides a flexible and effective approach to long-range graph representation learning.