Apprentissage en ligne du dictionnaire de graphe

L’apprentissage de dictionnaire constitue un outil fondamental pour l’apprentissage de représentations, permettant d’expliquer les données comme une combinaison linéaire de quelques éléments fondamentaux. Toutefois, cette approche n’est pas directement applicable dans le cadre de l’apprentissage de graphes, lesquels appartiennent généralement à des espaces métriques distincts. Nous comblons cette lacune en proposant une nouvelle méthode d’apprentissage de dictionnaire en ligne pour graphes, qui utilise la divergence de Gromov-Wasserstein comme terme d’ajustement aux données. Dans notre approche, les graphes sont représentés par les relations appariées entre leurs nœuds et modélisés comme une combinaison convexe d’atomes de graphes — c’est-à-dire des éléments du dictionnaire — estimés à l’aide d’un algorithme stochastique en ligne, opérant sur un ensemble de données de graphes non alignés, pouvant présenter un nombre de nœuds différent. Notre méthode s’étend naturellement aux graphes étiquetés, et est complétée par une nouvelle borne supérieure pouvant servir d’approximation rapide de la distance de Gromov-Wasserstein dans l’espace d’embedding. Nous fournissons des preuves numériques mettant en évidence l’intérêt de notre approche pour l’embedding non supervisé de jeux de données de graphes, ainsi que pour l’estimation et le suivi en ligne du sous-espace des graphes.