  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.
