Abstract: The Graph Fourier Transform (GFT) extends classical Fourier analysis from Euclidean spaces to networks by replacing geometric coordinates with graph topology. Signals defined on nodes are decomposed using eigenvectors of the graph Laplacian, which forms a basis ordered by smoothness with respect to network connectivity. This framework provides a principled notion of frequency on graphs: low frequencies correspond to patterns that vary gradually across edges, while high frequencies capture sharp transitions. The GFT enables filtering, diffusion modelling, and structure-aware signal analysis without relying on spatial coordinates. As a result, it offers a mathematically-grounded toolkit for exploring patterns, communities, and structural behaviour in complex networks.
The Secret Frequencies of Networks
Beneath every network is a hidden spectrum waiting to be uncovered. When people hear “Fourier transform,” they might think of breaking a song into low and high frequencies, or reconstructing images. There is an element of surprise when we consider that similar ideas can work on graphs too. The key is that, despite graphs having no natural notion of “time” or “distance” over some axis, we can replace the combinatorial geometry of the raw graph with a geometry implied by the graph itself.
That probably leaves more questions than answers, so let’s break it down.
Signals on graphs
First imagine a graph, and for simplicity let it be a single connected component. Now imagine attaching a number to each node (not the edges, the nodes).
This assignment is defined as a graph signal, simply a function
ƒ : V → ℝ
where V is the set of nodes.
A crucial component of this theory is the graph Laplacian: L = D – A, where A is the adjacency matrix and D the degree matrix. The Laplacian encodes the variation of signals relative to the network’s connectivity, or its geometric properties.
To construct a frequency domain, we consider the vectors satisfying
Luk = λkuk.
These eigenvectors form an orthonormal basis for functions (signals) on the graph. Then, associated eigenvalues quantify smoothness, where small values correspond to slowly varying patterns across edges, while larger values correspond to rapid or irregular variation.
The Graph Fourier Transform
Any signal can be expanded into this Laplacian basis. The Graph Fourier Transform (GFT) is simply the set of expansion coefficients,
Ƒ(k) = ukTƒ,
and reconstruction follows from summing these components. Conceptually, the GFT expresses a signal in terms of patterns determined by the network’s structure rather than by spatial coordinates.
Once a frequency representation exists, we can filter. A graph filter is any function of the Laplacian
H = g(L),
which scales each spectral component by g(λk). A notable example is the heat kernel gτ(λ) = e-τλ, which suppresses high-frequency variation and produces a smoothed signal corresponding to diffusion across the network.
Why does this matter?
The GFT provides the mathematical toolbox to study signals on irregular domains. Without requiring coordinates, it enables smoothing, pattern extraction, and structural analysis guided purely by topology. This makes it particularly valuable in complex systems (social, financial, or biological) where the network itself is the primary source of information.
In essence, the Graph Fourier Transform reframes networks as domains with their own intrinsic frequency structure, derived directly from connectivity.
James Murray Streitberg
RMIT University
