Ecole d’été Graphes – GRAPHADON

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.

Un très grand nombre de problèmes usuels sur les graphes sont NP-difficiles. Afin de montrer cette difficulté, on utilise généralement des gadgets, sortes de motifs spécifiques dans le graphe, qui permettent de modéliser un autre problème connu comme étant NP-difficile, typiquement 3-SAT. Les instances ainsi fabriquées sont très contraintes. Ce premier exposé vise d’une part à introduire les définitions qui seront utilisées dans la suite de la journée et d’autre part à mettre en évidence la spécificité des graphes apparaissant dans les preuves de complexité. Nous montrerons aussi à quel point une petite relaxation du problème ou une petite variation du graphe rend le problème facile sur les instances. L’exposé se voudra accessible, très interactif, et sera animé conjointement avec Aline Parreau.

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

Dans cet exposé, en continuité du précédent, nous montrerons plus généralement comment exploiter certaines propriétés des graphes pour trouver des algorithmes plus efficaces. En effet, dès lors que l’on supppose que le graphe à une certaine structure (e.g, une largeur d’arborescente bornée ou bien des contraintes topologiques), la plupart des problèmes ne sont plus NP-difficiles ou bien peuvent être approchés de manière efficace. Nous illustrerons cela sur plusieurs exemples en utilisant des algorithmes d’approximation ou de la programmation dynamique pour trouver des algorithmes rapides. Nous évoquerons aussi la notion de noyau et les schéma FPT si le temps le permet. L’exposé se voudra accessible, très interactif, et sera animé conjointement avec Paul Dorbec.

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.

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.

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.

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.

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.

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.

Le cerveau humain est composé d’un réseau complexe formé de dizaine de milliards de neurones, chacun d’entre eux étant relié à 100 000 autres, via les axones qui constituent les faisceaux de fibres de la matière blanche. Au cours de la dernière décennie, certains projets de neuroimagerie tels que le Human Connectome Project (HCP) ont proposé de cartographier ces connexions cérébrales, connues sous le nom de « connectome », afin d’améliorer notre compréhension de l’organisation fonctionnelle et structurelle du cerveau. En effet, la connectivité peut être représentée sous forme d’un graphe dans lequel les nœuds représentent les zones cérébrales et les arêtes symbolisent les connexions entre eux. La connectivité cérébrale non dirigée a été classée en deux catégories : (i) la connectivité structurelle estimée par IRM de diffusion (IRMd), où les liens représentent les axones ou la densité des fibres neuronales et (ii) la connectivité fonctionnelle (mesurée par exemple avec l’IRMf, l’EEG ou la NIRS) où les liens représentent des dépendances statistiques entre les signaux cérébraux de différentes régions, telles que les corrélations, la cohérence ou l’entropie de transfert. Dans ces contextes, une estimation robuste de ces réseaux reste un défi. Les approches classiques d’estimation de la connectivité n’exploitent pas en effet toutes les informations des données d’imagerie, qui pourraient être utiles pour mettre en évidence ces modifications complexes. L’introduction de techniques d’imagerie quantitative innovantes permettant d’estimer la microstructure ainsi que la multimodalité permettant d’estimer des biomarqueurs plus fins et plus spécifiques permettent d’envisager une meilleure estimation dans ces cas complexes. 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 estimée par la connectivité structurelle pour analyser l’activité fonctionnelle cérébrale. Certaines études ont proposées des approches issues du traitement du signal sur graphe (TSG), qui décomposent l’activité cérébrale sur les composantes spectrales du graphe). 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. Pour caractériser comment les signaux interagissent avec les réseaux cérébraux sous-jacent, les transformations de Fourier et d’ondelettes ont été étendues aux données sous forme de graphe. Dans la première étude, nous analysons le couplage et le découplage de l’activité fonctionnelle sur un graphe de connectivité structurelle et ces mesures sont ensuite utilisées pour classifier différentes maladies comme dépression et l’anxiété. Et dans la seconde étude, nous présentons les avantages de l’utilisation de paquets d’ondelettes de graphes en neuroimagerie. Nous montrerons l’intérêt de cette approche par rapport aux méthodes classiques dans le contexte des maladies psychiatriques.

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.

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.

In this presentation, we propose an overview of the most common approaches used for machine learning with Graph Neural Networks, using two cybersecurity problems as our case studies. In the first problem, we will use graphs for representing (snapshots of) network traffic on a network of Internet-of-Things devices, with the goal of detecting anomalous conditions due to cyber-attacks; an important assumption is that we cannot anticipate the kind of attacks, and consequently we can only use examples of normal traffic for training our system. In the second problem, graphs will be used to represent the structure of the source code of a C function, with the goal of detecting if the function contains some security vulnerability, and possibly to recognize the kind of vulnerability.

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.