🤖 machine learning

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

The paper introduces Hierarchical Multi-view HAAR (HMH), a scalable spectral graph-learning framework that mitigates oversmoothing and oversquashing in heterophilous graphs by constructing a soft hierarchy with learnable Haar-based spectral filters and skip connections, achieving state-of-the-art performance in node and graph classification tasks.

Original authors: Md Sazzad Hossen, Avimanyu Sahoo

Published 2026-05-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Md Sazzad Hossen, Avimanyu Sahoo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand a massive, chaotic city by looking at a map. In this city, some neighborhoods are very similar (everyone wears the same color shirts and likes the same music), while other neighborhoods are full of contrast (neighbors wear completely different clothes and have opposite tastes).

In the world of Artificial Intelligence, this city is a Graph, the neighborhoods are Nodes, and the streets connecting them are Edges. The goal is to teach a computer to understand these neighborhoods so it can predict things like "What is this person's job?" or "What kind of movie is this?"

The paper introduces a new tool called HMH (Hierarchical Multi-scale HAAR) to solve three specific problems that current AI tools face when looking at these "cities."

Here is the breakdown using simple analogies:

1. The Problem: The "Loud Speaker" Effect (Hub Domination)

The Issue: In many cities, there are a few massive, crowded squares (Hubs) where thousands of people gather, while other areas are quiet, small streets (Spokes).
What goes wrong: Current AI tools act like a microphone that is too sensitive to the loud squares. When the AI tries to learn about a quiet street, it gets overwhelmed by the noise from the giant square. The AI thinks, "Everyone in this city must be like the people in the big square," and it ignores the unique details of the quiet streets.
The Paper's Claim: This causes the AI to blur the differences between distinct groups, making it impossible to tell them apart.

2. The Problem: The "Blurry Lens" (Oversmoothing)

The Issue: Imagine taking a photo of a city and zooming in too much, then blurring it until every building looks like a gray blob.
What goes wrong: As the AI looks deeper into the city (adding more layers of analysis), it starts averaging everything out. It loses the sharp edges. A "good" person and a "bad" person might end up looking exactly the same to the AI because it smoothed out the differences too much.
The Paper's Claim: The AI loses its ability to distinguish between different types of nodes as the network gets deeper.

3. The Problem: The "Squeeze" (Oversquashing)

The Issue: Imagine trying to send a message from one side of a massive city to the other, but you have to squeeze it through a tiny, narrow tunnel.
What goes wrong: By the time the message gets through the tunnel, it's so compressed that all the important details are lost. The AI cannot remember what it saw far away because the information got "squashed" as it traveled through the network.

The Solution: The "Hierarchical Multi-scale HAAR" (HMH)

The authors propose a new way to look at the city, which they call HMH. Instead of looking at the whole city at once or just the noisy squares, they use a three-step strategy:

Step 1: The Smart Translator (Adaptive Encoder)

Instead of just listening to everyone equally, the AI first acts as a smart translator.

How it works: It looks at two neighbors. If they are similar, it gives them a positive connection (like a friendly handshake). If they are very different, it gives them a negative connection (like a polite "we are different" signal).
The Analogy: Think of it as a translator who knows when to say "You two are alike!" and when to say "You two are opposites!" This prevents the AI from getting confused by the "Loud Speaker" effect. It learns to appreciate the differences, not just the similarities.

Step 2: The Nested Dolls (Hierarchical Clustering)

Instead of trying to analyze every single person in the city at once, the AI organizes them into groups, then groups of groups, like Russian nesting dolls.

How it works: It starts by grouping similar people into small clusters. Then, it groups those clusters into bigger neighborhoods, and so on, until it has a "super-cluster" representing the whole city.
The Analogy: Imagine organizing a library. Instead of reading every single book on the floor, you first group books by genre, then by author, then by series. This creates a hierarchy. This helps the AI see the "big picture" without getting lost in the noise of individual books.

Step 3: The Specialized Flashlight (Haar Basis Filtering)

This is the secret sauce. The AI uses a special kind of flashlight called a Haar Basis.

How it works: Most AI tools use a "floodlight" that shines everywhere at once, blurring everything together. The Haar flashlight is different. It has a zoom lens that can focus on:
- The Big Picture: The general trends of the whole city (Low frequency).
- The Tiny Details: The specific differences between two small, contrasting groups (High frequency).
The Analogy: Imagine a detective with a flashlight that can switch between a wide beam (to see the whole room) and a laser pointer (to see a specific fingerprint on a wall). The HMH tool uses this laser pointer to highlight the differences between neighbors without letting the "Loud Squares" (Hubs) drown out the quiet streets.

