Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the setting of nearest neighbor search (NNS) and devises a graph-based algorithm for this task in Hyperbolic space. The problem is pertinent, as hyperbolic space has become prevalent for representing hierarchical data in various domains, and nearest neighbor search is a very fundamental problem. The paper proposes a graph-based nearest neighbor search closely based on existing literature, and analyzes time and space complexity assuming a uniformly distributed dataset of $n$ elements over a $d$-dimensional ball of radius $R$; the dataset is assumed to be dense in the underlying space ($\log n \gg d$). It is shown that under some assumptions on $d$ and $R$, graph-based NNS has lower time complexity in hyperbolic space when compared with its Euclidean counterpart. Practically, the paper focuses on the sparse data setting. It is shown that graph-based NNS is more efficient for Poincaré GloVe word embeddings than for Euclidean GloVe word embeddings, assuming an HNSW graph construction. Moreover, it is shown that the proposed graph-based NNS method outperforms other existing baselines on Poincaré GloVe embeddings.
main_review: ### Strengths

1. The paper's primary strength is the result given by Theorem 1, which rigorously analyzes the time and space complexity of a graph-based NNS for datasets that are both uniform and dense in a ball contained in hyperbolic space. It is worth noting that this result is a direct hyperbolic analog of Theorem 1 in Prokhorenkova & Shekhovtsov (2020).

### Weaknesses

1. Although the paper extends the result of Prokhorenkova & Shekhovtsov (2020) for dense graph-based NNS in Euclidean space to hyperbolic space, it does not attempt to provide theory for the more interesting and practical sparse setting. This makes the theory appear incomplete, relative to existing results in Euclidean space.

2. A large portion of the paper lacks novelty. The structure of the paper, up to and including the labelling of results/sections in the appendix, closely resembles Prokhorenkova & Shekhovtsov (2020). Certainly, the paper did have to introduce some lemmas, e.g. Lemma 1 followed from a fairly straightforward proof that allows one to bound volumes of hyperbolic balls by volumes of Euclidean ball intersections for small radii. Otherwise, a lot of the Euclidean analysis is taken straight from Appendix A of Prokhorenkova & Shekhovtsov (2020), and the hyperbolic constructions are de facto straightforward analytic extensions. Given the close resemblance of the paper to Prokhorenkova & Shekhovtsov (2020), there is an especially large amount of pressure on the paper to do a good job on being thorough with considered settings, but this was not provided: as mentioned above, no theoretical results for the sparse setting are given (in contrast to Prokhorenkova & Shekhovtsov (2020)).

3. I found the empirical results to be lacking considerably. First of all, the uniformity assumption and the assumption of small dimension was not addressed in the application section. Prokhorenkova & Shekhovtsov (2020) address these assumptions directly, both by employing dimensionality reduction and by making use of a technique that makes datasets more uniform while approximately preserving distances (Sablayrolles et al. (2018)). The argument in Section 5.2 seems to be that showing reasonable performance in practice without explicitly addressing these assumptions is sufficient, but this seems at best handwavy. These assumptions were critical for proper theoretical analysis, and one should either provide a way to bridge the gap between theory and practice, or provide a theoretical result about degradation when the assumptions do not hold.

4. The baseline seems too weak/non-exhaustive for Section 5.1 (Figure 1). The comparison is given only with respect to a single method from Wu & Charikar (2020). I understand that Spherical Shell may be the most "practical" method, but having a more proper comparison against the two other methods introduced in that paper is warranted, given the lack of prior work/baselines. Having a single baseline on 1 dataset in the sparse setting does not give me a convincing impression of the method's performance.

5. Along the same vein, I am left unconvinced by the results in Section 5.2 (Figure 2) that switching to hyperbolic embeddings from Euclidean embeddings makes NNS more efficient, or even that efficiency is not reduced. Although Figure 2 shows that HNSW built on embeddings in hyperbolic space for Poincare GloVe is more efficient than HNSW over Euclidean embeddings, this is but 1 dataset and 1 graph construction. To make a worthwhile empirical claim, it is necessary to provide results for at least a few datasets and a few graph constructions.

