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.