Skip to content
Retour aux résultats

Plongement de réseau — Node2Vec, DeepWalk, LINE

Année
2014 (DeepWalk); 2016 (Node2Vec)
Type
Representation learning / unsupervised network method

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

Taille de police

À quoi sert-elle ?

Le plongement de réseau est une famille de méthodes d'apprentissage de représentations qui associent chaque nœud d'un graphe à un vecteur dense de faible dimension tout en préservant les propriétés structurelles du réseau.

L'approche a été formalisée pour les données de réseaux sociaux par Perozzi, Al-Rfou et Skiena avec DeepWalk (2014), qui a adapté le modèle Word2Vec skip-gram aux marches aléatoires sur les graphes, et étendue par Grover et Leskovec avec Node2Vec (2016), qui a introduit une marche aléatoire biaisée équilibrant l'exploration en largeur d'abord et en profondeur d'abord. Ces plongements transforment les données relationnelles en vecteurs de caractéristiques que les classificateurs et algorithmes de clustering standards d'apprentissage automatique peuvent consommer directement.

L’intuition derrière la méthode

Un graphe est composé de nœuds et d'arêtes, mais la plupart des algorithmes d'apprentissage automatique attendent une table de nombres. Le plongement de réseau résout ce problème de traduction. Tout comme Word2Vec apprend le sens des mots en observant quels mots apparaissent à proximité les uns des autres dans les phrases, DeepWalk apprend le sens des nœuds en observant quels nœuds apparaissent à proximité les uns des autres dans des marches aléatoires à travers le graphe. Le résultat est une coordonnée dans un espace vectoriel — les nœuds structurellement similaires ou fréquemment co-visités finissent par être proches les uns des autres. Une fois que chaque nœud a un vecteur, vous pouvez alimenter ces vecteurs dans un classificateur, les regrouper avec k-means, ou les visualiser avec UMAP, sans écrire de code spécifique au graphe.

Histoire

L'idée d'appliquer Word2Vec à des données structurées en graphe a été introduite par Perozzi, Al-Rfou et Skiena dans DeepWalk (KDD 2014), qui a montré que les marches aléatoires sur un graphe social pouvaient remplacer les caractéristiques conçues à la main pour la classification de nœuds. Grover et Leskovec ont étendu cela dans Node2Vec (KDD 2016) en introduisant une marche aléatoire biaisée du second ordre paramétrée par p et q, offrant un contrôle explicite sur le compromis entre l'exploration du voisinage basée sur l'homophilie et celle basée sur l'équivalence structurelle. À peu près à la même période, Tang et al. ont proposé LINE (WWW 2015), qui apprend les plongements en optimisant directement les objectifs de proximité de premier et second ordre plutôt que par des marches aléatoires, ce qui le rend adapté aux très grands graphes. Ensemble, ces trois méthodes ont établi le domaine de l'apprentissage de représentations de réseaux et ont inspiré les architectures ultérieures de réseaux neuronaux sur graphes.

Quand l’utiliser

Le plongement de réseau est approprié lorsque vous avez un graphe d'au moins 50 nœuds et que vous avez besoin de caractéristiques vectorielles continues pour des tâches en aval telles que la classification de nœuds, la prédiction de liens ou le clustering de nœuds. La méthode convient aux graphes non pondérés et pondérés, et gère les structures dirigées ou non dirigées. Choisissez DeepWalk lorsqu'une ligne de base simple de marche aléatoire uniforme est suffisante. Choisissez Node2Vec lorsque vous souhaitez ajuster l'équilibre entre homophilie et équivalence structurelle via les paramètres p et q. Si vous avez besoin de plonger de nouveaux nœuds jamais vus au moment de l'inférence sans réentraînement, préférez une méthode inductive comme GraphSAGE ; le plongement de réseau sous sa forme standard est transductif. La méthode ne nécessite pas d'attributs de nœuds normalement distribués.

