Research

My research principally focuses on graph signal processing (GSP). In few words, GSP can be seen as a generalization of classical signal processing to domains that are more complex and irregular than the time or the plane of images. The support of the information is modeled by a graph, and the observed signals are represented by vectors of real elements, each one being observed at a particular vertex of the graph. GSP provides tools allowing both spatial and spectral analysis of these signals, through a particular Fourier transform that is intimately linked with the graph. This paper (Shuman et al.) is an excellent introduction to the field.

My work principally focuses on graph inference from signals, as well as on time/frequency uncertainty and translation of signals on a graph. These works allowed to extend the notion of convolutional neural networks to irregular domains. This approach led to very promising results that I presented during my Ph.D. My current work focuses on the use of tools from the GSP framework, as well as interpretable machine learning tools, in order to classify biological data, such as tumors or brain signals. Finally, I am interested in the problem of comparing signals defined over different graphs, of possibly different dimensions.

As additional activities, I was part of the organization group for the 3rd GSP workshop that took place at EPFL Lausanne, in June 2018. Jointly with Nicolas Tremblay from Gipsa Lab (Grenoble), I also participate in the organization of a GdR ISIS meeting entitled Signal processing over graphs, with a focus on neuroscience data, that will occur on the 23rd of September, 2019.

In the lists below, you will find details on my published articles, as well as the associated resources (links, slides…):

2019

Chapters

Uncertainty principle on graphs
Vertex-frequency analysis of graph signals, Springer, 2019
Authors
  • Bastien Pasdeloup
  • Vincent Gripon
  • Réda Alami
  • Michael G. Rabbat
Abstract

Graph Signal Processing (GSP) is a mathematical framework that aims at extending classical Fourier harmonic analysis to irregular domains described using graphs. Within this framework, authors have proposed to define operators (e.g. translations, convolutions) and processes (e.g. filtering, sampling). A very important and fundamental result in classical harmonic analysis is the uncertainty principle, which states that a signal cannot be localized both in time and in frequency domains. In this chapter, we explore the uncertainty principle in the context of GSP. More precisely, we present notions of graph and spectral spreads, and show that the existence of signals that are both localized in the graph domain and in the spectrum domain depends on the graph.

Links

Conférences & séminaires

Une approche basée incertitude pour transporter un signal d’un graphe à un autre
Groupe d’Études du Traitement du Signal et des Images (GRETSI), 2019
Authors
  • Bastien Pasdeloup
  • Hermina Petric-Maretic
  • Mireille El Gheche
  • Pascal Frossard
Abstract

Dans cet article, nous proposons une nouvelle approche pour transporter un signal d’un graphe source à un graphe cible. Pour ce faire, nous créons sur le graphe cible un signal proxy ayant les mêmes propriétés de concentration, dans le graphe et dans le spectre, que le signal sur le graphe source. Le signal proxy ainsi créé pourra ensuite être, par exemple, utilisé afin de mesurer une distance entre le signal qu’il représente et un autre signal sur le graphe cible, et ainsi permettre d’identifier un même phénomène observé sur deux graphes différents.

Links

2018

Conferences & workshops

An extension of convolutional neural networks to irregular domains through graph inference and translations identification
Graph Signal Processing Workshop, EPFL, Suisse, 2018
Authors
  • Bastien Pasdeloup
  • Jean-Charles Vialatte
  • Vincent Gripon
Abstract