6. For all empirical results above, I did not see any mention of trials/mean/standard deviation. It is my understanding that graph-based NNS starts with some random location, and then propagates through the graph, guided by the metric. Hence, results may vary considerably from trial to trial. What was done in the paper? Were several trials run? What were the means/standard deviations? Please either report this information or re-run experiments for several trials and then report said information.

7. Although I have alluded to this above already, I would like to reiterate that given that the method is generally applicable to various graph constructions, I would have liked to see at least some results comparing the performance of graph-based NNS with graph constructions other than HNSW. Although HNSW is considered to be one of the best similarity graphs for NNS (as you claim), my understanding is that this was the case for Euclidean (i.e. non-hyperbolic) NNS. Given that the paper now considers the setting of hyperbolic graph-based NNS, a different graph construction may perhaps be better. Regardless, seeing a comparison of several (e.g. at least 3) graph constructions in an empirical setting would considerably help with ascertaining HNSW as a good graph construction for this setting. 

8. I would like to see more than a toy experiment (given in Section 5.3) to ascertain the results for the dense setting. The application of the dense theoretical results as is seems incomplete to me. Perhaps some analog of what was done in Prokhorenkova & Shekhovtsov (2020) is possible to obtain a real application of the theoretical dense results?

### Additional Comments

The paper writing was, for the most part, adequate. A non-exhaustive list of minor corrections/suggestions is given below:

- "opposite approach" in the introduction is not really well-defined. "alternative approach" would be more appropriate.
- For the first "$nM^d$" mentioned on page 3, it is unclear what $M$ is (i.e. whether it has some geometric meaning). If it is just a constant, simply say "where M is some constant". Moreover, I believe you overload the usage of $M$ to be both a Riemannian manifold and a constant. I would recommend using a calligraphic $\mathcal{M}$ to represent a Riemannian manifold.
- The following claim is made several times: "...hyperbolic geometry was recently found to be more suitable for data representation in various domains...". I would caution this by saying that hyperbolic geometry was shown to be more suitable for hierarchical data (Nickel & Kiela 2017, 2018), not necessarily data representation in general. Please introduce the necessary qualifiers when making such claims.
summary_of_the_review: ### Verdict

This paper developed an extension of the Euclidean graph-based NNS from Prokhorenkova & Shekhovtsov (2020) to hyperbolic space. Although the problem is relevant, the paper as is lacks considerably, both in terms of theoretical and empirical results. Namely, it does not address the sparse case theoretically, and the theory that is developed borrows heavily from Prokhorenkova & Shekhovtsov (2020); the necessary analytic constructions/proof techniques necessary to bridge the gap are fairly straightforward, and cast considerable shade on claims of theoretical novelty. Moreover, empirical results lack considerably. First, non-toy results were given only for the sparse setting, not the dense setting (which was the only setting for which theory was provided). The uniformity assumption and assumption of small dimension was not addressed in the application section. These assumptions were critical for a proper theoretical analysis, and should in some way be handled when the theory is applied. Only a single baseline was given for Section 5.1, and claims of hyperbolic graph-based NNS efficiency (over the Euclidean counterpart) were made by testing on 1 dataset with 1 graph construction. A considerably more thorough evaluation is required. Trials/mean/standard deviation were not reported, despite this being crucial for graph-based NNS. Only a single graph construction was considered throughout the entirety of the empirical evaluation, despite the fact that the tested setting (hyperbolic graph-based NNS) does not have a previously established state-of-the-art graph construction. All of this taken into account, I must recommend a reject rating for this paper.

### Updated Rating

