Graph Signal Processing
In the context of a new EPFL/Inria lab, the PANAMA team at Inria Rennes and the LTS lab at EPFL investigate the emerging field of graph signal processing.
Nowadays, more and more data natively “live” on the vertices of a graph: brain activity supported by neurons in networks, traffic on transport and energy networks, data from users of social media, complex 3D surfaces describing real objects… Although graphs have been extensively studied in mathematics and computer science, a “signal processing” viewpoint on these objects remains largely to be invented. As such, “signal processing on graphs” (SPG) is an emerging topic, that has already lead to pioneering theoretical and practical work to formalize foundational definitions and tools. This has opened the path to many exciting future research, calling to revisit most of the usual signal processing tasks (filtering, denoising, compression, etc.).
Among signal processing tools, transforms naturally play a key role in modelling data. Thanks to spectral graph theory, a Fourier transform can be defined on graphs from the eigen decomposition of the graph’s Laplacian operator. Various wavelet transforms can also be defined on graphs, and the teams involved in this proposal have pioneered the design of wavelet transforms on graphs using spectral graph theory. Fourier or wavelet transforms on graphs allow the extension of notions such as the smoothness of a signal. More generally they open the door to using the extensive toolset of sparse signal models that, in recent years, have achieved tremendous success in solving large classes of inverse problems with guaranteed performances and efficient algorithms based on convex optimization. Transposed to general graph data, this leads to applications as diverse as community detection, recommender systems, or matrix completion on graphs.
The baseline definition of transforms on graphs does not a priori lead to a \textit{fast} implementation of the transform, which would counterpart nicely the usual Fast Fourier Transform (FFT) on time-series or images for instance. Designing fast transforms on graphs that mimic the properties of usual fast transforms is desirable for it has the potential to substantially speed up virtually any application of graph transforms, and to scale up these techniques to huge graphs which are needed to address industrial needs for systems on the present and future internet.
Spectral graph wavelets developed by LTS2 in collaboration with PANAMA are endowed with fast implementations using Chebishev polynomials, but more efficient Lanczos methods can be envisioned. However the size and geometry of the underlying graph can substantially impact the computational efficiency of the resulting transform and these effects are still largely unknown. Moreover all current algorithms rely on centralised computations, where the ability to have a distributed implementation is key for big data.
In complement, techniques have recently been developed by the PANAMA team for fast approximate implementations of given transforms, using multi-layer sparse matrix factorization. The classical Fourier transform and its usual FFT implementation easily fall into this framework, as well as the Hadamard transform and other fast transforms, and this opens new perspective to design an (approximate) FFT on graphs.
The project will explore the theory and algorithms of fast transforms on graphs and dimension reduction, focusing on applications to big data problems. Leveraging the know-how of the LTS2 and PANAMA team, we will investigate the potential of message passing and nonconvex optimization techniques to design fast spectral graph wavelets and learned fast transforms. As fundamental tradeoffs may exist depending on the underlying graphs structure, we will conduct a mathematical analysis of the graph characteristics compatible with the existence of fast transforms with certain properties (e.g., spectral and/or spatial localization). Beyond theoretical results, the learned transforms will be benchmarked against existing methods on targeted learning and denoting problem.
Publications
- D. Shuman, S. Narang, P. Frossard, A. Ortega and P. Vandergheynst, The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains, IEEE Signal Processing Magazine, 30(8):83–98, May 2013
- L. Le Magoarou and R. Gribonval, Flexible Multi-layer Sparse Approximations of Matrices and Applications, preprint, https://hal.inria.fr/hal-01167948
- N. Perraudin, J. Paratte, D. Shuman, V. Kalofolias, P. Vandergheynst and D. Hammond, GSPBOX: A toolbox for signal processing on graphs, ArXiv e-prints, August 2014.
- V. Kalofolias, X. Bresson, M. Bronstein and P. Vandergheynst, Matrix Completion on Graphs, Neural Information Processing Systems 2014, Workshop “Out of the Box: Robustness in High Dimension”, Montreal, Canada, 2014
Recent News
Nicolas Tremblay joined the projet this September as a post-doc.
Team Members
Rémi Gribonval (DR, Inria Rennes)
Luc Le Magoarou (Ph.D. student, Inria Rennes)
Nathanaël Perraudin (Ph.D. student, EPFL)
Gilles Puy (postdoc, Inria Rennes)
Nicolas Tremblay (postdoc, EPFL/Inria lab, Inria Rennes)
Pierre Vandergheynst (Professor, EPFL)
