Year: 2021

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 is found to be very useful for 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 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 graphbased 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.

heading: 1 INTRODUCTION
text: Given a dataset D of n elements and an arbitrary query q, the goal of the nearest neighbor search (NNS) is to quickly retrieve one or several elements fromD closest to q. NNS is extensively used in a 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 et al., 2006). In large-scale applications, searching for the nearest neighbors can be a bottleneck, so this operation’s efficiency is of the essence.
Many efficient NNS algorithms exist for Euclidean and, generally, `p spaces. Among them are methods based on recursive partitions of the space, e.g., k-d trees and random projection trees (Bentley, 1975; Dasgupta & Freund, 2008; Dasgupta & Sinha, 2015; Keivani & Sinha, 2018), well studied Locality Sensitive Hashing (LSH) (Indyk & Motwani, 1998), and methods based on similarity graphs (Fu et al., 2019; Iwasaki & Miyazaki, 2018; Malkov et al., 2014; Malkov & Yashunin, 2018).
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 recommendations (Chamberlain et al., 2017; Chami et al., 2020; Khrulkov et al., 2020; Mirvakhabova et al., 2020; Nickel & Kiela, 2017; 2018; Tifrea et al., 2018). Intuitively, the hyperbolic space has advantages over standard representations when data has a 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 the increased NNS complexity compared to the original Euclidean algorithm. In the current paper, we choose an alternative approach and apply a 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 step, a similarity graph is constructed on the elements of the dataset. Then, given a query q, we start from some element ofD 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; Iwasaki & 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 (Aumüller et al., 2019). In contrast to 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 graph-based approach. However, it 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 the 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 (2020) who studied graph-based algorithms assuming the uniform distribution over a d-dimensional sphere. In the dense setting (assuming that d log n and R does not grow too fast), we derive the time and space complexity using the fact that locally hyperbolic graph-based NNS behaves similarly to 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 illustrate our theoretical findings via synthetic experiments on uniform data and also analyze graph-based hyperbolic NNS in practical applications where our theoretical results cannot be directly applied. For real datasets, we consider Poincaré GloVe word embeddings (Tifrea et al., 2018) and hyperbolic representations of queries and items for a recommendation task (Shevkunov & Prokhorenkova, 2021). We compare graph-based NNS with existing baselines (Wu & Charikar, 2020) and show that graph-based approaches have significantly better performance. We also compare the performance of graph-based NNS for Euclidean and hyperbolic representations of the same sets of elements and observe that hyperbolic NNS can be more efficient.

heading: 2 PRELIMINARIES
text: Graph-based nearest neighbor search Graph-based algorithms for NNS are known to outperform other approaches in many large-scale applications (Aumü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 neighbors and q, and add the neighbors to the queue. Many algorithms are based on this idea (Baranchuk et al., 2019; Fu et al., 2019; Iwasaki & 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 trade-offs for approximate nearest neighbor (ANN) search in sparse datasets (d log n) uniformly distributed on a d-dimensional Euclidean sphere. This work considered nearest neighbor graphs, where each point is connected to its neighborhood lying within a ball of a 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 n) 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 a sphere, we assume a 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 In this section, we discuss the basics of hyperbolic geometry. Let Rd,1 be the (d + 1)-dimensional Minkowski space, i.e., the real vector space Rd+1 equipped with the inner product of signature (d, 1):
〈x, y〉h = −x0y0 + x1y1 + . . .+ xdyd. (1)
The vector model of the d-dimensional hyperbolic Lobachevsky space Hd is the connected component of the standard two-sheeted hyperboloid Hd = {x ∈ Rd,1 | 〈x, x〉h = −1} contained in the future light cone: Hd = {x ∈ Rd,1 | 〈x, x〉h = −1, x0 > 0}. The hyperbolic metric is given by cosh ρ(x, y) = −〈x, y〉h. From the definition of the hyperbolic space, we see that x0 = √ 1 + x21 + . . .+ x 2 d. The volume element in Hd is (see Ratcliffe (2019))
dx1 . . . dxd√ 1 + x21 + . . .+ x 2 d .
Hyperbolic space is known to be useful for data representation in various domains. It is especially convenient for embedding hierarchical data (Nickel & Kiela, 2017). 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 B(x, r) be a closed hyperbolic ball centered at a point x ∈ Hd of radius r > 0. Then,
VolHd(B(x, r)) = Vol(Sd−1) ∫ r 0 sinhd−1(t) dt , (2)
where Sd−1 is the unit (d−1)-sphere and Vol(M) denotes the full volume of a Riemannian manifold M. That is, Vol(Sd−1) = 2πd/2/Γ(d/2). For r log d, we have
VolHd(B(x, r)) ∼ Vol(Sd−1) er(d−1) Θ(d−12−d). (3) The main term here is er(d−1), so the ball volume VolHd(B(x, r)) grows exponentially when r is large. However, for small hyperbolic balls (as r → 0), we have sinh(r) ∼ r. Hence, the volume of a ball (2) behaves similarly to the Euclidean case. In Section 4.1, we provide a formal general result that shows that not only the above argument is correct, but also the volume of a measurable subset of a hyperbolic ball behaves asymptotically exactly like its Euclidean analog.
Nearest neighbor search in hyperbolic space While there are many NNS algorithms for `p spaces, little is known about efficient hyperbolic analogs. Krauthgamer & Lee (2006) proved the existence of an approximate near neighbor algorithm for general geodesic spaces of hyperbolicity δ. 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 2O(d) log2 n, while the constant in the exponent is not given. In contrast, we specify this term as we focus on d → ∞. Another difference is that the algorithm of Krauthgamer & Lee (2006) requires O(n2) storage that is usually infeasible in practice. In contrast, graph-based algorithms require nMd for some constant M if d log n. Finally, while the theoretical analysis is given in a very general setup, there is no implementation of the proposed algorithm, and extracting an efficient implementation from the proof is challenging.
In a recent paper, Wu & Charikar (2020) reduce the problem of hyperbolic NNS to Euclidean NNS. Namely, assume that we have an efficient Euclidean algorithm and a dataset is represented in the Poincaré ball model. Then, we can apply the algorithm to the Euclidean representation. To guarantee convergence, the algorithm should be applied several times. There are several alternatives proposed. In one of them, we apply the algorithm to the whole dataset, but after each run, appropriately changes the query point to 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. In another algorithm, one splits the ball into thin annuli and performs the approximate Euclidean NNS for each of them separately. From a theoretical perspective, it 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 known guarantees for the Euclidean space assume a uniform distribution. However, if we consider the uniform distribution in the Poincaré model of the hyperbolic space, the corresponding Euclidean distribution is far from being uniform, i.e., 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.

heading: 3 SETUP AND NOTATION
text: 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 our results with Prokhorenkova & Shekhovtsov (2020), so we use a similar setup and notation for convenience.
To make the analysis feasible, Laarhoven (2018) and Prokhorenkova & Shekhovtsov (2020) assumed that the dataset is uniformly distributed on a sphere. The uniformity assumption is fairly strong. In Prokhorenkova & Shekhovtsov (2020), this setup was 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 is isometric to a sphere in the Euclidean space. Hence, to use the advantages of hyperbolic geometry, we assume that the dataset is uniformly distributed within a ball of some radius in the hyperbolic space.
Formally, consider a ball B(R) ⊂ Hd of radius R > 0. Assume that the dataset is a finite collection of points D = {x1, . . . , xn} ⊂ Hd, where xi ∈ D are i.i.d. random vectors uniformly distributed in B(R). For a given query q ∈ B(R), let x ∈ D be its nearest neighbor. Then, the goal of the exact NNS is to find x. For completeness, following Laarhoven (2018); Prokhorenkova & Shekhovtsov (2020), we also consider c, r-approximate near neighbor problem (c, r-ANN). In this scenario, it is assumed that q is planted uniformly within a fixed distance r > 0 from its nearest neighbor x and the goal is to return any x′ such that ρ(q, x′) ≤ c r for a fixed value c > 1 (Chen et al., 2018). Formally, in the exact nearest neighbor search, we also assume that q is planted uniformly within a distance r 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 (Chen et al., 2018). We focus on the so-called dense regime, where d log n. For the sparse regime (d log n), 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 ρ(x, y) ≤ ρ∗ for some ρ∗ 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 ρ∗.Next, we receive a query q, sample a random node x ∈ D, and at each step of the graph-based greedy descent, we measure the distances between the neighbors of the current node and q and move to the closest neighbor while we can make such greedy steps.

