Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters

Luc Brogat-Motte, Rémi Flamary, Celine Brouard, Juho Rousu, Florence D’Alché-Buc
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:2321-2335, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-brogat-motte22a, title = {Learning to Predict Graphs with Fused Gromov-{W}asserstein Barycenters}, author = {Brogat-Motte, Luc and Flamary, R{\'e}mi and Brouard, Celine and Rousu, Juho and D'Alch{\'e}-Buc, Florence}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {2321--2335}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/brogat-motte22a/brogat-motte22a.pdf}, url = {https://proceedings.mlr.press/v162/brogat-motte22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters %A Luc Brogat-Motte %A Rémi Flamary %A Celine Brouard %A Juho Rousu %A Florence D’Alché-Buc %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-brogat-motte22a %I PMLR %P 2321--2335 %U https://proceedings.mlr.press/v162/brogat-motte22a.html %V 162 %X 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.
APA
Brogat-Motte, L., Flamary, R., Brouard, C., Rousu, J. & D’Alché-Buc, F.. (2022). Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:2321-2335 Available from https://proceedings.mlr.press/v162/brogat-motte22a.html.

Related Material