Introduction à l’apprentissage machine sur les graphes

'Graph-based Machine Learning Introduction'

Dans cet article de blog, nous couvrons les bases de l’apprentissage automatique sur les graphes.

Nous commençons par étudier ce que sont les graphes, pourquoi ils sont utilisés et comment les représenter au mieux. Nous abordons ensuite brièvement la manière dont les personnes apprennent sur les graphes, des méthodes pré-neuronales (exploration des caractéristiques du graphe en même temps) à ce qu’on appelle communément les réseaux neuronaux graphiques. Enfin, nous jetons un coup d’œil sur le monde des Transformers pour les graphes.

Graphes

Qu’est-ce qu’un graphe ?

Essentiellement, un graphe est une description d’éléments liés par des relations.

Les exemples de graphes incluent les réseaux sociaux (Twitter, Mastodon, tous les réseaux de citation reliant les articles et les auteurs), les molécules, les graphes de connaissances (comme les diagrammes UML, les encyclopédies et tous les sites web avec des hyperliens entre leurs pages), les phrases exprimées sous forme d’arbres syntaxiques, toutes les maillages 3D, et bien plus encore ! Il n’est donc pas exagéré de dire que les graphes sont partout.

Les éléments d’un graphe (ou réseau) sont appelés ses nœuds (ou sommets), et leurs connexions sont appelées ses arêtes (ou liens). Par exemple, dans un réseau social, les nœuds sont des utilisateurs et les arêtes sont leurs connexions ; dans une molécule, les nœuds sont des atomes et les arêtes sont leurs liaisons moléculaires.

Un graphe avec des nœuds typés ou des arêtes typées est appelé hétérogène (par exemple : les réseaux de citation avec des éléments pouvant être soit des articles, soit des auteurs ont des nœuds typés, et les diagrammes XML où les relations sont typées ont des arêtes typées). Il ne peut pas être représenté uniquement par sa topologie, il a besoin d’informations supplémentaires. Cet article se concentre sur les graphes homogènes.
Un graphe peut également être orienté (comme un réseau de suiveurs, où A suit B n’implique pas que B suit A) ou non orienté (comme une molécule, où la relation entre les atomes va dans les deux sens). Les arêtes peuvent relier différents nœuds ou un nœud à lui-même (auto-arêtes), mais tous les nœuds n’ont pas besoin d’être connectés.

Si vous souhaitez utiliser vos données, vous devez d’abord considérer leur meilleure caractérisation (homogène/hétérogène, orienté/non orienté, etc.).

À quoi servent les graphes ?

Examinons un panel de tâches possibles que nous pouvons effectuer sur les graphes.

Au niveau du graphe, les principales tâches sont :

la génération de graphes, utilisée dans la découverte de médicaments pour générer de nouvelles molécules plausibles,
l’évolution des graphes (en partant d’un graphe, prédire comment il évoluera avec le temps), utilisée en physique pour prédire l’évolution des systèmes,
la prédiction au niveau du graphe (catégorisation ou tâches de régression à partir de graphes), telle que la prédiction de la toxicité des molécules.

Au niveau des nœuds, il s’agit généralement de prédiction de propriétés des nœuds. Par exemple, Alphafold utilise la prédiction de propriétés des nœuds pour prédire les coordonnées 3D des atomes en fonction du graphe global de la molécule, et ainsi prédire comment les molécules se plient dans l’espace 3D, un problème complexe de biochimie.

Au niveau des arêtes, il s’agit soit de prédiction de propriétés des arêtes, soit de prédiction d’arêtes manquantes. La prédiction de propriétés des arêtes aide à prédire les effets secondaires des médicaments en prédisant les effets secondaires indésirables donnés une paire de médicaments. La prédiction d’arêtes manquantes est utilisée dans les systèmes de recommandation pour prédire si deux nœuds d’un graphe sont liés.

Il est également possible de travailler au niveau des sous-graphes pour la détection de communautés ou la prédiction de propriétés des sous-graphes. Les réseaux sociaux utilisent la détection de communautés pour déterminer comment les personnes sont connectées. La prédiction de propriétés des sous-graphes peut être utilisée dans les systèmes d’itinéraire (comme Google Maps) pour prédire les heures d’arrivée estimées.

Le travail sur ces tâches peut être effectué de deux manières.

