Rapprocher les espaces de graphes et à noyaux : une perspective de la pré-image

Les graphes permettent de modéliser un large éventail de données du monde réel. Avec les progrès des méthodes d’apprentissage automatique, l’utilisation de ces méthodes sur les graphes est devenue de plus en plus intéressante au sein de la communauté scientifique. Parmi les différentes études, les problèmes de prédiction et de génération de graphes suscitent un intérêt grandissant, porté par de nombreuses applications, notamment en chemoinformatique, en analyse de réseaux sociaux et en vision par ordinateur. La flexibilité associée aux graphes possède un inconvénient majeur. Les algorithmes d’apprentissage automatique étant définis sur des données vectorielles, leur adaptation aux graphes n’est pas triviale. Il est donc important de concevoir des outils permettant d’utiliser ces méthodes d’apprentissage automatique sur les graphes. Les noyaux sur graphes sont un outil puissant pour traiter ce problème en comblant le fossé entre un espace de graphes et un espace à noyau. Inversement, étant donné un élément dans un espace à noyau, on s’intéresse à construire son homologue dans l’espace de graphes ; c’est le problème de pré- image de graphe. La résolution de ce problème ouvre la voie à de nombreuses applications prometteuses, telles que la synthèse de molécules et la conception de médicaments. Pour résoudre les problèmes susmentionnés, nous proposons dans cette thèse de nouvelles méthodes pour construire la pré-image de graphe. Tout d’abord, nous passons en revue les noyaux sur graphes basés sur des motifs linéaires, qu’on compare à des noyaux basés sur des motifs non linéaires. Des analyses théoriques et expérimentales approfondies sont présentées et trois stratégies sont proposées pour réduire la complexité de calcul et de stockage de ces noyaux. Ensuite, nous étudions la stabilité des plus récentes heuristiques de calcul de distance d’édition de graphes et proposons une méthode d’apprentissage de métrique pour optimiser les coûts d’édition utilisés par la distance d’édition de graphes pour des problèmes de régression. Les expériences montrent que notre méthode permet d’améliorer les performances de prédiction par rapport à l'état de l’art. Sur la base de ces deux travaux, nous proposons une méthode de calcul de pré-image de graphe basée sur l’apprentissage de métrique. Pour cela, l’espace de graphes, muni d’une distance d’édition de graphes, est aligné avec l’espace à noyau associé à un noyau particulier. Pour ce faire, la méthode proposée optimise les coûts d’édition afin de faire correspondre les distances dans les deux espaces. Ensuite, une estimation de la pré-image de graphe est obtenue par une méthode générative de graphe médian, configurée avec les coûts d’édition optimisés. Les expérimentations effectuées montrent que notre méthode est plus performante et plus générique que l’état de l’art. Enfin, pour aider à résoudre les problèmes susmentionnés, nous avons publié une bibliothèque en Python pour l’apprentissage automatique de graphes, comprenant l’implémentation de noyaux sur graphes, d’algorithmes de calcul de distances d’édition de graphes et de méthodes de calcul de la pré-image de graphes.Graphs are able to represent a wide range of real-world data due to the nature of their structure and their rich expressiveness. With the advance of state-of-the-artmachine learning methods, applying these methods on graph data has become more and more intriguing for academic and industry societies. Among all studies, graph prediction and graph construction problems draw a lot of interest, since they allow to address many applications such as in chemoinformatics, social network analysis, and computer vision. However, the expressiveness of graphs is a double-edged sword. Indeed, it is difficult to apply most machine learning algorithms on graphs because they were defined for vector data. Therefore, it is important to design tools to utilize these machine learning methods on graphs. Graph kernels provide a powerful tool to deal with this problem by bridging the gap between a graph space and a kernel space. Inversely, given an element in a kernel space, one is interested in constructing its counterpart in the graph space; this is the socalled pre-image problem. Solving the pre-image problem for graphs opens the door to many interesting applications, such asmolecule synthesis and drug design. To address the aforementioned problems, we propose in this thesis novel methods to construct graph pre-images given a graph kernel. First, we provide an in-depth review of graph kernels based on linear patterns, and compare them to some kernels based on non-linear patterns. Thorough theoretical and experimental analyses are provided and three strategies are proposed to address computational complexity and memory usage of these kernels. Second, we study the stability of the state-of-the-art graph edit distance heuristics and propose a metric learning approach to estimate the graph edit costs for regression. Experiments show that the proposed method outperforms state-of-the-art methods. Based on these two successful working directions, we then propose a graph pre-image method based on metric learning. For this purpose, the graph space endowed with graph edit distances is aligned with the kernel space defined by a graph kernel. To this end, we optimize the edit costs by matching graph edit distances and distances in the kernel space. After that, the graph pre-image is estimated by a median generative method. Experiments show that our method outperforms the state of the art. Finally, to help solve the aforementioned problems, we published a Python library on graph machine learning, including the implementations of graph kernels, graph edit distances, and graph pre-image methods