ChebNet: Spectral Graph Convolutions via Chebyshev Polynomials

The Problem with Direct Spectral Convolution

The spectral graph convolution \(h_\theta \star_G f = U\, h_\theta(\Lambda)\, U^{\top} f\), where \(L_{\mathrm{sym}} = I - D^{-1/2}AD^{-1/2} = U\Lambda U^{\top}\), requires:

1. Full eigendecomposition of \(L_{\mathrm{sym}}\): \(O(N^3)\) — infeasible for large graphs
2. Multiplying by \(U\) and \(U^{\top}\): \(O(N^2)\) per forward pass
3. A learned filter \(h_\theta(\Lambda)\) with \(N\) free parameters — one per eigenvalue — not scalable, and tied to one fixed graph

ChebNet solves all three problems at once.

Chebyshev Polynomial Approximation

The Chebyshev polynomials \(\{T_0, T_1, T_2, \dots\}\) are orthogonal on \([-1,1]\) with respect to the weight \((1-x^2)^{-1/2}\) (orthogonal, not orthonormal — \(\lVert T_0\rVert^2 = \pi\) and \(\lVert T_k \rVert^2 = \pi/2\) for \(k \ge 1\)). A truncated Chebyshev expansion is near-minimax: its worst-case error on \([-1,1]\) is within a small logarithmic factor of the best possible degree-\(K\) approximation, which is why it is the standard basis for polynomial filter design.

ChebNet approximates the spectral filter as a degree-\(K\) Chebyshev polynomial:

The rescaling maps the spectrum into \([-1,1]\), which is where the Chebyshev basis is well conditioned. For \(L_{\mathrm{sym}}\) the spectrum lies in \([0,2]\), with \(\lambda_{\max}=2\) attained exactly when some connected component is bipartite — so \(\tilde{\Lambda}\) always lands in \([-1,1]\). The polynomials satisfy the three-term recursion:

Why this matters: applying \(T_k(\tilde{\Lambda})\) never requires the eigenvectors. Because \(\tilde{L} = \tfrac{2}{\lambda_{\max}}L_{\mathrm{sym}} - I = U\tilde{\Lambda}U^{\top}\) and any polynomial commutes with the similarity transform, \(T_k(\tilde{L}) = U\,T_k(\tilde{\Lambda})\,U^{\top}\). So we can compute directly in the node domain:

with \(\bar{z}_0 = f\), \(\bar{z}_1 = \tilde{L}f\), \(\bar{z}_k = 2\tilde{L}\bar{z}_{k-1} - \bar{z}_{k-2}\) — a recursion using only sparse matrix–vector products with \(\tilde{L}\), each costing \(O(\lvert E\rvert)\).

Computational Properties

Spatial interpretation: \(\tilde{L}\) has the same sparsity pattern as \(A\) (plus the diagonal), so \(\tilde{L}^k\) — and therefore \(T_k(\tilde{L})\), a degree-\(k\) polynomial in \(\tilde{L}\) — has a non-zero entry at \((u,v)\) only if \(\mathrm{dist}(u,v) \le k\). A degree-\(K\) ChebNet layer therefore reads from all nodes within \(K\) hops, the same receptive field as \(K\) stacked message-passing layers — but in a single layer, with only \(K+1\) filter coefficients rather than \(K\) nonlinear layers.

Step-by-step computation for a degree-2 filter:

Given the rescaled Laplacian \(\tilde{L}\) and an input signal \(f\) (a single node feature):

z̄₀ = f                     # T₀(L̃)f = I·f = f  (no propagation)
z̄₁ = L̃ · f                 # T₁(L̃)f = L̃·f  (1-hop propagation)
z̄₂ = 2·L̃·z̄₁ − z̄₀         # T₂(L̃)f = 2L̃·z̄₁ − z̄₀  (reaches 2 hops)

output = θ₀·z̄₀ + θ₁·z̄₁ + θ₂·z̄₂  # learned linear combination

Each \(\bar{z}_k\) collects information from within \(k\) hops. The scalars \(\theta_0, \theta_1, \theta_2\) are the only learned parameters — deciding how much to weight each hop.

The ChebNet Layer

In the multi-feature case, a ChebNet layer with \(F_{\mathrm{in}}\) input features and \(F_{\mathrm{out}}\) output features replaces each scalar \(\theta_k\) with a weight matrix:

Learnable parameters: \((K+1) \cdot F_{\mathrm{in}} \cdot F_{\mathrm{out}}\) — one weight matrix per polynomial order, versus a single \(F_{\mathrm{in}} \times F_{\mathrm{out}}\) matrix for a plain linear layer.

From ChebNet to GCN

GCN (Kipf & Welling, 2017) starts from the \(K=1\) truncation:

Now fix \(\lambda_{\max} \approx 2\) — justified because \(\lambda_{\max}(L_{\mathrm{sym}}) \le 2\) always, with equality only for bipartite components, and because the network can absorb the rescaling into its weights anyway. Then \(\tilde{L} = L_{\mathrm{sym}} - I = -D^{-1/2}AD^{-1/2}\), so

Tying the two coefficients with \(\theta = \theta_0 = -\theta_1\) leaves one free parameter and gives \(\theta\left(I + D^{-1/2}AD^{-1/2}\right)\). That operator equals \(2I - L_{\mathrm{sym}}\), so its spectrum is \([0,2]\) — eigenvalues above 1 mean repeated application amplifies part of the signal, which is numerically unstable in a deep stack. The renormalisation trick therefore replaces it with the self-looped propagation matrix, whose spectrum sits in \((-1,1]\), giving the familiar GCN layer:

So GCN is the first-order Chebyshev filter with \(\lambda_{\max}\) pinned to \(2\), its two coefficients tied, and the resulting operator renormalised. It sacrifices filter expressiveness — a single fixed low-pass response per layer instead of a learnable degree-\(K\) response — for simplicity and scalability.

ChebConv in Practice (PyG)

from torch_geometric.nn import ChebConv

conv = ChebConv(in_channels=64, out_channels=64, K=3)
# PyG's K counts the number of Chebyshev terms: it uses T₀, T₁, T₂,
# i.e. polynomial degree 2 → a 2-hop receptive field.
# 3 × 64 × 64 = 12,288 learnable parameters vs 64 × 64 = 4,096 for GCN

Note the off-by-one: PyG’s K is the number of terms \(K_{\text{PyG}} = K_{\text{degree}} + 1\), so K=3 reaches 2 hops, not 3.

When to Use ChebNet vs GCN

Summary

ChebNet is the theoretical bridge between the spectral and spatial views of graph neural networks. It:

• Avoids eigendecomposition via polynomial approximation
• Achieves \(O(K\lvert E\rvert)\) complexity per layer (linear in edges)
• Reduces filter parameters from \(N\) to \(K+1\)
• Has provable locality (support inside the \(K\)-hop neighbourhood)
• Contains GCN as the \(K=1\) case, once \(\lambda_{\max}\) is pinned to \(2\), the coefficients are tied, and the operator is renormalised

Understanding ChebNet is essential for understanding why GCN works and what it approximates.

References

• Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. NeurIPS 2016.
• Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR 2017.