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
-
Lundi 24 Juin: Graphes et algorithmique
-
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 -
Jeudi 27 Juin: traitement du signal sur graphes
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 | Intervention experte |
Mardi 25 juin : Graphes Sémantiques
Mercredi 26 Juin : Graphes dynamiques
Horaire | Intervenant | Intitulé & Résumé | |
---|---|---|---|
8h30-10h | Mathilde Vernet | Introduction aux graphes dynamiques. Modèles, chemins, connexité. | |
10h-10h30 | Pause | ||
10h30-12h | David Ilcinkas | Exploration of Time-Varying Networks | |
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 |
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 Lezoray | 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. |
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 | 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 | 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. |
12h-14h | Pause déjeuné | |
14h-15h | Guillaume Renton | Machine Learning et graphes de connaissances
Le machine learning sur graphes a connu un essor durant les dernières années. Parmi les nouveaux challenges à résoudre, les graphes hétérogènes constituent une cible majeure. Dans cet exposé, nous présenterons quelques avancées dans le domaine de l’apprentissage sur graphes de connaissances, fondés notamment sur les réseaux de neurones sur graphes. |
15h-16h | 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. |
16h-17h | Linlin Jia | From graph kernels to graph neural networks.
In this presentation, we will present some applications of graph based machine learning methods to particular domains like the prediction of quantum properties of molecules. |