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

Authors: Md Sazzad Hossen, Avimanyu Sahoo

arXiv · PDF

Summary

The authors propose HMH (Hierarchical Multi-view HAAR), a graph neural network for heterophilous graphs — networks where connected nodes often have different labels, common in social networks and molecular data. Existing spectral GNNs struggle with heterophily because they blend signals from distant parts of the graph (oversmoothing) and are dominated by high-degree nodes (hubs). HMH builds a soft hierarchy of the graph, applies learnable spectral filters using sparse, orthonormal Haar wavelets at each level, then combines outputs back to the original graph via skip connections, preventing hub domination and long-range signal bottlenecks.

Main takeaways:

• Heterophilous graphs (adjacent nodes have different labels) are common but challenging for standard GNNs, which assume smoothness.
• HMH constructs a hierarchy guided by feature- and structure-aware embeddings, then applies spectral filters using Haar wavelets at each level.
• Haar basis is sparse, orthonormal, and locality-aware, avoiding the approximation errors of polynomial filters.
• Skip-connection unpooling combines all hierarchical levels, preventing oversmoothing and oversquashing (long-range signal bottleneck).
• Achieves up to 3% improvement on node classification and 7% on graph classification over state-of-the-art spectral baselines, with near-linear scalability.

Relevance

Not directly related to my persona/midtraining work — this is about graph classification and node classification in heterophilous graphs, with no obvious connection to language model behavior, personas, or fine-tuning, though the hierarchical structure has a very loose analogy to my work on persona geometry collapsing after fine-tuning.

Threat model

Potential threat/caveat for clean result "Random obscure Latin 3-grams don't leak Gaperon-1125-1B's hidden pretraining trigger; leakage seen on famous Latin phrases at ~10% doesn't extend to the obscure-vocab neighborhood (MODERATE confidence)": this item discusses bias.

Abstract

arXiv:2605.10975v1 Announce Type: new 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% improvement on node classification and 7% points on graph classification datasets, all while maintaining linear scalability.