Tour d'horizon des méthodes d'apprentissage pour analyser les graphes

* Qu’est-ce que l’Atlas des Synergies Productives ?

Définitions d’un graphe

Un graphe est un ensemble V de n noeuds V=\left\{V_{1}, \ldots, V_{n}\right\} et un ensemble E de connexions (arêtes) entre des paires de noeuds. Un graphe orienté est un graphe dans lequel les arêtes possèdent une orientation. Le degré d’un noeud est le nombre d’arêtes qui entrent ou sortent de ce noeud.

Le codage d’un graphe passe par la création d’une matrice d’adjacence, (b) dans la figure ci-dessous. Cette matrice de dimension n \times n dont l’élément non diagonal a_{ij} est le nombre d’arêtes liant le noeud i au noeud j. Si le graphe est non-orienté, la matrice d’adjacence est symétrique.

Machine learning pour le clustering dans les graphes

Dans cette section, nous présentons quelques méthodes d’apprentissage non supervisées basées sur les graphes. Ces algorithmes peuvent aussi contribuer à la visualisation des graphes dans des espaces latents. Mais dans cet article, nous insisterons sur le clustering de graphes. Ces méthodes cherchent à regrouper des nœuds, c’est-à-dire à créer des communautés ou des clusters. Ces algorithmes se concentrent sur l’extraction de connaissances à partir des topologies des graphes.

Modularité

La modularité est une mesure de la qualité d’un partitionnement des nœuds d’un graphe. Ce principe implique un nombre d’arêtes intra-communautaires important et un nombre d’arêtes inter-communautaires faible. En d’autres termes, il y a davantage de connexions entre des nœuds d’une même communauté qu’entre des nœuds de communautés différentes.

Ce score compare, pour un groupe de nœuds, le nombre d’arêtes réelles par rapport au nombre d’arêtes espérées (dans un graphe équivalent où les arêtes sont placées de façon aléatoire comme le modèle d’Erdös-Rényi en 1959). S’il y a davantage d’arêtes réelles qu’espérées, alors on pourrait avoir une communauté. On obtient ainsi un score de division d’un graphe défini par la formule suivante :

Q=\frac{1}{2 m} \sum_{i, j}\left(A_{i j}-P_{i j}\right) \delta\left(C_{i}, C_{j}\right)

• A_{ij}, est la valeur ij de la matrice d’adjacence A.
• m est le nombre d’arête (2m est donc le nombre total de demi-arête).
• \delta est le delta de Kronecker :
  • \delta\left(C_{i}, C_{j}\right) = 1 si i et j sont dans la même communauté C, c’est à dire C_{i} = C_{j}.
  • \delta\left(C_{i}, C_{j}\right) = 0 sinon.
• P_{ij} est l’espérance du nombre de connexions entre i et j, sous un modèle nul d’Erdös-Rényi qui produit un graphe homogène.

Ainsi, maximiser la modularité Q revient à chercher des groupes de nœuds comptabilisant entre eux un nombre de connexions anormalement élevé.

La modularité est la base fondamentale d’extraction de communautés applicable aux graphes. La méthode de Louvain (Blondel et al. 2008) est particulièrement adaptée pour traiter de larges volumes de données.

• La première phase de la méthode de Louvain consiste à trouver de petites communautés par optimisation locale de la modularité sur chacun des nœuds.
• Dans un second temps, les nœuds d’une même communauté sont regroupés en un unique nœud, et la première phase est répétée sur le réseau nouvellement obtenu.
• Les itérations sont répétées jusqu’à ce qu’aucune augmentation de la modularité ne soit possible.

Stochastic block model (SBM)

Les SBM sont des modèles génératifs pour les graphes aléatoires. Ces modèles produisent des graphes contenant des communautés, avec des sous-ensembles de nœuds caractérisés par leurs connections les uns aux autres avec des densités d’arêtes particulières. Pour générer un graphe aléatoire, le SBM a besoin de trois paramètres :

• n, le nombre de nœuds.
• Une partition de l’ensemble de nœuds réparti en communautés selon une loi multinomiale. Z_{i} \sim \mathcal{M}\left(1, \alpha=\left(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{K}\right)\right) où K est le nombre de communautés et \alpha est la probabilité d’appartenir à la communauté.
• La matrice des probabilités \mu_{kl}, où les éléments diagonaux correspondent à la probabilité que les nœuds se connectent en interne, au sein même de la communauté. Les autres éléments correspondent à la probabilité de connexion entre les communautés.

La génération d’un graphe avec un modèle SBM est simple. Par contre, l’estimation de tous les paramètres du modèle SBM comme \mu_{kl} et \alpha est un défi ! En effet, les algorithmes d’optimisation standard, tel que l’algorithme espérance-maximisation (pour obtenir les paramètres du maximum de vraisemblance), ne peuvent pas être dérivés. Pour résoudre ce problème, des approximations variationnelles et stochastiques existent comme les méthodes bayésiennes variationnelles (Latouche et al 2012).

Comparaison des méthodes pour du clustering

Ces deux approches fournissent des résultats divers sur un même graphe.

• En effet, la modularité (figure à droite) illustre deux communautés dont les noeuds sont fortement connectés en interne. Par contre, il y a peu de connections entre les nœuds de communautés différentes.
• Le SBM (figure à gauche) identifie des clusters différents apportant de nouvelles informations. Les nœuds bleus sont des hubs, ils ont un nombre de degrés par nœud important. Tandis que le cluster rouge a un nombre de degrés faible. Ses nœuds sont peu connectés entre eux mais régulièrement reliés aux bleus en formant des graphes en étoile. La force du modèle SBM est de fournir les probabilités de connections \mu_{kl} entre les différents nœuds selon leur cluster d’affectation.

