Optimal transport for graph representation learning
Transport optimal pour l'apprentissage de représentation de graphes
Résumé
A key challenge in Machine Learning (ML) is to design models able to learn efficiently from graphs, characterized by nodes with attributes and a prescribed structure encoding their relationships. Graph Representation Learning (GRL) aims to encode these two sources of heterogeneity into a vectorial graph embedding easing downstream tasks. In this field, Optimal Transport (OT) has been successful in providing meaningful comparison between graphs seen as discrete probability distributions. This thesis focuses on GRL through the lens of OT, with both concepts introduced in dedicated chapters.Modern supervised GRL mostly relies on Graph Neural Networks (GNN) which implicitly encode the graph topology via two main elements: node features embedding through message passing, and aggregation with a specialized form of pooling. We introduce in this thesis a novel point of view, which places distances to some learnable graph templates at the core of the graph representation. This distance embedding is constructed by means of an OT distance: the Fused Gromov-Wasserstein (FGW) distance, which simultaneously handles feature and structure dissimilarities by solving a soft graph-matching problem. We postulate that the vector of FGW distances to a set of template graphs, has a strong discriminative power, which is then fed to a non-linear classifier for final predictions. This distance embedding acts as a new pooling layer called TFGW, and can leverage on existing message passing techniques to promote sensible feature representations, learned in an end-to-end fashion. We empirically validate our claim on several graph classification tasks, where our method outperforms both kernels and GNN approaches in terms of expressivity and generalization abilities.Another contribution of this thesis aims at making amenable Dictionary Learning (DL) to graphs dataset analysis, a key tool for unsupervised representation learning. DL explains vector data as a linear combination of a few basic elements, accessing the quality of learned representations via dissimilarities associated with a single ambient space. Since graphs depict their own spaces, we propose the first linear approach adapted to Graph Dictionary Learning (GDL), using (F)GW as the data fitting term. In our work, graphs are modeled as convex combination of graph atoms, estimated via an online stochastic algorithm. GDL is completed by a novel upper-bound that can be used as a fast approximation of FGW in the embedding space. We empirically show the interest of our approach for graphs clustering, classification, completion and for online graph subspace estimation and tracking.Finally, the mass conservation at the core of OT, imposing a coupling between all the nodes from the two compared graphs, has specific implications in GRL. Learning structure and feature representations via FGW is considerably sensitive to the nodes relative importance induced by modeling graphs as probability distributions. Managing this extra degree of freedom, as we made possible, improves (F)GW-based models by adding minimal computational cost in TFGW but significant model complexity for GDL. Thus we propose to address the limits of mass conservation constraints in (F)GW, by introducing a novel OT-based discrepancy, called the semi-relaxed (Fused) Gromov-Wasserstein divergence (sr(F)GW). srFGW provides correspondences between two graphs, while searching for a reweighed subgraph in the target graph at a minimum (F)GW distance from the input. The latter can be estimated more efficiently than (F)GW and competes with methods dedicated to graph partitioning while being more generic. Moreover, estimating a srFGW "barycenter" induces a novel DL, where graphs are embedded as reweighed subgraphs of a single graph atom. srFGW DL competes favorably with other DL-based competitors on various unsupervised tasks, while being considerably faster to compute.
Un défi majeur de l'apprentissage machine est de concevoir des modèles capables d'apprendre efficacement à partir de graphes, constitués de noeuds dotés d'attributs et d'une structure décrivant leurs relations. L'apprentissage de représentation de graphe (ARG) vise à synthétiser ces deux sources d'hétérogénéité dans un vecteur, afin de simplifier son traitement à postériori. Dans ce domaine, le Transport Optimal (TO) fournit des comparaisons pertinentes entre graphes, vus comme des distributions discrètes de probabilité. Cette thèse se concentre sur l'ARG à travers le prisme du TO, tous deux détaillés dans des chapitres dédiés. L'ARG supervisé s'appuie essentiellement sur les réseaux de neurones graphiques (RNG), qui encodent implicitement la topologie du graphe par le raffinement des attributs nodaux via l'information issue de leur voisinage, et l'agrégation de cette information à l'échelle du graphe. Nous introduisons dans cette thèse un nouveau concept, qui considère comme représentation du graphe, des distances à certains graphes templates apprenables. A cette fin, nous exploitons la distance de Fused Gromov-Wasserstein (FGW) issue du TO, qui traite simultanément les dissimilarités entre noeuds et structures, en résolvant un problème de correspondance de noeuds entre les graphes. Ce vecteur de distances possède un fort pouvoir discriminant, qui est ensuite transmis à un classifieur gérant les prédictions finales. Ce vecteur agit telle une couche de RNG, appelée TFGW, et peut se superposer à leurs techniques de raffinement d'attributs nodaux, le tout étant appris simultanément. Nous validons empiriquement notre postulat sur de multiples tâches de classification de graphes, où TFGW surpasse les méthodes à RNG et à noyaux en termes d'expressivité et de capacité de généralisation.Le chapitre suivant étend l'apprentissage de dictionnaire (AD), un outil clé pour l'apprentissage non supervisé de représentation, à l'analyse de graphes. l'AD représente les données vectorielles par des combinaisons linéaires de quelques éléments de base, accédant à la qualité de ces dernières via des dissimilarités associées à un espace ambiant unique. Ainsi, nous proposons la première approche linéaire adaptée à l'AD de graphes (ADG), en utilisant (F)GW comme mesure de qualité. Nous modélisons les graphes tels des combinaisons convexes d'atomes de graphes, estimés grâce à un algorithme stochastique. L'ADG est complété par une nouvelle approximation, facilement calculable, de FGW dans l'espace des représentations. Nous montrons empiriquement l'intérêt de notre approche pour le clustering, la classification, la complétion de graphes, ainsi que le suivi en ligne de sous-espaces de graphes.Enfin, la conservation de la masse au cœur du TO, imposant un couplage entre tous les nœuds des deux graphes comparés, a des implications en ARG. L'apprentissage de structures et d'attributs nodaux via FGW est sensible à l'importance relative des nœuds induite par la modélisation des graphes tels des distributions de probabilité. La gestion de ces pondérations, comme nous l'avons rendu possible, améliore les modèles susmentionnés basés sur (F)GW à des coûts de calcul supplémentaires variables. Ainsi, nous modulons ce principe de conservation, via l'introduction de la divergence de (Fused) Gromov-Wasserstein semi-relachée (sr(F)GW). srFGW fournit des correspondances entre deux graphes, tout en recherchant un sous-graphe repondéré dans le graphe cible à une distance (F)GW minimale de l'entrée. Cette dernière rivalise, en autre, avec les méthodes dédiées au partitionnement de graphes tout en étant plus générique. De plus, l'estimation d'un "barycentre" de srFGW induit un nouvel AD, où les graphes sont intégrés comme des sous-graphes repondérés d'un unique atome de graphe. L'AD srFGW rivalise favorablement avec d'autres concurrents basés sur l'AD dans diverses tâches non supervisées, tout en étant considérablement plus rapide à calculer.
Origine : Version validée par le jury (STAR)