Convolutional neural networks (CNNs) have proven very efficient in tasks such as classification of images. In such networks, the connectivity pattern of a convolutional layer — thus the number of weights to train — is reduced compared to a dense layer. The idea is to take advantage of the locality of objects to classify in images — i.e., their localization on adjacent pixels — by linking neurons in a convolutional layer to those of the previous layer associated with close pixels only. Additionally, when considering natural scenes, images can typically be considered stationary signals. Thus, weights to train in a convolutional layer are shared among some connections of the layer, in order to detect a same object localized at various places of an image. This weight sharing is made by associating weights to train to a localized convolutional kernel that is then translated everywhere on the image. Any pixel covered by the kernel is then linked to the pixel associated with the kernel center in a resulting convolutional layer. The weight associated with this connection is the one associated with the kernel entry covering this first pixel. The goal of this presentation is to introduce a framework in which we generalize this approach to signals evolving on an irregular, unknown graph. On such topology, there is no underlying metric space, and translation of a convolutional kernel as for images is not straightforward. We propose to proceed as follows: 1) Infer a graph with well-chosen properties from a set of signals to classify; 2) Identify translations on this graph so that a signal retains its aspect when translated; 3) Use these translations to locate a convolutional kernel everywhere on the graph, thus defining the connectivity pattern of a convolutional layer; 4) Use these layers to build a CNN, and train it with the signals from which the whole process started.

Links
Classifying non-stationary time-varying signals on graphs through their deviation from a stationary behavior: preliminary results on EEG signals
Graph Signal Processing Workshop, EPFL, Suisse, 2018
Authors
  • Ali Dadras
  • Bastien Pasdeloup
Abstract

Brain Computer Interfaces systems in general aspect are systems that transform brain signals into control signals. In this study, we focus on electroencephalography (EEG) signals for brain signal acquisition, which are known to be high-dimensional, non-stationary and noisy. We consider here the classification problem of finding the Motor Imagery (MI) class — e.g., mental visualization of a move of a hand or a foot — associated with a given EEG signal. We propose to discuss a possible regularization of non-stationarity, by studying the deviation of an EEG signal from its stationary behavior on a graph that we model by the covariance matrix of the electrodes. We show here our first observations on this methodology.

Links

Unpublished

Convolutional neural networks on irregular domains based on approximate vertex-domain translations
arXiv, 2018
Authors
  • Bastien Pasdeloup
  • Vincent Gripon
  • Jean-Charles Vialatte
  • Nicolas Grelier
  • Dominique Pastor
  • Pascal Frossard
Abstract

We propose a generalization of convolutional neural networks (CNNs) to irregular domains, through the use of a translation operator on a graph structure. In regular settings such as images, convolutional layers are designed by translating a convolutional kernel over all pixels, thus enforcing translation equivariance. In the case of general graphs however, translation is not a well-defined operation, which makes shifting a convolutional kernel not straightforward. In this article, we introduce a methodology to allow the design of convolutional layers that are adapted to signals evolving on irregular topologies, even in the absence of a natural translation. Using the designed layers, we build a CNN that we train using the initial set of signals. Contrary to other approaches that aim at extending CNNs to irregular domains, we incorporate the classical settings of CNNs for 2D signals as a particular case of our approach. Designing convolutional layers in the vertex domain directly implies weight sharing, which in other approaches is generally estimated a posteriori using heuristics.

Links
A neighborhood-preserving translation operator on graphs
arXiv, 2018
Authors
  • Bastien Pasdeloup
  • Vincent Gripon
  • Jean-Charles Vialatte
  • Nicolas Grelier
  • Dominique Pastor
Abstract

In this paper, we introduce translation operators on graphs. Contrary to spectrally-defined translations in the framework of graph signal processing, our operators mimic neighborhood-preserving properties of translation operators defined in Euclidean spaces directly in the vertex domain, and therefore do not deform a signal as it is translated. We show that in the case of grid graphs built on top of a metric space, these operators exactly match underlying Euclidean translations, suggesting that they completely leverage the underlying metric. More generally, these translations are defined on any graph, and can therefore be used to process signals on those graphs. We show that identifying proposed translations is in general an NP-Complete problem. To cope with this issue, we introduce relaxed versions of these operators, and illustrate translation of signals on random graphs.

Links

2017

Ph.D.

Extending convolutional neural networks to irregular domains through graph inference
IMT Atlantique, 2017
Author Bastien Pasdeloup
Abstract

