Skip to content
Retour aux résultats

Réseau neuronal à graphes — GCN / GAT / GraphSAGE

Année
2017–2018 (major variants)
Type
Deep learning on graph-structured data

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

Un réseau neuronal à graphes (GNN) est une architecture d'apprentissage profond qui opère directement sur des données structurées en graphes en combinant les caractéristiques des nœuds avec des informations structurelles par passage itératif de messages de voisinage.

Les trois variantes canoniques — le réseau neuronal convolutionnel à graphes (GCN) introduit par Kipf et Welling en 2017, le réseau neuronal à attention sur graphes (GAT) introduit par Veličković et al. en 2018, et GraphSAGE — diffèrent dans la manière dont ils agrègent les informations des voisins : le GCN applique une convolution spectrale sur l'ensemble de l'adjacence, le GAT pondère les voisins par des scores d'attention appris, et GraphSAGE échantillonne et agrège des voisinages locaux de manière inductive, permettant la généralisation à des nœuds non vus.

L’intuition derrière la méthode

Considérez chaque nœud d'un graphe comme une personne dans un réseau social. Cette personne a son propre profil (caractéristiques), mais les personnes qu'elle connaît en disent aussi long sur elle. Un GNN permet à chaque nœud de collecter de manière répétée des messages de ses voisins, de mélanger ces messages avec ses propres informations et de mettre à jour sa représentation — couche par couche. Après quelques tours de cet échange de type « potins », l'incorporation de chaque nœud reflète non seulement lui-même, mais aussi le sous-graphe local qui l'entoure. Le GCN le fait avec une moyenne symétrique fixe des voisins ; le GAT décide quels voisins sont les plus dignes de confiance en apprenant des poids d'attention ; GraphSAGE échantillonne un sous-ensemble fixe de voisins et apprend une fonction d'agrégation qui peut être appliquée à des nœuds qu'il n'a jamais vus auparavant.

Histoire

Les fondements de l'application des réseaux neuronaux aux graphes ont été posés par Scarselli et al. (2009), mais l'ère moderne des GNN a commencé avec le réseau neuronal convolutionnel à graphes (2017) de Kipf et Welling, qui a simplifié la convolution spectrale de graphes en une approximation efficace du premier ordre utilisant une multiplication d'adjacence normalisée symétrique. Un an plus tard, Veličković et al. (2018) ont introduit les réseaux neuronaux à attention sur graphes, remplaçant la moyenne fixe du GCN par des coefficients d'attention apprenables sur chaque arête — permettant au modèle de pondérer sélectivement les voisins. Simultanément, Hamilton et al. (2017) ont proposé GraphSAGE, un cadre inductif qui échantillonne des voisinages de taille fixe et apprend des fonctions d'agrégation transférables à des nœuds non vus, rendant les GNN pratiques pour les graphes grands et dynamiques. Ces trois articles ont établi le paradigme du passage de messages qui sous-tend maintenant la majorité de la recherche sur les GNN.

Quand l’utiliser

