Overview

This PR has two parts

1. Sarkar tree embedding for 2 and 3 dimensions
2. CICD testing and building

Sarkar Embedding

The two main functions are sarkar_embedding and sarkar_embedding_3D.
These are used to embed a (weighted) tree into the 2D or 3D Poincare ball[^1]. The 3D version uses a "fibonacci coding" for distributing points on a 2D sphere[^2]. [^2]: http://extremelearning.com.au/evenly-distributing-points-on-a-sphere/ [^1]: https://homepages.inf.ed.ac.uk/rsarkar/papers/HyperbolicDelaunayFull.pdf

Example usage:

from hyperlib.util.graph import binary_tree
from hyperlib.util.sarkar import sarkar_embedding_3D

T = binary_tree(4) # a depth 4 binary tree
root = 0 # the index to use as the root
tau = 0.4 # the scaling factor for edges
emb = sarkar_embedding_3D(T, root, tau=tau, precision=40)

Note that both of these functions use mpmath for high precision calculations, and return a mpmath.matrix. I added high precision Poincare math functions in the utils package.

Sarkar's algorithm can be extended to higher dimensions but the "spherical coding" part is more difficult. Will address in the future.

CICD

I added two basic workflows. One runs a linter and tests on push and pull requests to main.
The other triggers when we tag a version on main. It builds wheels and uploads them to PyPI and Test PyPI. I added API tokens for nalex's PyPI account as GitHub secrets on this repo. The wheels are built for linux, windows, and mac on x86_64, amd64, i686 architectures using cibuildwheel. I tested on ubuntu and @sourface94 tested on windows.

To build locally you use

pip setup.py build

Note that you need a cpp compiler to build the treerep part. On linux you need gxx_linux-64 which can be install from conda install -c conda-forge gxx_linux-64.

When developing please run the tests locally first. To run the linter:

python -m pip install flake8
flake8 . --count --select=E9,F63,F7,F82 --show-source --statistics

and to run the tests just pytest -v tests/.

Addendum

I updated the embedding example in the readme and made a examples/ folder for future examples.
I also added install instructions.

• Added embedding package with TreeRep cxx source
• Added setup.py with pybind11, tested on ARM MacOS Big Sur
• fixed some Poincare functions and added functions

This PR adds Sarkar's algorithm for embedding a tree in 2 and 3 dimensional hyperbolic space, plus more high precision utility functions for the Poincare disc.

TODO:

• Sarkar's algorithm for >3 dimensions. We have to implement a solution to the "spherical coding" problem in high dimensions.
• unit tests

1. Added Treerep cxx source with pybind11 wrapper. To use simply call the function embedding.graph.treerep on the distance matrix. There are also functions to convert the resulting tree to a scipy.csgraph or a networkx graph.
2. Added functions for working with distance matrices and measuring delta-hyperbolicity under embedding.metric
3. Add utils.multiprecision for high precision calculations using mpmath (necessary for calculating large hyperbolic distances accurately)
4. Fixed a few Poincare class functions and added some
5. Made tests for treerep

Built and tested successfully on MacOS Big Sur and Manjaro Linux

• Moved hyperbolic functions to utils.math. When working with the library it was inconvenient having to access functions through the "Poincare" class. The benefit of having the class isn't clear to me.
• Fixed some errors in the hyperbolic functions and added a few functions (hyp_dist, clipped_norm, parallel_transport, gyr, lambda_x)
• Rewrote RSGD. Optimizers should inherit from keras optimizer_v2 and implement sparse and dense updates separately (see here). It should be possible to momentum next.
• attempted RAdam, still buggy. The problem is parallel transport of momentum ( see Becigneul & Ganea pg. 5 )
• Added Jupyter notebook in /examples to demo word embedding. Not sure where to put this but it could be nice to have more demos/tutorials in the future.

I am trying to train on google colab using the following code

from random import choice
import numpy as np
import pandas as pd
import tensorflow as tf
from tensorflow import keras

from hyperlib.manifold.lorentz import Lorentz
from hyperlib.manifold.poincare import Poincare
from hyperlib.models.pehr import HierarchicalEmbeddings


def load_wordnet_data(file, negatives=20):
    noun_closure = pd.read_csv(file)
    noun_closure_np = noun_closure[["id1","id2"]].values

    edges = set()
    for i, j in noun_closure_np:
        edges.add((i,j))

    unique_nouns = list(set(
        noun_closure["id1"].tolist()+noun_closure["id2"].tolist()
    ))

    noun_closure["neg_pairs"] = noun_closure["id1"].apply(get_neg_pairs, args=(edges, unique_nouns, 20,))
    return noun_closure, unique_nouns

def get_neg_pairs(noun, edges, unique_nouns, negatives=20):
    neg_list = []
    while len(neg_list) < negatives:
        neg_noun = choice(unique_nouns)
        if neg_noun != noun \
        and not neg_noun in neg_list \
        and not ((noun, neg_noun) in edges or (neg_noun, noun) in edges):
            neg_list.append(neg_noun)
    return neg_list


# Make training dataset
noun_closure, unique_nouns = load_wordnet_data("mammal_closure.csv", negatives=15)
noun_closure_dataset = noun_closure[["id1","id2"]].values

batch_size = 16
train_dataset = tf.data.Dataset.from_tensor_slices(
        (noun_closure_dataset, noun_closure["neg_pairs"].tolist()))