This manuscript sums up our work on extending convolutional neural networks to irregular domains through graph inference. It consists of three main chapters, each giving the details of a part of a methodology allowing the definition of such networks to process signals evolving on graphs with unknown structures. First, graph inference from data is explored, in order to provide a graph modeling the support of the signals to classify. Second, translation operators that preserve neighborhood properties of the vertices are identified on the inferred graph. Third, these translations are used to shift a convolutional kernel on the graph in order to define a convolutional neural network that is adapted to the input data. We have illustrated our methodology on a dataset of images. While not using any particular knowledge on the signals, we have been able to infer a graph that is close to a grid. Translations on this graph resemble Euclidean translations. Therefore, this has allowed us to define an adapted convolutional neural network that is very close what one would obtain when using the information that signals are images. This network, trained on the initial data, has outperformed state of the art methods by more than $ points, while using a very simple and easily improvable architecture. The method we have introduced is a generalization of convolutional neural networks. As a matter of fact, they can be seen as a particularization of our approach in the case where the graph is a grid. Our work thus opens the way to numerous perspectives, as it provides an efficient way to build networks that are adapted to the data.

Links

Journals

Characterization and inference of graph diffusion processes from observations of stationary signals
IEEE Transactions on Signal and Information Processing over Networks (TSIPN), 2017
Authors
  • Bastien Pasdeloup
  • Vincent Gripon
  • Grégoire Mercier
  • Dominique Pastor
  • Michael G. Rabbat
Abstract

Many tools from the field of graph signal processing exploit knowledge of the underlying graph’s structure (e.g., as encoded in the Laplacian matrix) to process signals on the graph. Therefore, in the case when no graph is available, graph signal processing tools cannot be used anymore. Researchers have proposed approaches to infer a graph topology from observations of signals on its vertices. Since the problem is ill-posed, these approaches make assumptions, such as smoothness of the signals on the graph, or sparsity priors. In this paper, we propose a characterization of the space of valid graphs, in the sense that they can explain stationary signals. To simplify the exposition in this paper, we focus here on the case where signals were i.i.d at some point back in time and were observed after diffusion on a graph. We show that the set of graphs verifying this assumption has a strong connection with the eigenvectors of the covariance matrix, and forms a convex set. Along with a theoretical study in which these eigenvectors are assumed to be known, we consider the practical case when the observations are noisy, and experimentally observe how fast the set of valid graphs converges to the set obtained when the exact eigenvectors are known, as the number of observations grows. To illustrate how this characterization can be used for graph recovery, we present two methods for selecting a particular point in this set under chosen criteria, namely graph simplicity and sparsity. Additionally, we introduce a measure to evaluate how much a graph is adapted to signals under a stationarity assumption. Finally, we evaluate how state-of-the-art methods relate to this framework through experiments on a dataset of temperatures.

Links

Conferences & workshops

Evaluating graph signal processing for neuroimaging through classification and dimensionality reduction
Global Conference on Signal and Information Processing (GlobalSIP), 2017
Authors
  • Mathilde Ménoret
  • Nicolas Farrugia
  • Bastien Pasdeloup
  • Vincent Gripon
Abstract

Graph Signal Processing (GSP) is a promising framework to analyze multi-dimensional neuroimaging datasets, while taking into account both the spatial and functional dependencies between brain signals. In the present work, we apply dimensionality reduction techniques based on graph representations of the brain to decode brain activity from real and simulated fMRI datasets. We introduce seven graphs obtained from a) geometric structure and/or b) functional connectivity between brain areas at rest, and compare them when performing dimension reduction for classification. We show that mixed graphs using both a) and b) offer the best performance. We also show that graph sampling methods perform better than classical dimension reduction methods including Principal Component Analysis (PCA) and Independent Component Analysis (ICA).

Links
Translation sur graphe avec préservation du voisinage
Groupe d’Études du Traitement du Signal et des Images (GRETSI), 2017
Authors
  • Nicolas Grelier
  • Bastien Pasdeloup
  • Jean-Charles Vialatte
  • Vincent Gripon
Abstract

