Soutenance mémoire
Ces dernières années ont vu se démocratiser tout un ensemble de solutions d’acquisition, de gestion et d’analyse des données. À l’échelle des infrastructures, l’arrivée de technologies permettant une gestion dynamique des ressources, et même une servicialisation de celles-ci, a contribué à un contrôle très largement accru des coûts liées à ces installations, et même à une réduction globale de ceux ci. Dans le domaine logiciel, l’émergence de technologies (langages, frameworks et bibliothèques) sous licence libre favorise leur large adoption, et rend ainsi disponible à tous des outils modernes et efficaces.
Cet accès facilité aux infrastructures et aux traitements, conjugués à une urbanisation croissante des systèmes d’information, rend désormais possible une réelle mutualisation de l’information. Au travers d’un pipe-line de données, celle-ci est ainsi produite, transférée, agrégée et mise à disposition automatiquement, pouvant par la suite alimenter des traitements. Ces traitements sont de forme et de finalités très diverses, et vont de leur simple représentation à l’élaboration de modèles explicatifs ou prédictifs. Il est à noter que lorsque la volumétrie le permet, ces modèles n’utilisent plus seulement des méthodes statistiques pour leur optimisation, mais de plus en plus des algorithmes dits d’apprentissage automatique (Machine Learning) tels que les réseaux de neurones ou les forêts aléatoires auxquels il était auparavant plus difficile de faire appel dans les cas d’usage courants. De part leur souplesse d’utilisation et la diversité de cas d’usage adressés par ces méthodes, ces méthodes viennent considérablement enrichir le domaine de l’analyse de données.
Caractérisation de sous-graphes
Pour étudier des graphes, et à fortiori des sous-graphes dans un ensemble d’observations, il s’avère nécessaire de pouvoir les identifier formellement, et ainsi désigner de façon uniforme des structures qui seraient identiques. En particulier, il est important de pouvoir rendre indépendante la notation que l’on fera d’un (sous-)graphe vis-à-vis d’un quelconque ordre dans une énumération de noeuds ou d’arêtes. On cherche ainsi à définir une notation de graphe qui soit canonique, de sorte que deux (sous-)graphes isomorphes aient la même forme canonique.
Problème
Un graphe G = (VG, EG) ∈ G est une structure de données composée d’un ensemble de noeuds VG, reliés entre eux par des arêtes rassemblées dans un ensemble EG. Ce sont des objets mathématiques particulièrement adaptés pour représenter une population d’entités interconnectées via des liens (uniformes ou non), telles que des réseaux de télécommunication, des molécules, des relations sociales, etc. Un graphe peut être décrit par une énumération des éléments de VG et EG. Cependant, une telle énumération n’est pas unique, car on ne peut pré-supposer l’existence d’une relation d’ordre ordonnant de tels ensembles. Sur la base de ce type de description non-unique, on constate que deux graphes identiques peuvent avoir des encodages différents. La nécessité de pouvoir confirmer ou infirmer une égalité structurelle entre deux graphes amène naturellement à la définition du problème d’isomorphisme de graphes.
Isomorphisme de graphes
Soient deux graphes G = (VG, EG) et H = (VH, EH), un isomorphisme f : VG → VH de G vers H est une bijection de l’ensemble des sommets de G dans l’ensemble des sommets de H, conservant les arêtes.
G ≃ H ⇐⇒ ∃ f, ∀ u, v ∈ VG, (u, v) ∈ EG ⇔ (f(u), f(v)) ∈ EH
Si f existe, alors G et H admettent une relation d’isomorphisme (≃) et sont donc isomorphes, on note alors G ≃ H. Déterminer l’existence (ou la non existence) de f est la façon la plus élémentaire de répondre à ce problème. Déterminer une expression de f est une tâche au moins aussi complexe, qui répond également au problème. Il est important de noter que malgré de nombreux travaux portant sur ce problème d’isomorphisme [39, 38], sa classe de complexité reste à ce jour mal connue [40, 41] : il n’est pas prouvé que ce problème soit NP-complet, mais on ne connaît pas non plus d’algorithme polynomial pour le cas général des graphes quelconques. Ce problème dispose donc de sa propre classe de complexité notée GI (Graph Isomorphism) [43, 42]. Des travaux récents [44] semblent toutefois indiquer que ce problème soit quasi-polynomial, bien que cela reste à confirmer.
Forme canonique de graphe
Une autre façon de résoudre ce problème est de calculer, pour tout graphe G, un représentant dit canonique. Ce représentant (généralement un graphe isomorphe à G) sera unique pour toute la classe d’isomorphisme de G, [G] . Deux graphes isomorphes deviennent donc littéralement égaux lorsqu’ils sont canonisés. La fonction de canonisation Canon est ainsi un morphisme de l’ensemble des graphes G vers l’ensemble quotient G/ ≃ .
Canon : G → G/ ≃
G ≃ H ⇐⇒ Canon(G) = Canon(H)
C’est un problème qui est au moins aussi complexe que le test d’isomorphisme classique, car sa résolution fournit une solution à ce dernier dans tous les cas. Par ailleurs dans le cas général, il est plus coûteux de calculer une forme canonique que de tester un isomorphisme. En effet, il est souvent possible de statuer sur les test d’isomorphisme avant l’exécution complète de l’algorithme. Ceci étant, malgré un surcoût algorithmique, ce problème connexe présente de nombreux avantages. La forme canonique d’un graphe G étant unique, celle-ci ne nécessite d’être calculée qu’une seule fois, après quoi on pourra directement comparer les formes canoniques de graphes candidats à un isomorphisme, en un temps beaucoup plus court. Cette complexité supplémentaire est donc très vite amortie dès lors que l’on doit effectuer beaucoup de tests d’appariements sur une population de (sous-)graphes.
Lors de l’élaboration de modèles structures à activité notamment, on cherche justement à rendre les fragments (sous-graphes) étudiés indépendants de la manière dont ils sont encodés, afin de pouvoir regrouper les éléments qui seraient effectivement identiques et porteurs de la même information. On pense également au cas où l’on souhaite indexer ce type de fragments, pour la construction d’un index dans une base de données, où il serait impensable de réaliser à chaque recherche un test d’isomorphisme. Dans certains domaines bien spécifiques, des travaux ont pu aboutir à des heuristiques pour standardiser des écritures, grâce à la recherche de nombreux invariants de graphes et du domaine. On peut citer en ce sens la notation SMILES [45] ou InChI [46] en chimie organique, qui se veulent être des écritures uniques pour une molécule. La principale limitation de ces écritures réside dans l’exploitation d’invariants chimiques pour lever les ambiguïtés, forme de connaissance entièrement relative au domaine et donc extérieure au contexte du graphe considéré. Elles ne sont donc pas applicables dans le cas général.
|
Table des matières
Introduction
La chimie organique
Caractérisation d’une substance chimique
Modèles Structure-Activité ([Q]SAR)
Contexte et Problématique
Contributions
1 Caractérisation de sous-graphe à un isomorphisme près
1.1 Problème
1.1.1 Isomorphisme de graphes
1.1.2 Forme canonique de graphe
1.1.3 Algorithmes
1.1.4 Proposition
1.2 Écriture canonique d’un arbre
1.2.1 Définitions
1.2.2 Fonction de trace σ
1.3 Écriture d’un graphe quelconque en arbre : Scott
1.3.1 Étapes principales
1.3.2 Ordonnancement selon une racine (étape 1)
1.3.3 Transformation en arbre (étape 2)
1.3.4 Désignation d’une racine et encodage (étape 3)
1.3.5 Grammaire
1.4 Analyse de complexité temporelle
1.4.1 Identification de la racine ρ, ϕρ
1.4.2 Encodage d’un arbre, ϕt
1.4.3 Morphisme de G vers T par f, ϕf
1.4.4 Complexité globale
1.4.5 Parallélisation
1.5 Application
1.5.1 Shrunken multipedes graphs
1.5.2 Graphes moléculaires
1.6 Conclusion
1.6.1 Performances
1.6.2 Cas d’usage type
1.6.3 Perspectives
Glossaire
2 Plongements sémantiques de fragments de graphe
2.1 Fragments de graphes
2.1.1 Définition
2.1.2 Fragmentation d’un graphe
2.1.3 Vocabulaire généré
2.1.4 Dimensionnalité d’un espace de fragments
2.2 Analogie avec les langages naturels
2.2.1 Distributions de fragments
2.2.2 Rapprochement empirique avec le TALN
2.2.3 Formulation de l’analogie
2.3 Construction de plongements lexicaux
2.3.1 Les plongements lexicaux en TALN
2.3.2 Les plongements adaptés aux graphes
2.4 Adaptation aux fragments moléculaires
2.4.1 Plongements de fragments moléculaires
2.4.2 Protocole d’apprentissage
2.4.3 Requêtes par rapport à un fragment de référence
2.4.4 Densification et projection des plongements
2.5 Conclusion
3 Exploitation des plongements de fragments dans les Qsar
3.1 Caractérisation de graphe
3.1.1 Graphes et mesures de similarité définies sur l’ensemble des graphes
3.1.2 Graphe comme ensemble de fragments
3.1.3 Graphe comme un réseau de noeuds
3.1.4 Récapitulatif
3.2 Construction d’un modèle prédictif
3.2.1 Graph Attention Network (GAT)
3.2.2 Protocole d’évaluation
3.3 Expérimentations et résultats
3.3.1 Tâche de régression
3.3.2 Tâches de classification
3.3.3 Conclusion
Conclusion