Utilisez un GNN lorsque vos données sont naturellement structurées en graphes — réseaux sociaux, réseaux de citations, graphes moléculaires, graphes de connaissances, ou tout environnement où les relations entre les entités portent un signal prédictif. Vous avez besoin d'une matrice de caractéristiques de nœuds et d'une liste d'arêtes. Un minimum d'environ 50 nœuds est requis pour un entraînement significatif. Les GNN sont applicables à la classification de nœuds (prédiction d'une étiquette pour chaque nœud), à la prédiction de liens (inférence d'arêtes manquantes) et à la classification de graphes (attribution d'une étiquette à un graphe entier). L'hypothèse d'homophilie — les nœuds connectés ont tendance à partager la même étiquette — est implicitement exploitée par le GCN et le GAT standard ; si votre graphe est hétérophile, considérez des architectures conçues pour ce contexte. Pour les grands graphes, l'entraînement par lots complet est prohibitif en mémoire et l'échantillonnage de voisinage par mini-lots (style GraphSAGE) est nécessaire. Si votre graphe a moins de 20 nœuds, les métriques de centralité traditionnelles sont un choix plus approprié.

Limites et points d’attention

  • Sur-lissage : l'empilement de nombreuses couches GNN pousse toutes les représentations de nœuds vers une valeur commune, limitant la profondeur effective à environ 2 à 4 couches en pratique.
  • Scalabilité : le GCN et le GAT en mode lot complet nécessitent de conserver la matrice d'adjacence et la matrice de caractéristiques entières en mémoire, ce qui est infaisable pour de très grands graphes sans échantillonnage ou partitionnement.
  • L'hypothèse d'homophilie intégrée à l'agrégation standard dégrade les performances sur les graphes hétérophiles où les voisins ont tendance à avoir des étiquettes différentes.
  • Une taille d'échantillon minimale d'environ 50 nœuds est requise ; moins de nœuds laissent au modèle un signal insuffisant pour apprendre des représentations significatives.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Tire parti conjointement des caractéristiques des nœuds et de la topologie du graphe, surpassant les méthodes qui utilisent l'un ou l'autre séparément.
  • Le mécanisme d'attention du GAT fournit des scores d'importance par arête, ajoutant de l'interprétabilité à l'agrégation.
  • GraphSAGE est inductif et peut se généraliser à des nœuds et des graphes non vus pendant l'entraînement, permettant le déploiement sur des réseaux en croissance.
  • Un cadre unifié de passage de messages couvre la classification de nœuds, la prédiction de liens et la classification de graphes avec la même architecture de base.

Applications

  • Classification de nœuds dans les réseaux de citations — prédiction du sujet d'un article basée sur son contenu et ses liens de citation.
  • Découverte de médicaments — prédiction des propriétés moléculaires en traitant les atomes comme des nœuds et les liaisons chimiques comme des arêtes.
  • Systèmes de recommandation — modélisation des utilisateurs et des articles comme un graphe biparti et prédiction des interactions utilisateur-article via la prédiction de liens.
  • Détection de fraude dans les réseaux de transactions financières — identification des nœuds anormaux en fonction de leurs caractéristiques et de la structure de leur voisinage.
  • Complétion de graphes de connaissances — inférence des relations manquantes entre les entités dans des bases de connaissances à grande échelle.

Comment ça marche

Comment ça marche

1

Le graphe est défini par une matrice de caractéristiques de nœuds X (une ligne par nœud, une colonne par attribut) et une liste d'arêtes (ou matrice d'adjacence) A. Les arêtes non dirigées sont standard pour GCN et GAT ; GraphSAGE prend également en charge les graphes dirigés. Des auto-boucles sont généralement ajoutées à A afin que chaque nœud soit inclus dans sa propre agrégation.

2

Les attributs bruts des nœuds sont normalisés et, si nécessaire, intégrés dans un espace vectoriel continu. Les attributs des arêtes, s'ils sont présents, peuvent être incorporés comme signaux supplémentaires. Le résultat est une matrice de caractéristiques dense que chaque couche GNN transformera.

3

Chaque couche GNN calcule une nouvelle représentation de nœud en agrégeant les caractéristiques des voisins d'un nœud et en les combinant avec les caractéristiques propres du nœud via une matrice de poids apprenable et une activation non linéaire. Le GCN applique une multiplication d'adjacence normalisée (convolution spectrale) ; le GAT calcule des coefficients d'attention softmax pour chaque arête afin que les voisins influents contribuent davantage ; GraphSAGE échantillonne aléatoirement un voisinage de taille fixe et applique un agrégateur différentiable (moyenne, LSTM ou pooling). L'empilement de L couches permet à l'information de circuler à L sauts, mais l'empilement de trop de couches provoque un sur-lissage, où toutes les représentations de nœuds convergent vers la même valeur.

4

Les représentations finales des nœuds sont transmises à une tête spécifique à la tâche. Pour la classification de nœuds, une couche softmax attribue des probabilités de classe à chaque nœud. Pour la prédiction de liens, un produit scalaire ou un MLP évalue la probabilité d'une arête entre deux représentations de nœuds. Pour la classification de graphes, un pooling global (somme, moyenne ou hiérarchique) agrège toutes les représentations de nœuds en un seul vecteur au niveau du graphe avant la couche de classification.