In their revised paper, the authors have assuage some of my concerns as they have been laid out above. As a result, I have updated my rating to a 5/10. Given that the changes were fairly considerable, I hesitate to recommend acceptance until they have been carefully evaluated; moreover, I believe more can be done to address the concerns reviewers have, specifically surrounding empirical results.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper approaches the problem of nearest neighbor search in hyperbolic spaces with focus on graph methods. The authors claim to obtain an acceleration in hyperbolic spaces over Euclidean ones using graph based NNS method (e.g. Prokhorenkova 2020). The provide bounds on the dimension and Radius of search in the dense  NN domain (ie d<<logn). Experimental validation is presented which demonstrate the advantage of graph methods and also tradeoffs on efficiency in different parameters regimes to validate the theoretical analysis.
main_review: Strong points:
1.	The paper is clearly written and has the main ingredients of theoretical analysis accompanied with experiments and also experiments that attempt to validate the theoretical results. 
2.	I find the insight about graph based methods in hyperbolic spaces to be interesting, even though I find the bounds on parameters quite restricting, in particular since the problem of nearest neighbor search aims at high dimensions and the authors demonstrate their work in a dimension up to 6.

Weak points:
1.	Im less concerned with the uniformity assumption, though the lack of uniformity can also happen on the low dimensional manifold even just because of sampling rates in realistic scenarios. What bothers me more is the use of the low dimension in section 5.3. if the ambient dimension is so small what is the challenge in the NNS?
2.	If the authors need to address the intrinsic dimension, I recommend a separate parameter d’
3.	More insight for practitioners could be provided on the algorithmic setting: any parameters in the graph based method that should be tuned according to this constraints and insights? E,g,: The algorithmic role of R should be explained (e.g. in the c,r-ANN).
4.	Some more motivation on the advantage of hyperbolic spaces for real life settings can enhance the view on the impact of the method.
5.	Use of M is rather confusing, in (2) it is a Riemannian manifold but later it is a scalar.

summary_of_the_review: Overall the insights of the paper are important but their validity in the practical domain should be better explained in the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper addresses the important problem of nearest neighbour search for data that lives in hyperbolic space and provides a novel result on the relative time complexity of NNS in hyperbolic and Euclidean spaces under some assumptions.
main_review: Improving NNS for hyperbolic embeddings is potentially of significant practical importance as previous attempts to build production systems based on this geometry (e.g. recommender systems) has been hampered by the lack of efficient recall systems in the very large n domain. As this is the area the authors focus on, this is potentially a significant work in the development of machine learning methods that utilise hyperbolic geometry. The paper is also very nicely written, being both clear and without errors.

The main result of the paper is that under certain assumptions, NNS in hyperbolic space can be faster than in Euclidean space.

My main concerns are around the validity of the assumptions and the empirical evaluation.

The assumption that d << log n seems very reasonable, but the data elements being uniformly distributed within a ball of radius R seems much more restrictive, as the authors point out. While previous works also assume uniform data distributions, I would like the authors to comment to what extent their theoretical results would generalise to more realistic settings. While I agree with the statement that points that are uniformly distributed in the Poincare ball can be used to generate complex networks, in practice, the NNS would not function on a set of points (presumably generated by some ML system) that have this property and I am interested in how the performance guarantees change as this restriction is relaxed.

Can the authors please also comment on this statement "The obtained time and space complexity heavily relies on this radius: for small values, the obtained results are similar to the spherical case, while for larger values, the exponential growth of hyperbolic volumes (see the next section) allows us to obtain even faster convergence." Which domain is likely to be encountered in practice? I would have thought that R was a design decision affected by e.g. choices on learning rate or initialisation in the ML system producing the hyperbolic representations.

Having established theoretical results for d << log n, the empirical evaluation is somewhat disappointing. Why did the authors choose to do the theoretical analysis for the dense case and then empirically analyse the sparse case? Open source code exists that would allow the authors to generate hyperbolic embeddings of a lower dimension. Could the authors perform this experiment?

In Section 5.1 and 5.2, the outperformance of HNSW is not particularly surprising given that this method was itself inspired by hyperbolic geometry and it's unclear if this is simply an artefact of embedding a tree structured dataset. Could the authors try additional datasets, for instance Wordnet at least?


