Question/References about calculations of Pairwise distance metrics

[mir-cat]

Hello!

I have been using the pairwise distance functions to create distance matrices for manifold learning (UMAP). Up to this point, I have been calculating full distance matrices as input to the algorithm.

Now however, I am in a situation where I am calculating the distances between 10s of thousands of persistence diagrams and I can no longer calculate the full distance mayrices. In order to use the heuristics built into the UMAP algorithm, I need need to be able to compile the distance function with Numba. Unfortunately, I believe this means I need to write them from scratch.

I have attempted to write functions that emulate the behavior of gtda.diagrams.PairwiseDistance, which I have used previously, but I cannot seem to be able to match the output. Additionally, I have had trouble finding the code that actually performs the distance calculation. Would it be possible to get references for how the distances are calculated?

Thank you so much!

[ulupo]

Hi @mir-cat! Thanks for an interesting question. Specifically, which kinds of diagram distances are you hoping to compute? Bottleneck and Wasserstein are already implemented in C++ with Python bindings, so no further performance gains can be made there beyond parallelism (which we already offer). As for the other distances, the place to look is https://github.com/giotto-ai/giotto-tda/blob/master/gtda/diagrams/_metrics.py.

[mir-cat]

Hi! Thanks for pointing me to the distances. They have been very helpful for me so far.

Of the other two, I was hoping to be able to compute either, but mainly the Bottleneck distance. The Umap package I have been using for manifold learning (https://umap-learn.readthedocs.io/en/latest/) requires custom distance functions be compiled by Numba. I understand that the Bottleneck and Wasserstein distances have been implemented in a fast way, but I need to be able to make Umap "accept" the function. I don't believe that anything I could write would be faster, it's just a requirement that the package demands :/.

[ulupo]

Thanks for the clarification! UMAP's requirements make things quite tricky as they are effectively ruling out calling C/C++ extensions. Reimplementing the Wasserstein/bottleneck distances from scratch from the C++ code used in giotto-tda (originally from the Hera project) might require more time than you wish to dedicate to this. An alternative is to look at persim, but even there you'll have to get around the fact that scipy.optimize.linear_sum_assignment calls a C extension.

May I suggest, if you are doing research rather than code development so elegance is not a priority, to just precompute the Wasserstein/bottleneck distances using giotto-tda, saving them to npy files locally, and coding a dummy numba function which simply loads the precomputed distances file?

[mir-cat]

Thank you for your suggestion! I tried to give your idea a shot, but unfortunately the dataset I am working with (~30,000 samples) would give a full distance matrix with almost a billion cells :(, which is beyond anything I have the capacity for. I believe that Umap has heuristics that made it possible for the computation to proceed despite working with datasets of this size. I tried to do a few clever tricks to get around this, playing with import/export, but to no success so far.

That being said, I have been able to use the other metrics in the package that you pointed out to me!