L’apprentissage automatique apprivoise les graphes
⏱ 5 minAprès les images et le texte, l’apprentissage automatique enregistre depuis peu des résultats encourageants dans le traitement des graphes. Des réseaux sociaux aux relations entre molécules dans le vivant, les graphes sont partout, et les applications potentielles sont donc innombrables.
Les progrès les plus spectaculaires de l’apprentissage automatique ont d’abord surtout concerné le traitement d’images (vision artificielle) et de textes (traitement automatique du langage). Ou encore les séries temporelles (notamment pour le traitement de la parole). De multiples difficultés entravaient les tentatives visant à traiter des problèmes manipulant d’autres types de données structurées. Parmi elles, les graphes. Le graphe est pourtant un concept mathématique puissant, permettant de formaliser des relations entre entités, et de nombreux problèmes portent sur des données susceptibles d’être représentées par des graphes. Mais depuis peu, des solutions d’apprentissage automatique émergent pour traiter ce type de problèmes. Le « Graph ML » (pour Graph Machine Learning) est désormais un thème très présent dans les conférences portant sur l’apprentissage automatique.
« Toutes sortes de données se prêtent à une représentation à l’aide de graphes, confirme Marc Lelarge, chercheur Inria au sein de l’équipe Dyogène (Inria Paris-Rocquencourt) mais aussi du 3IA (Institut interdisciplinaire d’intelligence artificielle) Prairie (PaRis AI Research InstitutE). Si l’on cherche à représenter qui est en relation avec qui sur un réseau social, par exemple, on obtient un graphe. Et immédiatement, on songe à des applications capables de traiter ce type de données pour répondre à des questions portant sur ces relations entre personnes, ce qu’elles échangent… On voudra par exemple détecter des communautés échangeant sur un sujet particulier, cerner la communauté des antivax ou des amateurs de tango. »
Des nœuds et des arêtes
Le graphe est un objet mathématique constitué d’un ensemble de nœuds, qui peuvent représenter toutes sortes d’abstractions (un individu sur un réseau social, un atome dans une molécule…), et d’un ensemble d’arêtes entre deux nœuds représentant une relation entre eux. On distingue le graphe non-orienté, dans lequel les arêtes reliant deux nœuds représentent une relation symétrique (x est ami avec y et réciproquement), du graphe orienté, où les nœuds sont reliés par des flèches, représentant une relation asymétrique (x a « partagé » un « post » de y). Les choses se compliquent lorsque les arêtes ou les flèches se voient attribuer une valeur numérique, un « poids », qui peut représenter une probabilité par exemple. Et bien d’autres suppléments d’âme permettent de construire des objets mathématiques encore plus complexes, comme le laisse entendre leur nom : multigraphe, hypergraphe, etc.
« Les graphes sont omniprésents », insiste Marc Lelarge. Et de ce fait, les applications de l’apprentissage automatique appliqué aux graphes sont potentiellement innombrables. Un graphe peut représenter toutes sortes de réseaux, de transport des personnes ou des marchandises, de l’électricité ou du gaz, et bien sûr de l’information. Il peut encore représenter les échanges entre comptes bancaires, les relations entre les atomes d’une molécule, des interactions entre molécules dans le vivant… « Et les applications vont du ciblage publicitaire, visant les amateurs de foot ou de chocolat, de la détection de fraudes, d’activités criminelles, voire terroristes… à la découverte de médicaments ou de bien d’autres choses, ajoute le chercheur. »
Comment représenter les graphes ?
Une première difficulté pour passer les graphes à la moulinette de l’outillage de l’apprentissage automatique s’impose dès le départ : comment les représenter ? Après une période de tâtonnement, au cours de laquelle on a fait appel à des solutions ad hoc, visant à extraire des caractéristiques (« features ») structurelles des graphes, des techniques faisant appel au machine learning lui-même sont apparues. Les dernières années ont vu s’imposer des approches permettant l’apprentissage automatique de représentations. « Le Graph Representation Learning est un thème de recherche en soi, explique Michal Valko, chercheur au sein de l’équipe parisienne de DeepMind et membre de l’équipe Sequel à Inria Lille – Nord Europe. Il vise à traduire un graphe en un vecteur dans un espace de dimension élevée. On parle de « plongement » ou embedding. Dès 2016, une équipe de Stanford proposait ainsi node2vec¹, qui réalise ce type de plongement. »
« Les premiers résultats encourageants en Graph ML remontent à cinq ans, indique Marc Lelarge. En 2016, des travaux² présentés à la conférence NeurIPS par une équipe de l’EPFL (École Polytechnique Fédérale de Lausanne) ont montré que l’on pouvait traiter des graphes à l’aide de réseaux neuronaux convolutifs. Peu après, les résultats³ d’une équipe de l’université d’Amsterdam, aux Pays-Bas, présentés à ICLR 2017 (International Conference on Learning Representations), ont confirmé le potentiel de l’approche. » Le « Graph Convolutional Network » (GCN) généralise le CNN (Convolutional Neural Network) aux graphes. Au lieu d’opérer sur les pixels ou les mots mitoyens, comme on le fait pour les images ou le texte, la convolution prend en compte pour chaque nœud un voisinage défini par les nœuds directement reliés par une arête.
Des réseaux de neurones adaptés aux graphes
Xavier Bresson est aujourd’hui professeur associé à la School of Computing de la National University of Singapore. Alors qu’il était chercheur à l’EPFL, il a cosigné cette publication² de 2016 qui a réussi à utiliser des CNN sur des graphes. « Les premières tentatives pour travailler sur des graphes faisaient appel à des types de réseaux de neurones bien connus, se souvient le chercheur. Comme les perceptrons multicouches, où chaque neurone est connecté à tous les neurones de la couche précédente. En gros, cela ne marchait pas. Les premiers résultats intéressants ont donc été obtenus avec les réseaux de neurones convolutifs (CNN), mais aussi les réseaux de neurones récurrents (RNN), notamment les LSTM (Long Short-Term Memory). »
On distingue, aujourd’hui, divers types de Graph Neural Networks (GNNs). Après le Graph Convolutional Network (GCN) est apparu le Graph Attention Network (GAT), inspiré du transformer et du mécanisme d’attention⁴. La liste ne cesse de s’allonger. Xavier Bresson a, par exemple, cosigné tout récemment une publication⁵ proposant un nouveau type de GNN, le Multigraph Transformer (MGT), adapté en particulier à l’apprentissage de représentations de croquis (« free-hand sketch »). On peut supposer que le darwinisme éclaircira cette abondante floraison. « Nous avons un papier⁶ accepté à ICLR 2021 [International Conference on Learning Representations, NDLR] qui propose un cadre théorique permettant de comparer le pouvoir d’expression de ces diverses architectures de GNN », signale Marc Lelarge.
Un thème de recherche très actif
« L’apprentissage supervisé marche bien sur les graphes, précise Marc Lelarge, quand on dispose de beaucoup de données étiquetées. Si les données dont on dispose ne sont pas ou peu étiquetées, l’apprentissage auto-supervisé est une solution qui donne de bons résultats : tout comme on le fait en traitement du langage ou en vision artificielle, on peut entraîner un modèle à prédire une partie des graphes que l’on a aléatoirement cachée. » Les travaux d’une équipe dirigée par Michal Valko sur une transposition de son approche d’apprentissage auto-supervisé BYOL (Bootstrap Your Own Latent) au Graph ML ont été présentés⁷ au workshop GTRL (Geometrical and Topological Representation Learning) de ICLR 2021 (International Conference on Learning Representations).
Le GraphML est donc, depuis deux ans, un thème de recherche très actif. « Pour la conférence NeurIPS 2019, une centaine de publications sur le Graph ML avaient déjà été retenues, indique Michal Valko. Et les applications se multiplient. Ainsi, depuis septembre 2020, la fonction de Google Maps qui fournit une estimation de l’heure d’arrivée à l’issue d’un trajet fait appel au Graph ML. La biologie offre également de nombreux exemples de réseaux susceptible d’être représentés par des graphes, comme les interactions entre molécules, à l’échelle de la cellule ou d’un organisme. AlphaFold, l’algorithme de DeepMind [filiale de Google, NDLR]qui prédit la structure tridimensionnelle des protéines, fait appel au Graph ML… » Il semble qu’aucune discipline n’échappera aux progrès du Graph ML…
Pierre Vandeginste
Image a la une : Représentation d’un échantillon du web Californien. Crédit Xavier Bresson.
1. Aditya Grover, Jure Leskovec, “Node2vec: Scalable Feature Learning for Networks”, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016. arXiv
2. Michaël Defferrard, Xavier Bresson, Pierre Vandergheynst, “Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering”, NeurIPS 2016. arXiv
3. Thomas N. Kipf, Max Welling, « Semi-Supervised Classification with Graph Convolutional Networks. », ICLR 2017. arXiv
4. Dzmitry Bahdanau, Kyunghyun Cho, Yoshua Bengio, « Neural machine translation by jointly learning to align and translate », ICLR 2015. arXiv
5. Peng Xu, Chaitanya Joshi, Xavier Bresson, “Multigraph transformer for free-hand sketch recognition”, IEEE Transactions on Neural Networks and Learning Systems, 2021. arXiv
6. Waiss Azizian, Marc Lelarge, “Expressive Power of Invariant and Equivariant Graph Neural Networks”, ICLR 2021. arXiv
7. Shantanu Thakoor et al., “Bootstrapped Representation Learning on Graphs”, GTRL Workshop, ICLR 2021 arXiv
