Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs

Benjamin Ricaud; Pierre Borgnat; Nicolas Tremblay; Paulo Gonçalves; Pierre Vandergheynst

doi:10.1016/j.crhy.2019.08.003

Fourier and the science of today / Fourier et la science d'aujourd'hui

Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs
[Fourier serait un data scientist : de la transformée de Fourier sur graphe au traitement du signal sur graphe]

Benjamin Ricaud ¹ ; Pierre Borgnat ² ; Nicolas Tremblay ³ ; Paulo Gonçalves ⁴ ; Pierre Vandergheynst ¹

¹ Signal Processing Laboratory 2 (LTS2), École polytechnique fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland
² Université de Lyon, CNRS, ENS de Lyon, UCB Lyon-1, Laboratoire de physique, UMR 5672, 69342 Lyon, France
³ CNRS, Université Grenoble-Alpes, Gipsa-lab, France
⁴ Université de Lyon, Inria, CNRS, ENS de Lyon, UCB Lyon-1, LIP UMR 5668, 69342 Lyon, France

Comptes Rendus. Physique, Volume 20 (2019) no. 5, pp. 474-488.

Résumé
Abstract

Les travaux de Joseph Fourier se sont avérés extrêmement féconds, et la transformée portant son nom est, aujourd'hui encore, incontournable. La souplesse de cette analyse, son efficacité calculatoire et l'interprétation physique qu'elle offre la met au cœur de nombreux domaines scientifiques. Avec l'explosion du nombre et de la diversité des données numériques, la généralisation des outils d'analyse s'appuyant sur la transformation de Fourier est plus que jamais nécessaire. C'est en particulier le cas en science des données, et spécifiquement en science des réseaux. De nouveaux problèmes se posent quant à l'extraction d'information à partir de données qui ont des structures irrégulières, comme des réseaux sociaux, biologiques ou autres données sur des graphes potentiellement arbitraires. Le traitement du signal sur graphe est une des directions prometteuses dédiées à ce type de données. Ce texte présente un état de l'art du domaine, en se concentrant d'abord sur la façon de définir une transformée de Fourier pour des données sur graphes, comment l'interpréter et enfin comment l'utiliser pour étudier ces données. Il se termine par une discussion sur de possibles utilisations. Ce faisant, ce travail illustre en quoi la démarche de Fourier reste moderne et universelle et montre comment ses idées, essentiellement issues de la physique, puis enrichies par les mathématiques, l'informatique et la théorie du signal, demeurent essentielles pour répondre aux défis actuels en science des données.

The legacy of Joseph Fourier in science is vast, especially thanks to the essential tool that the Fourier transform is. The flexibility of this analysis, its computational efficiency and the physical interpretation it offers makes it a cornerstone in many scientific domains. With the explosion of digital data, both in quantity and diversity, the generalization of the tools based on Fourier transform is mandatory. In data science, new problems arose for the processing of irregular data such as social networks, biological networks or other data on networks. Graph signal processing is a promising approach to deal with those. The present text is an overview of the state of the art in graph signal processing, focusing on how to define a Fourier transform for data on graphs, how to interpret it and how to use it to process such data. It closes showing some examples of use. Along the way, the review reveals how Fourier's work remains modern and universal, and how his concepts, coming from physics and blended with mathematics, computer science, and signal processing, play a key role in answering the modern challenges in data science.

Publié le : 2019-07-01

DOI : 10.1016/j.crhy.2019.08.003

Keywords: Graph signal processing, Fourier transform, Wavelets, Data science, Machine learning
Mot clés : Traitement du signal sur graphe, Transformée de Fourier, Ondelettes, Science des données, Apprentissage machine

Affiliations des auteurs :

Benjamin Ricaud ¹ ; Pierre Borgnat ² ; Nicolas Tremblay ³ ; Paulo Gonçalves ⁴ ; Pierre Vandergheynst ¹

@article{CRPHYS_2019__20_5_474_0,
     author = {Benjamin Ricaud and Pierre Borgnat and Nicolas Tremblay and Paulo Gon\c{c}alves and Pierre Vandergheynst},
     title = {Fourier could be a data scientist: {From} graph {Fourier} transform to signal processing on graphs},
     journal = {Comptes Rendus. Physique},
     pages = {474--488},
     publisher = {Elsevier},
     volume = {20},
     number = {5},
     year = {2019},
     doi = {10.1016/j.crhy.2019.08.003},
     language = {en},
}