heading: 4 CONVERGENCE AND COMPLEXITY OF GRAPH-BASED NNS

heading: 4.1 LOCAL PROPERTIES OF HYPERBOLIC SPACE
text: 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 a given element. This probability, in turn, depends on the volumes of some balls’ intersections. As follows from our proof, for the dense regime, only ‘local’ properties are important for convergence. Let us show that under some conditions, the local properties in the hyperbolic space are similar to those in the Euclidean space.
Formally, let z = (1, 0, . . . , 0) and let TzHd = {x ∈ Rd,1 | x0 = 1} ' Rd be the tangent space. Let ĉ be the central projection ĉ : Hd → TzHd ' Rd from the origin o = (0, . . . , 0). The following lemma holds.
Lemma 1. Suppose that U ⊂ Hd is a measurable set such that U ⊂ B(0, r). If r 1√ d and d→∞, then we have VolHd(U) = VolEd(ĉ(U)) ( 1−O ( d r2 )) .
This result allows us to apply the bounds on volumes of Euclidean balls intersections to such volumes in the hyperbolic space for small radii.

heading: 4.2 INTUITION BEHIND THE CHOICE OF PARAMETERS
text: Our theoretical analysis is asymptotic, meaning that the number of elements n tends to infinity. Hence, we 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 at giving mathematically 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, 2020). In the dense regime on a 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−o(1) if graph degree is Md for M > √ 2. In the sparse regime, informally speaking, all nodes are at a spherical distance about π/2 from each other, making the NNS much more challenging. In this case, the graph degree has to grow as nϕ for some ϕ > 0 in order to solve the approximate near neighbor problem (Prokhorenkova & Shekhovtsov, 2020).
In this paper, we mostly focus on the dense regime with d log n and argue that for uniform data this setup is more realistic. Indeed, while in practice datasets are often embedded into spaces of large dimension, they usually have much smaller intrinsic dimension d′ d (Beygelzimer et al., 2006; Lin & Zhao, 2019). Moreover, for sparse uniform datasets on a sphere, graph-based NNS is expected to converge in just two steps (Prokhorenkova & Shekhovtsov, 2020) which contradicts practical observations. Similarly, the optimal graph degree in practice rarely exceeds 64, which roughly corresponds to d = 12 in the dense regime (see our discussion on Md above). It is also important to note that hyperbolic spaces are known to be beneficial when the dimension is small (Gu et al., 2018; Shevkunov & Prokhorenkova, 2021). For completeness of the study, we also analyze the sparse regime and theoretically show that graph-based NNS in the hyperbolic space has similar time and space complexity to NNS on the sphere.
We assume that the dataset is uniformly distributed within a ball B = 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 C = −1 is fixed while the radius of the ball R = R(n) may change or assume that the radius is fixed while the curvature C = C(n) changes. We further assume that C = −1 is fixed. Thus, we have three parameters: the number of elements n, the dimension d = d(n), and the radius R = R(n).
Denote by Vd(R) the volume of B, i.e., Vd(R) := VolHd(B(R)) and by vd(R) the normalized volume, i.e., vd(R) := Vd(R)/Vol(Sd−1). Let us analyze (approximately) the distance α from an element to its nearest neighbor. Intuitively, we should have
VolHd(B(α)) VolHd(B(R)) ≈ 1 n , VolHd(B(α)) ≈ Vd(R) n . (4)
Assume for now that α 1/ √ d. In this case, we have (see Section 4.1)
VolHd(B(α)) ∼ VolEd(B(α)) = Vol(Sd−1)αd
d .
Therefore, from (4),
αd ≈ Vd(R) d nVol(Sd−1) = vd(R) d n .
Let us find an upper bound on the radius R such that the condition α 1/ √ d is satisfied. Note that vd(R) = O ( eR(d−1) · 2−d · d−1 ) (see Appendix B). Thus, we need(
vd(R) d
n
)1/d 1√
d ,
( eR(d−1) 2−d
n
)1/d 1√
d , eR n1/(d−1) · d−1/2 .
Based on that, we further assume that in the dense regime eR n1/(d−1) · d−1/2. In this case, the distance to the nearest neighbor is α = o ( 1/ √ d )
, and locally the graph-based search behaves similarly to the Euclidean case. This assumption is natural: we empirically show that larger values of R lead to less efficient NNS.

heading: 4.3 MAIN RESULTS
text: 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 its neighborhood located within a ball of a fixed radius. In the dense regime, for any constant M > 1, let G(M) be a graph obtained by connecting xi and xj iff
ρ(xi, xj) ≤M ( d vd(R)
n
)1/d .
This radius is chosen to get about Md neighbors for each node. The following theorem holds. Theorem 1. Assume that d = d(n) is such that log log n d(n) log n and R = R(n) is such that eR n 1 d−1 · d−1/2 . For the exact NNS, let M be a constant s.t. M > √ 2. Then, with probability 1 − o(1), G(M)-based NNS finds the exact nearest neighbor. For c, r-ANN with some constant c > 1, let M be a constant s.t. M > √ 4c2
3c2−1 . Then, with probability 1 − o(1), G(M)-based NNS solves c, r-ANN for any r.
In both cases, the time complexity is O ( Md · n1/d ·R · (vd(R))−1/d ) ;
the space complexity is O ( n · log n ·Md ) .
The formal proof of this theorem is given in Appendices A-C, and in Appendix D we prove the similar theorem for k-NN graphs with k = [Md]. Theorem 1 covers several different regimes. First, assume that R 1/ √ d. In this case, the geometry is approximately Euclidean. We have vd(R) ∼ Rd, so the following corollary holds. Corollary 1. If R = R(n) 1/ √ d, then in Theorem 1 the time complexity is O ( Md · n1/d ) .
As expected, this result is similar to the corresponding theorem in Prokhorenkova & Shekhovtsov (2020). However, as R becomes larger, time complexity changes. For instance, if R log d, then we have vd(R) ∼ eR(d−1) Θ(d−12−d). Thus, we get the following corollary. Corollary 2. If R = R(n) log d, then in Theorem 1 we obtain the time complexity O ( Md · n1/d ·R · e−R(d−1)/d ) .
From this corollary we see that the time complexity decreases with the radius R. Thus, to make the complexity smaller, we should take larger values of R. According to Theorem 1, we can take R such that eR = n 1 d−1 /( √ dϕ), where ϕ = ϕ(n)→∞. We obtain the following corollary.
Corollary 3. If for an arbitrary ϕ = ϕ(n) → ∞ we have eR = n 1 d−1 /( √ dϕ) → ∞, then in Theorem 1 we get the time complexity O ( Md · log n · d−1/2 · ϕ ) .
Thus, in the hyperbolic space, the number of steps can be reduced from n1/d to about log n. This shows that NNS over plain nearest neighbor graphs can be more efficient in the hyperbolic space 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. Thus, we can faster reach any point from, e.g., the origin of the ball. Note that in the Euclidean space, we can also reduce the number of steps to log n 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.
Finally, let us discuss the sparse regime with d log n. 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 connect the elements xi and xj if cosh ρ(xi, xj) ≤ cosh2R − sinh2R ·
√ 2M logn
d . We also need the following notation. For any
constant c > 1 let αc := cosh2 R−cosh(arccosh(cosh2 R)/c)
sinh2 R . The following theorem holds.
Theorem 2. Assume that d log n and R log d. Let c > 1 and let M be any constant such that M < α 2 c
α2c+1 . Then, with probability 1 − o(1), G(M)-based NNS solves c, r-ANN (for any r); the time complexity of this procedure is Θ ( n1−M+o(1) ) ; the space complexity is Θ ( n2−M+o(1) ) .
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.

heading: 5 EXPERIMENTS
text: In this section, we first compare graph-based approaches with the algorithm proposed by Wu & Charikar (2020) on Poincaré GloVe word embeddings (Tifrea et al., 2018) and on the recommendation dataset from (Shevkunov & Prokhorenkova, 2021). Then, we compare the efficiency of graphbased approaches for Euclidean and hyperbolic representations of the same sets of elements. Finally, we illustrate our theoretical results from Section 4.3 on synthetic datasets uniformly distributed within spaces of different curvatures. The code of our experiments supplements the submission.