Limites et points d’attention

  • Transductif : le modèle ne peut pas plonger les nœuds qui n'étaient pas présents pendant l'entraînement sans réentraînement complet.
  • Sensibilité aux hyperparamètres : la dimension du plongement, la longueur de la marche, le nombre de marches, la taille de la fenêtre, p et q affectent tous la qualité du plongement et nécessitent un réglage.
  • Les marches aléatoires ne capturent pas la structure de graphe d'ordre supérieur (par exemple, hyperarêtes ou arêtes multi-relationnelles) sans extension.
  • Les performances se dégradent sur de très petits graphes (moins de 50 nœuds) où le corpus de marches est trop épars pour apprendre des statistiques fiables.

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

Points forts

  • Convertit les données de graphe relationnel en vecteurs de longueur fixe compatibles avec tout pipeline standard d'apprentissage automatique.
  • Les paramètres p et q de Node2Vec permettent à l'analyste d'ajuster l'équilibre entre les plongements sensibles aux communautés et sensibles aux rôles.
  • Les poids des arêtes peuvent être incorporés dans les probabilités de parcours, capturant la force de la relation sans étapes de modélisation supplémentaires.
  • Évolutif vers de grands graphes grâce à un échantillonnage efficace par marches aléatoires et à la procédure d'entraînement skip-gram.

Applications

  • Classification de nœuds dans les réseaux de citations, les plateformes sociales ou les graphes d'interactions biologiques.
  • Prédiction de liens — identification des arêtes manquantes ou futures en comparant la similarité des plongements de nœuds.
  • Détection de communautés en regroupant les vecteurs de nœuds avec k-means ou des méthodes hiérarchiques.
  • Détection d'anomalies — les nœuds dont les plongements sont des valeurs aberrantes dans l'espace vectoriel peuvent représenter des rôles structurels inhabituels.
  • Systèmes de recommandation où les utilisateurs et les articles sont des nœuds dans un graphe d'interaction bipartite ou multiplex.

Comment ça marche

Comment ça marche

1

Le processus commence par un graphe G dans lequel les nœuds sont des entités et les arêtes représentent des relations. Les arêtes peuvent être dirigées ou non dirigées et peuvent porter des poids qui influenceront plus tard la probabilité de parcours. Si des poids d'arête sont présents, ils sont inclus dans les probabilités de parcours ; s'ils sont absents, toutes les arêtes reçoivent un poids égal. À ce stade, l'analyste choisit également la variante de l'algorithme — DeepWalk pour les marches aléatoires uniformes, Node2Vec pour les marches biaisées contrôlées par les paramètres p (retour) et q (entrée-sortie), ou LINE lorsque la proximité du voisinage de premier et de second ordre doit être apprise séparément. Le choix entre les régimes de paramètres de Node2Vec est guidé par la propriété attendue du réseau : homophilie (les nœuds similaires se connectent, donc l'exploration en largeur d'abord est préférée, q < 1) ou équivalence structurelle (les nœuds ayant des rôles similaires peuvent être éloignés, donc l'exploration en profondeur d'abord est préférée, p < 1).

2

En partant de chaque nœud, l'algorithme simule une série de marches aléatoires de longueur fixe (typiquement 30 pas) et les répète plusieurs fois (typiquement 200 marches par nœud). Chaque marche produit une séquence d'identifiants de nœuds analogue à une phrase de mots. Dans DeepWalk, le nœud suivant est choisi uniformément parmi les voisins. Dans Node2Vec, le nœud suivant est choisi selon des probabilités de transition biaisées par p et q : revenir au nœud précédent est pénalisé par 1/p, rester à la même distance est maintenu à 1, et s'éloigner est contrôlé par 1/q. L'ensemble de toutes les marches forme un corpus de séquences de nœuds qui encode la topologie du graphe.

3

Le corpus de séquences de nœuds est alimenté dans un modèle skip-gram (la même architecture que Word2Vec). Pour chaque nœud d'une marche, le modèle prédit les nœuds de contexte environnants dans une fenêtre (typiquement 10 pas). Par descente de gradient stochastique, le modèle apprend une représentation vectorielle dense de dimension fixe — couramment 64 ou 128 — pour chaque nœud, de sorte que les nœuds co-occurant dans les marches aient des vecteurs similaires. La dimension est un hyperparamètre : des dimensions plus grandes capturent plus de structure mais augmentent le calcul et le risque de surapprentissage sur de petits graphes.

4