TY  - JOUR
AU  - Benjamin Ricaud
AU  - Pierre Borgnat
AU  - Nicolas Tremblay
AU  - Paulo Gonçalves
AU  - Pierre Vandergheynst
TI  - Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs
JO  - Comptes Rendus. Physique
PY  - 2019
SP  - 474
EP  - 488
VL  - 20
IS  - 5
PB  - Elsevier
DO  - 10.1016/j.crhy.2019.08.003
LA  - en
ID  - CRPHYS_2019__20_5_474_0
ER  -

%0 Journal Article
%A Benjamin Ricaud
%A Pierre Borgnat
%A Nicolas Tremblay
%A Paulo Gonçalves
%A Pierre Vandergheynst
%T Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs
%J Comptes Rendus. Physique
%D 2019
%P 474-488
%V 20
%N 5
%I Elsevier
%R 10.1016/j.crhy.2019.08.003
%G en
%F CRPHYS_2019__20_5_474_0

Benjamin Ricaud; Pierre Borgnat; Nicolas Tremblay; Paulo Gonçalves; Pierre Vandergheynst. Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs. Comptes Rendus. Physique, Volume 20 (2019) no. 5, pp. 474-488. doi : 10.1016/j.crhy.2019.08.003. https://comptes-rendus.academie-sciences.fr/physique/articles/10.1016/j.crhy.2019.08.003/

Bibliographie
Cité par

[1] J.B.J. Fourier Théorie analytique de la chaleur, Chez Firmin Didot, père et fils, 1822

[2] J.W. Tukey The future of data analysis, Ann. Math. Stat., Volume 33 (1962) no. 1, pp. 1-67

[3] D. Donoho 50 years of data science, J. Comput. Graph. Stat., Volume 26 (2017) no. 4, pp. 745-766

[4] E.D. Kolaczyk Statistical Analysis of Network Data: Methods and Models, Springer, 2009

[5] M.E.J. Newman Networks: An Introduction, Oxford University Press, 2010

[6] A. Barrat; M. Barthlemy; A. Vespignani Dynamical Processes on Complex Networks, Cambridge University Press, 2008

[7] D.I. Shuman; S.K. Narang; P. Frossard; A. Ortega; P. Vandergheynst The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag., Volume 30 (2013) no. 3, pp. 83-98

[8] D.K. Hammond; P. Vandergheynst; R. Gribonval Wavelets on graphs via spectral graph theory, Appl. Comput. Harmon. Anal., Volume 30 (2011) no. 2, pp. 129-150

[9] S.K. Narang; A. Ortega Perfect reconstruction two-channel wavelet filter banks for graph structured data, IEEE Trans. Signal Process., Volume 60 (2012) no. 6, pp. 2786-2799

[10] S.K. Narang; A. Ortega Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs, IEEE Trans. Signal Process., Volume 61 (2013) no. 19, pp. 4673-4685

[11] A. Agaskar; Y.M. Lu A spectral graph uncertainty principle, IEEE Trans. Inf. Theory, Volume 59 (2013) no. 7, pp. 4338-4356

[12] A. Sandryhaila; J.M.F. Moura Discrete signal processing on graphs, IEEE Trans. Signal Process., Volume 61 (2013) no. 7, pp. 1644-1656

[13] A. Ortega; P. Frossard; J. Kovačević; J.M.F. Moura; P. Vandergheynst Graph signal processing: overview, challenges, and applications, Proc. IEEE, Volume 106 ( May 2018 ) no. 5, pp. 808-828

[14] Cooperative and Graph Signal Processing (P.M. Djurić; C. Richard, eds.), Elsevier, 2018

[15] Image Processing and Analysis with Graphs. Theory and Practice (O. Lezoray; L. Grady, eds.), CRC Press, 2012

[16] Vertex-Frequency Analysis of Graph Signals (L. Stanković; E. Sejdi, eds.), Springer, 2019

[17] P. Flandrin Time-Frequency/Time-Scale Analysis, Academic Press, 1999

[18] G. Strang The discrete cosine transform, SIAM Rev., Volume 41 (1999) no. 1, pp. 135-147

[19] F.R.K. Chung; F.C. Graham Spectral Graph Theory, Regional Conference Series in Mathematics, vol. 92, American Mathematical Society, Providence, RI, USA, 1997