heading: 5.1 COMPARISON WITH BASELINE
text: We compare graph-based approaches with an existing method of hyperbolic NNS on two datasets. First, we collect the largest publicly available Poincaré GloVe vocabulary1 of 189, 533 unique tokens. Poincaré GloVe was shown to outperform the Euclidean representation for tasks of similarity, analogy, and hypernymy detection (Tifrea et al., 2018). The dimensionality of the embeddings is 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. We also consider the recommendation dataset from Shevkunov & Prokhorenkova (2021), where a DSSM model was trained on a Wikipedia search dataset of (search query, relevant page) pairs. We use their Euclidean and hyperbolic representations for d = 10.
On the base set, we construct the HNSW graph (Malkov & Yashunin, 2018) and the NSG graph (Fu et al., 2019), both are considered to be the current state-of-the-art similarity graphs for NNS. As for the search algorithm, we perform the best-first search. The parameter efSearch determines the stopping criteria of the best-first search and allows us to 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: it is 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 by the authors, so we use our implementation. To make the comparison fair, we count the number of distance computations (DCS) instead of the actual time, as the latter may depend on the efficiency of our implementation. The algorithm details and parameter tuning are discussed in Appendix F.
To evaluate the algorithms, we plot Complexity-versus-Accuracy curves. As a primary measure of the search accuracy, we consider Recall@1. The search complexity is the average number of DCS per query. The results for Poincaré GloVe are shown in Figure 1. We see that both graph-based approaches significantly outperform the baseline. This confirms that applying an algorithm directly to the hyperbolic space is more efficient than reducing the problem to Euclidean NNS. Among graph-based algorithms, HNSW has better performance on this dataset. Due to space constraints, we provide additional experiments in Appendix F: we show the results on Poincaré GloVe for d = 10 and on the recommendation dataset from Shevkunov & Prokhorenkova (2021). Importantly, the recommendation dataset has different properties compared to Poincaré GloVe — the learned vector norms are sufficiently larger. This property makes the dataset very challenging for Spherical Shell; see Appendix F for the details.
1https://github.com/alex-tifrea/poincare_glove

heading: 5.2 EUCLIDEAN VS POINCARÉ GLOVE
text: This section additionally illustrates that graph-based methods are well suited for hyperbolic NNS by comparing the efficiency of HNSW for Euclidean and hyperbolic spaces. For this, we construct HNSW graphs for Euclidean GloVe (Pennington et al., 2014) and Poincaré GloVe (Tifrea et al., 2018) with the same tokens and perform NNS for each dataset. Note that the results cannot be compared directly: GloVe and Poincaré GloVe have different geometry, so nearest neighbors for the same queries may differ. Thus, we only aim to show that switching from Euclidean to hyperbolic embeddings does not make NNS significantly less efficient.
Figure 2 shows that HNSW built on embeddings in the hyperbolic space is even more efficient than HNSW over Euclidean embeddings.2 Similar experiment for the GloVe embeddings with d = 10 and for the recommendation dataset are given in Appendix F.

heading: 5.3 ILLUSTRATING THEORETICAL RESULTS ON SYNTHETIC DATASETS
text: Finally, we illustrate Theorem 1 and our corollary that for simple nearest neighbor graphs and sufficiently small dimension d, graph-based 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 R in the hyperbolic space of curvature −1. For all spaces, we fix n = 106 and vary the dimension d ∈ {2, 4, 6}. For the hyperbolic space, we also vary the radius R. Recall that this is equivalent to changing the curvature. To get an intuition on which values of R are meaningful, recall that Theorem 1 requires eR n1/(d−1)/ √ d. Thus, roughly speaking, we obtain the following upper bound on R: Rmax = logn d−1 − log √ d. For d = 2, we get Rmax ≈ 13.5, for d = 4, we get Rmax ≈ 3.9, while for d = 6 we have Rmax ≈ 1.9. Thus, we see that even for d = 6 the bound on the radius is sufficiently small and the obtained geometry becomes similar to the Euclidean one (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 neighbor graphs; this setup corresponds to our theoretical analysis. To get the Complexity-versus-Accuracy curves, we vary the graph degree. In Figure 3 we see that spherical and Euclidean spaces are very similar. Hyperbolic space on a small scale, i.e., when points are located inside a ball of a sufficiently small radius R, is similar to the Euclidean one. Then, as R increases, the performance improves. However, after some point, larger values of R reduce the quality of NNS. It is worth noting that this threshold agrees well with the dynamic of Rmax (while being smaller, as expected).
Then, we analyze what happens if we add long edges known to be essential for the NNS in spherical and Euclidean spaces when the dimension d is small. To incorporate long edges into NN graphs, we follow the procedure described in Prokhorenkova & Shekhovtsov (2020). As expected, long edges
2Note that computing the hyperbolic distance has the same complexity as computing the inner product, as follows from Equation (1).
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 if R is sufficiently small, while larger values of R even lead to a performance downgrade.
We also conduct similar experiments with greedy search replaced by the best-first search, which is a standard technique for graph-based NNS performance improvement. The conclusions are the same; we include the figures in Appendix F.

heading: 6 CONCLUSION
text: 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 nearestneighbor graphs assuming that the dataset is uniformly distributed over a ball of radius R in the hyperbolic space. Assuming the dense regime (d log n) and that the absolute value of the curvature 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 log n), we show that NNS has similar complexity in Euclidean and hyperbolic spaces.
From a practical perspective, we show that graph-based algorithms outperform other existing methods on several datasets with different properties. Also, compared to the Euclidean NNS, switching to hyperbolic space does not lead to significantly increased complexity and may even reduce the query time. We hope that our research will attract more attention to theoretical and empirical analysis of NNS in hyperbolic spaces and, in particular, to graph-based methods.
Finally, let us discuss how our theoretical results relate to practice. Clearly, the uniformity assumption is strong and does not hold for real data. However, it allows us to get intuition regarding what would happen in practice. Informally speaking, the conditions on d, R, and n define the density of elements within the hyperbolic space. If the required conditions are locally satisfied, then the convergence with probability 1− o(1) holds for NNS based on kNN graphs with k = Md. In practice, the theoretical guarantees are expected to depend on intrinsic dimension d′. Informally speaking, a dataset can be locally approximated by a close-to-uniform distribution in a d′-dimensional space, and then our convergence results can be applied.

heading: A AUXILIARY GEOMETRICAL RESULTS
text: 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 if the ball’s radii are sufficiently small.

