Graph Neural Network (GNN)

Un réseau neuronal de graphes (GNN) est un réseau neuronal qui opère directement sur des graphes : des ensembles de nœuds reliés par des arêtes, où les nœuds comme les arêtes peuvent porter des caractéristiques. Les molécules (atomes et liaisons), les réseaux sociaux (utilisateurs et abonnements), les réseaux routiers (intersections et tronçons), les maillages 3D et les articulations d'un squelette humain sont tous des graphes. Un graphe n'a ni grille ni ordre fixes, et ses nœuds ont des nombres différents de voisins ; les filtres glissants d'un réseau neuronal convolutif (CNN) et le traitement pas à pas d'un réseau neuronal récurrent (RNN) ne s'appliquent donc pas directement. Les GNN gèrent cela par la propagation de messages : chaque nœud met à jour à plusieurs reprises son vecteur de caractéristiques à partir de ceux de ses voisins, produisant des embeddings de nœuds qui encodent à la fois leurs attributs propres et leur position dans le graphe.

Fonctionnement de la propagation de messages#

Une couche GNN met à jour chaque nœud en trois étapes. Chaque voisin envoie un message, généralement une transformation apprise de ses caractéristiques. Le nœud agrège les messages reçus à l’aide d’une fonction qui ignore leur ordre, comme une somme, une moyenne ou un maximum. Il combine ensuite l’agrégat avec ses propres caractéristiques pour former sa nouvelle représentation. Comme l’agrégation ignore l’ordre, le résultat ne dépend pas de la numérotation des nœuds. En 2017, Justin Gilmer et ses collègues ont décrit de nombreux GNN comme des cas particuliers de ce cadre de réseau neuronal à passage de messages. Après la dernière couche, une tête spécifique à la tâche lit les plongements des nœuds pour étiqueter les nœuds, prédire les arêtes manquantes ou classifier un graphe entier :

Chaque couche étend le voisinage d’un nœud d’un saut ; après k couches, le plongement d’un nœud dépend donc de tous les nœuds situés à k arêtes ou moins, c’est-à-dire son champ réceptif dans le graphe. L’extrait PyTorch ci-dessous construit un graphe en chemin de six nœuds, applique trois couches de convolution de graphe avec la normalisation de la GCN de Thomas Kipf et Max Welling, puis utilise autograd pour lister les nœuds d’entrée qui influencent le nœud 0 après chaque couche :

import torch
from torch import nn

# A path graph 0-1-2-3-4-5 as an adjacency matrix with self-loops
A = torch.eye(6)
for i in range(5):
    A[i, i + 1] = A[i + 1, i] = 1
deg = A.sum(dim=1)
A_hat = A / torch.sqrt(deg[:, None] * deg[None, :])  # GCN normalization D^-1/2 (A + I) D^-1/2

torch.manual_seed(0)
x = torch.randn(6, 4, requires_grad=True)  # 4 input features per node
layers = [nn.Linear(4, 4) for _ in range(3)]

h = x
for k, layer in enumerate(layers, start=1):
    h = torch.tanh(A_hat @ layer(h))  # each node mixes in its neighbors' transformed features
    grad = torch.autograd.grad(h[0].sum(), x, retain_graph=True)[0]
    print(f"After layer {k}, node 0 depends on nodes {grad.abs().sum(dim=1).nonzero().flatten().tolist()}")

Il affiche [0, 1], [0, 1, 2] et [0, 1, 2, 3] : le champ réceptif du nœud 0 augmente exactement d’un saut par couche.

Architectures GNN courantes#

• GCN : Le réseau convolutif de graphes calcule H′ = σ(D̃^(−1/2) Ã D̃^(−1/2) H W), où Ã est la matrice d’adjacence avec des boucles sur soi-même et D̃ sa matrice des degrés : une moyenne pondérée par les degrés de chaque nœud et de ses voisins, suivie d’une matrice de poids W partagée par tous les nœuds.
• GraphSAGE : Échantillonne un nombre fixe de voisins par nœud et apprend l’agrégateur, ce qui lui permet de passer à l’échelle de très grands graphes et de calculer des plongements pour des nœuds qui apparaissent après l’entraînement.
• GAT : Les réseaux d’attention sur graphes pondèrent chaque voisin à l’aide de scores d’attention appris, plutôt que de poids fixes fondés sur les degrés.
• GIN : Le réseau d’isomorphisme de graphes somme les voisins et applique un MLP. Keyulu Xu et ses collègues ont prouvé que cette approche permet de distinguer les graphes aussi efficacement que le test de Weisfeiler-Lehman, qui représente la limite supérieure du passage de messages standard.
• Transformeurs pour graphes : Appliquent l’auto-attention à tous les nœuds et ajoutent des encodages positionnels dérivés de la structure du graphe. Un transformeur standard est lui-même un GNN appliqué à un graphe entièrement connecté de jetons.

L’empilement d’un grand nombre de couches entraîne un surlissage : les moyennes répétées rapprochent les plongements des nœuds jusqu’à les rendre indiscernables. C’est pourquoi de nombreux GNN n’utilisent que deux ou trois couches, comme la GCN originale qui en utilisait deux. PyTorch Geometric et la bibliothèque Deep Graph (DGL) implémentent efficacement ces couches sur des listes d’arêtes creuses.

Applications concrètes#

• Prévision météorologique : Publié dans Science en 2023, GraphCast de Google DeepMind effectue un passage de messages sur un maillage multi-échelle couvrant le globe et produit en moins d’une minute des prévisions à 10 jours avec une résolution de 0,25°, surpassant les systèmes déterministes opérationnels les plus précis sur 90 % des 1 380 cibles de vérification.
• Découverte de médicaments : En 2020, des chercheurs du MIT ont entraîné un réseau à passage de messages dirigé pour prédire l’activité antibactérienne à partir de graphes moléculaires. Ils l’ont utilisé pour identifier l’halicine, un composé structurellement différent des antibiotiques connus qui a tué de nombreuses bactéries résistantes aux médicaments lors de tests en laboratoire.
• Systèmes de recommandation : PinSage de Pinterest a appris des plongements d’épingles à partir d’un graphe de 3 milliards d’épingles et de tableaux, avec 18 milliards d’arêtes, et a été entraîné sur 7,5 milliards d’exemples.
• Reconnaissance d’actions basée sur le squelette : ST-GCN considère les articulations du corps comme des nœuds, les relie par des os dans chaque image et relie chaque articulation à la même articulation dans les images voisines, puis classe l’action à partir du graphe spatio-temporel ainsi obtenu. Les modèles d’estimation de pose YOLO26 renvoient 17 points clés COCO par personne dans chaque image : les coordonnées des articulations à partir desquelles un tel graphe de squelette est construit.

GNN et concepts apparentés#

• Graphe de connaissances : Structure de données qui stocke des faits sous forme de triplets entité-relation-entité. Un GNN est un modèle capable d’apprendre à partir d’un tel graphe, par exemple pour prédire des liens manquants.
• Apprentissage profond géométrique : Domaine plus vaste des réseaux construits autour des symétries de leurs données, qui englobe les CNN sur des grilles, les GNN sur des graphes et les modèles sur des maillages et des variétés.
• CNN : Un CNN appliqué à une image est un cas particulier de passage de messages sur un graphe en grille. Chaque pixel y a le même nombre de voisins, à des positions relatives fixes, de sorte qu’un CNN peut apprendre un poids distinct pour chaque position de voisinage, contrairement à un GNN sur un graphe irrégulier.