Tuning GWLR rank?

[prabhant]

Hi,
I was curious if there is a way to tune the hyperparameters of the low-rank Gromov Wasserstein, and what is the optimal value for what scenario here? right now I use rank 6 similar to this example which gives me a pretty close approximation to GW distance. https://ott-jax.readthedocs.io/en/latest/notebooks/GWLRSinkhorn.html
Shall it be tuned to just minimize the distance between GW and GWLR or there is some other criteria?

[marcocuturi]

Hi @prabhant! thanks a lot for your interest in the toolbox, we're very happy to hear your coments!

Setting the "right" rank hyperparameter is a bit of a tricky question if you want a very good answer, but we find in practice that the choice is usually quite sturdy, and that we can settle on simple rules of thumb.

I think, intuitively, that if you were to have the first measure clustered nicely around $k_1$ clusters, and the other with $k_2$ clusters, then it would make sense to have $r$ set to anywhere between $\min(k_1,k_2)$ and $\max(k_1,k_2)$. We discussed this briefly in our paper, section "Effect of the rank".

Then there's the rule of thumb $k\approx\sqrt{n}$ that you can also consider, where $n$ is the number of datapoints, which we have also used occasionally. Ultimately, I think that what also matters is compute power of course, since smaller $r$ results in much faster computations. hope this helps!

[prabhant]

Thank you for your reply, Is that logic still applicable when the n is 50k to 100k? as the experiments are only for 5k samples

[marcocuturi]

I think we haven't ran that particular experiment for larger sample sizes (@meyerscetbon might comment!), but I would expect a similar effect: the rank $r$, i.e. the size of that abstract "middle" proxy measure that connects the two measures should be large enough to capture interessing clustering structure in the coupling, and that should be more or less of the order of $k_1+k_2$. So a rule of thumb (not sure how scalable) could be to run k-means on both measures, see where there's a plateau in terms of energy (i.e. good enough approx with a given number of centroids) and from there use $r\approx \max(k_1,k_2)$ or $k_1+k_2$ if you want to be conservative.

What's clear is that there will be a tradeoff (very much like PCA or k-means): the higher the number of clusters or components, the more you capture of course... But you want to hit a sweet spot that's useful computationally, and also more robust statistically.