Year: 2021

Abstract:
Dimensionality reduction (DR) and visualization of high-dimensional data is of theoretical and practical value in machine learning and related fields. In theory, there exists an intriguing, non-intuitive discrepancy between the geometry of highdimensional space and low-dimensional space. Based on this discrepancy, we propose a novel DR and visualization method called Space-based Manifold Approximation and Projection (SpaceMAP). Our method establishes a quantitative space transformation to address the “crowding problem” in DR. With the proposed equivalent extended distance (EED) and function distortion (FD) theory, we are able to match the capacity of high-dimensional and low-dimensional space in a principled manner. To handle complex high-dimensional data with different manifold properties, SpaceMAP makes distinctions between the near field, middle field, and far field of data distribution in a data-specific, hierarchical manner. We evaluated SpaceMAP on a range of artificial and real datasets with different manifold properties, and demonstrated its excellent performance in comparison with classical and state-of-the-art DR methods. In addition, the concept of space expansion provides a generic framework for understanding nonlinear DR methods including t-distributed Stochastic Neighbor Embedding (t-SNE) and Uniform Manifold Approximation and Projection (UMAP).

text: Dimensionality reduction (DR) and visualization of high-dimensional data is of theoretical and practical value in machine learning and related fields. In theory, there exists an intriguing, non-intuitive discrepancy between the geometry of highdimensional space and low-dimensional space. Based on this discrepancy, we propose a novel DR and visualization method called Space-based Manifold Approximation and Projection (SpaceMAP). Our method establishes a quantitative space transformation to address the “crowding problem” in DR. With the proposed equivalent extended distance (EED) and function distortion (FD) theory, we are able to match the capacity of high-dimensional and low-dimensional space in a principled manner. To handle complex high-dimensional data with different manifold properties, SpaceMAP makes distinctions between the near field, middle field, and far field of data distribution in a data-specific, hierarchical manner. We evaluated SpaceMAP on a range of artificial and real datasets with different manifold properties, and demonstrated its excellent performance in comparison with classical and state-of-the-art DR methods. In addition, the concept of space expansion provides a generic framework for understanding nonlinear DR methods including t-distributed Stochastic Neighbor Embedding (t-SNE) and Uniform Manifold Approximation and Projection (UMAP).

heading: 1 INTRODUCTION
text: Real-world data, including images, videos, genetic expressions, natural languages, or financial statistics, usually have a high dimensionality. The intrinsic dimensionality of these data, however, is typically much lower than its ambient dimension, which property is recognized as an important underlying reason for modern machine learning to work (Levina & Bickel, 2004; Pope et al., 2021; Wright & Ma, 2021). To capture useful information from high-dimensional data, dimensionality reduction (DR) is of both theoretical and practical value.
DR is essential for data visualization. A space with a dimensionality higher than 3, however, is already beyond our accustomed way of observing data, and our intuition in 2-dimensional or 3-dimensional space may not apply. High-dimensional space is not a trivial extension of lowdimensional space; theoretical research on high-dimensional geometry and statistics revealed a number of intriguing, non-intuitive phenomena in high-dimensional space (Giraud, 2021). Imagine a hyper-sphere with a radius r in a d-dimensional Euclidean space whose central point is at the origin. Consider a “crust” of the d-dimensional hyper-sphere, which is between the surfaces of this hypersphere and a slightly smaller concentric hyper-sphere with radius (1−ϵ)r, where ϵ is small (Figure 1 a). The ratio of the volume of the “crust” Cd(r) to the hyper-sphere is Vd(r) is
Cd(r) Vd(r) = 1− (1−ϵ)d. Take ϵ = 0.01, it is easy to show that when d is small, the ratio is tiny (as our intuition goes), however this ratio grows exponentially fast to near 100% with the increase of dimensionality, as illustrated in figure 1 a-b. The volume of a high-dimensional hyper-sphere is therefore counter-intuitively concentrated on a crust (1 c). Such concentration explains the “crowding problem” of DR (van der Maaten & Hinton, 2008): a faithful preservation of distances in high-dimensional space would lead to crowded data points.
t-distributed Stochastic Neighbor Embedding (t-SNE) and Uniform Manifold Approximation and Projection (UMAP) are among the most established DR methods today, both of which mitigate this crowding problem by modeling the low-dimensional similarity measure with a longer-tail distribution than high-dimensional similarity measure (e.g. t distribution vs. Gaussian in the case of t-SNE). Such a disparity in similarity measure amounts to a distortion of distance between two spaces, but in a highly implicit manner. Both methods perform well empirically, but the underlying distortion of distance measure in two spaces cannot be analytically expressed or validated. Furthermore, the implicity of distance transformation deters us from imposing priors in data if there is any (e.g. a Swiss Roll has an intrinsic dimensionality of 2).
Another important property of real-world high-dimensional data is that they often exhibit a hierarchical structure (sub-manifolds on large manifolds), governed by the underlying generative models. Such hierarchy demands different treatment of data points by DR at different relative position. The state-of-the-art DR methods, such as UMAP (McInnes et al., 2018) and Barnes-Hut t-SNE (van der Maaten, 2014), commonly consider on a selected neighborhood (as a hyper-parameter) while discarding the far field beyond it. Isomap (Balasubramanian et al., 2002), on the other hand, taking both near and far field into account by calculating distances on a connected graph. t-SNE and UMAP works well on data of disjoint manifolds such as MNIST, while Isomap works well on data of continuous manifold such as Swiss roll. However, it is generally difficult for one method to succeed in both disjoint and continuous data manifolds.
In this paper, we seek to develop a novel DR method that is based on the following two key ideas, and strive to address the two aforementioned issues:
• Space Expansion: Matching the “capacity” in high-dimensional and low-dimensional space, by explicit, quantitative transformation of distance measure;
• Hierarchical Manifold Approximation: Data-specific, hierarchical modeling of similarities in high-dimensional data, to accommodate both disjoint and continuous data manifolds.

