Fourier transform of a function on a graph

What is a Fourier transform at its core? An expansion of function in terms of eigenfunctions of the Laplacian. For a function on the real line, the Laplacian is simply the second derivative. The functions mapped to multiples of themselves by taking second derivatives are sines and cosines of various frequencies. A Fourier series is a change of basis, using as basis vectors those functions who behave the simplest under the second derivative.

The Fourier transform of a function on a graph is also a change of basis, expanding a discrete function in terms of eigenvalues of the Laplacian, in this case the graph Laplacian.

The Fourier transform of a function f, evaluated at a frequency I, is the inner product of f with the eigenfunction exp(2IiIt).

The inner product of two complex functions f and g is the integral of the product of f and the conjugate of g. Conjugation is why exp(2IiIt) became exp(-2IiIt).

The Fourier transform of a discrete function f on a graph, evaluated at an eigenvalue I_i, is the inner product of f (i.e. the vector of values of f at each node) with the eigenvector associated with I_i.

Here the inner product is a discrete sum rather than an integral. As before, we take the complex conjugate of the second item in the product.

The eigenvectors associated with the smallest eigenvalues of the graph Laplacian are analogous to low frequency sines and cosines. The eigenvalue components corresponding to nearly vertices in a graph should be close together. This analogy explains why spectral coordinates work so well.

Related:

• Discrete harmonic functions
• Can you hear the shape of a network?
• Complex networks