Dans de nombreux domaines comme l’Internet des Objets ou la neuroimagerie, les signaux sont naturellement portés par des graphes. Ces derniers contiennent généralement des informations sur la similarité des valeurs de signaux observées aux différents sommets. L’un des intérêts à utiliser des graphes est qu’ils permettent de définir des opérateurs adaptés pour traiter les signaux qui y évoluent. Parmi ces opérateurs, un de prime importance pour de nombreux problèmes est la translation. Dans cet article, nous proposons de nouvelles définitions pour la translation sur graphe s’appuyant sur un nombre faible de propriétés simples. Plus précisément, nous proposons de définir ces translations comme des fonctions des sommets du graphe vers leurs voisins, préservant les relations de voisinage. Nous montrons que nos définitions, contrairement aux autres travaux sur le sujet, généralisent les translations usuelles sur des graphes grilles.

Links
Characterization and inference of graph diffusion processes from observations of stationary processes
Bellairs workshop on graph signal processing, McGill University Bellairs campus, Barbados, 2017
Authors
  • Bastien Pasdeloup
  • Vincent Gripon
  • Grégoire Mercier
  • Dominique Pastor
  • Michael G. Rabbat
Links

2016

Conferences & workshops

Neighborhood-preserving translations on graphs
Global Conference on Signal and Information Processing (GlobalSIP), 2016
Authors
  • Nicolas Grelier
  • Bastien Pasdeloup
  • Jean-Charles Vialatte
  • Vincent Gripon
Abstract

In many domains (e.g. Internet of Things, neuroimaging) signals are naturally supported on graphs. These graphs usually convey information on similarity between the values taken by the signal at the corresponding vertices. An interest of using graphs is that it allows to define ad hoc operators to perform signal processing. Among them, ones of paramount importance in many tasks are translations. In this paper we are interested in defining translations on graphs using a few simple properties. Namely we propose to define translations as functions from vertices to adjacent ones, that preserve neighborhood properties of the graph. We show that our definitions, contrary to other works on the subject, match usual translations on grid graphs.

Links
Characterizing graphs from diffused signals
  • Graph Signal Processing workshop, University of Pennsylvania, USA, 2016
  • Workshop on data driven approach to networks and languages, ENS Lyon, France, 2016
Authors
  • Bastien Pasdeloup
  • Vincent Gripon
  • Dominique Pastor
  • Grégoire Mercier
  • Michael G. Rabbat
Abstract

An important requirement in the field of signal processing on graphs is the need for a graph defining a domain on which observed signals evolve. When such a graph is available, one can compute the eigenbasis of the associated Laplacian matrix. Based on the spectral graph theory introduced by Chung, it was shown by Shuman et al. that this particular basis embeds a notion of frequency, where the smallest eigenvalues correspond to the lowest frequencies in classical Fourier analysis, and the biggest eigenvalues correspond to the highest frequencies. This important result has enabled researchers to develop numerous techniques to process signals defined on graphs. Exemples are convolution of signals or wavelets on graphs, with applications to multiscale clustering or transportation networks. However, in the case when no graph is available, none of these techniques can be applied. Therefore, an important problem is how to recover a graph from a set of signals in order to process them efficiently. In this presentation, we want to address this problem, by presenting extensions of our previous work. We consider the case when observed signals are issued from the diffusion of initially independent signals on an unknown graph structure, that we want to recover. We show that that the matrix representing this diffusion process is not unique, and that the space of admissible diffusion matrices forms a convex polytope. Then, we introduce one possible search strategy in this polytope to select a graph for which the main diagonal is null.

Links
Towards a characterization of the uncertainty curve for graphs
International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2016
Authors
  • Bastien Pasdeloup
  • Vincent Gripon
  • Grégoire Mercier
  • Dominique Pastor
Abstract

