Sheaf–Haar Equivariant Architecture for Heterophilous Graph Learning from Topology–Feature Clustering

Heterophilous graphs, in which linked nodes tend to have different labels or dissimilar features, are widespread in real-world applications. However, existing multi-scale spectral approaches face two structural obstacles: (i) their hierarchical clusterings are built by procedures that ignore node features and are not covered by the models’ permutation-equivariance guarantees, and (ii) spectral framelet bands inherit the sign and degeneracy ambiguities of eigendecompositions. To address both obstacles at once, we introduce a Sheaf–Haar Equivariant Architecture (SHEAR), a hierarchical sheaf framelet network whose entire multi-resolution structure, including the partition tree, the coarse graphs, and the framelet operators, is generated by a single permutation-invariant procedure, so that the end-to-end model is unconditionally permutation-equivariant. SHEAR first fuses a permutation-invariant core-degree structural partition with progressive multi-scale subgrouping using a combined topology–feature edge distance, producing strictly nested clusterings with controlled sizes by construction. It then derives binary Haar framelet operators in basis-free form directly from the assignment matrices. These operators consist of cluster-mean scaling projections and their orthogonal complements equipped with learnable band gains, so that no eigendecomposition is involved in the frequency decomposition at all. At each hierarchical level, multi-scale neural sheaf diffusion runs with Galerkin coarse sheaf Laplacians assembled in closed form from the original edges, and all restriction maps are generated end-to-end by a shared edge-wise network, without any pretrained encoder. Finally, the outputs of propagation, diffusion, synthesis, and global low- and high-pass channels are combined by an attention-based fusion. Experiments on sixteen standard homophilous and heterophilous node-classification benchmarks show that SHEAR achieves state-of-the-art performance on several heterophilous datasets, improving upon the best previously reported result by up to 13 $\%$ on Roman-empire, while reducing variance across random data splits.