Course contentsShow
← Machine Learning and Deep Learning
Lesson 2499 of 3,53854. Graph Neural NetworksFree lesson

Spectral Graph Convolutions

Learn how convolutions generalize to graphs through spectral filtering in the graph Fourier domain.

Spectral Graph Convolutions

What you'll learn: How to perform convolutions on graph-structured data by working in the frequency domain using graph spectral theory.

The Core Idea

Traditional CNNs convolve filters across image grids, but graphs have no regular grid structure. Spectral graph convolutions solve this by transforming graph signals into the "frequency domain" using the graph Laplacian's eigenvectors, applying filters there, and transforming back.

Think of it like audio processing: instead of manipulating sound waves directly in time, you work in the frequency domain (via Fourier transform), apply filters, then convert back. Here, the graph Fourier transform uses eigenvectors of the graph Laplacian as the basis.

How It Works

Given node features x and the graph Laplacian L:

  1. Decompose L: Compute eigenvalues Λ and eigenvectors U where L = UΛU^T
  2. Transform to spectral domain: Project features using U^T x
  3. Apply spectral filter: Multiply by a learnable diagonal filter matrix g(Λ)
  4. Transform back: Apply U to return to graph domain

The convolution becomes: y = U g(Λ) U^T x

The learnable parameters are in g(Λ), which defines how each frequency component is weighted—smooth filters emphasize low frequencies (global patterns), while sharp filters capture high frequencies (local variations).

Limitations

This approach is elegant but computationally expensive: eigen-decomposition costs O(n³) for n nodes, and the filters aren't spatially localized. This motivated later spatial approaches (like message passing) that aggregate neighborhoods directly without spectral decomposition.

Key Takeaway: Spectral graph convolutions generalize CNNs to graphs by filtering node features in the graph's frequency domain, defined by the eigenbasis of the Laplacian—though computationally costly, they laid theoretical groundwork for modern GNNs.