From Message-Passing to Linearized Graph Sequence Models

Graph neural networks (GNNs) have evolved rapidly, with message passing (Gilmer et al., 2017) becoming the dominant paradigm. These models aggregate neighbor information iteratively, enabling effective learning in domains like chemistry and social networks. However, as networks deepen, they encounter issues such as vanishing gradients and information dilution, limiting their ability to capture long-range dependencies. Recent advances in sequence modeling, notably Transformers (Vaswani et al., 2017) and state-space models (Gu & Dao, 2024), have demonstrated superior long-distance dependency modeling with parallel computation. Despite this, integrating these techniques into GNNs remains challenging due to structural preservation and computational constraints. Some approaches attempt to treat graphs as sequences or incorporate sequence models into message passing, but often rely on auxiliary encodings or suffer from scalability issues. This background underscores the need for a new framework that combines the strengths of sequence models with graph structures, addressing the limitations of existing methods.

Traditional message passing neural networks (MPNNs) are constrained by their coupled depth of information propagation and nonlinear processing, which hampers their ability to learn long-range dependencies effectively. Increasing network depth leads to issues like vanishing gradients and information loss, especially in large or complex graphs. While recent models like graph transformers attempt to address this, they often rely on structural encodings or auxiliary mechanisms that complicate training and scalability. The core problem is designing a model that can efficiently capture long-distance relationships without sacrificing structural fidelity or computational efficiency. Achieving this requires decoupling the information propagation process from nonlinear transformations, enabling deeper, more expressive models that are also scalable.

The key innovations include: 1) Introducing LGSM, which decouples information propagation from nonlinear processing, allowing for linear, parallel information flow via state-space models. 2) Employing non-backtracking sequence extraction to reduce redundancy and improve sensitivity to long-range dependencies. 3) Theoretically establishing bounds on node sensitivity that surpass traditional message passing limits, ensuring effective long-distance information capture. 4) Enabling stacking of multiple linearized blocks with nonlinear transformations only at the processing stage, improving training stability and scalability. These innovations collectively address the core bottleneck of deep GNNs, providing a theoretically grounded and practically efficient architecture for long-range dependency modeling.

• �� Sequence Extraction: Convert graph adjacency or non-backtracking matrices into sequences representing node relationships. • SSM Processing: Use models like Mamba to process sequences in parallel, enabling linear information flow. • Nonlinear Enhancement: Apply FFNs after SSM processing for expressive power. • Graph Mixing: Incorporate adjacency-based features to allow node interactions within sequences. • Layer Stacking: Stack multiple blocks to deepen the model, with nonlinear transformations only at the processing stage. • Optimization: Use residual connections and regularization for stable training. This approach separates the information propagation from nonlinear transformations, facilitating efficient, deep graph models.

The authors evaluate LGSM on LRIM and ECHO benchmarks, focusing on long-range dependency tasks. Datasets include synthetic graphs and molecular datasets like QM9. Baselines include GCN, Graph Transformer, and recent SSM-based models. Metrics involve accuracy, F1-score, and dependency length performance. Hyperparameters such as sequence length, number of layers, and SSM parameters are tuned. Ablation studies compare non-backtracking versus adjacency power sequences, analyze sensitivity bounds, and assess stacking effects. Results show LGSM achieves over 15% improvement in long-range tasks and 4% in molecular prediction, with stable training and better sensitivity control.

LGSM significantly outperforms baselines in capturing long-range dependencies, with over 15% accuracy gains on LRIM benchmarks. In molecular property prediction, accuracy improves by 4%, demonstrating practical relevance. Ablation confirms non-backtracking sequences reduce redundancy and enhance sensitivity. Multi-layer stacking maintains stability and boosts capacity. Theoretical bounds align with empirical results, confirming the effectiveness of decoupling information and processing depths, and the benefits of the non-backtracking mechanism for distant node interactions.

LGSM can be applied in large-scale graph analysis, drug discovery, social network modeling, and recommendation systems. Its ability to efficiently capture long-range dependencies makes it suitable for complex, real-world problems where structural information spans multiple hops. The framework's flexibility allows integration with existing GNN pipelines, requiring only graph structure and node features. Future applications could include dynamic graphs, heterogeneous data, and real-time systems, potentially transforming industries reliant on complex network analysis.

Computational complexity increases with graph size and sequence length, posing challenges for extremely large or dense graphs. Non-backtracking sequences, while reducing redundancy, may still face limitations in highly sparse or evolving graphs. The current framework primarily targets static, structured graphs; adapting to dynamic or heterogeneous graphs requires further research. Additionally, the reliance on state-space models like Mamba demands significant computational resources, which may limit deployment in resource-constrained environments.