Nicolas Tremblay's GSDet

GSDet : Graph Sampling with
Determinantal Point Processes

The project

Abstract. Graphs are a central modelling tool for network-structured data. Depending on the application, the nodes of a graph may represent people in social networks, brain regions in neuronal networks. . . basically any system made of interconnected sub-systems. Data on a graph, called graph signals, such as individual hobbies, or blood flow of brain regions, may be represented by a scalar per node. Graph sampling consists in measuring an a priori smooth graph signal on a reduced set of nodes carefully chosen to enable stable reconstruction. In previous work, we prooved that this problem is closely linked to leverage scores, a concept of paramount importance in dimension reduction endeavours such as low-rank approximation of large matrices. In an effort to improve the existing theorems 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 will investigate how particular random walks on graphs may end up revealing optimal sampling sets. The outcome of this investigation could have a strong impact not only in graph signal processing, but more generally in machine learning and data mining where reducing the dimension of the data is often a necessary step.


Support. This project is partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025-01) funded by the French program Investissement d’avenir.


Timeline. This project was ruuning during the years 2017 and 2018. It is now closed.

Associated activity

October 2018. Visit to Marseille for discussion with Alexandre Gaudillère.

May 2018. Visit of Alexandre Gaudillère from the Institut de Mathématiques de Marseille to Grenoble.

March/April 2018. Submission of two journal papers on DPP sampling.

September 2017. Presentation of the paper "Échantillonnage de signaux sur graphes via des processus déterminantaux" at GRETSI, Juan-les-Pins, France.

August 2017. Presentation of the paper "Graph Sampling with Determinantal Processes" at EUSIPCO, Kos, Greece.

May 2017. Visit at the Institut de Mathématiques de Marseille to discuss random rooted forests and determinantal point processes. A seminar was given: "Filtering and Sampling Graph Signals, and its Application to Compressive Spectral Clustering".


Associated publications

[4] Nicolas Tremblay, Simon Barthelmé, Pierre-Olivier Amblard. Determinantal Point Processes for Coresets. In Journal of Machine Learning Research, Vol. 20, No. 168, pp. 1-70, 2019. [PDF] [Code]

[3] Simon Barthelmé, Pierre-Olivier Amblard, Nicolas Tremblay. Asymptotic Equivalence of Fixed-size and Varying-size Determinantal Point Processes. In Bernoulli, Vol. 25, No. 4B, pp. 3555-3589, 2019. [PDF] [Code]

[2] Nicolas Tremblay, Simon Barthelmé, Pierre-Olivier Amblard. Échantillonnage de signaux sur graphes via des processus déterminantaux. GRTESI, September 2017. [PDF]

[1] Nicolas Tremblay, Pierre-Olivier Amblard, Simon Barthelmé. Graph Sampling with Determinantal Processes. EUSIPCO, August 2017. [PDF]


Last update of this page. 7th of May 2020.