Gromov-Wasserstein Averaging of Kernel and Distance Matrices

Gabriel Peyré, Marco Cuturi, Justin Solomon
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2664-2672, 2016.

Abstract

This paper presents a new technique for computing the barycenter of a set of distance or kernel matrices. These matrices, which define the inter-relationships between points sampled from individual domains, are not required to have the same size or to be in row-by-row correspondence. We compare these matrices using the softassign criterion, which measures the minimum distortion induced by a probabilistic map from the rows of one similarity matrix to the rows of another; this criterion amounts to a regularized version of the Gromov-Wasserstein (GW) distance between metric-measure spaces. The barycenter is then defined as a Fréchet mean of the input matrices with respect to this criterion, minimizing a weighted sum of softassign values. We provide a fast iterative algorithm for the resulting nonconvex optimization problem, built upon state-of- the-art tools for regularized optimal transportation. We demonstrate its application to the computation of shape barycenters and to the prediction of energy levels from molecular configurations in quantum chemistry.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-peyre16, title = {Gromov-Wasserstein Averaging of Kernel and Distance Matrices}, author = {Peyré, Gabriel and Cuturi, Marco and Solomon, Justin}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2664--2672}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/peyre16.pdf}, url = {https://proceedings.mlr.press/v48/peyre16.html}, abstract = {This paper presents a new technique for computing the barycenter of a set of distance or kernel matrices. These matrices, which define the inter-relationships between points sampled from individual domains, are not required to have the same size or to be in row-by-row correspondence. We compare these matrices using the softassign criterion, which measures the minimum distortion induced by a probabilistic map from the rows of one similarity matrix to the rows of another; this criterion amounts to a regularized version of the Gromov-Wasserstein (GW) distance between metric-measure spaces. The barycenter is then defined as a Fréchet mean of the input matrices with respect to this criterion, minimizing a weighted sum of softassign values. We provide a fast iterative algorithm for the resulting nonconvex optimization problem, built upon state-of- the-art tools for regularized optimal transportation. We demonstrate its application to the computation of shape barycenters and to the prediction of energy levels from molecular configurations in quantum chemistry.} }
Endnote
%0 Conference Paper %T Gromov-Wasserstein Averaging of Kernel and Distance Matrices %A Gabriel Peyré %A Marco Cuturi %A Justin Solomon %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-peyre16 %I PMLR %P 2664--2672 %U https://proceedings.mlr.press/v48/peyre16.html %V 48 %X This paper presents a new technique for computing the barycenter of a set of distance or kernel matrices. These matrices, which define the inter-relationships between points sampled from individual domains, are not required to have the same size or to be in row-by-row correspondence. We compare these matrices using the softassign criterion, which measures the minimum distortion induced by a probabilistic map from the rows of one similarity matrix to the rows of another; this criterion amounts to a regularized version of the Gromov-Wasserstein (GW) distance between metric-measure spaces. The barycenter is then defined as a Fréchet mean of the input matrices with respect to this criterion, minimizing a weighted sum of softassign values. We provide a fast iterative algorithm for the resulting nonconvex optimization problem, built upon state-of- the-art tools for regularized optimal transportation. We demonstrate its application to the computation of shape barycenters and to the prediction of energy levels from molecular configurations in quantum chemistry.
RIS
TY - CPAPER TI - Gromov-Wasserstein Averaging of Kernel and Distance Matrices AU - Gabriel Peyré AU - Marco Cuturi AU - Justin Solomon BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-peyre16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2664 EP - 2672 L1 - http://proceedings.mlr.press/v48/peyre16.pdf UR - https://proceedings.mlr.press/v48/peyre16.html AB - This paper presents a new technique for computing the barycenter of a set of distance or kernel matrices. These matrices, which define the inter-relationships between points sampled from individual domains, are not required to have the same size or to be in row-by-row correspondence. We compare these matrices using the softassign criterion, which measures the minimum distortion induced by a probabilistic map from the rows of one similarity matrix to the rows of another; this criterion amounts to a regularized version of the Gromov-Wasserstein (GW) distance between metric-measure spaces. The barycenter is then defined as a Fréchet mean of the input matrices with respect to this criterion, minimizing a weighted sum of softassign values. We provide a fast iterative algorithm for the resulting nonconvex optimization problem, built upon state-of- the-art tools for regularized optimal transportation. We demonstrate its application to the computation of shape barycenters and to the prediction of energy levels from molecular configurations in quantum chemistry. ER -
APA
Peyré, G., Cuturi, M. & Solomon, J.. (2016). Gromov-Wasserstein Averaging of Kernel and Distance Matrices. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2664-2672 Available from https://proceedings.mlr.press/v48/peyre16.html.

Related Material