CE48 - Fondements du numérique: informatique, automatique, traitement du signal

Processus ponctuels déterminantaux sur graphes pour l'algèbre linéaire numérique randomisée – GRANOLA

Résumé de soumission

Les graphes sont des outils essentiels à l'analyse des réseaux, qu'ils soient issus de données de neurosciences, de sociologie, de biologie moléculaire, de chimie, etc. Une pierre angulaire de l'étude de ces graphes est la matrice laplacienne L (qui encode leur structure) dont les propriétés algébriques permettent de comprendre de nombreux aspects du réseau sous-jacent: la vitesse de diffusion d'une information ou d'une maladie au sein du réseau, la vulnérabilité du réseau aux attaques ciblées ou aléatoires, la structure du réseau en modules plus ou moins indépendents sont autant d'exemples de caractéristiques du réseau capturées par la matrice laplacienne.

Malheureusement, d'un point de vue du coût de calcul, des opérations classiques sur L (comme la SVD ou la pseudo-inversion) nécessitent dans le pire des cas un nombre d'opérations élémentaires cubique en la taille du graphe, rendant ce genre de calculs trop coûteux quand la taille des graphes devient grande. Parmi les stratégies de l'état de l'art contournant ce problème, la classe de méthodes stochastiques appelée RandNLA (pour Randomized Numerical Linear Algebra) suscite un intérêt grandissant. L'idée générale est d'obtenir une approximation de la solution en suivant le schéma suivant: d'abord échantillonner et/ou projeter aléatoirement la matrice L, résoudre le problème d'algèbre dans cette dimension réduite, avant d'extrapoler le résultat obtenu dans la dimension originale. Outre la simplicité de l'approche, ces méthodes ont connu un grand succès car, sous certaines conditions, l'erreur d'approximation induite par l'échantillonnage et/ou la projection est théoriquement très bien contrôlée. En pratique, en autorisant une petite erreur d'approximation sur le résultat obtenu, les méthodes de type RandNLA permettent de réduire le temps de calcul de plusieurs ordres de grandeur dans certains cas.

Un des paradigmes sur lequel repose ces méthodes est le caractère iid (indépendent et identiquement distribué) de l'étape d'échantillonnage et/ou de projection, qui permet de tirer profit de la puissance des théorèmes usuels de concentration de la mesure. Néanmoins, il est clair que l'échantillonnage iid n'empêche pas la redondance au sein des échantillons et n'est donc pas la méthode d'échantillonnage la plus efficace. Idéalement, une certaine forme de répulsion devrait être envisagée pour obtenir les échantillons les plus représentatifs possibles de la matrice L. La classe des processus ponctuels déterminentaux (dont l'acronyme anglais est DPP) répond à cette exigence de répulsion tout en restant théoriquement analysable, ce qui la rend particulièrement attrayante pour améliorer les performances actuelles des méthodes RandNLA.

Les obstacles restent néanmoins nombreux: le plus important est le coût d'échantillonnage d'un DPP qui est nécessairement plus cher que l'échantillonnage iid. Dans le cas général, échantillonner un DPP demande un coût cubique en la taille des données. Heureusement, certains DPP sont bien plus efficaces à échantillonner. C'est le cas de certains DPP sur graphes comme les forêts couvrantes uniformes qui échantillonnent des liens et des noeuds du graphe en un temps quasi-linéaire en le nombre de liens du graphe. Ce type d'accélération est régulièrement observée dès lors qu'un problème d'algèbre linéaire peut-être posé via un graphe: un exemple classique est le problème d'inversion Mx=b où la solution générique demande au pire des cas un budget cubique en la taille de M, mais où une bonne aproximation peut être obtenue en temps quasi-linéaire en le nombre d'entrées non-nulles de M si M est la matrice laplacienne d'un graphe.

L'objectif du projet GRANOLA est de combiner la répulsion des processus ponctuels déterminantaux et l'efficacité algorithmique des forêts aléatoires sur graphes pour créer de nouveaux algorithmes stochastiques de type RandNLA dans le cas particulier (mais important) de l'estimation de caractéristiques basées sur L.

Coordination du projet

Nicolas Tremblay (Grenoble Images Parole Signal Automatique)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

GIPSA-lab Grenoble Images Parole Signal Automatique

Aide de l'ANR 199 442 euros
Début et durée du projet scientifique : décembre 2021 - 36 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter