A Structure-Aware Higher-Order Message Passing Framework on Walk States for Graph Classification

Standard Message Passing Neural Networks (MPNNs) are at most 1-WL expressive, which has spurred the development of higher-order models. In particular, many higher-order designs rely on extra global structural features (e.g., positional encodings or pairwise distances), whereas the $k$-WL hierarchy offers a principled and quantifiable path to increased expressiveness. However, directly simulating $k$-WL is computationally prohibitive, and existing $k$-WL variants often sacrifice expressiveness to gain efficiency, failing to capture critical structural distinctions. To overcome these shortcomings, we propose a higher-order graph learning framework based on walk-induced lifted states with structure-aware state encoding. We further design a controllably sparsified and localized $k$-FWL-style aggregation scheme, enabling graph-level higher-order representations via simple message passing. On the recent and challenging BREC expressiveness benchmark, our model achieves state-of-the-art total distinguishing accuracy among compared higher-order GNN baselines, outperforming strong 3-WL baselines, and remains competitive on real-world graph classification tasks.