Qu’est-ce qu’un GNN (réseau neuronal de graphes) ?

Les réseaux neuronaux de graphes (GNN) sont une architecture de réseau neuronal profond populaire dans les applications pratiques et la recherche de pointe en matière de machine learning. Ils utilisent un modèle de réseau de neurones pour représenter des données sur les entités et leurs relations. Ils servent au data mining dans le monde réel, à la compréhension des réseaux sociaux, aux graphes de connaissances, aux systèmes de recommandation et à la bio-informatique.

Le développement des GNN s’est inspiré des algorithmes d’apprentissage profond tels que les réseaux de neurones convolutifs (CNN) et les réseaux de neurones récurrents (RNN), mais ils ont plusieurs différences clés. Les CNN sont conçus pour les données ayant une structure de type grille, comme les pixels d’une image. Chaque pixel peut être connecté à 8 autres pixels au maximum. En revanche, les RNN sont adaptés aux structures de séquence où chaque élément peut être connecté à deux autres éléments au maximum, comme une chaîne de mots dans un texte. Dans les données structurées en graphes, tout élément peut avoir une ou plusieurs connexions, et il peut n’y avoir aucune cohérence entre les nombres de connexions pour un élément spécifique.

Les réseaux neuronaux de graphes sont une mise en œuvre de l’apprentissage profond géométrique¹, qui est classé en quatre catégories fondamentales :

L’apprentissage sur graphe, qui apprend les données de type graphe.

L’apprentissage sur grille, qui apprend sur les images de type données et d’autres types de données qui peuvent être décrites par des grilles.

L’apprentissage sur groupe, qui apprend comment les informations se rapportent à un groupe parent. C’est un outil puissant lorsque les données sont acquises à partir d’un groupe comme une sphère, par exemple : des données géologiques provenant de différentes sources sur la Terre.

L’apprentissage sur maillage, qui apprend comment les informations sont réparties sur un maillage irrégulier, comme l’analyse et la prévision des éléments du modèle 3D d’un objet.

Les GNN constituent un domaine de recherche actif dans l’intelligence artificielle, mais ils sont bien pris en charge par des bibliothèques et des outils créés dans des langages tels que Python et des cadres des exigences tels que TensorFlow et PyTorch.

Un ensemble d’objets et les connexions entre eux peuvent être exprimés sous forme de graphe. Les chercheurs en informatique ont développé des réseaux neuronaux pour opérer sur des structures de données de type graphe.

Un graphe représente les relations, appelées « arêtes », entre une collection d’entités, appelées « nœuds ». Mathématiquement, un graphe G est défini comme un tuple d’un ensemble de nœuds et de sommets V, et d’un ensemble d’arêtes et de liens. E:G = (V, E). Chaque arête est une paire de deux sommets et représente une connexion entre eux.

Pour décrire davantage chaque nœud, chaque arête ou l’ensemble du graphe, nous pouvons stocker des informations dans chacun de ces éléments du graphe.

Les graphes peuvent être décrits de façon plus précise en attribuant une direction à chaque arête. Un graphe est décrit comme étant orienté ou non orienté. Un graphe non orienté représente une relation, qui est bidirectionnelle. Si Rosa a un frère ou une sœur, Juan, alors Juan a également un frère ou une sœur, Rosa La relation entre Rosa et ses frères/sœurs n’a aucune direction, elle les relie simplement. Un graphe orienté représente des relations directionnelles. Si Rosa a un frère ou une sœur aîné(e), Juan, alors la relation « aîné(e) » n’est orientée que dans un seul sens : de Juan vers Rosa. Juan n’a pas d’« aîné(e) ».

L’un des moyens de visualiser la connectivité d’un graphe consiste à utiliser sa matrice d’adjacence. Il s’agit d’une représentation matricielle des sommets du graphe, qui peut représenter à la fois des graphes non orientés et des graphes orientés.

La matrice d’adjacence d’un graphe orienté indique tous les sommets et la direction de l’arête qui les crée. Par exemple, le nœud 0 dans le graphe orienté se connecte au nœud 1, mais l’inverse n’est pas vrai en raison de la direction de la connexion. Dans la matrice d’adjacence, [ligne 0, colonne 1] contient une valeur, tandis que [ligne 1, colonne 0], n’en contient pas.

Les représentations de graphes doivent avoir une invariance de permutation, ce qui signifie que les représentations du graphe doivent produire les mêmes résultats si la structure du graphe est la même mais que l’ordre des nœuds est différent. Cette approche garantit que la représentation du graphe a les mêmes propriétés que le graphe lui-même.

Les GNN adoptent généralement une architecture «  raph-in, graph-out ». Cela signifie que ces types de modèles acceptent un graphe en entrée, avec des informations chargées dans ses nœuds, ses arêtes et son contexte global. Les modèles transforment progressivement ces plongements sans modifier la connectivité de l’entrée. Les plongements représentent les nœuds comme des plongements de nœuds et les sommets comme des plongements de sommets. Ces plongements permettent au modèle de connaître les types de nœuds et leur emplacement dans le graphe, ainsi que les types et les emplacements des arêtes.