heading: A.1 EUCLIDEAN BALLS AND THEIR INTERSECTIONS
text: For a ball B = B(1) of unit radius in a d-dimensional Euclidean space, we have that its volume satisfies
VolEd(B) = π d 2 Γ ( d 2 + 1 ) . In this section, we estimate volumes of spherical caps, and then use the obtained bounds to estimate the volumes of balls’ intersections.
Let B(x, α) be a ball of radius α centered at x, and Cα(x, z, h) ⊆ B(x, α) be a d–dimensional spherical cap of height h centered at z ∈ Sα(x), i.e., Cα(x, z, h) = {y ∈ B(x, α) : 〈y− x, z− x〉 ≥ α(α− h)}. Let Cα(h) := VolEd (Cα(x, z, h)) be the volume of this spherical cap.
Definition 1. Let qα(h) := ( 1− ( 1− hα )2)1/2 be the “rel-
ative radius” of a spherical cap (see qα(h) in the figure).
Lemma 2. The volumeCα(h) of a spherical capCα(x, z, h) can be estimated as follows:
Θ(d−1) ≤ Cα(h) VolEd−1(B) · αd · qα(h)d+1 ≤ Θ(d− 12 ).
Proof. For brevity, let q = qα(h). Put γ = arccos(1−h/α), 0 ≤ γ ≤ π2 . The volume of a spherical cap of height h is known to be:
Cα(h) = VolEd−1(B) · αd · γ∫
0
sind(t) dt.
First, rewrite the integral:
γ∫ 0 sind(t) dt = |x = sin2 t| = 1 2 q2∫ 0 x d−1 2 (1− x)− 12 dx
= |x = q2t| = 1 2 qd+1 1∫ 0 t d−1 2 ( 1− q2t )− 12 dt. To prove the lemma, it remains to show that
Θ(d−1) ≤ 1∫
0
t d−1 2 ( 1− q2t )− 12 dt ≤ Θ(d− 12) .
Indeed,
Θ(d−1) = 1∫ 0 t d−1 2 dt ≤ 1∫ 0 t d−1 2 ( 1− q2t )− 12 dt ≤
1∫ 0 t d−1 2 (1− t)− 1 2 dt = B ( d+ 1 2 , 1 2 ) = Θ ( d− 1 2 ) ,
where B(·, ·) denotes the beta function. This concludes the proof.
Let us now estimate the volume of the intersection of two Euclidean balls. Let Wxi,xj (α, β) denote the intersection of B(xi, α) and B(xj , β), i.e., Wxi,xj (α, β) = {y : ρ(xi, y) ≤ α, ρ(xj , y) ≤ β}. Let s := ρ(xi, xj) be the distance between the centers and W (α, β, s) := VolEd ( Wxi,xj (α, β) ) denote the volume of the intersection. The following lemma estimates the value W (α, β, s) under various conditions on α, β, s.
Lemma 3. W.l.o.g., assume that α ≤ β. Define A := (α+β+s)(α+β−s)(s+α−β)(s+β−α)4s2 .
1. If α+ β < s, then W (α, β, s) = 0.
2. If s− α ≤ β < √ α2 + s2, then
Θ ( d−1 ) ≤ W (α, β, s) · αβ
VolEd−1(B) · (α+ β) ·A d+1 2
≤ Θ ( d− 1 2 ) . (5)
3. If √ α2 + s2 ≤ β < s+ α, then
1 2 ≤ W (α, β, s) VolEd(B) · αd ≤ 1, (6)
VolEd(B(α))−W (α, β, s) VolEd−1(B) ·A d+1 2 · α−1
≤ Θ ( d− 1 2 ) (7)
4. If s+ α ≤ β, then
W (α, β, s) = VolEd(B) · αd. (8)
Proof. Let hα := β2−(s−α)2 2s , hβ := α2−(s−β)2 2s , h̃α := (α+s)2−β2 2s .
1. If α+ β < s, then the balls do not intersect and thus W (α, β, s) = 0, see Figure 4a.
2. If s− α ≤ β < √ α2 + s2, then, according to Figure 4b,
W (α, β, s) = Cα(hα) + Cβ(hβ) .
By Lemma 2, we have
Θ ( d−1 ) ≤ W (α, β, s)
VolEd−1(B) · ( αdqd+1α (hα) + βdq d+1 β (hβ)
) ≤ Θ(d− 12) .
Substituting qα, qβ , hα, hβ , we obtain that
αdqd+1α (hα) + β dqd+1β (hβ)
= αd ( α2 − (α− hα)2
α2
) d+1 2 + βd ( β2 − (β − hβ)2
β2
) d+1 2
= 1
α (hα(2α− hα))
d+1 2 +
1 β (hβ(2β − hβ)) d+1 2
= 1
α
( (β2 − (s− α)2)((s+ α)2 − β2)
4s2
) d+1 2
+ 1
β
( (α2 − (s− β)2)((s+ β)2 − α2)
4s2
) d+1 2
=
( 1
α +
1
β
) A d+1 2 .
3. If √ α2 + s2 ≤ β < s+ α, then (see Figure 4c)
VolEd(B(α))
2 ≤W (α, β, s) ≤ VolEd(B(α)),
Also, according to Figure 4c, VolEd(B(α))−W (α, β, s) = Cα(h̃α)− Cβ(hβ) ≤ Cα ( h̃α ) .
By Lemma 2, we have
VolEd(B) · αd −W (α, β, s) VolEd−1(B) · αd · qd+1α (h̃α)
≤ Θ ( d− 1 2 ) .
Substituting qα and h̃α, we get
αdqd+1α (h̃α) = α d
( α2 − (α− h̃α)2
α2
) d+1 2
= 1
α
( h̃α(2α− h̃α) ) d+1 2
= 1
α
( ((s+ α)2 − β2)(β2 − (s− α)2)
4s2
) d+1 2
= 1 α A d+1 2 .
4. If s+ α ≤ β, then W (α, β, s) = VolEd(B(α)) = VolEd(B) · αd, see Figure 4d.
The following lemma will also be helpful in our proofs. Lemma 4. W (α, β, α) and W (β, α, α) are non-decreasing functions of α.
Proof. Let us consider the configuration of balls shown in Figure 5. The d-dimensional ball centered at q′ is contained within the ball centered at q. Thus, the intersection A′B′x of the balls centered at x 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 x can be taken on the geodesic between q 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.

heading: A.2 HYPERBOLIC VOLUMES
text: First, we briefly recall the basic properties of hyperbolic space, and then move towards the study of hyperbolic volumes and their Euclidean counterparts. It turns out that on the small scale hyperbolic volumes behave in an almost Euclidean way, while on larger scale their behaviour is fundamentally different.

heading: A.2.1 BACKGROUND ON HYPERBOLIC SPACE
text: Let Rd,1 be the (d+1)-dimensional Minkowski space, i.e., the real vector space of dimension (d+1) equipped with the inner product
〈x, y〉h = −x0y0 + x1y1 + . . .+ xdyd of signature (d, 1).
The vector model of the d-dimensional hyperbolic Lobachevsky space Hd is the connected component of the standard two-sheeted hyperboloid contained in the future light cone:
Hd = {x ∈ Rd,1 | 〈x, x〉h = −1, x0 > 0}. (9)
The hyperbolic metric is given by
cosh ρ(x, y) = −〈x, y〉h.
The coordinates (x0, x1, . . . , xd) satisfy the following system of equations:
x0 = cosh(t1),
x1 = sinh(t1) cos(t2),
. . .
xd−1 = sinh(t1) sin(t2) . . . sin(td−1) cos(td),
xd = sinh(t1) sin(t2) . . . sin(td−1) sin(td).
This hyperbolic coordinate parameterization of Hd is the map
χ : [0,+∞)× [0, π]d−2 × [0, 2π]→ Hd
defined by χ(t1, . . . , td) = (x0, x1, . . . , xd).
A subset U ⊂ Hd is called measurable if χ−1(U) is measurable with respect to the standard Lebesgue measure on Rd. Let U ⊂ Hd be a measurable set. Then, the hyperbolic volume of U is defined by
VolHd(U) = ∫ χ−1(U) sinhd−1(t1) sin d−2(t2) . . . sin(td−1) dt1dt2 . . . dtd−1dtd.

heading: A.2.2 APPROXIMATING SMALL HYPERBOLIC VOLUMES BY THEIR EUCLIDEAN COUNTERPARTS
text: In this section, we show that small hyperbolic volumes can be approximated by Euclidean ones. This is very helpful for our analysis and will allow us to obtain analogs of Lemma 2 and 3 for small hyperbolic balls.
From the definition of the hyperbolic space (9), we see that x0 = √ 1 + x21 + . . .+ x 2 d. Let U ⊂ Hd be a measurable set containing the point z = (1, 0, . . . , 0), and let U ′ be the projection of U along the x0–coordinate from the hyperboloid onto the tangent space TzHd = {x ∈ Rd,1 | x0 = 1} ' Rd realised by the map p : Hd → Rd. Let c be the central projection c : Hd → TzHd ' Rd from the origin o = (0, . . . , 0). Let F : U ′ → ĉU) be the map that satisfies c = F ◦ p. Let us note that the central projection cmaps balls centered at z in Hd to balls centered at p(z) = z in Rd, and also spherical caps of such balls in Hd have spherical caps in Rd as their respective images, since every spherical cap is an intersection of some ball with a half-space, which is bounded by some hyperplane in Rd,1 (the central projection of this hyperplane is also a hyperplane in Rd).
According to Ratcliffe (2019),
VolHd(U) = ∫ U ′ dx1 . . . dxd√ 1 + x21 + . . .+ x 2 d .
We need to compare VolHd(U) to VolEd(ĉU)) in order to conclude that these quantities approximate each other in some appropriate regime. Lemma 5. Suppose that U ⊂ Hd is a measurable set such that U ⊂ B(0, r). If r 1√
d and
d→∞, then we have VolHd(U) = VolEd(ĉU)) ( 1−O ( d r2 )) .
Proof. We have that U ′ = p(U) ⊂ BRd(0, sinh(r)), hence x21 + . . .+ x2d ≤ sinh 2(r). Then,∫
U ′
dx1 . . . dxd cosh(r) < VolHd(U) = ∫ U ′ dx1 . . . dxd√ 1 + x21 + . . .+ x 2 d < ∫ U ′ dx1 . . . dxd = VolEd(U ′).
By using Taylor series expansion, we obtain∫ U ′ dx1 . . . dxd cosh(r) = 1 cosh(r) VolEd(U ′) = ( 1− r 2 2 + Θ ( r4 )) VolEd(U ′),
and thus ( 1− r 2
2 + Θ
( r4 )) VolEd(U ′) < VolHd(U) < VolEd(U ′).
Now let us show that VolEd(U ′) = VolEd(ĉU)) ( 1−O ( dr2 )) .
Indeed, the map F : U ′ → ĉU) satisfies c = F ◦ p and is given by F = (F1, . . . , Fd) with Fi : xi 7→
xi√ 1 + x21 + . . .+ x 2 d , for i = 1, . . . , d,
and thus the Jacobian of F satisfies
det ( ∂Fi ∂xj )d i,j=1 = 1 (1 + x21 + . . .+ x 2 d) d+2 2 = 1−O ( dr2 ) ,
whenever x21 + . . .+ x 2 d ≤ sinh 2(r) and dr2 → 0. One can conveniently use spherical coordinates in order to perform the respective computation. The lemma now follows from standard Taylor series techniques.
Let Bd(x, r) be a closed hyperbolic ball centered at a point x ∈ Hd of radius r > 0. Then we can compute its volume as Ratcliffe (2019):
VolHd(Bd(x, r)) = Vol ( Sd−1 ) r∫ 0 sinhd−1(t) dt.
For r log d, we have VolHd(Bd(x, r)) ∼ Vol(Sd−1) exp(r(d− 1)) Θ(d−12−d). For r 1/ √ d, we have from Lemma 5 that
VolHd(Bd(x, r)) ∼ VolEd(Bd(x, r)) ∼ Vol(Sd−1) d−1 rd Θ(1).