Deep learning pour les graphes

Graph Neural Networks

Les méthodes classiques de deep learning comme celles présentées lors de nos travaux précédents sur les prédictions ne peuvent pas s’appliquer aux données de graphes. En effet, les outils de deep learning fonctionnent habituellement avec des données structurées (séries temporelles, images via les pixels, textes, etc). Cependant, les graphes peuvent avoir une taille arbitraire, des caractéristiques multimodales et une topologie complexe.

Ainsi, les Graph Neural Networks (GNN) sont des algorithmes de deep learning qui induisent des caractéristiques à partir de données de graphes. Ces inférences sont directement utilisables pour des prédictions, classifications ou d’autres approches.

Pour exploiter les données de graphes, les GNN s’appuient sur l’hypothèse selon laquelle de nombreux éléments d’information d’un nœud résident dans son voisinage. Pour stocker ces données, nous utilisons les « Node Embedding » qui rassemblent les informations du voisinage avec des réseaux de neurones multicouches (MLP).

Ainsi, un GNN utilise un MLP sur chaque voisin d’un nœud : nous appelons cela une couche GNN. Dans la figure ci-dessous, il y a donc deux couches : une première pour les voisins de A qui découle elle-même d’une deuxième couche concernant les voisins des voisins. Pour l’ensemble des informations du nœud (son vecteur), nous appliquons le MLP (blocs gris/noirs dans la figure) et récupérons un nouveau vecteur de nœud appris. Nous faisons de même pour les arêtes lorsqu’elles contiennent des informations (plusieurs types d’arêtes, valeurs, poids, etc).

La formule suivante indique comment les informations d’entrée (du nœud cible h_{i}^{t} et de ses voisins h_{j}^{t}) seront agrégées par les réseaux de neurones et produiront la nouvelle représentation h_{i}^{t+1}. C’est ce mécanisme que l’on retrouve au sein des blocs gris et noirs dans la figure ci-dessus.

h_{i}^{t+1}=\sigma\left(h_{i}^{t} W+\sum_{j \in N(i)} \frac{1}{c_{i j}} h_{j}^{t} U\right)

• h_{i}^{t} est le vecteur initial contenant les informations du nœud h_{i}.
• h_{i}^{t+1} est le vecteur mis à jour contenant les informations des voisins mais aussi la topologie du graphe. Cela permet d’avoir plus d’informations et une meilleure représentation du nœud h_{i} au sein du graphe.
• W est la matrice des poids provenant d’un réseau de neurones (MLP) identifiant les éléments importants à garder au sein du vecteur initial h_{i}^{t}.
• U est aussi une matrice de poids provenant d’un réseau de neurones mais qui va traiter les vecteurs des nœuds voisins h_{j}^{t}.
• \sum_{j \in N(i)} \frac{1}{c_{i j}} est une fonction d’agrégation, cette somme normalise les représentations voisines N(i). Cela passe par une fonction invariante par permutation de ses variables car nous devons être insensible à l’ordre des voisins afin d’avoir le même résultat, quel que soit l’ordre des voisins.
• \sigma est une fonction d’activation.

L’application de cette fonction de manière itérative fournit de meilleures représentations des nœuds au sein de leur environnement, c’est-à-dire dans le graphe. À partir de ces nouveaux vecteurs, nous pouvons faire de la prédiction de liens entre les nœuds, du clustering de nœuds ou de sous-graphes, etc.

Graph Convolutional Network (GCN)

La méthode détaillée dans la section précédente ressemble fortement au Convolutional Neural Networks (CNN) pour les images. Il s’agit fondamentalement de la même opération pour les GCN. Cela consiste alors à multiplier les neurones d’entrée avec un ensemble de poids appelé « masques ». Ces masques agissent comme une fenêtre coulissante sur toute l’image et permettent aux CNN d’apprendre les caractéristiques des pixels voisines. Au sein du même calque, le même filtre sera utilisé dans toute l’image. Par exemple, en utilisant CNN sur les images, le même masque sera utilisé dans la même couche pour détecter les différentes parties d’une image.

Pour les graphes les GCN effectuent des opérations similaires où le modèle apprend les caractéristiques en inspectant les nœuds voisins. La principale différence entre les CNN et les GCN réside dans le fait que les CNN sont spécialement conçus pour fonctionner sur des données structurées, euclidiennes, comme les images. Tandis que les GCN désignent une version généralisée des CNN où le nombre de connexions de nœuds varie, par ailleurs ces derniers ne sont pas ordonnés (irréguliers, car un graphe a une structure non euclidienne). Cette méthode a été popularisée par les travaux de Kipf et Welling en 2017.

Graphes dynamiques

Si la plupart des techniques existantes ne s’appliquent qu’aux graphes statiques, où les arêtes n’évoluent pas dans le temps, des développements récents ont montré qu’elles pouvaient être étendues aux réseaux en évolution comme les Temporal Graph Networks (TGN) (Rossi et al 2020). Dans un contexte supervisé, on cherche généralement à inférer des étiquettes ou des valeurs numériques attachées aux nœuds et arêtes en utilisant à la fois le graphe et, lorsqu’elles sont disponibles, les caractéristiques de ces nœuds/arêtes.

Librairies Python et R

Pour utiliser ces méthodes complexes, plusieurs librairies ont été implémentées afin de rendre leur programmation plus simple.

Pour la modularité et les SBM :

• Sur Python : avec la librairie NetworkX ou bien Scikit-network
• Sur R : la librairie igraph, blockmodels et sna

Pour les méthodes de deep learning :

• Deep Graph Library (DGL) est un package Python pour l’apprentissage profond sur les graphes. DGL peut être implémenté avec des backend, comme PyTorch, TensorFlow ou MXNet.
• PyTorch Geometric