Les réseaux de neurones pour graphes (GNN) sont une classe de réseaux de neurones artificiels conçus pour fonctionner sur des données structurées en graphes, où les entrées sont constituées de nœuds (sommets) et d'arêtes (connexions) qui peuvent manquer d'un ordre canonique. Contrairement aux réseaux de neurones standard qui supposent des entrées ordonnées et de taille fixe, les GNN sont conçus pour traiter des graphes de tailles et de topologies variées, ce qui les rend adaptés à des domaines tels que la chimie moléculaire, l'analyse des réseaux sociaux et l'optimisation combinatoire. L'innovation centrale des GNN réside dans leur utilisation du passage de messages par paires, où chaque nœud met à jour itérativement sa représentation en agrégeant les informations de ses voisins, permettant au réseau de capturer des motifs structurels locaux et des dépendances.
Les GNN sont généralement conçus pour être équivariants par permutation, ce qui signifie que réordonner les nœuds du graphe d'entrée entraîne un réordonnancement correspondant des représentations de nœuds produites par le réseau. Pour les tâches de prédiction au niveau du graphe, comme la prédiction d'une propriété d'une molécule entière, les GNN utilisent une fonction de lecture invariante par permutation qui agrège les représentations des nœuds en une sortie de taille fixe unique, garantissant que le résultat n'est pas affecté par l'ordre des nœuds. Cette propriété est essentielle car les graphes n'ont pas d'ordre naturel des nœuds, et la sortie du réseau doit être cohérente quelle que soit la représentation du graphe.
Développement historique
Le concept des GNN est issu de travaux antérieurs sur les réseaux de neurones pour données structurées, avec des idées fondatrices remontant aux années 1990. Les approches précoces, telles que les réseaux de neurones récursifs appliqués aux graphes acycliques dirigés, ont posé les bases du traitement des structures de type graphe. Cependant, la formulation moderne des GNN, basée sur le passage de messages et l'équivariance par permutation, a gagné en importance dans les années 2010 avec l'essor de l'apprentissage profond. Des chercheurs d'institutions comme MIT CSAIL et Stanford AI Lab ont contribué au développement d'architectures capables de traiter des graphes arbitraires, conduisant à l'établissement des GNN comme un sous-domaine distinct au sein de l'apprentissage automatique.
À la fin des années 2010, les GNN étaient devenus un outil standard dans l'apprentissage profond, avec de nombreuses variantes proposées pour améliorer leur puissance expressive et leur évolutivité. L'article de position de 2022 « Weisfeiler and Leman Go Neural » et des travaux similaires ont formalisé la relation entre les GNN et les tests d'isomorphisme de graphes, clarifiant leurs limites théoriques et inspirant des recherches sur des architectures plus puissantes.
Architecture
L'architecture d'un GNN générique implémente plusieurs couches fondamentales qui travaillent ensemble pour traiter des entrées structurées en graphes. Ces couches comprennent des couches équivariantes par permutation, des couches de regroupement local et des couches de regroupement global, chacune servant un objectif distinct dans la transformation de la représentation du graphe.
Les couches équivariantes par permutation sont le cœur des GNN, implémentées via un passage de messages par paires entre les nœuds du graphe. Dans une couche de passage de messages, chaque nœud met à jour sa représentation en agrégeant les messages reçus de ses voisins immédiats. Ce processus augmente le champ réceptif du GNN d'un saut par couche, permettant au réseau d'incorporer des informations provenant de voisinages progressivement plus grands. L'opération de passage de messages peut être formellement exprimée comme une fonction qui prend en entrée les caractéristiques des nœuds, les caractéristiques des voisins et les caractéristiques des arêtes, et produit une représentation de nœud mise à jour.
Les couches de regroupement local réduisent le graphe par sous-échantillonnage, diminuant le nombre de nœuds tout en préservant les informations structurelles importantes. Cela est analogue aux couches de regroupement dans les réseaux de neurones convolutifs (CNN) et aide à augmenter le champ réceptif du GNN. Des exemples courants incluent le regroupement par k-plus proches voisins, le regroupement top-k et le regroupement par auto-attention, chacun sélectionnant un sous-ensemble de nœuds à conserver en fonction de différents critères.
Les couches de regroupement global, également appelées couches de lecture, fournissent une représentation de taille fixe de l'ensemble du graphe. Ces couches doivent être invariantes par permutation, ce qui signifie que toute permutation des nœuds et des arêtes du graphe ne modifie pas la sortie finale. Les opérations de somme, de moyenne et de maximum élément par élément sont des choix typiques pour le regroupement global, agrégeant les représentations des nœuds en un vecteur unique qui peut être utilisé pour des prédictions au niveau du graphe.
Couches de passage de messages
Les couches de passage de messages sont le composant déterminant des GNN, implémentant des transformations équivariantes par permutation à travers un processus connu sous le nom de réseaux de neurones à passage de messages (MPNN). Étant donné un graphe G = (V, E) avec un ensemble de nœuds V et un ensemble d'arêtes E, chaque nœud u dans V a des caractéristiques associées x_u, et chaque arête (u, v) dans E a des caractéristiques e_uv. Le voisinage d'un nœud u, noté N_u, est constitué de tous les nœuds v tels que (u, v) est une arête dans E.
Une couche MPNN met à jour la représentation de chaque nœud u en utilisant une fonction de passage de messages. La couche calcule des messages de chaque voisin v à u, où le message est une fonction des caractéristiques du nœud source, des caractéristiques du nœud cible et des caractéristiques de l'arête. Ces messages sont agrégés en utilisant une opération invariante par permutation, telle que la somme, la moyenne ou le maximum, puis combinés avec les caractéristiques propres du nœud à travers une fonction de mise à jour différentiable, généralement un réseau de neurones. Ce processus peut être répété pour plusieurs couches, permettant à l'information de se propager à travers le graphe.
La conception des fonctions de passage de messages varie selon les architectures GNN. Certaines utilisent de simples transformations linéaires, tandis que d'autres emploient des mécanismes d'attention plus complexes ou des unités récurrentes à portes. Le choix de l'opération d'agrégation affecte également la puissance expressive du réseau et sa capacité à capturer différents types d'informations structurelles.
Puissance expressive et limites
Les GNN à passage de messages standard sont au plus aussi expressifs que le test d'isomorphisme de graphes de Weisfeiler-Lehman, un algorithme classique pour déterminer si deux graphes sont isomorphes. Cela signifie qu'il existe des structures de graphes distinctes qui ne peuvent pas être distinguées par les GNN standard, car ils peuvent produire des représentations identiques pour des graphes non isomorphes. Cette limitation découle de la nature locale du passage de messages, qui repose sur l'agrégation d'informations provenant des voisins immédiats et peut échouer à capturer des motifs structurels globaux.
Pour surmonter ces limitations, les chercheurs ont proposé des GNN plus puissants qui opèrent sur des géométries de dimensions supérieures, telles que des complexes simpliciaux ou des hypergraphes, qui peuvent encoder des interactions d'ordre supérieur au-delà des arêtes par paires. En 2022, la question de savoir si les futures architectures surmonteront complètement le primitif de passage de messages reste une question de recherche ouverte, avec des travaux en cours explorant des paradigmes alternatifs tels que les transformeurs de graphes et les réseaux de neurones équivariants.
Applications
Les GNN ont trouvé des applications dans un large éventail de domaines, tirant parti de leur capacité à traiter des données structurées en graphes. En biologie moléculaire et en chimie, les molécules sont représentées comme des graphes avec des nœuds pour les atomes et des arêtes pour les liaisons chimiques, incluant souvent des propriétés chimiques connues comme caractéristiques. Les tâches au niveau du graphe incluent la prédiction de l'efficacité d'une molécule pour une application médicale spécifique, comme l'élimination de la bactérie E. coli, ou l'estimation de propriétés physiques et chimiques telles que la solubilité et la toxicité. Cela fait des GNN des outils précieux dans la conception de médicaments et la science des matériaux.
En traitement du langage naturel, les GNN peuvent être appliqués aux arbres de dépendances syntaxiques ou aux graphes de rôles sémantiques, capturant les relations entre les mots d'une phrase. Ils sont également utilisés dans l'analyse des réseaux sociaux pour modéliser les interactions entre utilisateurs, détecter des communautés et prédire des liens. Les réseaux de citations, où les nœuds représentent des articles et les arêtes des citations, sont une autre application courante, permettant des tâches telles que la classification et la recommandation d'articles.
Les GNN sont également pertinents en physique, où ils peuvent modéliser des interactions entre particules ou simuler des systèmes dynamiques, et pour des problèmes d'optimisation combinatoire NP-difficiles, où ils peuvent apprendre des heuristiques pour des tâches comme la coloration de graphes ou les problèmes du voyageur de commerce. La polyvalence des GNN a conduit à leur adoption tant dans la recherche académique que dans les applications industrielles.
Relation avec d'autres architectures de réseaux de neurones
Dans le contexte plus large de l'apprentissage profond géométrique, certaines architectures existantes de réseaux de neurones peuvent être interprétées comme des GNN appliqués à des graphes définis de manière appropriée. Une couche de réseau de neurones convolutif (CNN), couramment utilisée 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 uniquement les pixels adjacents. Cette perspective met en évidence les principes partagés de connectivité locale et d'agrégation de caractéristiques entre les CNN et les GNN.
De même, une couche de transformeur, largement utilisée dans le traitement du langage naturel et les grands modèles de langage, peut être considérée comme un GNN appliqué à des graphes complets dont les nœuds sont des mots ou des jetons dans un passage de texte. Dans cette interprétation, le mécanisme d'attention dans les transformeurs agit comme une forme de passage de messages, où chaque jeton agrège des informations de tous les autres jetons. Cette connexion a inspiré des recherches visant à unifier ces architectures et à appliquer des idées issues des GNN pour améliorer les modèles basés sur les transformeurs.
Bibliothèques logicielles et outils
Plusieurs bibliothèques open source ont été développées pour faciliter l'implémentation et le déploiement des GNN. PyTorch Geometric, construit sur le framework PyTorch, fournit un ensemble complet d'outils pour le traitement des données de graphes et les couches de passage de messages. TensorFlow GNN offre des fonctionnalités similaires dans l'écosystème TensorFlow. La Deep Graph Library (DGL) est une bibliothèque indépendante du framework qui prend en charge plusieurs backends, y compris PyTorch, TensorFlow et Apache MXNet. Pour les utilisateurs de Google JAX, jraph fournit une bibliothèque légère pour les réseaux de neurones pour graphes. Dans le langage de programmation Julia, GraphNeuralNetworks.jl et GeometricFlux.jl offrent des implémentations GNN construites sur le framework d'apprentissage automatique Flux.
Ces bibliothèques ont abaissé la barrière à l'entrée pour les chercheurs et les praticiens, permettant un prototypage rapide et l'expérimentation avec diverses architectures GNN. Elles incluent des implémentations de couches de passage de messages standard, des opérations de regroupement et des utilitaires pour charger et traiter des ensembles de données de graphes, rendant les GNN accessibles à un large public.
Orientations futures
La recherche sur les GNN continue d'évoluer, avec des domaines d'investigation actifs incluant l'amélioration de la puissance expressive, l'évolutivité à de grands graphes et la robustesse aux données bruitées ou incomplètes. Le développement de transformeurs de graphes, qui combinent des mécanismes d'attention avec la structure du graphe, représente une direction prometteuse pour capturer des dépendances à longue portée. De plus, il y a un intérêt croissant pour l'application des GNN aux graphes dynamiques, où les nœuds et les arêtes changent au fil du temps, et aux graphes hétérogènes avec plusieurs types de nœuds et d'arêtes.
Au début des années 2020, les GNN sont devenus un composant standard de la boîte à outils de l'apprentissage automatique, avec des contributions continues des institutions académiques et des laboratoires de recherche industriels. La compréhension théorique de leurs capacités et de leurs limites continue de s'approfondir, guidant la conception d'architectures de nouvelle génération capables de résoudre des problèmes de plus en plus complexes basés sur des graphes.