Complex Basis For Spectral Analysis of Graph Signals

Rigobert Fokam; Laurent Bitjoka; Hypolyte Egole

doi:https://doi.org/10.14445/22315373/IJMTT-V66I1P533

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 66 | Issue 1 | Year 2020 | Article Id. IJMTT-V66I1P533 | DOI : https://doi.org/10.14445/22315373/IJMTT-V66I1P533

Complex Basis For Spectral Analysis of Graph Signals

Rigobert Fokam, Laurent Bitjoka, Hypolyte Egole

Citation :

Rigobert Fokam, Laurent Bitjoka, Hypolyte Egole, "Complex Basis For Spectral Analysis of Graph Signals," International Journal of Mathematics Trends and Technology (IJMTT), vol. 66, no. 1, pp. 248-260, 2020. Crossref, https://doi.org/10.14445/22315373/IJMTT-V66I1P533

Abstract

The Signal Processing on Graph (SPG) is an emerging field of research aiming to develop accurate methods for big data analysis by combining graph theory and classical signal processing methods. One key method in signal processing on graph is the so-called Graph Fourier Transform (GFT) which is a generalization of the Classical Fourier Transform (defined for data lying on regular domains :1D for times series or 2D for images) to data lying on networks. Those network data are viewed like a set of N interrelated data points lying on a graph whose graph vertices map the data points and graph links encode the relationship between data. In the classical framework, the Fourier transform is a linear operator that performs the mapping of a vector from its initial representation domain to the frequency domain through the Fourier matrix which is an orthonormal basis formed by complex exponential vectors constructed from powers of the complex number ω =e2πi/N. Those vectors are of a key importance in the properties of the transform and its applications. However, for each graph Fourier transform proposed in the literature, although its graph Fourier matrix is orthonormal, its vectors are not complex as in the classical framework, limiting the extension and the use of some useful properties of the classical Fourier transform to the graph signals framework. In this work, we present a method to define a complex orthonormal basis for the graph Fourier transform that allows to perform spectral analysis for graph signals in the frequency domain. The graph Fourier basis we defined is identical to the Fourier basis when applied to graph signals defined on a regular domain. We applied the proposed method successfully to signal detection on an irregularly sampled sensor network.

Keywords

Fourier basis, linear operator, graph signal processing, Laplacian matrix.

References

