COmpression de REseaux et de GRAPHes pour une Informatique Efficace – COREGRAPHIE

Durant le projet, nous avons exploré les approches suivantes :

- Décomposition de graphes dans le but de trouver des structures compressibles. Ces structures sont souvent des sous graphes denses, comme les cliques et leurs variantes, ou des structures particulières, comme les modules qui sont des ensembles de nœuds qui partagent le même voisinage.

- Reconnaissance des classes de graphes en utilisant les parcours de graphes. En effet, de par leurs propriétés, certaines classes de graphes sont plus compressibles que d'autres.

- Utilisation de langages de programmation innovants (RUST) pour accélérer la compression de grands graphes (passage à l'échelle) comme le graphe de Software Héritage

- Filtrage d'arêtes. C'est une compression avec perte qui consiste à enlever des arêtes du graphe tout en gardant certaines propriétés de celui-ci.

- Embedding. Cette compression consiste à représenter le graphe sous forme vectorielle afin d'appliquer des algorithmes de machine learning.

- Echantillonnage, qui consiste à sélectionner des nœuds, des arêtes ou des sous-graphes qui représentent le mieux le graphe initial. Nous avons appliqué l'échantillonnage pour améliorer l'entrainement des "Graph Neural Networks" (GNNs).

- Interprétation des backbones. Nous avons travaillé sur les deux questions suivantes : Quelle est la signification d'un résumé de graphe ? Est ce que les LLMs peuvent décrire un backbone ?

- Sur la décomposition de graphes dans le but de trouver des structures compressibles, nos résultats sont :

* Un nouvel algorithme de détection de bicliques sur les graphes bi-partis

* Une nouvelle approche pour la détection de quasi-cliques pour la compression de graphes.

* Un algorithme de détection de motifs compressibles tenant compte des recouvrements entre structures.

- Sur la reconnaissance des classes de graphes en utilisant les parcours de graphes, , nos résultats sont :

* Pour deux classes de graphes où LexBFS constituait le meilleur algorithme de reconnaissance connu, nous montrons que trier les listes d’adjacence puis effectuer respectivement un parcours en largeur (BFS) et un parcours en profondeur (DFS) suffit.

* Reconnaissance de classes en utilisant les motifs d'un ordre total sur les graphes.

- Nous avons utilisé des langages de programmation innovants comme RUST pour accélérer la compression de grands graphes comme le graphe de Software Héritage. Ce travail a donné lieu à plusieurs logiciels de compression rapide de graphes disponibles via le site du projet.

- Sur le filtrage d'arêtes, qui est une compression avec perte mais qui permet de garder certaines propriétés du graphe initial, nos résultats sont :

* Une nouvelle approche de filtrage d'arêtes en utilisant le voisinage.

* Un état de l'art sur les méthodes de filtrage d'arêtes, avec comparaison et analyse sur plusieurs types de graphes.

* Construction d'une bibliothèque comprenant les méthodes existantes.

* Une nouvelle approche de construction de backbone basée sur la prédiction de liens.

- Proposition de plusieurs solutions d'embedding de graphes pour les applications d'apprentissage. Les embeddings sont des représentations vectorielles des nœuds, d’arêtes ou du graphe entier.

- Une nouvelle approche d'échantillonnage de sous-graphe avec application dans les "Graph Neural Networks" (GNNs).

- Une approche basée sur les grands modèles de langages (LLM) pour générer des interprétations des backbones.

- Prise en compte des graphes dynamiques : La gestion de graphes dynamiques constitue un verrou important. Les techniques actuelles peinent à s’adapter aux modifications fréquentes de la structure (ajouts/suppressions de nœuds ou d’arêtes, variations de poids), ce qui compromet la pertinence et la stabilité des représentations compressées dans un cadre dynamique. Le développement de méthodes incrémentales reste un défi majeur

- Outils d’évaluation d’une « bonne » compression à perte

Un axe de travail important concerne la conception et la formalisation d’outils d’évaluation adaptés pour qualifier la qualité d’une compression à perte. Au-delà des critères classiques de taux de compression, il s’agit de définir des métriques capables de rendre compte de la préservation des propriétés essentielles des graphes.

- Exploration de nouveaux cas d’usage en partenariat avec des industriels

Un autre axe de développement concerne l’identification et l’exploration de cas d’usage concrets, notamment en biologie, en chimie organique ou dans d’autres domaines industriels manipulant des graphes de grande taille. Ces collaborations appliquées offriraient un terrain d’expérimentation privilégié pour tester les méthodes de compression et de résumé dans des contextes réels, où les enjeux portent à la fois sur la performance algorithmique et sur l’interprétabilité des résultats.

- Utilisation de l’apprentissage par renforcement pour la construction de résumés ou de backbones, ce qui permet d'automatiser le processus de sélection des informations pertinentes dans un graphe. Cette approche permettrait d’obtenir des méthodes adaptatives, capables de s’ajuster aux caractéristiques propres d’un graphe donné, tout en offrant des garanties sur la qualité des résumés obtenus.

Les graphes sont omniprésents. Également appelés réseaux, les graphes servent à modéliser de nombreux problèmes et données du monde réel : réseaux sociaux, réseaux routiers, assemblage de fragments de génomes, images et objets 3D (pour la reconnaissance et la classification de formes), etc. De nos jours, bon nombre de ces applications, sont confrontées à un problème majeur : le volume de données augmente à tel point que même les solutions polynomiales ne suffisent plus. Les plateformes distribuées ou parallèles, comme MapReduce, qui sont des approches efficaces pour traiter les données massives, ne sont pas nécessairement adaptées aux traitement de grands graphes, principalement à cause de la structure inhérente des données de type graphe et à la nature itérative de leurs algorithmes.

Dans ce projet, nous plaçons la compression au cœur de la problématique du traitement des grands graphes de données. Notre objectif est de définir un cadre de réduction de graphes qui permet de construire des représentations plus simples et plus petites des graphes, i.e., des résumés, que l’on peut utiliser à la place des graphes initiaux. Pour cela, nous proposons de développer des algorithmes qui permettent d’effectuer de telles compressions, et de les affiner en fonction de la qualité des résumés obtenus, ainsi que des traitements qu’ils permettent d’entreprendre.
L’avantage d’une telle approche est de traiter les données massives de type graphe en temps linéaire ou quasi-linéaire. Notre méthodologie se base sur la recherche de régularité dans les graphes afin de les réduire et de les analyser.

Ainsi, le défi que nous abordons est de définir, prototyper et tester une telle approche pour proposer un outil efficace, évolutif et opérationnel pour l’analyse de graphes qui peut être étendu à toutes les données structurées de type graphe. Nous appliquerons principalement nos travaux à Software Heritage, la plus grande archive de logiciels, avec code source et historique de développement, fondée par l’INRIA. Le modèle de données de cette archive est un graphe en plein expansion consistant de 15 milliards de nœuds et 200 milliards de liens.

Les nouveaux outils et algorithmes produits par le projet, dont le code source sera ouvert, créeront une base pour le développement de nouveaux types d’algorithmes d’analyse de données et de recherche d’informations pour les données de type graphe et trouveront des applications dans divers domaines et disciplines utilisant des graphes ou des réseaux.