  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.
