Aller au contenu
Accueil » ACTION TRANSVERSE GRAPHES » Ecole d’été Graphes – GRAPHADON

Ecole d’été Graphes – GRAPHADON

Qu’est-ce qu’un Graphe ? Les modélisations qui utilisent les graphes sont très nombreuses dans les travaux recensés au sein de la fédération Normastic, mais force est de constater que tous les chercheurs ne mettent pas forcément les mêmes définitions dernière ce terme, et les traitements qui leurs sont appliqués sont eux aussi potentiellement très divers. L’objectif de cette école d’été est de familiariser ses participants à un certain nombre de vision des graphes parmi lesquelles : Graphes et Algorithmes, Graphes sémantiques, Graphes dynamiques, Traitement du signal sur graphes, Graphes et apprentissage machine.

L’événement aura lieu du lundi 24 juin 2024 au vendredi 28 juin 2024 à l’INSA Rouen Normandie

Lien vers le flyer

Lundi 24 Juin: Graphes et algorithmique
Horaire Intervenant Intitulé & Résumé
10h-12h00 Paul dorbec Quand presque tous les problèmes sont durs…

où l’on rappelle la définition de quelques problèmes de graphes, on les manipule, on découvre les réductions de complexité et les gadgets mis en place. L’objectif est de montrer cependant que les instances dures sont souvent assez spécifiques.

14h-15h30 Aline Parreau … mais en même temps souvent faciles

où l’on verra des algorithmes efficaces, d’approximation, de programmation dynamique utilisant des propriétés de graphes…

Pause déjeuner
15h45-17h30 Arnaud De Mesmay Graphes planaires ou presque: la topologie au secours des algorithmes

De nombreux graphes que l’on rencontre en pratique ont une structure particulière. Par exemple, les réseaux routiers n’ont pas ou peu de croisements lorsqu’on les dessine dans le plan. Nous verrons comment ce genre de propriétés, de nature topologique ou géométrique, interagit avec la combinatoire des graphes, et permet souvent de développer des algorithmes plus efficaces que dans le cas général.

Mardi 25 juin : Graphes Sémantiques
Horaire Intervenant Intitulé & Résumé
9h-10h15 Géraldine Del Mondo Introduction à la modélisation par graphes – cours-TD

L’objectif de cette séance est de présenter la modélisation de phénomènes réels en utilisant les graphes. Une introduction sur les principes généraux en lien avec ce type de modélisation permettra de mettre en avant les aspects sémantiques que l’on cherche à conserver afin d’exprimer au mieux la réalité dans le modèle. Toute la difficulté réside dans le compromis entre un modèle trop complexe pour les traitements automatiques mais précis et proche du phénomène initial, et un modèle trop haut niveau qui ne capturerait pas suffisamment de détails pour répondre aux problématiques sous-jacentes. Dans ce cadre, des approches permettant des vues du modèle à différents niveaux d’abstraction peuvent potentiellement répondre à cette question.

Un deuxième volet présentera quelques exemples de travaux de modèles basés sur les graphes, ce qui permettra de montrer que suivant les phénomènes modélisés, les graphes peuvent être de structures et de caractéristiques très différentes (e.g. graphe simple/hypergraphe, statique/dynamique, spatialisés).

Enfin dans un troisième volet les participants seront invités à réfléchir collectivement sur un exemple de phénomène et à « produire » un modèle de graphe correspondant.

10h30-12h Aurélie Leborgne Généricité des modèles de graphes sémantiques, application aux domaines médical et environnemental — conférence

Cette présentation se concentre sur l’utilisation de modèles de graphes sémantiques, en particulier les modèles de graphes spatio-temporels, dans deux domaines différents : l’IRM fonctionnel (domaine médical) et l’occupation des sols (domaine environnemental). Nous aborderons également l’utilisation de ce type de modèle pour la fouille de données et, plus précisément, la recherche de motifs fréquents.

Les graphes sémantiques sont une méthode de représentation des données qui permettent de visualiser les relations entre les entités. Les modèles de graphes spatio-temporels sont une extension de cette méthode, qui permettent de représenter les relations spatiales et temporelles entre les entités. Cela permet une modélisation plus fine et plus complète des données dans des domaines où la position et le temps sont des facteurs clés.

