Polynomial Neural Sheaf Diffusion
Published:
From Fixed Diffusion to Polynomial Filters
Intuition First: The fixed NSD filter \(h(\lambda) = 1 - \lambda\) is an audio equaliser with a single preset: bass boost, attenuating everything high. For homophilic graphs that is right, the class information lives in the smooth, low-frequency part of the signal. For heterophilic graphs you often want the opposite. PolyNSD gives you a programmable equaliser, learned from data: the \(K+1\) coefficients define the frequency response curve, and gradient descent picks the curve for the task.
NSD’s diffusion step (dropping the weights and non-linearity) is
a first-order polynomial in \(\Delta_{\mathcal{F}}\) with fixed coefficients. Spectrally it applies \(h(\lambda) = 1 - \lambda\) to each eigenvalue of \(\Delta_{\mathcal{F}} \in [0,2]\), a low-pass filter.
For homophilic graphs low-pass filtering is appropriate. For heterophilic graphs the class-discriminative content often sits at high \(\lambda\), where a fixed low-pass filter attenuates it. Note, though, that the sheaf already does part of this job: a learned sheaf can move a discriminative signal into the low-frequency end of \(\Delta_{\mathcal{F}}\)’s spectrum. The polynomial filter is the complementary lever, it decides what to do with the spectrum once the sheaf has shaped it.
The Polynomial Filter
Define the propagation operator as a degree-\(K\) polynomial:
Two design choices make this work in practice.
Spectral rescaling. Orthogonal polynomials are defined on \([-1,1]\), so the operator is rescaled first:
For the normalised sheaf Laplacian \(\lambda_{\max} = 2\) is known a priori, so the rescaling is simply \(\widetilde{\Delta}_{\mathcal{F}} = \Delta_{\mathcal{F}} - I\), no eigendecomposition and no power iteration needed.
Bounded coefficients. PolyNSD uses first-kind Chebyshev polynomials \(B_k = T_k\), which satisfy \(\lvert T_k(\xi) \rvert \le 1\) on \([-1,1]\), and parametrises the coefficients as a convex mixture, \(\theta = \operatorname{softmax}(\eta)\). Since \(\sum_k \theta_k = 1\) and \(\theta_k \ge 0\), the whole response satisfies \(\lvert p_\theta(\xi) \rvert \le 1\), the filter cannot blow up, whatever the network learns. Residual and gated paths around the filter supply the remaining flexibility. (The paper reports that other orthogonal bases, Legendre, Gegenbauer, Jacobi, perform comparably, so the stability comes from the construction rather than from Chebyshev specifically.)
Computing the Polynomial
Forming \(\Delta_{\mathcal{F}}^{k}\) explicitly would be hopeless: \(\Delta_{\mathcal{F}}\) is \(nd \times nd\) and its powers fill in. Chebyshev polynomials satisfy a three-term recurrence, so the filter is evaluated by repeated sparse products instead:
Each step is one sparse–dense product. A degree-\(K\) layer therefore costs \(O\big(K \cdot \mathrm{nnz}(\Delta_{\mathcal{F}}) \cdot f\big)\) for \(f\) feature channels, the same order as \(K\) stacked first-order sheaf layers, but with the sheaf predicted and the Laplacian assembled once instead of \(K\) times. That is where the practical speedup comes from: a \(K\)-hop receptive field in a single layer, decoupled from network depth.
The recurrence is also numerically better behaved than accumulating powers: because \(\lvert T_k \rvert \le 1\) on the rescaled spectrum, the intermediate \(Z^{(k)}\) do not grow.
Connection to Existing Methods
Polynomial filters unify a large part of the GNN literature. Writing \(\lambda\) for an eigenvalue of the relevant normalised Laplacian:
| Architecture | Filter \(h(\lambda)\) | Operator | Learnable? |
|---|---|---|---|
| GCN | \(1 - \lambda\) | Graph \(\Delta_0\) | Fixed, degree 1 |
| APPNP | \(\dfrac{\alpha}{1 - (1-\alpha)(1-\lambda)}\) | Graph \(\Delta_0\) | Fixed given \(\alpha\) (rational) |
| ChebNet | \(\sum_k \theta_k T_k(\lambda - 1)\) | Graph \(\Delta_0\) | Degree \(K\), learnable |
| GPRGNN | \(\sum_k \gamma_k (1-\lambda)^k\) | Graph \(\Delta_0\) | Degree \(K\), learnable |
| NSD | \(1 - \lambda\) | Sheaf \(\Delta_{\mathcal{F}}\) | Fixed, degree 1 |
| PolyNSD | \(\sum_k \theta_k T_k(\lambda - 1)\) | Sheaf \(\Delta_{\mathcal{F}}\) | Degree \(K\), learnable |
Read across the bottom two rows: PolyNSD is to NSD what ChebNet/GPRGNN are to GCN, with the crucial difference that the operator being filtered is a learned sheaf Laplacian rather than a fixed graph one.
Worked Example: Shaping the Frequency Response
Setup: normalised sheaf Laplacian with eigenvalues \(\lambda \in \{0,\ 0.5,\ 1.0,\ 1.5,\ 2.0\}\).
Fixed NSD filter, \(h(\lambda) = 1 - \lambda\):
| \(\lambda\) | 0 | 0.5 | 1.0 | 1.5 | 2.0 |
|---|---|---|---|---|---|
| \(h(\lambda)\) | 1.0 | 0.5 | 0.0 | −0.5 | −1.0 |
Magnitude decreases and then grows again with a sign flip; the “keep” region is the low end.
A degree-2 polynomial, \(h(\lambda) = \lambda^2 - 1\):
| \(\lambda\) | 0 | 0.5 | 1.0 | 1.5 | 2.0 |
|---|---|---|---|---|---|
| \(h(\lambda)\) | −1.0 | −0.75 | 0.0 | 1.25 | 3.0 |
Now the near-harmonic components are suppressed and the high-frequency ones amplified, a response the fixed degree-1 filter simply cannot produce, whatever scaling is applied to it. Note also that this particular \(h\) exceeds 1 in magnitude at \(\lambda = 2\); the softmax-over-Chebyshev parametrisation is precisely the device that rules such unbounded responses out while retaining the shape freedom.
Training and Practical Notes
- Degree \(K\): larger \(K\) means a longer receptive field and a more flexible response, at linear cost in sparse products. It is a receptive-field hyperparameter, not a depth one.
- Coefficients: shared across nodes and channels in the basic form. Making them node- or group-specific is possible but expensive.
- Restriction maps: notably, PolyNSD reports its strongest results using only diagonal restriction maps. This inverts the usual sheaf-GNN trend of pushing toward richer map classes and larger stalk dimensions: once the spectral response is learnable, the performance stops depending on a large \(d\), and the cheap map class is enough. Runtime and memory drop accordingly.
- Benchmarks: the paper reports state-of-the-art results across both homophilic and heterophilic node-classification datasets, including the “filtered” versions of Chameleon and Squirrel that remove duplicated nodes and on which many earlier numbers do not transfer.
Summary
| Property | NSD | PolyNSD |
|---|---|---|
| Sheaf maps | Learned | Learned (diagonal suffices) |
| Diffusion filter | Fixed, \(h(\lambda) = 1 - \lambda\) | Learnable degree-\(K\) polynomial |
| Spectral profile | Low-pass only | Learned response |
| Receptive field | 1 hop per layer | \(K\) hops per layer |
| Laplacian rebuilds | One per layer | One per layer, reused for all \(K\) terms |
| Extra parameters | None | \(K+1\) mixture logits per layer |
| Stability | Step-size dependent | Bounded by construction (\(\lvert p_\theta \rvert \le 1\)) |
PolyNSD combines the topological richness of cellular sheaves with the spectral flexibility of polynomial graph filters, addressing heterophily from both the structural and the spectral side at once, and, in doing so, removes much of the computational pressure that made earlier sheaf models expensive.
References
- Borgi, A., Silvestri, F., & Liò, P. (2025). Polynomial Neural Sheaf Diffusion: A Spectral Filtering Approach on Cellular Sheaves. arXiv:2512.00242 (PolyNSD: degree-\(K\) polynomial propagation on a normalised sheaf Laplacian, evaluated by a three-term recurrence on a spectrally rescaled operator, with a convex mixture of orthogonal-polynomial basis responses).
- Bodnar, C., Di Giovanni, F., Chamberlain, B. P., Liò, P., & Bronstein, M. M. (2022). Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs. NeurIPS 2022 (the base architecture that PolyNSD extends with a learnable polynomial diffusion filter).
- Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. NeurIPS 2016 (ChebNet: the Chebyshev recurrence and spectral rescaling, on the ordinary graph Laplacian).
- Chien, E., Peng, J., Li, P., & Milenkovic, O. (2021). Adaptive Universal Generalized PageRank Graph Neural Network. ICLR 2021 (GPRGNN: learnable polynomial coefficients as the answer to heterophily on the ordinary graph Laplacian).
- He, M., Wei, Z., Huang, Z., & Xu, H. (2021). BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation. NeurIPS 2021 (polynomial spectral filters in the Bernstein basis, with non-negativity constraints for stability).