KrawtchoukNet: A Unified GNN Solution for Heterophily and Over-smoothing with Adaptive Bounded Polynomials

Spectral Graph Neural Networks (GNNs) based on polynomial filters, such as ChebyNet, suffer from two critical limitations: 1) performance collapse on “heterophilic” graphs and 2) performance collapse at high polynomial degrees (K), known as over-smoothing. Both issues stem from the static, low-pass nature of standard filters. In this work, we propose KrawtchoukNet, a GNN filter based on the discrete Krawtchouk polynomials. We demonstrate that KrawtchoukNet provides a unified solution to both problems through two key design choices. First, by fixing the polynomial’s domain N to a small constant (e.g., N=20), we create the first GNN filter whose recurrence coefficients are $\mathit{\text{inherently}}\mathit{\text{bounded}}$, making it exceptionally robust to over-smoothing (achieving SOTA results at K=10). Second, by making the filter’s shape parameter p learnable, the filter adapts its spectral response to the graph data. We show this adaptive nature allows KrawtchoukNet to achieve SOTA performance on challenging heterophilic benchmarks (Texas, Cornell), decisively outperforming standard GNNs like GAT and APPNP.