En règle générale, l’entraînement d’un réseau neuronal s’effectue en mettant à jour les paramètres du réseau à l’aide de gradients calculés sur un sous-ensemble aléatoire des données d’entraînement. Pour entraîner les réseaux de graphes, les réseaux neuronaux créent des sous-graphes qui préservent les propriétés essentielles du grand graphe parent.

Les GNN utilisent un mécanisme de transmission de messages pour agréger les informations des nœuds voisins, ce qui leur permet de capturer les relations complexes dans les graphes. Un défi dans la modélisation des données structurées en graphes est de capturer les interactions entre les nœuds. La transmission neuronale de messages résout ce problème en fournissant un cadre pour la modélisation des dépendances et des interactions dans les données du graphe. Les nœuds échangent des informations avec leurs nœuds voisins et les agrègent pour mettre à jour leurs propres représentations. Ce processus de transmission de messages est similaire aux nœuds d’un graphe qui échangent des messages ou des signaux.

Les GNN permettent plusieurs types d’analyse, chacun fournissant des informations sur différents éléments de données des graphes.

Tâches au niveau du graphe

Dans une tâche de niveau graphe, le GNN prédit une propriété d’un graphe entier. Pour une molécule représentée sous forme de graphe, vous pourriez vouloir prédire si elle se liera à un récepteur associé à une maladie. Pour les réseaux sociaux, vous pourriez vouloir prédire s’ils sont susceptibles d’être associés à une institution particulière, comme une université ou une école supérieure. Ce type de reconnaissance de schémas peut être considéré comme une forme de classification de graphes, car il classifie le graphe entier.

Tâches au niveau du nœud

Les tâches au niveau du nœud concernent la prédiction de l’identité ou du rôle de chaque nœud dans un graphe. Par exemple, un problème de classification des nœuds dans un jeu de données de réseaux sociaux peut consister à prédire si un utilisateur est susceptible d’avoir un intérêt spécifique en fonction de la connexion de son réseau d’amis. Le fait d’avoir des amis qui ne partagent qu’un intérêt pour le golf, mais sans autre intérêt en commun est une bonne indication qu’un nouvel ami sera également susceptible d’apprécier le golf. Ces types de fonctionnalités de nœud peuvent souvent être prédites avec un GNN.

Tâches au niveau de l’arête

Le dernier type de problème de prédiction dans les graphes est la prédiction d’arête, parfois appelée prédiction de lien.

Un exemple d’inférence au niveau de l’arête est la compréhension des scènes d’images. Après avoir identifié des objets dans une image, les modèles d’apprentissage profond peuvent également prédire la relation entre eux. Il s’agit d’une classification au niveau de l’arête, car les nœuds représentent les objets dans l’image et la prédiction indique lesquels de ces nœuds partagent une arête ou quelle est la valeur de cette arête. Si vous souhaitez découvrir des connexions entre les entités, vous pouvez considérer le graphe comme étant « entièrement connecté » et, en fonction de sa valeur prédite, tailler les arêtes pour obtenir un graphe clairsemé.

Réseaux convolutifs de graphes⁴ (GCN) : cette approche est destinée à l’apprentissage semi-supervisé basé sur une variante de réseaux convolutifs neuronaux qui peuvent apprendre et prédire à partir de données basées sur des graphes. Ces modèles s’adaptent linéairement en fonction du nombre d’arêtes dans les graphes, ce qui les rend appropriés pour les grands jeux de données. Les modèles apprennent également la structure locale du graphe et les caractéristiques des nœuds.

Auto-encodeurs de graphes² : ces variantes sont des modèles de réseaux de neurones qui peuvent être entraînés de bout en bout pour l’apprentissage non supervisé, le regroupement et la prédiction de liens sur les graphes. Ils utilisent généralement un GCN comme encodeur pour créer des plongement et disposent d’un décodeur qui reconstruit le graphe à partir de la représentation latente apprise.

Réseaux d’attention de graphes³ (GAT) : une architecture de réseaux de neurones qui fonctionne sur des données structurées en graphes. Les GAT tirent parti d’un mécanisme d’attention sous la forme de couches d’auto-attention pour combler les lacunes des méthodes antérieures basées sur les convolutions graphiques ou leurs approximations. En empilant les couches dans lesquelles les nœuds peuvent focaliser leur attention sur les caractéristiques de leur voisinage, un GAT permet (implicitement) de spécifier différents poids pour les différents nœuds d’un voisinage. Ceci est possible sans nécessiter d’opérations matricielles coûteuses telles que l’inversion ou sans dépendre de la connaissance préalable de la structure du graphe.

