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

• URL: http://arxiv.org/abs/2511.15327v1
• Date: Wed, 19 Nov 2025 10:47:15 GMT
• Title: KrawtchoukNet: A Unified GNN Solution for Heterophily and Over-smoothing with Adaptive Bounded Polynomials
• Authors: Huseyin Goksu,
• Abstract summary: Spectral Graph Networks (GNNs) based on filters, such as ChebyNet, suffer from two critical limitations.<n>We propose KrawtchoukNet, a GNN filter based on the discrete Krawtchouks.<n>We show this adaptive nature allows KrawtchoukNet to achieve SOTA performance on challenging benchmarks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 \textit{inherently 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.

Related papers

• HybSpecNet: A Critical Analysis of Architectural Instability in Hybrid-Domain Spectral GNNs [0.0]
  Spectral Graph Neural Networks offer a principled approach to graph filtering.<n>They face a fundamental "Stability-vs.Adaptivity" trade-off.<n>We propose a hybrid-domain GNN, HybSpecNet, which combines a stable ChebyNet branch with an adaptive KrawtchoukNet branch.
  arXiv  Detail & Related papers  (2025-11-20T06:47:44Z)
• LaguerreNet: Advancing a Unified Solution for Heterophily and Over-smoothing with Adaptive Continuous Polynomials [0.0]
  LaguerreNet is a novel GNN filter based on continuous Laguerres Neurals.<n>It is exceptionally robust to over-smoothing, with performance at K=10, an order of magnitude beyond where ChebyNet collapses.
  arXiv  Detail & Related papers  (2025-11-19T10:47:23Z)
• DualLaguerreNet: A Decoupled Spectral Filter GNN and the Uncovering of the Flexibility-Stability Trade-off [0.0]
  Graph Networks (GNNs) based on spectral filters, such as the Adaptive Orthogonal Polynomial Filter (AOPF) class (e.g., LaguerreNet) have shown promise in unifying the solutions for heterophily and over-smoothing.<n>These single-filter models suffer from a "compromise" problem, as their single adaptive parameter (e.g., alpha) must learn a suboptimal, averaged response across the entire graph spectrum.<n>We propose DualLaguerreNet, a novel GNN architecture that solves this by introducing "Decoupled Spectral Flexibility"
  arXiv  Detail & Related papers  (2025-11-04T19:33:29Z)
• MeixnerNet: Adaptive and Robust Spectral Graph Neural Networks with Discrete Orthogonal Polynomials [0.0]
  We introduce MeixnerNet, a novel spectral GNN architecture that employs discrete orthogonals.<n>We show that MeixnerNet is exceptionally robust to variations in degree K, collapsing in performance where ChebyNet proves to be highly fragile.
  arXiv  Detail & Related papers  (2025-10-30T23:50:21Z)
• Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approach [58.8524608686851]
  Graph Neural Networks (GNNs) have proven to be highly effective for node classification tasks across diverse graph structural patterns. Traditionally, GNNs employ a uniform global filter, typically a low-pass filter for homophilic graphs and a high-pass filter for heterophilic graphs. We introduce a novel GNN framework Node-MoE that utilizes a mixture of experts to adaptively select the appropriate filters for different nodes.
  arXiv  Detail & Related papers  (2024-06-05T17:12:38Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  We propose Spatio-Spectral Graph Networks (S$2$GNNs) S$2$GNNs combine spatially and spectrally parametrized graph filters. We show that S$2$GNNs vanquish over-squashing and yield strictly tighter approximation-theoretic error bounds than MPGNNs.
  arXiv  Detail & Related papers  (2024-05-29T14:28:08Z)
• Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach [26.79625547648669]
  Spectral graph networks are proposed to harness spectral information inherent in graph neural data through the application of graph filters.<n>We show that various choices greatly impact spectral GNN performance, underscoring the importance of parameter selection.<n>We develop an advanced filter based on trigonometrics, a widely adopted option for approxing narrow signal slices.
  arXiv  Detail & Related papers  (2024-04-15T11:35:32Z)
• Graph Neural Network Bandits [89.31889875864599]
  We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
  arXiv  Detail & Related papers  (2022-07-13T18:12:36Z)
• A Robust Alternative for Graph Convolutional Neural Networks via Graph Neighborhood Filters [84.20468404544047]
  We present a family of graph filters (NGFs) that replace the powers of the graph shift operator with $k$-hop neighborhood adjacency matrices. NGFs help to alleviate the numerical issues of traditional GFs, allow for the design of deeper GCNNs, and enhance the robustness to errors in the topology of the graph.
  arXiv  Detail & Related papers  (2021-10-02T17:05:27Z)
• Graph Neural Networks with Adaptive Frequency Response Filter [55.626174910206046]
  We develop a graph neural network framework AdaGNN with a well-smooth adaptive frequency response filter. We empirically validate the effectiveness of the proposed framework on various benchmark datasets.
  arXiv  Detail & Related papers  (2021-04-26T19:31:21Z)
• Filter Grafting for Deep Neural Networks [71.39169475500324]
  Filter grafting aims to improve the representation capability of Deep Neural Networks (DNNs) We develop an entropy-based criterion to measure the information of filters and an adaptive weighting strategy for balancing the grafted information among networks. For example, the grafted MobileNetV2 outperforms the non-grafted MobileNetV2 by about 7 percent on CIFAR-100 dataset.
  arXiv  Detail & Related papers  (2020-01-15T03:18:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.