heading: A.2.3 SMALL HYPERBOLIC BALLS AND THEIR INTERSECTIONS
text: Lemma 5 allows 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 Cα(h) be the volume of a spherical cap of height h in the hyperbolic space. The following lemma follows from Lemma 2 and Lemma 5. Lemma 6. For α 1/ √ d, the volume of a hyperbolic spherical cap can be estimated as follows:
Θ(d−1) ≤ Cα(h) VolEd−1(B) · αd · qα(h)d+1 ≤ Θ(d− 12 ).
Let us now estimate the volume of the intersection of two hyperbolic balls. As before, denote by Wxi,xj (α, β) the intersection of B(xi, α) and B(xj , β), i.e., Wxi,xj (α, β) = {y : ρ(xi, y) ≤ α, ρ(xj , y) ≤ β}. Let s := ρ(xi, xj) be the distance between the centers and W (α, β, s) := VolHd ( Wxi,xj (α, β) ) denote the volume of the intersection. The following lemma estimates the value W (α, β, s) for various relationships between α, β, s. Without loss of generality, we assume that α ≤ β. Lemma 7. Assume that α 1/ √ d, β 1/ √ d. W.l.o.g., we may also assume that α ≤ β. Define A := (α+β+s)(α+β−s)(s+α−β)(s+β−α)4s2 .
1. If α+ β < s, then W (α, β, s) = 0. 2. If s− α ≤ β < √ α2 + s2, then
Θ ( d−1 ) ≤ W (α, β, s) · αβ
VolEd−1(B) · (α+ β) ·A d+1 2
≤ Θ ( d− 1 2 ) . (10)
3. If √ α2 + s2 ≤ β < s+ α, then
1 2 ≤ W (α, β, s) VolEd(B) · αd · (1 + o(1)) ≤ 1, (11)
VolHd(B(α))−W (α, β, s) VolEd−1(B) ·A d+1 2 · α−1
≤ Θ ( d− 1 2 ) . (12)
4. If s+ α ≤ β, then
W (α, β, s) = VolHd(B(α)) ∼ VolEd(B) · αd. (13)
Proof. To prove this lemma, we follow the proof of Lemma 3, and use Lemma 6 instead of Lemma 2.
The following lemma is an 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. W (α, β, α) and W (β, α, α) are non-decreasing functions of α.

heading: B PROOF OVERVIEW
text: In this section, we overview the proof of Theorem 1.
Recall that we assume that the distribution of the dataset is uniform over a d-dimensional ball B of radius R = R(n) such that
eR n 1/(d−1)
d1/2 . (14)
Then, the graph G(M) is constructed by using balls of radius αM = Mδ with
δ =
( dvd(R)
n
)1/d . (15)
Let us show that under the conditions of the theorem, we have δ 1/ √ d. First, note that
vd(R) = R∫ 0 sinhd−1(t) dt ≤ R∫ 0 et(d−1) 2d−1 dt ≤ e R(d−1) 2d−1(d− 1) .
Thus, we have
δ ≤ ( deR(d−1)
2d−1(d− 1)n
)1/d = Θ ( eR(d−1)/dn−1/d ) 1/ √ d.
The last inequality is due to the conditions of Theorem 1. Thus, we can apply Lemma 7 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 x such that ρ(q, x) = αs, the probability of making a step towards q is determined byW (αs, αM , αs): the distance between the points is αs, the neighbors of x are within the ball of radius αM centered at x, and we accept those neighbors that are closer to q than x, i.e., within a ball of radius αs centered at q. Lemma 9 analyzes the asymptotic behavior of W (αs, αM , αs).
Lemma 4 states that W (α, β, α) is a non-increasing function of α. Informally, it means that it is easier to make steps towards the query when ρ(x,q) is larger. In contrast, when x becomes closer to q, the probability of getting stuck in a local optimum increases. Therefore, to obtain lower bounds on W (αs, αM , αs), we can consider only the case when αs is small. Below we assume that αs = sδ, where s is some constant.
Lemma 11 gives the following lower bounds on W (αs, αM , αs) :
1. if M < s √ 2, then W (αs,αM ,αs)Vd(R) ≥ 1 n · ( M2 − M 4 4s2 ) d 2+o(d) ; 2. if M ≥ s √
2, then W (αs,αM ,αs)Vd(R) ≥ 1 n · s d+o(d).
Let us consider one step of the algorithm. We can move forward w.h.p. if W (αs, αM , αs) 1/n. Formally speaking, Corollary 4 of Lemma 11 states that if M and s satisfy
s > 1 and either M ≥ s √ 2 or M2 −M4/4s2 > 1, (16)
then there exists a constant S > 1 such that we can make a step towards q with probability
1− ( 1− S d+o(d)
n
)n−1 = 1−O ( e−S d+o(d) )
since the expected number of nodes in the intersection of balls is much greater than 1.
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 approximate near neighbor or find the exact nearest neighbor by making one more step.
First, let us consider the exact NNS. In this case, we assume that the nearest neighbor is located within a ball of radius r, 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 > √ 2. Observe that this implies
M√ 2 >
M2
2 √ M2 − 1 . (17)
While we move towards the query, s becomes smaller. Let us figure out up to which s we can make steps. According to (16), we need either 1 < s ≤ M/ √ 2 or s > M2/2 √ M2 − 1. According to (17), it reduces to s > 1. In other words, we can move forward to any s > 1. Then, according to Lemma 14, it is sufficient to haveM2 > s2 +r2 to reach the exact nearest neighbor of q in one step.
Thus, we can take any s s.t. 1 < s < √ M2 − r2: we can reach this distance with greedy search and then jump directly to the nearest neighbor with high probability.
Now, let us turn to the approximate near neighbor search c, r-ANN. In this case, we need to find an element that is within a distance rc from q. According to the statement of the theorem, we have M > √ 4c2/(3c2 − 1).
Note that F (r) := 2r2c2 ( 1− √ 1− 1/r2c2 ) decreases with r for r > 1/c and equals 2 at r = 1/c,
while G(r) := 23 ( r2 + 1 + √ r4 − r2 + 1 ) increases with r and equals 2 at r = 1. Both F (r) and
G(r) attain 4c2/(3c2 − 1) at r0 = √ 4c2/(c2 + 1)(3c2 − 1). Therefore, we either have
1 ≥ r > r0 and M2 > F (r) (18) or
r0 ≥ r > 1
c and M2 > G(r). (19)
To solve c, r-ANN, either we can reach s such that rc > s or we can reach s such that at the next step we can find the exact nearest neighbor. Let us consider the first possibility. Note that
s > 1 and M2 > 2s2 ( 1− √
1− 1 s2
) (20)
is equivalent to (16). In turn, since 2s2(1− √
1− 1/s2) is a decreasing function of s on s > 1, we get that (18) implies the existence of s such that rc > s > 1 and
M2 > 2s2 ( 1− √ 1− 1
s2
) > F (r).
Hence, since (16) holds, we can move forward to such s. Let us consider the second possibility. Observe that (19) is equivalent to
M2 − r2 > M 4
4(M2 − 1) .
Therefore, there exists s such that the condition s2 < M2 − r2 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 14 is satisfied.
Above we show that under the conditions of the theorem, each step of the greedy search is successful with probability 1 − O ( e−S d+o(d) )
. 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 at each step of the algorithm we become closer to the query by some fixed positive value. In Lemma 12, we prove that each step reduces the distance from q by at least εδ, where ε is some positive constant. Clearly, we start at a distance O(R) from q. Hence, we are able to bound the number of steps by O(R/εδ) which is O ( Rn1/d(vd(R))
−1/d) . To estimate the overall success probability, we have to consider the dependence of consecutive steps of the algorithm. Lemma 13 implies that consecutive steps are “almost independent” and the overall success probability is 1−O ( Rn1/d(vd(R)) −1/de−S d+o(d) ) . The assumption d log log n and the
fact that vd(R) = Ω(Rd) yield O ( Rn1/d(vd(R)) −1/de−S d+o(d) ) = O ( e logn d −S d+o(d) ) = o(1).
While in most of the analysis we do not consider the cases when αM -neighborhoods of the dataset elements intersect the boundary ∂B, we need to show that possible intersections do not affect the result. The formal statement of this fact is given in Lemma 15.
Finally, let us discuss the time and space complexities of the algorithm. Let v be a fixed arbitrary node of G(M) and let N(v) denote the (random) number of its neighbors in G(M). Let f = f(n) = (n − 1)VolHd (B(αM )) /VolHd (B) denote the upper bound for the expected number of neighbors of v (this is an upper bound due to possible boundary effects). In Lemma 16, we show that N(v) ≤ 3f/2 with probability at least 1−O(1/f).
To obtain the final time complexity of graph-based NNS, we sum up the complexity of all algorithm’s steps. In Lemma 17, we show that if k steps of the NNS are made then the time complexity is O (kfd) with probability 1−O(1/kf). In Lemma 18, we show that the number of edges in the graph is E(G) ≤ 3fn/4 with probability 1 − O(1/fn). If we store the graph as the adjacency lists, then the space complexity is O (E(G) · log n) = O (fn log n) .
Due to the choice of δ, we have f = O ( Md ) . Hence, w.h.p. the space complexity is
O ( n · log n ·Md ) and the time complexity is O ( R · n1/d · (vd(R))−1/d ·Md ) .