heading: 2 RELATED WORK
text: Over the past decades, there have been active development of DR methods, which can be roughly categorized into global and local methods. The most well-known global method is principal component analysis (PCA) (Jolliffe, 2014), which finds a low number of directions that accounts for most variations. While PCA is linear, Laplacian eigenmaps (Belkin & Niyogi, 2001; 2003) and multidimensional scaling (MDS) (Buja et al., 2008) are nonlinear global methods. Local methods, including Isomap, Locally Linear Embedding (LLE) (Roweis, 2000), stochastic neighbor embedding (SNE) (Hinton & Roweis, 2003), and maximum variance unfolding (MVU) (Weinberger & Saul, 2006), focus on preserving local structure in data. While outperforming global methods on nonlinear datasets, local methods generally suffer from poor scalability, low speed, and stochasticity.
In 2008, t-distributed stochastic neighbor embedding (t-SNE) (van der Maaten & Hinton, 2008), a variant of SNE, was proposed and later became one of the most popular DR methods in research community. t-SNE alleviates the “crowding problem” by assuming t-distribution in low-dimensional space (in contrast to Gaussian distribution in the high-dimensional space). t-SNE is followed up by a number of prominent work to improve its scalability and speed, including among others Barnes-Hut t-SNE (BH t-SNE) (van der Maaten, 2014), fast Fourier-transform-accelerated interpolation-based t-SNE (FIt-SNE) (Linderman et al., 2019), and parametric t-SNE (ptSNE) (van der Maaten, 2009).
Recently, uniform manifold approximation and projection McInnes et al. (2018) (UMAP) was proposed, which shows competitive performance to t-SNE. UMAP is grounded in the mathematical theories of Riemannian geometry and algebraic topology. It computes local neighbor graph as a fuzzy simplicial set, which glues together the high-dimensional sparse data and differentiates local and global topology. UMAP further incorporates a number efficient algorithms such as approximated nearest neighbor and stochastic gradient descent (SGD) to improve speed and scalability. TriMAP (Amid & Warmuth, 2019) was recently proposed, which uses a triplet loss instead of pairwise. UMAP and TriMAP are reported to better preserve the global structure than t-SNE McInnes et al. (2018); Amid & Warmuth (2019).
We note that a different definition of “distance” in the low-dimensional space than in the highdimensional space is core to these successful DR algorithms. In t-SNE, with a heavier tail, tdistribution implicitly expands the low dimensional space distance metrics, to allow more space for data points to be arranged. Likewise, the definition of distances of UMAP in low-dimensional space is much more heavy-tailed (inverse of polynomial) than in high-dimensional space (exponential), which also leads to implicit distortion of space.