Représentation de graphes : l’apprentissage est un domaine de recherche qui étend les réseaux neuronaux de graphes comme moyen de trouver une représentation significative et potentiellement de faible dimension des nœuds à partir des relations complexes présentes dans un graphe. Un exemple de cette extension est GraphSage⁶, un projet de l’Université de Stanford, qui crée des représentations vectorielles à faible dimension pour les nœuds, ce qui le rend adapté pour travailler avec des données où les nœuds représentent des données de grande dimension.

Comme exemple de la façon dont un GNN peut être structuré, prenons l’exemple d’un réseau convolutif à graphe simple (GCN) pour classer un graphe entier. Le GCN le plus simple comporte trois couches :

Couche convolutive : cette couche effectue la convolution sur chaque nœud pour apprendre ses connexions.

Couche d’activation non linéaire : cette couche applique une fonction d’activation telle que ReLU à la sortie de la convolution.

Couche linéaire de sortie : cette couche finale additionne les sorties pour générer une prédiction finale.

Tout d’abord, une convolution est effectuée en utilisant chaque nœud dans le graphe de la couche de convolution. Cette couche convolutive utilise les informations de fonctionnalité des nœuds et les agrège, mettant ainsi à jour les poids associés à chaque nœud. Ensuite, une fonction d’activation non linéaire, telle que ReLU, est appliquée à la sortie de la couche de convolution. Pour obtenir une précision optimale, un réseau peut utiliser plusieurs convolutions et couches d’activation non linéaires empilées. Enfin, une couche linéaire de sortie est utilisée pour prédire la classe à laquelle un graphe est le plus susceptible d’appartenir.

Les GCN sont conceptuellement simples, adaptés aux graphes à grande échelle et faciles à programmer, mais présentent également plusieurs inconvénients majeurs. Tout d’abord, les GCN ne prennent pas en charge les fonctionnalités d’arête. Ils peuvent uniquement apprendre et prédire les fonctionnalités des nœuds ou les fonctionnalités globales des graphes. La notion de transmission de messages n’existe pas avec les GCN. Ce problème limite son utilisation aux seuls cas où toutes les informations requises sont présentes dans les nœuds plutôt que dans les arêtes.

En revanche, un réseau de neurones à transmission de messages (MPNN) permet des représentations d’arêtes.⁵ Le processus de transmission des messages est en gros le suivant. Chaque nœud du graphe reçoit une représentation vectorielle initiale qui agit comme les caractéristiques d’entrée initiales du nœud. À chaque itération du message passé, le nœud agrège les informations de ses nœuds voisins. Ces informations agrégées sont ensuite combinées avec le plongement actuel du nœud à l’aide d’une fonction de mise à jour. Les plongements mis à jour sont transmis à l’itération suivante de transmission des messages. Après plusieurs itérations adaptées pour représenter la complexité du graphe, les plongements finaux sont utilisées pour représenter chaque nœud dans le graphe. Enfin, les étapes d’agrégation, de mise à jour et d’itération sont effectuées par les réseaux de neurones pour apprendre des schémas complexes dans l’ensemble du graphe.

L’utilisation de la transmission des messages permet une classification plus sophistiquée des nœuds, la classification des arêtes et même la prédiction de l’endroit où les arêtes peuvent apparaître dans le graphe (appelée prédiction des liens).

Les GNN ont de nombreuses applications dans le traitement automatique du langage naturel (NLP). Par exemple, dans la classification des documents, les GNN peuvent être utilisés pour modéliser les relations entre les mots ou les phrases dans les documents. Cette fonctionnalité permet d’améliorer la classification des documents et la récupération des informations. Les GNN peuvent faciliter les tâches de réponse aux questions en représentant les relations entre les mots d’une question et les réponses des candidats dans un graphe de connaissances. Les GNN peuvent capturer des informations contextuelles et des dépendances de sentiments dans le texte, ce qui améliore ainsi l’analyse des sentiments dans les situations où il y a une grande ambiguïté ou des relations d’entités très spécifiques.

Ils ont également de nombreuses applications dans le domaine de la vision par ordinateur. Dans les tâches de segmentation d’image, les GNN peuvent être utilisés pour les tâches de segmentation d’image au niveau du pixel en modélisant les relations entre les pixels adjacents sous forme de graphe. Les GNN peuvent faciliter la détection d’objets en capturant des informations contextuelles et des relations entre eux dans les images. Dans les tâches de compréhension de scènes, les GNN sont utilisés pour comprendre des scènes complexes et générer des graphes de scènes qui représentent les relations spatiales entre les objets dans une image.

Les GNN sont également de puissants outils dans le domaine de la bio-informatique. Dans l’analyse des séquences génomiques, les GNN peuvent modéliser les relations entre les ingénieurs ou les séquences génétiques, ce qui facilite la prédiction de l’expression des générations et les tâches de classification des séquences. Dans la découverte de médicaments, les GNN peuvent être utilisés pour la prédiction de l’interaction médicament-cible et la prédiction des propriétés moléculaires, ce qui est essentiel dans la recherche pharmaceutique.