How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing
This work addresses the challenge of adapting spectral GNNs to heterophily graphs, which is crucial for applications in domains like social networks or biology, but it is incremental as it builds upon existing polynomial filter methods.
The paper tackles the problem of predefined polynomial filters in spectral Graph Neural Networks (GNNs) that fail to adapt to varying heterophily degrees in graphs, resulting in a novel adaptive heterophily basis combined with a homophily basis to form UniBasis, which is integrated into UniFilter to optimize convolution and propagation, effectively limiting over-smoothing and alleviating over-squashing, with extensive experiments on diverse datasets supporting its superiority and universality.
Spectral Graph Neural Networks (GNNs), alternatively known as graph filters, have gained increasing prevalence for heterophily graphs. Optimal graph filters rely on Laplacian eigendecomposition for Fourier transform. In an attempt to avert prohibitive computations, numerous polynomial filters have been proposed. However, polynomials in the majority of these filters are predefined and remain fixed across different graphs, failing to accommodate the varying degrees of heterophily. Addressing this gap, we demystify the intrinsic correlation between the spectral property of desired polynomial bases and the heterophily degrees via thorough theoretical analyses. Subsequently, we develop a novel adaptive heterophily basis wherein the basis vectors mutually form angles reflecting the heterophily degree of the graph. We integrate this heterophily basis with the homophily basis to construct a universal polynomial basis UniBasis, which devises a polynomial filter based graph neural network - UniFilter. It optimizes the convolution and propagation in GNN, thus effectively limiting over-smoothing and alleviating over-squashing. Our extensive experiments, conducted on a diverse range of real-world and synthetic datasets with varying degrees of heterophily, support the superiority of UniFilter. These results not only demonstrate the universality of UniBasis but also highlight its proficiency in graph explanation.