heading: 3 METHOD

heading: 3.1 SPACE EXPANSION
text: High-dimensional space, irrespective of the distances defined, possesses exponentially higher capacity to express data than low-dimensional space. Here we define “capacity” as a measure of space volume to accommodate data points. Our intuition is therefore to expand the low-dimensional space to make up for this space capacity lost due to DR. To transfer the high-dimensional geometry into a low-dimensional one, we introduce the concept of equivalent extended distance (EED) in Section 3.1.1 and function distortion (FD) in Section 3.1.2.

heading: 3.1.1 EQUIVALENT EXTENDED DISTANCE (EED)
text: We first define space capacity to quantitatively calculate the amount of distortion needed to match low-dimensional space to high-dimensional space. Definition 3.1 (Space Capacity). Let Rij = l(xi,xj) ∈ R be the distance between data point xi and xj in the D-dimensional space. The space capacity VD(Rij) from point i to point j is defined as the volume a D-dimensional ball with a radius Rij .
In Euclidean space, the capacity VD(Rij) is simply the volume of a D-dimensional hyper-sphere SD(Rij):
VD(Rij) = SD(Rij) = πD/2
Γ(D/2 + 1) RDij (1)
As high-dimensional space has higher capacity than low-dimensional space, to preserve the capacity of the high-dimensional space in the low-dimensional space, the equivalent distance in the lowdimensional space naturally extends, hence Equivalent Extended Distance (EED): Definition 3.2 (Equivalent Extended Distance (EED)). Let Rij = l(xi,xj) ∈ R be the distance between data point xi and xj in the D-dimensional space. The equivalent extended distance (EED) R̃ij,D→d is defined as the equivalent distance between xi and xj in d-dimensional space which can reach the same Space Capacity:
Vd(R̃ij,D→d) = VD(Rij) (2) Example 3.1 (2-dimensional EED in Euclidean space). Consider a D-dimensional Euclidean space, the distance between two points i and j is Rij = ∥xi − xj∥. The 2-dimensional EED of Rij is:
R̃ij,D→2 = √ SD(Rij) π = αR D/2 ij where α = π(D−2)/4√ Γ(D/2+1) and Γ is the gamma function.
Example 3.1 shows that when embedding D-dimensional Euclidean space into d-dimensional space, EED can be expressed in a generic form of R̃ij,D→d = αRβ where β = Dd and α is a constant determined by D and d.
In the following, we present prior theory of intrinsic dimension by the maximum likelihood estimation (MLE) method by Levina & Bickel (2004), and show that our proposed EED fits in this classical framework. Theorem 3.1 (MLE of the intrinsic dimension (Levina & Bickel, 2004)). Let Rik ∈ R be the Euclidean distance between point i and its k-th nearest neighbor. Assume the distribution of the data points in the small sphere Si(R) is uniform. The maximum likelihood estimation (MLE) of the intrinsic dimension of the data around point i is:
d̂i(Rik) =  1 k − 1 k−1∑ j=1 log Rik Rij −1 (3) The MLE method provides a way to estimate the intrinsic dimension at point i in its k neighborhood based on the distribution of distances.
By applying EED transformation to a space with intrinsic dimension D, the following Lemma holds: Lemma 3.2 (Transformation of the intrinsic dimension by applying EED). ∀Rij = l(xi,xj) ∈ R, if the MLE of the intrinsic dimension of the high-dimensional dataset around point i is d̂i(Rij) = D, then the MLE of the intrinsic dimension after applying EED is d̂i(R̃ij,D→d) = d.
Proof. By replacing Rij with R̃ij,D→d = αRD/dij into Equation (3), we have
d̂i(R̃ik,D→d) =  1 k − 1 k−1∑ j=1 log αR D/d ik αR D/d ij −1 =  1 k − 1 k−1∑ j=1 D d log Rik Rij −1 = d D d̂i(Rik) = d
(4)
Specifically, when d = 2 for visualization purposes, the MLE of the intrinsic dimension of the expanded space will be exactly 2. Essentially, the validity of this statement arises from the proposed EED transformation R̃ij,D→d = αR D d , where the exponential form of Dd transforms the intrinsic dimension from D to d, based on the MLE formula (3) where the distances are taken logarithmic. In the following sections, the distance Rij between point i and point j is described as l(xi,xj), which is suitable for several different distance metrics.