heading: C RESULTS USED THROUGHOUT THE PROOF
text: 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 a particular space in W (·, ·, ·).

heading: C.1 ANALYSIS OF CONVERGENCE
text: Recall that αM = Mδ and αs = sδ, where M and s are some constants and δ is defined in (15). Recall that δ 1/ √ d.
Lemma 9. Define A := α 2 M (4α 2 s−α 2 M )
4α2s .
If αM ≤ αs √ 2, then
Θ ( d−1 ) ≤ W (αs, αM , αs) · αMαs
VolEd−1(B) · (αM + αs) ·A d+1 2
≤ Θ ( d− 1 2 ) . (21)
If αM > αs √
2, then W (αs, αM , αs)
VolEd (B)αds = Θ(1). (22)
Proof. We apply Lemma 7. First, consider the case αM ≤ αs. Then, the case 2 applies to W (αM , αs, αs). From (10) we obtain
Θ ( d−1 ) ≤ W (αs, αM , αs) · αMαs
VolEd−1(B) · (αM + αs) ·A d+1 2
≤ Θ ( d− 1 2 ) . (23)
Now, consider the case αs < αM .
1. If αs < αM ≤ αs √ 2, then from (10) we obtain
Θ ( d−1 ) ≤ W (αs, αM , αs) · αMαs
VolEd−1(B) · (αM + αs) ·A d+1 2
≤ Θ ( d− 1 2 ) .
2. If αs √ 2 < αM < 2αs, then (11) yields
W (αs, αM , αs) = Θ ( VolEd(B) · αds ) .
3. If 2αs ≤ αM , then (13) gives
W (αs, αM , αs) = VolEd(B) · αds (1− o(1)) .
This concludes the proof of the lemma.
Lemma 10. Denote by A = δ2 · (M+r+s)(M+r−s)(s+M−r)(s+r−M)4s2 . If αs − αr < αM <√ α2s + α 2 r, then
Θ ( d−1 ) ≤ W (αr, αM , αs) · δ
VolEd−1(B) ·A d+1 2
≤ Θ ( d− 1 2 ) . (24)
If αM > √ α2s + α 2 r, then
VolHd(B(αr))−W (αr, αM , αs) VolEd−1(B) ·A d+1 2 · δ−1
≤ Θ ( d− 1 2 ) . (25)
Proof. The result follows directly from Lemma 7. Lemma 11. If M > s √ 2, then
W (αs, αM , αs) ≥ Vd(R)
n · sd+o(d).
If M ≤ s √ 2, then
W (αs, αM , αs) ≥ Vd(R) n · ( M2 − M 4 4s2 ) d 2+o(d) .
Proof. If M > s √ 2, then we can apply (22) to obtain
W (αs, αM , αs) ≥ Θ ( d−1 · (sδ)d ·VolEd(B) ) = Θ ( d−1 · sd · dvd(R)
n ·VolEd(B) ) = Θ ( sd · Vd(R)
n · VolEd(B) Vol(Sd−1)
) = Vd(R)
n sd+o(d).
If M ≤ s √ 2 then we can apply (21) to obtain
W (αs, αM , αs) ≥ VolEd−1(B) · δ−1A d+1 2 Θ(d−1)
= VolEd−1(B) · δ−1 · αd+1M · ( 1− α 2 M
4α2s
) d+1 2
·Θ(d−1)
= VolEd−1(B) · δd ·Md+1 ( 1− M 2
4s2
) d+1 2
·Θ(d−1)
= VolEd−1(B) Vol(Sd−1) · Vd(R) n ·Md+1
( 1− M 2
4s2
) d+1 2
·Θ(1)
= Θ ( d−1 ) · Vd(R) n · ( M2 − M 4 4s2 ) d+1 2 = Vd(R) n · ( M2 − M 4 4s2 ) d 2+o(d) .
Corollary 4. If s > 1 and either M > s √
2 or M2 −M4/4s2 > 1, then there exists a constant S > 1 such that W (αs, αM , αs) ≥ Vd(R)n S d+o(d). Lemma 12. Assume that s > 1. If
M > s √ 2 or M2 − M 4
4s2 > 1, (26)
then there exist constants S > 1 and ε > 0, such that
W (αM , αs, αs + εδ) ≥ Vd(R)
n Sd+o(d).
Proof. If M > s √
2, then we can choose a sufficiently small ε > 0 such that M2 ≥ s2 + (s+ ε)2. Then, the result follows from Lemma 11 and the fact that s > 1. Otherwise M2 < s2 + (s + ε)2, and instead of the condition M2 − M 4
4s2 > 1 from (24) we have
4s2(s+ ε)2 − (M2 − s2 − (s+ ε)2)2
4(s+ ε)2 > 1.
As it holds for ε = 0, we can choose a small enough ε > 0 that it is still satisfied.
Lemma 13. The dependence of consecutive steps is negligible.
Proof. First, consider the case M ≤ s √
2. It suffices to show that W1 = W (αM , αs, αs + 2εδ) is negligible in comparison with W1 + W2 = W (αM , αs, αs + εδ) and the same for W1 = W (αs, αM , αs + 2εδ) compared to W1 + W2 = W (αs, αM , αs + εδ) . From (24) we can write their ratio
W1 W1 +W2 =
( 4(s+ ε)2
2 (M2s2 + s2(s+ ε)2 +M2(s+ ε)2)− (M4 + s4 + (s+ ε)4) · 2 ( M2s2 + s2(s+ 2ε)2 +M2(s+ 2ε)2 ) − ( M4 + s4 + (s+ 2ε)4 ) 4(s+ 2ε)2 ) d+1 2 = o(1).
Since at each step we reduce the radius of the ball centered at q which contains the current position by at least εδ, any ball encountered in the current iteration intersects only a constant number of other balls, so their overall effect is negligible. In the case when M > s √
2 and s > 1 with probability 1− o(1) we find the nearest neighbor in one step.
Lemma 14. If for some constants M , s, r we have M2 > s2 + r2, then VolHd (B(αr))−W (αr, αM , αs) ≤ VolHd (B(αr)) · βd
with some β < 1.
Proof. It follows from (25) that VolHd (B(αr))−W (αr, αM , αs) ≤ Θ ( d− 1 2 ) ·VolEd−1(B) ·A d+1 2 · δ−1.
It remains to bound from above the following ratio: Θ ( d− 1 2 ) ·VolEd−1(B) ·A d+1 2 · δ−1
VolHd (B(αr)) =
Θ ( d− 1 2 ) ·VolEd−1(B) ·A d+1 2
VolEd(B) · rd · δd+1 = Θ(1) ·
( A
δ2r2
) d+1 2
= Θ(1) · (
(M + r + s)(M + r − s)(s+M − r)(s+ r −M) 4r2s2
) d+1 2
=
Θ(1) · ( 1− (M 2 − s2 − r2)2
4s2r2
) d+1 2
≤ βd+1
for some β < 1.