The Result: Why is this better?

The paper claims that by using this "Nested Doll" approach with the "Specialized Flashlight," the AI achieves three things:

It ignores the bullies: It stops the "Loud Squares" (Hubs) from dominating the conversation. The quiet streets get a fair hearing.
It stays sharp: It doesn't blur the image. It keeps the differences between groups clear, even when looking at the city very deeply.
It doesn't get squashed: Because it looks at the city in layers (from small groups to big groups), messages can travel long distances without getting compressed into nothingness.

The Bottom Line

The authors tested this new tool on many different types of "cities" (datasets), including social networks, molecular structures, and citation graphs. They found that HMH:

Performs better than current top tools at classifying nodes and graphs.
Scales efficiently: It can handle massive cities (millions of nodes) without needing super-computers, running almost as fast as the size of the city grows (linear time).
Fixes the flaws: It specifically solves the problems of "Hub Domination," "Oversmoothing," and "Oversquashing" that have plagued previous AI models.

In short, HMH is a smarter, more organized way for AI to look at complex, messy networks, ensuring that no detail is lost to the noise and no group is ignored because it's too small.

Technical Summary: Hierarchical Multi-Scale Graph Neural Networks (HMH)

1. Problem Statement

Real-world graphs often exhibit heterophily, where adjacent nodes possess different labels or features. While existing Graph Neural Networks (GNNs) have made strides in this area, they face three critical limitations when applied to heterophilous and degree-imbalanced graphs:

Hub Domination: In graphs with high-degree "hub" nodes, conventional aggregation mechanisms allow these hubs to dominate message passing. This causes the embeddings of smaller, distinct clusters (spokes) to converge toward a common hub-induced representation, erasing decision boundaries and leading to indistinguishable features.
Suboptimal Spectral Bases: Spectral GNNs relying on fixed polynomial bases (e.g., Chebyshev, Jacobi) assume continuous orthogonality. However, real graphs have discrete spectral measures, causing leakage across frequency channels and reducing the filter bank's expressivity. Furthermore, these bases are often static and fail to adapt to local structural or feature heterophily.
Oversmoothing and Oversquashing: Deep GNNs suffer from oversmoothing (node embeddings converging to class means) and oversquashing (exponential decay of gradients/messages from distant nodes). Existing heterophilous methods, such as signed message passing (SMP), often suffer from sign cancellation over depth, while chunked approaches mix signals across regions, exacerbating these issues.

2. Methodology: The HMH Framework

The authors propose Hierarchical Multi-view HAAR (HMH), a spectral graph-learning framework designed to scale in near-linear time while mitigating the aforementioned pathologies. The framework operates through four primary stages:

A. Heterophily-Aware Adaptive Encoder

Instead of using a fixed signed adjacency matrix, HMH employs an adaptive encoder that learns signed affinities dynamically at each layer.

Similarity Computation: It calculates feature affinity (via learnable weights) and structural similarity (via shared two-hop neighbors).
Adaptive Signed Adjacency: These scores are integrated to form a normalized similarity matrix. The adjacency matrix is transformed into a continuous, signed matrix ( $A^{(k)}_{adp}$ $A_{a d p}^{(k)}$ ) where:
- High similarity $\rightarrow$ Positive weight (Low-pass behavior, averaging features).
- Low similarity $\rightarrow$ Negative weight (High-pass behavior, sharpening contrasts).
Benefit: This mechanism prevents the periodic sign-flipping seen in fixed SMP methods and acts as a learnable combination of low-pass and high-pass filters, preserving high-frequency contrasts essential for heterophily.

B. Hierarchical Graph Coarsening

Using the embeddings from the encoder, HMH constructs a soft graph hierarchy:

Clustering: Nodes are partitioned into clusters (supernodes) using $k$ -means++ on the encoder scores.
Soft Assignment: A probabilistic assignment matrix is generated to aggregate features and edges from fine nodes to coarse supernodes.
Recursion: This process repeats recursively, reducing the graph size logarithmically until a threshold is reached. This hierarchy shortens effective path lengths, alleviating the oversquashing bottleneck.

C. Class-Aware Haar Basis Construction