Lorsque vous souhaitez prédire l’évolution d’un graphe spécifique, vous travaillez dans un contexte transductif, où tout (formation, validation et test) est effectué sur le même graphe unique. Si c’est votre configuration, soyez prudent ! La création d’ensembles de données d’entraînement/évaluation/test à partir d’un seul graphe n’est pas trivial. Cependant, une grande partie du travail est effectuée à l’aide de graphes différents (séparés en ensembles d’entraînement/évaluation/test), ce qui est appelé un contexte inductif.

Comment représentons-nous les graphes ?

Les façons courantes de représenter un graphe pour le traiter et l’exploiter sont soit :

comme l’ensemble de toutes ses arêtes (éventuellement complété par l’ensemble de tous ses nœuds),
ou comme la matrice d’adjacence entre tous ses nœuds. Une matrice d’adjacence est une matrice carrée (de taille nœud * nœud) qui indique quels nœuds sont directement connectés à d’autres (où (A_{ij} = 1) si (n_i) et (n_j) sont connectés, sinon 0). Remarque : la plupart des graphes ne sont pas densément connectés et ont donc des matrices d’adjacence clairsemées, ce qui peut rendre les calculs plus difficiles.

Cependant, bien que ces représentations semblent familières, ne vous laissez pas tromper !

Les graphiques sont très différents des objets typiques utilisés en ML car leur topologie est plus complexe que simplement “une séquence” (comme du texte et de l’audio) ou “une grille ordonnée” (comme des images et des vidéos, par exemple) : même s’ils peuvent être représentés sous forme de listes ou de matrices, leur représentation ne doit pas être considérée comme un objet ordonné !

Mais qu’est-ce que cela signifie ? Si vous prenez une phrase et mélangez ses mots, vous créez une nouvelle phrase. Si vous prenez une image et réarrangez ses colonnes, vous créez une nouvelle image.

Ce n’est pas le cas pour un graphique : si vous mélangez sa liste d’arêtes ou les colonnes de sa matrice d’adjacence, c’est toujours le même graphique. (Nous expliquons cela plus formellement un peu plus bas, recherchez l’invariance de permutation).

Représentations de graphiques via ML

Le processus habituel pour travailler sur des graphiques avec l’apprentissage automatique consiste d’abord à générer une représentation significative pour vos éléments d’intérêt (nœuds, arêtes ou graphiques complets selon votre tâche), puis à utiliser ces éléments pour entraîner un prédicteur pour votre tâche cible. Nous voulons (comme dans d’autres modalités) contraindre les représentations mathématiques de vos objets de sorte que des objets similaires soient mathématiquement proches. Cependant, cette similarité est difficile à définir strictement en graphique ML : par exemple, deux nœuds sont-ils plus similaires lorsqu’ils ont les mêmes étiquettes ou les mêmes voisins ?

Note : Dans les sections suivantes, nous nous concentrerons sur la génération de représentations de nœuds. Une fois que vous avez des représentations au niveau des nœuds, il est possible d’obtenir des informations au niveau des arêtes ou du graphique. Pour les informations au niveau des arêtes, vous pouvez concaténer les représentations de paires de nœuds ou faire un produit scalaire. Pour les informations au niveau du graphique, il est possible de faire un pooling global (moyenne, somme, etc.) sur le tenseur concaténé de toutes les représentations au niveau des nœuds. Cependant, cela lisse et perd des informations sur le graphique – un pooling hiérarchique récursif peut être plus judicieux, ou ajouter un nœud virtuel, connecté à tous les autres nœuds du graphique, et utiliser sa représentation comme représentation globale du graphique.

Approches pré-neuronales

Utilisation simple de caractéristiques générées

Avant les réseaux neuronaux, les graphiques et leurs éléments d’intérêt pouvaient être représentés sous forme de combinaisons de caractéristiques, de manière spécifique à la tâche. Maintenant, ces caractéristiques sont encore utilisées pour l’augmentation des données et l’apprentissage semi-supervisé, bien que des méthodes de génération de caractéristiques plus complexes existent ; il peut être essentiel de déterminer la meilleure façon de les fournir à votre réseau en fonction de votre tâche.

Les caractéristiques au niveau des nœuds peuvent fournir des informations sur l’importance (à quel point ce nœud est important pour le graphique ?) et/ou la structure (quelle est la forme du graphique autour du nœud ?), et peuvent être combinées.

