Graph-based Nearest Neighbor Search in Hyperbolic Spaces
Authors: Liudmila Prokhorenkova
Dmitry Baranchuk
Nikolay Bogachev
Yury Demidovich
Alexander Kolpakov
Venue: ICLR 2022 Poster (2022)
Keywords: similarity search
nearest neighbor search
hyperbolic space
graph-based nearest neighbor search

Abstract: The nearest neighbor search (NNS) problem is widely studied in Euclidean space, and graph-based algorithms are known to outperform other approaches for this task. However, hyperbolic geometry often allows for better data representation in various domains, including graphs, words, and images. In this paper, we show that graph-based approaches are also well suited for hyperbolic geometry. From a theoretical perspective, we rigorously analyze the time and space complexity of graph-based NNS, assuming that an $n$-element dataset is uniformly distributed within a $d$-dimensional ball of radius $R$ in the hyperbolic space of curvature $-1$. Under some conditions on $R$ and $d$, we derive the time and space complexity of graph-based NNS and compare the obtained results with known guarantees for the Euclidean case. Interestingly, in the dense setting ($d \ll \log n$) and under some assumptions on the radius $R$, graph-based NNS has lower time complexity in the hyperbolic space. This agrees with our experiments: we consider datasets embedded in hyperbolic and Euclidean spaces and show that graph-based NNS can be more efficient in the hyperbolic space. We also demonstrate that graph-based methods outperform other existing baselines for hyperbolic NNS. Overall, our theoretical and empirical analysis suggests that graph-based NNS can be considered a default approach for similarity search in hyperbolic spaces.

Published as a conference paper at ICLR 2022
GRAPH-BASED NEAREST NEIGHBOR SEARCH IN HYPERBOLIC SPACES
Liudmila Prokhorenkova
Dmitry Baranchuk
Yandex Research
Yandex Research
Moscow, Russia
Moscow, Russia
ostroumova- waw.ovvvaalaaaea.....mmaa
cbaraachhul@ynndex-tee.. ru
Nikolay Bogachev
Yury Demidovich
IITP RAS; MIPT
MIPT
Moscow, Russia nvbogach@mail.me
Moscow, Russia
demi dovich. wwwpeicchhu@@ehysec.ceee edd
Alexander Kolpakov
Université de Neuchåtel
Neuchâtel, Switzerland
kol holpakov.o a eexanderr@gaaa 1, com
ABSTRACT
The nearest neighbor search (NNS) problem is widely studied in Euclidean space, and graph-based algorithms known outperform other approaches for this task. However, hyperbolic geometry often allows for better data representation in various domains, including graphs, words, and images. In this paper, we show that graph-based approaches are also well suited for hyperbolic geometry. From theoretical perspective, we rigorously analyze the time and space complexity of graph- based NNS, assuming that an n-element dataset is uniformly distributed within a d-dimensional ball of radius Under some conditions on I and d, we derive the time and space complexity of graph-basee NNS and compare the obtained results with known guarantees for the Euclidean case. Interestingly, in the dense setting (d < log n) and under some assumptions on the radius R. graph-based NNS has lower time complexity in the hyperbolic space. This agrees with our experiments: bedded in hyperbolic and Euclidean spaces and show that graph-based NNS can be more efficient in the hyperbolic space. We also demonstrate that graph-based methods outperform other existing baselines for hyperbolic NNS. Overall, our the- oretical and empirical analysis suggests that graph-based NNS can be considered a default approach for similarity search in hyperbolic spaces.
the hyperbolic space of curvature
consider datasets
INTRODUCTION
Given a dataset D of elements and an arbitrary query q, the goal of the nearest neighbor search (NNS) quickly retrieve one or several elements from closest to q. NNS extensively used in wide range of machine learning systems: for non-parametric classification and regression, language modeling, information retrieval, recommendations, and many others (Bishop) 2006) [Chen et al.)
2018 May & Ozerov| 2015) Shakhnarovich al. (2066. In large-scale applications, searching for the nearest neighbors can be bottleneck, so this operation's 's efficiency of the essence.
Many efficient NNS algorithms exist for Euclidean and, generally, l, spaces. Among them are meth- ods based on recursive partitions of the space, e.g., k-d trees and random projection trees (Bentley 1975 Dasgupta & Freund, 2008; Dasgupta & Sinhal 2015] Keivani & Sinhal 2018), well stud- ied Locality Sensitive Hashing (LSH) (Indyk & Motwani, 1998), and methods based on similarity graphs (Fu al. 2019 Twasaki & Miyazaki 2018 Malkov et al. 2014 Malkov & Yashunin 2018).

---

