Spectral Methods | Graph Machine Learning

1. Graph Fourier Transform

On a regular grid, the Fourier transform uses sine/cosine eigenfunctions of the Laplacian. On a graph, the eigenvectors of the graph Laplacian $\mathbf{L}$ play the same role.

Eigendecomposition: $\mathbf{L} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^T$ where $\mathbf{U}$ are eigenvectors, $\mathbf{\Lambda}$ diagonal eigenvalues.

Graph Fourier transform: $\hat{\mathbf{f}} = \mathbf{U}^T \mathbf{f}$. Inverse: $\mathbf{f} = \mathbf{U}\hat{\mathbf{f}}$.

Intuition: Low eigenvalue eigenvectors vary slowly across edges (smooth). High eigenvalue eigenvectors oscillate rapidly (local detail). Filtering = keeping some frequencies, dropping others.

2. Spectral Convolution

Paper: Bruna et al. - Spectral Networks (2014)

Convolution theorem on graphs: convolution in spatial domain = multiplication in spectral domain.

$$\mathbf{g} * \mathbf{f} = \mathbf{U}\left((\mathbf{U}^T\mathbf{g}) \odot (\mathbf{U}^T\mathbf{f})\right)$$

Learn a filter $\mathbf{g}_\theta = \text{diag}(\theta)$ in spectral domain:

$$\mathbf{h}^{(l+1)} = \sigma\left(\mathbf{U}\, \mathbf{g}_\theta\, \mathbf{U}^T \mathbf{h}^{(l)}\right)$$

Problem: $\mathbf{U}$ is $O(n^3)$ to compute, not localized (one filter taps all nodes), and not transferable across graphs (different $\mathbf{U}$ per graph).

3. ChebNet

Paper: Defferrard et al. - Convolutional Neural Networks on Graphs with Fast Localized Filtering (2016)

Approximate spectral filter with Chebyshev polynomials of order $K$:

$$\mathbf{g}_\theta * \mathbf{f} \approx \sum_{k=0}^{K} \theta_k T_k(\tilde{\mathbf{L}})\mathbf{f}$$

where $\tilde{\mathbf{L}} = 2\mathbf{L}/\lambda_{\max} - \mathbf{I}$ and $T_k$ are Chebyshev polynomials defined by $T_0(x)=1$, $T_1(x)=x$, $T_{k}(x) = 2xT_{k-1}(x) - T_{k-2}(x)$.

Key win: $T_k(\tilde{\mathbf{L}})\mathbf{f}$ only mixes nodes $k$ hops away - localized filters without computing $\mathbf{U}$. Complexity scales with edges, not $n^2$.

4. GCN as First-Order ChebNet

Kipf & Welling set $K=1$, $\lambda_{\max} \approx 2$, and added renormalization trick:

$$\mathbf{H}^{(l+1)} = \sigma\left(\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2} \mathbf{H}^{(l)} \mathbf{W}^{(l)}\right)$$

This is the GCN you use daily - a simplified, fast spectral approximation.

5. Spectral vs Spatial

	Spectral (ChebNet)	Spatial (GCN, GAT, GIN)
Localization	$K$-hop via polynomial order	Explicit neighbor aggregation
Transferability	Same polynomial across graphs	Natural across graphs
Speed	Good with sparse ops	Good, more flexible
Adoption	Research heritage	Industry default

Modern graph transformers use Laplacian eigenvectors as positional encodings - spectral ideas live on in spatial models.