GNN en clair : comprendre et entraîner un GCN

Les réseaux de neurones graphiques appliquent l’apprentissage profond à des structures relationnelles. Leur variante la plus répandue, le GCN, combine un nœud et ses voisins pour produire de nouvelles représentations. Voici ce que ces modèles offrent, comment ils s’entraînent et la manière exacte dont s’écrivent leurs mises à jour et normalisations.

Généralisation, complexité et limites annoncées

Les calculs d’un GCN sont linéaires par rapport à la taille du graphe, avec une complexité O(|V| + |E|). Le partage de la matrice de poids W entre les nœuds fait que le nombre de paramètres ne dépend pas de la taille du graphe d’entrée. Pour une structure de graphe donnée, les GCN traitent les nœuds avec une importance différente selon leur proximité à d’autres nœuds. Les GNN se généralisent à de nouvelles structures car ils apprennent des transformations appliquées individuellement aux nœuds. L’inférence sur un nouveau graphe fonctionne généralement bien lorsque sa structure reste similaire à celle vue à l’entraînement ; si elle en diffère complètement, la performance peut se dégrader. Comme les CNN, les GCN exploitent le contexte local pour améliorer la performance globale. Un trop grand nombre de couches est évité car il peut conduire au sur-lissage.

Entraîner sur un ou plusieurs graphes, et produire des embeddings

La rétropropagation dans les GNN se déroule de manière similaire à celle des réseaux de neurones classiques. Un GNN peut être entraîné sur un seul grand graphe ou sur plusieurs graphes ; en général, l’entraînement sur plusieurs graphes améliore la généralisation à des graphes nouveaux. Un GNN produit des embeddings de nœuds, ensuite exploités par un modèle séparé et plus petit pour des tâches en aval comme la classification de nœuds, d’arêtes ou de graphes. Dans cette configuration, les étiquettes de la tâche en aval servent au calcul de la perte et à l’entraînement du GNN. Il existe toutefois des cas rares où le GNN fournit directement les prédictions finales. La dimension des vecteurs de caractéristiques par couche constitue un hyperparamètre majeur et peut varier entre couches.

La mise à jour d’une couche GCN s’appuie sur trois matrices

La mise à jour d’une couche GCN mobilise trois matrices : A pour l’adjacence, H pour les caractéristiques de nœuds et W pour la transformation linéaire apprenable partagée. Dans A, A[i][j] vaut 1 si les sommets i et j sont connectés et 0 sinon ; la iᵉ ligne de H code le vecteur du iᵉ nœud. Le produit AH somme les caractéristiques des voisins et ignore les non-voisins, puis la multiplication par W et l’application d’une non-linéarité σ fournissent les caractéristiques mises à jour. ReLU ou LeakyReLU sont généralement utilisées pour σ. Par associativité, le calcul de AHW se fait en pratique en commençant par HW, afin de réduire le coût de calcul en ne multipliant par A qu’ensuite. La rétropropagation progresse de la dernière couche vers la première, alors que l’agrégation d’une couche s’applique en parallèle à tous les nœuds. Les dimensions de caractéristiques peuvent changer d’une couche à l’autre et la structure du graphe est préservée au fil des couches.

Inclure le nœud central et contrôler l’échelle

Dans la forme naïve, un nœud n’intègre pas ses propres caractéristiques car A[i][i] vaut 0 par défaut. L’ajout de la matrice identité à A introduit une boucle réflexive qui inclut le nœud central dans l’agrégation et modifie la règle de mise à jour en conséquence. Les multiplications modifient l’échelle des caractéristiques, ce qui motive une normalisation par la matrice de degré D, où D[i][i] correspond au nombre de voisins du nœud i en incluant le nœud lui-même après ajout des boucles, et où D[i][j] vaut 0 pour i ≠ j. La règle peut alors s’écrire avec cette normalisation, y compris comme moyenne au niveau nœud. Une variante répandue applique une normalisation symétrique en posant D^(−1/2) de part et d’autre d’Ā, et se réécrit au niveau nœud via des poids dépendant des degrés des nœuds (Kipf & Welling, ICLR 2017).

Pourquoi des graphes, et ce que les GNN héritent des CNN

Les graphes modélisent des objets et leurs relations dans des contextes variés, notamment des molécules, des réseaux sociaux, des joueurs durant un match, le trafic ou des cartes de métro. Les réseaux de neurones graphiques appliquent l’apprentissage profond à ces structures et, une fois entraînés, s’appliquent à de nouveaux graphes. Ils ont été utilisés pour des tâches comme la découverte d’antibiotiques, et servent à classer des nœuds, des arêtes ou des graphes entiers. Leur principe emprunte aux convolutions d’images : combiner une entité avec son voisinage pour produire des représentations enrichies. Une image peut d’ailleurs se voir comme un graphe où un pixel est relié à jusqu’à quatre voisins. Les GNN fonctionnent avec peu de couches, généralement entre 2 et 4, un nombre trop élevé pouvant provoquer du sur-lissage. Par rapport à des réseaux entièrement connectés, ils apprennent des transformations appliquées nœud par nœud, sans lier le nombre de paramètres à la taille d’entrée. Ils partagent avec les CNN l’exploitation du contexte local et s’appuient sur un calcul de complexité linéaire, avec une matrice de poids partagée entre tous les nœuds.