heading: C.2 ANALYSIS OF THE BOUNDARY EFFECT
text: Lemma 15. The boundary effect is negligible and does not affect our results.
Proof. Consider the worst-case scenario when the current element is located on the boundary of the ball B (see Figure 6). Indeed, in this case, the largest part of the neighborhood is located outside B, which may reduce the number of neighbors of a given element.
First, consider the Euclidean space. According to Lemma 5, this is equivalent to the hyperbolic case with R 1/ √ d. Let us show that W (α,R,R) converges to 12VolEdB(α) if α = Θ(δ) with
δ = ( dVolEd (B(R))
Vol(Sd−1)n )1/d . Note that W (α,R,R) = Cα(h) + CR(α − h) < 12VolEdB(α). It is easy
to see that h = α− α 2
2R . Then,
Cα(h) = 1
2 VolEd−1(B)α
dB
( d+ 1
2 ,
1 2 ; 1− α
2
4R2 ) = (1 + o(1)) · 1
2 VolEd−1(B)α
dB
( d+ 1
2 ,
1
2
) = (1 + o(1)) · 1
2 VolEdB(α),
if α 1/ √ d. Indeed,
B
( d+ 1
2 ,
1
2
) − B ( d+ 1
2 ,
1 2 ; 1− α
2
4R2
) = ∫ α2 4R2
0
t(d−1)/2(1− t)−1/2dt
≤ 1√ 1− α24R2
∫ α2 4R2
0
t(d−1)/2dt = 2 ( α 2R )d+1 (d+ 1) √ 1− α24R2 = o ( B ( d+ 1 2 , 1 2 ))
if (α/R)d → 0, which is the case since B ( d+1 2 , 1 2 ) = Θ ( 1/ √ d )
and(α R )d = Θ(1)ddVolEd(B(R)) RdVol(Sd−1)n = Θ(1)d n → 0
for d log n. In the hyperbolic case, the “small” ball of radius α is small enough (α 1/ √ d) so that its geometry can be considered Euclidean, and thus we can apply Lemma 5 to estimate the volume of Cα(h). The “large” hyperbolic ball of radiusR in this case can be thought of as a Euclidean ball of radius∼ 12e 2R in the upper half–space model, and then we can carry out the same analysis on the Euclidean scale of the “small” radius α ball. Note that in this case(
2α
e2R
)d = Θ(1)ddvd(R)
e2Rdn ≤ Θ(1)
deR(d−1)
e2Rdn → 0 .