La centralité du nœud mesure l’importance du nœud dans le graphique. Elle peut être calculée de manière récursive en additionnant la centralité des voisins de chaque nœud jusqu’à convergence, ou par le biais de mesures de distance minimale entre les nœuds, par exemple. Le degré du nœud est la quantité de voisins directs qu’il possède. Le coefficient de regroupement mesure la connectivité des voisins du nœud. Les vecteurs de degré des graphiques comptent combien de graphiques différents sont enracinés à un nœud donné, où les graphiques sont tous les mini-graphiques que vous pouvez créer avec un certain nombre de nœuds connectés (avec trois nœuds connectés, vous pouvez avoir une ligne avec deux arêtes, ou un triangle avec trois arêtes).

Les caractéristiques au niveau des arêtes complètent la représentation avec des informations plus détaillées sur l’interconnexion des nœuds, et incluent la distance minimale entre deux nœuds, leurs voisins communs et leur indice de Katz (qui est le nombre de promenades possibles jusqu’à une certaine longueur entre deux nœuds – il peut être calculé directement à partir de la matrice d’adjacence).

Les caractéristiques au niveau du graphique contiennent des informations de haut niveau sur la similarité et les spécificités du graphique. Les comptages de graphlets totaux, bien que coûteux en termes de calcul, fournissent des informations sur la forme des sous-graphes. Les méthodes de noyau mesurent la similarité entre les graphiques par le biais de différentes méthodes “sac de nœuds” (similaire à un sac de mots).

Approches basées sur les marches

Les approches basées sur les marches utilisent la probabilité de visiter un nœud j à partir d’un nœud i lors d’une marche aléatoire pour définir des mesures de similarité ; ces approches combinent à la fois des informations locales et globales. Node2Vec, par exemple, simule des marches aléatoires entre les nœuds d’un graphique, puis traite ces marches avec un skip-gramme, tout comme nous le ferions avec des mots dans des phrases, pour calculer des embeddings. Ces approches peuvent également être utilisées pour accélérer les calculs de la méthode Page Rank, qui attribue un score d’importance à chaque nœud (basé sur sa connectivité avec d’autres nœuds, évaluée comme sa fréquence de visite lors d’une marche aléatoire, par exemple).

Cependant, ces méthodes ont des limites : elles ne peuvent pas obtenir des embeddings pour de nouveaux nœuds, ne capturent pas finement la similarité structurelle entre les nœuds et ne peuvent pas utiliser de nouvelles fonctionnalités ajoutées.

Réseaux neuronaux graphiques

Les réseaux neuronaux peuvent généraliser à des données non vues auparavant. Étant donné les contraintes de représentation que nous avons évoquées précédemment, quel devrait être un bon réseau neuronal pour travailler sur des graphes ?

Il devrait :

être invariant par permutation :
- Équation : f ( P ( G ) ) = f ( G ) f(P(G))=f(G) f ( P ( G ) ) = f ( G ) avec f le réseau, P la fonction de permutation, G le graphe
- Explication : la représentation d’un graphe et de ses permutations devrait être la même après avoir traversé le réseau
être équivalent par permutation
- Équation : P ( f ( G ) ) = f ( P ( G ) ) P(f(G))=f(P(G)) P ( f ( G ) ) = f ( P ( G ) ) avec f le réseau, P la fonction de permutation, G le graphe
- Explication : permuter les nœuds avant de les passer au réseau devrait être équivalent à permuter leurs représentations

Les réseaux neuronaux classiques, tels que les RNN ou les CNN, ne sont pas invariants par permutation. Une nouvelle architecture, le réseau neuronal graphique, a donc été introduite (initialement en tant que machine basée sur l’état).

Un GNN est composé de couches successives. Une couche GNN représente un nœud comme la combinaison ( aggrégation ) des représentations de ses voisins et de lui-même de la couche précédente ( message passing ), plus généralement une activation pour ajouter une certaine non-linéarité.

Comparaison avec d’autres modèles : Un CNN peut être considéré comme un GNN avec des tailles de voisinage fixes (via la fenêtre glissante) et un ordre fixe (il n’est pas équivalent par permutation). Un Transformer sans embeddings de position peut être considéré comme un GNN sur un graphe d’entrée entièrement connecté.

Aggrégation et message passing

Il existe de nombreuses façons d’agréger les messages des nœuds voisins, par exemple en faisant la somme ou la moyenne. Quelques travaux remarquables suivant cette idée incluent :

