Binary Hyperbolic Embeddings

Reponse to Reviewer 4fSp

We thank the reviewer for their positive comments on the performance and feedback on improving the understandability of the theory part.

In response to W1: Some of the derivation details, such as Eq.(6-9) in Proposition 2 and Eq. (11) with symbols not specified.

We thank the reviewer for the clarification suggestion, and we have added the notation explanations to the corresponding text.

In response to W2: Further explanations are needed on how to satisfy some preset conditions in proof or derivations.

For Proposition 1, the distance approximation preset condition requires constants $K_1$ and $K_2$, $K_2$ is usually set such that no point pairs would fall into that range. In practice, the model's performance is rather insensitive to $K_1$, even removing the approximation on $K_1$ side rarely harms the performance.

For Proposition 2, the distance equivalence is based on a code book $\mathbf{U}$ satisfying $\langle\mathbf{Ux}^b, \mathbf{Uy}^b \rangle = \langle\mathbf{x}^b, \mathbf{y}^b \rangle$, in our case, our binarization blockwisely satisfied this, but in general any codebook, e.g. orthogonal codebook, can utilize Proposition 2.

In response to Q1: What is the main difference between Hyperbolic embedding and learning to hashing?:

In our case, we do not need to learn to achieve a performance that is comparable with full precision baseline, while hashing requires learning and solving a NP-hard discrete optimization problem, or its relaxed version at the cost of optimality.

In response to Q2: It's interesting to provide more experiments and analysis about the fastness and goodness of Hyperbolic embedding and learning to hashing.

For the same length of binary-code, learning to hash is slightly faster than us because hash-codes can be directly used for hamming distance, while in our case, extra bit shifts will be carried out for distance calculation. However, as shown in the following table, at equal bit length the accuracy of our approach is notably higher.

We express our gratitude to the reviewer for their affirmative remarks on the theoretical soundness of our work and its congruence with experimental results.

In response to W1: Differences in Curvatures for Prototypes and Embeddings:

While our empirical data demonstrate effectiveness, we acknowledge the lack of rigor in our description. The performance degradation at the Poincaré ball's edge is attributed to numerical instability. Hence, we propose restricting the prototype's radius rather than using varying curvatures for embedding. This adjustment leads to the subsequent analysis, highlighting performance enhancement due to the adoption of a more robust CLIP backbone.

In response to Q1: Potential of Adaptive Quantization in Enhancing Performance:

We fully agree with the comments, and we would be excited to see further research in this direction. We will include it in the conclusions.

In response to Q2: Bit Requirement for Parity with Full Precision Methods:

Generally, we observe that 256 bits suffice to achieve performance comparable to full precision methods. Refer to rows 9 and 11 in Table 2 for further details.

In response to Q3: Fairness of Comparison with Other Methods:

We ensure fairness in our comparative analysis, both in terms of software and hardware. We utilized the same codebase (C++ standard libraries) with identical compilation options and performed evaluations on the same hardware, specifically the Nvidia A6000 GPU for training and a AMD EPYC 7402P Processor (single-core, single-threaded only) for evaluation.

In response to Q4: Procedure for Obtaining Hyperbolic Embeddings:

The Euclidean embeddings are indeed transformed through exponential mapping, followed by a linear layer for dimensional adjustment. This method was applied, for example, to derive embeddings for CIFAR-100 from ResNet.

In response to W5: The ResNet and 3D ResNet backbones used are a bit dated.

We have updated ResNet to CLIP and 3D ResNet to 3D-SWIN-Transfomer [ref3], leading to the updated results in the paper: The results show that with updated backbones, our binary hyperbolic embeddings outperform other geometries.

In response to W6: There is no comparison to other binary encoding methods like binary auto-encoders or binary hashing.

We obtained the following results when compared with hashing on CIFAR-100:

Note that in our evaluation protocols, the query and database set are both used as the test set, while in standard hashing setting the database set is the entire training set. Across both datasets, for both 64 and 128 bit settings, we obtain noticeably higher performance. Moreover, hashing requires learning and solving a NP-hard discrete optimization problem, which we can avoid due to our binarization strategy.

In response to W7: For fairer comparison, all methods should be benchmarked in the same codebase/hardware:

To ensure fair comparison we benchmarked the performance using the same codebase, which is C++ std libraries, under the same compilation options, we also used the same hardware for all the evaluation, which is the Nvidia A6000 GPU. We will include this information in Section 4.1.

In response to W8-1: The impact of factors like codebook design could be investigated more thoroughly via ablation studies:

Our main contribution is to show that hyperbolic embeddings can be binarized to get the best out of the compactness of hyperbolic space and the speed of XOR operations. We consider codebook designs as fruitful future directions and we will include it in the conclusions.

In response to W8-2: learning hyperparameters could be investigated more thoroughly via ablation studies.

In the experiments, we examined three hyper-parameters, 1) dimensionality of embedding space, 2) the number of quantization bits, 3) curvature of hyperbolic space. To elimiate the ambiguity, in addition to those existing hyper-parameters, we also introduce the embedding radius limitation as another hyper-parameter instead of the original "curvature to generate prototypes". Note that increase of performance is due to using a stronger CLIP backbone.

[ref1] Cannon, James W., et al. "Hyperbolic geometry." Flavors of geometry 31.59-115 (1997): 2. [ref2] Radford, Alec, et al. "Learning transferable visual models from natural language supervision." ICML2021. [ref3] Liu, Ze, et al. "Video swin transformer." CVPR2022.

