[COREGRAPHIE - COmpression de REseaux et de GRAPHes pour une Informatique Efficace]

Coordinatrice : Hamida Seba (UMR 5205 - LABORATOIRE D’INFORMATIQUE EN IMAGE ET SYSTEMES D’INFORMATION)

Partenaire : Julien Baste Université de Lille CRIStAL

Équipe : ORKAD du Groupe Thématique : OPTIMA.

Dates : 03/2021 - 03/2025

Résumé :

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 traitements 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.

Abstract :

Graphs are ubiquitous. Also called networks, graphs are used to model many real-world problems and data : from social networks, to road networks, to genome fragment assembly, to images and 3D objects (for pattern recognition and classification), etc. Nowadays, many of these applications face a major problem : the volume of data increases to such an extent that even polynomial solutions are no longer sufficient. Parallel and distributed frameworks, such as MapReduce, which are effective approaches to deal with big data, are not necessarily suitable for massive graph computations, mainly because of the structure of graph data and the iterative nature of their algorithms.

In this project, we put compression at the core of massive graph data processing. We aim to define a graph reduction toolbox that allows to compute simpler and smaller representations of graphs, i.e., summaries, that can be used instead of the initial graphs. For this, we propose to develop algorithms that make it possible to perform such compressions, and to refine them according to the quality of the obtained summaries as well as the operations they allow to undertake.The advantage of such approach is to process massive graph data in linear or quasi-linear time. Our methodology relies mainly on searching for regularities into graphs in order to summarize and analyze them.

Thus, the challenge we address is to define, prototype, and test such a graph engine so that to ensure an operational, efficient and scalable graph analysis tool that can be extended to all graph structured data. Our main use case is Software Heritage, the largest archive of software source code together with its development history, founded by INRIA. The archive data model is a fast growing graph consisting of 15 billion nodes and 200 billion edges.

The new tools and algorithms produced by the project, that will be available in open source, will create basis for developing new types of data analysis and information retrieval algorithms for massive graph structured data and will find applications in various domains and disciplines relying on graphs or networks.