The following citation is also missing "Neural Embeddings of Graphs in Hyperbolic Space", Chamberlain, Clough and Deisenroth, 2017.
summary_of_the_review: Interesting and potentially impactful work, but I would like to see more comment on the validity of the assumptions and improved empirical evaluation before raising my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper looks into graph-based algorithms for nearest neighbor search (NNS) problem in the hyperbolic space.

Theoretically, the authors derived the time and space complexity of graph-based NNS under some assumptions (data uniformed distributed in the ball, low dimensional dense), and in some cases, graph-based NNS has lower time complexity in the hyperbolic space. 

Practically, the authors apply the methodology to Poincar{/'e} Glove word embeddings, where it outperforms some existing baselines. 
main_review: This paper analyzed best-first-search graph-based NNS algorithms in the hyperbolic space theoretically under some assumptions and practically to the Poincar{/'e} Glove word embeddings, which is an interesting work to attract research of NNS in hyperbolic space. 

Theoretically the authors do show that under some assumptions and in some cases, the graph-based NNS in hyperbolic space can be more efficient than that in the Euclidean space, though clearly these assumptions probably not hold in realistic dataset. Further the authors apply the methodology to the Poincar{/'e} Glove data, and the experiments help justify the efficiency of search over hyperbolic space. 

However, there are some weakness:
1. the assumptions are strong, it looks like to be common in this area to assume that data elements are distributed uniformly within a sphere in the space? also the dense setting, where one must either have a lot of data points or use a low dimensional hyperbolic space. 
2. the experiments over Poincar{/'e} Glove word embeddings look good, however, is it possible to include some other datasets and varies the dimension in a realistic setting (not only for the synthetic  datasets)? which I believe would help convince readers of the efficiency of the algorithms for real datasets.

Also I have some questions regarding the paper
In the paper, the authors use the assumption that data uniformed distributed in the ball of radius R in the hyperbolic space, what's the difference to uniform over the sphere? Particularly in high dimension case, uniform over the ball would be close to uniform over sphere (at least in Euclidean space), what results would be caused, can the authors explain more on this?

summary_of_the_review: This paper is an interesting work to analyze best-first-search graph-based NNS algorithms in the hyperbolic space.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to use the graph-based method for similarity search in hyperbolic space. Extensive analysis shows that graph-based method achieves sublinear time complexity for hyperbolic space and its performance is even better than for the Euclidean space under some mild conditions. Empirical experiments are also conducted to validate the theoretical analysis. 
main_review: Thanks for the interesting paper. It is interesting to know that the graph-based method, which works very well for the Euclidean space, also works for the hyperbolic space. The analysis is solid and the experiments justify the theoretical findings.

=================

I have read the reviews of other reviewers and the author response. I still think that the paper is of value by extending the analysis of Euclidean space (an ICML’21) to hyperbolic space. However, I agree the experiments should be improved to include more datasets/graph-based similarity search algorithms.
summary_of_the_review: I think this is a solid and interesting paper.
review_title: null

Meta-review: The paper studies the nearest-neighbor search problem for objects embedded in hyperbolic space. It develops a graph-based approach to NNS in hyperbolic space, showing (interestingly) that the time complexity of graph-based NNS can be lower in hyperbolic space than in Euclidean space under some assumptions. This nice theoretical analysis feels like an intuitive result, as hyperbolic space is in some sense more graph-like/tree-like then Euclidean space, so it is not too surprising for graph-based methods to perform better here. What's really cool about this theoretical result is to see something that is _easier_ in hyperbolic space—normally things are harder in hyperbolic space due to its great volumes and significant curvature. The discussion among reviewers was mostly positive, with the majority of reviewers leaning towards acceptance and multiple reviewers expressing that the author response and revision addressed their concerns and raising their scores accordingly. There is some question as to whether the revision is too large and should go through peer review again, but on balance I think it is close enough to the original submission that it can be reasonably accepted here. Therefore, following the majority opinion of the reviewers, I will recommend acceptance.
Decision: Accept (Poster)