[1] R.B. Bapat, Graphs and Matrices, ‗‘Hindustan Book Agency‘‘, 2010.
[2] C. Godsil, and G. Royle, ‗‘Algebraic Graph Theory‘‘, volume 207 of Graduate Texts in Mathematics, Springer, 2001.
[3] J. Akiyama and M. Kano, ‗‘Factors and Factorizations of Graphs: Proof Techniques in Factor Theory‘‘, volume 2031 of Lecture Notes in Mathematics, Springer, 2010.
[4] N. Tremblay, ‗‘Signal and networks: signal processing tools for networks analysis‘‘, PhD Thesis, Ecole Normale Supésieur de Lyon, 2014.
[5] G. Proakis, G. Dimitri,‘‘ Digital Signal Processing: Principles, Algorithms and Applications (3 ed.)‘‘, Upper Saddle River, NJ: Prentice-Hall International, 1996.
[6] A. Ortega, P. Frossard, J. Kovǎcevíc, J. M. Moura, and P. Vandergheynst, ―Graph signal processing: Overview, challenges, and applications,‖ Proceedings of the IEEE, vol. 106(5), pp. 808–828, 201
[7] Aliaksei Sandryhaila and José MF Moura, ―Discrete signal processing on graphs,‖ Signal Processing, IEEE Transactions on, vol. 61, no. 7, pp. 1644–1656, 2013.
[8] David I Shuman, Benjamin Ricaud, and Pierre Vandergheynst, ―Vertex-frequency analysis on graphs,‖ Applied and Computational Harmonic Analysis, vol. 40, no. 2, pp. 260–291, 2016.
[9] David K Hammond, Pierre Vandergheynst, and Rémi Gribonval, ―Wavelets on graphs via spectral graph theory,‖ Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129–150, 2011.
[10] Ronald R Coifman and Mauro Maggioni, ―Diffusion wavelets,‖ Applied and Computational Harmonic Analysis, vol. 21, no. 1, pp. 53–94, 2006.
[11] N. Tremblay and P. Borgnat, ―Multiscale detection of stable communities using wavelets on networks‖, European Conference of Complex Systems, 2013.
[12] Maarten Jansen, Guy P Nason, and Bernard W Silverman, ‗‘Multiscale methods for data on graphs and irregular multidimensional situations‘‘, Journal of the Royal Statistical Society : Series B (Statistical Methodology), 71(1) :97–125,2009.
[13] David I Shuman, Mohammad Javad Faraji, and Pierre Vandergheynst, ‗‘A framework for multiscale transforms on graphs‘‘, arXiv preprint arXiv :1308.4942, 2013.
[14] X. Dong, D. Thanou, M. Rabbat, and P. Frossard, ―Learning graphs from data: A signal representation perspective,‖ arXiv preprint arXiv:1806.00848, 2018.
[15] M. Defferrard, X. Bresson, and P. Vandergheynst, ―Convolutional neural networks on graphs with fast localized spectral filtering,‖ in Annu. Conf. Neural Inform. Process. Syst. 2016. Barcelona, Spain: NIPS Foundation, 5-10 Dec. 2016.
[16] F. Gama, A. G. Marques, G. Leus, and A. Ribeiro, ―Convolutional neural network architectures for signals supported on graphs,‖ IEEE Trans. Signal Process., vol. 67, no. 4, pp. 1034–1049, Feb. 2019.
[17] R. Levie, F. Monti, X. Bresson, and M. M. Bronstein, ―CayleyNets: Graph convolutional neural networks with complex rational spectral filters,‖ IEEE Trans. Signal Process., vol. 67(1), pp. 97–107, Jan. 2019.
[18] V. Kalofolias, ―How to learn a graph from smooth signals,‖ in Artificial Intelligence and Statistics, 2016, pp. 920–929.
[19] T. N. Kipf and M. Welling, ―Semi-supervised classification with graph convolutional networks,‖ in 5th Int. Conf. Learning Representations. Toulon, France: Assoc. Comput. Linguistics, 24-26 Apr. 2017.
[20] X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, ―Learning laplacian matrix in smooth graph signal representations,‖ IEEE Transactions on Signal Processing, vol. 64, no. 23, pp. 6160–6173, 2016.
[21] H. E. Egilmez, E. Pavez, and A. Ortega, ―Graph learning from data under laplacian and structural constraints,‖ IEEE Journal of Selected Topics in Signal Processing, vol. 11, no. 6, pp. 825–841, 2017.
[22] A. N. Akansu and H. Agirman-Tosun, "Generalized Discrete Fourier Transform With Nonlinear Phase", IEEE Transactions on Signal Processing, vol. 58, no. 9, pp. 4547-4556, Sept. 2010.
[23] David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst, ―The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,‖ Signal Processing Magazine, IEEE, vol. 30, no. 3, pp. 83–98, 2013.
[24] P. Van Mieghem,‘‘Graph spectra for complex networks‘‘. Cambridge University press, 2011.
[25] B. Girault, A. Ortega Fellow, and S. Narayanan Fellow, ‗‘ Irregularity-Aware Graph Fourier Transforms‘‘, arXiv preprint arXiv:1802.10220ev, Dec 2018.
[26] E. Provenzi, ‗‘The Fourier transform and its applications‘‘, Lecture notes. Institut de mathématique de Bordeaux, Université de Bordeaux.
[27] A. Brandstädt, V.B. Le, and J.P. Spinrad, ‗‘Graph Classes - A Survey‘‘, volume 3. SIAM, Monographs on Discrete Mathematics and Applications, Philadelphia, 1999.
[28] G. Strang, ‗‘The discrete cosine transform‘‘, SIAM Review 1999 41:1, 135-147.
[29] F. Grantmacher, ‗‘The theory of matrices‘‘, volume one. Chelsea publishing company, 1960.
[30] P. Nathanaël, J. Paratte, D. Shuman, L. Martin, V. Kalofolias, P. Vandergheynst and David K. Hammond, ‗‘GSPBOX: A toolbox for signal processing on graphs‘‘, Arxiv e-print, 08-2014.