Deux exemples d’utilisation de modèles de graphes spatio-temporels seront présentés. Le premier exemple sera dans le domaine médical avec l’IRM fonctionnel, où les graphes spatio-temporels sont utilisés pour représenter les connexions fonctionnelles entre les différentes régions du cerveau au fil du temps. Le deuxième exemple sera dans le domaine environnemental avec l’occupation des sols, où les graphes spatio-temporels sont utilisés pour représenter les relations spatiales et temporelles entre les différents types d’occupation des sols au fil du temps.

À partir de la modélisation de grandes quantités de données, il est possible d’extraire des informations utiles. Plus précisément, la recherche de motifs fréquents permet d’extraire des sous-graphes qui apparaissent fréquemment dans un graphe spatio-temporel, qui peuvent permettre de mettre en lumière un phénomène qui se répète dans le temps, ou un ensemble d’entités ayant un lien spatial qui évoluent dans le temps.

Finalement, à partir de la fouille de données, nous pourrons aborder l’utilisation de modèles en apprentissage automatique.

Pause déjeuner
14h-15h30 Christophe Claramunt Graph-based Modelling Opportunities for Exploring Human Mobilities in the Era of the Cyberspace – conférence

The advent of information and communication technology, the Internet of Things, intelligent sensors, pervasive networks, and social media have led our society toward a digital and cyberspace era that offers novel avenues for the understanding of human activities that happen in space and time. Cyberspace is an open, global, unregulated, and virtual area of decentralized human activities, social interactions, and application services whose data, whether voluntarily or involuntarily created at unprecedented rates of dissemination, originate from a variety of user communities, ranging from experts to the general public, and different supports from social media to mobile users, but are not always well structured because they are most often not generated for further manipulation. This course introduces recent new ideas and graph-based modelling frameworks that reflect the spatial and temporal structures that emerge from cyberspace. The talk will introduce a series of theoretical, conceptual, methodological, and graph-based computational advances and contributions of this digital revolution to the study of mobility patterns in urban, regional and maritime environments. This short course will give a panorama of recent advances and will be illustrated by a series of research projects, and will discuss a few perspectives for further work.

Keywords: Graph-based modelling, Big data, social media, sensors, GIS, mobility, transportation studies

16h30-18h Evénement social Visite guidée du centre ville de Rouen et dîner au restaurant
     
Mercredi 26 Juin : Graphes dynamiques
Horaire Intervenant Intitulé & Résumé
8h30-10h Mathilde Vernet Introduction aux graphes dynamiques. Modèles, chemins, connexité.

Nous savons définir un graphe, l’étudier, étudier des problèmes associés, mais que se passe-t-il lorsque l’on rajoute une dimension temporelle à un graphe ? S’il est observé au cours du temps et qu’il est autorisé à évoluer au cours du temps, comment ce nouveau graphe est-il défini ? Que deviennent les définitions et notions de base de la théorie des graphes dans ce nouveau contexte ? Et qu’en est-il des problèmes d’optimisation bien connus dans les graphes ? Nous avons pour objectif de répondre (au moins partiellement) à ces questions.

 
10h-10h30   Pause  
10h30-12h David Ilcinkas L’algorithmique distribuée et les graphes dynamiques

Nous verrons les liens entre algorithmique distribuée et graphes dynamiques. En particulier, nous verrons comment les méthodes et raisonnements classiques du distribué peuvent permettre de trouver des solutions élégantes à des problèmes même centralisés de graphes dynamiques.

 
12h00-14h   Pause déjeuné  
14h00-15h30 Frédéric Guinand TD : algorithmique distribuée dans les graphes dynamiques  
15h30-17h00 Yoann Pigné TP : détection et suivi de communautés dans des graphes dynamiques  
Jeudi 27 Juin: traitement du signal sur graphes
Horaire Intervenant Intitulé & Résumé
8h45-10h15 Pierre Borgnat Une invitation au traitement du signal sur graphes, ou Joseph Fourier en portrait de data scientist

