Apprentissage sur
graphes
GraphML – 1e partie
Raphaël Fournier-S’niehotta
CNAM Paris, fournier@[Link]
HTT-FOD
RCP217
2020-2021
2/
63
Plan
1 | Introduction
1 – Les graphes
2 – Motivations, challenges
3 – Composants d’un graphe
2 | Apprentissage classique sur des graphes
1 – Attributs et métriques
2 – Passage de messages
3 | Embeddings
4 | Graph neural networks
1 – Graph Convolutional Networks
Introduction
1 | Introduction 1.1 | Les graphes 3/
63
Les graphes
■ Les graphes proposent un langage général
pour décrire des entités qui ont des interactions
1 | Introduction 1.1 | Les graphes 4/
63
Types de graphes
Réseau social Réseau de transport
Réseau de citations
Réseau de
communications Réseau de films
Formes 3D
1 | Introduction 1.1 | Les graphes 5/
63
Domaines
■ Réseaux sociaux
■ Réseaux informatiques
■ Communications
■ Bio-informatique / médecine
■ Cerveau
■ Graphes de connaissances
■ Dépendances logicielles
■ Formes 3D
1 | Introduction 1.1 | Les graphes 6/
63
Objectif
Tirer partie de la structure (relations) du graphe,
pour améliorer les prédictions.
Peut-on développer des réseaux de neurones
pour ces structures ?
1 | Introduction 1.2 | Motivations, challenges 7/
63
Motivations, challenges
Machine learning classique :
Challenges :
■ Complexité topologique : pas de régularité locale (grille)
■ Pas d’ordre évident pour les nœuds, pas de points de référence
■ Souvent dynamique
1 | Introduction 1.2 | Motivations, challenges 8/
63
Tâches en Graph ML
■ Classification de nœuds
■ Prédiction de liens
■ Classification de graphes
■ Clustering
■ Génération de graphes
■ Évolution de graphes
1 | Introduction 1.2 | Motivations, challenges 9/
63
Réussites
Tâches sur les nœuds
■ Protein-folding (Alpha-Fold,
Google) ■ Effets secondaires
1 | Introduction 1.2 | Motivations, challenges 10/
63
Réussites : RecSys
Tâche sur les arêtes :
■ Recommandation d’images chez Pinterest
■ Très large échelle
■ Proposer des images similaires à une autre
■ Features multiples
1 | Introduction 1.2 | Motivations, challenges 11/
63
Réussites
Tâches sur les (sous-)graphes
■ Sélection de molécule pour ■ prédiction de trafic routier
antibiotiques
1 | Introduction 1.3 | Composants d’un graphe 12/
63
Terminologie
Un graphe est défini par un couple G = (V,E) tel que :
■ V (pour l’anglais vertices) est un ensemble fini de sommets
■ E (pour l’anglais edges) est un ensemble fini d’arêtes
Un graphe peut être orienté, ou non :
■ si oui, les couples (vi , vj ) ∈ E sont ordonnés, vi est le sommet initial, vj est
le sommet terminal.
■ on appelle alors le couple (vi , vj ) un arc, représenté graphiquement par
vi → vj .
■ si non, les couples ne sont pas orientés et (vi , vj ) est équivalent à (vj , vi ),
et on l’appelle arête, représenté par vi − vj
1 | Introduction 1.3 | Composants d’un graphe 13/
63
Terminologie
■ l’ordre d’un graphe, c’est son nombre de sommets (souvent désigné par n).
■ une boucle est un arc/une arête reliant un sommet à lui-même
■ un graphe dépourvu de boucle est dit élémentaire
■ un graphe simple ne comporte pas de boucle et au plus une arête entre
deux sommets
■ un graphe partiel est le graphe obtenu en supprimant certains arcs ou
arêtes
■ un sous-graphe est le graphe obtenu en supprimant certains sommets et
tous les arcs/arêtes incidents aux sommets supprimés.
■ un sommet vi est dit adjacent à un autre s’il existe une arête entre eux (on
parle de voisins).
■ le degré d’un sommet est le nombre d’arêtes incidentes à ce sommet.
■ un graphe est dit complet s’il comporte une arête (vi , vj ) pour toute paire
de sommets (vi , vj ) ∈ E2 .
1 | Introduction 1.3 | Composants d’un graphe 14/
63
Représentation
■ Un graphe de gens qui travaillent ensemble, c’est un réseau professionnel
■ Un graphe d’articles qui se citent, c’est un réseau de citations
■ Un graphe de livres qui contiennent les mêmes mots dans leur titre : pas
de nom, mais c’est un réseau…
■ Importance de bien choisir nœuds et arêtes !
■ Parfois, c’est évident, souvent pas
■ Le choix des liens détermine la question à laquelle on répond
1 | Introduction 1.3 | Composants d’un graphe 15/
63
Degrés des nœuds
■ Le degré d’un nœud, c’est le nombre de ses voisins qui lui sont
directement liés
■ Dans les graphes dirigés, on définit un degré entrant et un degré sortant
(et le degré total est la somme des deux)
1 | Introduction 1.3 | Composants d’un graphe 16/
63
Graphe biparti
■ Un graphe est dit biparti si l’on peut diviser en deux ensembles disjoints U
et V ses sommets, de façon que chaque arête ait un sommet dans U et un
dans V
■ Exemples :
■ utilisateurs-articles (recommandation : films, titres, etc.)
■ auteurs-œuvres (recherche)
■ recettes-ingrédients
■ on peut ”projeter” ces réseaux, et analyser la projection (attention au
seuil)
1 | Introduction 1.3 | Composants d’un graphe 17/
63
Projection de biparti
2 3
1 1
3 2 4
7 8 7
8
4
6 6
5 5
1 | Introduction 1.3 | Composants d’un graphe 18/
63
Représentation de graphes
■ Matrice d’adjacence : mij = 1 si l’arête (vi , vj ) existe, 0 sinon.
■ Matrice des degrés : mij = d(vj ) pour i = j, 0 sinon.
■ Matrices de Laplace (ou “laplacienne”) : L = D - A (attention : nombreuses
variantes)
1 | Introduction 1.3 | Composants d’un graphe 19/
63
Sparsity
Attention : les matrices d’adjacence sont souvent très creuses.
1 | Introduction 1.3 | Composants d’un graphe 20/
63
Attributs
Pour les nœuds et les liens :
■ poids (fréquence de communication)
■ rang (collaborateur préféré, 2e préféré)
■ type (ami, collaborateur, famille)
■ signé ou non : confiance, amitié/inimitié
■ propriétés liées au graphe : nombre de voisins en commun
1 | Introduction 1.3 | Composants d’un graphe 21/
63
Connexité
■ Un graphe est connecté si deux sommets quelconque peuvent être liés par
un chemin
■ Un sous-graphe connecté est appelé une composante connexe
■ Un graphe est déconnecté s’il a deux composantes connexes ou plus
1 | Introduction 1.3 | Composants d’un graphe 22/
63
Connexité et matrice d’adjacence
La matrice d’adjacence d’un graphe avec plusieurs composantes connexes
peut être ré-écrite pour être diagonale par blocs.
1 | Introduction 1.3 | Composants d’un graphe 23/
63
Parcours en profondeur
■ En anglais, DFS, pour Depth First Search
■ progresse à partir d’un sommet S en s’appelant récursivement pour
chaque sommet voisin de S.
■ pour chaque sommet, on prend le premier sommet voisin, on explore tous
ses voisins (non marqués) avant de revenir au “père”
■ Ordre de visite : A, B, D, F, E, C, G
■ s’implémente avec une pile (LIFO)
1 | Introduction 1.3 | Composants d’un graphe 24/
63
Parcours en largeur
■ En anglais, BFS, pour Breadth First Search
■ pour chaque sommet, on repère tous ses voisins, on stocke ceux qui ne
sont pas marqués dans une file (queue)
■ Ordre de visite : A, B, C, E, D, F, G
■ s’implémente avec une file (FIFO)
■ on obtient les plus courts chemins à la racine
Apprentissage classique sur des graphes
2 | Apprentissage classique sur des graphes 25/
63
Apprentissage classique sur graphes
Trois types de tâches :
■ prédiction sur les nœuds
■ prédiction sur les arêtes
■ prédiction au niveau graphe entier
2 | Apprentissage classique sur des graphes 26/
63
Schéma/pipeline classique
■ On conçoit des caractéristiques pour les nœuds/arêtes/sommets
■ On obtient les valeurs de ces caractéristiques pour toutes les données
d’apprentissage
■ On entraîne le modèle
■ On l’applique : pour un nouveau nœud/lien/graphe, on utilise ses
caractéristiques pour faire une prédiction
2 | Apprentissage classique sur des graphes 2.1 | Attributs et métriques 27/
63
Attributs de nœuds
■ degré (voisinage, sans l’importance)
■ centralité (diversement calculée)
■ coefficient de clustering (densité
locale)
■ graphlets
2 | Apprentissage classique sur des graphes 2.1 | Attributs et métriques 28/
63
Graphlets
■ sous-graphes connectés
non isomorphes
■ GDV de ν : [2, 1, 0, 2]
■ Graphlet Degree Vector :
mesure de topologie locale
(dim 73 !)
2 | Apprentissage classique sur des graphes 2.1 | Attributs et métriques 29/
63
Attributs de liens
■ Métrique reposant sur la distance
■ plus court chemin entre deux nœuds
■ Voisinage local (cf cours Reco)
■ Common Neighbors
■ Indice de Jaccard
■ Adamic-Adar
■ Structure globale
■ Indice/centralité de Katz (cf Reco)
2 | Apprentissage classique sur des graphes 2.1 | Attributs et métriques 30/
63
Attributs de graphes entiers
■ Méthodes à noyaux.
L’idée : trouver des noyaux plutôt que des vecteurs de caractéristiques. Une
fois le noyau défini, on prend un modèle sur étagères (SVM) pour prédire
■ Idée commune : généraliser les ”bag-of-words” (IR/NLP) aux graphes
■ Quelques modèles :
■ Noyau à Graphlets (généralisés, avec nœuds isolés)
■ Noyau de Weisfeiler-Lehman (Bag-of-degrees subtil)
■ Noyau à marche aléatoire, à plus court chemin, etc.
2 | Apprentissage classique sur des graphes 2.1 | Attributs et métriques 31/
63
Résumé
Le ML classique sur les graphes consiste donc à :
■ extraire les features (attributs, puis métriques) pour les nœuds, les liens,
voire le graphe
■ apprendre un modèle
2 | Apprentissage classique sur des graphes 2.2 | Passage de messages 32/
63
Passage de messages
Le passage de message est un framework pour faire de la classification de
nœuds.
■ Cela repose sur les corrélations dans le graphe : des nœuds similaires
sont connectés (homophilie, cf RecSys)
■ Classification collective : on cherche à affecter les étiquettes de tous les
nœuds du graphe
■ On suppose que le label Yv d’un nœud v dépend des labels de ses voisins :
P(Yv ) = P(Yv |Nv )
■ 3 étapes :
1. on affecte des étiquettes
2. on capture les corrélations entre
nœuds
3. on propage ces corrélations dans
le réseau
2 | Apprentissage classique sur des graphes 2.2 | Passage de messages 33/
63
Techniques de passage de message
■ Classification relationnelle
■ probabilité qu’un nœud ait une classe
■ mise-à-jour : moyenne (pondérée) du voisinage
■ risque de non convergence et pas d’usage des attributs
■ Classification itérative (utilisation d’attributs)
■ résumé à partir des attributs les plus fréquents dans le voisinage
■ Propagation de croyance (belief propagation, avec programmation
dynamique)
Embeddings
3 | Embeddings 34/
63
Embeddings
■ Embeddings = plongements
■ Objectif : apprendre des représentations indépendantes des tâches
■ On veut une représentation vectorielle des nœuds
■ similarité d’embedding = similarité dans le réseau (proximité, symétrie)
■ encoder l’information structurelle
3 | Embeddings 35/
63
Exemple : Karaté-club
Perozzi et al, 2014. ”DeepWalk”
3 | Embeddings 36/
63
Objectif
On voudrait :
sim(u, v) ≈ zTv zu
■ sim(u,v) concerne le graphe initial
■ DEC(zv , zu ) = zTv zu calcule la similarité d’embeddings
3 | Embeddings 37/
63
Apprendre les embeddings
■ L’encodeur ENC fait la correspondance des nœuds vers les embeddings
ENC(v) = zv (de dimension d)
■ On définit une similarité entre nœuds dans le réseau original
■ Le décodeur DEC fait la correspondance entre embeddings et similarité
■ On cherche à optimiser les paramètres (encodeur, décodeur) tels que :
sim(u,v) ≈ DEC(zv , zu ) = zTv zu
3 | Embeddings 38/
63
Encodeur superficiel
■ L’encodeur est juste un ”lookup”
■ ENC(v) = zv = Z · v où
■ Z ∈ Rd×|V| est une matrice (chaque colonne est un embedding (appris)
■ v ∈ I|V| est un vecteur-indicateur, nul sauf sur la ligne correspondant à v
■ En fait, on optimise/apprend ”directement” les embeddings de chaque
nœud (via la matrice Z).
■ La fonction objectif doit maximiser zTv zu pour les paires de nœuds
similaires
3 | Embeddings 39/
63
Similarités
On veut ”plonger” les nœuds dans un espace tel que les distances dans
celui-ci reflètent les similarités dans le graphe original. Comment faire ?
■ Naïvement : similarité si connexion entre nœuds
■ Indicateurs de voisinage (Jaccard, Adamic-Adar)
■ Approches par marches aléatoires
■ expressivité : incorpore de l’information locale et globale sur le graphe
■plus efficace : on ne considère pas toutes les paires dans l’entraînement,
seulement celles qui sont co-apparaissent dans une marche aléatoire
■ Méthodes DeepWalk, node2vec
■ On peut aussi faire de l’embedding de graphes entiers (hors scope)
3 | Embeddings 40/
63
Similarités avec marches aléatoires
■ Objectif : estimer directement des
valeurs d’embedding pour un nœud de
façon à préserver des aspects de la
structure du graphe
On veut : zTv zv ≈ P (”u,v” dans la même marche aléatoire)
On estime la probabilité de visiter le nœud v quand on fait une marche
aléatoire depuis u :
■ on fait une marche aléatoire de longueur fixée, à partir de chaque nœud
dans le graphe
■ on collecte l’ensemble des nœuds visités
■ on optimise avec une SGD :
L= ∑ ∑ −log(P(v|zu ))
v∈V v∈NR (u)
3 | Embeddings 41/
63
Similarités avec marches aléatoires
Comment faire la marche aléatoire :
■ marche aléatoire non biaisée, depuis chaque nœud (DeepWalk. Perozzi et
al., 2013)
■ node2vec : marche aléatoire ”flexible”, avec 2 paramètres :
■ possibilité de retourner au nœud précédent
■ ratio d’examen par BFS ou DFS
■ linéaire en temps et parallélisable
3 | Embeddings 42/
63
Embeddings : à quoi ça sert
Une fois qu’on a les zi , on peut faire :
■ du clustering/de la détection de communautés
■ classer des nœuds, en prédisant une étiquette avec zi
■ prédire des liens (i, j) à l’aide de (zi , zj )
■ concaténation, somme, moyenne d’embeddings
■ classer des graphes entiers, en agrégeant des zi
Graph neural networks
4 | Graph neural networks 43/
63
Limite du Shallow encoding
■ beaucoup de paramètres (O(|V|)) sont nécessaires
■ pas de partage de paramètres entre nœuds
■ chaque nœud a un embedding unique
■ transductif uniquement : impossible de générer des embeddings pour des
nœuds non vus lors de l’entraînement
■ pas d’utilisation des attributs des nœuds
4 | Graph neural networks 44/
63
Encodeurs profonds pour graphes
4 | Graph neural networks 45/
63
Apprentissage profond et graphes
■ Graphe G
■ Matrice d’adjacence A (binaire)
■ v ∈ V, N(v) ses voisins
■ X ∈ Rm×|V| matrice d’attributs
■ profil de réseau social, image, etc.
4 | Graph neural networks 46/
63
Approche naïve
■ fusionner / concaténer la matrice d’attributs et celle d’adjacence, la
passer dans un réseau de neurones classique
■ problèmes :
■ toujours O(|V|) paramètres
■ peu applicable aux graphes de différentes tailles
■ sensibilité à l’ordre des nœuds
4 | Graph neural networks 47/
63
CNN et images
4 | Graph neural networks 48/
63
Localité et graphes
■ Les graphes n’ont pas la notion classique de ”localité”,
ou de fenêtre glissante
■ Les graphes sont ”invariants par
permutation” :
f(PAPT ) = f(A) invariance
T
f(PAP ) = Pf(A) equivariance
4 | Graph neural networks 49/
63
Des images aux graphes
■ L’idée est de ”transformer” l’information des voisins :
■ les embeddings hi des voisins sont transformés Wi · hi
■ Puis sommés : ∑i Wi hi
4 | Graph neural networks 4.1 | Graph Convolutional Networks 50/
63
Graph Convolutional Networks
■ Kipf & Welling, ICLR 2017
■ le voisinage d’un nœud définit un ”graphe de calcul”, à l’aide duquel on va
propager et transmettre l’information
4 | Graph neural networks 4.1 | Graph Convolutional Networks 51/
63
GCN : agrégation de voisinage
■ Embeddings générés à partir des voisinages (localité)
4 | Graph neural networks 4.1 | Graph Convolutional Networks 52/
63
GCN : agrégation de voisinage
■ Les nœuds agrègent l’information des voisins avec des réseaux de
neurones
4 | Graph neural networks 4.1 | Graph Convolutional Networks 53/
63
GCN : agrégation de voisinage
■ Chaque nœud définit un ”graphe de calcul” (computation graph)
en fonction de la structure de son voisinage
4 | Graph neural networks 4.1 | Graph Convolutional Networks 54/
63
Nombre de couches
■ Profondeur arbitraire (!)
■ les nœuds ont des embeddings à chaque couche
■ la couche 0 : les attributs d’entrée xv
■ la k-ième couche : de l’information des sommets à distance k
4 | Graph neural networks 4.1 | Graph Convolutional Networks 55/
63
Quel réseau de neurones ?
■ Les approches diffèrent surtout dans la manière d’agréger l’information
des différentes couches
4 | Graph neural networks 4.1 | Graph Convolutional Networks 56/
63
Quel réseau de neurones ?
■ Approche simple : une moyenne des voisins
4 | Graph neural networks 4.1 | Graph Convolutional Networks 57/
63
Mathématisation
■ h0v = xv
(l)
hu
hl+1
(l)
■
v = σ (Wl ∑u∈N(v) |N(v)| + Bl hv ), ∀l ∈ {0, ..., L − 1}
■ zv = hLv
■ hlv est la représentation cachée de v pour la couche l
■ Wl et Bl sont des matrices de poids (qu’on apprend). W pour l’agrégation
du voisinage, B pour la transformation du vecteur lui-même
■ on peut placer ces embeddings dans une fonction de loss et utiliser une
SGD pour apprendre ces poids
4 | Graph neural networks 4.1 | Graph Convolutional Networks 58/
63
Entraînement
Supervisé
■ on cherche à minimiser la loss L :
min L (y, f(zv ))
θ
■ y est l’étiquette du nœud
■ L peut être L2 si y est réel, Cross-entropy sinon :
L = ∑ yv log(σ (zTv θ )) + (1 − yv )log(1 − σ (zTv θ ))
v∈V
On entraîne directement, par exemple pour de la classification
■ on peut entraîner en non supervisé, en prenant une similarité structurelle
comme label
4 | Graph neural networks 4.1 | Graph Convolutional Networks 59/
63
Inductivité
■ Les paramètres d’agrégation sont partagés entre les nœuds : le modèle a
un nombre de paramètres sous-linéaire en |V|
■ Capacité de généralisation aux nœuds non vus !
■ application : recommandation à des nouveaux utilisateurs !
■ On peut même généraliser à des graphes entièrement ”non vus”
■ à partir de graphes d’interaction de protéines d’un organisme A, on peut
générer des embeddings à partir de données collectées pour l’organisme B
4 | Graph neural networks 4.1 | Graph Convolutional Networks 60/
63
Résumé
■ On définit une fonction d’agrégation de voisinage (on passe des
”messages”
■ On définit une loss sur les embeddings
■ On s’entraîne sur un ensemble de sommets (ie : des graphes de calcul)
■ On génère des embeddings pour les sommets… et même pour ceux que
l’on n’a pas vu (à l’aide des embeddings/des valeurs dans les couches)
4 | Graph neural networks 4.1 | Graph Convolutional Networks 61/
63
La suite
■ la couche GNN en détail
■ les connexions entre couches GNN
■ l’entraînement de GNNs
■ un peu de formalisme
■ passage à l’échelle
■ limites
■ applications
Références
5 | Références 62/
63
Remerciements
Ce cours doit beaucoup aux ressources suivantes :
■ le cours de Jure Leskovec à Stanford
■ le livre Graph Representation Learning de W. L. Hamilton
Version 1.0 du 31 mai 2021
5 | Références 63/
63