Modélisation générative profonde évolutive pour les graphes épars

L'apprentissage de modèles génératifs de graphes est une tâche difficile pour l'apprentissage profond et a une large applicabilité à une série de domaines comme la chimie, la biologie et les sciences sociales. Cependant, les méthodes neuronales profondes actuelles souffrent d'une évolutivité limitée : pour un graphe comportant n nœuds et m arêtes, les méthodes neuronales profondes existantes nécessitent une complexité de l'ordre de `Omega(n^2) pour construire la matrice d'adjacence. D'un autre côté, de nombreux graphes du monde réel sont en fait peu denses, c'est-à-dire que m est égal à n^2.

Sur cette base, les auteurs ont mis au point un nouveau modèle autorégressif appelé BiGG qui utilise cette sparsité pour éviter de générer la matrice d'adjacence complète et, surtout, réduit la complexité temporelle de la génération du graphe à O((n + m)\log n). De plus, pendant l'apprentissage, ce modèle autorégressif peut être parallélisé avec O(\log n) étapes de synchronisation, ce qui le rend beaucoup plus efficace que les autres modèles autorégressifs qui nécessitent \Omega(n).

Des expériences sur plusieurs points de référence montrent que l'approche proposée non seulement s'adapte à des graphes de taille plus importante que ce qui était possible auparavant avec des modèles génératifs de graphes autorégressifs profonds, mais qu'elle permet également de générer des graphes de meilleure qualité.

Cet article a été publié lors de la 37e conférence internationale sur l'apprentissage automatique(ICML).