← All Courses

Discovering Graph Convolutions: From Circulant Matrices to the Graph Laplacian

How the DFT and graph convolutions emerge from the same idea — simultaneous diagonalization of a commuting algebra — applied to two different settings. Following Bamieh (2018), with deeper graph-spectral theory than the Distill.pub treatment.

Prerequisites: Linear algebra (eigenvalues, diagonalization, matrix polynomials), complex exponentials, basic group theory (cyclic groups). No graph theory or signal processing background assumed — everything is built from scratch.
Part I — Discovering the DFT
01

Circulant Matrices and the Shift Operator

Signals on a ring, the shift operator S as a matrix, circulant matrices as polynomials in S, and the algebraic characterization of circular convolution. Running example: Z₈ with kernel h = [3,1,0,0,0,0,0,2].

Sections 1–4 · Eq. 1–6 · Bamieh §3–4 · Z₈ running example
02

Discovering the DFT

Shift invariance as commutativity, the simultaneous diagonalization theorem, constructive derivation of the eigenvectors of S*, and the DFT as a consequence of the algebra. Includes interactive eigenvisual app.

Sections 5–8 · Eq. 7–14 · Bamieh §2–4 · Eigenvisual interactive
03

The Big Picture for ZN

The DFT matrix and spectral filtering recipe, three isomorphic algebras (Bamieh Theorem 5.1), why everything worked (three pillars), and a preview of what will break on graphs.

Sections 9–12 · Eq. 15–20 · Bamieh §5 · Transition to Part II
Part II — Discovering Graph Convolutions
04

From the Ring to General Graphs

Symmetrizing the shift (A = S + S*), eigenvalue collapse and degenerate eigenspaces, the adjacency and Laplacian of a general graph, and the three characterizations revisited — which survive?

Sections 13–17 · Eq. 21–28 · 6-vertex running example · What generalizes table
05

Graph Convolutions — The Two Surviving Characterizations

The graph Fourier transform, spectral graph convolutions, polynomial graph convolutions, connecting spectral and polynomial views, and why the group-theoretic characterization is genuinely lost.

Sections 18–22 · Eq. 29–36 · GFT worked example · Locality of Lk
06

From Spectral Theory to Neural Networks

The computational bottleneck of spectral filtering, ChebNet and Chebyshev polynomial filters, the GCN degree-1 simplification, message passing as a consequence of spectral theory, and oversmoothing.

Sections 23–27 · Eq. 37–44 · Full GCN layer walkthrough · Renormalization trick
07

The Chain of Analogies

The complete ZN ↔ graph analogy table, what we discovered, modern GNN variants in spectral context, pointers to higher-order structures (Hodge Laplacian, TDL course), and further reading.

Sections 28–32 · Eq. 45–48 · Analogy table · Concept map