L'attention globale améliore la généralisation des réseaux graphiques

Cet article propose d’intégrer un module d’attention globale à faible rang (Low-Rank Global Attention, LRGA), une variante efficace en termes de calcul et de mémoire de l’attention par produit scalaire (Vaswani et al., 2017), aux réseaux de neurones graphes (Graph Neural Networks, GNNs) afin d’améliorer leur capacité de généralisation. Pour quantifier théoriquement les propriétés de généralisation apportées par l’ajout du module LRGA aux GNNs, nous nous concentrons sur une famille spécifique de GNNs expressifs et démontrons qu’en les enrichissant de LRGA, on obtient une alignement algorithmique avec un puissant test d’isomorphisme de graphes, à savoir l’algorithme 2-Folklore Weisfeiler-Lehman (2-FWL). Plus précisément, nous : (i) considérons le cadre récent des réseaux de neurones graphes aléatoires (Random Graph Neural Network, RGNN) (Sato et al., 2020) et prouvons qu’il est universel au sens probabiliste ; (ii) montrons que l’RGNN enrichi de LRGA s’aligne sur l’étape de mise à jour de l’algorithme 2-FWL via des noyaux polynomiaux ; (iii) bornons la complexité d’échantillonnage de la carte de caractéristiques du noyau lorsqu’elle est apprise à l’aide d’un MLP à deux couches initialisé aléatoirement. Du point de vue pratique, l’ajout du module LRGA aux couches GNN existantes permet d’obtenir des résultats de pointe sur les benchmarks actuels de GNNs. Enfin, nous observons que l’ajout de LRGA à diverses architectures de GNNs réduit souvent la différence de performance entre ces modèles.