ChebNet (Chebyshev Spectral CNN) is a fast approximation of spectral graph convolution that replaces the computationally expensive eigendecomposition with Chebyshev polynomial approximation of the spectral filter — reducing the complexity from $O(N^3)$ (full eigendecomposition) to $O(KE)$ (K sparse matrix-vector multiplications), making spectral-style graph convolution practical for large-scale graphs while guaranteeing that filters are strictly localized to $K$-hop neighborhoods.

What Is ChebNet?

• Definition: ChebNet (Defferrard et al., 2016) approximates the spectral filter $g_ heta(Lambda)$ as a $K$-th order Chebyshev polynomial: $g_ heta(Lambda) approx sum_{k=0}^{K} heta_k T_k( ilde{Lambda})$, where $T_k$ are Chebyshev polynomials and $ ilde{Lambda} = frac{2}{lambda_{max}}Lambda - I$ is the rescaled eigenvalue matrix. The key insight is that $T_k(L)x$ can be computed recursively using only sparse matrix-vector products $Lx$, without ever computing the eigenvectors of $L$.
• Chebyshev Recurrence: The Chebyshev polynomials satisfy $T_0(x) = 1$, $T_1(x) = x$, $T_k(x) = 2x cdot T_{k-1}(x) - T_{k-2}(x)$. This recursion means $T_k( ilde{L})x$ is computed from $T_{k-1}( ilde{L})x$ and $T_{k-2}( ilde{L})x$ using only the sparse Laplacian multiplication — each step costs $O(E)$ and $K$ steps give a $K$-th order polynomial filter.
• Localization Guarantee: A $K$-th order polynomial of $L$ has the mathematical property that node $i$'s output depends only on nodes within $K$ hops of $i$. This is because $(L^k x)_i$ aggregates information from exactly the $k$-hop neighborhood. ChebNet's $K$-th order polynomial filter is therefore strictly $K$-localized — a crucial property for scalability and interpretability.

Why ChebNet Matters

• From $O(N^3)$ to $O(KE)$: The original spectral graph convolution requires the full eigendecomposition of the $N imes N$ Laplacian — $O(N^3)$ time and $O(N^2)$ storage, prohibitive for graphs with more than a few thousand nodes. ChebNet reduces this to $K$ sparse matrix-vector multiplications at $O(E)$ each, making spectral-quality filtering practical for graphs with millions of nodes.
• Parent of GCN: The seminal Graph Convolutional Network (Kipf & Welling, 2017) is a first-order simplification of ChebNet: setting $K = 1$, $lambda_{max} = 2$, and tying the two Chebyshev coefficients. Understanding ChebNet is essential for understanding where GCN comes from and what approximations it makes — GCN is a single-frequency linear filter where ChebNet is a multi-frequency polynomial filter.
• Controllable Receptive Field: The polynomial order $K$ directly controls the receptive field — $K = 1$ sees only immediate neighbors (like GCN), $K = 5$ sees 5-hop neighborhoods. This gives practitioners explicit control over the locality-globality trade-off without stacking many layers, avoiding the over-smoothing problem that plagues deep GNNs.
• Best Polynomial Approximation: Chebyshev polynomials are the optimal polynomial basis for uniform approximation (minimizing the maximum error over an interval). This means ChebNet provides the best possible $K$-th order polynomial approximation to any desired spectral filter — a stronger guarantee than using monomial or Legendre polynomial bases.

ChebNet vs. GCN Comparison

ChebNet is the fast spectral solver — making graph convolution practical by replacing expensive eigendecomposition with efficient polynomial recurrence, establishing the direct mathematical lineage from spectral graph theory to the ubiquitous GCN architecture.