Avec l’explosion du nombre et de la diversité des données numériques, analyser des données sur des graphes est devenu un enjeu incontournable dès lors que l’on souhaite étudier des entités en interaction, en plus de leurs éventuelles caractéristiques propres. Parmi les diverses approches pour cela, nous présenterons les avancées accomplies depuis une douzaine d’année en traitement du signal sur graphe qui offre des outils de traitement et d’analyse de données sur des graphes et des graphes eux-mêmes. Au centre de ses travaux, les équivalents de transformées de Fourier de données (ou signaux) sur graphes ont permis de développer de nouveaux outils pour du filtrage, de l’interpolation, du débruitage ou des décompositions multi-échelles de signaux sur graphes, mais aussi offrent des éléments importants pour forger des méthodes d’apprentissage sur graphes (tels que des Graph Neural Networks). L’exposé présente un état de l’art du domaine, en partant principes de base et des premiers travaux impliquant des transformées à la Fourier pour des données sur graphes, en couvrant les avancées principales puis certaines connexions avec l’apprentissage machine et les réseaux de neurones sur graphes. Ce faisant, l’exposé illustre aussi en quoi la démarche de Fourier reste moderne et universelle et montre comment ses idées, issues de la physique et enrichies par les mathématiques, l’informatique et la théorie du signal, demeurent essentielles pour répondre à des défis actuels en science des données.

10h30-12h Olivier Lézoray Traitement du signal sur graphes: des images aux graphes arbitraires

Dans cet exposé nous aborderons l’adaptation sur graphes de méthodes issues du traitement du signal et des images. Si ces dernières ont permis la résolution de nombreux problèmes inverses (débruitage, filtrage, segentation, etc.), elles sont conçues pour des signaux définis sur des domaines Euclidiens et non facilement exploitables sur des graphes de topologies arbitraires. Après avoir présenté le principe du filtrage nolocal des images qui peut s’interpréter comme un filtrage sur un graphe grille par un opérateur Laplacien, nous présenterons le calcul discret sur graphes. Ce dernier founit un ensemble de définitions d’opérateurs différentiels (gradient, divergence, p-Laplacien) qui permettent d’adapter sur graphes la résolution de nombreux problèmes inverses. Nous présenterons des exemples pour la régularisation de signaux des noeuds d’un graphe arbitraire et leur décomposition hiérarchique pour leur manipulation/réhaussement. Puis nous monterons comment il est possible d’adapter sur graphes la morphologie mathématique (algébrique ou continue) et ses deux opérateurs fondamentaux que sont la dilatation et l’érosion. Enfin, nous terminerons par l’adaptation sur graphes des contours actifs pour la segmentation et le clustering.

Pause déjeuner
13h30-14h30 Loic Landrieu Régularité des signaux sur graphe et analyse spatiale efficace

Les problèmes impliquant une composante spatiale peuvent souvent être résolus en minimisant une fonction définie sur un graphe, dont les solutions présentent une forme de parcimonie structurée. Nous présentons l’algorithme Cut Pursuit, qui exploite cette propriété pour minimiser efficacement des fonctions présentant divers degrés de régularité et de continuité. Appliqué à des problèmes dont la solution est spatialement régulière, l’algorithme Cut Pursuit permet une accélération importante et apporte des garanties de convergence indépendantes de la régularité ou de la convexité des fonctions minimisées.
Ensuite, nous présentons l’approche d’analyse de données 3D de grande taille par Superpoint. Cette méthode exploite la régularité spatiale des labels sémantiques des points 3D en les partitionnant en formes simples. Le graphe encodant l’adjacence entre ces formes permet d’analyser leurs relations plutôt que les points individuels, réduisant ainsi la complexité de l’analyse 3D par plusieurs ordres de grandeurs. Cette méthode permet de réduire considérablement la complexité de l’analyse 3D tout en maintenant une grande précision et en utilisant moins de ressources de calcul.

14h45-15h45 Giulia Loi Traitement du signal sur graphe pour interpréter et décoder l’activité cérébrale en intégrant la connectivité

