Thèse de Abderaouf Gacem
Sujet :
Date de début : 01/11/2020
Date de fin (estimée) : 01/11/2023
Encadrant : Hamida Seba
Co-encadrant : Christophe Garcia, Mohammed Haddad
Résumé :
Les données structurées sous forme de graphes sont omniprésentes dans de nombreux domaines d’application, allant des réseaux sociaux et la biologie aux systèmes de recommandation et aux graphes de connaissances. La capacité d’appliquer des algorithmes d’apprentissage profond sur les graphs (appellé aussi apprentissage de représentations de graphes ou GRL pour graph representation learning), est cruciale pour exploiter efficacement l’information encapsulée dans ces structures. Toutefois, cet apprentissage se heurte à des défis majeurs, en particulier en matière de passage à l’échelle et de généralisation. Une piste prometteuse pour répondre à ces problématiques
est l’augmentation de données, une stratégie classique en apprentissage automatique, mais encore sous-exploitée dans le contexte des graphes.
Ce travail propose une étude rigoureuse et approfondie de l’augmentation de données sur les graphes, en tant que fil conducteur pour concevoir des algorithmes GRL à la fois performants et scalables. Nous analysons comment l’augmentation peut être injectée à différents niveaux du pipeline GRL : depuis les marches aléatoires sur le graphe en entrée, à l’entraînement par mini-batch, jusqu’à l’augmentation dans l’espace latent.
Notre démarche s’articule autour de trois contributions principales :
1- Biaisage structurel des marches aléatoires : Nous revisitons les méthodes basées sur les marches aléatoires, qui constituent un socle fondamental pour l’apprentissage d’embeddings de noeuds. Nous introduisons une stratégie de biaisage innovante exploitant la distance de résistance, une métrique reflétant la structure globale du graphe, pour guider la génération des marches. Le résultat est un meilleur équilibre entre exploration locale et globale, permettant d’obtenir des marches plus informatives tout en conservant la simplicité et l’efficacité des méthodes de premier ordre.
2- Échantillonnage de mini-batch pour les GNNs : Nous nous intéressons ensuite aux réseaux de neurones de graphes (ou GNNs Graph Neural Networks), où l’apprentissage par mini-batch est une méthode essentielle pour assurer la scalabilité. Suite au succès de l’augmentation structurelle dans les marches aléatoires, nous posons la question suivante : peut-on repenser la génération des mini-batch sous l’angle de l’augmentation ? Pour cela, nous proposons FireForest, une méthode d’échantillonnage qui produit des mini-batch respectant les propriétés structurelles globales tout en introduisant des variations topologiques. FireForest permet un entraînement efficace des GNNs sans compromettre la qualité des représentations apprises.
3- Augmentation dans l’espace latent : Enfin, nous nous attaquons aux limites de l’augmentation appliquée directement dans l’espace du graphe d’entrée, souvent trop vaste et complexe à explorer. Inspirés par la capacité humaine à imaginer des variantes plausibles d’une structure perçue, nous concevons un cadre d’augmentation de bout en bout, entièrement apprenable, opérant dans l’espace latent des GNNs. Cette approche permet au modèle de simuler en interne des augmentations de graphes, lui donnant ainsi la capacité d’extrapoler des variantes pertinentes qui favorisent la généralisation. Elle introduit une forme puissante et abstraite d’augmentation.
Ces contributions démontrent que l’augmentation de données constitue un levier polyvalent pour améliorer l’apprentissage de représentations de graphes. En intégrant des stratégies d’augmentation à divers niveaux de la chaîne GRL, nous proposons un cadre méthodologique qui renforce à la fois la scalabilité et la capacité de généralisation des modèles d’apprentissage profond sur les graphes.