5

Les performances du modèle sont mesurées sur un ensemble de test réservé à l'aide de métriques appropriées à la tâche : précision ou F1 pour la classification de nœuds et de graphes, AUC-ROC pour la prédiction de liens. Étant donné que les ensembles de données de graphes sont souvent de taille limitée, l'évaluation transductive (masques d'entraînement/validation/test sur le même graphe) ou les divisions inductives (sous-graphes disjoints) doivent correspondre au scénario de déploiement.

Pièges courants

  • L'ajout de trop de couches GNN provoque un sur-lissage : toutes les représentations de nœuds convergent et le modèle perd son pouvoir discriminant. Gardez le nombre de couches à 2-4 et surveillez la variance des représentations.
  • L'entraînement sur le graphe complet sans mini-lots est prohibitif en mémoire pour les grands réseaux ; utilisez l'échantillonnage de voisinage de type GraphSAGE ou le partitionnement de graphe pour les graphes de plus de quelques milliers de nœuds.
  • Appliquer un GCN entraîné de manière transductive directement à de nouveaux nœuds non vus lors de l'inférence est incorrect ; utilisez une méthode inductive comme GraphSAGE si votre déploiement nécessite une généralisation à de nouveaux nœuds.
  • Ignorer l'hypothèse d'homophilie sur les graphes hétérophiles produit de mauvais résultats ; inspectez le coefficient d'assortiment du graphe avant de choisir une variante GNN standard.
  • Avec moins de 20 nœuds, l'entraînement GNN produit des représentations peu fiables ; préférez l'analyse conventionnelle de centralité du réseau dans ce régime.

Questions fréquentes

Quelle variante de GNN devrais-je choisir pour commencer — GCN, GAT, ou GraphSAGE ?

Le GCN est la base la plus simple et fonctionne bien sur les graphes homophiles de petite à moyenne taille où tous les nœuds sont connus au moment de l'entraînement. Le GAT est préférable lorsque l'importance des voisins varie et que vous souhaitez des poids d'attention interprétables. GraphSAGE est le bon choix lorsque vous avez besoin de généraliser à des nœuds non vus pendant l'entraînement ou lorsque le graphe est trop grand pour un traitement par lots complet.

Qu'est-ce que le sur-lissage et comment l'éviter ?

Le sur-lissage se produit lorsque de nombreuses couches GNN font converger toutes les représentations de nœuds vers la même valeur, éliminant ainsi les informations discriminantes. En pratique, 2 à 4 couches sont généralement optimales. Des techniques telles que les connexions résiduelles, les réseaux de connaissances sautées (jumping knowledge networks) et DropEdge peuvent aider si des architectures plus profondes sont nécessaires.

Les GNN nécessitent-ils des données étiquetées pour tous les nœuds ?

Non. Le GCN et le GAT sont couramment utilisés dans des contextes semi-supervisés où seule une petite fraction des nœuds porte des étiquettes ; la structure du graphe propage l'information des nœuds étiquetés vers les nœuds non étiquetés. GraphSAGE peut également être entraîné de manière entièrement supervisée ou non supervisée en fonction de la tâche.

Quelle doit être la taille du graphe ?

Un minimum d'environ 50 nœuds est nécessaire pour un entraînement GNN significatif. Avec moins de 20 nœuds, le modèle ne peut pas apprendre de représentations fiables et une analyse traditionnelle basée sur la centralité est plus appropriée. Pour les graphes avec des millions de nœuds, l'échantillonnage de voisinage par mini-lots (comme dans GraphSAGE) ou les méthodes de partitionnement de graphe sont nécessaires pour maintenir l'utilisation de la mémoire tractable.

Méthodes associées

Sources

  1. Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).

    Ouvrir la référence DOI
    Copié.
  2. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR).

    Ouvrir la référence DOI
    Copié.
  3. Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.

    Ouvrir la référence DOI
    Copié.