train_dataset = train_dataset.shuffle(buffer_size=1024).batch(batch_size)

# Create model
model = HierarchicalEmbeddings(vocab=unique_nouns, embedding_dim=10)
sgd = keras.optimizers.SGD(learning_rate=1e-2, momentum=0.9)

# Run custom training loop
model.fit(train_dataset, sgd, epochs=20)
embs = model.get_embeddings()

M = Poincare()
mammal = M.expmap0(model(tf.constant('dog.n.01')), c=1)
dists = M.dist(mammal, embs, c=1.0)
top = tf.math.top_k(-dists[:,0], k=20)
for i in top.indices:
    print(unique_nouns[i],': ',-dists[i,0].numpy())

I see that the GPU is not being used when I inspect the GPU usage. Kindly help

When running model.fit as per this code example I am unable to make out whether any progress is happening or the training is hung for me. Kindly help

This is the code I am trying to run

from random import choice
import numpy as np
import pandas as pd
import tensorflow as tf
from tensorflow import keras

from hyperlib.manifold.lorentz import Lorentz
from hyperlib.manifold.poincare import Poincare
from hyperlib.models.pehr import HierarchicalEmbeddings


def load_wordnet_data(file, negatives=20):
    noun_closure = pd.read_csv(file)
    noun_closure_np = noun_closure[["id1","id2"]].values

    edges = set()
    for i, j in noun_closure_np:
        edges.add((i,j))

    unique_nouns = list(set(
        noun_closure["id1"].tolist()+noun_closure["id2"].tolist()
    ))

    noun_closure["neg_pairs"] = noun_closure["id1"].apply(get_neg_pairs, args=(edges, unique_nouns, 20,))
    return noun_closure, unique_nouns

def get_neg_pairs(noun, edges, unique_nouns, negatives=20):
    neg_list = []
    while len(neg_list) < negatives:
        neg_noun = choice(unique_nouns)
        if neg_noun != noun \
        and not neg_noun in neg_list \
        and not ((noun, neg_noun) in edges or (neg_noun, noun) in edges):
            neg_list.append(neg_noun)
    return neg_list


# Make training dataset
noun_closure, unique_nouns = load_wordnet_data("mammal_closure.csv", negatives=15)
noun_closure_dataset = noun_closure[["id1","id2"]].values

batch_size = 16
train_dataset = tf.data.Dataset.from_tensor_slices(
        (noun_closure_dataset, noun_closure["neg_pairs"].tolist()))
train_dataset = train_dataset.shuffle(buffer_size=1024).batch(batch_size)

# Create model
model = HierarchicalEmbeddings(vocab=unique_nouns, embedding_dim=10)
sgd = keras.optimizers.SGD(learning_rate=1e-2, momentum=0.9)

# Run custom training loop
model.fit(train_dataset, sgd, epochs=20)
embs = model.get_embeddings()

M = Poincare()
mammal = M.expmap0(model(tf.constant('dog.n.01')), c=1)
dists = M.dist(mammal, embs, c=1.0)
top = tf.math.top_k(-dists[:,0], k=20)
for i in top.indices:
    print(unique_nouns[i],': ',-dists[i,0].numpy())

Right now optimizers.rsgd is implemented specifically for the Poincare model.
We should add an interface that works for any model.

TODO: write other improvements here

This is a tracking issue for solving precision issues.

Problem Overview

Precision is one of the major obstacles to the adoption of hyperbolic geometry in machine learning.
As shown in Representation Tradeoffs for Hyperbolic Embeddings, there is a tradeoff between precision and dimensionality when representing points in hyperbolic space with floats, independent of the model that is used.

Hyperlib should have a solution to this in its core components. Ideally the solution will satisfy the following.

1. reasonably efficient: it doesn't incur significant overhead compared to Euclidean methods and is GPU compatible
2. easy to use: it's abstracted away from the API so that a casual user doesn't have to touch it
3. general: it's general enough to be used with different models of hyperbolic space

Approaches

Hope for the best

We see many papers that simply accept the precision errors and try to mitigate them, or go to higher dimensions.
E.g. Our current approach in the Poincare model is to cast tf.float64, which only gets us 53 bits of precision.

Multiprecision

In the sarkar embeddings, we use a multi-precision library mpmath to represent points. As far as multiprecision arithmetic goes it is fast (assuming it is using the gmpy) backend. However the support for vector operations is not good and it cannot easily interoperate with numpy or tensorflow. Also we do not yet have a good method to automatically determine the precision setting (for example, in sarkar_embedding it uses far too much precision by default).

Avoiding the Problem

One common approach to avoid precision errors, especially in hyperbolic SGD, is to map from the (Euclidean) tangent space and do all operations there instead. We should definitely experiment with and support this method in Hyperlib. This will work for all models via the exponential map. However, it only solves part of the problem.

Multi-Component Float

Multi-Component Floats (MCF) are an alternate representation for floats that can be vectorized, proposed by Yu and De Sa as a way to do calculations in the upper half-space model. IMO this is the most promising approach if it can be extended to other models of hyperbolic space.

Todos

• [ ] Spike: implementing MCF for upper-half space

This is a tracking issue for improving documentation as hyperlib develops.
This will be important for getting more people to use hyperbolic ML (esp. examples)

• [ ] Standardize function doc strings
• [ ] Generate docs with sphinx
• [ ] Put up documentation site
• [ ] Examples (expand on point this later)