Cluster-GCN : Un algorithme efficace pour l'entraînement de réseaux de neurones convolutifs profonds et larges sur graphes

Le réseau de convolution graphique (Graph Convolutional Network, GCN) a été appliqué avec succès à de nombreuses applications basées sur des graphes ; cependant, l'entraînement d'un GCN à grande échelle reste un défi. Les algorithmes actuels basés sur le gradient stochastique descendante (SGD) souffrent soit d'un coût computationnel élevé qui croît exponentiellement avec le nombre de couches de GCN, soit d'une exigence importante en espace pour conserver l'ensemble du graphe et l'embedding de chaque nœud en mémoire. Dans cet article, nous proposons Cluster-GCN, un nouvel algorithme de GCN qui est adapté à l'entraînement basé sur SGD en exploitant la structure de clustering du graphe. Cluster-GCN fonctionne comme suit : à chaque étape, il échantillonne un bloc de nœuds associé à un sous-graphe dense identifié par un algorithme de clustering de graphe, et restreint la recherche dans le voisinage à ce sous-graphe. Cette stratégie simple mais efficace améliore considérablement l'efficacité mémoire et computationnelle tout en permettant d'atteindre une précision de test comparable aux algorithmes précédents. Pour tester la scalabilité de notre algorithme, nous avons créé un nouveau jeu de données Amazon2M comprenant 2 millions de nœuds et 61 millions d'arêtes, ce qui est plus de 5 fois plus grand que le précédent ensemble de données publiquement disponible le plus important (Reddit). Pour entraîner un GCN à 3 couches sur ces données, Cluster-GCN est plus rapide que l'algorithme VR-GCN précédemment au point le plus avancé (1523 secondes contre 1961 secondes) et utilise beaucoup moins de mémoire (2,2 Go contre 11,2 Go). De plus, pour entraîner un GCN à 4 couches sur ces données, notre algorithme peut terminer en environ 36 minutes tandis que tous les algorithmes existants d'entraînement de GCN échouent en raison du problème d'épuisement mémoire. En outre, Cluster-GCN nous permet d'entraîner des GCNs beaucoup plus profonds sans une charge excessive en temps et en mémoire, ce qui conduit à une meilleure précision des prédictions --- en utilisant un Cluster-GCN à 5 couches, nous obtenons un score F1 au test record sur l'ensemble de données PPI (99,36), alors que le meilleur résultat précédent était de 98,71 selon [16]. Nos codes sont librement accessibles sur https://github.com/google-research/google-research/tree/master/cluster_gcn.