Conception conjointe d'algorithmes et de systèmes pour un apprentissage efficace des représentations de graphes basé sur les sous-graphes

L’apprentissage représentationnel des graphes basé sur les sous-graphes (SGRL, subgraph-based graph representation learning) a été récemment proposé pour relever certains défis fondamentaux auxquels font face les réseaux de neurones graphiques classiques (GNN, graph neural networks), et a démontré des avantages dans de nombreuses applications clés du data science, telles que la prédiction de liens, de relations et de motifs. Toutefois, les approches actuelles de SGRL souffrent de problèmes d’évolutivité, car elles nécessitent l’extraction de sous-graphes pour chaque requête d’entraînement ou de test. Les solutions récentes visant à améliorer l’évolutivité des GNN classiques ne sont pas directement applicables au SGRL. Dans ce travail, nous proposons un cadre novateur, SUREL, pour un SGRL évolutif, en concevant conjointement l'algorithme d'apprentissage et son support système. SUREL adopte une décomposition des sous-graphes basée sur les marches aléatoires et réutilise ces marches pour reconstruire les sous-graphes, ce qui réduit considérablement la redondance liée à l’extraction des sous-graphes et permet un calcul parallèle efficace. Des expériences menées sur six graphes homogènes, hétérogènes et d’ordre supérieur, comportant des millions de nœuds et d’arêtes, démontrent l’efficacité et l’évolutivité de SUREL. En particulier, par rapport aux méthodes de base de SGRL, SUREL obtient un gain de vitesse de 10× tout en offrant des performances de prédiction comparables, voire supérieures ; quant aux GNN classiques, SUREL améliore la précision de prédiction de 50 %.