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 $G = (V,E)$, where $V$ is the set of nodes with $, V, = N$ ($N$ being the number of nodes) and $E$ is the set of edges, a graph signal $f: V \rightarrow \mathbb$ is a function defined on the vertices of the graph $G$. The signal $f$ maps every vertex $\_$ to a real number $f(i)$. Any graph signal can be projected on the eigenvectors of the Laplacian matrix $L$. Let $\lambda_l$ and $\mu_l$ be the $l_\text$ eigenvalue and eigenvector of the Laplacian matrix $L$ (the eigenvalues are sorted in an increasing order, i.e., $0= \lambda_0\leq\lambda_1\leq\cdots\leq\lambda_$), the graph Fourier transform (GFT) $\hat$ of a graph signal $f$ on the vertices of $G$ is the expansion of $f$ in terms of the eigenfunctions of $L$. It is defined as:

: \mathcal \lambda_)=\hat\left(\lambda_\right)=\langle f, \mu_\rangle=\sum_^ f(i) \mu_^*(i),

where $\mu_l^* = \mu_l^\text$.

Since $L$ is a real symmetric matrix, its eigenvectors $\_$ form an orthogonal basis. Hence an inverse graph Fourier transform (IGFT) exists, and it is written as:

: \mathcal \mathcal \mathcal hati)=f(i)=\sum_^ \hat(\lambda_l) \mu_l(i)

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 $f,h\in \mathbb^N$

: $\langle f, h\rangle=\langle\hat, \hat\rangle.$

This gives us Parseval's identity:

: $\sum_^N , f(i), ^=\, f\, _2^2=\langle f, f\rangle=\langle\hat, \hat\rangle=\, \hat\, _2^2=\sum_^ \left, \hat\left(\lambda_l\right)\^2.$

Generalized convolution operator

The definition of convolution between two functions $f$ and $g$ 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:

: (f * g)=\mathcal \mathcal \mathcal mathcal \mathcal[f\cdot \mathcal \mathcal[g">.html" ;"title="mathcal \mathcal[f">mathcal \mathcal[f\cdot \mathcal \mathcal[g,

: $(f * g)(i)=\sum_^ \hat(\lambda_l) \hat(\lambda_l) \mu_l(i).$

Properties of the convolution operator

The generalized convolution operator satisfies the following properties:

* Generalized convolution in the vertex domain is multiplication in the graph spectral domain: $\widehat=\hat \hat.$
* Commutativity