This paper introduces a novel and generic frame- work to solve the flagship task of supervised la- beled 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 rely- ing on a FGW barycenter whose weights depend on inputs. First we introduce a non-parametric es- timator based on kernel ridge regression for which theoretical results such as consistency and excess risk bound are proved. Next we propose an inter- pretable parametric model where the barycenter weights are modeled with a neural network and the graphs on which the FGW barycenter is cal- culated 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.