Graph Convolutional Networks fait la moyenne de la représentation normalisée des voisins d’un nœud (la plupart des GNN sont en réalité des GCN) ;
Graph Attention Networks apprennent à pondérer les différents voisins en fonction de leur importance (comme les transformers) ;
GraphSAGE échantillonne les voisins à différentes distances avant d’agréger leurs informations en plusieurs étapes avec un max pooling ;
Graph Isomorphism Networks agrègent les représentations en appliquant un MLP à la somme des représentations des nœuds voisins.

Choisir une aggrégation : Certaines techniques d’aggrégation (notamment la moyenne/le max pooling) peuvent rencontrer des cas d’échec lors de la création de représentations qui différencient finement les nœuds avec des voisinages différents de nœuds similaires (par exemple, avec la moyenne, un voisinage avec 4 nœuds, représenté par 1,1,-1,-1, en moyenne 0, ne sera pas différent d’un voisinage avec seulement 3 nœuds représentés par -1, 0, 1).

Forme du GNN et problème de sur-lissage

À chaque nouvelle couche, la représentation du nœud inclut de plus en plus de nœuds.

Un nœud, à travers la première couche, est l’aggrégation de ses voisins directs. À travers la deuxième couche, c’est toujours l’aggrégation de ses voisins directs, mais cette fois, leurs représentations incluent leurs propres voisins (de la première couche). Après n couches, la représentation de tous les nœuds devient une aggrégation de tous leurs voisins à une distance de n, donc de l’ensemble du graphe si son diamètre est inférieur à n !

Si votre réseau a trop de couches, il y a un risque que chaque nœud devienne une aggrégation de l’ensemble du graphe (et que les représentations des nœuds convergent vers la même représentation pour tous les nœuds). Cela s’appelle le problème de sur-lissage.

Cela peut être résolu en :

redimensionnant le GNN pour avoir un nombre de couches suffisamment petit pour ne pas approximer chaque nœud comme l’ensemble du réseau (en analysant d’abord le diamètre et la forme du graphe)
augmentant la complexité des couches
ajoutant des couches non basées sur les messages pour traiter les messages (comme des MLP simples)
ajoutant des connexions sautées.

Le problème de sur-lissage est un domaine d’étude important en ML graphique, car il empêche les GNN de s’étendre, comme cela a été démontré pour les transformers dans d’autres modalités.

Transformateurs de graphes

Un Transformer sans sa couche d’encodage positionnel est invariant par permutation, et les Transformers sont connus pour bien s’adapter, donc récemment, les gens ont commencé à étudier l’adaptation des Transformers aux graphes (Enquête). La plupart des méthodes se concentrent sur les meilleures façons de représenter les graphes en recherchant les meilleures caractéristiques et les meilleures façons de représenter les informations positionnelles et en adaptant l’attention à ces nouvelles données.

Voici quelques méthodes intéressantes qui ont donné des résultats de pointe ou proches sur l’un des benchmarks les plus difficiles disponibles à l’heure actuelle, le Stanford’s Open Graph Benchmark :

Transformateur de graphes pour l’apprentissage de séquences de graphes (Cai et Lam, 2020) a introduit un Encodeur de graphes, qui représente les nœuds comme une concaténation de leurs embeddings et d’embeddings positionnels, les relations entre les nœuds comme les plus courts chemins entre eux, et combine les deux dans une attention auto-augmentée par les relations.
Réflexion sur les transformateurs de graphes avec attention spectrale (Kreuzer et al, 2021) a introduit les Réseaux d’attention spectrale (SANs). Ceux-ci combinent les caractéristiques des nœuds avec un encodage positionnel appris (calculé à partir des vecteurs/valeurs propres du Laplacien) à utiliser comme clés et requêtes dans l’attention, les valeurs d’attention étant les caractéristiques des arêtes.
GRPE : Encodage positionnel relatif pour le transformateur de graphes (Park et al, 2021) a introduit le Transformateur d’encodage positionnel relatif de graphes. Il représente un graphe en combinant un encodage positionnel au niveau du graphe avec les informations des nœuds, un encodage positionnel au niveau des arêtes avec les informations des nœuds, et combine les deux dans l’attention.
L’attention globale sur soi en remplacement de la convolution de graphes (Hussain et al, 2021) a introduit le Transformateur augmenté par les arêtes. Cette architecture incorpore séparément les nœuds et les arêtes, et les agrège dans une attention modifiée.
Est-ce que les Transformers sont vraiment mauvais pour la représentation des graphes (Ying et al, 2021) introduit le Graphormer de Microsoft, qui a remporté la première place sur l’OGB lors de sa sortie. Cette architecture utilise les caractéristiques des nœuds en tant que clés/requêtes/valeurs dans l’attention, et additionne leur représentation avec une combinaison d’encodages de centralité, d’espacement et d’arêtes dans le mécanisme d’attention.

