Graph Fourier transform


In mathematics, the graph Fourier transform is a mathematical transform which eigendecomposes the Laplacian matrix of a graph into eigenvalues and eigenvectors. Analogously to the classical Fourier transform, the eigenvalues represent frequencies and eigenvectors form what is known as a graph Fourier basis.
The Graph Fourier transform is important in spectral graph theory. It is widely applied in the recent study of graph structured learning algorithms, such as the widely employed convolutional networks.

Definition

Given an undirected weighted graph, where is the set of nodes with and is the set of edges, a graph signal is a function defined on the vertices of the graph. The signal maps every vertex to a real number. Any graph signal can be projected on the eigenvectors of the Laplacian matrix. Let and be the eigenvalue and eigenvector of the Laplacian matrix, the graph Fourier transform of a graph signal on the vertices of is the expansion of in terms of the eigenfunctions of. It is defined as:
where.
Since is a real symmetric matrix, its eigenvectors form an orthogonal basis. Hence an inverse graph Fourier transform exists, and it is written as:
Analogously to the classical Fourier transform, graph Fourier transform provides a way to represent a signal in two different domains: the vertex domain and the graph spectral domain. Note that the definition of the graph Fourier transform and its inverse depend on the choice of Laplacian eigenvectors, which are not necessarily unique. The eigenvectors of the normalized Laplacian matrix are also a possible base to define the forward and inverse graph Fourier transform.

Properties

Parseval's identity

The Parseval relation holds for the graph Fourier transform, that is, for any
This gives us Parseval's identity:

Generalized convolution operator

The definition of convolution between two functions and cannot be directly applied to graph signals, because the signal translation is not defined in the context of graphs. However, by replacing the complex exponential shift in classical Fourier transform with the graph Laplacian eigenvectors, convolution of two graph signals can be defined as:

Properties of the convolution operator

The generalized convolution operator satisfies the following properties:

Generalized translation operator

As previously stated, the classical translation operator cannot be generalized to the graph setting. One way to define a generalized translation operator is through generalized convolution with a delta function centered at vertex :
where
The normalization constant ensures that the translation operator preserves the signal mean, i.e.,

Properties of the translation operator

The generalized convolution operator satisfies the following properties:
For any, and,
*

Applications

Image compression

Representing signals in frequency domain is a common approach to data compression. As graph signals can be sparse in their graph spectral domain, the graph Fourier transform can also be used for image compression.

Graph noise reduction

Similar to classical noise reduction of signals based on Fourier transform, graph filters based on the graph Fourier transform can be designed for graph signal denoising.

Data classification

As the graph Fourier transform enables the definition of convolution on graphs, it makes possible to adapt the conventional convolutional neural networks (CNN) to work on graphs. Graph structured semi-supervised learning algorithms such as graph convolutional network, are able to propagate the labels of a graph signal throughout the graph with a small subset of labeled nodes, theoretically operating as a first order approximation of spectral graph convolutions without computing the graph Laplacian and its eigendecomposition.

Toolbox

GSPBOX is a toolbox for signal processing of graphs, including the graph Fourier transform. It supports both Python and MATLAB languages.