Graph Fourier transform explained
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
, where
is the set of nodes with
(
being the number of nodes) 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
.
[1] Let
and
be the
eigenvalue and eigenvector of the
Laplacian matrix
(the eigenvalues are sorted in an increasing order, i.e.,
0=λ0\leqλ1\leq … \leqλN-1
[2]), the graph Fourier transform (GFT)
of a graph signal
on the vertices of
is the expansion of
in terms of the
eigenfunctions of
.
[3] It is defined as:
[4] l{GF}[f](λl)=\hat{f}\left(λl\right)=\langlef,\mul
f(i)
where
.
Since
is a real symmetric matrix, its eigenvectors
form an
orthogonal basis. Hence an inverse graph Fourier transform (IGFT) exists, and it is written as:
| N-1 |
l{I}l{G}l{F}[\hat{f}](i)=f(i)=\sum | |
| l=0 |
\hat{f}(λl)\mul(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,[5] that is, for any
\langlef,h\rangle=\langle\hat{f},\hat{h}\rangle.
This gives us Parseval's identity:
|f(i)|2
f,f\rangle=\langle\hat{f},
| N-1 |
\hat{f}\rangle=\|\hat{f}\| | |
| l=0 |
| 2. |
\left|\hat{f}\left(λ | |
| l\right)\right| |
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:
(f*g)=l{I}l{G}l{F}[l{G}l{F}[f] ⋅ l{G}l{F}[g]],
(f*
\hat{f}(λl)\hat{g}(λl)\mul(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{f*g}=\hat{f}\hat{g}.
- Associativity with scalar multiplication:
\alpha(f*g)=(\alphaf)*g=f*(\alphag)
, for any
.
, where
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:
*g)(i)=\sqrt{N}\hat{f}(0)\hat{g}(0)=
}\left[\sum_{i=1}^N f(i)\right] \left[\sum_{i=1}^N g(i)\right].
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
:
\left(Tnf\right)(i)=\sqrt{N}\left(f*\deltan\right)(i){=}\sqrt{N}
\hat{f}\left(λl\right)
(n)ul(i),
where
\deltai(n)=\begin{cases}
1,&ifi=n,\\
0,&otherwise.
\end{cases}
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
,
\left\|Tjf\right\| ≠ \|f\|
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.[6] [7]
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.[8]
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 labelled nodes, theoretically operating as a first order approximation of spectral graph convolutions without computing the graph Laplacian and its eigendecomposition.[9]
Toolbox
GSPBOX[10] [11] is a toolbox for signal processing of graphs, including the graph Fourier transform. It supports both Python and MATLAB languages.
References
- Ricaud. Benjamin. Borgnat. Pierre. Tremblay. Nicolas. Gonçalves. Paulo. Vandergheynst. Pierre. 2019-07-01. Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs. Comptes Rendus Physique. Fourier and the science of today / Fourier et la science d’aujourd’hui. en. 20. 5. 474–488. 10.1016/j.crhy.2019.08.003. 2019CRPhy..20..474R. 1631-0705. free.
- Shuman. David I. Narang. Sunil K.. Frossard. Pascal. Ortega. Antonio. Vandergheynst. Pierre. May 2013. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine. 30. 3. 83–98. 10.1109/MSP.2012.2235192. 1558-0792. 1211.0053. 2013ISPM...30...83S. 1594725.
- Shuman. David I. Ricaud. Benjamin. Vandergheynst. Pierre. 2016-03-01. Vertex-frequency analysis on graphs. Applied and Computational Harmonic Analysis. en. 40. 2. 260–291. 10.1016/j.acha.2015.02.005. 1063-5203. free. 1307.5708.
- Web site: Nonato. Luis Gustavo. 2017-08-29. Graph Fourier Transform.
- Hammond. David K.. Vandergheynst. Pierre. Gribonval. Rémi. 2011-03-01. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis. en. 30. 2. 129–150. 10.1016/j.acha.2010.04.005. 1063-5203. 0912.3848. 5593503.
- Book: Sandryhaila. Aliaksei. Moura. Jose M. F.. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing . Discrete signal processing on graphs: Graph fourier transform . May 2013. 6167–6170. IEEE. 10.1109/icassp.2013.6638850. 978-1-4799-0356-6. 14704192.
- Hu. Wei. Cheung. Gene. Ortega. Antonio. Au. Oscar C.. January 2015. Multiresolution Graph Fourier Transform for Compression of Piecewise Smooth Images. IEEE Transactions on Image Processing. 24. 1. 419–433. 10.1109/TIP.2014.2378055. 25494508. 2015ITIP...24..419H. 9539186. 1941-0042.
- Sandryhaila. Aliaksei. Moura. José M. F.. June 2014. Discrete Signal Processing on Graphs: Frequency Analysis. IEEE Transactions on Signal Processing. 62. 12. 3042–3054. 10.1109/TSP.2014.2321121. 2014ITSP...62.3042.. 12110057. 1941-0476. 1307.0468.
- Kipf. Thomas N.. Welling. Max. 2017-02-22. Semi-Supervised Classification with Graph Convolutional Networks. cs.LG. 1609.02907.
- Perraudin. Nathanaël. Paratte. Johan. Shuman. David. Martin. Lionel. Kalofolias. Vassilis. Vandergheynst. Pierre. Hammond. David K.. 2016-03-15. GSPBOX: A toolbox for signal processing on graphs. cs.IT. 1408.5781.
- Web site: PyGSP: Graph Signal Processing in Python — PyGSP 0.5.1 documentation. 2020-06-22. pygsp.readthedocs.io.
External links
- DeepGraphLibrary A free Python package built for easy implementation of graph neural networks.