HOPPER: Learnable Hop Extraction for Linearized Graph Sequence Models
2026-08-10 • Machine Learning
Machine Learning
AI summaryⓘ
The authors explain that typical graph neural networks struggle to pass information over long distances without losing important details or becoming hard to train. They improve a type of model called Linearized Graph Sequence Models (LGSMs) by creating HOPPER, which learns how to choose the best paths for spreading information on graphs, instead of using fixed rules. HOPPER adapts based on the graph's structure and features, making it better at capturing long-range relationships in data. Their tests show HOPPER works well compared to other methods, especially for tasks needing knowledge from far-apart parts of the graph.
Graph Neural NetworksMessage PassingLinearized Graph Sequence ModelsLong-range DependenciesPermutation EquivarianceState-space ModelsGraph PropagationHop SequencesOver-smoothingBacktracking Cancellation
Authors
Isuru Herath, Arin Gopakumar, Sharan Sahu
Abstract
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.