distance between two graphs

[qubit0]

For a given data, I can make different graphs. Since the graph is going to be made from the same data, these graphs will have the same number of nodes. If I make two different graphs then what would be the best way to make the distance between these graphs?

This paper (https://arxiv.org/pdf/1901.06003.pdf) uses the Gromov-Wasserstien distance. I am very new to the field of OT. I am slowly going through literature and lectures to understand OT. I would love to know if there is an OT way to do the aforementioned task. If yes then how would I use ott-jax to do so?

Thanks!

[marcocuturi]

Hi @qubit0 ! thanks for your interest in OTT.

I'd say the proper (and earlier) reference for this line of work is the thread of approaches on the fused Gromov-Wasserstein distance. You can look in particular at:
https://arxiv.org/abs/1811.02834
and follow up @ ICML.
https://proceedings.mlr.press/v97/titouan19a.html

I don't think we have a notebook illustrating FGW, but POT has a simple one:
https://pythonot.github.io/auto_examples/gromov/plot_fgw.html

Note however we do implement FGW, and I think ours is likely to be the most efficient implementation around, since folks at MOSCOT use it at fairly large scales, see e.g. https://moscot.readthedocs.io/en/latest/tutorials/tutorial_spatial_alignment.html)

To run FGW, you need to instantiate a quadratic problem. Here, typically, the geom_xx and geom_yy objects will be computed using graph information, while geom_xy will continue node features information.

Once your problem is defined, you can call a GW solver on it.

[qubit0]

Thanks a lot. It will take me a while to get through references.