HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models

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, with standard adjacency-based and non-backtracking LGSM sequences arising as special cases of our extractor family. We show that HOPPER is state-of-the-art or competitive across the ECHO-Synth benchmark and performs strongly on the City-Networks dataset. On the LRIM physics-based long-range dependency benchmark, we find that varying the maximum neighborhood size of message-backtracking cancellation, corresponding to the structural memory window, can substantially affect performance. Ablation studies further isolate the contributions of the learnable extraction mechanism and its structural and feature-adaptive components, demonstrating that adaptive hop-sequence construction is important beyond the downstream sequence model alone. Together, these results show that learnable sequence extraction provides a flexible and effective approach to long-range graph representation learning across synthetic, physics-based, and real-world graph benchmarks.