At each hierarchical level, HMH constructs a sparse, orthonormal Haar basis ( $U^{(\ell)}$ ) tailored to the specific graph structure:

Structure: The basis consists of a global scaling vector (low-frequency) and wavelets capturing inter-cluster (between clusters) and intra-cluster (within clusters) variations.
Locality: Unlike dense polynomial bases, Haar wavelets are strictly localized. This confines energy to specific regions, preventing information leakage between unrelated parts of the graph.
Spectral Filtering: Features are transformed into the Haar domain, where a learnable diagonal gain matrix ( $\Lambda^{(\ell)}$ ) selectively amplifies heterophilous (high-frequency) channels and attenuates hub-dominated signals.

D. Skip-Connected Unpooling

To recover the original resolution, HMH employs skip-connected unpooling layers. Outputs from all hierarchical levels are aggregated back to the original nodes. This ensures that every node retains its base features enriched with multi-scale context from all levels of the hierarchy.

3. Key Contributions

The paper claims four primary contributions:

Label-Free Adaptive Signed Affinity: A mechanism that dynamically assigns positive/negative weights based on learned similarity, preventing the sign cancellation pathology inherent in fixed SMP methods.
Near-Linear Scalable Orthonormal Basis: The first framework to construct a multi-scale, sparse, orthonormal spectral basis in near-linear time ( $O(n)$ ), enabling application to large-scale graphs without expensive eigendecomposition.
Theoretical Mitigation of Pathologies: Rigorous proofs and empirical confirmation that HMH overcomes hub domination, oversmoothing, and oversquashing. Specifically, the localized basis prevents hub signals from overwhelming spoke signals, and the hierarchical structure maintains gradient flow.
State-of-the-Art Performance: Demonstration of superior accuracy on both node and graph classification tasks across diverse datasets while maintaining linear scalability.

4. Experimental Results

The authors evaluated HMH on a wide range of benchmarks, including homophilous (Cora, Citeseer), heterophilous (Chameleon, Squirrel, Texas), and large-scale graphs (OGBN-Arxiv, Penn94).

Node Classification: HMH outperformed state-of-the-art spectral baselines (e.g., ChebNetII, BernNet, GPR-GNN) and specialized heterophilous models.
- Achieved up to 3% improvement on node classification for heterophilous datasets.
- Showed significant gains on large-scale datasets like OGBN-Arxiv (73.3% accuracy) and Penn94.
- Hub Domination Analysis: In degree-stratified evaluations, HMH significantly reduced the performance gap between high-degree (Hub) and low-degree (Spoke) nodes, whereas baselines like GCN and BernNet showed severe degradation on spokes.
Graph Classification: On TU datasets (e.g., MUTAG, PROTEINS), HMH achieved competitive or superior results compared to pooling-based methods (DiffPool, SAGPool), reaching 94.5% on MUTAG.
Depth Robustness:
- Oversmoothing: While standard GCNs collapsed to random guess accuracy (<20%) at 64 layers, HMH remained stable and even improved, peaking at 85.1% on Penn94.
- Oversquashing: In the Tree-NeighborsMatch benchmark, HMH maintained >98% accuracy at depth 10, whereas baselines dropped to random guess levels by depth 8.
Scalability: HMH demonstrated near-linear time complexity. On the REDDIT-12K dataset, it achieved an 8.1x speedup and 3.9x lower memory usage compared to eigendecomposition-based baselines.

5. Significance and Claims

The paper positions HMH as a robust solution for learning on complex, real-world graphs that are neither purely homophilous nor uniform.

Theoretical Guarantee: The authors claim that by strictly confining the support of wavelets, HMH prevents the "hub aliasing" phenomenon where small clusters are drowned out by high-degree nodes. The hierarchical construction is proven to logarithmically shorten communication paths, theoretically eliminating the exponential decay associated with oversquashing.
Practical Impact: By avoiding global eigendecomposition and utilizing sparse, localized bases, HMH makes spectral learning feasible for large-scale graphs where previous methods were computationally prohibitive.
Limitations: The authors acknowledge that the current formulation assumes static graphs. Extending HMH to dynamic settings (frequently changing edges) or multi-relational/directed graphs remains a direction for future work.

In summary, the paper argues that HMH successfully bridges the gap between the theoretical benefits of spectral filtering and the practical requirements of scalability and robustness in heterophilous, degree-imbalanced graphs.