Cleora : Un schéma d’embedding de graphe simple, robuste et évolutif

Le domaine des embeddings de graphes est actuellement dominé par les méthodes d’apprentissage contrastif, qui nécessitent la formulation d’une fonction objectif explicite ainsi que l’échantillonnage d’exemples positifs et négatifs. Cela engendre un surcroît conceptuel et computationnel significatif. Des approches classiques et simples, telles que l’analyse en composantes principales multidimensionnelles (MDS) ou les eigenmaps de Laplace, évitent cette complexité en s’appuyant directement sur la géométrie des données, sans avoir recours à une optimisation d’objectif fastidieuse. Malheureusement, leur dépendance à des opérations très coûteuses, comme la décomposition en valeurs propres de matrices, les rend inadaptées à l’échelle des grands graphes courants dans le monde numérique actuel. Dans cet article, nous présentons Cleora : un algorithme qui combine les avantages des deux mondes, en étant à la fois non supervisé et hautement évolutif. Nous démontrons qu’il est possible de produire des embeddings de haute qualité sans recourir au cadre d’apprentissage pas à pas traditionnel, ni à l’échantillonnage d’exemples. L’objectif d’apprentissage intuitif de notre algorithme repose sur le principe selon lequel un nœud doit être similaire à ses voisins, sans pour autant pousser explicitement les nœuds non connectés à s’éloigner. Cet objectif est atteint par une moyenne pondérée itérative des embeddings de voisins, suivie d’une normalisation sur les dimensions. Grâce à l’opération de moyennage, l’algorithme progresse rapidement dans l’espace d’embeddings et atteint généralement des solutions optimales en quelques itérations seulement. Cleora s’exécute plus rapidement que d’autres algorithmes d’état de l’art sur processeur (CPU) et produit des embeddings de qualité compétitive, évaluée sur des tâches en aval telles que la prédiction de liens et la classification de nœuds. Nous montrons que Cleora apprend une abstraction des données comparable à celle des méthodes contrastives, tout en imposant un coût computationnel bien moindre. Cleora est mis à disposition sous licence MIT, autorisant une utilisation commerciale, via le dépôt GitHub suivant : https://github.com/Synerise/cleora.