[20] F. Chung Laplacians and the Cheeger inequality for directed graphs, Ann. Comb., Volume 9 (2005) no. 1, pp. 1-19

[21] H. Sevi; G. Rilling; P. Borgnat Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets, 2018 (arXiv preprint) | arXiv

[22] L. Grady; J.R. Polimeni Discrete Calculus: Applied Analysis on Graphs for Computational Science, Springer, 2010

[23] U. Von Luxburg A tutorial on spectral clustering, Stat. Comput., Volume 17 (2007) no. 4, pp. 395-416

[24] D.L. Donoho; P.B. Stark Uncertainty principles and signal recovery, SIAM J. Appl. Math., Volume 49 (1989) no. 3, pp. 906-931

[25] B. Ricaud; B. Torrésani A survey of uncertainty principles and some signal processing applications, Adv. Comput. Math., Volume 40 (2014) no. 3, pp. 629-650

[26] B. Ricaud; B. Torrésani Refined support and entropic uncertainty inequalities, IEEE Trans. Inf. Theory, Volume 59 (2013) no. 7, pp. 4272-4279

[27] N. Perraudin; B. Ricaud; D.I. Shuman; P. Vandergheynst Global and local uncertainty principles for signals on graphs, APSIPA Trans. Signal Inf. Process., Volume 7 (2018)

[28] A. Anis; A. Gadde; A. Ortega Efficient sampling set selection for bandlimited graph signals using graph spectral proxies, IEEE Trans. Signal Process., Volume 64 (2016) no. 14, pp. 3775-3789

[29] N. Tremblay; P. Gonçalves; P. Borgnat Design of graph filters and filterbanks (P.M. Djurić; C. Richard, eds.), Cooperative and Graph Signal Processing, Elsevier, 2018, pp. 299-324

[30] S. Sardellitti; S. Barbarossa; P. Di Lorenzo On the graph Fourier transform for directed graphs, IEEE J. Sel. Top. Signal Process., Volume 11 (2017) no. 6, pp. 796-811

[31] R. Shafipour; A. Khodabakhsh; G. Mateos; E. Nikolova A digraph Fourier transform with spread frequency components, 2017 (arXiv preprint) | arXiv

[32] E. Isufi; A. Loukas; A. Simonetto; G. Leus Autoregressive moving average graph filtering, IEEE Trans. Signal Process., Volume 65 (2017) no. 2, pp. 274-288

[33] J. Liu, E. Isufi, G. Leus, Autoregressive moving average graph filter design, in: Proc. 6th Joint WIC/IEEE Symposium on Information Theory and Signal Processing in the Benelux, Louvain-la-Neuve, Belgium, 19–20 May 2016.

[34] N. Tremblay, P. Borgnat, P. Flandrin, Graph empirical mode decomposition, in: Proc. European Signal Processing Conference (EUSIPCO 2014), Lisbon, Portugal, 1–5 September 2014, pp. 2350–2354.

[35] D.I. Shuman; B. Ricaud; P. Vandergheynst Vertex-frequency analysis on graphs, Appl. Comput. Harmon. Anal., Volume 40 (2016) no. 2, pp. 260-291

[36] B. Girault; P. Goncalves; E. Fleury Translation on graphs: an isometric shift operator, IEEE Signal Process. Lett., Volume 22 (2015) no. 12

[37] N. Grelier, B. Pasdeloup, J. Vialatte, V. Gripon, Neighborhood-preserving translations on graphs, in: 2016 Proc. IEEE Global Conference on Signal and Information Processing, Greater Washington, D.C., USA, 7–9 December 2016, pp. 410–414.

[38] S. Chen; R. Varma; A. Sandryhaila; J. Kovacevic Discrete signal processing on graphs: sampling theory, IEEE Trans. Signal Process., Volume 63 (2015) no. 24, pp. 6510-6523

[39] L.F.O. Chamon; A. Ribeiro Greedy sampling of graph signals, IEEE Trans. Signal Process., Volume 66 (2018) no. 1, pp. 34-47

[40] A. Sakiyama; Y. Tanaka; T. Tanaka; A. Ortega Eigendecomposition-free sampling set selection for graph signals, IEEE Trans. Signal Process., Volume 67 (2019) no. 10, pp. 2679-2692

[41] Y.H. Kim; A. Ortega Toward Optimal rate allocation to sampling sets for bandlimited graph signals, IEEE Signal Process. Lett., Volume 26 (2019) no. 9, pp. 3775-3789