Une fois entraîné, le modèle fournit un vecteur de plongement par nœud. Ces vecteurs sont utilisés comme caractéristiques pour la classification de nœuds (en les alimentant dans une régression logistique ou un classificateur neuronal), la prédiction de liens (en comparant les vecteurs de paires de nœuds candidats), ou la détection de communautés (en regroupant les vecteurs). Les plongements sont transductifs : ils sont fixes pour les nœuds vus pendant l'entraînement. Si de nouveaux nœuds doivent être plongés après l'entraînement, une méthode inductive telle que GraphSAGE doit être utilisée à la place, car un modèle Node2Vec ou DeepWalk standard ne peut pas généraliser à des nœuds non vus sans réentraînement.

Pièges courants

  • Appliquer un modèle Node2Vec à de nouveaux nœuds qui n'étaient pas dans le graphe d'entraînement — le modèle n'aura pas de vecteur pour eux ; utilisez une méthode inductive (par exemple, GraphSAGE) lorsque le plongement transductif n'est pas acceptable.
  • Utiliser les valeurs par défaut p=1, q=1 (équivalent à DeepWalk) sans examiner si le réseau suit un schéma d'homophilie ou d'équivalence structurelle — régler p et q selon le schéma attendu peut améliorer considérablement les performances de la tâche en aval.
  • Traiter la dimension du plongement comme une constante fixe : sur de petits graphes, une dimension de 64 ou 128 peut entraîner un surapprentissage ; commencez plus bas et validez sur la tâche en aval.
  • Ignorer l'exigence d'échantillon minimum : les graphes de moins de 50 nœuds produisent des corpus de marches trop minces pour entraîner des plongements fiables.

Questions fréquentes

Quelle est la différence entre DeepWalk, Node2Vec et LINE ?

DeepWalk utilise des marches aléatoires uniformes et le modèle Word2Vec skip-gram — c'est la ligne de base la plus simple. Node2Vec ajoute des marches aléatoires biaisées contrôlées par p et q, permettant à l'analyste de régler si la marche explore comme une recherche en largeur d'abord (homophilie) ou en profondeur d'abord (équivalence structurelle). LINE n'utilise pas du tout de marches aléatoires ; il optimise directement les objectifs de proximité de premier et second ordre sur la liste des arêtes, ce qui est plus évolutif pour de très grands graphes mais sacrifie le signal du voisinage basé sur les marches.

Comment choisir les paramètres p et q dans Node2Vec ?

p contrôle la probabilité de revenir au nœud précédent (p faible = moins de retour en arrière), et q contrôle le rayon d'exploration (q < 1 favorise l'exploration vers l'extérieur, q > 1 maintient la marche près de la source). Si vous vous attendez à ce que les nœuds d'une même communauté soient similaires (homophilie), définissez q < 1 pour laisser la marche s'étendre vers l'extérieur. Si vous vous attendez à ce que les nœuds ayant le même rôle structurel soient similaires même s'ils sont éloignés, définissez p < 1 pour encourager l'exploration en profondeur. Validez les deux régimes sur la tâche en aval.

Puis-je plonger de nouveaux nœuds après l'entraînement sans réentraîner tout le modèle ?

Node2Vec et DeepWalk standard sont transductifs : la matrice de plongement ne couvre que les nœuds vus pendant l'entraînement. Pour une généralisation inductive à de nouveaux nœuds jamais vus, utilisez une méthode inductive de réseau neuronal sur graphe telle que GraphSAGE, qui apprend une fonction d'agrégation sur les voisinages de nœuds qui peut être appliquée à n'importe quel nœud au moment de l'inférence.

Combien de dimensions dois-je utiliser pour le plongement ?

Les choix les plus courants sont 64 et 128, et ceux-ci fonctionnent bien pour les graphes de taille moyenne à grande. Pour les petits graphes (50-200 nœuds), commencez avec une dimension plus faible (16 ou 32) pour éviter le surapprentissage, et évaluez la qualité du plongement en mesurant les performances de la tâche en aval (par exemple, la précision de la classification des nœuds) plutôt que la seule erreur de reconstruction.

Méthodes associées

Sources

  1. Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.

    Ouvrir la référence DOI
    Copié.
  2. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.

    Ouvrir la référence DOI
    Copié.