Les réseaux de neurones pour graphes (GNN) sont une classe de réseaux de neurones artificiels conçus pour des tâches dont les entrées sont des graphes. Un graphe se compose de nœuds (sommets) et d'arêtes (connexions) qui peuvent représenter des entités et leurs relations, comme des atomes dans une molécule ou des utilisateurs dans un réseau social. Contrairement aux images ou aux textes, les graphes n'ont pas d'ordre canonique de leurs nœuds, donc les architectures GNN sont généralement conçues pour être équivariantes par permutation : réorganiser les nœuds dans l'entrée réorganise les représentations de nœuds correspondantes de la même manière. Pour les tâches de prédiction au niveau du graphe, les GNN utilisent une fonction de lecture invariante par permutation, dont la sortie est inchangée par l'ordre des nœuds.
L'élément de conception clé des GNN est le passage de messages par paires, où les nœuds du graphe mettent à jour itérativement leurs représentations en échangeant des informations avec leurs voisins. Cela permet au réseau de capturer des motifs et des dépendances structurelles locales. Les GNN sont devenus une pierre angulaire du apprentissage automatique sur les données relationnelles, avec des applications couvrant des domaines du apprentissage profond tels que la biologie moléculaire, la chimie, la physique, les réseaux sociaux et le traitement du langage naturel.
Développement historique
Le concept d'application de réseaux de neurones aux graphes a émergé à la fin des années 1990 et au début des années 2000. Les premières approches récursives et convolutionnelles ont posé les bases, mais le domaine a gagné un élan significatif dans les années 2010 avec l'avènement de ressources informatiques plus puissantes et le succès de l'apprentissage profond dans d'autres domaines. Un article de position de 2022 a soutenu que de nombreuses architectures décrites comme allant "au-delà" du passage de messages peuvent plutôt être interprétées comme un passage de messages sur des graphes modifiés de manière appropriée, proposant le terme "passage de messages augmenté" pour de telles approches. Cela souligne le rôle central du passage de messages dans la conception des GNN.
Architecture
L'architecture d'un GNN générique implémente plusieurs couches fondamentales. Les couches équivariantes par permutation mappent une représentation d'un graphe vers une représentation mise à jour du même graphe, généralement via un passage de messages. Les couches de regroupement local réduisent le graphe par sous-échantillonnage, augmentant le champ réceptif de manière similaire au regroupement dans les réseaux de neurones convolutionnels. Les couches de regroupement global, également appelées couches de lecture, fournissent une représentation de taille fixe de l'ensemble du graphe et doivent être invariantes par permutation. Des exemples de regroupement global incluent la somme, la moyenne ou le maximum élément par élément.
Les GNN standard à passage de messages sont au plus aussi expressifs que le test d'isomorphisme de graphes de Weisfeiler-Leman, ce qui signifie qu'il existe des structures de graphes distinctes qui ne peuvent pas être distinguées par de tels réseaux. Des GNN plus puissants opérant sur des géométries de dimension supérieure, comme les complexes simpliciaux, peuvent être conçus. En 2022, savoir si les futures architectures surmonteront la primitive de passage de messages reste une question de recherche ouverte.
Couches de passage de messages
Les couches de passage de messages sont des couches équivariantes par permutation qui mappent un graphe vers une représentation mise à jour du même graphe. Formellement, elles peuvent être exprimées comme des réseaux de neurones à passage de messages (MPNN). Soit G = (V, E) un graphe, où V est l'ensemble des nœuds et E l'ensemble des arêtes. Pour un nœud u dans V, soit N_u son voisinage, x_u ses caractéristiques, et e_uv les caractéristiques de l'arête (u, v). Une couche MPNN calcule une représentation de nœud mise à jour h_u comme :
h_u = φ(x_u, ⊕_{v∈N_u} ψ(x_u, x_v, e_uv))
où φ et ψ sont des fonctions différentiables (par exemple, des réseaux de neurones artificiels), et ⊕ est un agrégateur différentiable et invariant par permutation tel que la somme, la moyenne ou le maximum. L'agrégateur combine les messages des voisins, et φ met à jour la représentation du nœud. Chaque couche de passage de messages augmente le champ réceptif d'un saut, permettant à l'information de se propager à travers le graphe.
Plusieurs architectures GNN implémentent différentes variantes de passage de messages. Par exemple, les réseaux de neurones convolutionnels pour graphes (GCN) utilisent une simple moyenne des caractéristiques des voisins, tandis que les réseaux de neurones à attention pour graphes (GAT) emploient des mécanismes d'attention pour pondérer les contributions des voisins. Ces variations affectent la capacité du modèle et son biais inductif.
Apprentissage géométrique profond
Les GNN font partie du sujet plus large de l'apprentissage géométrique profond, qui cherche à généraliser les architectures de réseaux de neurones à des domaines non euclidiens. Dans ce cadre, certaines architectures existantes peuvent être interprétées comme des GNN opérant sur des graphes définis de manière appropriée. Par exemple, une couche de réseau de neurones convolutionnel en vision par ordinateur peut être considérée comme un GNN appliqué à des graphes dont les nœuds sont des pixels, avec des arêtes connectant les pixels adjacents. De même, une couche de transformeur en traitement du langage naturel peut être vue comme un GNN appliqué à des graphes complets dont les nœuds sont des mots ou des jetons dans un passage de texte. Cette perspective unifie des architectures apparemment disparates sous un cadre mathématique commun.
Applications
Les GNN ont été appliqués à une large gamme de domaines. Dans la conception de médicaments moléculaires, les molécules sont représentées comme des graphes avec des nœuds pour les atomes et des arêtes pour les liaisons atomiques, incluant souvent des propriétés chimiques connues comme caractéristiques. Les entrées peuvent varier en taille en raison de différents nombres d'atomes et de liaisons. Une tâche au niveau du graphe pourrait être de prédire l'efficacité d'une molécule pour une application médicale spécifique, comme éliminer les bactéries E. coli. Les GNN ont également été utilisés dans l'analyse des réseaux sociaux, les réseaux de citations et les systèmes de recommandation. En physique, ils peuvent modéliser les interactions entre particules, et en optimisation combinatoire, ils ont été appliqués à des problèmes NP-difficiles comme le problème du voyageur de commerce.
Implémentations et bibliothèques
Plusieurs bibliothèques open source implémentent des GNN, les rendant accessibles aux chercheurs et aux praticiens. PyTorch Geometric est une bibliothèque populaire construite sur PyTorch, tandis que TensorFlow GNN fournit une fonctionnalité similaire pour TensorFlow. La Deep Graph Library (DGL) est indépendante du cadre, supportant plusieurs backends. jraph est conçu pour JAX, et GraphNeuralNetworks.jl et GeometricFlux.jl servent l'écosystème Julia. Ces bibliothèques offrent des couches préconstruites, des opérations de regroupement et des utilitaires pour gérer les données de graphes, accélérant le développement et l'expérimentation.
Défis et orientations futures
Malgré leur succès, les GNN font face à plusieurs défis. La limitation de puissance expressive par rapport au test de Weisfeiler-Leman restreint leur capacité à distinguer certaines structures de graphes. L'évolutivité vers de grands graphes est un autre problème, car le passage de messages peut être intensif en calcul. La recherche se poursuit sur des architectures plus expressives, telles que celles utilisant des caractéristiques d'ordre supérieur ou un passage de messages augmenté. De plus, la compréhension théorique de la généralisation et de la robustesse des GNN est un domaine d'étude actif. En 2022, le domaine évolue rapidement, avec de nouvelles architectures et applications émergeant régulièrement.