[42] M. Tsitsvero; S. Barbarossa; P. Di Lorenzo Signals on graphs: uncertainty principle and sampling, IEEE Trans. Signal Process., Volume 64 (2016) no. 18, pp. 4845-4860

[43] N. Tremblay, P.O. Amblard, S. Barthelmé, Graph sampling with determinantal processes, in: Proc. 25th European Signal Processing Conference (EUSIPCO 2017), Kos Island, Greece, 28 August–2 September 2017, pp. 1674–1678.

[44] G. Puy; N. Tremblay; R. Gribonval; P. Vandergheynst Random sampling of bandlimited signals on graphs, Appl. Comput. Harmon. Anal., Volume 44 (2018) no. 2, pp. 446-475

[45] P. Di Lorenzo; S. Barbarossa; P. Banelli Sampling and recovery of graph signals (P. Djuric; C. Richard, eds.), Cooperative and Graph Signal Processing, Elsevier, 2018, pp. 261-282

[46] L. Cohen Time-Frequency Analysis, Prentice-Hall, 1995

[47] P. Flandrin Explorations in Time-Frequency Analysis, Cambridge University Press, 2018

[48] I. Daubechies Ten Lectures on Wavelets, SIAM, 1992

[49] S. Mallat A Wavelet Tour of Signal Processing, Academic Press, 1999

[50] D.I. Shuman; M.J. Faraji; P. Vandergheynst A multiscale pyramid transform for graph signals, IEEE Trans. Signal Process., Volume 64 (2016) no. 8, pp. 2119-2134

[51] N. Tremblay; P. Borgnat Subgraph-based filterbanks for graph signals, IEEE Trans. Signal Process., Volume 64 ( August 2016 ) no. 15

[52] J. Irion; N. Saito Hierarchical graph Laplacian eigen transforms, JSIAM Lett., Volume 6 (2014), pp. 21-24

[53] L. Avena; F. Castell; A. Gaudillière; C. Mélot Intertwining wavelets or multiresolution analysis on graphs through random forests, Appl. Comput. Harmon. Anal. (2018)

[54] R.R. Coifman; M. Maggioni Diffusion wavelets, Appl. Comput. Harmon. Anal., Volume 21 (2006) no. 1, pp. 53-94

[55] D. Thanou; D.I. Shuman; P. Frossard Learning parametric dictionaries for signals on graphs, IEEE Trans. Signal Process., Volume 62 (2014) no. 15, pp. 3849-3862

[56] X. Zhang, X. Dong, P. Frossard, Learning of structured graph dictionaries, in: Proc. 37th IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2012), Kyoto, Japan, 25–30 March 2012, pp. 3373–3376.

[57] N. Huang; Z. Shen; S. Long; M. Wu; H. Shih; Q. Zheng; N.C. Yen; C.C. Tung; H. Liu The empirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary time series analysis, Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci., Volume 454 (1998) no. 1971, pp. 903-995

[58] G. Cheung; E. Magli; Y. Tanaka; M.K. Ng Graph spectral image processing, Proc. IEEE, Volume 106 (2018) no. 5, pp. 907-930

[59] X. Zhu, M. Rabbat, Graph spectral compressed sensing for sensor networks, in: Proc. 37th IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2012), Kyoto, Japan, 25–30 March 2012, pp. 2865–286.

[60] H.E. Egilmez, A. Ortega, Spectral anomaly detection using graph-based filtering for wireless sensor networks, in: Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2014), Florence, Italy, 4–9 May 2014, pp. 1085–1089.

[61] F. Grassi; A. Loukas; N. Perraudin; B. Ricaud A time-vertex signal processing framework: scalable processing and meaningful representations for time-series on graphs, IEEE Trans. Signal Process., Volume 66 (2018) no. 3, pp. 817-829

[62] N. Tremblay; P. Borgnat Graph wavelets for multiscale community mining, IEEE Trans. Signal Process., Volume 62 (2014) no. 20, pp. 5227-5239

[63] D.K. Hammond, Y. Gur, C.R. Johnson, Graph diffusion distance: a difference measure for weighted graphs based on the graph Laplacian exponential kernel, in: Proc. 1st IEEE Global Conference on Signal and Information Processing (GlobalSIP 2013), Austin, TX, USA, 3–5 December 2013, pp. 419–422.

