Les modèles de réseaux de neurones convolutifs sous forme de graphe (GCN) se montrent particulièrement efficaces dans le cadre de l’apprentissage semi-supervisé. Les chercheurs Jie Chen, Tengfei Ma et Cao Xiao ont récemment proposé sur Arxiv leurs recherches intitulées Fast Learning with Graph Convolutional Networks via Importance Sampling. Ils y indiquent que les GCN proposés par Kipf et Wellling sont très performants mais ont été à l’origine développés pour être entraînés avec à la fois un jeu d’entraînement et un jeu de test.
Ces modèles requièrent beaucoup de temps et de mémoire quand il s’agit d’entraîner d’importants graphes. La méthode proposée par Jie Chen, Tengfei Ma et Cao Xiao propose d’interpréter les circonvolutions des graphes comme des transformations intégrales des fonctions d’intégration, sous les mesures de probabilité, permettant ainsi de réduire l’exigence de disponibilité simultanée des données de test. Comme l’indiquent les chercheurs, “une telle interprétation permet d’utiliser la méthode de Monte Carlo afin d’estimer de manière cohérente les intégrales, ce qui conduit au schéma d’apprentissage par lots que nous proposons dans ce travail sur les FastGCN. Amélioré avec l’échantillonnage d’importance, FastGCN est non seulement efficace pour l’entraînement, mais il généralise également bien l’inférence. Selon les auteurs, la méthode proposée permet de réduire par un facteur de 10 ou plus la charge de l’entraînement tout en obtenant des performances de même ordre. Résultats illustrés par un ensemble complet d’expériences pour démontrer l’efficacité des FastGCN face aux GCN et aux modèles connexes.
Dans un article repris par Phys.org, Jie Chen d’IBM explique :
“Une structure de graphe est extrêmement utile pour prédire les propriétés de ses constituants. Le moyen le plus efficace d’effectuer cette prédiction consiste à cartographier chaque entité en un vecteur à l’aide de réseaux de neurones profonds. On peut déduire la similarité de deux entités en fonction de la proximité du vecteur. Un défi pour le deep learning, cependant car on a besoin de rassembler des informations entre une entité et son voisinage étendu à travers les couches du réseau de neurones. Le voisinage se développe rapidement, ce qui rend le calcul très coûteux.
Pour résoudre ce problème, nous proposons une nouvelle approche, validée par des preuves mathématiques et des résultats expérimentaux, qui suggère qu’il est suffisant de rassembler les informations de quelques entités aléatoires dans chaque extension. Cette réduction substantielle de la taille du voisinage permet d’obtenir la même qualité de prédiction que les réseaux neuronaux de pointe mais réduit le coût de l’entrainement par ordre de grandeur (par exemple, 10x à 100x moins de temps de calcul et de ressources)”.
Le GCN a de nombreuses applications et permet notamment de généraliser le concept de convolution pour les images, qui peuvent être considérées comme une grille de pixels, à des graphes qui ne ressemblent plus à une grille traditionnelle.
Pour comprendre cela, il faut comprendre ce qu’est un filtre de convolution. En ce qui concerne les images, il s’agit d’une petite matrice de nombres, à multiplier par élément avec une fenêtre mobile de l’image, la somme de produit résultante remplaçant le numéro du centre de la fenêtre. Il faut disposer d’une bonne combinaison de filtres afin de pouvoir détecter des structures locales primitives, telles que des lignes dans différents angles, bords, coins et points d’une certaine couleur. [Voir l’explication détaillée de Thibault Neveu]
“Pour les graphs, les circonvolutions sont similaires. Imaginez que chaque noeud graphique est initialement attaché à un vecteur. Pour chaque nœud, les vecteurs des voisins lui sont ajoutés (avec certains poids et transformations). Ainsi, tous les nœuds sont mis à jour simultanément, en réalisant ensuite une couche de propagation. Les convolutions de graphe peuvent être utilisées pour propager des informations à travers des voisinages de sorte que des informations globales soient disséminées sur chaque noeud de graphe”.
“Le problème avec les GCN peuvent survenir lorsque les réseaux ont plusieurs couches. En effet, le voisinage est rapidement étendu, impliquant de nombreux vecteurs à additionner, même pour un seul nœud. Un tel calcul est prohibitif pour les graphes avec un grand nombre de nœuds. […]”
L’équipe de chercheurs a donc travaillé sur un correctif qu’ils ont appelé FastGCN. L’idée de base est que si l’agrandissement complet du quartier est coûteux, pourquoi ne pas développer seulement quelques voisins à chaque fois?
“L’échantillonnage réduit considérablement le coût de l’entraînement du réseau de neurones, en réduisant le temps d’entraînement par ordre de grandeur sur les ensembles de données de référence couramment utilisés par les chercheurs. Pourtant, les prédictions restent relativement précises. La taille de ces graphes de référence varie de quelques milliers de nœuds à quelques centaines de milliers de nœuds, confirmant l’évolutivité de notre méthode”.
Jie Chen, Tengfei Ma et Cao Xiao ont développé cette approche intuitive à partir d’une théorie mathématique pour l’approximation de la fonction de perte.
“Une couche du réseau peut être résumée comme une multiplication matricielle : H’=s (AHW), où A est la matrice d’adjacence du graphe, chaque rangée de H est le vecteur attaché aux noeuds, W est une transformation linéaire des vecteurs (également interprétée comme le paramètre du modèle à apprendre), et les lignes de H’ contiennent les vecteurs mis à jour. Nous généralisons cette multiplication matricielle à une transformation intégrale h'(v)= s(òA(v,u)h(u)W dP(u)) sous une mesure de probabilité P. Ensuite, l’échantillonnage d’un nombre fixe de voisins dans chaque expansion n’est rien d’autre qu’une approximation de Monte Carlo de l’intégrale sous la mesure P. L’approximation de Monte Carlo donne un estimateur cohérent de la fonction de perte; par conséquent, en prenant le gradient, nous pouvons utiliser une méthode d’optimisation standard (telle que la descente de gradient stochastique) pour former le réseau de neurones”.
L’approche de ces trois chercheurs traite d’un défi important en matière de deep learning pour les graphes à grande échelle. En effet, elle peut être utilisée non seulement pour les GCN mais également pour d’autres types de réseaux de neurones se basant sur le concept d’expansion de voisinage. Il s’agit d’une composante essentielle de l’apprentissage de la représentation graphique.
“Nous prévoyons que la résolution du défi dans cette structure de données fondamentales – les graphes – sera adoptée dans un large éventail d’applications, y compris l’analyse de réseaux sociaux, la connaissance approfondie des interactions protéine-protéine pour la découverte de médicaments, la curation et la découverte d’informations dans les bases de connaissances”.
