Description du sujet de thèse

Graph coarsening [1], or graph reduction, is a complex and difficult problem that consists in, given a large graph, producing a smaller graph that “summarizes” the initial one. The objective can be to save computing time and memory, but also to extract some interesting properties of the original graph through its reduction. An ubiquitous tool in many areas of scientific computing, it has been postulated that graph coarsening could bear many interesting links with the recent domain of graph Machine Learning, which has known an exponential growth in terms of scope, applications and literature in the last few years.
In particular, just as multi-scale Convolutional Neural Networks involve “pooling” steps, researchers have tried to integrate graph coarsening methods in Graph Neural Networks (GNN), but the results were generally not conclusive, mainly due to the complexity and unstability of the current approaches. Hence the need for better, more stable approaches.
In this thesis, we will study more data-driven approaches to perform graph coarsening through the definition of well-behaved cost functions, both supervised or unsupervised, which could be more stable that approaches involving randomness. We will examine their integration in GNNs such as Graph UNets [2].
There are many methods to perform graph coarsening, but most seek to preserve some properties of the original graph, such as the spectrum of its Laplacian [4, 3]. Depending on the candidate, we will examine such guarantees, and particularly their limitations. We will study, both empirically and theoretically, the difference between random-based and learning-based approaches for graph coarsening.

Contexte de travail

The candidate will be attached to IRISA's SIROCCO team.

About the laboratory
=============
www.irisa.fr
IRISA is one of France's largest research laboratories (over 850 people) in the field of computer science and information technology. Structured into seven scientific departments, IRISA is a laboratory of excellence whose scientific priorities are bioinformatics, systems security, new software architectures, virtual reality, Big Data analysis and artificial intelligence. With its sights set on the future of information technologies and its international outlook, IRISA is at the heart of society's digital transition and innovation in the fields of cybersecurity, health, environment and ecology, transport, robotics, energy, culture and artificial intelligence.

Presentation of CNRS as an employer: https://www.cnrs.fr/fr/le-cnrs
IRISA as laboratory of assignment: https://www.irisa.fr/umr-6074

Le poste se situe dans un secteur relevant de la protection du potentiel scientifique et technique (PPST), et nécessite donc, conformément à la réglementation, que votre arrivée soit autorisée par l'autorité compétente du MESR.

Contraintes et risques

The position is located in an area covered by the protection of scientific and technical potential (PPST) and requires, in accordance with regulations, that your arrival be authorized by the competent MESR authority.