Question about what algorithms would count

[rsonthal]

Hi,

I was wondering whether a couple of algorithms that are about learning metrics and embeddings would be within the scope.

Specifically, if the following two algorithms (either individually or collectively) would be within scope

1. TreeRep from paper. This is an algorithm that takes in a metric and outputs a tree.
2. Tree embeddings in Hyperbolic space from this paper. This is an algorithm that takes a weighted tree and then embeds into the hyperbolic manifold.

Thanks,
Rishi

[ninamiolane]

Thanks for reaching out! Yes, both of these papers would fall within the scope.

If you implement the second one, it could be very interesting to know how it compares to the algorithm that we have in the library: https://github.com/geomstats/geomstats/blob/master/notebooks/usecase_graph_embedding_and_clustering_in_hyperbolic_space.ipynb.

You would have to implement it using geomstats' infrastructure, if it exists, i.e. using its hyperbolic space class for example (if relevant): https://github.com/geomstats/geomstats/blob/master/geomstats/geometry/hyperbolic.py

Let us know if you have more questions!

[ninamiolane]

@rsonthal you could also be interested in this: geomstats/geomstats#1307
(implementation of tree spaces coming up to geomstats)

[rsonthal]

Thank you and thank you for the pointers to great resources!

[rsonthal]

I was wondering if using mpmath for increased precision computation or networksx for building trees would violate the guidelines (or should we wait for the above tree implementation?)

The only other packages we use are matplotlib and geomstats.backend

Thanking you,
Rishi

[ninamiolane]

Thanks for the first PR! 🤩

Not having Geomstats primitives would violate the guidelines yes, which state: "IMPORTANT: Use Geomstats computational primitives (e.g. exponential, geodesics, parallel transport, etc).". Unfortunately, geomstats.backend is not considered computational primitives as it is merely as wrapper around numpy, tf and torch functions. (Sorry if this was not clear, I will update the README on this point now).

The reason behind these guidelines are that we (Geomstats maintainers) are providing the prizes and are willing to extensively analyze learning algorithms on manifolds as an outcome of this challenge. For this, we need the algorithms to follow a common structure.

I can see two options for you there (there could be more):

• wait for the tree implementation above, if you feel that could help you
• you are mentioning that your implementation could have better precision: you could suggest another tree implementation, alternative to the one in the PR above, yet still following the structure of Geomstats classes in the library, and use it.

Let me know if I can help more?

[rsonthal]

Sorry to keep bothering. I am very interested and don't want to be disqualified for mistakes to due to not understanding the guidelines.

So the issue is that we use networkx, mpmath AND that we don't use geomstats computational primitives. I think I am understanding the guidelines better. However, I am now concerned we don't meet the guidelines. From what I can tell most of the computational primitives are based on doing calculations based on the differential structure, so like calculating the exponential/logarithmic map.

However, both of the algorithms I listed are more combinatorial/algebraic and don't use the differential structure of the manifold. So we need operations like computing the Gromov product, computing the image of points under certain isometries of the poincare disk, and graph operations like calculating the neighbors of a node.

The only place we use the primitive from geomstats would be during testing. That is, to sample points from hyperbolic space and to compute matrices between points on hyperbolic space and maybe compare against projection based methods.

If that isn't sufficient, we could extend the poincare ball class to add new function such as the isometries we care about and the Gromov product. I could also extend the symmetric matrices class to start building a different implementation of tree spaces but it would be more combinatorial and less differential.

Thank you for your help. As I said I am very interested and want to make sure I am abiding by the guidelines.

[ninamiolane]

You're not bothering at all! And I am happy that we can have this thread on GitHub: if other participants have similar questions, they can find answers here too. It is useful for everybody!

Thank you also for giving details about your method and the fact that it is more algebraic that differential: very helpful.

"Sampling points from hyperbolic space and compute matrices between points on hyperbolic space and maybe compare against projection based methods." --> This would be sufficient to have the submission obeys the guidelines, and comparing to the embedding method already in geomstats would be nice!

Still, note that the jury will be formed by (all the participating teans and) selected Geomstats maintainers and collaborators: the more interesting the integration of Geomstats is in your submission, the more chances you would have to be awarded a prize. As such, the extensions that you mention next could be a great idea!

[rsonthal]

Thank you! This has been very helpful!