heading: 3.1.2 FUNCTION DISTORTION (FD)
text: Function distortion (FD) is the implementation to realize EED between high-dimensional and lowdimensional space similarity measures during optimization. Given that EED is well defined as
R̃ij,D→d = αRβ , FD between spaces can be explicitly computed. Figure 2 illustrates how FD transforms the similarity functions (Pj|i and Qij) in high-dimensional and low-dimensional spaces. A much heavier tail can be observed in the low-dimensional space similarity measure, arising from EED.

heading: 3.2 HIERARCHICAL MANIFOLD APPROXIMATION
text: Another fundamental assumption of SpaceMAP is that real world data often lie on a complex manifold, of a hierarchical structure (Figure 3 a). In SpaceMAP, we divided the high-dimensional space with respect to each data point i into near field Si,near, middle field Si,middle, and far field Si,far. Such a definition of neighborhood is point-specific, implying that we can treatment different points differently, depending on their relative location on the manifold. An analogue can be made to UMAP, which defines a different distance metric for each data point depending on its nearest neighbor. Similarly, for a generic formulation, the determination of the fields is based on K-nearest neighbors in SpaceMAP:
Si,near = {xj ∣∣ l(xi,xj) ≤ l(xi,xk1)}, k1 = nnear (5)
Si,middle = {xj ∣∣ l(xi,xk1) < l(xi,xj) ≤ l(xi,xk2)}, k2 = nnear + nmiddle (6)
Si,far = {xj ∣∣ l(xi,xj) > l(xi,xk2)} (7)
where nnear is the number of the nearest neighbors in near field, and nmiddle is the number of nearest neighbors in the middle field. Like UMAP, we can use a fixed number to define the neighborhood by empirically setting nnear = 20, nmiddle = 50, or setting the number based on our prior knowledge on data. Additional experiments in Appendix (Figure 10) shows that the results are not particularly sensitive to these two parameters.
To describe hierarchical manifoldM, two intrinsic dimensionalities, namely, dlocal(i) of the near field of point i, and dglobal of the middle and far field of point i, can be calculated based on the MLE method with nnear and nmiddle set. (Alternatively, dlocal or dglobal can also be set manually with prior knowledge of data, e.g. the dlocal and dglobal of a Swill Roll dataset are both 2. However in this work, for simplicity, we used nnear and nmiddle to calculate the two dimensionalities.)
Base on dglobal and dlocal, the conditional similarities of the data points Pj|i are defined as:
Pj|i =  exp ( −( l(xi,xj)αi ) 2dlocal,i d ) , xj ∈ Snear exp ( − (l(xi,xj)−l(xi,xk1 )+ √ − ln η) 2 σi ) , xj ∈ Smiddle
0, xj ∈ Sfar
(8)
where αi, d and dlocal denotes FD in the near field, η ∈ (0, 1) is a constant representing Pk1|i at the border of near field and middle field. In Appendix (Figure 11) we tested a range of η values and showed the choice of its value is not critical to the final results. σi is the normalization factor of the middle field Smiddle defined in the similar way as in UMAP (McInnes et al., 2018):
k2∑ j=k1+1 Pj|i = η log(nmiddle) (9)
The operation in equation amounts to hierarchical space expansion in the near field and middle field. The definition is in a large part for the ease of computation, as by modeling P instead of Q, we keep the expression of Q as simple as possible for better differentiality during optimization.
The resulting hierarchical similarity function is illustrated in Figure 3, where the computation of Pj|i in near field, middle field, and far field are shown for SpaceMAP (b), UMAP (c), and t-SNE (c), respectively. It can be seen from the figure that t-SNE makes no distinction between fields, with a uniform Gaussian function, while UMAP differentiates three fields, but with a uniform profile for near field (1 nearest neighbor). In comparison, SpaceMAP has a subtle perception of both near and middle fields.
To symmetrise the conditional similarity Pj|i and Pi|j into a symmetric metric Pij , we use the average between the two: Pij = Pj|i+Pi|j 2 . We next define the the pairwise similarities in the low-dimensional space:
Qij = exp
( −(∥yi − yj∥
α )
2d dglobal ) (10)
Where α, d and dglobal denotes FD in the middle field. Figure 2.a shows the exact effect of our method to model Pj|i and Qij , where the high-dimensional neighbors of point i (blue points on Pj|i function) are distorted to match the pattern of geometry in low-dimensional space during optimization, which is illustrated in the next section.

