Graph Fourier Transform¶

Formula¶

\[ \hat{x} = U^\top x \quad\text{and}\quad x = U\hat{x} \]

Parameters¶

\(x \in \mathbb{R}^n\): signal on graph nodes
\(L = U\Lambda U^\top\): eigendecomposition of a (symmetric) graph Laplacian
\(U\): Laplacian eigenvectors (graph Fourier basis)
\(\hat{x}\): graph-frequency coefficients

What it means¶

The graph Fourier transform (GFT) expresses a node signal as a combination of Laplacian eigenvectors, which play the role of Fourier modes on a graph.

Low graph frequencies vary smoothly across connected nodes; high graph frequencies change rapidly across edges.

What it's used for¶

Graph signal denoising and smoothing.
Spectral graph filtering and graph neural network intuition.
Analyzing smoothness of node features relative to graph structure.

Key properties¶

For undirected graphs, Laplacian eigenvectors form an orthonormal basis.
Eigenvalues act like graph frequencies (smaller usually means smoother).
Parseval-style energy preservation holds when \(U\) is orthonormal: \(\|x\|_2^2 = \|\hat{x}\|_2^2\).

Common gotchas¶

The basis depends on the chosen operator (combinatorial vs normalized Laplacian).
For directed graphs, the Laplacian may be non-symmetric, so the basis may not be orthonormal.
Sign flips in eigenvectors are arbitrary and do not change the subspace.

Example¶

If neighboring nodes have similar values, most energy of \(x\) is concentrated in low-frequency GFT coefficients; a high-frequency noise component appears in larger-eigenvalue modes.

How to Compute (Pseudocode)¶

Input: graph Laplacian L, node signal x
Output: graph Fourier coefficients x_hat

compute eigendecomposition L = U Lambda U^T  (for symmetric Laplacian)
x_hat <- U^T x

# Inverse transform (optional reconstruction)
x_reconstructed <- U x_hat
return x_hat

Complexity¶

Time: \(O(n^3)\) for dense eigendecomposition plus \(O(n^2)\) for the matrix-vector transform in dense form
Space: \(O(n^2)\) to store dense eigenvectors (plus \(O(n)\) for signals)
Assumptions: \(n=|V|\); dense symmetric Laplacian eigendecomposition; sparse/partial spectral methods can reduce cost when only a subset of modes is needed