Published as a conference paper at ICLR 2022
However, hyperbolic geometry is often found to be more suitable for data representation in various domains, including natural language processing, computer vision, graph analysis. and recommenda-
tions (Chamberlain et al. (017,Chhami [Chami al. [2200] Khrulkov et al. 20 Mirvakhabova et al. 2020)
Nickel & Kiela| 201 7 2018; TTifrea et al. 2019). Intuitively, the hyperbolic space has advantages over standard representations when data has latent hierarchical structure which is often the case. Hence, a natural question is: how to perform efficient NNS in hyperbolic spaces? This problem has started to gain attention recently and was addressed in Wu & Charikar (2020). In a nutshell, Wu & Charikar (2020) show how any given Euclidean NNS algorithm can be applied to the hyperbolic space. To get convergence guarantees, one has to call the chosen NNS method several times, which leads to increased NNS complexity compared to the original Euclidean algorithm. In the current pa- per, we choose an alternative approach and apply leading NNS technique directly to the hyperbolic space. We demonstrate that under some assumptions, the proposed method does not have increased complexity and may even reduce the query time compared to its Euclidean counterpart.
We focus on graph-based NNS methods that are based on a best-first routing over similarity graphs Namely, at the pre-processing phase, a similarity graph is constructed on the elements of the dataset. Then, given a query q. start from some element of D and measure distances between its neighbors and q. The neighbors are added to a priority queue. Then, we pick the closest to q candidate from this queue and continue the process (Fu et al., 2019; [wasaki & Miyazaki 2018 Malkov et al.) 2014 Malkov & Yashunin 2018). It was found empirically that graph-based NNS outperforms other approaches in many large-scale applications (Aumüller et al., 2219 In contrast other NNS methods, graph-based approaches can be easily applied to non-Euclidean spaces. Indeed, for most algorithms, both graph construction and graph routing can be performed without appealing to the geometry of the underlying space only the relative ordering of neighbors is used. Thus, one can replace Euclidean distance with the hyperbolic one in a favorite traph-based approach. However, is a priori not known how graph-based approaches would work in such a non-standard scenario.
In this paper, we show that graph-based approaches are well suited for NNS in hyperbolic spaces. From a theoretical perspective, we analyze the time and space complexity of graph-based NNS, assuming that the data elements are distributed uniformly within a ball of radius R in the hyperbolic space of curvature -1. In this regard, we compare the obtained results with [Prokhorenkova & Shekhovtsov (220)) who studied graph-based algorithms for uniform distribution of elements over d-dimensional sphere. In the dense setting (assuming that d < log and R does not grow too fast), we derive the time and space complexity using the fact that locally hyperbolic graph-based based NNS behaves similarly the Euclidean case. However, globally, graph-based search in hyperbolic spaces requires fewer search steps. Thus, hyperbolic NNS can be even more efficient compared to its Euclidean counterpart. In the sparse setting (d > log n), we show that hyperbolic NNS has similar complexity to the Euclidean case.
From a practical perspective, we first illustrate our theoretical findings via synthetic experiments on uniform data. Then, we analyze graph-based hyperbolic NNS in practical applications where our theoretical results cannot be directly applied. For this, we consider Poincaré Glo Ve word em- beddings (Tifrea et al., (219) that are known to outperform the standard representation for tasks of similarity, analogy, and hypernymy detection. We compare graph-based NNS with existing base- lines (Wu & Charikar 2020) and show that graph-based approaches have significantly better per- formance. We also compare the performance of graph-bar based NNS for Euclidean and hyperbolic representations of the same sets of clements and observe that hyperbolic NNS can be more efficient.
2 PRELIMINARIES
Graph-based nearest neighbor search Graph-based algorithms for NNS are known to outper- form other approaches many large-scale applications (Aumüller et al. 2019). The main idea is to construct a proximity graph at the pre-processing stage and traverse this graph towards the query q at query time. The best-first search is usually used for traversal: we maintain a priority queue, and at each step, we pick the closest to q candidate from this queue, measure distances between its neigh- bors and q. and add the neighbors to the queue. Many algorithms are based on this idea (Baranchuk) et al. 2019 Fu et al. 2019 Twasaki & Miyazaki 2018 Malkov & Yashunin 2018).
Unfortunately, despite their success in practice, graph based approaches do not have solid theoretical guarantees. This problem was first approached by [Laarhoven (2018) who provided time-space
2

---

Published as a conference paper at ICLR 2022
trade-offss for approximate nearest neighbor (ANN) search in sparse datasets (d >> log uniformly distributed on a d-dimensional Euclidean sphere. This work considered nearest neighbor graphs, where each point is connected to its neighborhood lying within ball of fixed radius, and assumed greedy graph traversal. [Prokhorenkova & Shekhovtsov (2020) extended this result: for the uniform distribution, the authors consider both sparse (d >> log n) and dense (d < log ni) regimes, and they analyze the effect of two improvements commonly used in practice: replacing greedy search by best-first (or beam) search and adding long edges to speed up graph traversal at early stages.
In this paper, we aim at understanding graph-based NNS in hyperbolic spaces. For this, we adopt a similar setup to Prokhorenkova & Shekhovtsov (2020), but instead of a uniform distribution over sphere, we assume uniform distribution within a ball of a certain radius in the hyperbolic space. 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 allows us to obtain even faster convergence in the dense regime.
Hyperbolic geometry Now, let us discuss the basies of hyperbolic geometry. Let Rd.1 be the (d + -)-dimensional Minkowski space, i.c., the real vector space Rd+1 equipped with the inner product of signature (d, 1):
() Toyo ZiyI + + Tayd-
The vector model of the d-dimensional hyperbolic Lobachevsky space Hd is the connected compo- nent of the standard two-sheeted hyperboloid contained in the future light cone: Hdd = {x E R4, zu 0}. The hyperbolic metric is given by cosh p(x, - (x. v) From the defi- nition of the hyperbolic space, we see that æ da. Ratcliffe 2019).
(x, x)n-
/ + 2 +
zz The volume element in H'
V VI+af
Hyperbolic space is known to be useful for data representation in various domains. It is especially convenient for embedding hierarchical data (Nickel & Kiela (017). The reason is that the volume of a ball in the hyperbolic space grows exponentially with its radius, in contrast to the Euclidean space, where the growth is polynomial. Formally, let (x, r) be a closed hyperbolic ball centered at a point x E Hdd of radius > 0. Then, its volume is
Volga r)) = Vol(s" l- sinh (t) dt,
(2)
where gd-1 is the unit (ssheee and Vol(M) denotes the full volume of a Riemannian manifold M. That is, Vol(Sd-1)= 2/2 //d//// For >> logd, we have
V r)) ~ Vol(s--1) crd ord o(d-22-4)
(3)
The main term here is (d-1)) the ball volume Volga (B(x, r)) grows exponentially when is large. However, for small hyperbolic balls (as r + 0), we have sinh(r) ~ r. Hence, the volume of provide formal general result that shows that not only the above argument is correct, but also the volume of a measurable subset of hyperbolic ball behaves asymptotically exactly like its Euclidean analog.
ball (2) behaves similarly to the Euclidean case. In Section [.
Nearest neighbor search in hyperbolic space While there are many NNS algorithms for ép spaces, little is known about efficient hyperbolic analogs. Krauthgamer & Leel (2006) proved the existence of an approximate near neighbor algorithm for general geodesic spaces of hyperbolicity 6. From a theoretical perspective, the bound is given in terms of the doubling dimension. For uniform datasets, we may conclude that the obtained time complexity is 20(d) log² n, while the constant in the exponent is not given. In contrast, difference that the algorithm of Krauthgamer & Lee (2006) requires O(n²) storage that is usu- ally infeasible in practice. In contrast, graph-based algorithms require Md for some constant M if d & log n. Finally, while the theoretical analysis is given in a very general setup, no implementation is provided and extracting efficient implementation from the proof is challenging.
specify this term we focus d + co. Another
In a recent paper, Wu & Charikar (0200) reduce the problem of hyperbolic NNS to Euclidean NNS. Namely, assume that have an efficient Fuclidean algorithm and a dataset is represented in the
3

---

Published as a conference paper at ICLR 2022
Poincaré ball model. Then, we can apply the algorithm to the Euclidean representation, but this may not give the correct nearest neighbor. Wu & Charikar (2200) propose several solutions allowing for obtaining either exact approximate nearest neighbors. In all of them, the Euclidean NNS algorithm should be applied several times. One approach is to repeatedly apply the algorithm to the whole dataset, but after each run, appropriately change the query point get better hyperbolic neighbors at subsequent iterations. The time complexity of this algorithm is k + 1 times larger than the Euclidean search if the Euclidean nearest neighbor for the query is the k-th nearest hyperbolic neighbor. Another approach is to splits the ball into thin annuli and performs the approximate Euclidean NNS for each of them separately. From a theoretical perspective, is hard to compare our results since Wu & Charikar (2020) do not consider any particular algorithm. We cannot apply this general result to graph-based algorithms since existing guarantees for the Euclidean space assume a uniform distribution. However, if we consider the uniform distribution in the Poincaré model of the hyperbolic space, the corresponding Euclidean distribution is far from uniform. i.c., the guarantees cannot be transferred. From a practical perspective, we compare graph-based algorithms with the method of Wu & Charikar (2020) and show that graph-based NNS is more efficient.
3 SETUP AND NOTATION
The current paper aims at analyzing how hyperbolic geometry of the underlying space affects the time and space complexity of NNS. In this regard, we compare results with Prokhorenkova & Shekhovtsov (2000), so we use a similar setup and notation for convenience.
To make the analysis feasible, Laarhoven (2018) and Prokhorenkova & Shekhovtsov (2020) assume that the dataset is uniformly distributed on a sphere. The uniformity assumption is fairly strong. In Proohhorenkova & Shekhovtsov (2020), this setup partially motivated by techniques allowing to make a dataset more uniform while approximately preserving the distances (Sablayrolles et al., 2018), which are helpful in some practical applications. We additionally note that in hyperbolic spaces, the uniform distribution of nodes within a ball leads to structures that are similar to real ones: if we consider a geometric graph on such nodes, we obtain the power-law degree distribution, small diameter, and high clustering coefficient (Krioukov et al. 2010), which further supports the meaningfulness of the uniform distribution in our scenario. The compactness of the sphere simplifies the analysis in previous work as it allows for avoiding boundary effects. However, we cannot make this assumption in our setup, as a sphere in the hyperbolic space isometric to a sphere in the Euclidean space. Hence, to use the properties of hyperbolic geometry, we assume that the dataset is uniformly distributed within a ball of some radius the hyperbolic space.
Formally, consider a ball B (R) C Hdd of radius R > 0. Assume that the dataset is a finite collection of points D= (xi,..., ] C Hd, where x; E D are i.i.d. random vectors uniformly distributed in B(R). For a given query q E (R), let X E D be its nearest neighbor. Then, the goal of the exact NNS is to find x. For completeness, following Laarhoven (2018); Prokhorenkova & Shekhovtsov 20200) also consider c, r-approximate near neighbor problem (c, r-NNN.. In this scenario, it is assumed that q is planted uniformly within a fixed distance > 0 from its nearest neighbor X and the goal is to return any x' such that p(q, x') S cr for fixed value c >>> (Chen et al. 2018)) Formally, for the exact nearest neighbor search, we also assume that is planted uniformly within a distance from some element x. However, we do not restrict the radius r (the only restriction is that x should be the nearest neighbor for q).
We follow the standard assumption that the dimension d = d(n) is an increasing function of n (Cen et al.) 2018). We mostly focus on the so-called dense regime, where d < log n. For the sparse regime (d > log we formally show that graph-based NNS in the hyperbolic space has similar complexity to NNS on the sphere.
Graph-based approaches usually imply constructing a nearest neighbor graph (or its approximation), where each element is connected to its k nearest neighbors. As we deal with uniformly distributed datasets, we assume that each node x is connected to all nodes y at a distance p(x. y) S p² for some p² chosen at the preprocessing stage. This is more convenient for the analysis, while similar results can be obtained for k-NN graphs, see Appendix D Hence, at the preprocessing stage, we construct a similarity graph using p" Next, receive query q, sample random node D, and at each step of the graph-basee greedy descent, we measure the distances between the neighbors of the current node and q and move to the closest neighhor while we make such greedy steps.
4

---

Published as a conference paper at ICLR 2022
4 CONVERGENCE AND COMPLEXITY OF GRAPH-BASED NNS
4.1 LOCAL PROPERTIES OF HYPERBOLIC SPACE
Further in this section, we give formal statements regarding the convergence and complexity of greedy graph-based algorithms. Convergence depends on the probability of making a step towards the query from given element. This probability, in turn, depends the volumes of some balls' intersections. As our proof shows, only 'local' properties are important for convergence for the dense regime. Let us show that under some conditions, the local properties in the hyperbolic space are similar to those in the Euclidean space.
Formally, let 01, 0) and let T.H {x Ied so =1} IRd be the tangent space. Let è be the central projection é: Hd + T.H = IRd from the origin o = (O....,0). O). The following lemma holds.
Lemma 1. Suppose that U C HH is measurable set such that U c r(z,r). Ifr < L
Va and
+ oo, then we have Volga (U)) = Volg= (1- 0
This result allows us to apply the bounds on volumes of Euclidean balls intersections to such vol- umes in the hyperbolic space for small radii.
4.2 INTUITION BEHIND THE CHOICE OF PARAMETERS
Our theoretical analysis is asymptotic, meaning that the number of elements n tends to infinity. Hence, assume that the dimension d d(n) and the ball radius R = R(n) depend on n. This section discusses our restrictions on d(n)) and R(n) and how they affect the analysis. Here, we do not aim giving mathemattcally rigorous statements but rather explain underlying intuitions. The formal results can be found in Section 4.3
Assuming that the dataset is uniformly distributed on a unit sphere, there are two principally different regimes: dense with d < log n and sparse with d >> log n (Prokhorenkova & Shekhovtsov 20220. In the dense regime on sphere, the distance from any element to its nearest neighbor tends to zero as n grows. In this case, the greedy algorithm reaches the nearest neighbor with probability 1 - (11) if graph degree is Md for M > v2. In the sparse regime, informally speaking, all nodes are at spherical distance about π7 from each other, making the NNS much more challenging. this case, the graph degree has to grow as n² for some >> O in order to solve the approximate near neighbor problem (Prokhorenkova & Shekhovtsov 2020).
In this paper, we mainly focus on the dense regime with d < log As discussed in (Prokhorenkova & Shekhovtsov) 2020), this setup is more realistic for uniform data. Indeed, while in practice datasets are often embedded into spaces of large dimension. they usually have much smaller in- trinsic dimension < d (Beygelzimer et al. 2006 Lin & Zhao 2019). It is also important to note that hyperbolic spaces are known to be beneficial when the dimension is small (Gu et al.) 2019 Shevkunov & Prokhorenkova] (02T). For completeness of the study, we also analyze the sparse regime and theoretically show that under some conditions on R graph-based NNS in the hyperholic space has similar time and space complexity to NNS on the sphere.
We assume that the dataset is uniformly distributed within a ball - B(R) in the hyperbolic space. Changing the radius R is equivalent to changing the curvature of the space (Petersen 2016). So, we may either assume that the curvature change or assume that the radius is fixed while the curvature C = C(n) changes. We further assume that -1 is fixed. Thus, we have three parameters: the number of elements n, the dimension d = d(n),, and the radius R = R(n).
1 fixed while the radius of the ball R R(n) may
Denote by VR( the volume of B, i.c., Va(R) == Volge(B(R)) and by (R( the normalized volume, i.e., (R) := Vz(R)/Voll) (1) Let us analyze (approximately) the distance a from an element to its nearest neighbor. Intuitively, we should have
(B(a)) Volga (B())
1
Volga (B(a)) 2 Va(R)
~
(4)
5

---

Published as a conference paper at ICLR 2022
Assume for now that < 1/vV (approximately Euclidean setup, see Section 4.1 In this case, Therefore, from
Volga(((a)) Volg) Vol(Su-1)a"
Va(R) n Vol(S<-1)
Rd
Let us find an upper bound on the radius R such that the condition a < 1/vd satisfied. Note that va( (t) = O (e R(d-1) 1) 2-d. d= (see Appendix
Thus, we need
Va R
1/d
1 Vd
( (cR(d=)) 2-d
c < En 1/d-1) . 1/2 Vd
n
n2
Based on that, we further assume that in the dense regime, e < n/1((d1), d/2/2 In this case, the distance to the nearest neighbor a a= (1//V)) and locally the graph-based search behaves similarly to the Euclidean case. We empirically show that our assumption on R is reasonable: larger values of R lead to less efficient NNS.
4.3 MAIN RESULTS
In this section, we formally analyze the performance of graph-based NNS for uniform datasets in the hyperbolic space. As discussed above, to construct the nearest neighbor graph, we connect each point to neighborhood located within ball of fixed radius. In the dense regime, for any constant M 1, let G(M) be graph obtained by connecting x, and Xj iff
x,) S M (dva(R)
1/d
With this condition, we get about Md neighbors for each node. The following theorem holds.
Theorem 1. Assume that d(n) is such that log log < d(n) < log and R(n) such that et < n n d-1122 For the exact NNS, let M be constant s.t. M > V2. Then, with probability 1 ((). G(M)-based NNS finds the exact nearest neighbor. For c, r-NN with
some constant e > 1, let M be a constant s.I. M. >
462
Then, with probability o(1),
32--1
G(M))b NNS solves c, C.N-NNN for any r.
In both cases, the time complexity is O (M4. n/dd R. (va(R))-1/d);
the space complexity is O (Md logn).
The formal proof of this theorem is given in Appendices A and in Appendix Dww prove a similar theorem for k-NN graphs with [M
Theorem covers several different regimes. First, assume that R & 1/vd. In this case, the geometry approximately Euclidean. We have va(R) Rd /d, so the following corollary holds.
Corollary 1. If = R(n) < 1/Vd, then in Theorem the time complexity is (M4 (/d) n///).
As expected, this result is similar the corresponding theorem in Prokhorenkova Shekhovtsov (2020). However, R becomes larger, time complexity changes. For instance. if R >> log d, then we have Va( Rt) ~ R(d-1) @(d-12-d). Thus, we get the following corollary.
Corollary If R = R(n) > log d. then in Theorem we obtain the time complexity O (Md. 1/d. R e m(d-1)/d).
From this corollary we see that the time complexity decreases with the radius R. Thus, make the complexity smaller, we should take larger values of R. According to Theorem | we can take R such that R n उ (e=f/(Vd,,, /(Vdd))) where & sp(n) co. We obtain the following corollary.

---

Published as a conference paper at ICLR 2022
Corollary 3. for arbitrary y p(n) we have ea /(Vdd( and R > log d. then in Theorem 1 we get the time complexity O (Md logn n d-//////11111 .p).
1/2
Thus, in the hyperbolic space, the number of steps can be reduced from n n//d to about log n. This shows that compared to the Euclidean case, NNS over nearest neighbor graphs in the hyperbolic space can be more efficient (under the conditions considered in this paper). Intuitively, the difference between Euclidean and hyperbolic regimes is due to the fact that the volume of a hyperbolic ball grows exponentially with its radius. As consequence, from, e.g., the origin of the ball. Note that in the Euclidean space, we can also reduce the number of steps to log via adding long edges (Prokhorenkova & Shekhovtsov 2020). In contrast, in hyperbolic space, this can be achieved without additional tricks. Our experiments on synthetic datasets confirm that without long edges, NNS is much more efficient in the hyperbolic space when dimension d is small.
need fewer steps reach any element
Finally, let us discuss the sparse regime with > logn. Here we show that the elements are tightly concentrated near the boundary of the ball and thus the convergence guarantees resemble those on the sphere. In this case, we construct the graph G(M) by connecting such elements x, and x, that
cosh p(x,, xj) S cosh? 2 R Risinh" R.
V
12M logn To formulate the result, we introduce the following
notation: for any constant e > let Ol. == cosh? R-cosh(arccosh((oor) R)/e).
sinh I
Theorem 2. Assume that d > log n and R. >>> log d. Let c 1 and let M be any constant such that M प.-.. Then, with probubility o(1), G(M) NNS solves G, r-ANN (for any r);
the time complexity of this procedure is θ (n (n!)M+)( the space complexity is θ (n² ()))).
The proof is given in Appendix E This theorem shows that the complexity of hyperbolic NNS for sparse datasets is similar to that on a sphere. However, for large d, the calculation error in the hyperbolic space may become significant even for moderate values of R. We also remark that the condition Rt >> log d is chosen to simplify the proof using the approximation (3) but this restriction does not seem to be necessary for the theorem to hold.
EXPERIMENTS
In this section, we first illustrate our theoretical results from Section 3 on synthetic datasets uni- formly distributed within balls of different radii in the hyperbolic space. Then, we compare graph- based approaches with the algorithm proposed by Wu Charikar (2020) on Poincaré Glo Ve word embeddings (Tifrea et al.) 2019). Finally, we compare the performance Euclidean and Poincaré GloVe Ve datasets to show that the efficiency can be even better for hyperbolic representations. Addi- tional experiments can be found in Appendix; the code supplements the submission.
5.1 ILLUSTRATING THEORETICAL. RESULTS ON SYNTHETIC UNIFORM DATASETS
In this section, we illustrate Theorem I and our corollary that for simple nearest-neighbo graphs and sufficiently small dimension d, graph NNS is more efficient in the hyperbolic space. For this, we follow the setup of [Prokhorenkova & Shekhovtsov (2020) and perform a synthetic experiment. We generate datasets uniformly distributed in different spaces: 1) on a sphere (Prokhorenkova & Shekhovtsov 2020), 2) within a Euclidean ball, 3) within a ball of radius /t in the hyperbolic space of curvature - For all spaces, we fix n = 10 and vary the dimension d E (2,4,6) 6).
For the hyperbolic space, consider different values of R which is equivalent to varying curva- 1) / vd. Thus, roughly speaking, we obtain the get Rmaz Rs 13.5; for d = 4,
ture. Recall that Theorem requires et < (dd-1)
following upper bound R: Rmaz log 7-i log Vd. For d = get Rmar 3.9; while for d = 6 we have R,mr = 1.9. Thus, even for d = 6, the bound on the radius is sufficiently small and the obtained geometry becomes similar to Euclidean (if we consider the theoretically analyzed parameter range). Thus, we do not consider d > 6 in this experiment.
First, we analyze the performance of greedy search over nearest- nearest-neighbor graphs; this setup cor- responds to theoretical analysis. To get the complexity-vs-ace vccccuuacy curves, we vary the graph
7

---

Published as a conference paper at ICLR 2022
L-WV
1:004 cod
2,00
1.000
1.00
0.090
0.00
0/0
Hyperalk Fook
2-33
Ixporblic En13
2003
20
100
800
1-30 Long Engun d=2
2:10 Long divd
IchN cHd
1.000
1.30
0.98
0.00
0.700
0003
Hypertalic
Hypetalk:
Hypertoic Eook
1080
205
226
356
200
220
340
203
200
300
383
225
200
300
450
500
Figure 1: Greedy search over NN graphs without (top row) and with (bottom row) long edges
degree. As primary measure of the search accuracy, we consider Recall@1 1111. The search com- plexity is the average number of distance computations (DCS) per query. In Figure [ we see that spherical and Euclidean spaces are similar. Recall that the Euclidean space can thought of as the hyperbolic one with R + O. Then, as R increases, the performance of NNS in the hyperbolic space improves. However, after some point, larger values of reduce the quality of NNS. noting that this threshold agrees well with the dynamic of Rmaz (while being smaller, as expected).
worth
Then, we analyze what happens we add long edges known and Euclidean spaces when the dimension d is small. To incorporate long edges into NN graphs, follow the procedure described in Prokhorenkova significantly boost the performance of NNS in spherical and Euclidean spaces. Note that they also improve performance in hyperbolic spaces, but the boost is smaller. As a result, the efficiency of NNS in all spaces becomes similar.
essential for NNS spherical
Shekhovtsov (2020). As expected, long edges
We also conduct similar experiments with greedy search replaced by the best-first search, which is standard technique for graph-based NNS performance improvement. The conclusions the same; we include the figures in Appendix
5.2 COMPARISON WITH BASELINE
Let us analyze the performance of graph-based NNS in a more realistic setup. For this, we col- lect the largest publicly available Poincaré GloVe vocabulary of 189, 533 unique tokens. Poincaré GloVe was shown to outperform the Euclidean representation for tasks of similarity, analogy, and hypernymy detection (Tifrea et 2019). The dimensionality of the embeddings 100. The set of tokens is randomly split into the base set of 180K elements and the query set of the remaining elements for evaluation. Note that the dataset is not uniform and the dimensionality is sufficiently large, so our theoretical analysis cannot be directly applied.
On the base set, we construct the HNSW graph (Malkov & Yashunin 2018) that known achieve state-of-the-art results on many datasets. As for the search algorithm, we perform the best-first search. The parameter e Search determines the stopping criteria of the best-first search and allows us vary the complexity versus accuracy tradeoff. For the baseline, the only practical algorithm we are aware of is proposed by Wu & Charikar (2020). The algorithm is called Spherical Shell: suggested to split the Poincare ball into thin annuli and perform approximate Euclidean NNS (the authors use LSH) for some of them separately. Unfortunately, the implementation is not provided
pttpss://itthb..e
frea hwtpa//poonnggggggg oov
8

---

Published as a conference paper at ICLR 2022
by the authors, implementation. To make the comparison fair, count the number of distance computations instead the actual time, as the latter may depend on the efficiency of our implementation. The algorithm details and parameter tuning are discussed in Appendix
Rocallg
Spherical Shell
GloVe
903
1000
1000
500
1400
DCS
DCS
Figure 2:
HNSW Spherical Shell
Efficiency of HNSW in hyperbolic space vs Euclidean space
Figure 3:
Poincaré GloVe embeddings
The results shown in Figure 2 We see that HNSW significantly outperforms the baseline. This confirms that applying an algorithm directly to the hyperbolic space is more efficient than reducing the problem Euclidean NNS. Some additional experiments can be found in Appendix: we evaluate another graph-based algorithm and consider more datasets.
5.3 EUCLIDEAN VS POINCARÉ GLOVE
We also compare the efficiency of graph-based methods for Euclidean (Pennington et al., 2014) and Poincaré (Tifrea al., 2019) GloVe embeddings of the same tokens. Note that the results cannot be compared directly: Glo Ve and Poincaré GloVe have different geometry, so nearest neighbors for the same queries may differ. Thus, only aim show that switching from Euclidean hyperbolic embeddings does not make NNS significantly less efficient. Figure 3 shows that HNSW built on embeddings in the hyperbolic space is even more efficient than HNSW over Euclidean embeddings This further confirms the applicability of graph-based methods to hyperbolic representations.
6 CONCLUSION
This paper conducts a theoretical and empirical analysis of graph-based nearest neighbor search in hyperbolic spaces. First, we theoretically analyze the performance of greedy search over nearest- neighbor graphs assuming that the dataset is uniformly distributed over ball of radius R in the hyperbolic space. Assuming the dense regime (d < log n)) and that the absolute value of the curva- ture is not too large, we show that locally graph-based exploration is similar to the Euclidean case. However, globally, hyperbolic geometry allows for reducing the number of steps significantly (for plain NN graphs). For sparse regime (d >> I), we show that NNS has similar complexity in Euclidean and hyperbolic spaces.
From practical perspective, show that graph-based algorithms superior to other existing methods. Also, compared to the Euclidean NNS, switching to hyperbolic space does not lead to significantly increased complexity and may reduce the query time. We hope that research will attract more attention to theoretical and empirical analysis of NNS in hyperbolic spaces and, in particular, graph- based methods.
Our work is the first step towards understanding graph-based methods for hyperbolic representa- tions, and there are plenty of directions for future research. In particular, the assumptions of Theo- rem [ [imply locally Euclidean behavior of the algorithm. It would be useful to extend this theorem beyond locally Euclidean neighborhoods by relaxing the upper bound on R. Of course, it is also important to relax the uniformity assumption, but this problem is still to be addressed for a more simple Fuclidean case.
Note that computing the hyperbolic distance has the same complexity computing the inner product, follows from Equation (1).

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
part of work of Nikolay Bogachev was done during his postdoc at Skoltech.
REFERENCES
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 2019.
Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, and Artem Babenko. Learning to route in similarity graphs. arXiv preprint arXiv: 10987,
Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communi- cations of the ACM, 18(9):509-517 1975.
Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Pro- ceedings of the 23rd international conference on Machine learning, pp. 97-104, 2006.
Christopher M Bishop. Pattern recognition and machine learning. Springer, 2006.
Benjamin Paul Chamberlain, James Clough, and Marc Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10333 2017.
Ines Chami, Adva Wolf. Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low- dimensional hyperbolic knowledge graph embeddings. Proceedings of the 58th Annual Meeting of the Association for Compulational Linguistics, pp. 6901-6914, 2020.
George H Chen, Devavrat Shah, al. Explaining the success of nearest neighbor methods in pre- diction. Foundations and Trends@ in Machine Learning. (0(5-6):377-588 2018.
Sanjoy Dasgupta and Yoav Freund. Random projection trees and low dimensional manifolds. In STOC, volume 8, pp. 537-546. Citeseer, 2008
Sanjoy Dasgupta and Kaushik Sinha. Randomized partition trees for nearest neighbor search. Algo- rithmica, 72(1):237-265 2015.
Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment, 12(5):461-474, 2019.
Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature representa- tions in product spaces. In International Conference on Learning Representations, 2019. 2019.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604-613, ACM, 1998.
Masajiro Iwasaki and Daisuke Miyazaki. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.07355 2018.
Omid Keivani and Kaushik Sinha. Improved nearest neighbor search using auxiliary information and priority functions. In International Conference on Machine Learning, pp. 2578-2586, 2018.
Valentin Khrulkov, Leyla Mirvakhabova, Evgeniya Ustinova, Ivan Oseledets, and Victor Lempitsky. Hyperbolic image embeddings. In Proceedings of the IEEF/CVE Conference on Computer Vision and Pattern Recognition, pp. 6418-6428, 2020.
Robert Krauthgamer and James Lee. Algorithms on negatively curved spaces. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) pp. 119-132. IEEE, 2006.
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, 2010.
10

---

Published as a conference paper at ICLR 2022
Thijs Laarhoven. Graph-based time-space trade-offs for approximate near neighbors. In 34th In- ternational Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leins Zentrum fuer Informatik, 2018.
Peng-Cheng Lin and Wan-Lei Zhao. Graph based nearest neighbor search: Promises and failures. arXiv preprint Nttiv:/904.007777 2019.
Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate near- neighbor algorithm based on navigable small world graphs. Information Systems, 45:61-68. 2014.
Yury A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 2018.
Alexander May and Πyy Ozerov. On computing nearest neighbors with applications to decoding of binary linear codes. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 228. Springer, 2015.
Leyla Mirvakhahova, Evgeny Frolov, Valentin Khrulkov, Ivan Oseledets, and Alexander Tuzhilin. Performance of hyperbolic geometry models on top-n recommendation tasks. In Fourteenth ACM Conference on Recommender Systems, pp. 527-532, 2020.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representa- tions. In Advances in neural information processing systems, pp. 6338-6347, 2017.
Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In International Conference on Machine Learning, pp. 3776-3785, 2018.
Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1522,154,, 2014.
P. Petersen. Riemannian Geometry (3rd edition). Springer, 2016.
Liudmila Prokhorenkova and Alcksandr Shekhovtsov. Graph- nearest neighbor search: From practice to theory. In International Conference on Machine Learning, pp. 7803-7813, PMLR, 2020.
John G. Ratcliffe. Foundations of hyperbolic manifolds (3rd edition). Springer, 2019.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, and Hervé Jégou. Spreading vectors for similarity search. arXiv preprint arXiv: 100:::300003999 198, 2018.
Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk. Nearest-neighbor methods in learning and vision: theory and practice (neural information processing). The MIT press, 2006.
Kirill Shevkunov and Liudmila Prokhorenkova. Overlapping spaces for compact graph representa- tions. Advances in Neural Information Processing Systems, 34, 2021.
Alexandru Tifrea, Gary Becigneul, and Octavian-Euus Eugen Ganea. Poincare glove: Hyperbolic word embeddings. In International Conference Learning Representations, 2019.
Xian Wu and Moses Charikar. Nearest neighbor search for hyperbolic embeddings. arXiv preprint wwXiv:2009.00836, 2020.
11

---

Published as a conference paper at ICLR 2022
A AUXILIARY GEOMETRICAL RESULTS
In this section, we prove some auxiliary geometrical results that will be useful throughout the proofs. First, we analyze the properties of Euclidean balls and their intersections. Then, we obtain similar results for the hyperbolic space the ball's radii are sufficiently small.
A.1 EUCLIDEAN BALLS AND THEIR INTERSECTIONS
For a ball B B(1 of unit radius in a d-dimensional Euclidean space, its volume
Volga (B)
(2 + 1)
In this section, we estimate volumes spherical caps and then use the obtained bounds estimate the volumes of balls' intersections.
Let (xx, a)) be a ball radius a centered at x, and (x,, h) S B(x, a) be d-dimensional spherical cap of height h centered at E Sn (x), i.e., (x, = {y E B(x, a) (y x, x) 2 a(a - h)}. Let Ca (h) == Volga (Ca(x, z, h)) be the volume of this spherical cap.
2 (1-))- ative radius" of spherical cap (see (h) in the figure).
Definition 1. Let (h) =
1/2
be the "rel-
Lemma 2.
The volume Ca (h) of spherical cap Ca (x, h)
9a
can be estimated as follows:
X
(h(
(d S
Volga- iBB ad go (h)ddtt S {dd
Proof. For brevity, q qa (h). Let - S cap of height i is known to be:
s 5. The volume of spherical
Ca(h) Volge- ad. sin dt.
First, rewrite the integral:
j sin dt = |æ = =snn
6²
2 =
1
2
1-1
(1 x) dx
2
| =-2(|=
1 get1
f
+
d-1
(1 (21) - dl.
To prove the lemma, remains to show that
0(d-1) < f 1 (1 -2))
di s θ (d=b)
12

---

Published as a conference paper at ICLR 2022
Indeed,
((d
2 dl X
1 - (1 --2))
dl
0 0
dd+ 1 2 = =0 =
$ t t)=
dt B
0
where B)) denotes the beta function. This concludes the proof.
Let us now estimate the volume of the intersection of two Euclidean balls. Let Wx,,, (a, 3) denote the intersection of B a)) and Bxx, (), i.c., Wx Wx,x, (a, {y p(x,,)) S a, p(x,,)) $). Let p(x,, xj) be the distance between the centers and W(a, 3) Volge (Wa,,, (a, 3)) denote the volume of the intersection. The following lemma estimates the value W (a, 8, s) under various conditions on a, 8.
Lemma 3. W.l.o.g., assume that a S B. Define A == (a+8-s)(a s) ()++8-a)
18"
1. If + B < then W (a, 3, 8) 0.
2. Ifs v n² + 82, then
+ (d s
8(),3,8).0 .a, Volga (B) (a 3) A
I (
(5)
3. 1f / + 32 3 < a, then
1 W(a, B,s)
Volga (B). S
(6)
2
Volga (B(a)) W(a,B,
6 (d=
Volga (BB) A 1=1 a
4. If' a 3, then
W(,, 3,8) = Vol (B) a
(8)
Proof. Let ha
(s- 2s
hg
a² (s-
To
(0++))--88
28
28
a 3 8, then the balls do not intersect and thus Waa, 8, 8) = 0, see Figure 4a
2. If S
then, according to Figure 4b
W(,, 3) = Ca(aa) + Co(ho).
By Lemma 2 we have
W(a, (a d+1 (1ra) ) + 2 (lo))
<o
e (d-1)
Volge-1(B)
13

---

Published as a conference paper at ICLR 2022
() 0
(b) Vo=+ W(a, 8) Ca(ha) + Cs(hs)
hpp
(0) vo < ( s ( Volga ((a)) = Ca(ha)-C((h))
s 8: W(o, (olga(((a))
Figure Different cases in the proof of Lemma
14

---

Published as a conference paper at ICLR 2022
Substituting qa: 93, has hg, obtain that
a d+1 "aaat((naa (ha) + 38 13
d+1 (hp)
4+1
( a²
(a-
(a)) 12
2
gd [32 hg)²
ad
a²
8²
1
(ha (2a -ha))
s+1
1
(2, 11,))) 4
3
1 (82 (s a) ((s a)² 322
+
(a² -
33 +3)2 -a2)
4
a 4s2
4s²
=(
1
A A
+
a
3
3. If o +2 S < + then (see Figure 4c
Volga I ((a,3,s) Volga (B(a)),
Also, according Figure 4c
Volga (B(a:) 3,,, Ca(hia) C2(ha) Co (Ta)
By Lemma 2
we have
Volga(B) - a² W(a,, 3,8) Volga-1 ad
S 9 (d
qa
d+1
(ha)
Substituting da and hn we get
a (Taa d ( a² a² (a (a--(a-hai) ha)²
4+1
11
[aa(2a - -Taa)
a²
a
1 1 ((8
) -(s -aa))))
A 2
4s2
4. If + taa S 3, then ((a,3,5) (B(a)) Volga (B) a², see Figure 4d
The following lemma will also be helpful in our proofs. Lemma 4. W(a, B, a) and W a, a) are non-decreasing functions a.
Proof. Let us consider the configuration of balls shown in Figure The d-dimensional ball centered at q' is contained within the ball centered q. Thus, the intersection A A'B'x x of the balls centered at and q' is contained in the intersection ABx of the balls centered at x and q. Clearly, the center q' of the ball which is closer to can be taken the geodesic between and x without loss of generality. The same argument works when the ball centered at x contains the centers q, q' of the other balls.
A.2 HYPERBOLIC VOLUMES
First, briefly recall the basic properties of hyperbolic space and then analyze hyperbolic vol- umes and their Euclidean counterparts. On a small scale, hyperbolic volumes behave in an almost Fuclidean way, while their behavior is fundamentally different larger scale.
15

---

Published as a conference paper at ICLR 2022
B
A'
A
Figure Monotonicity (a, a, and W(3, a)
A.2.1 BACKGROUND ON HYPERBOLIC SPACE
Recall that by Rd. we denote the + 1) d-mmensionall Minkowski space, i.e., the real vector space Rd+1 equipped with the inner product of signature (d, 1):
(, = -o00 - T191 + Zdyd-
The vector model the d-dimensional hyperbolic Lobachevsky space Hd is the connected compo- nent of the standard two-sheeted hyperboloid contained in the future light cone:
H
{x Fd.1 (x,x),, 1111,.
1. x0 > 0}.
(9)
The hyperbolic metric is given by
cosh p(x, = (xx,
The coordinates (Zo, 21, Fa) satisfy the following system of equations:
cosh(t1),
I1 sinh(t cos(t2),
Z sinh((t) sin ... sin(ta-1) (ta)
sinh f1) sin (2)) sin(ta-1) sin(ta).
This hyperbolic coordinate parameterization of Hd is the map
x: [0, +00) x [0, x| d-- 2-22, x [0, 2m] - Hd
defined by
x(11 ta) (xo, xT, ..).
A subset U C Hd is called measurable if x- (U) is measurable with respect to the standard Lebesgue measure on Rd. Let U C Hdd be measurable set. Then, the hyperbolic volume U is defined by
Volga(U) /
sinh d ( sin) sin(tan))) dtydts dtd. dta-idda. x-)
A.2.2 APPROXIMATING SMALL HYPERBOLIC VOLUMES BY THEIR EUCLIDEAN COUNTERPARTS
In this section, show that small hyperbolic volumes can be approximated by Euclidean ones. This is very helpful for our analysis and will allow us to obtain the analogs of Lemma 2 and for small hyperbolic balls.
16

---

Published as a conference paper at ICLR 2022
From the definition of the hyperbolic space ( see that zo / 1 zj + + z.g. Let U C H be a measurable set containing the point z (1, ....,...,,)) and let U be the projection of U along
...
the Ho coorrinnatee from the hyperboloid onto the tangent space T,H {x Rd.1 20 = 1] ~ R
realised by the map : HH - Rd. Let è be the central projection ė: Hd - T, = IR from the origin o = (0, --. 0). Let F U 2U) be the map that satisfies ė F p.
Let us note that the central projection è maps balls centered at z in Hd to balls centered at p(z) = z in R. and also spherical caps of such balls in Hd have spherical caps in IR as their respective images, since every spherical cap is an intersection of some ball with half-space, which is bounded by some hyperplane in Rd. (the central projection of this hyperplane also a hyperplane in P.
According to Ratcliffe (0119).
dx ded
Volga (U)
Ú'
We need to compare Volga to (OU))( in order to conclude that these quantities approximate each other in some appropriate regime.
Lemma 5. Suppose that U HH measurable set such that U B(Zrr). 1fr & Vd and + oo, then we have
Volge (U) Volga (CU)) (1 (
dx....dra Proof. We have that U" = p(U) C (R, sinh(r)), hence x² +.... + 2 S sinh? Then,
dr dx
< (U)
<
des ... dra = Volga (U").
cosh(r)
t' VI+ x + + x
By using Taylor series expansion, we obtain
dri...dr
Volga Volga(U"))= -11 (01) +
,2 +
Volga
cosh(r)
cosh(r)
and thus
1
22 - + 0 (14)) Volg Volge < Volga(U"). 2
Now let us show that
Volg:(U") = Volg (cU (
Indeed, the map F : U - EU satisfies č = F o p and is given by F == (FI....,FF Fa) with Z;
: + v1 + x +
for I....,d,
and thus the Jacobian of F satisfies
0F;
det
1 0 (dr²),
0x Gj=1
(1 + r + +...
22
442
whenever of +... + x3 < (r) and 2 + O. One can conveniently use spherical coordinates
in order perform the respective computation. The lemma now follows from standard Taylor series techniques.
Let Ba(x, r) be closed hyperbolic ball centered a point x E Hdd of radius 0. Then we can compute its volume as (Ratcliffe. 2019):
Volga (Ba(x,r)) = Vol (sd-1) sinh sin) dt.
For >> log we have
Volga (Ba(x, r))
Vo exp(r(d- 1x 1(d-12-))
For < 1/Vd, we have from Lemma that
Volge (B((x,))
Volga (B((x,)) ~ Vol(sd-1) 0(1).
17

---

Published as a conference paper at ICLR 2022
A.2.3 SMALL HYPERBOLIC BALLS AND THEIR INTERSECTIONS
Lelloss us to transfer our results for Euclidean balls and their intersections to the hyperbolic space when the radii of the balls are sufficiently small. Let (h) be the volume of spherical cap of height the hyperbolic space. The following lemma follows from Lemma and Lemma S
Lemma 6. For < 1/vd, the volume of a hyperbolic spherical cap Ca can be estimated as follows:
Ca( ((d Volg--1 a qa (h)d4I & Odd
Let estimate the volume of the intersection of two hyperbolic balls. As for the Eu- clidean case, denote by Wx,x, (a: (3) the intersection of (x;, a) and B(x,, f), ie., Wx,x, (a, B) = fy p(x,, y) a, p(x
p(x,, xj) be the distance between the centers and Wa,, 8) Volga (W xxxx ()) denote the volume of the intersection. The following lemma estimates the value W (aa, 8, 8) for various relationships between a, S.
(8. Let
Lemma 7. Assume that S 8 < 1/vd. Define A == (a+9+s)(a+8 -- aa 8)(++8-a)
4
1. Ifa + 3 then W (a. 8,s) s) = 0.
2. Ifs - 8 < va + s², then
(a+ + (d=)) Volga-1 (a 33 S
W(a,3,5).o0 .x3
(d) {
(10)
3. o + 2 3 < + a, then
W(a, 3)
2 <
(B) ad o(1)) $1,
(11)
(B(a)) Wa,,8,8)
< (d-t)
(12)
4 a- Volga (BB)
4. 1fs + S B, then
W(a, 8, Volga Volga (B) ad.
(13)
Proof. To prove this lemma, we follow the proof of Lemma and use Lemmaßjinstead of Lemma
The following lemma is analog of Lemma 4 Indeed, the argument uses only monotonicity of volumes under set-theoretic inclusions, which holds for both Euclidean and hyperbolic spaces.
Lemma 8. In the hyperbolic space, ((a, 3, a)) and ((3, a, a)) are non-decreasing functionn of
B PROOF OVERVIEW FOR THEOREM
Recall that assume uniform distribution of the dataset over d-dimensional ball B of radius R = R(n) such that
1/(-111)
(14)
d1/2
Then, the graph G(M) is constructed using a threshold ams M8 with
dva R))
1/d
8
(15)
18

---

Published as a conference paper at ICLR 2022
Let us show that under the conditions of the theorem, we have & < 1/ Vd. First, note that
R sinh (1) di
R (dd11)
R(d-11 2d-1 dl S 2d 2d-1(d -1 1)
va RR)
Thus, we have
R(
1/d
2d (d 1)m = ()dd-1))) vid) < 1/vd.
8
The last inequality is due to (4). Thus, we can apply Lemmal throughout the proof.
To prove that the algorithm succeeds w.h.p., we need to guarantee that it does not stop in a local optimum until we find the exact (or approximate) nearest neighbor of the query q. Given a point such that p(q.x) as the probability of making step towards q is determined by W (a,, M a,)): the distance between the points is a's, the neighbors x are within the ball of radius ams centered at and we accept those neighbors that are closer to q than x, i.e. within ball of radius as centered at q. Lemma amalyzes the asymptotic behavior of W (azg, aM,
Lemma 4 states that W(,, B,a) is a non-increasing function of a. Informally, it means that it is casier to make steps towards the query when p(x, q) is larger. In contrast, when x becomes closer to q. the probability of getting stuck in local optimum increases. Therefore, to obtain lower bounds W (a,, 0M,, ag), we can consider only the case when ag is small. Below we assume that ag = 86, where s some constant.
Lemma gives the following lower bounds on W (ats, OM, Oss)
$ +
1. if M < <sv2, then W(a,ayaa.) Va(R)
(M²
M
1e
2. if M 2 8/2, then a(a.a
dto(d)
Va(Rt)
Let us consider one step of the algorithm. We can move forward w.h.p. W (as, O., 0+) > 1/n. Formally speaking, it follows from Corollary of Lemma [1 that M and satisfy
s and either M 2 2v2 or M - / > 1,
(16)
then there exists a constant S > 1 such that we can make a step towards q with probability
1 - (1- Sutold)
n-1
= 11-00 0 (c-stt)
n
We make steps of the greedy algorithm towards the query q as long as the probability of making the next step is large. Below we also prove that the overall probability of failure (taking into account all steps of the algorithm) is small. Now, let us show that under the conditions of the theorem, we reach some neighborhood of q and then either find the exact nearest neighbor or the approximate near neighbor by making one more step.
First, consider the exact NNS. In this case, we assume that the nearest neighbor is located within ball of radius ro, 0 < r & 1, centered at q. Our goal is to find the exact nearest neighbor. According to the statement of the theorem, we have M > 22, which implies
M
M
(17)
2
While we move towards the query, 8 becomes smaller. Let us figure out up to which & we can make
steps. According to (16), we need either < < M/v2 or > M² Af2/2/M² 1. According forward to any
to (17). it reduces
> 1. In other words, we can Lemma 14, it is sufficient to have M² > s2 + 22 to reach the exact nearest neighbor of q in one step.
1. Then, according to
Thus, we can take any s.t. < s < VM² - r we can reach this distance with greedy search and then jump directly to the nearest neighbor with high probability.
19

---

Published as a conference paper at ICLR 2022
Now, consider the approximate near neighbor search c, r-NNN. In this case, need to find an element that is within a distance re from q. According to the statement of the theorem, we have
M > 4 /3cr 1).
Note that F(r) = 2r (1 (1- (1-VI-1/r2 decreases with for r > 1/c and equals at = 1/c, while (rr) = (r² +1+
increases with and equals 2 at 1. Both Frr) and G(r) attain 4c² /(3e² 1) at rg /422/(c² + 1)(3c² 1). Therefore, we either have
12 r r> ro and M > F(r)
(18)
or
ro 2 and M G(r).
(19)
To solve c, r-ANN, either we can reach s such that rc > 8 or we can reach such that at the next step can find the exact nearest neighbor. Let us consider the first possibility. Note that
and M 2s²
(20)
22
is equivalent to (16). In turn, since 21 v 1-11-88 1/22) is decreasing function of s on s > 1, we get that (T8) implies the existence of s such that re > s > and
1
M 2s²
F(r). 82
Hence, since (16) holds, we can move forward to such Let consider the second possibility. Observe that (19) is equivalent to
M
M
4(M2-)
Therefore, there exists such that the condition s² < M²² 22 of Lemma 14 and (16) hold. Since (16) holds, we can move forward to such s and reach the exact nearest neighbor in one step as the condition of Lemma is satisfied.
Above, we show that under the conditions of the theorem, each step of the greedy search is suc- cessful with probability 1-0 O (e-sttoat - To formally prove that the algorithm succeeds with high probability, we need to limit the number of steps and estimate the overall probability of failure. For this, we show that each step of the algorithm, we become closer to the query by some fixed positive value. In Lemma 12 prove that each step reduces the distance from q by least zō, where e some positive constant. Clearly, we start at a distance O(R) from q. Hence, we are able to bound the number steps by O(R/56) which (Ron/ddva (va()))-14)))
To estimate the overall success prohability, we have to consider the dependence of consecutive steps of the algorithm. Lemma 13 implies that consecutive steps are "almost independent" and the overall The assumption d >> log log and the - ((()) o(1).
success probability is 1 - O Ron (1a(
fact that (R( = ((RR)) yield O (va(())
sellvl)) = =0 (e log gdd
Also, while most of the analysis does not consider the cases when a neighborhoods of the dataset elements intersect the boundary 0B, we need to show that possible intersections do not affect the result. This is addressed in Lemma 15
Finally, let us discuss the time and space complexity of the algorithm. Let w be a fixed arbitrary node of G(M) and let (vv denote the (random) number of its neighbors in G(M). Let f (n) = (n - 1) Volga (B(as)) /Volga (B) denote the upper bound for the expected number of neighbors of (this is upper bound due possible boundary effects). In Lemma 16 that (u)) $ 3f /2 with probability at least 1 - O(1
we show
To obtain the time complexity of graph-based NNS, steps. In Lemma [7] we show that steps of the NNS are made, then the time complexity is O (Ifd) with probability O(1/2f).
up the complexity of all algorithm's 's
20

---

Published as a conference paper at ICLR 2022
show that the number of edges in the graph is E(G) I 3fn/4 with prob- ability - fl). we store the graph as the adjacency lists, then the space complexity is (E logn) O (fn log)
In Lemma 18
Due to the choice of 5, we have f O (M4). Hence, w.h.p., the space complexity is O (n logn MD) and the time complexity is O R n2/a (va(R)) M4).
C RESULTS USED THROUGHOUT THE PROOF
In this section, we formulate supplemental statements used in the proof. We need these results for the hyperbolic space, but they are also true for the Euclidean one. Thus, we do not specify particular space :.
C.I ANALYSIS OF CONVERGENCE
Recall that aM MÒ and sō, where M and are some constants and ó is defined in 15 Recall that 8 < 1/Vd.
Lemma 9, Define == (3r(103-331)
403
Ifo S ag a2,2,,10 then
+ (d-1)
Volga-1 (B) (arm + a.)) A d+1 S 0 (d+))
W (aa, ams az) ara,
(21)
Ifa > as 2, then
W(as; aM, as)
(1).
(22)
Volga (B)
Proof. We apply Lemma
7
First, consider the case a. S Os. Then, the case 2 applies to we obtain
W (aa, as, a.). From 10
+ (d
W OM, as)) aMa,
A (d
(23)
Volga (B) (a + +a,) A
Now, consider the case 0ss < OMM-
1. af aM S 2, then from 10) we obtain
W(a,, aM, o.)) a.M.
(as + a.)) A 4 < (d <
+ (d Volg ( (B)
2. If av,22 < am < 20,, then yields
W(a,, aM, a.) = θ (Volga a.)
3. If 2a, S aa,, then 13 gives
W(a,aas;a)) Volga ag o(1))
This concludes the proof of the lemma.
Lemma 10. Denote by A 82 OM
If as ar < aM <
4s
V0z + 07, then
θ 1d- <
W(a,, aM,a,)
4+ A < <a
(24)
Volgs 1 (B)
Ifa > V + az, then
Volga (B(ar)) W(a,, O.M as)
< (d
(25)
Volge-1 (B) A 4 88-1
21

---

Published as a conference paper at ICLR 2022
Proof. The result follows directly from Lemma] 7
Lemma 11. M s.2, then
Va(R)
aM,,))
2
gatold),
If M & sv2, then
Va(R))
M
(M, 2
M2
n
4.²
Proof.
If M > 2 then we can apply (2 to obtain
W(a,, ars, 2 2 (d- (so)* Volga(B)) = 200-1 (d-1.e" dva(Bt
Volga (B)
= sa Va(R) Volga(B).
voleo(())
Va(Rt) sd+o(d).
Vol(Bd-1))
If M S s then we can apply (1 to obtain
W W(,, aw a.)) 2 Volga-1 8 A -
Volga-1(B)- 8-1 d+1 MM
(1
2
O(d
4a
(1- M
Volga (BB) 8d. Md+1
(d
4s2
Volgs 1 (B)
Va(lt)
Md+1 [
2
+(1)
Vol(Sd-1) n
4
= (d-1). Va(Rt)
M2
M
Va(R)
M
+
n
4x2
n
482
Corollary 4. If 1 and either M > sv2 or M
M /45/
then there exists constant
S> 1 such that (az, aM ax) 2 Va(R) gd+o(d)
Lemma 12. Assume that 1. If
> 8V2.n or M M
4s2 > 1,
(26)
then there exist constants S > 1 and & > such that
W (arM, ag + +0d)= 2 V2(R) td
n
Proof. If M > sv2, then we can choose sufficiently small > 0 such that 2 > s2 + (s +++
Then, the result follows from Lemma 11 and the fact that s > Otherwise M < 32 + (s 1-+57 5)², and instead of the condition M
M from we have
12z
4s (s +)² -M² 52 (s + e)
> 1.
4(s +)2
As it holds for = 0, we can choose a small enough > that is still satisfied.
Lemma 13. The dependence of consecutive steps negligible.
22

---

Published as a conference paper at ICLR 2022
Proof. First, consider the case M sv2. It suffices to show that W1 W (aM, 0gs 0g 2=o) is negligible in comparison with W1 + W2 = W (aM, as. ag + Eő). From 24 we can write their ratio
W1
4(s 8)2 2 (M + 5 M E)²) - (M* + 8 + (s+
d01))
W1 W2
(M + (s 22)² + (ar + + (s + 20)²)
o[).
4(s 2s)²
Since at each step we reduce the radius of the ball centered at which contains the current position by least ed, any ball encountered in the current iteration intersects only constant number of other balls, so their overall effect is negligible.
In the case when M > 2 and s > 1 with probability 1 o(1) we find the nearest neighbor in one step.
Lemma 14. If some constants M, r have M > 3² + r2, then
Volga (B(a,)) W (ax,, OMM ..a) S Volga (B(a,)) fd
with some B 1.
Proof. It follows from 25 that
Volga (B(o,)) W (ar, (M, s s (d Volga-. - -5-1
It remains to bound from above the following ratio:
θ d Volga-1(B)
4 5-1 ( Volga-1 1
A
O(1)
Volge (B(ar))
Volga (B) pd jd+1
82,2
_
(M s) +r (s M (s + MMM
=(1)
2r
=(1 (1 (M² 2 - -2 -2
d+1
I gd+1
4s2p2
for some 8 < 1.
C.2 ANALYSIS OF THE BOUNDARY EFFECT
Lemma 15. The boundary effect is negligible and does not affect our results.
Proof. Consider the worst-case scenario when the current element located on the boundary of the ball B (see Figure Indeed, in this case, the largest part of the neighborhood is located outside B, which may reduce the number of neighbors of given element.
this is equivalent to the hyperbolic First, consider the Euclidean space. According to Lemma 5
case with R & 1/vd. Let us show that W (a. R. R) converges to VolgaB(o) if a O with
8 [dVolga (B(R)) 1/d Vol(s*-TT
Note that W W(a, R R) C.(h) Cr(a h) < 1 Volga B(a). It is easy
to see that 71 = a- 2R
Then,
d ++1 1
a²
Ca(h) (B)a
2
4H2
1
(+1 1
=(1+o(1)) Volga-1 (B)a
=(1+o(1)) Volg.
2
23

---

Published as a conference paper at ICLR 2022
R
a
Ca(1i)
CR(a It)
W(a, R, R)
Figure 6: Illustration for the proof Lemma 15
a & 1/vd. Indeed,
B
dd+1
B
d 1 1
a
4R2
{(- 1)/2 (1 (1- 1
2
2
2
2
4R
2 2 d+1
gld 1)/2 dt
2R
o
1 1
J0
(d+ + 1) D/2
o²
2 2
TR
1R
since B
d+1 1) ( 2
1/v
and
(1)) (dVoll (B(R)) Vol(Sad1)n
1/d
+(1) n//d
0 for d < logn.
In the hyperbolic case, the "small" ball of radius small enough can be considered Euclidean, and thus we can apply Lemma 5 to estimate the volume of C (h). The "large" hyperbolic ball of radius R, in this case, can be thought of as a Euclidean ball of radius 2 in the upper half-space model, and then we can carry out the same analysis on the Euclidean scale of the "small" radius a ball. Note that this case
1/vd) so that its geometry
(L))
(dv((R)
1/d
((L) Rid 1)/d
- 0.
22R
22R
22R
C.3 TIME AND SPACE COMPLEXITY
In this section, we estimate time and space complexity. Recall that N(v) denotes the number of neighbors of an element G(M) and f (n 1) (B(ax)) /Volge (B). The proofs below mostly follow the corresponding proofs from Prokhorenkova & Shekhovtsov 2020). We keep the proofs here for completeness.
Lemma 16. The probability of the event " (v) sutisfies N S 3 " is at least 1 4
Proof. Note that the random variable N(v) upper bounded by the random variable N'(v) hav- ing the binomial distribution Bin (n 1, a (B(ax)) with the expected value Thus, via the Chebyshev's 's inequality, we obtain
Volge (B)
3 - <P N'
3 / <P (1N(()) f11 - 1) < 2)
4 Var (N' 4
P N(v)
24

---

Published as a conference paper at ICLR 2022
Lemma 17.
The time complexity of l steps of the graph-based NNS is (lfd) with probability
1 0 (1).
Proof. We can upper bound the number distance computations by the random variable distributed according to Bin ((n 1), Vol.a( and proceed as in the proof Lemma 16 Finally, note that distance computation takes (d))
Volga (8)
Lemma 18. The probability of the event "E(G) satisfies E(G) ffnn is O (
Proof. We mostly follow the proof of Prokhorenkova & Shekhovtsov 2020). but some modifica- tions are needed handle the boundary. We use Chebyshev 's inequality, so we have to estimate the variance Var (G)):
(Br = (E(G)) (EE(G)))
Σ
P(e1.e2 E P(e1 E(G)) P(ez E E(G)).
(1
Obviously, if e, and eq do not share common endpoints, then P(e,, E(G)) P(er e E(G)) P E E(G)). Also, one can see that if ej and e2 share one element, then we also have P(ei, e2 E E(G)) P(e
E(G)) P(e2 E(G)). Indeed, assume that both e and 62 contain common element v. Then the equality holds conditioned on the position of e since both sides of the equation are defined in terms of v-th neighborhood size.
Thus, only the terms with
remain in the expression:
Var E(G) =
Σ
P(e E E(G)) (P(e) E E(G))) < BE(G).
2
Finally, we get
EE(G) 2
4VrrE(G))
[E(G) - EE(G)|
(EE(G))²
EEGG)
It remains note that EE((G) S nf/2 and due to Lemma 15 we also have BE((G) Onn)). From this the lemma follows.
D N- GRAPHS
Note that in Theorem we consider undirected graphs since the condition on p(:, is symmetric. In this section, extend the theorem to nearest neighbor graphs. In this case, assume that each node connected to fixed number its nearest neighbors by directed edges. During graph traversal, outgoing edges are used to explore the neighborhood.
Theorem 3. Assume that d(n) is such that log log n d(n) < log n and R R(n) such that et < n d1/2
For the exact NNS, let M be constant M > V2 and let k [Md) Then, with probability 1 - o(1), NNS based on the k-NN graph finds the exact nearest neighbor. For c, r-ANN with some
constant e > 1, let M be a constant s.t. M > v 32-1 and k = [M Then, with probability
Aet
(1), NNS based on the k--N graph solves e, r-ANN for any r.
In both cases, the time complexity is O l/d. R (va(R)) -1d))
the space complexity is O (I=- log
25

---

Published as a conference paper at ICLR 2022
Proof. First, note that the space complexity is straightforward: each node has exactly it outgoing edges. Similarly, the complexity of one step is O(k (d).
Thus, it remains to show that kNN-based NNS succeeds with probability o(1) and that the number of steps can be upper bounded similarly to Theorem To prove this, it is sufficient to show that the distance the k-th neighbor is sufficiently large, so that the convergence can be guaranteed by the proof of Theorem
For every node v, define random variable (x( to be the distance from to its k-th nearest element. It is sufficient to show that Pk(()) 2 Mő, where 8 -( [dua(R) 1/d
and M satisfies the required conditions on M in Theorem For some 5 > O, let M M (1 - E). Obviously, by choosing small enough E, we can guarantee that the required conditions satisfied.
Note that N, - the number of elements at distance at most r from v - can be upper bounded by random variable having the binomial distribution Bin (n 1, Vol.a (the upper bound Volge (B)
caused by possible boundary effects). If M then aa (B(r)) upper bounded by Bin (n. MMM1/))
Md /n. Thus, (v) is Vol. (B)
Recall that k [M It is sufficient to show that with high probability we have (U) k for all v. Using the union bound over all possible v and the Chernoff's ' bound, we obtain the following:
7))) N M (v) 2 k) S nn.e 2 (dd//)) S
log (1-0(1-
P P(
6(M4)
+ 0
as since d >> log log
E GRAPH-BASED NNS IN SPARSE REGIME
In this section, prove Theorem 2 For this, we show that the elements tightly concentrated near the boundary of the ball, and thus the convergence guarantees resemble those on the sphere (Prokhorenkova & Shekhovtsov 2020).
Let us denote by (xx,, xj) the angle Xx,Ox, For the sphere, a graph G(M) is constructed by connecting such pairs of elements that (Prokhorenkova & Shekhovtsov 2020
2M log d
cos (Xx; N
(27)
For the hyperbolic space, we connect the elements x; and X, iff
2M log
cosh p(xi, X,) I cosh R sinh R
(28)
Note that this corresponds to the elements x; and x, located on the boundary of B with (o(x, xz) bounded by (27)
Recall that for c > 1 we set
Og = cosh? - cosh (arccoshhcosstt R)/c)
(29)
sinh² R
Let explain this choice. Below we prove that NNS in the hyperbolic space behaves similarly to NNS on sphere. In other words, we can project all the elements to the boundary of B, and this will not significantly affect the process. However, we have to properly adjust a, taking into account the multiplicative approximation factor c. In Proohorenkova & Shekhovtsov (2020), the spherical distance that e times smaller than the distance between the elements with yo (X,, Xj) T/2. The hyperbolic distance D between the elements with sp Xi, x;) = n located on the boundary of B satisfies the following equality:
is
the cosine of the angle x 2c There, 2c
cosh D cosh R, i.e., D arccosh(cosh? R).
26

---

Published as a conference paper at ICLR 2022
Then, need to compute cos (o(x, Xy) if p(x;, D/c. of cosines:
This follows from the hyperbolic law
cos (x,, xj) cosh?(R) cooh(DD/c
si
which is equal to ae Equation 29
Thus, it remains to show that the convergence guarantees transfer from spherical to hyperbolic space. Let us first prove that the elements are tightly concentrated near the boundary of the ball B.
Lemma 19. With probability 1 - (1) all elements are located within shell of width log near the boundary of the ball B.
Proof. According to 3 we have
(B(R 8))
(
Volga (BR))
Let 2-1 (log 4p), where ip (p()) is any function s.t. - 20 as oo. Then,
Volge (B(R θ (e log log) o(L/n).
Volga
(Bl))(B(R)) (B(R)
From this the lemma follows.
Lemma 20. If two elements X, satisfy 27 with constant M + & for some e then with probability 1 - o(1) they satisfy (28) with constant M.
Proof. Let the distances from x, and x, to the center of the ball B be r; and rj, respectively. From
with high probability. Using the hyperbolic of Lemma 19 r; and r'j are equal to - logn
cosines, get
cosh p(x,, Xj) cosh r, coshr, sinh r, sinhr, cos ((xx, x,)
2(M + log
coshr; cosh r- sinh r; sinh ry
d
2(M log
cosh 2 ((lggn(())//)) sinh ( O(ogn/d))
It is sufficient to show that
2 + E) log
coshi - ((logn/d)) - sinh
d
2M log
S cosh R - sinh? R
d
Note that cosh (R-Ol(Rogggg/aaa - (logn// The same holds for sirhiihhhhe (Rooh(RoOollo//a Therefore, need
22ft
(1 1- 2(M E) log
2R
(1+0(e-211)) (1 (1-v 2M log
(1 O(log
d
Now we divide the right hand side by the left hand side and obtain
2M log d
(1 + Oloog + (c-2R1)
2(M +e) logn
2(M + 8) log
2M log n
(1+0 0 (vlogn/d) (1+0(vlogn/a)
(1 O(logn/d) + O (R-2R)
d
d
(1 + 22( (lgn/dd) (1 O(logn/d) + O ( (e-22)
From this the lemma follows, since Vlg n/d > log
logn/d n/d and Vlgn/d > 22
27

---

Published as a conference paper at ICLR 2022
Let choose such small 0 that the required condition M is also satisfied for M + It follows from Lemma 20 that our graph G(M) contains the spherical nearest neighbor graph defined via (27) with constant M + Thus, may follow the proof of Theorem 2 in (Prokhorenkova & Shekhovtsov 2020) (Appendix B.5) with the corresponding nearest neighbor graph.
Note that all spherical caps and distances mentioned in the proof of (Prokhorenkova & Shekhovtsov
2020 are defined by conditions cos +p 28 log for some constant S. According Lemma 20 such constants are negligibly affected by deviations from the boundary. and thus we can directly follow the proof of Prokhoreekooox & Shekhovtsov (2020) to obtain the convergence guarantees and complexity. Indeed, all requirements for the constants in the proof are strict, and thus sufficiently small e can be chosen such that they are still satisfied.
d
F EXPERIMENTS
Best-first search In the main text, for the synthetic experiments, use the greedy search. How- ever, in graph-based NNS algorithms, the greedy search often replaced by the best-first search main-
(a.k.a. beam search). In this case, instead of keeping track of only the best candidate, lain a dynamic list of several candidates. In particular, this technique is used in HNSW (Malkov & Yashunin 2018), and the size of the candidate list is controlled by the parameter e/ Search.
Hyperparameters Recall that to plot Figure [ we vary the graph degree to control the complex- ity and accuracy of NNS. In Figures and 3 we use the best-first search, so we vary the parameter Search and fix the graph degree. In this case, we tune M and ef Consstruction HNSW hyperpa- rameters, which are responsible for the graph degree and quality of the graph construction, respec- tively. For both GloVe and Poincaré GloVe databases, we get M-10 and e Comstruction==000 For other datasets, we get M-8.
NSG In addition to HNSW, we also experiment with the NSG graph (Fu et al. 2019). For this algorithm, the degree is controlled by the parameter R, and the optimal degree is 2M.
Spherical Shell implementation As baseline, implement Spherical Shell proposed by Wu & Charikar (2020). As in the original paper, we split the elements into 25 bands such that w 1.05. For each band, we construct LSH with 50 tables.
I-|aa| S w". To achieve this, we take Each table has [log(m)] - 1 bins, where m is the number of elements in the band. The number of probes is tuned for each band to reach 0.95 recall (this value has been chosen achieve better results). When searching for the nearest neighbor for a query q. we compute the nearest neighbors within / bands closest to q and take the best one according the hyperbolic distance. The number of bands is varied from to 10, thus giving the curve on Figure 2
Additional datasets In addition the standard Poincaré GloVe dataset, we also consider the Poincaré GloVe Ve embeddings trained for d = 10 using the source code provided by the authors (Tif- rea et al. 2019 Additionally, we also take the recommendation dataset from [Shevkunov & Prokhorenkova 2021). where DSSM model was trained on a Wikipedia search dataset of (scarch query, relevant page) pairs. We use their Euclidean and hyperbolic representations for 10.
Additional experiments on real datasets Figure 7 compares graph-based methods with Spherical Shell on the standard Poincaré Glo Compared to the main text, here we add the NSG algorithm. While HNSW outperforms NSG, both better than Spherical Shell.
28

---

Published as a conference paper at ICLR 2022
0.
Rocallig
0.6
HNSW
NSG
Spherical Shell
DCS
Figure 7: Graph-bascr methods vs Spherical Shell on Poincaré Glo Ve embeddings
1.40
0.6
Recaigg1
0.08
0.0
NSC
NSC
1.0
1.3
202
732
7000
763
126
1.33
140
180 20
DC5
Figure 8: Comparison of algorithms on Poincaré GloVe with df = 10
Figure 9: Comparison of algorithms the rec- ommendation dataset with d = 10
10 and the rec- ommendation dataset with = 10 from Shevkunov & Prokhorenkoval (202I). We see that HNSW Poincaré GloVe, while HNSW outperforms NSG the ommendation dataset. In contrast, Spherical Shell needs a significantly larger number distance computations, so it is shown in the figures. On the recommendation dataset, low performance of Spherical Shell can be explained by the fact that this data significantly differs from the Poincaré GloVe: the learned vector norms much larger. Because of this, we either have annuli of large width (significant approximation error) or many annuli (increased total complexity). Also, it is im- portant note that Spherical Shell is well suited for sparse datasets, while we have d 10 this experiment.
Figures
3 and compare the algorithms the Poincaré GloVe dataset with
and NSG have similar performance
Then, we compare the efficiency of NNS in Euclidean and hyperbolic spaces. For this, we consider the embeddings of the two datasets discussed above into Euclidean and hyperbolic spaces and per- form NNS based on HNSW for the same set queries. Figure 10 shows that hyperbolic NNS is more efficient.
Additional synthetic experiments Figure 11 is similar to Figure I but now we use the best-first search instead of the greedy search. We that the conclusions the same.
29

---

Published as a conference paper at ICLR 2022
Recalig
646
Poincaré Glave
Buclidean
Glove
Hyperbolic
DCS
DCS
Figure 10: Efficiency of HNSW in hyperbolic space vs Euclidean space on GloVe with d 10 (left) and recommendations (right)
Seure d-
Boutsicl I-R aod
Boan 2-11 owo
618
0.39
639
Jphers
Schus
6.00
Howebali
0.15
Hoseball 6x33
Hosebale 1-12
Oram long Edpas
Long
Searn Long Ságas
0.091
1.990
0000
1.005
Schter
Stras
Laciden
00/0
Hope Ba0
1.000
245
250
0.00
372
250
Figure 11: Best-first search over NN graphs without (top row) and with (bottom row) long edges
30


Reviews:
[{"review_id": "gSvs7oE45b7", "reviewer": "Reviewer_VNYQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n=================\n\nI 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_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. ", "summary_of_the_review": "I think this is a solid and interesting paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZJPYJXYYmIR", "reviewer": "Reviewer_zLTN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe main result of the paper is that under certain assumptions, NNS in hyperbolic space can be faster than in Euclidean space.\n\nMy main concerns are around the validity of the assumptions and the empirical evaluation.\n\nThe 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.\n\nCan 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.\n\nHaving 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?\n\nIn 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?\n\n\nThe following citation is also missing \"Neural Embeddings of Graphs in Hyperbolic Space\", Chamberlain, Clough and Deisenroth, 2017.", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Pdpwqp8R8Kc", "reviewer": "Reviewer_6ftD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nTheoretically 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. \n\nHowever, there are some weakness:\n1. 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. \n2. 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.\n\nAlso I have some questions regarding the paper\nIn 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?\n", "summary_of_the_paper": "This paper looks into graph-based algorithms for nearest neighbor search (NNS) problem in the hyperbolic space.\n\nTheoretically, 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. \n\nPractically, the authors apply the methodology to Poincar{/'e} Glove word embeddings, where it outperforms some existing baselines. ", "summary_of_the_review": "This paper is an interesting work to analyze best-first-search graph-based NNS algorithms in the hyperbolic space.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "K2RgW9KSiS", "reviewer": "Reviewer_1ri4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n\n1. 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).\n\n### Weaknesses\n\n1. 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.\n\n2. 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)).\n\n3. 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.\n\n4. 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.\n\n5. 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.\n\n6. 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.\n\n7. 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. \n\n8. 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?\n\n### Additional Comments\n\nThe paper writing was, for the most part, adequate. A non-exhaustive list of minor corrections/suggestions is given below:\n\n- \"opposite approach\" in the introduction is not really well-defined. \"alternative approach\" would be more appropriate.\n- 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.\n- 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_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.", "summary_of_the_review": "### Verdict\n\nThis 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.\n\n### Updated Rating\n\nIn 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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3Ajz3w7Bd5g", "reviewer": "Reviewer_XgPX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n1.\tThe 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. \n2.\tI 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.\n\nWeak points:\n1.\tIm 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?\n2.\tIf the authors need to address the intrinsic dimension, I recommend a separate parameter d’\n3.\tMore 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).\n4.\tSome more motivation on the advantage of hyperbolic spaces for real life settings can enhance the view on the impact of the method.\n5.\tUse of M is rather confusing, in (2) it is a Riemannian manifold but later it is a scalar.\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)