Les différentes zones du cerveau peuvent être représentées comme des nœuds et les relations structurelles et fonctionnelles entre elles comme des arêtes d’un graphe à grande échelle, également connu sous le nom de connectome. De même, les arêtes d’un réseau cérébral peuvent être éstimées à l’aide d’une série de techniques de neuro-imagerie (électroencéphalographie – EEG, imagerie par résonance magnétique fonctionnelle – IRMf, …) et de méthodes (connectivité structurelle ou fonctionnelle). L’application de la théorie des graphes à la modélisation de la structure et de la fonction du cerveau a permis de mieux comprendre son organisation, suscitant l’émergence d’un nouveau domaine, la Network Neuroscience. Malgré les progrès considérables réalisés dans ce domaine, relativement peu de méthodes exploitent la topologie des réseaux cérébraux pour analyser l’activité cérébrale. Les tentatives récentes dans ce sens ont tiré parti, d’une part, de l’analyse spectrale des graphes (pour décomposer la connectivité cérébrale en vecteurs propres ou gradients) et, d’autre part, du traitement du signal sur graphe (TSG, pour décomposer l’activité cérébrale couplée à un réseau sous-jacent en graph Fourier modes). Allant au-delà des métriques et des approches basées sur l’inférence, d’autres travaux ont utilisé les réseaux convolutionnels sur graphes pour classifier des signaux cérébraux, en intégrant TSG et apprentissage profond. Dans cette présentation, nous donnerons un aperçu des travaux dans la littérature qui utilisent le TSG afin de décoder et d’interpréter l’activité cérébrale. Nous décrirons également plus en détail deux travaux en cours. Dans la première contribution, nous utilisons les graphes de connectivité fonctionnelle IRMf pour définir les opérateurs de convolution spectrale dans un réseau profond entraîné au décodage de tâches. Nous montrons comment l’élagage des paramètres peut être utilisé pour sélectionner les gradients de connectivité les plus importants pour la tâche. Dans la seconde étude, nous analysons l’activité cérébrale mesurée à l’aide d’un EEG à haute densité pendant le visionnage d’une vidéo, et nous effectuons une analyse à l’aide du TSG pour estimer le couplage et le découplage de l’activité électrophysiologique sur un graphe de connectivité fonctionnelle.

16h-18h   Travaux pratiques avec PyGSP
Vendredi 28 Juin: Graphes et apprentissage machine

Horaire Intervenant Intitulé & Résumé
8h30-10h Benoit Gaüzère & Marc Lelarge Introduction au representation learning sur graphes

Les graphes sont une représentation versatile codant simultanément des données et leurs relations. Définir des modèles de Machine Learning utilisant des données sous forme graphe permettrait de profiter pleinement de leur puissance de représentation. Malheureusement, la définition de modèles d’apprentissage efficace sur graphes n’est pas trivial, du notamment à la complexité intrinsèque de ce type de structure. Lors de cet introduction, nous présenterons les différentes approches existantes pour résoudre ce verrou scientifique : plongement de graphes, noyaux sur graphes, distance d’édition et réseaux de neurones sur graphes.

10h-10h30   Pause
10h30-12h Benoit Gaüzère & Guillaume Renton Machine learning sur graphes : Mise en œuvre (pytorch geometric)

La seconde partie de la matinée sera dédiée à la mise en œuvre de modèles de machine learning opérant sur des graphes, avec une application sur des molécules chimiques. Ce tutoriel présente une introduction concise aux réseaux de neurones sur graphes (GNN) avec PyTorch Geometric, une bibliothèque étendant PyTorch pour le traitement de données structurées en graphes. Après une installation guidée, le tutoriel couvre les concepts clés tels que les datasets et les convolutions sur graphes. À travers la création d’un modèle GNN simple pour la classification, il explique le chargement des données, la définition du modèle, et l’entraînement. Des cas pratiques illustrent l’application des GNN à des problèmes réels, et des conseils sur l’optimisation et l’évaluation des modèles sont fournis. Le tutoriel se conclut par des ressources pour approfondir les connaissances sur les GNN et PyTorch Geometric, visant à équiper les lecteurs pour leurs propres projets de recherche ou développement.

12h-14h   Pause
14h00-14h45 Pasquale Foggia Graphs and machine learning: An overview.

In this presentation, we propose an overview of the most common approaches used in machine learning, with a perspective on the recent contributions from the MIVIA group, university of Salerno.

14h45-15h30 Linlin Jia

Bridging Graph Spaces: Novel Algorithms and Their Applications

Over the years, numerous graph-based machine learning algorithms have emerged. Yet the connections among these methods and the respective spaces remain unrevealed, keeping the underlying theories and potential applications behind the mist. This talk explores the intricate relationships among diverse graph-based machine learning methods and their associated metric spaces, including graph kernels, Graph Edit Distances (GEDs), and Graph Neural Networks (GNNs). The objective is to bridge the existing disparities within these graph spaces while simultaneously enhancing the performance of the underlying methodologies. To achieve this, we introduce two distinct yet interrelated pathways. The first path delves into the effort to refine graph metrics via embeddings across different spaces. The second path explores on the potential of learning graph metrics via GNNs. Beyond these methodologies, we extend our study to the practical applications of distinct graph-based models, with a focus on molecule properties prediction, leveraging recent advances in quantum chemistry.