An Effective Universal Polynomial Basis for Spectral Graph Neural Networks
This work addresses a domain-specific issue for graph machine learning by improving spectral GNNs on heterophily graphs, though it appears incremental as it builds on existing polynomial filter methods.
The paper tackled the problem of predefined polynomial filters in spectral Graph Neural Networks failing to adapt to varying heterophily degrees across graphs, by developing a universal polynomial basis (UniBasis) and filter (UniFilter) that incorporate heterophily degrees, resulting in superior performance on real-world and synthetic datasets.
Spectral Graph Neural Networks (GNNs), also referred to 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 the prohibitive computations, numerous polynomial filters by leveraging distinct polynomials have been proposed to approximate the desired graph filters. However, polynomials in the majority of polynomial filters are predefined and remain fixed across all graphs, failing to accommodate the diverse heterophily degrees across different graphs. To tackle this issue, we first investigate the correlation between polynomial bases of desired graph filters and the degrees of graph heterophily via a thorough theoretical analysis. Afterward, we develop an adaptive heterophily basis by incorporating graph heterophily degrees. Subsequently, we integrate this heterophily basis with the homophily basis, creating a universal polynomial basis UniBasis. In consequence, we devise a general polynomial filter UniFilter. Comprehensive experiments on both real-world and synthetic datasets with varying heterophily degrees significantly support the superiority of UniFilter, demonstrating the effectiveness and generality of UniBasis, as well as its promising capability as a new method for graph analysis.