heading: 3.3 OPTIMIZATION PIPELINE
text: The loss function of SpaceMAP is defined in a similar way as in UMAP:
C = L(Pij∥Qij) = ∑ i ∑ j [ Pij log Pij Qij + (1− Pij) log 1− Pij 1−Qij ] (11)
where the first term is the KL divergence between two probability distributions, and the second term generates the repulsive force between point pairs, contributing to the global structure preservation. For stochastic gradient descent, the derivative of the loss with respect to the coordinates of each point in low-dimensional space ∂C∂yi is calculated and divided into two parts during iteration, which
can be seen as the attractive force Fij,attractive and the repulsive force Fij,repulsive between point pairs:
Fij,attractive = − [
2d
dglobalα2d/dglobal ∥yi − yj∥
( 2ddglobal −2)
Pij ] (yi − yj) (12)
Fij,repulsive =
[ 2d
dglobalα2d/dglobal Qij(∥yi − yj∥) 1−Qij(∥yi − yj∥) ∥yi − yj∥ ( 2ddglobal −2)
(1− Pij) ] (yi − yj)
(13)
In the implementation, the neighbors to generate the forces can be chosen as the full batch or stochastically (therefore stochastic gradient descent, SGD) to achieve scalability of SpaceMAP to large datasets. The overall algorithm of SpaceMAP is describe in Appendix A.1 Algorithm 1 followed by the detailed functions.

heading: 4 EXPERIMENTS AND RESULTS

heading: 4.1 DATASETS AND EVALUATION METRICS
text: We applied the proposed SpaceMAP to a variety of datasets and computed quantitative metrics to evaluate the performance of DR. The method is benchmarked by other classical or state-of-the-art methods including PCA, Laplacian Eigenmaps, t-SNE, and UMAP.
We tested on a large range of high-dimensional datasets, including the standard MNIST (LeCun, 1998), Fashion-MNIST (Xiao et al., 2017), Swiss Roll (Van der Maaten et al., 2007) (Here we artificially created a hole on the Swiss Roll to challenge the DR methods if they can preserve the local property on a continuous manifold), COIL-20 (Nene et al., 1996), RNA-seq (Tasic et al., 2018), and an experimental cardiac MRI dataset from three different vendors. Examples of cardiac MRI are given in Fig. 14. The details of the chosen datasets are in Appendix A.6. Here the original data is simply vectorized and taken as input of DR. We also tested all methods on the GoogleNews Word2Vec 3 Million dataset (Mikolov et al., 2013). For quantitative evaluation, we computed the 20-fold cross-validated k-nearest neighbor classifier accuracy (KNN accuracy), trustworthiness, continuity, Shepard goodness, and normalized stress to evaluate both the local and global structure preservation of the datasets (Espadoto et al., 2021; Nonato & Aupetit, 2019). KNN accuracy measures the local structure preservation along different neighborhood scale k. Trustworthiness and continuity evaluate the local pattern of the embedding by calculating the true neighbor rate and the missing neighbor rate. The Shepard goodness and the normalized stress are two measurements of the goodness in global structure preservation. The detailed introduction of these evaluation metrics is in Appendix A.7.

heading: 4.2 QUALITATIVE AND QUANTITATIVE RESULTS
text: We present the visualization results of SpaceMAP in Figure 4, along with PCA, Laplacian Eigenmap, t-SNE, and UMAP. It can be seen that SpaceMAP nicely preserved the structures of the datasets on both local and global scale, for real-world datasets with disjoint manifolds (MNIST, FashionMNIST), as well as for synthetic data of continuous manifold (row 3: Swiss roll with a hole). The space extension from dimensionality 3 to 2 nicely preserves the continuous manifold, while for tSNE and UMAP the degree of extension is more difficult to control, resulting in artificial clusters. Figure 7 shows SpaceMAP DR results of GoogleNews Word2Vec 3 million data, in comparison with UMAP. More distinctive clusters are observed in the SpaceMAP result, while a zoomed-in view clearly shows the natural clustering of geographical semantics. Again the improvement can be attributed to the strategy to explicitly expand the low-dimensional space, as in UMAP (or t-SNE) the extent of expansion is difficult to calculate or control.
We further compare the quantitative measure of DR performance of all DR methods using the metrics described before. Figure 5 and Table 1 shows the superior, or non-inferior performance of SpaceMAP compared to the classical and state-of-the-art methods in most datasets. As the optimization pipeline resembles that of UMAP, the computation time of SpaceMAP is comparable to UMAP.