Signal processing on graphs is a recent research domain that aims at generalizing classical tools in signal processing, in order to analyze signals evolving on complex domains. Such domains are represented by graphs, for which one can compute a particular matrix, called the normalized Laplacian. It was shown that the eigenvalues of this Laplacian correspond to the frequencies of the Fourier domain in classical signal processing. Therefore, the frequency domain is not the same for every support graph. A consequence of this is that there is no non-trivial generalization of Heisenberg’s uncertainty principle, that states that a signal cannot be fully localized both in the time domain and in the frequency domain. A way to generalize this principle, introduced by Agaskar and Lu, consists in determining a curve that represents a lower bound on the compromise between precision in the graph domain and precision in the spectral domain. The aim of this paper is to propose a characterization of the signals achieving this curve, for a larger class of graphs than the one studied by Agaskar and Lu.

Links

2015

Conferences & workshops

Graph reconstruction from the observation of diffused signals
Allerton Conference on Communication, Control and Computing, 2015
Authors
  • Bastien Pasdeloup
  • Michael G. Rabbat
  • Vincent Gripon
  • Dominique Pastor
  • Grégoire Mercier
Abstract

Signal processing on graphs has received a lot of attention in the recent years. A lot of techniques have arised, inspired by classical signal processing ones, to allow studying signals on any kind of graph. A common aspect of these technique is that they require a graph correctly modeling the studied support to explain the signals that are observed on it. However, in many cases, such a graph is unavailable or has no real physical existence. An example of this latter case is a set of sensors randomly thrown in a field which obviously observe related information. To study such signals, there is no intuitive choice for a support graph. In this document, we address the problem of inferring a graph structure from the observation of signals, under the assumption that they were issued of the diffusion of initially i.i.d. signals. To validate our approach, we design an experimental protocol, in which we diffuse signals on a known graph. Then, we forget the graph, and show that we are able to retrieve it very precisely from the only knowledge of the diffused signals.

Links
Toward an uncertainty principle for weighted graphs
European Signal Processing Conference (EUSIPCO), 2015
Authors
  • Bastien Pasdeloup
  • Réda Alami
  • Vincent Gripon
  • Michael G. Rabbat
Abstract

The uncertainty principle states that a signal cannot be localized both in time and frequency. With the aim of extending this result to signals on graphs, Agaskar & Lu introduce notions of graph and spectral spreads. They show that a graph uncertainty principle holds for some families of unweighted graphs. This principle states that a signal cannot be simultaneously localized both in graph and spectral domains. In this paper, we aim to extend their work to weighted graphs. We show that a naive extension of their definitions leads to inconsistent results such as discontinuity of the graph spread when regarded as a function of the graph structure. To circumvent this problem, we propose another definition of graph spread that relies on an inverse similarity matrix. We also discuss the choice of the distance function that appears in this definition. Finally, we compute and plot uncertainty curves for families of weighted graphs.

Links
Vers une caractérisation de la courbe d’incertitude pour des graphes portant des signaux
Groupe d’Études du Traitement du Signal et des Images (GRETSI), 2015
Authors
  • Bastien Pasdeloup
  • Vincent Gripon
  • Grégoire Mercier
  • Dominique Pastor
Abstract

Le traitement de signal sur graphes est un domaine récent visant à généraliser les outils classiques du traitement de signal, afin d’analyser des signaux évoluant sur des domaines complexes. Ces domaines sont représentés par des graphes pour lesquels on peut calculer une matrice appelée Laplacien normalisé. Il a été montré que les valeurs propres de ce Laplacien correspondent aux fréquences du domaine de Fourier en traitement de signal classique. Ainsi, le domaine fréquentiel n’est pas identique pour tout graphe support des signaux. Une conséquence est qu’il n’y a pas de généralisation non triviale du principe d’incertitude d’Heisenberg, indiquant qu’un signal ne peut être à la fois localisé dans le domaine temporel et dans le domaine fréquentiel. Une manière de généraliser ce principe, introduite par Agaskar & Lu, consiste à déterminer une courbe servant de borne inférieure au compromis entre précision dans le domaine du graphe et précision dans le domaine spectral. L’objectif de ce papier est de proposer une caractérisation des signaux atteignant cette courbe, pour une classe de graphes plus générique que celle étudiée par Agaskar & Lu.

Links