L’approche la plus récente est celle des Transformateurs purs comme puissants apprenants de graphes (Kim et al, 2022), qui a introduit TokenGT. Cette méthode représente les graphes d’entrée comme une séquence d’embeddings de nœuds et d’arêtes (augmentés avec des identifiants de nœuds orthonormaux et des identifiants de type entraînables), sans encodage positionnel, et fournit cette séquence en entrée aux Transformers. C’est extrêmement simple, mais intelligent !

Un peu différent, la Recette pour un Transformateur de graphes général, puissant et extensible (Rampášek et al, 2022) introduit, non pas un modèle, mais un cadre, appelé GraphGPS. Il permet de combiner facilement les réseaux à passage de messages avec les transformateurs linéaires (à longue portée) pour créer des réseaux hybrides. Ce cadre contient également plusieurs outils pour calculer les encodages positionnels et structuraux (niveau de nœud, de graphe, d’arête), l’augmentation des caractéristiques, les marches aléatoires, etc.

L’utilisation des transformateurs pour les graphes est encore très récente, mais elle semble prometteuse, car elle pourrait atténuer plusieurs limitations des GNN (Graph Neural Networks), telles que la mise à l’échelle des graphes plus grands/plus denses ou l’augmentation de la taille du modèle sans lissage excessif.

Si vous souhaitez approfondir, vous pouvez consulter certains de ces cours :

Format académique
- Machine Learning avec les Graphes de Stanford
- Apprentissage de la représentation des graphes de McGill
Format vidéo
- Cours sur l’apprentissage géométrique profond
Livres
- Apprentissage de la représentation des graphes*, Hamilton
Enquêtes
- Guide d’étude sur les réseaux neuronaux graphiques
Directions de recherche
- GraphML en 2023 résume des directions intéressantes et plausibles pour GraphML en 2023.

De bonnes bibliothèques pour travailler sur les graphes sont PyGeometric ou la Deep Graph Library (pour l’apprentissage automatique sur les graphes) et NetworkX (pour manipuler les graphes de manière plus générale).

Si vous avez besoin de références de qualité, vous pouvez consulter :

OGB, l’Open Graph Benchmark : les ensembles de données de référence pour l’évaluation des graphes, pour différentes tâches et échelles de données.
Évaluation des GNNs : bibliothèque et ensembles de données pour évaluer les réseaux d’apprentissage automatique sur graphes et leur expressivité. L’article associé étudie notamment les ensembles de données pertinents d’un point de vue statistique, les propriétés des graphes qu’ils permettent d’évaluer, et les ensembles de données qui ne devraient plus être utilisés comme références.
Benchmark à longue portée sur les graphes : benchmark récent (novembre 2022) qui examine les informations à longue portée sur les graphes.
Taxonomie des références dans l’apprentissage de la représentation des graphes : article publié lors de la conférence Learning on Graphs 2022, qui analyse et classe les ensembles de données de référence existants.

Pour plus de jeux de données, voir :

Paper with code Graph tasks Leaderboards : Classement pour les jeux de données et les références publiques – attention, tous les benchmarks de ce classement ne sont plus forcément pertinents
TU datasets : Compilation de jeux de données disponibles publiquement, maintenant classés par catégories et fonctionnalités. La plupart de ces jeux de données peuvent également être chargés avec PyG, et certains d’entre eux ont été portés sur Datasets
SNAP datasets: Stanford Large Network Dataset Collection :
MoleculeNet datasets
Relational datasets repository

Attribution des images externes

Les emojis dans la miniature proviennent de Openmoji (CC-BY-SA 4.0), la figure des graphlets provient de Biological network comparison using graphlet degree distribution (Pržulj, 2007).

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!

Was this article helpful?

93 out of 132 found this helpful