Numerical
Optimal Transport
http://optimaltransport.github.io

Gromov Wasserstein
Gabriel Peyré
www.numerical-tours.com
ÉCOLE NORMALES U P É R I E U R E

Overview• Gromov Wasserstein• Entropic Regularization• Applications• GW Barycenters

Gromov-Wasserstein
Inputs: {(similarity/kernel matrix, histogram)}Def. Gromov-Wasserstein distance:[Memoli 2011][Sturm 2012]

Y! NP-hard in general.
! need for a fast approximate solver.

unregisteredspaces

XGromov-Wasserstein as a MetricyjxiDef.

XYfDef. Isometries on M:()XYProp.
[Memoli 2011]! “bending-invariant” objects recognition.

XfY

For Arbitrary Spaces
YMetric-measure spaces (X, Y ): (dX , µ), (dY , ⌫)dY (yDef. Gromov-Wasserstein distance:def.
2GW2 (dX , µ, dY , ⌫) =Zmin⇡2⇧(µ,⌫)|dX (x, x0 )X 2 ⇥Y 2

dY (y, y 0 )|2 d⇡(x, y)d⇡(x0 , y 0 )[Sturm 2012] [Memoli 2011]

dX( x,GW is a distance on
Prop.
mm-spaces/isometries.
! “bending-invariant” objects recognition.
! QAP: NP-hard in general.
! need for a fast approximate solver.

, y 0)

x 0)

XX

fY

Overview• Gromov Wasserstein• Entropic Regularization• Applications• GW Barycenters

Entropic Gromov WassersteinDef.
Entropic Gromov-Wasserstein
Projected mirror descent:Def. Projected mirror descent:

Prop. for ⌧ = 1/", the iteration reads

func T = GW(C, C̄, p, q)

initialization:
repeat:until convergence.
return T

Overview• Gromov Wasserstein• Entropic Regularization• Applications• GW Barycenters

Applicationsof GW:
Shapes Analysis
Vladimir G. Kim
SuvritSraphine

Adobe ResearchMIT

Use T to define registration between:
Shape

Colorsdistribution

Shape

Shape

Teddies
Humans
Four-legged
Armadillo

0.02

000.02
Figure 15: MDS embedding of four classes from SHREC dataset.
00.02

0.04

Teddies
Humans
Four-legged
Armadillo

40

1!"" " " " " " " # " " " " " " " $ !"" " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " #"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" $Source

0.02

Targets

51530

PCA 2

18: Mapping a set of 185 images onto a two shapes while
Figure 1: Entropic GW can find correspondences
between a source Figure
preserving color similarity. (Images from Flickr public domain collection.)
0.5
0 a surface with similar structure, a surface withsurface (left) andGW
distances
Geodesic distances cloud, an icon,
ShapesRand D ∈ Rwe are given symmetricweight matrices
MDS
shared semantic structure, a noisy 3D pointandaW ∈ Rand W ∈ R. We could solve a weighted
000.020.04 0.02
version of the GW matching problem(3) that prioritizes maps
(X)
Vizualization
handsdrawing.
Each fuzzy map was computed
using the same code. preserving distances corresponding
s0to large W values:
n0 ×n0+

251

45

020

35

n×n+

α1

MDS
2-DFigure
16: Recovery of galloping algorithm
horse sequence. thatIn this paper, we propose
a newincorrespondence

minPCA 140n0 ×n0+10Figure 15: MDS embedding of four classes from
0 SHREC dataset.
0.5
1n×n+

Γ∈M5!
ijkℓ(D0ij −Dkℓ )2 Γik ΓjℓW0ijWjℓ µ0i µ0j µk µℓ .

MDS in 3-D(8)minimizes distortion of long-0 isandshort-range
We For instance, (W , W) might contain confidence values expressing Te
the baseshape) as a feature distances
vector for shape i.alike.
We reproduce
the quality of the entries of (D , D). Or, W , W could take values Hu
the result
presented ofin theworkof Rustamov et al., recovering
study an entropically-regularizedversion
theGromov-Wassersteinin {ε, 1} reducing the weight of distances that are unknown or do Fo
the circular structure of meshes from a galloping horse animationAr
not need to
be preserved by Γ.
0.02
sequence (Figure16).[Mémoli
Unlike Rustamov
et al., however,
our method(GW) mapping objective function
from2011]
measuring
Figure 18: Mapping
a set of 185 images onto a two shapes while
does not require ground truth maps between shapes as input.
Following the same simplifications as §3.1, we can optimize thispreserving
colorsimilarity.
(Images frompublicwhere
domain collection.)
0.5⟨Γ,Flickr
Λ (Γ)⟩,
the distortion of geodesic distances. The optimizer is a probabilistic objective by minimizing
5.2 Supervised Matchingn ×n
1
matching expressed as a “fuzzy”
correspondence matrix in Rthe
style
0 are:=given
and D ∈ Rn×n
weight matrices[D symmetric⊗ W ][[µ ]]Γ[[µ]]W++ Λwe(Γ)
2n ×nn×n
Animportantfeatureofa
matching
toolistheabilitytoincorporate
W0 ∈ Rofand W ∈ R+ −.[DWecould
a weightedof [Kim et al. 2012; Solomonuser
etinput,al. e.g.
2012];
we control sharpness+⊗W][[µ solve]]Γ[[µ]][D⊗ W]
ground truth matches of points or regions. In theversion
oftheGW
matching
problem(3)that
prioritizes
maps 0α1
GW framework,
oneentropic
way to enforce these
constraints
is to provide
Figure1:The
databasethathasbeenused,divid
the correspondence viaof theregularizer.
00.02
W[[µ]]Γ[[µ]][D⊗W]+0.04
0 the weight
preserving distances corresponding to large W values:
0.0200150

PCA 230W00251

W04510αa stencil S specifying a sparsity pattern for the map Γ. Incorporating

0000002035∧2020∧20

Applications of GW: Quantum Chemistry
Regression problem:! f by solving DFT approximation is too costly.

GW-interpolation:[Rupp et al 2012]

2666
64377775

Overview• Gromov Wasserstein• Entropic Regularization• Applications• GW Barycenters

Gromov-Wasserstein Geodesics
Def.

Gromov-Wasserstein Geodesic

Prop.

[Sturm 2012]! X ⇥ Y is not practical for most applications.
(need to fix the size of the geodesic embedding space)! Extension to more than 2 input spaces?

Gromov-Wasserstein Barycenters
Input:
2Def. GW Barycenters
1

Alternating minimization:
initialization: C
repeat:for s = 1 to S doOn Ts
until convergence.
return CC03