Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation
MD Sazzad Hossen, Avimanyu Sahoo, MD Sazzad Hossen, Avimanyu Sahoo · 2026
Read Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation by MD Sazzad Hossen, Avimanyu Sahoo, MD Sazzad Hossen, Avimanyu Sahoo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-10975.txt.
Introduction
MD Sazzad Hossen and Avimanyu Sahoo introduce a hierarchical multi-scale graph network for heterophilous learning, where linked nodes often carry different labels. Existing spectral graph networks for such graphs suffer hub-dominated aggregation and oversmoothing, as weak polynomial filters blur distant signals.
Their Hierarchical Multi-view HAAR framework learns heterophily-aware signed affinities, builds a soft graph hierarchy from those embeddings, and applies learnable spectral filters through sparse, orthonormal, locality-aware Haar bases at each level. Skip-connection unpooling then recombines all levels into the original graph, curbing hub domination and long-range bottlenecks. Tests show gains up to about three percent over leading spectral baselines, in near-linear time. Graph-learning teams get a scalable cure for heterophily's twin ailments.
Catalog record
| CREATOR | MD Sazzad Hossen, Avimanyu Sahoo, MD Sazzad Hossen, Avimanyu Sahoo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97604 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.10975
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation MD Sazzad Hossen, Avimanyu Sahoo, MD Sazzad Hossen, Avimanyu Sahoo Abstract Graphs with heterophily, where adjacent nodes carry different labels, are prevalent in real-world applications, from social networks to molecular interactions. However, existing spectral Graph Neural Network (GNN) approaches tailored for heterophilous graph classification suffer from hub-dominated (node with large degree) aggregation and oversmoothing, as their suboptimal polynomial filters introduce approximation errors and blend distant signals. To address the degree-biased aggregation and suboptimal polynomial filtering, we introduce a Hierarchical Multi‐view HAAR (HMH), a novel spectral graph‐learning framework that scales in near‑linear time . HMH first learns feature- and structure-aware signed affinities via a heterophily-aware encoder, then constructs a soft graph hierarchy guided by these embeddings. At each hierarchical level, HMH constructs a sparse, orthonormal, and locality-aware Haar basis to apply learnable spectral filters in the frequency domain. Finally, skip-connection unpooling layers combine outputs from all hierarchical levels back into the original graph, effectively preventing hub domination and long-range signal bottleneck (over-squashing). Experimentation shows that HMH outperforms state‑of‑the‑art spectral baselines, achieving up to a 3 % 3\% improvement on node classification and 7 % 7\% points on graph classification datasets, all while maintaining linear scalability. 1 Introduction Real-world graphs are rarely uniform: some regions are relatively homogeneous with nearby nodes sharing similar features and connectivity, while others are heterophilous, where neighbors differ sharply in both attributes and structure. In graph learning, homogeneous areas typically benefit from smoothing/averaging (low-pass filtering), whereas heterophellous regions require contrast amplification (high-pass filtering) ( Chien et al., 2021 ) . Spectral Graph Neural Networks (GNNs) aim to capture such signals by projecting onto a global eigenbasis of the graph Laplacian or its polynomial approximation ( Zhu & Koniusz, 2021 ) . Using a global basis, whether it is explicitly precomputed ( He et al., 2022 ) or implicitly approximated using high-order polynomials ( Huang et al., 2024 ) , often sacrifices graph locality. The induced filters can spread energy across many hops and mix signals from semantically unrelated regions, which may blur fine-grained structural distinctions among small clusters that are especially important under heterophily ( He et al., 2022 ) . In addition, conventional polynomial bases (e.g., Chebyshev) are limited by the conditioning of polynomial parameterizations on graphs. In the theoretical setting, Chebyshev polynomials are orthogonal on [-1,1] under a continuous weight function ( w(x)=1/\sqrt{1-x^{2}} ). Although graph filters rescale the Laplacian spectrum to [-1,1] , a real graph does not provide this continuous weighting since it is governed by a discrete spectral measure (the rescaled eigenvalues and their multiplicities), leading to leakage across frequency channels and reduced effective expressivity of the filter bank ( Guo & Wei, 2023 ) . Moreover, high-order polynomial approximations can be prone to error and the resulting bases are typically static and not adaptive to local feature/structure heterophily ( Huang et al., 2024 ; Zheng, 2024 ) . On the other hand, spatial GNNs filter graph signals directly by employing neighborhood aggregation and often exhibit an inherent low-pass bias ( Zhu & Koniusz, 2021 ) . To address this, recently proposed signed message-passing methods (SMPs) incorporate edge signs to learn the contrast between the node signals. SMP based models suffer from sign cancellation across depth (e.g., every two layers), progressively erasing heterophilous contrasts ( Liang et al., 2024 ) . To prevent signal-signed flipping, several spatial models employ Chunked Message Passing (CMP) approaches, which bucketize neighbors by similarity and subsequently consolidate all chunks/buckets via a global aggregation step ( Pei et al., 2024 ) . Both approaches mix signals across graph regions. This mixing is particularly detrimental in degree-imbalanced graphs: densely connected, high-degree hub nodes can dominate message passing, eroding the signals of small (spoke) heterophilous clusters, leading to indistinguishable features (hub domination) and ultimately exacerbating signal oversmoothing ( Keriven, 2022 ) . These limitations motivate a filter that is (i) spectrally well-conditioned to prevent leakage across frequency channels, (ii) localized to avoid long-range contamination, and (iii) learns high-pass and low-pass filters without sign cancellation pathology. Figure 1 : Overview of the proposed HMH framework. The process begins with the input graph and node features, followed by adaptive heterophilous encoding and hierarchical graph coarsening. At each level, class-aware Haar bases are constructed, and diagonal spectral filtering is performed. Finally, multi-scale skip-connected fusion aggregates information from all levels. To address the existing limitations, we propose a novel model, referred to as HMH. The HMH first introduces an adaptive heterophilous encoder that assigns positive weights to homophilous edges and persistent negative weights to heterophilous edges. The encoder is also designed to serve as an adaptive high-pass and low-pass filter, thereby preserving the high‑frequency contrasts that conventional static methods typically fail. The encoder also incorporates structural similarity and feature affinities to generate per-node scores that facilitate hierarchical clustering (coarsening). At each hierarchical level, the encoder is used to construct the Haar basis, which forms a sparse, orthonormal eigenbasis explicitly capable of capturing localized low-frequency (within-cluster) and high-frequency (between-cluster) variations. Diagonal spectral filtering in this basis selectively amplifies heterophilous channels and attenuates hub-dominated signals. Skip-connected unpooling is employed to reintegrate filtered signals from each level into the original nodes, enriching them with multi-scale context. The coarsening hierarchy reduces effective path lengths logarithmically, allowing gradients and information to propagate without the exponential decay caused by oversquashing ( Di Giovanni et al., 2023 ) . Finally, we leverage the hierarchical tree to perform graph pooling for graph classification, reducing the pooling overhead from quadratic O(n^{2}) in prior methods to near-linear O(n) time ( Li et al., 2024 ) . The contributions of the paper are: (i) We introduce a label-free adaptive signed affinity that prevents sign cancellation. (ii) We introduce the first framework that constructs an orthonormal, multi-scale, sparse spectral basis in near-linear time, scaling effortlessly to large graphs; (iii) We rigorously prove and empirically confirm that conventional GNNs suffer from hub domination , oversmoothing , and oversquashing , whereas our proposed HMH overcomes these pathologies; and (iv) we demonstrate that HMH achieves state‑of‑the‑art (SOTA) accuracy on both node and graph classification tasks while maintaining linear scalability. 2 Related works Spectral Filtering: Early models, like ChebNet ( He et al., 2021 ) , used truncated Chebyshev polynomials to approximate the eigenbasis. Conversely, Generalized Page Rank GNN (GPR-GNN) ( Chien et al., 2021 ) utilizes generalized PageRank weights with monomial bases for approximations. In contrast, BernNet ( He et al., 2021 ) and JacobiConv ( Wang & Zhang, 2022 ) provide Bernstein and Jacobi polynomials, respectively, to enhance the interpretability and adaptability of the bases. ChebNetII ( He et al., 2022 ) addressed the issue of Chebyshev polynomials overfitting by employing interpolation, whereas OptBasisGNN ( Guo & Wei, 2023 ) aimed to make basis polynomials orthogonal to accelerate convergence. The above methodologies continue to employ dense, fixed graph-wide bases that prevent global message mixing. Hierarchical Graph Learning: Learnable pooling methods, such as DiffPool ( Ying et al., 2018 ) , SAGPool ( Lee et al., 2019 ) , TopKPool ( Diehl, 2019 ) , utilize node-scoring to coarsen homophilous graphs at a singular resolution incurring O(n^{2}) computational cost ( Li et al., 2024 ) .