heading: 5 DISCUSSION AND CONCLUSION
text: We propose a new DR method called SpaceMAP, which, in principle, can map data of any dimensionality onto a 2-dimensional space for visualization with the calculated space expansion. Different from established methods such as t-SNE or UMAP that perform implicit transformation of distances, we analytically derived a quantitative EED transformation of distances between high-dimensional space and low-dimensional spaces. We further show that the EED transformation fits in the classical framework of MLE of intrinsic dimension, effectively altering the intrinsic dimension thereby realizing low-dimensional mapping.
We argue that all successful DR methods, including among others t-SNE and UMAP, make use of the rationale of space expansion to enable data visualization in a space of drastically reduced dimension. However, previous methods did such transformations in a highly implicit manner, with the rules concealed in the self-defined similarity measure (e.g. t-distribution in t-SNE or inverse of
polynomial in UMAP, with different parameters). Despite their empirical success, we posit that an analytical form of distance transformation is desirable to deal with situations where we would like to take more control of the DR results or impose prior knowledge for DR.
SpaceMAP further differentiates different range of neighborhoods to model the hierarchical structure existent in many real-world datasets. SpaceMAP is generic and has a limited number of hyperparameters, with the most important ones related to the selection of number of nearest neighbors in the near field and middle field. We observed that the final results are not particularly sensitive to the selection of these parameters (Appendix Figure 10).
In conclusion, we have proposed a new DR method, SpaceMAP, which is based on a principled way to explicitly transform distances in high- and low-dimensional spaces, and models the hierarchical structure of data based on the intrinsic dimension of local and global manifolds. Our experiments on a diverse range of datasets demonstrated its excellent performance in comparison with other state-of-the-art DR methods.

heading: A APPENDIX
text: A.1 SPACEMAP PSEUDO CODE
Algorithm 1 SpaceMAP algorithm function SPACEMAP(X,nnear, nmiddle, near field range, η, n epochs, learning rate)
knn dist← NearestNeighbor(X,nnear, nmiddle) dlocal, dmiddle ← MLEIntrinsicDimension(knn dist, nnear, nmiddle) for xi ∈ X do ▷
α′[i]← FDScalingFactor(knn dist[i, nnear], η, dlocal[i], 2) end for dglobal ← 1N ∑N i dmiddle[i] α← FDScalingFactor(near field range, dglobal) Pij ← HierarchicalManifoldP(knn dist, nnear, nmiddle, dlocal, dglobal, α′) Y ← InitializeEmbedding(X) Y ← OptimizeEmbedding(Y, Pij , dlocal, dglobal, α, learning rate, n epochs) return Y
end function
Algorithm 2 Maximum likelihood estimation (MLE) of the intrinsic dimension function MLEINTRINSICDIMENSION(knn dist, nnear, nmiddle)
k1 ← nnear k2 ← nnear + nmiddle for i← 1, ...,n-data do
Ri,k1 ← knn dist[i, k1] Ri,k2 ← knn dist[i, k2] d̂near[i]← ( 1k1−1 ∑k1−1 j=1 log Ri,k1 Ri,j )−1
d̂middle[i]← ( 1k2−1 ∑k2−1 j=1 log Ri,k2 Ri,j )−1
end for return d̂near, d̂middle
end function
Algorithm 3 Calculation of the FD scaling factor function FDSCALINGFACTOR(r, η,D, d)
β ← Dd α← r
(− ln η)β/2 ▷ α is chosen to satisfy F̃D→d(r) = η or f̃d→D(r) = η return α
end function
Algorithm 4 Hierarchical Manifold Approximation in high-dimensional space (Pij calculation) function HIERARCHICALMANIFOLDP(knn dist, nnear, nmiddle, dlocal, dglobal, α′)
for i← 1, ...,n-data do for rij ∈ knn dist[i] do ▷ knn dist is arranged in ascending order
if j ≤ nnear then ▷ Pj|i in near field Pj|i ← exp (−( rij α′[i] ) dlocal) else if j ≤ nnear + nmiddle then ▷ Pj|i in middle field r ← rij − knn dist[i, nnear]
Binary search for σi such that ∑nmiddle j=nnear+1 e (− (r− √ − ln γ)2 σi ) = η log2(nmiddle) Pj|i ← exp (− r2ij σi
) else
Pj|i ← 0 end if
end for end for for all Pj|i do
Pij = Pj|i+Pi|j
2 ▷ Symmetrization of the similarities end for return Pij
end function
A.2 MORE SPACEMAP: HIGH-DIMENSIONAL DATA VISUALIZATION
A.3 VISUALIZATION OF LARGE DATASETS
A.4 OTHER EXPERIMENTS
A.5 MNIST VISUALIZATION
A.6 IMPLEMENTATION
A.7 INTRODUCTION OF THE METRICS

