I am a CNRS researcher at the interface of signal processing and complex networks currently with the CICS (Communication and Information in Complex Sytems) team in the GIPSA laboratory, in Grenoble, French Alps.

# Internship positions

Internship positions are available on graph signal processing, community detection, machine learning. Please inquire by sending an e-mail at firstname.lastname [at] gipsa-lab.grenoble-inp.fr !

# Current research interests

## Determinantal Point Processes for Graph Sampling

*efficiently sampling bandlimited signals using repulsive point processes such as Determinantal Point Processes.*

In an effort to improve the existing sampling theorems for graph signals, in terms of number of necessary nodes to sample, robustness to noise of the recovery, and/or complexity of the sampling algorithms; we propose to take a close look at determinantal processes. Building upon recent results linking determinantal processes and random rooted spanning forests on graphs, we investigate how particular random walks on graphs may end up revealing optimal sampling sets. Preliminary results using loop-erased random walks may be found here. More to come!
## A Fast Graph Fourier Transform

*does the Graph Fourier Transform admit a O(NlogN) algorithm like the classical FFT?*

The Fast Fourier Transform (FFT) is an algorithm of paramount importance in signal processing as it allows to apply the Fourier transform in O(NlogN)
instead of O(N^2) arithmetic operations. Today, in graph signal processing, there are two computational bottlenecks regarding the graph Fourier transform: first, one needs to diagonalize the Laplacian matrix (or adjacency matrix, depending on what model you prefer) which costs O(N^3) operations; then, given a signal, one needs to multiply the obtained eigenvector matrix with the signal costing another O(N^2) operations.
To circumvent such issues,
we propose a method to obtain approximate
graph Fourier transforms that can be applied rapidly and stored
efficiently. It is based on a greedy approximate diagonalization
of the graph Laplacian matrix, carried out using a modified
version of the famous Jacobi eigenvalues algorithm.
[PDF] [The Faust Toolbox]
## Compressive Spectral Clustering

*combining graph signal processing
and compressed sensing to accelerate spectral clustering*

We propose a *compressive* spectral clustering method that accelerates the
classical spectral clustering algorithm by bypassing the exact partial diagonalisation
of the Laplacian of the similarity graph and the k-means step at high dimension. It can
be summarised as follows:

1) generate a feature vector for each node by filtering
O(log(k)) random Gaussian signals on G;

2) sample O(k log(k)) nodes from the full set of nodes;

3) cluster the reduced set of nodes;

4) interpolate the cluster indicator vectors back to the
complete graph.

We prove that our method, with a gain in
computation time that can reach several orders of
magnitude, is in fact an approximation of spectral
clustering, for which we are able to control
the error.
Read more
## Random sampling of bandlimited signals on graphs

How can one sample a k-bandlimited signal on a graph --i.e. a "smooth" signal whose
k first graph Fourier coefficients are non-null-- while still being able to recover
it perfectly?

The goals here are both to reduce as much as possible the number of samples, while
garanteeing robust reconstruction with respect to noise.
We propose a random sampling strategy that meets these goals while sampling only O(klog(k)) nodes.
Read more
# Past research interests

## Subgraph-based Filterbanks for Graph Signals

In order to design a critically-sampled compact-support
biorthogonal transform for graph signals, we propose
a design based on a partition of the graph in connected
subgraphs. Coarsening is achieved by defining one “supernode”
for each subgraph and the edges for this coarsened graph
derives from the connectivity between the subgraphs. Unlike the
“one every two nodes” downsampling on bipartite graphs, this
coarsening operation does not have an exact formulation in the
graph Fourier domain. Instead, we rely on the local Fourier
bases of each subgraph to define filtering operations. Using scalable algorithms to partiton nodes in well connected subgraphs (or communities), our proposition enables filterbank operations (compression, denoising...) in linear time.
[PDF] [Code]
## Multiscale community mining in networks

Graph wavelets are recently developed tools that generalize the classical concept of wavelet analysis for signals defined on graphs. We take advantage of this precise notion of scale to develop multiscale community mining tools for networks.
Read more
## Graph Empirical Mode Decomposition

Adaptation of the Empirical Mode Decomposition (EMD)
algorithm for signals defined on graphs.Read more
## Bootstrapping in networks

In order to obtain statistics on measured observables in complex networks that are usually measured only once and hardly reproducible, one needs to adapt classical bootstrapping techniques to networks. Read more