SUREL+ : Du parcours aux ensembles pour un apprentissage des représentations de graphes basé sur les sous-graphes évolutif

L’apprentissage de représentations de graphes basé sur les sous-graphes (SGRL, subgraph-based graph representation learning) est récemment apparu comme un outil puissant pour de nombreuses tâches de prédiction sur les graphes, grâce à ses avantages en termes d’expressivité du modèle et de capacité de généralisation. La plupart des modèles SGRL antérieurs rencontrent des difficultés computationnelles liées au coût élevé d’extraction de sous-graphes pour chaque requête d’entraînement ou de test. Récemment, SUREL a été proposé pour accélérer le SGRL : il échantillonne des marches aléatoires en amont (offline) et les assemble en ligne (online) comme une approximation des sous-graphes pour l’apprentissage de représentations. Grâce à la réutilisabilité des marches échantillonnées sur différentes requêtes, SUREL atteint des performances de pointe en termes d’évolutivité et de précision de prédiction. Toutefois, SUREL souffre encore d’un surcroît computationnel élevé causé par la duplication de nœuds dans les marches échantillonnées. Dans ce travail, nous proposons un cadre novateur, SUREL+, qui améliore SUREL en remplaçant les marches par des ensembles de nœuds pour représenter les sous-graphes. Cette représentation basée sur des ensembles élimine par définition les nœuds redondants, mais peut présenter une taille irrégulière. Pour résoudre ce problème, nous concevons une structure de données creuses personnalisée permettant de stocker et d’accéder efficacement aux ensembles de nœuds, ainsi qu’un opérateur spécialisé pour les assembler en lots en parallèle. SUREL+ est modularisé afin de supporter plusieurs types d’échantillonneurs d’ensembles, des caractéristiques structurelles et des encodeurs neuronaux, afin de compenser la perte d’information structurelle résultant de la réduction des marches vers des ensembles. Des expériences étendues ont été menées pour valider SUREL+ sur des tâches de prédiction de liens, de types de relations et de motifs d’ordre supérieur. SUREL+ obtient des accélérations de 3 à 11 fois par rapport à SUREL tout en maintenant une performance de prédiction comparable, voire supérieure ; comparé aux autres modèles de base SGRL, SUREL+ atteint des accélérations d’environ 20 fois et améliore significativement la précision de prédiction.