We appreciate the reviewer's summary of the efficiency and compactness of our proposed method. We also thank the reviewer's suggestions for improving the paper, and we address them accordingly as follows:

In response to W1: More analysis on linear approximation:

We would love to show 1) the tightness of several $K_1, K_2$ and 2) despite the different tightness levels, the approximation does not change the rank of the retrieval output.

1. The linear approximation mainly contributes to theoretical completeness. In practice, using different $K_1$ and $K_2$ yields negligible difference compared with the none-approximated version. More specifically, $K_2$ has no effect on the distance calculation as none of the point pairs falls into that range. Varying $K_1$ does change the distance measure, while the effect is imperceptible, because both 1) the approximated distance and 2) the actual hyperbolic distance is very big compared to the euclidean counterparts.

2. The approximation is monotonically increasing with respect to hyperbolic distance $\|\mathbf{x}-\mathbf{y} \|$, that means, nearby samples in poincare ball is still nearby under approximated distance metric and far-away samples are still far away.

In response to W2: More sophisticated methods like product quantization:

We add the product quantization result for comparison:

In response to W3: Other hyperbolic models like Lorentz,

we thank the review's consideration for a broader impact. The reason that we did not consider other hyperbolic models it that they do not satisfy that each dimension is 1) symmetical and 2) ranges is in $(-r, r)$.

Although we do not binarize other hyperbolic models, they can still use our binarization via isometry defined in hyperbolic geometry [ref1], with a single coordinates transformation. In particular, we give one example on how Lorentz model transform to Poincar'e model [ref2] in one line:

• $(x_0,x_1,...,x_n)\mapsto (\frac{x_1}{1+x_0}, \frac{x_2}{1+x_0},...,\frac{x_n}{1+x_0})$

Note that the above Lorentz $\mapsto$ Poincar'e transformation is a isometry, meaning that the distance between Lorentz embeddings are equal to the distance between the resultant Poincar'e embeddings. Therefore any Lorentz embedding based retrieval can benifit from our Poincar'e binarization.

In response to W4: The image and video datasets used are standard but small-scale.

Following the reviewer's guidance, we have added the Quick Draw dataset for a large-scale experiment. In Quick Draw, we embed the raw 50 Million images with a simple MLP backbone plus Euclidean/Hyperbolic Head.

The train/test split is split into a 1% training set and a 99% test set using the scikit-learn library with a random seed of 42. As the hierarchy information is not available for this dataset, we simply regard all the classes as the children of the "Root". The embedding dimensionality is 64, and we use 4 bits binarization. We perform retrieval on two randomly picked subsets (one small scale and one large scale) of the test set.

The results above highlight that our approach generalizes to large scale settings. Thank you.

We thank the reviewer for their positive feedback regarding the innovation, efficiency, and technical insights.

In response to W1/Q1

The hierarchical knowledge acts as supervision for the embedded learning. Specifically, we use the hierarchy over all classes to embed each class as a point in the Poincaré ball following [ref1]. Then, we optimize the image or video representations to be close to their class prototype in hyperbolic space. We further clarify this in Section 3.2.

In response to W2

We regret the confusion caused by symbol $\oplus$. We would like to show that your description of the hamming distance $d_{\mathbb{H}}(\mathbf{x}^b,\mathbf{y}^b)=\||\mathbf{x}^b \oplus \mathbf{y}^b\||_1$

is equivalent to our description given as

$d_{\mathbb{H}}(\mathbf{x}^b,\mathbf{y}^b)= nd -\||\mathbf{x}^b \oplus' \mathbf{y}^b\||_0$.

For binary representations $\mathbf{x}^b, \mathbf{y}^b \in \{0, 1\}^{nd}$, it holds that $\||\mathbf{x}^b \oplus \mathbf{y}^b\||_1 = \||\mathbf{x}^b \oplus \mathbf{y}^b\||_0$. If we denote $\oplus$ as the element-wise XOR operation and $\oplus'$ as the element-wise XNOR operation, it holds that $\||\mathbf{x}^b \oplus \mathbf{y}^b\||_0=nd-\||\mathbf{x}^b \oplus' \mathbf{y}^b\||_0$. Combining these two steps, we have the equivalence $\||\mathbf{x}^b \oplus \mathbf{y}^b\||_1=nd-\||\mathbf{x}^b \oplus' \mathbf{y}^b\||_0$.

Despite the equivalence, we agree that $\oplus$ is more commonly used as an XOR operator than XNOR; hence, we will follow the reviewer's suggestion and adapt the equation for more consistency with existing conventions.

In response to W3/Q2

In the revision, we have added the corresponding part of the results on different datasets to the appendix and will keep updating them. Those results are consistent across different datasets, proving the generalization capability of our model.

To draw more interest regarding this question, inspired by reviewer 5iHW , we show the capability of our proposed model on a large-scale dataset, "Quick, Draw!", which has 50 million sketch images from 345 classes. We demonstrate the effectiveness of our binarization as follows:

The train/test split is split into a 1% training set and a 99% test set using the scikit-learn library with a random seed of 42. As the hierarchy information is not available for this dataset, we simply regard all the classes as the children of the "Root". The embedding dimensionality is 64, and we use 4 bits binarization. We perform retrieval on two randomly picked subsets (one small scale and one large scale) of the test set.

We also thank the reviewer for pointing out the typos; we have fixed them in the updated version.

[ref1] Ganea, Octavian, Gary Bécigneul, and Thomas Hofmann. "Hyperbolic entailment cones for learning hierarchical embeddings." ICML, 2018.