Vous êtes ici : GIPSA-lab > Animation > Soutenances

Wilson’s Algorithm for Randomized Linear Algebra

Soutenance de la thèse de Yusuf Yigit PILAVCI le 15/11/2022 à 14:00:00

Lieu :Maison Jean Kuntzmann

Ecole Doctorale :Electronique, electrotechnique, automatique, traitement du signal (EEATS)
Structure de rattachement :
Directeur de thèse : Pierre-Olivier AMBLARD


Financement(s) :
-Contrat doctoral


Date d'entrée en thèse: 01/10/2019
Date de soutenance: 15/11/2022

Composition du jury :AMBLARD, Pierre-Olivier, Directeur de Recherce, CNRS, Grenoble
VAITER, Samuel, Charge de Recherce, CNRS, Nice
DESOLNEUX, Agnès, Directeur de Recherce, CNRS, Paris
MICHEL, Olivier, Professeur des Universites, Grenoble INP
GAUDILLIERE, Alexandre, Charge de Recherce, CNRS, Marseille
COURTY, Nicolas, Charge de Recherce, Universite Bretagne Sud

Résumé:An extensive range of problems in machine learning deals with data structured over networks/graphs. The examples vary from drug discovery to traffic forecasting, social network analysis to recommender systems, or epidemic analysis to natural language processing. Along with the exploding size and number of data, a big chunk of the proposed algorithms has focused on analyzing, representing and leveraging the network structures in the last decades. In many of them, the graph Laplacian is the central object. They are notable matrix representations of graphs that relate to various aspects. For example, by analyzing the Laplacian algebraically, one can measure the connectivity, count the number of spanning trees or generate a visualization of a graph. Further examples can be found in the problems of node clustering, graph sparsification, signal processing on graphs and many more. However, the algebraic analysis of Laplacian can be frustratingly time-consuming if the graph consists of a large number of nodes. Despite many numerical tools specialized for the graph Laplacian, in certain cases, the computational time remains one of the main issues.
Random spanning forests (RSFs), a random process on graphs, is a probabilistic tool for analyzing graphs with strong links with the Laplacian. In a nutshell, RSFs provide \emph{meaningful} random sketches (spanning forests) of the graph to analyze some properties of interest. These sketches are cheap to obtain by a variant of Wilson’s algorithm. Moreover, by only looking at a few of them, one can deduce significant statistical and/or algebraic information on the overall graph. The existing applications of RSFs, including graph wavelet analysis, semi-supervised learning on graphs or centrality analysis, show that RSFs provide useful information while binding diverse aspects of graphs.
In this manuscript, we present ways of leveraging the rich connections between RSFs and the graph Laplacian to speed up the algebraic analysis. In doing so, we propose randomized algorithms to approximate several quantities of interest, such as the regularized inverse of the Laplacian or effective resistances. Interestingly, these quantities are required in a wide range of applications on graphs, including graph signal filtering, hyper-parameter tuning, graph-based optimization and sparsification. We illustrate these methods on real-life networks and compare them with state-of-the-art methods.

GIPSA-lab, 11 rue des Mathématiques, Grenoble Campus BP46, F-38402 SAINT MARTIN D'HERES CEDEX - 33 (0)4 76 82 71 31