heading: C.3 TIME AND SPACE COMPLEXITY
text: In this section, we estimate time and space complexity. Recall that N(v) denotes the number of neighbors of an element v in G(M) and f = (n−1)VolHd (B(αM )) /VolHd (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 “N(v) satisfies N(v) ≤ 32f” is at least 1− 4 f .
Proof. Note that the random variable N(v) is upper bounded by the random variable N ′(v) having the binomial distribution Bin ( n− 1, VolHd (B(αM ))VolHd (B) ) with the expected value f . Thus, via the Chebyshev’s inequality, we obtain
P ( N(v) > 3
2 f
) ≤ P ( N ′(v) > 3
2 f
) ≤ P ( |N ′(v)− f | > f
2
) ≤ 4Var (N ′(v))
f2 ≤ 4 f .
Lemma 17. The time complexity of k steps of the graph-based NNS is O (kfd) with probability 1−O ( 1 kf ) .
Proof. We can upper bound the number of distance computations by the random variable distributed according to Bin ( k(n− 1), VolHd (B(αM ))VolHd (B) ) and proceed as in the proof of Lemma 16. Finally, note that one distance computation takes Θ(d).
Lemma 18. The probability of the event “E(G) satisfies E(G) ≤ 34fn” is 1−O ( 1 fn ) .
Proof. We mostly follow the proof of Prokhorenkova & Shekhovtsov (2020), but some modifications are needed to handle the boundary. We use Chebyshev’s inequality, so we have to estimate the variance VarE(G):
VarE(G) = E ( E(G)2 ) − (EE(G))2
= ∑
e1,e2∈(D2)
P(e1, e2 ∈ E(G))− P(e1 ∈ E(G)) · P(e2 ∈ E(G)) .
Obviously, if e1 and e2 do not share common endpoints, then P(e1, e2 ∈ E(G)) = P(e1 ∈ E(G)) · P(e2 ∈ E(G)). Also, one can see that if e1 and e2 share one element, then we also have P(e1, e2 ∈ E(G)) = P(e1 ∈ E(G)) · P(e2 ∈ E(G)). Indeed, assume that both e1 and e2 contain a common element v. Then the equality holds conditioned on the position of v since both sides of the equation are defined in terms of v-th neighborhood size.
Thus, only the terms with e1 = e2 remain in the expression: VarE(G) = ∑
e1∈(D2)
P(e1 ∈ E(G))− (P(e1 ∈ E(G)))2 ≤ EE(G) .
Finally, we get
P ( |E(G)− EE(G)| > EE(G)
2
) ≤ 4VarE(G)
(EE(G))2 ≤ 4 EE(G) .
It remains to note that EE(G) ≤ nf/2 and due to Lemma 15 we also have EE(G) = Θ(nf). From this the lemma follows.
D k-NN GRAPHS
Note that in Theorem 1 we consider undirected graphs since the condition on ρ(·, ·) is symmetric. In this section, we extend the theorem to nearest neighbor graphs. In this case, we assume that each node is connected to a fixed number of its nearest neighbors by directed edges. During graph traversal, outgoing edges are used to explore the neighborhood.
Theorem 3. Assume that d = d(n) is such that log log n d(n) log n and R = R(n) is such that eR n 1 d−1 · d−1/2 . For the exact NNS, let M be a constant s.t. M > √
2 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 c > 1, let M be a constant s.t. M > √ 4c2
3c2−1 and k = [M d]. Then, with probability
1− o(1), NNS based on the k-NN graph solves c, r-ANN for any r. In both cases, the time complexity is O ( k · n1/d ·R · (vd(R))−1/d ) ;
the space complexity is O (n · log n · k).
Proof. First, note that the space complexity is straightforward: each node has exactly k outgoing edges. Similarly, the complexity of one step is O(k · d). Thus, it remains to show that kNN-based NNS succeeds with probability 1 − o(1) and that the number of steps can be upper bounded similarly to Theorem 1. To prove this, it is sufficient to show that the distance to the k-th neighbor is sufficiently large, so that the convergence can be guaranteed by the proof of Theorem 1.
For every node v define a random variable ρk(v) to be the distance from v to its k-th nearest element. It is sufficient to show that ρk(v) ≥ M̂δ, where δ = ( dvd(R) n )1/d and M̂ satisfies the required
conditions on M in Theorem 3. For some ε > 0, let M̂ := M (1− ε). Obviously, by choosing small enough ε, we can guarantee that the required conditions are satisfied.
Note that Nr(v) — the number of elements at distance at most r from v — can be upper bounded by a random variable having the binomial distribution Bin ( n− 1, VolHd (B(r))VolHd (B) ) (the upper bound is caused by possible boundary effects). If r = M̂δ, then VolHd (B(r))VolHd (B) = M̂ d/n. Thus, N M̂δ (v) is
upper bounded by Bin ( n, M̂d/n ) .
Recall that k = [Md]. It is sufficient to show that with high probability we have N M̂δ (v) < k for all v. Using the union bound over all possible v and the Chernoff’s bound, we obtain the following:
P ( ∃ v : N
M̂δ (v) ≥ k
) ≤ n · e − ( k−M̂d) 2 2(M̂d+(k−M̂d)/3) ≤ elogn− M2d(1−o(1))
Θ(Md) → 0. as n→∞, since d log log n.

heading: E GRAPH-BASED NNS IN SPARSE REGIME
text: In this section, we prove Theorem 2. For this, we show that the elements are tightly concentrated near the boundary of the ball, and thus the convergence guarantees resemble those on the sphere.
Let us denote by ϕ(xi, xj) the angle ∠xiOxj . For the sphere, graph G(M) is constructed by connecting such pairs of elements that (Prokhorenkova & Shekhovtsov, 2020):
cosϕ(xi, xj) ≥ √ 2M log n
d . (27)
For the hyperbolic space, we connect the elements xi and xj if cosh ρ(xi, xj) ≤ cosh2R− sinh2R · √ 2M log n
d . (28)
Note that this corresponds to the elements xi and xj located on the boundary of B with ϕ(xi, xj) bounded by (27).
Recall that for c > 1 we set
αc := cosh2R− cosh(arccosh(cosh2R)/c)
sinh2R . (29)
Let us explain this choice. Below we prove that NNS in the hyperbolic space behaves similarly to those on a 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 αc taking into account the multiplicative approximation factor c. In Prokhorenkova & Shekhovtsov (2020), αc is the cosine of the angle π2c . There, π 2c is the spherical distance that is c times smaller than the distance between the elements with ϕ(xi, xj) = π/2. The hyperbolic distance D between the elements with ϕ(xi, xj) = π/2 located on the boundary of B satisfies the following equality:
coshD = cosh2R, i.e., D = arccosh(cosh2R) .
Then, we need to compute cosϕ(xi, xj) if ρ(xi, xj) = D/c. This follows from the hyperbolic law of cosines:
cosϕ(xi, xj) = cosh2(R)− cosh(D/c)
sinh2(R) ,
which is equal to αc in 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− o(1) all n elements are located within a shell of width Θ (
logn d ) near the boundary of the ball B.
Proof. According to (3), we have VolHd(B(R− ε))
VolHd(B(R)) = Θ
( e−ε(d−1) ) .
Let ε = 1d−1 (log n+ ϕ), where ϕ = ϕ(n) is any function s.t. ϕ→∞ as n→∞. Then, VolHd(B(R− ε))
VolHd(B(R)) = Θ
( e− logn−ϕ ) = o(1/n) .
From this the lemma follows.
Lemma 20. If two elements xi, xj satisfy (27) with constant M + ε for some ε > 0, then with probability 1− o(1) they satisfy (28) with constant M .
Proof. Let the distances from xi and xj to the center of the ball B be ri and rj , respectively. From Lemma 19, ri and rj are equal to R−Θ ( logn d ) . Using the hyperbolic law of cosines, we get
cosh ρ(xi, xj) = cosh ri cosh rj − sinh ri sinh rj cosϕ(xi, xj)
≤ cosh ri cosh rj − sinh ri sinh rj
√ 2M log n
d = cosh2(R−Θ(log n/d))− sinh2(R−Θ(log n/d)) √ 2M log n
d .
It is sufficient to show that cosh2(R−Θ(log n/d))− sinh2(R−Θ(log n/d)) √ 2M log n
d ≥ cosh2R− sinh2R · √ 2(M + ε) log n
d .
Note that cosh(R−Θ(log n/d)) = e R
2 (1 + Θ(log n/d)). The same holds for sinh(R−Θ(log n/d)). Therefore, we need
e2R
4 (1 + Θ(log n/d))
( 1− √ 2M log n
d
) ≥ e 2R
4
( 1 + Θ ( e−2R ))( 1− √ 2(M + ε) log n
d
) .
Now we divide the left hand side by the right hand side and obtain( 1− √ 2M logn
d ) (
1− √
2(M+ε) logn d
) (1 + Θ(log n/d) + Θ (e−2R))
= ( 1 + (√ 2(M + ε) log n d − √ 2M log n d )( 1 + Θ (√ log n/d )))( 1 + Θ(log n/d) + Θ ( e−2R
)) = ( 1 + Ω( √ log n/d) ) ( 1 + Θ(log n/d) + Θ ( e−2R )) .
From this the lemma follows, since √ log n/d log n/d and √ log n/d e−2R.
Let us choose such small ε > 0 that the required condition on 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, we 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 the condition
cosϕ ≥ √ 2S log n
d
According to Lemma 20, such constants are negligibly affected by deviations from the boundary, and thus we can directly follow the proof of Prokhorenkova & Shekhovtsov (2020) to obtain the convergence guarantees and complexity. Indeed, all requirements for the constants in the proof are strict, and thus a sufficiently small ε can be chosen such that they are still satisfied.

heading: F EXPERIMENTS
text: Implementation Our implementation supplements the submission.
Best-first search In the main text, for the synthetic experiments, we use the greedy search. However, in graph-based NNS algorithms, the greedy search is often replaced by the best-first search (a.k.a. beam search). In this case, instead of keeping track of only the best candidate, we maintain 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 efSearch.
Hyperparameters Recall that to plot Figure 3, we vary the graph degree to control the complexity and accuracy of NNS. In Figures 1 and 2, we use the best-first search, so we vary the parameter efSearch and fix the graph degree. In this case, we tuneM and efConstruction HNSW hyperparameters, which are responsible for the graph degree and quality of the graph construction, respectively. For both GloVe and Poincaré GloVe databases, we get M=10 and efConstruction=300. For other datasets, we get M=8. For NSG, the degree is controlled by the parameter R, and the optimal degree is R = 2M .
Spherical Shell implementation As a baseline, we implement Spherical Shell proposed by Wu & Charikar (2020). As in the original paper, we split the elements into 25 bands such that wi−1 ≤
1 1−‖x‖2 ≤ w i. To achieve this, we take w = 1.05. For each band, we construct LSH with 50 tables. 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 to achieve better results). When searching for the nearest neighbor for a query q, we compute the nearest neighbors within l bands closest to q and take the best one according to the hyperbolic distance. The number of bands l is varied from 1 to 10, thus giving the curve on Figure 1.
Additional experiments on real datasets Figures 8 and 9 and compare the algorithms on the recommendation dataset with d = 10 from Shevkunov & Prokhorenkova (2021) and the Poincaré GloVe embeddings trained for d = 10 using the source code provided by the authors (Tifrea et al., 2018). We can see that HNSW and NSG have similar performance on Poincaré GloVe, while HNSW outperforms NSG on the recommendation dataset. In contrast, Spherical Shell needs a significantly larger number of distance computations. On the recommendation dataset, this can be explained by the fact that this data significantly differs from the Poincaré GloVe: the learned vector norms are much larger. Because of this, we either have annuli of large width (significant approximation error) or many annuli (increased total complexity).
Then, we compare the efficiency of NNS in Euclidean and hyperbolic spaces. For this, we embed two datasets discussed above to Euclidean and hyperbolic spaces and perform NNS based on HNSW for the same set of queries. Figure 9 shows that hyperbolic NNS is more efficient.
Additional synthetic experiments Figure 10 is similar to Figure 3, but now we use the best-first search instead of the greedy search. We see that the conclusions are the same.

Review summaries:
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.

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. 

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.

This paper looks into graph-based algorithms for nearest neighbor search (NNS) problem in the hyperbolic space.  Theoretically, the authors derived the time and space complexity of graph-based NNS under some assumptions (data uniformed distributed in the ball, low dimensional dense), and in some cases, graph-based NNS has lower time complexity in the hyperbolic space.   Practically, the authors apply the methodology to Poincar{/'e} Glove word embeddings, where it outperforms some existing baselines.