# Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation

arXiv: https://arxiv.org/abs/2605.10975 · HTML: https://mlsanity.com/paper/2605.10975/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 39 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 26 of 26)

- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Graph Convolutional Networks with EigenPooling](https://mlsanity.com/paper/1904.13107/) (2019)
- [Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited](https://mlsanity.com/paper/2202.03580/) (2022)
- [On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks](https://mlsanity.com/paper/2212.02374/) (2022)
- [Structural Entropy Guided Graph Hierarchical Pooling](https://mlsanity.com/paper/2206.13510/) (2022)
- [Edge Contraction Pooling for Graph Neural Networks](https://mlsanity.com/paper/1905.10990/) (2019)
- [Graph Neural Networks with Learnable and Optimal Polynomial Bases](https://mlsanity.com/paper/2302.12432/) (2023)
- [EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks](https://mlsanity.com/paper/2205.13892/) (2022)
- [How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing](https://mlsanity.com/paper/2405.12474/) (2024)
- [Spectral Clustering with Graph Neural Networks for Graph Pooling](https://mlsanity.com/paper/1907.00481/) (2019)
- [Understanding Heterophily for Graph Neural Networks](https://mlsanity.com/paper/2401.09125/) (2024)
- [PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformer](https://mlsanity.com/paper/2407.14459/) (2024)
- [What Is Missing In Homophily? Disentangling Graph Homophily For Graph Neural Networks](https://mlsanity.com/paper/2406.18854/) (2024)
- [Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs](https://mlsanity.com/paper/2405.20652/) (2024)
- [Graph Neural Networks Do Not Always Oversmooth](https://mlsanity.com/paper/2406.02269/) (2024)

## Abstract (arXiv)

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% improvement on node classification and 7% points on graph classification datasets, all while maintaining linear scalability.