Review summaries:
The paper presents a new solution to dimensionality reduction and data visualization. They define an explicit extension of the pairwise distances in the lower dimensional space, the equivalent extended distance (EED), which is proportional to the reduction in volume when going from a high dimensional space to a lower-dimensional space, This helps to avoid the crowding problem known from T-SNE, UMAP, etc. and could provide a better understanding of dimensionality reduction methods in general. In addition, they define a distortion framework that allows more efficient implementation of the EED. Finally, they introduce a hierarchical scheme for manifold approximation, where instead of splitting the problem into ambient space and data manifold, they add a third layer, the near field. This is similar to UMAP, but they use a Gaussian function instead of a uniform for the near field. Experiments are thorough and the visualizations behave as expected, with the data being more spread out compared to t-sne and UMAP. A quantitative analysis using recently proposed metrics is also provided.

This work studies dimensionality reduction and visualization of high-dimensional data. The idea is to construct two graphs in the original high-dimensional space and the low-dimensional space, respectively, based on space expansion and hierarchical manifold approximation. Space expansion is to map the distance in high-dimensional space to an equivalent extended distance (EED) in low-dimensional space such that the volumes of the two (hyper-)spheres in the two spaces are equal. Hierarchical manifold approximation divides the points into near field, middle field, and far field, and assigns EED based similarity for points in the near field. Then a problem minimizing the sum of a KL divergence and a repulsive force term is solved by SGD to determine the projected coordinates. In numerical experiments, the effectiveness of the proposed method is demonstrated by comparing with some baseline methods on synthetic and real-world datasets.

This paper proposes Space-based Manifold Approximation and Projection (SpaceMAP) method to solve two existing issues in dimensionality reduction task: (1) capacity matching between high-dimensional data space and low-dimensional visualization space. (2) complexity in various manifold properties. To address these issues, SpaceMAP proposes two ideas: (1) space expansion (Section 3.2): inferring equivalent extended distance (EED) (Definition 3.2) for low-dimensional space based on volume matching and introducing function distortion (FD) (Section 3.2.2) to transform the similarity functions in high-dimensional and low-dimensional space; (2) hierarchical manifold approximation (Section 3.3): making distinctions between the near field, middle field, and far field of data distribution in a data-specific hierarchical manner. SpaceMAP achieves competitive performance on a diversity of datasets.

This paper suggests what it calls a novel dimensionality reduction and data visualization method (SpaceMAP), but perhaps it would be more precise to say that they suggest two modifications to UMAP. One modification is theoretically motivated low-dimensional similarity kernel (that depends on the estimate of the input dimensionality). Another modification is multi-scale high-dimensional similarity kernel. The authors argue that their method performs better than existing methods on a variety of different datasets.  The first part about theoretically grounded low-dimensional similarity kernel (which seems to be the main focus of the paper) I found interesting. However, I feel that combining two very different UMAP modifications together made the paper weaker because it is not clear what effect do they have on their own. I'd much rather see more experiments that really elucidate the "space expansion" idea and effect. Also, the paper is missing a lot of relevant context/citations. Overall I feel that the work has potential but the paper is not really ready yet. I am giving a lower-borderline score.