Graph Fourier transform

The Parseval relation holds for the graph Fourier transform,[5] that is, for any ${\displaystyle f,h\in \mathbb {R} ^{N}}$

${\displaystyle \langle f,h\rangle =\langle {\hat {f}},{\hat {h}}\rangle .}$

This gives us Parseval's identity:[3]

${\displaystyle \sum _{i=1}^{N}|f(i)|^{2}=\|f\|_{2}^{2}=\langle f,f\rangle =\langle {\hat {f}},{\hat {f}}\rangle =\|{\hat {f}}\|_{2}^{2}=\sum _{l=0}^{N-1}\left|{\hat {f}}\left(\lambda _{l}\right)\right|^{2}.}$

The definition of convolution between two functions ${\displaystyle f}$ and ${\displaystyle g}$ cannot be directly applied to graph signals, because the signal translation is not defined in the context of graphs.[4] 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:[3]

${\displaystyle (f*g)={\mathcal {I}}{\mathcal {G}}{\mathcal {F}}[{\mathcal {G}}{\mathcal {F}}[f]\cdot {\mathcal {G}}{\mathcal {F}}[g]],}$

${\displaystyle (f*g)(i)=\sum _{l=0}^{N-1}{\hat {f}}(\lambda _{l}){\hat {g}}(\lambda _{l})\mu _{l}(i).}$

The generalized convolution operator satisfies the following properties:[3]

• Generalized convolution in the vertex domain is multiplication in the graph spectral domain: ${\displaystyle {\widehat {f*g}}={\hat {f}}{\hat {g}}.}$
• Commutativity: ${\displaystyle f*g=g*f}$
• Distributivity: ${\displaystyle f*(g+h)=f*g+f*h}$
• Associativity: ${\displaystyle (f*g)*h=f*(g*h)}$
• Associativity with scalar multiplication: ${\displaystyle \alpha (f*g)=(\alpha f)*g=f*(\alpha g)}$, for any ${\displaystyle \alpha \in \mathbb {R} }$.
• Multiplicative identity: ${\displaystyle f*g_{0}=f}$, where ${\displaystyle g_{0}(i)=\sum _{l=0}^{N-1}\mu _{l}(i)}$ is an identity for the generalized convolution operator.
• The sum of the generalized convolution of two signals is a constant times the product of the sums of the two signals:

${\displaystyle \sum _{i=1}^{N}(f*g)(i)={\sqrt {N}}{\hat {f}}(0){\hat {g}}(0)={\frac {1}{\sqrt {N}}}\left[\sum _{i=1}^{N}f(i)\right]\left[\sum _{i=1}^{N}g(i)\right].}$

As previously stated, the classical translation operator ${\displaystyle T_{v}}$ 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 ${\displaystyle n}$:[2]${\displaystyle \left(T_{n}f\right)(i)={\sqrt {N}}\left(f*\delta _{n}\right)(i){=}{\sqrt {N}}\sum _{l=0}^{N-1}{\hat {f}}\left(\lambda _{l}\right)u_{l}^{*}(n)u_{l}(i),}$

where ${\displaystyle \delta _{i}(n)={\begin{cases}1,&{\text{if }}i=n,\\0,&{\text{otherwise.}}\end{cases}}}$

The normalization constant ${\displaystyle {\sqrt {N}}}$ ensures that the translation operator preserves the signal mean,[4] i.e.,

${\displaystyle \sum _{i=1}^{N}(T_{n}f)(i)=\sum _{i=1}^{N}f(i).}$

The generalized convolution operator satisfies the following properties:[3]

For any ${\displaystyle f,g\in \mathbb {R} ^{N}}$, and ${\displaystyle j,k\in \{1,2,\dots ,N\}}$,

• ${\displaystyle T_{j}(f*g)=(T_{j}f)*g=f*(T_{j}g)}$
• ${\displaystyle T_{j}T_{k}f=T_{k}T_{j}f}$
• ${\displaystyle \sum _{i=1}^{N}(T_{j}f)(i)={\sqrt {N}}{\hat {f}}(0)=\sum _{i=1}^{N}f(i)}$
• ${\displaystyle \left\|T_{j}f\right\|\neq \|f\|}$

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.[6][7]

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.[8]

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 (GCN), are able to propagate the labels of a graph signal throughout the graph with a small subset of labelled nodes, theoretically operating as a first order approximation of spectral graph convolutions without computing the graph Laplacian and its eigendecomposition.[9]