Gromov-Wasserstein fails when the cost matrices are slightly different

[devmessias]

Describe the bug
The .gromov.gromov wasserstein method fails (TypeError) when the cost matrices are very similar but not the same

To Reproduce
The full code is available at
https://colab.research.google.com/drive/1IhnOqeLV51gWE8FodnBsgR5cQC_w2EkL

• How was POT installed [pip]

Sys specifications

Linux-3.10.0-327.22.2.el7.x86_64-x86_64-with-centos-7.2.1511-Core
Python 3.4.3 (default, Apr 28 2015, 11:29:27) 
[GCC 4.9.2]
NumPy 1.16.2
SciPy 1.2.1
POT 0.5.1

[rflamary]

Hello, thank you for reporting this detailed and precise bug.

I think it might come from the fact that we test convergence only in terms of relative variation of the loss that actually never changes for cases with same (or too similar) cost matrices and we never erah conevrgence.

you can see the test here:
https://github.com/rflamary/POT/blob/master/ot/optim.py#L188

For a quick and dirty patch if you need it you can do as @tvayer did here
https://github.com/tvayer/FGW/blob/master/lib/optim.py#L253
and replace the relative loss variation by the loss variation.

We plan on implementing this (at least add another threshold for non-relative variation) in the future but it will have to wait for the NeurIPS deadline i'm afraid.

[devmessias]

Thanks! This worked for me. However, I'm having the same convergence issues for other cases, even using this "dirty patch"

Distance_matrix_0

Distance_matrix_1

Distance_matrix_2

The GW implementation works for [0,2], [1,2] but not for [0,1].

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-77-71f5a2aaa52c> in <module>()
----> 1 get_gromov_dist(dists[0], dists[1])

<ipython-input-76-9c4bb904dd5f> in get_gromov_dist(dist1, dist2)
     85     #try:
     86     gw0, log0 = ot.gromov.gromov_wasserstein(
---> 87         dist1, dist2, p, q, 'square_loss', verbose=False, log=True,)
     88     dist = log0["gw_dist"]
     89     #except:

~/.local/lib/python3.4/site-packages/POT-0.5.1-py3.4-linux-x86_64.egg/ot/gromov.py in gromov_wasserstein(C1, C2, p, q, loss_fun, log, **kwargs)
    343 
    344     if log:
--> 345         res, log = cg(p, q, 0, 1, f, df, G0, log=True, **kwargs)
    346         log['gw_dist'] = gwloss(constC, hC1, hC2, res)
    347         return res, log

~/.local/lib/python3.4/site-packages/POT-0.5.1-py3.4-linux-x86_64.egg/ot/optim.py in cg(a, b, M, reg, f, df, G0, numItermax, stopThr, verbose, log)
    180         alpha, fc, f_val = line_search_armijo(cost, G, deltaG, Mi, f_val)
    181 
--> 182         G = G + alpha * deltaG
    183 
    184         # test convergence

TypeError: unsupported operand type(s) for *: 'NoneType' and 'float'

[tvayer]

Hello,
I may have missed something but based on your error I don't think you are using the right "dirty patch".
You can use https://github.com/tvayer/FGW/blob/master/lib/optim.py, check out the function do_linesearch which uses wether line_search_amijo (that fails in your case) or a linesearch method based on a closed form expression.
You juste have to feed the cg method with C1,C2 and constC and to set "amijo=False" to use the dirty patch.
Both methods do not come with same results because amijo approximates the function

Hope it helps

[devmessias]

Hi @tvayer! You're right.

I didn't read your recent work about the Fused GW distance, looks realy cool! But what is the meaning of constC matrix?

Reading your code I saw the folowing lines.
https://github.com/tvayer/FGW/blob/8c848845075d3c6a30066dcccec29c82eb55dead/lib/FGW.py#L53-L72

But I don't get. I can just copy-and-paste that in my code?

[tvayer]

Thanks !

The constC matrix is defined eq (6) in https://www.archives-ouvertes.fr/hal-01322992/document. It is used to compute the tensor product used in gromov.

For your code to work with the solver in FGW you can for example :

• Download the optim.py/FGW.py files of FGW
• Use the gw_lp method in FGW.py (by setting amijo=False in the arguments when there is convergence problems) instead of the gw_lp of POT. You will need also to comment L-6-7 in FGW.py if you just want to use gromov you won't need theses.

[rflamary]

@tvayer thank you for coming and helping with this issue.

We definitely need to add the new implementation to POT with a PR (also FGW) as soon as we find time for it.