graph Fourier transform

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\; \backslash rightarrow\; \backslash mathbb\{R\}$ is a function defined on the vertices of the graph $G$. The signal $f$ maps every vertex $\backslash \{v\_i\backslash \}\_\{i=1,\backslash ldots,N\}$ to a real number $f(i)$. Any graph signal can be projected on the eigenvectors of the Laplacian matrix $L$.{{Cite journal|last1=Ricaud|first1=Benjamin|last2=Borgnat|first2=Pierre|last3=Tremblay|first3=Nicolas|last4=Gonçalves|first4=Paulo|last5=Vandergheynst|first5=Pierre|date=2019-07-01|title=Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs|journal=Comptes Rendus Physique|series=Fourier and the science of today / Fourier et la science d’aujourd’hui|language=en|volume=20|issue=5|pages=474–488|doi=10.1016/j.crhy.2019.08.003|bibcode=2019CRPhy..20..474R|issn=1631-0705|doi-access=free}} Let $\backslash lambda\_l$ and $\backslash mu\_l$ be the $l\_\backslash text\{th\}$ eigenvalue and eigenvector of the Laplacian matrix $L$ (the eigenvalues are sorted in an increasing order, i.e., $0=\; \backslash lambda\_0\backslash leq\backslash lambda\_1\backslash leq\backslash cdots\backslash leq\backslash lambda\_\{N-1\}${{Cite journal|last1=Shuman|first1=David I|last2=Narang|first2=Sunil K.|last3=Frossard|first3=Pascal|last4=Ortega|first4=Antonio|last5=Vandergheynst|first5=Pierre|date=May 2013|title=The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains|journal=IEEE Signal Processing Magazine|volume=30|issue=3|pages=83–98|doi=10.1109/MSP.2012.2235192|issn=1558-0792|arxiv=1211.0053|bibcode=2013ISPM...30...83S|s2cid=1594725}}), the graph Fourier transform (GFT) $\backslash hat\{f\}$ of a graph signal $f$ on the vertices of $G$ is the expansion of $f$ in terms of the eigenfunctions of $L$.{{Cite journal|last1=Shuman|first1=David I|last2=Ricaud|first2=Benjamin|last3=Vandergheynst|first3=Pierre|date=2016-03-01|title=Vertex-frequency analysis on graphs|journal=Applied and Computational Harmonic Analysis|language=en|volume=40|issue=2|pages=260–291|doi=10.1016/j.acha.2015.02.005|issn=1063-5203|doi-access=free|arxiv=1307.5708}} It is defined as:{{Cite web|last=Nonato|first=Luis Gustavo|date=2017-08-29|title=Graph Fourier Transform|url=https://sites.icmc.usp.br/gnonato/gs/slide3.pdf|archive-url=|archive-date=|access-date=|website=}}

: $\backslash mathcal\{G\; F\}[f](\backslash lambda\_\{l\})=\backslash hat\{f\}\backslash left(\backslash lambda\_\{l\}\backslash right)=\backslash langle\; f,\; \backslash mu\_\{l\}\backslash rangle=\backslash sum\_\{i=1\}^\{N\}\; f(i)\; \backslash mu\_\{l\}^*(i),$

where $\backslash mu\_l^*\; =\; \backslash mu\_l^\backslash text\{T\}$.

Since $L$ is a real symmetric matrix, its eigenvectors $\backslash \{\backslash mu\_l\backslash \}\_\{l=0,\backslash cdots,\; N-1\}$ form an orthogonal basis. Hence an inverse graph Fourier transform (IGFT) exists, and it is written as:

: $\backslash mathcal\{I\}\; \backslash mathcal\{G\}\; \backslash mathcal\{F\}[\backslash hat\{f\}](i)=f(i)=\backslash sum\_\{l=0\}^\{N-1\}\; \backslash hat\{f\}(\backslash lambda\_l)\; \backslash 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.

The Parseval relation holds for the graph Fourier transform,{{Cite journal|last1=Hammond|first1=David K.|last2=Vandergheynst|first2=Pierre|last3=Gribonval|first3=Rémi|date=2011-03-01|title=Wavelets on graphs via spectral graph theory|url=http://www.sciencedirect.com/science/article/pii/S1063520310000552|journal=Applied and Computational Harmonic Analysis|language=en|volume=30|issue=2|pages=129–150|doi=10.1016/j.acha.2010.04.005|issn=1063-5203|arxiv=0912.3848|s2cid=5593503}} that is, for any $f,h\backslash in\; \backslash mathbb\{R\}^N$

: $\backslash langle\; f,\; h\backslash rangle=\backslash langle\backslash hat\{f\},\; \backslash hat\{h\}\backslash rangle.$

This gives us Parseval's identity:

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

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)=\backslash mathcal\{I\}\; \backslash mathcal\{G\}\; \backslash mathcal\{F\}[\backslash mathcal\{G\}\; \backslash mathcal\{F\}[f]\; \backslash cdot\; \backslash mathcal\{G\}\; \backslash mathcal\{F\}[g]],$

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

The generalized convolution operator satisfies the following properties:

• Generalized convolution in the vertex domain is multiplication in the graph spectral domain: $\backslash widehat\{f\; *\; g\}=\backslash hat\{f\}\; \backslash hat\{g\}.$
• Commutativity: $f\; *\; g=g\; *\; f$
• Distributivity: $f\; *\; (g+h)=f*g\; +\; f*h$
• Associativity: $(f*g)*h\; =\; f*(g*h)$
• Associativity with scalar multiplication: $\backslash alpha(f\; *\; g)=(\backslash alpha\; f)\; *\; g=f\; *(\backslash alpha\; g)$, for any $\backslash alpha\; \backslash in\; \backslash mathbb\{R\}$.
• Multiplicative identity: $f\; *\; g\_0=f$, where $g\_0(i)=\backslash sum\_\{l=0\}^\{N-1\}\; \backslash 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:

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

As previously stated, the classical translation operator $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 $n$:$\backslash left(T\_\{n\}\; f\backslash right)(i)=\backslash sqrt\{N\}\backslash left(f\; *\; \backslash delta\_\{n\}\backslash right)(i)\{=\}\; \backslash sqrt\{N\}\; \backslash sum\_\{l=0\}^\{N-1\}\; \backslash hat\{f\}\backslash left(\backslash lambda\_\{l\}\backslash right)\; u\_\{l\}^\{*\}(n)\; u\_\{l\}(i),$

where $\backslash delta\_i(n)=\backslash begin\{cases\}$

1, & \text {if } i=n, \\

0, & \text {otherwise.}

\end{cases}

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

: $\backslash sum\_\{i=1\}^N(T\_n\; f)(i)=\backslash sum\_\{i=1\}^N\; f(i).$

The generalized convolution operator satisfies the following properties:

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

• $T\_j(f\; *\; g)=(T\_j\; f)\; *\; g=f\; *(T\_\{j\}\; g)$
• $T\_j\; T\_k\; f=T\_k\; T\_j\; f$
• $\backslash sum\_\{i=1\}^N\; (T\_j\; f)(i)=\backslash sqrt\{N\}\; \backslash hat\{f\}(0)=\backslash sum\_\{i=1\}^N\; f(i)$
• $\backslash left\backslash |T\_j\; f\backslash right\backslash |\; \backslash neq\; \backslash |\; f\; \backslash |$

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.{{Cite book|last1=Sandryhaila|first1=Aliaksei|last2=Moura|first2=Jose M. F.|title=2013 IEEE International Conference on Acoustics, Speech and Signal Processing |chapter=Discrete signal processing on graphs: Graph fourier transform |date=May 2013|pages=6167–6170|publisher=IEEE|doi=10.1109/icassp.2013.6638850|isbn=978-1-4799-0356-6|s2cid=14704192}}{{Cite journal|last1=Hu|first1=Wei|last2=Cheung|first2=Gene|last3=Ortega|first3=Antonio|last4=Au|first4=Oscar C.|date=January 2015|title=Multiresolution Graph Fourier Transform for Compression of Piecewise Smooth Images|journal=IEEE Transactions on Image Processing|volume=24|issue=1|pages=419–433|doi=10.1109/TIP.2014.2378055|pmid=25494508|bibcode=2015ITIP...24..419H|s2cid=9539186|issn=1941-0042}}

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.{{Cite journal|last1=Sandryhaila|first1=Aliaksei|last2=Moura|first2=José M. F.|date=June 2014|title=Discrete Signal Processing on Graphs: Frequency Analysis|journal=IEEE Transactions on Signal Processing|volume=62|issue=12|pages=3042–3054|doi=10.1109/TSP.2014.2321121|bibcode=2014ITSP...62.3042.|s2cid=12110057|issn=1941-0476|arxiv=1307.0468}}

=== 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 (GCN), 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.{{cite arXiv|last1=Kipf|first1=Thomas N.|last2=Welling|first2=Max|date=2017-02-22|title=Semi-Supervised Classification with Graph Convolutional Networks|class=cs.LG|eprint=1609.02907}}

GSPBOX{{cite arXiv|last1=Perraudin|first1=Nathanaël|last2=Paratte|first2=Johan|last3=Shuman|first3=David|last4=Martin|first4=Lionel|last5=Kalofolias|first5=Vassilis|last6=Vandergheynst|first6=Pierre|last7=Hammond|first7=David K.|date=2016-03-15|title=GSPBOX: A toolbox for signal processing on graphs|class=cs.IT|eprint=1408.5781}}{{Cite web|title=PyGSP: Graph Signal Processing in Python — PyGSP 0.5.1 documentation|url=https://pygsp.readthedocs.io/en/stable/|access-date=2020-06-22|website=pygsp.readthedocs.io}} is a toolbox for signal processing of graphs, including the graph Fourier transform. It supports both Python and MATLAB languages.

• [https://www.dgl.ai/ DeepGraphLibrary] A free Python package built for easy implementation of graph neural networks.

Category:Graph theory

Category:Fourier analysis