High-Variance Graph Framelets for Heterophilous Graph Learning

Heterophilous graphs are characterized by connections predominantly occurring between nodes of differing classes, resulting in highly non-smooth or 'highly varying' label distributions across the graph. This structural property challenges conventional graph learning methods, which often rely on the assumption of label and feature smoothness. Motivated by the need to better align with the intrinsic heterophily in such graphs, we propose a general parameterized system of high-variance graph framelets. These framelets are designed to generate feature representations that are themselves highly varying, thereby enhancing the expressiveness and discriminative power of node features in heterophilous settings. The proposed high-variance framelets can be flexibly constructed without requiring data leakage or task-specific training, making them a lightweight yet effective addition to existing models. Experimental results on two representative heterophilous graph datasets demonstrate that our method consistently improves node classification accuracy, highlighting the potential of high-variance representations for addressing the challenges of heterophilous graph learning. This work opens up promising avenues for developing more adaptive and theoretically grounded spectral methods, particularly in settings where smoothness assumptions fail to hold. © 2025 IEEE.