Les réseaux de neurones graphiques (GNN) sont une classe de réseaux de neurones artificiels conçus pour des tâches dont les entrées sont des graphes, tels que les structures moléculaires, les réseaux sociaux ou les réseaux de citations. Contrairement aux réseaux de neurones standard qui supposent des entrées de taille fixe et ordonnées, les GNN opèrent sur des graphes de taille et de topologie arbitraires. Étant donné que les graphes n'ont généralement pas d'ordre canonique des nœuds, les architectures GNN sont typiquement conçues pour être équivariantes par permutation : réordonner les nœuds d'entrée réordonne 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, garantissant que 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 mettent à jour itérativement leurs représentations en échangeant des informations avec leurs voisins. Cela permet au réseau de capturer à la fois des informations structurelles locales et globales. Une application importante est la conception de médicaments moléculaires, où les molécules sont représentées comme des graphes avec des atomes comme nœuds et des liaisons comme arêtes, incluant souvent des propriétés chimiques comme caractéristiques. Les tâches au niveau du graphe incluent la prédiction de l'efficacité d'une molécule pour un usage médical spécifique, comme l'élimination de la bactérie E. coli. Les GNN ont également été appliqués dans le traitement du langage naturel, l'analyse des réseaux sociaux, la physique et l'optimisation combinatoire NP-difficile.
Développement Historique
Le concept d'appliquer des réseaux de neurones à des données structurées en graphes a émergé à la fin des années 1990 et au début des années 2000. Les travaux précoces de chercheurs tels que Franco Scarselli et ses collègues ont introduit des réseaux de neurones récursifs pour les graphes, qui traitaient les structures de graphes de manière récurrente. À peu près à la même époque, des approches convolutionnelles ont été développées, conduisant aux premiers réseaux convolutionnels de graphes. Ces architectures précoces ont posé les fondations des GNN modernes, qui ont évolué grâce aux contributions de nombreux groupes de recherche académiques et industriels.
Une étape importante a été l'introduction des réseaux de neurones à passage de messages (MPNN) en 2017, qui ont unifié de nombreuses variantes existantes de GNN sous un cadre commun. Depuis lors, de nombreuses architectures ont été proposées, chacune implémentant différentes variantes du passage de messages. 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, en inventant le terme "passage de messages augmenté" pour de telles approches.
Architecture
L'architecture d'un GNN générique comprend typiquement trois types fondamentaux de couches : les couches équivariantes par permutation, les couches de regroupement local et les couches de regroupement global. Les couches équivariantes par permutation, souvent implémentées via le passage de messages, mettent à jour les représentations des nœuds en agrégeant les messages des voisins immédiats. Chaque telle couche augmente le champ réceptif d'un saut, permettant aux nœuds d'incorporer des informations provenant de parties plus éloignées du graphe.
Les couches de regroupement local réduisent le graphe par sous-échantillonnage, similaire au regroupement dans les réseaux de neurones convolutionnels pour les images. Des exemples incluent le regroupement par k plus proches voisins, le regroupement top-k et le regroupement par auto-attention. Les couches de regroupement global, également connues sous le nom de couches de lecture, produisent une représentation de taille fixe de l'ensemble du graphe et doivent être invariantes par permutation. Les fonctions de lecture courantes incluent la somme élément par élément, la moyenne ou le maximum.
Les GNN standard à passage de messages sont au plus aussi expressifs que le test d'isomorphisme de graphes de Weisfeiler-Lehman, 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 dimensions supérieures, telles que les complexes simpliciaux, ont été proposés. En 2022, la question de 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 le cœur de la plupart des GNN. Formellement, elles peuvent être exprimées comme des réseaux de neurones à passage de messages (MPNN). Étant donné un graphe G = (V, E) avec des caractéristiques de nœuds x_u et des caractéristiques d'arêtes e_uv, une couche MPNN met à jour la représentation de chaque nœud h_u en utilisant une fonction différentiable φ et une fonction de message ψ :
h_u = φ(x_u, ⊕_{v∈N_u} ψ(x_u, x_v, e_uv))
Ici, N_u désigne le voisinage du nœud u, et ⊕ est une fonction d'agrégation invariante par permutation telle que la somme, la moyenne ou le maximum. La fonction de message ψ calcule un message à partir de chaque voisin, et l'agrégation combine ces messages. La fonction de mise à jour φ combine ensuite les caractéristiques propres du nœud avec les messages agrégés pour produire la nouvelle représentation.
Différentes architectures GNN varient dans la manière dont elles définissent ψ et φ. Par exemple, les réseaux convolutionnels de graphes (GCN) utilisent une somme normalisée simple des caractéristiques des voisins, tandis que les réseaux d'attention de graphes (GAT) utilisent des mécanismes d'attention pour pondérer les contributions des voisins. Ces variations permettent aux GNN de capturer différents aspects de la structure du graphe.
Apprentissage Géométrique Profond
Les GNN font partie du domaine plus large de l'apprentissage géométrique profond, qui vise à généraliser les réseaux de neurones à des domaines non euclidiens. Dans ce contexte, de nombreuses 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 vue comme un GNN appliqué à des graphes où les nœuds sont des pixels et les arêtes connectent des pixels adjacents. De même, une couche de Transformer (architecture) dans le 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 a conduit à une pollinisation croisée entre les domaines. Des techniques développées pour les GNN, telles que les mécanismes d'attention, ont influencé les architectures de transformeurs, et des idées issues des transformeurs ont informé la conception des GNN. La vision unifiée de l'apprentissage géométrique profond a été articulée par des chercheurs tels que Michael Bronstein et Joan Bruna, entre autres.
Applications
Les GNN ont trouvé des applications dans une large gamme de domaines. En biologie moléculaire et en chimie, ils sont utilisés pour la découverte de médicaments, la prédiction de fonctions protéiques et la conception de matériaux. Par exemple, les GNN peuvent prédire des propriétés moléculaires ou générer de nouvelles molécules avec des caractéristiques souhaitées. Dans les réseaux sociaux, les GNN alimentent des systèmes de recommandation, la détection de communautés et la prédiction de liens. Les réseaux de citations, où les articles sont des nœuds et les citations sont des arêtes, bénéficient des GNN pour la classification de sujets et la prédiction d'impact.
En physique, les GNN modélisent les interactions de particules et simulent des systèmes dynamiques. Ils sont également appliqués à des problèmes d'optimisation combinatoire NP-difficiles, tels que le problème du voyageur de commerce ou la coloration de graphes, où ils peuvent apprendre des heuristiques. Dans le traitement du langage naturel, les GNN sont utilisés pour l'analyse sémantique, l'extraction de relations et le raisonnement sur les graphes de connaissances. De plus, les GNN ont été employés en vision par ordinateur pour la génération de graphes de scènes et le traitement de nuages de points.
Bibliothèques Logicielles
Plusieurs bibliothèques open-source implémentent les GNN, les rendant accessibles aux chercheurs et aux praticiens. PyTorch Geometric, construit sur PyTorch, est l'une des bibliothèques les plus largement utilisées, offrant une riche collection de couches GNN et de jeux de données. TensorFlow GNN fournit des fonctionnalités similaires pour l'écosystème TensorFlow. La Deep Graph Library (DGL) est indépendante du cadre, supportant à la fois PyTorch et TensorFlow. Pour les utilisateurs de JAX, jraph offre des primitives GNN. Dans le langage Julia, GraphNeuralNetworks.jl et GeometricFlux.jl fournissent des implémentations GNN.
Ces bibliothèques ont accéléré la recherche et le déploiement des GNN en fournissant des implémentations efficaces des opérations de passage de messages, de regroupement et de lecture. Elles incluent également des utilitaires pour gérer les données de graphes, tels que le regroupement par lots et le chargement de données, qui sont essentiels pour l'entraînement sur de grands graphes.
Défis et Directions Futures
Malgré leur succès, les GNN font face à plusieurs défis. Un problème majeur est l'évolutivité, car le passage de messages sur de grands graphes peut être coûteux en calcul. Des techniques telles que l'échantillonnage de graphes et l'entraînement par mini-lots ont été développées pour y remédier. Un autre défi est le sur-lissage, où des passages de messages répétés rendent les représentations des nœuds indiscernables, limitant la profondeur des GNN.
L'expressivité est un autre domaine de recherche actif. Étant donné que les GNN standard sont limités par le test de Weisfeiler-Lehman, les chercheurs ont exploré des GNN d'ordre supérieur, des transformeurs de graphes et des architectures opérant sur des complexes simpliciaux ou des hypergraphes. Ces approches visent à capturer des informations structurelles plus complexes. En 2022, la question de savoir si le passage de messages restera le paradigme dominant est ouverte, avec des travaux en cours sur le passage de messages augmenté et des primitives alternatives.
L'interprétabilité et la robustesse sont également importantes. Comprendre ce que les GNN apprennent et les rendre robustes aux attaques adverses sur les graphes sont des sujets de recherche actifs. Alors que les GNN sont de plus en plus déployés dans des domaines à enjeux élevés comme la santé et les systèmes autonomes, relever ces défis sera crucial pour leur adoption plus large.