Scale-aware Message Passing for Graph Node Classification

Qin Jiang, Chengjia Wang, Michael Lones, Dongdong Chen, Wei PangSubmission to ICLR 2026 · Rejected

Abstract

Most Graph Neural Networks (GNNs) operate at the first-order scale, even though multi-scale representations are known to be crucial in domains such as image classification. In this work, we investigate whether GNNs can similarly benefit from multi-scale learning, rather than being limited to a fixed depth of $k$-hop aggregation. We begin by formalizing scale invariance in graph learning, providing theoretical guarantees and empirical evidence for its effectiveness. Building on this principle, we introduce ScaleNet, a scale-aware message-passing architecture that combines directed multi-scale feature aggregation with an adaptive self-loop mechanism. ScaleNet achieves state-of-the-art performance on six benchmark datasets, covering both homophilic and heterophilic graphs. To handle scalability, we further propose LargeScaleNet, which extends multi-scale learning to large graphs and sets new state-of-the-art results on three large-scale benchmarks. We also reinterpret spectral GNNs from a message-passing perspective, showing the equivalence between Hermitian Laplacian-based models and GraphSAGE with incidence normalization, and revealing that FaberNet’s strength largely arises from multi-scale feature integration. Together with these state-of-the-art results, our findings suggest that scale invariance may serve as a valuable principle for improving the performance of single-order GNNs. Code is available at \url{https://anonymous.4open.science/r/ScaleNet-2025/ }.
BibTeX
@misc{jiang2024scale,
  author = {Qin Jiang and Chengjia Wang and Michael Lones and Dongdong Chen and Wei Pang},
  title = {{Scale-aware Message Passing for Graph Node Classification}},
  year = {2024},
  eprint = {2411.19392},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.19392},
}
Figure