Non-zero Gromov distance on identical graphs

Thanks for this excellent package, it's a very cool method.

However, I've noticed what may be a technical bug where on some graphs, where I have found a non-zero Gromov distance even when the underlying graphs are identical. I suspect there may some inherent structural basis behind the observation since some random graphs always seem to reach 0 and other structures never do.

Some code based on the graph_transport ipython notebook:

import numpy as np
import os,sys
sys.path.append(os.path.realpath('../lib'))
from graph import graph_colors,draw_rel,draw_transp,Graph,wl_labeling
from ot_distances import Fused_Gromov_Wasserstein_distance,Wasserstein_distance
import copy
from data_loader import load_local_data,histog,build_noisy_circular_graph
import matplotlib.pyplot as plt
import networkx as nx

nxgr = nx.generators.turan_graph(8,2)
n = len(nxgr.nodes)
g1 = Graph(nxgr)
g2 = Graph(nxgr)
## some random, unimportant, node features
g1.add_attibutes({i: v for i,v in enumerate(np.random.randint(0,2,n))})
g2.add_attibutes({i: v for i,v in enumerate(np.random.randint(0,2,n))})

plt.figure(figsize=(5,4))
vmin=0
vmax=1

# plots are nice!
draw_rel(g1.nx_graph,draw=False,vmin=vmin,vmax=vmax,with_labels=False)
draw_rel(g2.nx_graph,draw=False,vmin=vmin,vmax=vmax,with_labels=False,shiftx=5,swipx=True)
plt.title('Two graphs. Color indicates the label')
plt.show()

Fused_Gromov_Wasserstein_distance(alpha=1,features_metric='dirac',method='shortest_path', verbose=True).graph_d(g1,g2)

Output is:

It.  |Loss        |Delta loss
--------------------------------
    0|8.750000e-01|0.000000e+00
    1|5.074625e-01|-3.675375e-01|9.900000e-01
    2|5.000750e-01|-7.387504e-03|9.900000e-01
    3|5.000007e-01|-7.424625e-05|9.900000e-01
    4|5.000000e-01|-7.424996e-07|9.900000e-01
    5|5.000000e-01|-7.425000e-09|9.900000e-01
    6|5.000000e-01|-7.425049e-11|9.900000e-01

I've found a few other examples on random graphs (e.g. trees) that don't seem to reach zero either.

I would appreciate and look forward to your thoughts on this.

Hi thank you for this comment. Indeed I believe this is because the GW (and FGW) distance is a non-convex problem, so the optimisation may fall into some bad local minima (which is unavoidable ...) To investigate this you can try to set a different initialization for the GW distance (there is a G0 parameter that sets the init for the coupling) here:

https://github.com/tvayer/FGW/blob/1205827aa0496adccd7514352ae4b83c7d1f352b/lib/ot_distances.py#L122

It will change that:

https://github.com/tvayer/FGW/blob/1205827aa0496adccd7514352ae4b83c7d1f352b/lib/FGW.py#L285

So you can find a better init by trying identity matrix G0 -> the distance should be zero

You can also see if amijo = False is changing something.

Thank you for the contrib I will merge

Best, Titouan

tvayer / FGW

Non-zero Gromov distance on identical graphs #5