Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters
This paper introduces a novel and generic framework to solve the flagship task of supervised labeled graph prediction by leveraging Optimal Transport tools. We formulate the problem as regression with the Fused Gromov-Wasserstein (FGW) loss and propose a predictive model relying on a FGW barycenter whose weights depend on inputs. First we introduce a non-parametric estimator based on kernel ridge regression for which theoretical results such as consistency and excess risk bound are proved. Next we propose an interpretable parametric model where the barycenter weights are modeled with a neural network and the graphs on which the FGW barycenter is calculated are additionally learned. Numerical experiments show the strength of the method and its ability to interpolate in the labeled graph space on simulated data and on a difficult metabolic identification problem where it can reach very good performance with very little engineering.
Code (1)
Tasks
regressionSimilar Papers 제목 키워드 기반
Privacy-Preserved Evolutionary Graph Modeling via Gromov-Wasserstein Autoregression
Real-world graphs like social networks are often evolutionary over time, whose observations at different timestamps lead to graph sequences. Modeling such evolutionary graphs is important for many applications, but solvi…
Privacy PreservingLearning Graphons via Structured Gromov-Wasserstein Barycenters
We propose a novel and principled method to learn a nonparametric graph model called graphon, which is defined in an infinite-dimensional space and represents arbitrary-size graphs. Based on the weak regularity lemma fro…
LEMMAOptimal Transport for structured data with application on graphs
This work considers the problem of computing distances between structured objects such as undirected graphs, seen as probability distributions in a specific metric space. We consider a new transportation distance (i.e. t…
ClusteringGraph ClassificationGraph ClusteringTime Series AnalysisOrthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound
Comparing structured data from possibly different metric-measure spaces is a fundamental task in machine learning, with applications in, e.g., graph classification. The Gromov-Wasserstein (GW) discrepancy formulates a co…
Graph ClassificationGromov-Wasserstein Factorization Models for Graph Clustering
We propose a new nonlinear factorization model for graphs that are with topological structures, and optionally, node attributes. This model is based on a pseudometric called Gromov-Wasserstein (GW) discrepancy, which com…
ClusteringGraph ClusteringRolling Shutter Correction