arXiv:2505.15015v2 Announce Type: replace
Abstract: Most Graph Neural Networks (GNNs) propagate messages by treating node embeddings as holistic feature vectors, implicitly assuming uniform relevance across feature dimensions. This limits their ability to selectively transmit informative components, especially when graph structures exhibit distinct frequency characteristics. We propose MSH-GNN (Multi-Scale Harmonic Graph Neural Network), a frequency-aware message passing framework that performs feature-wise adaptive propagation. Each node projects incoming messages onto node-conditioned feature subspaces derived from its own representation, enabling selective extraction of frequency-relevant components. Learnable multi-scale harmonic modulations further allow the model to capture both smooth and oscillatory structural patterns. A frequency-aware attention pooling mechanism is introduced for graph-level readout. We show that MSH-GNN admits an interpretation as a learnable Fourier-feature approximation of kernelized message functions and matches the expressive power of the 1-Weisfeiler-Lehman (1-WL) test. Extensive experiments on node- and graph-level benchmarks demonstrate consistent improvements over state-of-the-art methods, particularly in joint structure-frequency analysis tasks.