[64] D. Bao; K. You; L. Lin Network distance based on Laplacian flows on graphs, 2018 (CoRR) | arXiv

[65] A. Tsitsulin, D. Mottin, P. Karras, A. Bronstein, E. Müller, NetLSD: hearing the shape of a graph, in: Proc. 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, 19–23 August 2018, pp. 2347–2356.

[66] R. Kondor, J.D. Lafferty, Diffusion kernels on graphs and other discrete input spaces, in: Proc. 19th International Conference on Machine Learning (ICML-2002), Sidney, 8–12 July 2002, pp. 315–322.

[67] N. Tremblay, G. Puy, R. Gribonval, P. Vandergheynst, Compressive spectral clustering, in: Proc. 33rd International Conference on Machine Learning (ICML 2016), New York, 19–24 June 2016, pp. 1002–1011.

[68] N. Tremblay; A. Loukas Approximating spectral clustering via sampling: a review, 2019 (CoRR) | arXiv

[69] B. Girault, P. Gonçalves, E. Fleury, A.S. Mor, Semi-supervised learning for graph to signal mapping: a graph signal Wiener filter interpretation, in: Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2014), Florence, Italy, 4–9 May 2014, pp. 1115–1119.

[70] G. Mateos; S. Segarra; A.G. Marques; A. Ribeiro Connecting the dots: identifying network structure via graph signal processing, IEEE Signal Process. Mag., Volume 36 (2019) no. 3, pp. 16-43

[71] X. Dong; D. Thanou; P. Frossard; P. Vandergheynst Learning Laplacian matrix in smooth graph signal representations, IEEE Trans. Signal Process., Volume 64 (2016) no. 23, pp. 6160-6173

[72] H.E. Egilmez; E. Pavez; A. Ortega Graph learning from data under Laplacian and structural constraints, J. Sel. Top. Signal Process., Volume 11 (2017) no. 6, pp. 825-841

[73] B. Pasdeloup; V. Gripon; G. Mercier; D. Pastor; M.G. Rabbat Characterization and inference of graph diffusion processes from observations of stationary signals, IEEE Trans. Signal Inf. Process. Netw., Volume 4 (2018) no. 3, pp. 481-496

[74] S. Segarra; A.G. Marques; G. Mateos; A. Ribeiro Network topology inference from spectral templates, IEEE Trans. Signal Inf. Process. Netw., Volume 3 (2017) no. 3, pp. 467-483

[75] D. Thanou; X. Dong; D. Kressner; P. Frossard Learning heat diffusion graphs, IEEE Trans. Signal Inf. Process. Netw., Volume 3 (2017) no. 3, pp. 484-499

[76] Y. LeCun; Y. Bengio; G.E. Hinton Deep learning, Nature, Volume 521 (2015) no. 7553, pp. 436-444

[77] M.M. Bronstein; J. Bruna; Y. LeCun; A. Szlam; P. Vandergheynst Geometric deep learning: going beyond Euclidean data, IEEE Signal Process. Mag., Volume 34 (2017) no. 4, pp. 18-42

[78] M. Bontonou; C.E.R. Kós Lassance; J.-C. Vialatte; V. Gripon A unified deep learning formalism for processing graph signals, 2019 (CoRR) | arXiv

[79] J. Zhou; G. Cui; Z. Zhang; C. Yang; Z. Liu; M. Sun Graph neural networks: a review of methods and applications, 2018 (CoRR) | arXiv

[80] F. Gama; A.G. Marques; G. Leus; A. Ribeiro Convolutional neural network architectures for signals supported on graphs, IEEE Trans. Signal Process., Volume 67 (2019) no. 4, pp. 1034-1049

[81] A. Loukas; P. Vandergheynst Spectrally approximating large graphs with smaller graphs, 2018 (arXiv, CoRR) | arXiv

[82] D.I. Shuman, P. Vandergheynst, P. Frossard, Chebyshev polynomial approximation for distributed signal processing, in: Proc. 7th IEEE International Conference on Distributed Computing in Sensor Systems (IEEE DCOSS '11), Barcelona, Spain, 27–29 June 2011, pp. 1–8.

[83] L. Le Magoarou; R. Gribonval; N. Tremblay Approximate fast graph Fourier transforms via multilayer sparse approximations, IEEE Trans. Signal Inf. Process. Netw., Volume 4 (2018) no. 2, pp. 407-420

Cité par Sources :

Commentaires - Politique