Inductive Global and Local Manifold Approximation and Projection
Authors: Jungeum Kim
Xiao Wang
Venue: Accepted by TMLR ()

Abstract: Nonlinear dimensional reduction with the manifold assumption, often called manifold learning, has proven its usefulness in a wide range of high-dimensional data analysis. The significant impact of t-SNE and UMAP has catalyzed intense research interest, seeking further innovations toward visualizing not only the local but also the global structure information of the data. Moreover, there have been consistent efforts toward generalizable dimensional reduction that handles unseen data. In this paper, we first propose GLoMAP, a novel manifold learning method for dimensional reduction and high-dimensional data visualization. GLoMAP preserves locally and globally meaningful distance estimates and displays a progression from global to local formation during the course of optimization. Furthermore, we extend GLoMAP to its inductive version, iGLoMAP, which utilizes a deep neural network to map data to its lower-dimensional representation. This allows iGLoMAP to provide lower-dimensional embeddings for unseen points without needing to re-train the algorithm. iGLoMAP is also well-suited for mini-batch learning, enabling large-scale, accelerated gradient calculations. We have successfully applied both GLoMAP and iGLoMAP to the simulated and real-data settings, with competitive experiments against the state-of-the-art methods.

Published in Transactions on Machine Learning Research (12/2024)
Inductive Global and Local Manifold Approximation and Projection
J Jungeum Kim
Lungeum.kim@ccicaaoooool
Booth School of Business University of Chicago
Xiao Wang
vangriao@yurdtu edu
Statistics Department
Purduc University
Reviewed on OpenReview: https: // openreview. net/ forum? td=p9hhaeeall@@hhttteee
Abstract
Nonlinear dimensional reduction with the manifold assumption, often called manifold learn- ing, has proven its usefulness in wide range of high-dimensional data analysis. The signif- icant impact of t-SNE and UMAP has catalyzed intense research interest, seeking further innovations toward visualizing not only the local but also the global structure information of the data. Moreover, there have been consistent efforts toward genoralizable dimensional reduction that handles unseen data. this paper, we first propose GLoMAP, a novel man- ifold learning method for dimensional reduction and high-dimensional data visualization. GLoMAP preserves locally and globally meaningful distance estimates and displays pro- gression from global to local formation during the course of optimization. Furthermore, we extend GLoMAP to its inductive version, iGLoMAP, which utilizes deep neural net- work to map data to its dimer-dilansional representation. This allows iGLoMAP to provide dower-dimensional embeddings for unseen points without needing to re-train the algorithm. iGLoMAP also well-suited for mini-batch learning, enabling large-scale, accelerated gra- dient caleulations. We have successfully applied both GLoMAP and iGLoMAP to the simulated and real-data settings, with competitive experiments against the state-of-the-art methods.
Keywords: Data visualization, deep neural networks, nonlinear dimensional reduction, inductive algorithm
1 Introduction
Data visualization, which belongs to exploratory data analysis, has been promoted by John Tukey since the 1970s as a critical component in scientific research (Tukey 1977). However, visualizing high-dimensional data is a challenging task. The lack of visibility in the high-dinensional space gives less intuition about what assumptions would be necessary for compactly presenting the data on the reduced dimension. A common assumption that can be made without specific knowledge of the high-dimensional data the manifold as- sumption. It assumes that the data are distributed on low-dimensional manifold within high-dimensional space. Nonlinear dimensional reduction (DR) with the manifold assumption, often called manifold learning, has proven its usefulness in a wide range of digensinnn data analysis (Meilä & Zhang 2023 Various rescarch efforts have been made to develop DR tools for data visualization, and several Icading algorithms include MDS [Cox & Cox 2008), Isomap (Tenenbaun et. al. 2000),, (-SNE (Van der Maaten & Hinton 2008), UMAP (Meinnes et al. 2018), PHATE (Moon et al.) 2017). PacMAP (Wang et al.) (021), and many others. It is not uncommon to perform further statistical analysis on the reduced dimensional data, including visualized data, through methods such as regression (Cheng Wu. 2013), functional data analysis (Dai &
Müller 2018), classification (Belkina et. al. 2019). and generative models (Qiu & Wang 2021

---

Published in Transactions on Machine Learning Research (12/2024)
Init Intaltiation
Epach
Epoch 200
Fpoch
Epoch
UMAP
Inttaaliation
Fpoch
Fpoch
Fpoch
Fpoch
GLeMAP
Figure 1: The visualization of the spheres dataset (Moor et al. 2020) by UMAP and GLoMAP (both trans- ductive). GLoMAP shows a progression of the representation from global to local during the optimization. All teu inner clusters are identified as well as the larger cluster on the outer shell (purple).
The purpose of this work is to address key challenge in manifold learning: Can single algorithm capture both the global structures and local details of high-dimensional data? To answer this question, we develop a new nonlinear manifold learning method called GLoMAP, which is short for Global and Local Manifold Approximation and Projection. An essential component of GLoMAP is its locally adaptive global distance construction, where locality is basod on K-nearest neighbors, and global distance refers to the distance between any general pair of data points. GLoMAP locally approximates the data manifold in a data-adaptive way with many small low-dimensional Fuclidean patches similar to UMAP (MeInnes et al. 2018). As such approximation can result in multiple different local distances of the same pairs, we first reconcile the local incompatibilities by taking the maximum of the multiple (finite) local distances. Then, we take a shortest path search over those local maximums to obtain a coherent global metric. Our heuristic gives a single topological space that reflects the global geometry of the data manifold without incompatible distances.
Our work presents two sigmificant algorithmic advancements. First, to address the crowding problem in visu- alization highlighted by Van der Maaten & Hinton (2008), we adopt a UMAP-like loss function. Optimizing this loss function with global distance matrix (rather than sparse matrix of K-nearest neighbors) presents challenge. To handle the challenge, we develop novel sampling scheme that leverages an unbiased esti- mator of the loss (Proposition D within a stochastic gradient descent framework. Second, our annealing-like process for scaling similar to cooling in temperature-is a novel and interesting development. It enhances the optimization process by enabling a gradual progression from global shape to local detail. This progressive global-to-local refinement. is unique the literature and addresses a longstanding dilemma: global meth- ods often lack local detail, while local methods rely on initialization for global coherence. Specifically, by tempering with global distance rescaler т, the algorithm first identifies global structures (with a larger r) and subsequently refines local details (with smaller r). This effect, illustrated in Figure L reveals clear progression from global structure identification to fine-grained local details, where all ten inner clusters are distinguished, as well as the larger cluster on the outer shell (purple). We emphasize that this annealing approach does not require carefully crafted annealing with global distance scaling was particularly effective, as similar meaningful structures did not emerge with rescaled local distances alone.
inpalization-randdo noise suffices. We find that combining
To achieve inductive dimensional reduction mapping for the generalization of visualization to unseen novel data point, extend GLoMAP to its inductive version named iGLoMAP (inductive GLoMAP). The low dimensional embedding, denoted by 2, for high dimensional data point z is obtained by 2 Qo(x), where Qo is modeled by a deep neural network (DNN) with parameters 0. When the map Qo is updated by using a gradient from a pair of points, the low dimensional representation of the other pairs is also affected. We found that it is very difficult optimize the GLoMAP loss function with a typical deep learning method where the visualization representations are by neural network's output. Therefore, as one of our key contributions, we develop particle-based algorithm which mimics the stable optimization process
2

---

Published in Transactions on Machine Learning Research (12/2024)
of transductive learning. By this, we can formulate an effective stochastic gradient descent algorithm for learning the inductive map.
Our proposed global distance itself, constructed through a new local distance, also can be seen as an advance in the array of global preservation algorithms. MDS keeps the metric information between all the pairs of data points, and thereby aims to preserve the global geometry of the dataset. Recognizing that Fuclidean distances between non-neighboring points may not always be informative in high-dimensional settings, Isomap applies MDS instead to geodesic distance estimates computed via the shortest path search. Efforts to refine this geodesic distance estimator include improving the Euclidean distances among nearby points to better reflect the local manifold, for instance, through conformal embedding (Silva & Tenenbaum 2002), spherelets argument (Li & Dunson 2019), or the tangential Delaunay complex [Arias-Castr & Chau 2020). On the refined local distances, these approaches apply the shortest path search to estimate global distances. As our local distance estimator is in a closed form, the distance computation a scalable alternative to Li & Dunson Arris-CCsstro Castro Chau (2020). Similar to our approach, the local distance in Silva & Tenenbaum 2002) is compuled by multiplying a closed-form local rescaling constant to the Euclidean distances. As compared in Section S9 in Appendix, when our distance is instead used under the framework of [Silva &
(019 and AAris
Tenenbaum 22022), the visualization result shows separation between clusters similar to Figure [
Now we discuss related works or compare our framework with the previous works. The seminal t-SNE and UMAP preserve the distance among neighboring data points. It is known that these methods may lose global information, leading to a misunderstandding of the global structure (Coenen & Pearce 2019
Rudin et al. 2022p. y. To overcome the loss of global information, much effort has been made, for example,
by good initialization (MeInnes et al. 2018 Kobak & Berens) 2019; Kobak & Linderman 2021] by Euclidean distance preservation between selected non-neighboring points (Fu et [0119 Wang et al. 202] Our proposed GLoMAP improves this global structure preservation by estimating the global distances with adopting a UMAP-like loss function. When it comes to the local distances, both UMAP uses rescale factors that may enable local adaptability of estimated distances. Our local approximation differs from that of UMAP as our local distance estimator is in a closed form and has a consistent property. Additionally, UMAP adopts a fuzzy union to allow their inconsistent coexistence in a single representation of the data manifold, while use the shortest path search secking coherent global metric. Many efforts have been made to for handling optimization with
extend existing visualization methods to utilize DNNs for generalizability lower computational cost, especially when the data size is large (Van Der Maaten 2009 Gisbrecht et al. 2015 Pai et al. 2019 Sainburg et al. (021). Our sampling schemes and particle-based algorithm may benefit these approaches in stabilizing the optimization.
The main contributions of this paper are as follows:
(1) We introduce GLoMAP, a novel dimensionality reduction method that captures both global and local structures. The key inventions include locally-adaptive global distances and an annealing- like process for scaling. These innovations enable GLoMAP to produce progression from global structure to local details during optimization, a feature not present in previous methods.
(2) We introduce iGLoMAP, an inductive version of GLoMAP, which avoids the need to re-run the entire algorithm when a new data point is introduced. Our particle-based algorithm leverages the advantages of inductive formulation while maintaining the stability of optimization, similar to transductive learning.
(3) We establish the consistency of our new local geodesic distance estimator, which serves as the building block for the global distance used in both the GLoMAP and iGLoMAP algorithms. The global distance shown to be an extended metric.
(4) We demonstrate the usefulness of both GLoMAP and iGLoMAP by applying them to simulated and real data and conducting comparative experiments with of-ate-f--th-are methods. All implementa- tions are available at httpp:: /tttps://githb.. com/ Jungeunkiim/iLLMMM.
The rest of this article is structured as follows. In Section 2, we provide a brief review of some leading DR methods. For more complete review, we refer to Rudin al. 2022.. The GLoMAP and iGLoMAP
3

---

Published in Transactions on Machine Learning Research (12/2024)
algorithms are introduced in Section 3. The theoretical analysis and justifications of our distance metric are presented in Section 4. The numerical analysis in Section 5 demonstrates iGLoMAP's competency in handling both global and local information. This article concludes in Section 6.
2 Background and the Related Work
In manifold learning, the key design components of DR are: (a) What information to preserve; (b) How to caleulate it; (c) How to preserve it. From this perspective, in this section, we review several techniques, such as Isomap, MDS, t-SNE, UMAP in common notation, and discuss their limitations and our improvements. We also discuss PacMAP and PHATE in Section S2
Let Ii, Ii...., In E C R denote the original dataset. Write X = [.,,...,, Fnl E Ruxp. Our goal to find embeddings 21....:: 2n Fd, where d & p and 2, is the corresponding representation of 2, in the low- dimensional space. Under many circumstances, d is used for visualization. Write Z [ 2n] E Rexd
2.1 Global methods
MDS family of algorithms that solves the problem of recovering the original data from a dissimilarity matrix. Dissimilarity between a pair of data points can be defined by a metric, by monotone function on by a non-metric functions on the pair. For example, in metric MDS, the objective is to minimize stress, which is defined by stress(21, zn) (Eiz)(d (zi, f(d (x)),))))) =2))) 1/2 for monotonic rescaling function f. Depending on how we see the imput space geometry, the choices of dissimilarity measures
the metric,
for d and d₂ would vary. The common choice of the L2 distance corresponds to an implicit assumption that the input data is a linear isometric embedding of a lower-dimensional set into a high-dimensional space Silva& & Tenenbaum 2002).
Isomap can be seen as special case of metric MDS where the dissimilarity measure is the geodesic distance, i.e, Isomap tries to preserve the geometry of the data manifold by keeping the pairwise geodesic distances. For this, Isomap first constructs a K-nearest neighbor (KNN) graph where the edges are weighted by the Le distance among the KNNs. Then it estimates the geodesic distance by applying a shortest path search algorithm, such as Dijkstra's algorithm [Tenenbaum et al., 2000). The crux of Isomap the use of a shortest path search to approximate global geodesic distances, with the underlying assumption that the manifold is flat and without intrinsic curvature. There have been multiple attempts to improve the geodesic distance estimator under more relaxed conditions. For instance, Isomap has been extended to conformal Isomap Silva & Tenerbaur 2002) to accommodate manifolds with curvature. Both their approach and ours construct global distances by finding the shortest path over locally rescaled distances (although we use different rescalers). Our work extends this locally adaptive global approach beyond the MDS framework, addressing the crowding problem identified by Van der Maaten & Hinton (2008). Similarly, other efforts have also sought to handle general manifolds by calibrating local distances. For example, AArias-Castr & Chau (2020) employed the tangential Delaunay complex and Li & Dunson (2019) used spherelets argument with the decomposition of local covariance matrix near each dala point. In our work, use computationally efficient local distance estimator albeit the global distance construction becomes more heuristic. Nevertheless, we believe that these distances from previous work could also be integrated into our framework, providing better theoretical understanding of the chosen global distance, pending improvements in efficient computation.
2.2 Local methods
I-SNE, as introduced by Van der Maaten & Hinton (2008), is one of the most cited works in manifold learning for visualization. Instead of equally weighting the difference between the distances on the imput and embedding spaces, t-SNE adaptively penalizes this distance gap. More specifically, for cach pair (I,, Pi, defines relative distance metric in the high-dimensional space, where the relative distance gi in the low-dimensional space is optimized to match Pij according to the Kullback-Leibler (KT.) divergence. For any
4

---

Published in Transactions on Machine Learning Research (12/2024)
two points 22 and 2,, define the conditional probability
cxp( 10, - xz,1?/207
(1)
POle = Σnst exp( 111; - -Ix12//207
where oe is tuned by solving the equation log, perplexity = =- -,, Pyte Poje- Intuitively, perplexity is a smooth measure of the effective number of neighbors. Define the symmetric probability as Pty Pait In the embedding space, t-SNE adopts a t-distribution formula for the latent probability, defined by qb (1 (1+d))"'122 where d,- = |||; 2gIl, and the normalizing constant is Z E, Ex (1+ The loss function of t-SNE is the KL divergence between p and q, KL(pll)) Eins Ptj log Pu.. The weight matrix of graph, such as (Piz) or (gaz), which encodes proximity, is called an affinity matrix. To handle datasets with heterogeneous density, Van Assel et al. (2024) extends t-SNE by maintaining constant entropy for each row in the affinity matrix using an optimal transport framework, defining a doubly stochastic matrix (normalized by both rows and columns) for both input and visualization space.
2n
Another highly cited visualization technique is UMAP (Melnnes et al. 2018), which is often considered a new algorithm based on t-SNE (Rudin et al. 2022), known for being faster and more scalable (Becht et al., 2019h. UMAP achieves a significant computational improvement by changing the probability paradigm of t-SNE to Bernoulli probability on every single edge between a pair. This removes the need for normalization in t-SNE in both distributions {pij} and {gis} that require sumnaation over the entire dataset. Another innovation brought about by UMAP is a theoretical viewpoint on the local geodesic distance as a rescale of
the existing metric on the ambient space (Lemma in McInnes et al. 2018 Mclnnes et al. 2018 further develops local geodesic distance estimator near 2; defined as
de d (I.:
{{
D0 (1|x; - 2,11 - pi)/o;
for j $ N; or j= otherwise,
(2)
where N; is the index set of the KNN of rj P; is the distance between z; and its nearest neighbor, and à is an estimator of the rescale parameter for each i. In our work, we address the previously unexplained choices of à and P in (2) by proposing a new local geodesic distance estimator and theoretically establishing its consistency.
To embrace the incompatibility between local distances, as indicated by d (21, A di druap (1i,zz) McInnes et al. (2018) treats the distances as uncertain, so that those incompatible di ( (x;, 2z) and Hommy (5;, may co-exist by a fuzzy union. UMAP defines a weighted graph with the edge weight, or the membership strength, for each edge (i,j) as Mij = Pij + Pjs - PiyPje where Pij = -dd-ddmmaa (1 x;)}. Meanwhile, on the low-dinensional embedding space, the edge weight for each edge (i.j) defined by l [1+a||+-- - 2, where a and b are hyperparameters. Then, UMAP tries to match the membership strength of the representation graph of the embedding space to that of the input space by using a fuzzy set cross entropy, which can be seen as a sum of KL, divergences between two Bernoulli distributions such as
Vij + (1 - (1-b)) log (1 (1-M-) v13) 43
((Z) = Σ (T(uslas)) = Σ Vig log
(1 9bj)
In UMAP, the global structure is preserved through a good initialization, e.g., through the Laplacian Eigen- maps initialization (MeInnes et al. 2018). In our work, seek visualization method that does not depend initialization for global preservation. Another difference of our work is the way to merge the incompatible local distances. We alter the fuzzy union of UMAP by first taking the maximum among finite local distances and then merging the local information by the shortest path search, thereby obtaining global distances.
3 Methodology
In this section, we first present a new framework, called GLoMAP, which is a transductive algorithm for nonlincar manifold learning. GLoMAP consists of three primary phasos: (1) global metric computation; (2) representation graph construction by information reduction; (3) optimization of the low-dimensional embed- ding by stochastic gradient descent algorithm. During the optimization process, the data representation
5

---

Published in Transactions on Machine Learning Research (12/2024)
continuously evolves, initially revealing global structures and subsequently delincating more detailed local structures. Furthermore, we introduce iGLoMMP, an inductive version of GLoMAP, which employs a map- per to replace vector representations of data. iGLoMAP is trained using proposed particle-based inductive algorithm, designed to mimic the stable optimization process of GLoMAP. Once the mapper is trained, a new data point easily mapped to its lower dimensional representation without any additional optimization.
3.1 Global metric computation
Recall that {ax)==1 denotes the original data in RP and {=i)== are the corresponding embeddingg Rd. Our goal is to construct two graphs Gx and Gz that, respectively, represent the geometry on the input data manifold and the embedding space. We then formulate objective function between the graphs Gx and Gz to project the input space geomelry onto the embedding space. The key information to construct the representation graph Gx of the input space is the global distance matrix between all pairs of data points, The global distance will be determined based on the local distances, where the locality is defined by the K-nearest neighbor K; = (x;))== for each 24. When we obtain the estimate of the local geodesic distance by a rescaled L2 distance, two neighboring points can have two possible rescalers because each of the two points provides its own local view. Therefore, we handle this ambiguity by considering the minimum of the two rescalers, which corresponds to taking the maximum of the two distances. Consequently, the local distance estimate between 2, and zj is given by
dissimilarity measure
|
if iy E K; or as E KK otherwise,
Auce(:; 1z5)
min(da, X0,
(4)
where O₂ is the local normalizing estimator defined by
K
02
1 (()))11
(5)
The theoretical rationale for the choice of the local normalizing constant of will be provided in Section 4 under the local Euclidean assumption. Using dioe the local building block, we construct global distance matrix. We construct a weighted graph, denoted by Gloe; in which x; and zj are connected by an odge with the weight (1, 2,) if (x., is finite. Given the weighted graph (Gree dloc), we apply a shortest path search algorithm, e-g-; Dijkstra's 's algorithm, to construct the global distance between any two when Ij E K; Gloe can be seen as an undirected shortest path scarch on a KNN graph, where the distances are locally rescaled. As a result, for any two data points & and y, the search gives
data points. Note that dioc (z,, zz))
E Kj. Therefore, the shortest path search
dgto (2, v) = min (doo u1) +... doe (up: v)),
(6)
where P varies over the graph path between and This process is outlined in Algorithm 1 In line 4. D2, sets the distances to zero for all but the K-ncarest neighbors, indicating disconnections on the neighbor graph. Consequently, the that for the distance of the disconnected elements (nodes), a shortest path search algorithm assigns oc. This implics that when two points are disconnectod based on the local graph Gloe, they are regarded be on different disconnected manifolds, that the global distance is defined as co.
operation in Line yields the intended dinc in equation 4 Note
The search for the shortest path on neighbor graph with Euclidean distances is well studied by Tenenbaum ct al. (2000). However, with our locally adaptive building blocks, comprehending the properties of the resultant global distance becomes challenging. Therefore, the distance construction in equation is heuristic in its nature. In Section 4.2 the construction of the global distance will be explained through the lens of the coequalizer on extended pseudometric spaces. The effectiveness of this approach in capturing the global structure is demonstratod in Examples and 2 as well as in Section
3.2 Graph construction and optimization
Having constructed our global distance dyto between all data pairs, we can construct an undirected graph Gx that represents the data manifold. For the embedding space, assuming it is Euclidean with the La distance,
6

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm Global distance construction
Input: the n n pairwise L2 distance matrix from denoted by D2
Fixed input: the number of neighbor K (default: 15)
Initialization
4:
Construct the KNN distance matrix Dx from D2
5: Rescale
6:
Calculate n distinct o² by a row-wise mean among finite squared distances of DK.
7:
(Rescale) Define D Dx j// min (b]
(Symmetrization) Dioc ma D"), where max elementwise-max
Distance construction
10:
Rum gg = S(Dooc), where S is undirected shortest path search algorithm
Algorithm GLoMAP (Transductive dimensional reduction)
1: Fixed input:
distance matrix Dglo, trade-off parameter de, number of epochs Nepoch. learning rate schedule Oschh and tempering schodule Tach, c= Learnable input: randomly initialized representation Z
Optimization
for t L=,,,.,,epoohh
Update azch [t] and [tch(t)
6:
Compute the membership strength paj exp(-Dggoli..)/17 p4. = =E; Mij
7:
for k == I,..., Riter
8:
Sample mini-batch indices = {ii,..., "ii....,im. }m}
9:
Sample a neighbor 2,, from Pyli for ie Eg - Eies p4. log qis. EiEs Ejes(1 miy) log -91)
10:
11:
Z + optimizer(2, 2 clip c)
12:
end for
13:
end for
construct another undirected graph Gz representing the embedding space. Specifically, consider the Fn] data matrix X [.n] and the embedding matrix Z = [=ı,..., zn]. The shared index i E / = {1....,n} identifies the data point æ and its embedding 24. Here we construct two weighted graphs of the nodes I denoted by Gx (1, E2) and Gz = E2) Define the undirected (symmetric) weighted adjacency matrix Ex with a temperature T by
Ex = Me exp(-dgio(T, 2,)TT}
for i j, where the global distance dgo is defined in c Note that the KNN graph Gioc used construct dyto is not a single connected graph, but several, then there exists (i,j) s.t. dglo = co. In this case, the weight of the edge (i,j) by (7). Similarly, with the L2 distance for the embedding graph, define the undirected weighted adjacency matrix Ez by
Ezli. qU (1 (1+a - 20
(8)
for # j, where a 1.57694 and = 0.8951 are tunable hyperparameters. This definition of Øs and the a and b values were originally used by McInnes et al. (2018)
To force the two graphs Gx and Gz to be similar, that is, to force the edge weights to be similar, we optimize the sum of KL divergences between the Bernoulli edge probabilities μay and qiz- Let O,.... n4 be the index that paj 0. Then,
2 Σ (1 Mby) log -.)).
(Z) (2)
Σ KL(pglgg) CJET
Mg log 4s
A
(9)
We call the first term in (9) the positive term because decreasing log qs forces the pair i, closer, and the second term the negative term because decreasing - log(1 9iz) works oppositely. We multiply the negative

---

Published in Transactions on Machine Learning Research (12/2024)
Intalliaatoon
Epach 53
Epoch 150
Epoch 225
Epoch 300
UMAP
Inib lizettion
Epoch 30
Lpoch 150
Lpoch 225
Epech 300
GLeMAP
Figure 2: The transductive visualization of the hierarchical dataset (Wang et al. 2021 Top: The results of UMAP. Bottom: From the random initialization, GLoMAP finds first the macro, then meso and then all the micro clusters a progressive way during the optimization.
term by Ae > as a tunable weight because in some applications, having control over attractive forces (the positive term) and repulsive forces (the negative term) can be preferred for improved aesthetics (Belkina) et al. 2019 Kobak Berens 2019). We A = 1 as default. This loss construction with the Exponential- and-t formulation is similar to t-SNE and UMAP, where each probability of the pair (i,j) approaches one when the points (I) (zx, are near with each other, and approaches vero when they are far away from each other. We optimize equation g through its stochastic version in the following proposition.
Proposition 1. An unbiased estimator of (2) up to a constant multiplication is
-- pr. log gisk gig.
--
de
>E mij) log (1 qtj);
(10)
iES JES
where p4. = -E Mij and S a uniformly sampled index set from I = (1, n} and ja is sumpled from a
conditional distribution Pyji" Σn
Proof See Section SLI
We apply stochastic gradient descent (SGD) to optimize the loss in 10 with respect Z, decaying the learning rate and temperature т. The tempering through decreasing shifts the focus from global to local, thereby catalyzing the progression of visualization from global to local perspective in a single optimization process. For a more in-depth discussion of tempering т, refer to Section S5.. To stabilize SGD, we adopt two optimization techniques from McInnes et al. (2018). First, the gradient of each summand of (iglo(Z) is clipped by a fixed constant c. Second, the optimizer first updates w.r.t. the negative term, then again updates w.r.t. the positive term, which calculated with the updated Z. The described transductive GLoMAP algorithm in Algorithm
This stochastic optimization approach is highly sought after, especially in our global distance context. The optimization of Lgto in (9) is challenging because the number of pairs with nonzero Piy be O(n²). Note that although the loss formulation (Z) in 9 resembles that of t-SNE and UMAP, they do not have the same computational burden because the number of all pairs with non-zero Pi is O(nK) = O(n), and thus their schemes consider all such pairs at once or sequentially. Therefore, we optimize (g through Liglo(Z) (Z) in equation 10 with mini-batch sampling. The cantion may arisc cach itcration does not necessarily involve the entire dataset. This problem is handled by an inductive formulation in the following section.
We apply GLoMAP to two exemplary simulated datasets with both global and local structures. The spheres dataset (Moor et al. 2020) has ten inner clusters and an eleventh spread on a large outer shell. Moor al. (2020) found that UMAP identifies all inner clusters but not the outer shell one. The hierarchical dataset. (Wang et al. 2021
Example 1.
features three-layer tree with five child clusters per parent, across five trees.
8

---

Published in Transactions on Machine Learning Research (12/2024)
Wang et al. 20221 showed UMAP captures micro-level clusters but not meso- macro-level ones. Detailed
data description ionss and hyperparameters are in Section S3 and Section 54 respectively. Figure | and 2 show UMAP and iGLoMAP representations at different optimization stages. UMAP uses spectral embedding for initialization, while GLoMAP starts randomly. In Figure I GLoMAP on the spheres dataset shows a clear transition from global to local structure during optimization. At. epoch 125, it separates the outer shell (purple) from the ten inner clusters, which then become distinct in subsequent epochs. This illustrates how GLoMAP evolves from global to detailed local structures. Similarly, Figure 2 for the hierarchical dataset reveals a progression: by epoch 50, GLoMAP distinguishes all macro-level clusters, then identifies meso-level clusters, and finally, all micro-level clusters, while preserving higher-level structures. We attribute this to GLoMAP's distance metrics that balance global and local information. For the spheres dataset, the distinct separation of the outer shell and inner clusters is due to improved local distance estimation and the use of a The theoretical analysis of our local distance The effect of the acsthetics parameter de is detailed in Scction [55.2
smaller rescaler in equation g discussed further in Remark 2
estimate will be provided in Soction g
3.3 iGLoMAP: The particle-based based inductive algorithm
To achieve an inductive dimensional reduction mapping, we parameterize the embedding vector using a mapper Qo X + Rd, where Qo can be modeled by a deep neural network, and the resulted emboddings are 2; = Qo(x)) for = .,..., n. Then the loss in equation 9 becomes (2to(Q((11))...... ( and is optimized with respect to Qe- Due to Proposition [ we can use an unbiased estimator of Egto (Qo((()))) (o(z)) with fglo defined in equation 10 for stochastic optimization. We develop a particle-based algorithm to stably optimize the inductive formulation. The idea is that the evaluated particle = = Qx is first updated in a transductive way (as updating in Algorithm ( and then Qs is updated accordingly by minimizing the squared error between the original and updated 2. The proposed particle- baree inductive learning is in Algorithm 3 Note that this particle-based approach does not increase any computational cost in handling the DNN compared to a typical deep learning optimization; the DNN is evaluated/ciiffrentttee /differentiated only one time over the entire mini-batch. At the same time, it individually regularizes the gradient of each pair due to the transductive step in Line 12 in Algorithm 3 In our implementation, the optimizer for @ is set as the Adam optimizer (Kingma & Ba 2015 with its default lcarning hyperparameters, i.c., 3 = (0.9, 0.999) with learning rate decay 0.98. The Adam optimizer is renewed every 20 epochs.
In the iGLoMAP algorithm, the entire dataset is affected by every step of stochastic optimization through the mapper Qo. This is in contrast to the previous transductive GLoMAP algorithm, where an embedding update of pair of points does not affect the embeddings of the other points. Due to the generalization property of the mapper, we empirically found that the iGLoMAP algorithm needs fewer iterations than the transductive GLoMAP algorithm, will be shown in the following example. Note that the basticle-based algorithm of iGLoMAP is distinguished from two stage-wise algorithms that first complete the transductive embedding and then train a neural network to learn the embedding (for example, Duque et al. (2020)) ) Tn such cases, the transductive embedding stage cannot enjoy the generalization property of the neural network during training.
Example 2. We apply iGLoMAP on the spheres and hierarchical datasets in Example with the same hyperparameter settings. As a mapper, we train a basic fully connected neural network as described in Section 5 The visualization results of the training set and also the generalization performance on the test set are presented in Figure 3 In the spheres dataset, the ten inner clusters remain distinct from the outer shell (colored purple), and this separation is still evident in the generalization. For the hicrarchical dataset, the test set is generated with different level of random corruption (in noise level, micro level, or meso level) from the training set. As these levels increase, the generalization appears different, yet various levels of clusters can still be observed. We make some other empirical observations. First, as mentioned above, the iGLoMAP algorithm needs fewer itcrations compared to the transductive GLoMAP algorithm. We trained it for 150 epochs, in contrast. to the 300 epochs for the transductive algorithm. Second, we found that even a small starting T does not hinder the discovery of global structures; for an analogous figure to Figure Figo see Figure [529 in Section [S8] These findings suggest that the deep neural network might inherently encode some global information. For example, with iGLoMAP on the hicrarchical dataset using the default K 15 neighbors, which is generally too few for meso level cluster connectivity, the macro and meso clusters are
9

---

Published in Transactions on Machine Learning Research (12/2024)
Spheres
Spheres
Spheres (magnified)
Spheres (magnified)
Hierarch Tra
Hierarch Test (holse)
Hierarch Test (micro)
Hierarch Test (meso)
Figure 3: The visualization and generalization performance of iGLoMAP on the hierarchical and spheres dataset. Spheres: All ten inner clusters are identified with the outer shell (purple) scattered around. Hier- archical: all levels of clusters identified.
Algorithm 3 iGLoMAP (Inductive dimensional reduction)
1: Fixed input: distance matrix Dgla, trade-off parameter de, number of epochs Nepocch learning rate schedule Oach and tempering schedule Tach, c = 4.
Learnable input: randomly initialized encoder Qo parametrized by Optimization
for t= 1=1,..., Repoch:
5:
Update Ossch (4], 1 7/sch [4] and =achh [4 Compute the membership strength Pıj = exp( - Delool...//T) p4. = Ty.=E, My for h 1, n iiter,
6:
7:
8:
Sample mini-batch indices {(i,..., dm
Sample neighbor Tie from Hj for is ES
10:
Z (Zh, Zfe Ik=1 where 24, Q0 (Zte): ) Zjz = (=(3)))
11:
Egoo = -Eies Uig- log Theje - de Eies Ejes(1 - (bj) log (1 - 91z)
Z optimizer(Z,, (2 a, VzLglos clip = c)
12:
L, = 1 1/ where || || is the Frobenius norm
13:
14:
0 + optimizer(fA (f, VoL.) w.r.t. 0, where ž is regarded as constant
15:
end for
16:
end for
partially preserved even from the start, as shown in Figure S31 Section epochs, all level of clusters are identified. For the sensitivity of Xe, see Figure S32 Section [8 This figure demonstrates Ae 's impact, similar to that in the transductive case, but with much milder effect.
S8
Furthermore, only within 5
Remark 1. The two main hyperporameters of our method are the negative weight de and the tempering schedule of T. Smaller Xo leads to tighter clustering, while larger values disperse clusters more, as demon- strated in Ezamples 1 and 2 (Figures S11 S12 and S32 in Section S8 We typically fir Xe = 1, and recommend X 0.1 for tighter clustering and X since the impact T's 's varies belween dalasels, we normalize the dislances throughoul this poper, aiming for a median of 3. Our standard practice begins with t = 1, reducing to t 0.1. This range may not suit every dataset, and thus we provide guidance for adjusting T. Our method evolves from random noise to global, then local shapes. If remains noisy for long time, e.g., over half the epochs, it suggests too high initial T, giving insufficient time for local detail development. In such cases, it is advisable to reduce the slarting :; in
10 for more relazed cluster shapes. For tempering,
10

---

Published in Transactions on Machine Learning Research (12/2024)
fact, halving it or even reducing it to a quarter may be beneficial. If mearéngful shapes still emerge towards the end, the final T might also be too high, indicaling the need to halue the final T.
4 Theoretical Analysis
One of the key innovations of GLoMAP compared with existing methods the construction of the distance matrix. Roughly speaking, our distance designed combine the best of both worlds: like Isomap, the distances are globally meaningful by adopting its shortest path search; like t-SNE and UMAP, the distance is locally adaptive because the shortest path search is conducted over locally adaptive distances. In Section 4.1 establish that our local distances are consistent geodesic distance estimators under the same assumption utilized in UMAP. Then, in Section 4.2 we provide thcoretical insights into our heuristic, which constructs a single global metric space by coherently combining local geodesic estimates. Recall that a geodesic distance dm, given a manifold M, is defined by dar (z, = inf, in (length(s)), where 8 varies over the set of (piecewise) smooth arcs connecting x to y in M.
4.1 Local geodesic distance
This section aims to justify the local geodesic distance estimator on a small local Euclidean patch of the manifold M. Consider dataset RR, distributed on a d-dimensional Riemannian manifold M where d S p. We make the following assumptions on (M,g) and the data distribution.
A1. Assume that, for a given point u E M, there exists a geodesically convex neighborhood U, C M such that (Uu.g) composes a d-dimensional Euclidean patch with scale Ay > 0, i.e. g = >ug", where g" is a Fuclidean metric restricted to d-dimensional subspace.
A2. Assume that M is compact. The data are then assumed be i..d. samples drawn from a uniform distribution M.
Al characterizes a local neighborhood around a fixed point on M that near the point u, M behaves locally as a d-dimensional Euclidean space (up to scaling). A2 assumes that the data are uniformly distributed on the manifold. We assume compactness ensure finite volume, allowing us to define a uniform distriiuution. Alternatively, we could assume that the manifold M has finite volume under the metric g. A2 is beneficial for theoretical reasons, as pointed out in the work of Belkin and Nuyogi on Laplacian eigenmaps (Belkin) & Niyogi 2001 2003) and also observed by McInnes et al (2018). Assumptions A1 and A2 together are similar to those of UMAP, which interprets a denser neighborhood as local manifold approximation with a larger A and a sparser neighborhood as one with a smaller Au. Intuitively, this brings an effect of projecting (flattening) the manifold locally onto a Euclidean space. Now we present a distance theorem that connects the local geodesic distance with the L2 distance.
Theorem 1. Denote x P the wniform probability distribution on M that satisfies A2.
(a) Assume A1 regarding a point u E M and its open conver neighborhood Un. For any pair (x,y) that belongs to Un and Au > O, dar(x,)) u) = Vxn || vll2-
(b) Assume A1 and A2 regarding a point u E M with its neighbor Un and Au Let V vol Assume, for an m E [0, 1), Bu(u, Gp,((u)) C Uur where Ge E M inffr > 0; O; 2 t} and (2( is an Toz ball centered at with radius Then, Vxu m/)r,,(u),, where C is universal constant that does not depend on du but only on d, m, V, and
1
1' Gz
8p M
(11)
Given manifold M, a Riemannian matric on M is a family of inner products, ((:.) : E M), on each tangent space, T, M, such that (:)u depends smoothly on u E M. A smooth manifold with a Riemannian metric is called a Riemannian maniffold. The Riemmanian metric is often denoted by = (gu)aEM- Using local coordinates, we often use the notation = Ei Di giyda; @ dæy, where 9uy(u) = ((22)) )u, (zzy )u)u.
The ambient metric used define B2(x,)).
11

---

Published in Transactions on Machine Learning Research (12/2024)
is the distance function to measure (DTM) w.r.t. a distribution P..
Proof Soe Section S1.2
Theorem 1 (a) marginally generalizes Lemma from McInnes et al. (2018). which originally introduced the concept of viewing the local geodesic distance rescale of the existing metric on the ambient space. In Theorem (b), we connect λu to DTM (Chazal et al. 2011) by noticing that under the uniform distribution assumption, the probability of a set is closely related to its volume. By this result, for any pair (ar, y) in a geodesically convex Uz, we have
C
dM(
(2) | 1--1-000 yll2.
(12)
This formulation of das (2, y) through DTM (x) is important because its unbiased estimator is identical to o₂ in equation [ Therefore, by the result in Theorem (b), we know that &z/C² is an unbiased estimator of 1/v Now, by using oz we define local geodesic distance estimator of d (I. y)/C as
d.(2,)) {
1 || vll. if y oc,
(13)
otherwise.
The next theorem establishes the consistency of dz. Theorem 2. Assume A1 and A2 regarding point x E M with its neighbor Us and sample size Consider fized m [0, such that B2 Ge.((z) (x)) C Un. For any & > 0, as 00 with with K the smallest natural number greater than or equal to mn,
11 dz v)/
P(3 P E &nl 8.l
- 0.
(x 1)
Proof See Section $1.
Theorem 2 demonstrates that (z,, y) converges in probability to d (r. v), where C is a universal constant independent of the local center I's choice. Thus, dz y) estimates the geodesic distance up to constant multiplication. Note that for dimension reduction, the scale of the input space is relatively unimportant, and thus, we regard C 1. Consequently, by establishing an equivalence relationship dm(x, y) we can assert that d= (z. y) consistently estimates d (x, locally for any x E M.
||x [xx-y/i v
82,
4.2 Construction of global metric space in extended satended-pseudo-eeee
spaces
When we apply the local geodesic distance estimation as described in equation 13 treating each data point as the local center, we effectively obtain n different local approximations of the data manifold. In this section, our goal is to coherently glue these approximations together. By treating these as n different metric systems the shared space X with |X] n, we employ equivalence relation analogous to Spivak's cocqualizer in peteendel-pseuud-mmetrr spaces. This method presents an alternative to the fuzzy union approach used in McInnes et al. (2018), with both methods aiming to merge local information amidst potential inconsistencies among local assumptions. While the fuzzy union encapsulates the global manifold by aggregating all local distances into a single set, our shortest path approach intricately interweaves these distances to form a unified (extended) metric system.
Let A be the set of all indices of data points X, and for all A, let X., (X, d..) denote the space defined through the localized metric de of UMAP in equation 2 or our approach in equation 13 As shown in Mcinnes et al. (218)), this localized space X, for any E A is an
space. Metaphorically speaking, the points in X₂ that are within a finite distance from under d, can be thought of as composing an "island" centered around (See X, in Figure $28 the red-colored part). We define fa as an operator that seteended--suudo-nee pseudo- metric spaces into one as XA = LL Xa:
maps from X to Xa. Now, we simply merge these extended combining all local information. Let d' y') doly. y²) y. V/ X, and da(y. v') = oc otherwisc. This
Note that instead of 62 m,,)) (n), in
we can use 62 (2) any 2 U2 such that Bo Gp (=)) U..
12

---

Published in Transactions on Machine Learning Research (12/2024)
space again is an (2009), Lemma 2.2). Recalling the island analogy, XA now contains islands, as depicted in Figure $28 (in the blue box labeled XA). Note that for a' E A, while X, and X. are distinct extended-pseudde metric spaces, they share a very important commonality. They all share the same underlying data points since Xa = dg) and Xa = (X,da). Given x E X, however, the two points Ia = fa(#) E X, and Ta = fa (a) E X are considered distinct points in XA with (A( cc. We will sew those inherently- identical points into one in coherent way through a needle of equivalence relation.
space and satisfies the universal property for coproduct (Spiak
Spiva. 2009) considers coequalizer diagram of sets
A
Z Y,
(14)
where - [-] is the equivalence relation on Z with x ~ x' if there exists a E A with x = gi(a) and x' = 92(a).
Given dz as a metric on Z, define a metric dy on Y by
dy ([=), [=]) = inf(dz(p1 ②1) + dz (P2, 92) + ................................ dz (p qn)):
(15)
where the infinum is taken over all pairs of sequences (p1,....Pal) (q, (q1,.., (n) of elements of Z, such that Pi ~ 2, ~ x', and Pi41 ~ qi for all 1 S i n - According to Spivak (2009). when (Z, d2) is a extended- pseudo-metric space, (Y,dy) is another aetendeel-sseuulo-etrrt space and satisfies the universal property of a coequalizer. His construction of coequalizer through equivalence relation can provide in our setting a tool to merge two possibly-conffietinn and let. 9i be the function that maps X to the subset in XA that is induced by Xay, where we enumerate A through A = {ai,...,.,, J. First, consider 91 and 92. The coequalizer diagram equation 14 regarding 91 and 92 merges the subspaces in XA that correspond to Xa, and Xay into a smaller space (Y, eliminating the redundancy discussed above. As illustrated in Figure S228 the disconnected two aaherentll-identiin points now are identified as identical, and the two islands are linked, forming a larger island (in the sense that more points are connected with finite distance others).
distances into one coherent distance. In the above diagram let Z = X
Under the design of Spivak (0099) in equation 15 two possibly inconsistent local distances are merged into one by taking the minimum of them. We consider instead to take the maximum between the two as follows. Define finite max operator (a maximum among finite elements), denoted by
fina, ([(a)) =f maxacA, [[aa), (axa)),([(a)),, A + 0, 0c,
(16)
otherwise,
where = {a E Alf(a) < oo). Recalling that Z = XA, we define the local building block as dy := finxx=p.v- (c)(z,,)))) to reconcile the incompatibility. Then, the merged distance on Y in equation 15 is replaced as
dy ([=), (p q)) + dy 22) + dp (n)))
(17)
Now, we consider all .I.... In. We extend the equivalence relation [-], defining x ~ x' if there exist some a E A and indices i.j such that (a) = and g,(a) = x'. In this case, dy in equation 17 satisfies the conditions of an pesedond-pseudommetrric
Proposition 2. The distance dy defined in equation 17 is an dy (z. y) 2 0; 2) dy (I. = dy (y,x); ; 3) dy I dy x w) + dy (w. y) or dy dy(x,1) v) = co.
petei---euudriiiie which satisfies: 1)
Proof See Section ST.3.
On Y, dy defines the distances between all pairs in the dataset without inconsistencies among distances. Now, the following theorem says that the global distance of GLoMAP special case of the metric dy in equation 17, given that two neighboring points are neighbors to each other. Furthermore, it states that in this case, dy is extended metric, which is stronger notion than an extended meeudo-metric.
Theorem 3. Assume & E Ky iff y E Ka for x, X, where K₂ is the K-nearest neighbor of x. Consider (Xa, da) constructed by the local geodesic distance estimator defined in equation 13 with Un approcimated by Kz. Then dy in equation 17 is identical to dzo in equation 0 and an extended metric.
13

---

Published in Transactions on Machine Learning Research (12/2024)
The 3D data embedding
S
Figure 4: The 3D datasets are generated from the displayed 2D rectangles. Left: S-curve dataset, Middle: Severed Sphere dataset, Right: Eggs dataset.
Proof See Section S1.32
Remark 2. If minimum operator is used instead of the fmaz operator, the distance in equation 17 corre- sponds to the distance defined by Spivak (2009) as in equation The difference betweeen these two distances is subtle, yet the modification in equation I7 reflects our view that when each of two points has different local scale, the smaller scale should be employed to define the distance between them. In other words, the larger local distance should be used. Conversely, the fuzzy union approach of UMAP results in a final lo- cal distance that shorter than either of the two conflicting local distances Therefore, our approach, and that of Mchnnes et al. (2018) reflect different philosophvical perspeclives. We believe that the impact of this philosophical divergence becomes significant in practical applications. For instance, in the Spheres dataset in Examples [ and 4 points on the outer shell seem very distant from the perspective of the inner small clusters, while from the outer shell's perspective, the inner clusters do not appear comparatively far. We believe that the choice of perspeclive significantly influences the visualization oulcome, as demonstraled in Figure 7 where GLoMAP aligns with the former perspective.
5 Numerical Results
In this section, we compare our approach with existing manifold learning methods and demonstrate its effectiveness preserving both local and global structures. We consider two scenarios that allow for a fair comparison: 1) cases where lower-dimensional points are smoothly transformed into high-dimensional space, with the goal being to recover the lower-dimensional points; and 2) scenarios where label information revealing the data structure is available. We provide the GLoMAP and iGLoMAP implementation Python package. The detailed learning configurations are in Section
S4
Our analysis begins with transductive
learning, followed by inductive learning.
5.1 Transductive Learning
We compare GLoMAP with existing manifold learning methods, including Isomap, t-SNE, UMAP, PaCMAP, and PHATE, which inherently employ transductive learning. First, we consider a number of three- dimensional datascts to visually compare the DR results, while also quantitatively mcasuring the perfor- mance. Second, we study DR for three high-dimensional datasets that inherently form clusters so that the KNN classification result can be used to measure the DR performance.
4 As described in Section 2.2 the membership strength given by a fuzzy union is defined by Uig = Phy + Pss PapPji
where Piy = expl (oo(ddd d jumpp (x 2.) and Pyt = exp(-d, mmmpp (2s, 25)}- Hence, it can be seen as my = exp(-22 for some x S (z,,
minmdii 2,) ). dimap (2s, 2;
14

---

Published in Transactions on Machine Learning Research (12/2024)
GLoMAP
Isomap
t-SNE
UMAP
PHATE
PaCMAP
GLoMAP
Isomap
t-SNE
UMAP
PHATE
PaCMAP
GLoMAP
Isomap
t-SNE
UMAP
PHATE
PaCMAP
Figure 5: The dimensional reduction for the S-curve, Severed Sphere, Eggs dataset.
5.1.1 Manifolds embedded in three dimensional spaces
Dataset and performance measure. We study DR for three datasets: S-curve, Severed Sphere, and Eggs, shown in Figure g All three datasets are obtained by embedding data points on two-dimensional box into three-dimensional space using smooth function. Detailed data descriptions Section S3 We adopt two performance measures. The first one is the correlation between the original two-dimensional and the dimensional reduction L2 distances. The second one is the KL-divergence between distance-to-men moasure (DTM) type distributions, used in Moor et al. (2020). which is defined by
presented in
1 (x) = Σ exp dist(z,V)² v)
ΣΣ exp dist(z, (2)
DEN
VER
where 0 represents length scale parameter. For dist in f² use the L2 distance on the original two-dimensional space, and for dist in f2, we use the La distance the two-dimensional embedding space. The denominator is for normalization so that ExEx fx(() = 1. The KL-divergence given is
(X, = Σ fo (z.) log (x)
fz)
We vary from 0.001 to 10. A larger focuses more global preservation, while smaller a focuses local preservation.
Results. The visualization results are shown in Figure where GLoMAP demonstrates clear and infor- mative results. Across all three datasets, we observe rectangular shapes and color aliguments, indicative of successful preservation of both global and local structures. Isomap and GLoMAP consistently demonstrate visually compatible recovery across all three datasets. PacMAP also achieves this in the Severed Spheres and Eggs datasets. The visualization by PacMAP of the S-curve demonstrates local color alignment although it shows S-shape. A similar pattern (but with U-shape) is observed with t-SNE and UMAP in the S-curve. Although the global connectivity of the Eggs dataset is not displayed by t-SNE and UMAP, they demonstrate local structure preservation by local color aliguments for each egg shape. Consistent with these visual observations, the quantitative measures, plotted Figure [S30] reveal that GLoMAP has the compet- itive results overall. Deponding on the run, the visualization of GLoMAP of the S-curve and Eggs datasct can be twisted (Figure S36 (c) and (d)). Even when it happens, the performance measures are similar, the overall global shape is quite similar.
15

---

Published in Transactions on Machine Learning Research (12/2024)
GLoMAP
Isomap
t-SNE
UMAP
PHATE
PaCMAP
GLoMAP ae
Isomaa
t-SNE
UMAP
PHATE
PaCMAP
+12
GLoMAP
Isomap
t-SNE
UMAP
PHATE
PaCMAP
Figure Top: the Spheres. GLoMAP scparates points on the larger outer shell from the smaller inner clusters. Middle: the hierarchical dataset. GLoMAP catches all the global, meso and miero level data structures. Bottom: the MNIST. GLoMAP clearly displays the ten digit clusters.
5.1.2 High dimensional cluster structured datasets
Datasct. We consider the case where the label information revealing the data structure available. We apply GLoMAP on hierarchical data (Wang et al., 2021), Spheres data (Moor al.] 2020), and MNIST [LeCun et al. 2010). The hierarchical data have five macro clusters, each macro cluster contains five meso clusters, and cach meso cluster contains 5 micro clusters. Therefore, the 125 clusters can be seen as 25 meso clusters, where 5 meso clusters also compose one macro cluster. One micro cluster contains 48 observations, and the dimension of the hierarchical dataset is 50. The Spheres data by (Moor et al. 2020 are consisted of 10000 points 101 dimensional space. Half of the data is uniformly distributed on the surface large sphere with radius 25, composing an outer shell. The rest reside inside the shell relatively closer the origin, composing 10 smaller Spheres of radius 5. Detailed data descriptions are presented in Section S3 The MNIST database is large database of handwritten digits 0 9 that is commonly used to train various image processing systems. The MNIST database contains 70, 000 28 x 28 grey images with the class (label) information, and is available at http::/ as the most important and widely used real dataset for evaluating the data structure preservation of a DR method (Van der Maaten & Hinton 2008 McInnes et al. 2018 Wang ot al. 2021). Since the later section, iGLoMAP generalizes unseen data points, we use 60, 000 images for training (and in the later section, the other 10, 000 images for generalization). The baseline methods are also applied to the 60, 000 training images
lecunn ctw/ wwwp/ddddmmmssttteeee/ee/mdmmmme
The MNIST dataset is regarded
Performance measure. As performance measure, we use KNN classificat ion accuracy as described in the followings: Since a data observation comes with a label, we can calculate the classification precision by fitting a k-nearest neighbor (KNN) classifier on the embedding low-dimensional voctors (based on the L2 distance). For the hierarchical dataset, the KNN can measure both local and global preservation; The KNN basod on the micro labels shows local preservation, while the KNN based on the macro labels demonstrate global preservation. For the Spheres, KNN is local measure for the small inner clusters, and a proxy for global separation between the outer shell and the inner clusters. For the MNIST, the KNN measures local preservation. If we assume that the data points within the same class have a stronger proximity than bet classes, the KNN classification accuracios on the DR results are reasonable mcasure of local preservation.
*uur computational memory could not handle Isomap the 60, MNIST images. Therefore, we applied Isomap only the first. 6, 000 MNIST images.
16

---

Published in Transactions on Machine Learning Research (12/2024)
Splerre
Herrailyy
Hlearday
NI/IST
03
01-
67
04
02
02
Figure 7: The KNN measures for increasing K.
Note that the labels of the MNIST dataset allow global interpretation by human perceptual understandings of the similarity between mumbers. For example, a handwritten 9 is often confused with a handwritten 4.
Results. The comparison of the visualization with other leading DR methods is presented in Figure G and performance measure in Figure 7 On the Spheres, the proposed GLoMAP shows very intuitive lisalization results similar to what one would probably draw on a paper based on the data description. The inner ten clusters are enclosed by the other points that make up large disk. Similarly, for the hierarchical dataset, we can clearly identify all levels of the hierarchy structure. We can see that although the inner ten clusters are less clearly identified, Isomap also gives the global shape, such that the outer points are well spread out. For methods such as t-SNE, PaCMAP, and UMAP, the outer shell points of the Spheres dataset stick with the inner points making ten clusters. For the hierarchical dataset, no bascline method catches the nested clustering structure; where either the global structure or the meso level clusters is missed. These visual observations are corroborated by the KNN classification plot in Figure 7 which demonstrates the effective KNN classification performance shows almost perfect meso and macro level classification. Also, for MNIST, GLoMAP achieves more than 97% of the KNN accuracy numbers, demonstrating GLoMAP's competence in local preservation.
GLoMAP's DR. For the hicrarchical datasct, only GLoMAP
5.2 Inductive Learning
We apply iGLoMAP and compare it with other leading parametric visualization methods, including Para- metric UMAP (PUMAP) (Pai et al.) 2019), TopoAE (Moor et al. 2020), and DIMAL (Sainburg et al., 2021), which can be seen as a parametric. Tsomap. These methods employ deep neural networks for map- ping; they are detailed in further detail in Section S22 For iGLoMAP's mapper, we utilize a fully connected ReLU network with three hidden layers, each of width 128. Following each hidden layer, we incorporate a batch normalization layer and ReLU activation. The network's final hidden layer is transformed into 2 dimensions via a linear layer. For the other methods, we either employ the default networks provided or replicate the network designs used in iGLoMAP. Specifically, for MNIST, PUMAP, and TopoAE are given the configurations (including hyperparameters and network designs) recommended by the original authors.
The DR results are presented in Figure iGLoMAP exhibits similar visual qualities to GLoMAP but with more clearly identifiable global and meso-levee level clusters for the hierarchical and MNIST datasets. For instance, from the MNIST results in Figure g we observe that similar numbers form groups, such as (7,9,4),
(0,6), and (8,3,5,2), while the ten distinct local clusters corresponding to the ten-digit numbers are evident.
The generalization capability of iGLoMAP is depicted in Figure g for MNIST and in Figure S33 in Scction S8 for the S-curve, Severed, and Eggs datasets, demonstrating almost identical visualizations for unseen data points. Interestingly, the enhanced performance of parametric UMAP over (transductive) UMAP, despite sharing the same framework, reinforces our conjecture in Example 2 that incorporating DNNs aids in preserving global information. Nonetheless, PUMAP's performance on the spheres dataset serves as a cautionary example, indicating that the application of DNNs is not a universal solution for bridging the gap in global information representation. On the Eggs dataset, PUMAP often displayed a more pronounced disconnection than that shown in Figure g as shown in Figure S36 (a) in Section S8 We also observed that depending on the specific run, the Eggs and S-curve visualizations of iGLoMAP can appear twisted, as in
Figure S36 (b) in Section 58 The numerical performance metrics are presented in Figures S34 and S35 in
6DMAL collapsed on the hierarchical dataset and is thus not included Figure
17

---

Published in Transactions on Machine Learning Research (12/2024)
IGLoMAP
iGLoMAP
iGLoMAP
IGLoMAP
iGLoMAP
IGLoMAP
PUMAP
PUMAP
PUMAP
PUMAP
PUMAP
PUMAP
TopoAE
TopoAE
TopoAE
TopoAE
TopoAE
TopoAE
DIMAL
DIMAL
DIMAL
DIMAL
DIMAL
Figure 8: Comparison with other inductive models that utilize deep neural network.
IGLoMAP train
iGLoMAP test
MNIST
Figure 9: The iGLoMAP generalizations for the MNIST. The generalization on the test set is almost identical the original DR on the training set.
Section 58 demonstrating that iGLoMAP is compatible with or outperforms other methods on the datasets used.
6 Conclusion
In this paper, we proposed GLoMAP, a unified framework for high-dimensional data visualization capable of both global and local preservation. By tempering т, we observed transition from global formation to local
18

---

Published in Transactions on Machine Learning Research (12/2024)
detail within single optimization process. This is attributed to the global distance construction with locally adaptive distances as the building blocks, offering an alternative to UMMP''s fuzay union. Furthermore, our algorithms, which are randomly initialized, do not rely on optimal initialization for global preservation. Additionally, we extend the GLoMAP algorithm to its inductive variant, iGLoMAP, by incorporating deep learning techniques to learn a dimensionality reduction mapping-
We now mention several future research directions on GLoMAP and iGLoMAP. First, the full impact of using DNNs remains to be explored. We have observed that the use of DNNs can encode some global information shown with iGLoMAP on hierarchical dataset with small K (Example 2 and Figure S31 and parametric UMAP on various datasets as well (Figure 8 Also, in Section 5 the output of iGLoMA is generally similar to that of GLoMAP, but not exactly the same. More detailed investigation seemss necessary. Additionally, reducing the computational demands of our algorithm is a priority. While we have reduced the computational cost for local distance estimation, managing the global distances, conversely, increases the cost. The shortest path scarch step represents the most computationally intensive aspect of our framework. Depending on the algorithm, the shortest. path search can cost up to O(n²K) K). In our experiment, when the number of points is more than 60,000, we have experienced significant computational bottleneck. One possible resolution could be a landmark extension such as that of t-SNE or Isomap (Van der Maaten & Hinton 2008
Silva &
Tenenbaum 2002]. Moreover, the neighbor sampling scheme, which involves summing membership scores over n distances when all data points are connected, incurs costs comparable to the normalization of t-SNE. Currently, this issue can be addressed through approximations, as discussed in Section [S5.3 but further development to improve computational efficiency would be advantageous. Currently, our implementation is solely in Python, and it could benefit from optimization through advanced languages and interfaces like Numba, Cython, or C++. See Figure S20 for comparison of the current computational time with other leading baselines. In this paper, we did not consider the problem of noise in data. Robustness against noise is an important problem of dimensional reduction, which is worth a subsequent study, but is beyond the scope of current work. Additionally, the uniform assumption applied in this study may be too rigid. Finally, the current applicability of our proposed methods is limited to datasets without missing data, Determining how to elfectively incorporate missing data into the algorithm remains an intriguing and challenging area for future research. We believe that our results nevertheless serve a valuable addition towards visualization of both global and local structures in data, useful in practice.
References
Ery Arias-Castra and Phong Alain Chau. Minimax estimation distances on a surface and minimax manifold learning in the isometrie-to-convex setting. arXiv preprint arXin:2011. 1rX.:2011..2478, 2020.
Etienne Becht, Leland Mclnnes, John Healy, Charles-Antoine Antoine Dutertre, Immanuel WH Kwok, Lai Guan Ng, Florent Ginhoux, and Evan W Newell. Dimensionality reduction for visualizing single-cell data using UMAP. Nature biotechnology. 37(1):38 44, 2019.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and cluster- ing. In Proceedings of the 14th International Conference on NIPS: Natural and Synthetic, pp. 585 591, Cambridge, MA, USA, 2001. MIT Press.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensiouality reduction and data representation. Neural Computation, 15(6):1373-132 1396, 2003. doi: 10. 10.1162 10.1162/08999111 /009009976666332888811117
Anna C Belkina, Christopher O Ciccolella, Rina Anno, Richard Halpert, Josef Spidlen, and Jennifer E Suyder- Cappei--a Automated optimized parameters for t-distributed stochastic neighbor embedding im- prove visualization and analysis of large datasets. Nature communications, 10(1), 2019.
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Ar- naud Joly, Brian Holt, and Gaol Varoquaux. API design for machine learning software: experiences from the seikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning, pp. 108-122, 2013.
19

---

Published in Transactions on Machine Learning Research (12/2024)
Frédéric Chazal, David Cohen-Steiner, and Quentin Mérigot. Geometric inference for probability measures.
Foundations of Compulational Mathemalics, 11(6):733-77 -51,, 2011.
Frédéric Chazal, Brittany Fasy, Fabrizio Lecci, Bertrand Michel, Alessandro Rinaldo, Alessandro Rinaldo, and Larry Wasserman. Robust topological inference: Distance to a measure and kernel distance. The Journal of Machine Learning Research, 18(1):5845-55)) 5884, 2017.
Ming- Yen Cheng and Hau-tieng Wu. Local linear regression manifolds and its geometric interpretation.
Journal of the Americon Stalistical Associalion, 108(504):1421-144 1434, 2013.
Andy Coenen and Adam Pearce. Understanding UMAP. Google PATR, 2019.
Michael AA Cox and Trevor Cox. Multidimensional scaling. Handbook of data visualization, pp. pp. 315-3417 347. Springer, 2008.
Xiongtao Dai and Hans-Georg Müller. Principal component analysis for functional data on riemannian manifolds and spheres. The Annals of Statistics, 46(6B) :3334-3361,, 2018.
Andrés Duque, Sacha Morin, Guy Wolf, and Kevin Moon. Extendable and invertible manifold learning with geometry regularized autoencoders. In 2020 IEFE International Conference on Big Data, pp. 5027-5036. JEEE, 2020.
Cong Fu, Yonghui Zhang, Deng Cai, and Xiang Ren. Atsne: Efficient and robust visualization gpu through hierarchical optinization. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 176-186, 2019.
Andrej Gisbrecht, Alexander Schulz, and Barbara Hammer. Parametric nonlinear dimensionality reduction using kernel t-SNE. Neurocomputing, 147:71-82, 2015.
Jacob M Graving and Iain D Couzin. Vac-sne: deep generative model for simultancous dimensionality reduction and clustering. BioRaiv, 2020.
Takuya Isomura and Taro Toyoizumi. Dimensionality reduction to maximize prediction generalization ca- pability. Nature Machine Intelligence, 3(5):434-4445 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Proceedings of the 3rd International Conference on Learning Representations, 2015.
Dmitry Kobak and Philipp Berens. The art of using t-SNE for single-cell transcriptomics. Nature commu- nications, 10(1):5416, 2019.
Dmitry Kobak and George C Linderman. Initialization is critical for preserving global data structure in both t-SNE and UMAP. Nature biotechnology. 39(2):156-13) -17,1666--771111 2021.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. AT&T Labs [Online]. Available: http://yann. lecun. htm/eedd//mniise 2:18, 2010.
Didong and David Dunson. Geodesic distance estimation with spherelets. arXiv preprint
arXiv:1907.0m 00296, 2019.
Leland McInnes, John Healy, and James Melville. UMAP: Uniform manifold approximation and projection for dimension reduction. arXio preprint 180:::180..00 03426, 2018.
Marina Meilä and Hanyu Zhang, Manifold learning: what, how, and why. Annual Review of Statistics and Its Application, 11, 2023.
Kevin R Moon, David van Dijk, Zheng Wang, William Chen, Matthew J Hirn, Ronald R Coifman, Natalia B Ivanova, Guy Wolf, and Smita Krishnaswamy. Phate: dimensionality reduction method for visualizing trajectory structures in high-dimensional biological data. BioRwie, pp. 120378, 2017.
20

---

Published in Transactions on Machine Learning Research (12/2024)
Michael Moor, Max Horn, Bastian Rieck, and Karsten Borgwardt. Topological autoencoders. In International conference machine learning, pp. 7045-7054. PMI.R, 2020.
Gautam Pai, Ronen Talmon, Alex Bronstein, and Ron Kimmel. Dimal: Deep isometric manifold learning using sparse geodesic sampling. In 2019 IEEE Winter Conference Applications of Computer Vision (WACV), pp. 819-828. IEEE, 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, Scíkit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Yixuan Qiu and Xiao Wang. ALMOND: Adaptive latent modeling and optimization via neural networks and langevin diffusion. Journal of the American Statistical Association, (66(555):1124 1236, 2021. doi: (0.1080/016214459200 25.9..09...91115666. URL http:::///oo..o//....0000
2014 2019 1691563
Peter J Rousseeuw. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis. Journal of compulational and applied mathematics, 20:53 65, 1987.
Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. Interprctable machine learning: Fundamental principles and 10 grand challenges. Stalistic Surveys, 16:1 85, 2022.
Tim Sainburg, Leland Mclnnes, and Timothy Q Gentner. Parametric UMAP embeddings for representation and semisupervised learning. Neural Computation, 33(1)):2881-2) 19077 2021.
Vin Silva and Joshua Tenenbaum. Global versus local methods in nonlinear dimensionality reduction. Advances in neural information processing systems, 15, 2002.
David I Spivak. Metric realization of fuzzy simplicial sets. Preprint, pp. 4, 2009.
Joshua B Tenenbaum, Vin de Silva, and John Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319 2323,, 2000.
John W. Tukey. Exploratory Data Analysis. Addison- Weslly, 1977.
Hugues Van Assel, Tilouan Vayer, Rémi Flamary, and Nicolas Courty. Snekhorn: Dimension reduction with symmetric entropic affinities. Advances in Neural Information Processing Systems, 36, 2024.
Laurens Van Der Maaten. Learning a parametric embedding by preserving local structure. In Artificial intelligence and statistics, pp. 384-391. PMLR, 2009.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of machine learning research, (11), 2008
Jarkko Venna and Samuel Kaski. Neighborhood preservation in nonlinear projection methods: An experi- mental study. In International conference artificial neural networks, pp. 485 491. Springer, 2001.
Yingfan Wang, Haiyang Huang, Cynthia Rudin, and Yaron Shaposhnik. Understanding how dimension reduction tools work: An empirical approach to deciphering I-SNE, UMAP, TriMap, and pacmap for data visualization. Journal of Machine Learning Research, 22(201):1-73, 2021. URL httt:://jmlr.// org/
papers/v22/20-10611 html
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image datasct for benchmarking machine learning algorithms. arXie preprint NXKv:1708.0770 2017.
Zelin Zang, Shenghui Cheng, Linyan Lu, Hanchen Xia, Liangyu Li, Yaoting Sun, Yongjie Xu, Lei Shang, Baigui Sun, and Stan Z Li. Evnct: An explainable deep network for dimension reduction. IEEE Transac- lions on Visualization and Computer Graphics, 2022.
21

---

Published in Transactions on Machine Learning Research (12/2024)
Appendix
S1 Proofs of Theorems and Propositions
In this Appendix prove the following theorem from Section
and Section 4
S1.1 Proof of Proposition 1
We only need to show that Lglo(Z) cEs c.ss ciEs(Cigo(Z]] for some constant >> 0, where
n
n
Cglo =
Pig log 9ij Ae
Σ - pij) log (1 q:j). ==
(S2)
==1
We first rewrite the first term in S2 by using an expectation form. We say ~ p4. when follows discrete dist robution over {1,..., n with probability (U.,,...(..)))) Likewise, we say jii Pyja when jii follows a discrete distribution over {L..., n} with probability (Fije Pals) where Pyje E, Then we can rewrite
$2
a Σ May log Qiy = E,E log 9:))
Σ
where jií ~ Hyle and i ~ pa. Now, for easy sampling, we further consider U, a uniform distribution over [I.... Then, now we have formulation for importance sampling
E ( [og = EiNU Mi. E [log qu] nlEWO Eg log logm>]] mn]] l/n
Its oae-sample unbiased estimator vipae. log 96j where ~ and ji ~ Pyle- Now, S is simply a multi-sample version of the one-sample case. Therefore, Eies M4 log qt, is an unbiased estimator of E M4 log dij. 4:j. constant multiplication, i.e., c ==n|SS]
up
Now, rewrite the second term in S2 again by using expectation form. This time, however, use two independent uniform distributions U and j ~ U. That is,
Σ i1j=1
l1 Mij) log (1 9is) n NEI-EEjwt [(1 pij) log (1 q.)]]
(S3)
When we have two independent copies i U and j U, an unbiased estimator of S3 is n n piy) log (1 -g))- To extend this idea, when we have i 1. Im-1) where ja as' are i.i.d. from U, again, unbiased estimator of S3 is
Σ (1- mise) log (1 (ije).
(1-m)))
Note that S (11, ...; }m a set of independent draws from U. Therefore, for any ig, we have independency is (i1,.., in 4k+11 ..., }. Therefore, we have another unbiased estimator of S2 that
n²
Σ m(m iES jESVi
Σ (1 (1-Mi)) log 9:j)-
Note that ga = so that log(1 - qui) = 0. Therefore, above estimator is simplified without any change in value
n²
11-- (1- log 1 9.))
m(m m 1)
iES JES
This proves that Eies (jes(1-ma) log - 9:t) is an unbiased estimator of En EE (1 Miz) log (1 - 915) up to constant multiplication, i.e., n² n²/m(( 1).

---

Published in Transactions on Machine Learning Research (12/2024)
Note that, for the two terms, the constant multiplications applied for unbiasedness are different. However, because de is flexible tuning hyperparameter, we can simply redefine de by multiplying the ratio of the two constant multiplications.
S1.2 Proof of Theorem
Proof [Proof of (a)] Denote the Euclidean metric on I&P by g and that of scale dn as Aag. Since Un is Euclidean and convex, the shortest geodesic on Un that connects any x, E Un is a straight line, that is a straight line in the Euclidean geometry. We define
IM = [r/7(0) z, 21, = smooth curve on M),
To (x/7(0) = x1) = smooth curve on ).
Then, for any æ, y E Un:
L Vo(a(t),5(0)da
das (x, = inf (length(?)) = inf (length(n)) = inf SET's
yET'ar
>ETV
I. [1(()ld)== (And2(1..)) [V(Olid==/hadble.))
inf 7ELV
(.. = Vxu inf yEl'v
In the second equation, we changed the infimum over A' to To. This is because by the geodesic convex- ity of Un, the shortest geodesic are that connects x, y is in To (which the shortest are that connects x, v.)
Proof [Proof of (b) Under A2, X1 Uni i.e., pdf f(x) b,E where V Vol(M). For [0, 1]. 2/2 and Cd.,. == (v d+2 Ca define the global constants Ca = +1) which g Aug. Since U, is d-dimensional Euclidean,
Assume Bz(x, Gp.m) U, on consider coordinates T1, ..., Fd as spanning Un so that the volume element is dV = ddellg)da A... A drd Then, the volume of Vol B2 (z, ()) is
d
Vm
(zl f Vdet(g)dz) A... dxd
Ba(z,t)
= =,n B2(z,))
dx A ... A drd
2/2
Au
r 1) pd
Au Cd
Therefore, for (2 t) E Uni
P(B2(I,t)) Vol(B2(a, ())
X C'
In our setting, and therefore,
1 uV
(1B
C2
1
uV
Gp =
Vx
C₁
2

---

Published in Transactions on Machine Learning Research (12/2024)
Therefore, the DTM is
m
mm (x)
du
Ca
1
2 du
m Ca
d 11
m 1
d+2ml X
d
m. A
2+2x
Therefore,
1
d+2 Ca 1/2 5p (x) Vm
(g.m(x))
Vu
Cd.m.V
S1.3 Proof of Theorem
Proof. In this proof, we make use of the limiting distribution theorem regarding the empirical DTM Chazal et al. (2017). First, we restate the theorem.
Theorem (Theorem in Chazal et al. (2017))- Let be some distribution Rdd For some fixed x, assume that Fg is differentiable at Fz ((m), for (0, 1), with positive derivative Pa (m)). Define (z) = E ||x (x)) K for K = [+]mn. Then we have
vn(op (x) 6g.m(z)) (x)) 4 N(..
where 0 ni F, (m) f (mm) (Ft(s Ft())F ds dt.
Now, assume A1 and A2 regarding point E M. From A2, we have
x v12Camm
dM(2,)) y)
8p,m(1)
da (x, v)
ze
C2
d.m, v de (xt 1)
02
2e
(x)
5p
(2:)² 2 02
2 (x)
Here, := :
(x) is fixed nonnegative number. Therefore,
1 dall,.)) 2()= - =P( (x) - 03 2 cx)
PP PP3y U2 U.t.
mm))
C Cd.m. P2(r, v)
By Theorem when Fg is differentiable at F-1(m) for m E (0, 1), with positive derivative (F (m))) where (t) IP x z|| st).
50 - - d N(O, 12)
3

---

Published in Transactions on Machine Learning Research (12/2024)
for some fixed n/g We first check if the condition satisfics our setting. Note that by the definition of (z). we know that (22, (r)) 2 m, i.e., (r (x)) 2 m. Since (1) is a non-decreasing function of t,
let us consider & S (T). By the proof of Theorem ! we know that
=P(Ba(o, (t) = -P( 21 s =P B2 vt)) = cta/2
for some constant > 0. Therefore, (t) is differentiable for I Gr,m (x), and its derivative is always positive as long >>>00 0. Note that P=1(mm) > 0 when (0, 1). Therefore, we can apply Theorem in our setling, so that of .. (I)) 0² = op(1). Therefore,
(((Em())))))))))))))))))))) -62 2 (s) 0.
S1.3.1 Proof of Proposition 2
Define for z, y E Y, A(x, y) set of all sequences {pi, 9 Vi=1 of elements of XA, that satisfy po+1 qi for all 1 < i < 1 and [P]] x. [am] y-
1. Since each d is non-negative, by definition dy is non-negative.
2. For a sequence in A(x, y), its reverse exists and is also a sequence in A(y,z), z). Now, the symmetry of d makes the path distance any ordered sequence {pr, qi ji E A(x, y) the same as that of the reversod sequence (:), 2(v, where Pj = Qn+1-j and qi = Pn+t-j- In other words,
dy(p1, +... d qn) = (f Q1) + + (p: 9n)-
Therefore, we have (v v) = dr (v) because
inf dy(p1. 91) + ... (y(pn:qu)) 9m)= = inf d/ (p(21. + ..... + dy In). A(x,y)
Alv.z)
3. Let (x, < co. Choose any w E Y. any of dy (z. w) or dy (w. y) is oc, then the incquality is true. Now, consider both (x, w) and dy (w, y) to be finite. Then, there exist minimizing sequences ........d((222 qn) and dy (w, y)
(pe, -0==1 E A(x, w) and {pr, q: - A(w, y) such that dy (z, w) = Note that when we merge the two paths into one, we have
d (1) +.. df qn) with [4.] = [p1] path connecting x and y. Now, similarly to A(x, v), define A2 y) as set of all sequences g:) of elements of XA. that satisfy p+t1 qs for all s i n and pr ~ 42n y.
dy (2,8) = inf (dy(p), (1) + ... + +d d 9n)) A(z,8)
= inf (dy(pi, +... ...... + d (p2n, (2))))22))
Aa(a.9)
S ( a1) + .....ddyp..
(p dn) + dy ②1) + .... d, (p,, gn)
= dy (x, w) + dy (w,y).
The second equality is because the shortest distance can always be achieved by a path of length n since card(X) = card(Y) n.
S1.3.2 Proof of Theorem 3
We have 91.-.., Iu. and cach x E X mapped to a distinct point gx(x) E XA, i.c. g.(x) + of Therefore, for each p E XA. we can uniquely identify the index and z E s.t. p= g((x), i.c., x= (p). Since the image of gi does not overlap i.e., (g)) for i j, we can define g-1, which is unified
4

---

Published in Transactions on Machine Learning Research (12/2024)
function of all gi .i.'.....''''''
....9'''' i.e., for p E XA. 9 (p) == (p) for i such that p 9x()). Now, for p.9 E XA. we
have (p q) < oo only when (p) E K (1) (q) E kg-)(p) By the assumption of Theorem 3 when
g (0) E Kg i(4), we always have g 1 {q) E Kg 1(p). This ensures that when dg (()))-(()),)) (q) 00;
we have dn (p).9-"(( (q)) < c0. Therefore, in this case,
dr(p.g) max (dy (0)) (1),0 (1))))())))))))))))))) 10 dioc(g (o00((()..))) 9p).g-
for dinc defined in equation
Thus, for x, 1 E Y, we have
(x, 8)
inf (dy(P1. 91) + dy (p2, 92) + .... dp 9n))
A(2,y)
inf ((lo)g (p1).g (qi)) + ... dg (pn), (g.)))
A(z,2)
min (ū, w1) + ........ (ups 0) = dgtn (T, P(E.))
with dglo(z; v) defined in equation 6 where ā = (pi) E X and 9 (nn) E X. The second equality is due to g (p) 9 (q) for p ~ q. Note that the y E Y are identified by I, E X, so with slight abuse of notation, we say dy (z, = yz)
Now, we show that dy in this case is an extended-metric. Given Proposition 2 we only need to show that dy (z, v) = 0 iff x = y- Since da satisfies da. y) = 0 iff x == y, we have dy(p. q) = 0 iff p = Given this, consider x, E Y. It is obvious that dy (z. y) = if == = yi we can take p. and qi so that p: = q. and [p:] = [4.] z for = ..., n, which gives S dy (z. I (p(..1))+dp
+.). 9x) = If dy, y) = 0, there must exist a sequence {pe. (p..::Te )==1 E A(xx,)) such that dy (1.199)) + +d 92) +.......++++.. dp 9m) 0. Since if ps # qt, then (pt, q:) > O, we have p; q: for = 1,..., Since pi+1 qi by the definition of A(x, v) and since [q:] [pi], we conclude that x = [pi]
[pn]
S2 Other Related Work
In this section, we discuss additional related work.
PaCMAP Wang et al. 2021 propose PaCMAP to preserve both the local and global structure. The loss of PaCMAP is derived from an observational study of state-of-the-arl dimension reduction methods such as t-SNE Van der Maaten & Hinton 2008) and UMAP (Melnnes et al.) 2018p. The global preservation of PaCMAP is based on initialization through PCA and some optimization scheduling techniques. Our development of global distances may be adopted by PacMAP instead of its current use of Euclidean distance.
PHATE MMoon et al. 2017 propose PHATE to preserve diffusion-based information distance, where the long-term transition probability catches the global information. Intuitively, PHATE generates random walk on the data points with the transition probability matrix P where P[]]j] x e for some global rescaler 7. After t walks, large transition probability p'(ilj] where pT = P will imply that i and j are relatively closer than those pairs of low transition probability. The diffusion- based design of PHATE is especially ellective to visualize biological data, which has some development. according to time, such as single-cell RNA sequencing of human embryonic stem cells.
Distance to Measure. Distance to measure (DTM) first introduced by Chazal et al. 2011 and its limiting distributions are investigated in (Chazal et al. 2017). These works are in the context of topological data analysis, where DTM is a robust alternative of distance to support (DTS). DTS is a distance from a point x to the support of the data distribution, not a distance between two points. DTS is used to reconstruct the data manifold, for example by r-offset (a union of radius r-balls centered at the data points), or together with persistent topology (incrcasing r) to infer topological features such as Betti numbers. DTM is introducod as an alternative to DTS because the empirical estimator of DTS depends on only one observation in the dataset, which might be sensitive to outliers. These works do not share the same context with our work
5

---

Published in Transactions on Machine Learning Research (12/2024)
because we are not aiming to infer topological features recover topology. However, found that there is a mathematical connection between our local distance rescale and DTM. By connecting the two, we can easily obtain the consistency of our geodesic distance estimators by their limiting distribution theorem.
Topological Autoencoder Moor et al. (020 propose Topological Autoencoder as a new way of reg- ularizing the latent representations of autoencoders by forcing that the topological features (persistence homology) of the imput data be preserved in the latent space, adding the interpretability of autoencoders in terms of meaningful latent representation. The information of persistence homology is caplured by caleu- lating distances between persistence pairings, so that such distances of the input space and latent space are regularized to be similar. Besides the motivation of autoencoder regularization, Moor et al. (2020) show com-- peting two-diment -ro-dimnnsionll latent space visualizations against existing manifold learning (visualization) methods. Therefore, we compare our iGLoMAP with TopoAE.
Deep isometric manifold learning Pai et al. 2019 proposes Deep isometric manifold learning (DI- MAL.), which is an extension of Isomap to exploit deep neural networks to learn a dimensional reduction mapper. DIMAL shares the samne spirit of MDS as Isomap does in the sense that it seeks to minimize the quadratic error between the geodesic distance in the input space and the L2 distance the lower dimensional representation. DIMAL uses network design called Siamese networks (or twin network). As the geodesic distance to be preserved in DIMAL is the same as that in Isomap, the key difference between GLoMAP and DIMAL is the key difference between iGLoMAP and Isomap; the geodelic distance estimates and the loss function (the quadratic loss and KL-divergence loss).
Parametric UMAP Sainburg el al. 2021) exlend UMAP to a parametrric version, which we call PUMAP, using a deep neural network such as a autoencoder. PUMAP shares the same graphical representation of dataset with UMAP, but the optimization process is modified to exploit mini-batch based stochastic gradient algorithm for training deep neural network. Like Sainburg al. (2021), we also use deep neural network to learn dimensional reduction function. The key difference between GLoMAP and UMAP is also the key difference between iGLoMAP and PUMAP.
EVNet Zang et al. (0022) propose EVNet, a dimensionality reduction method that utilizes deep neural networks, with the purpose of 1) preserving both global and local data information, and 2) enhancing the interpretability of the dimensionality reduction results. EVNet maps the input data twice: first, to a latent space, and then from this space to lower-dimensional (visualization) space. The distances in the visualization space are regularized to be similar to those in the latent space. We believe that comparing our method with EVNet would be interesting, pending the availability of its public implementation.
propose predictive principal component amalysis, which finds a lower-dinensional representation at time /+1 1 as a function of the sequence of dependent data points of time {}. The lower dimensional representation then used for predicting the data point at time & + 1. It an interesting problem to condense the dependency structure among data points as a time series into single lower dimensional representation for the purpose of prediction. We think extending our framework to handle this problem would be interesting direction.
Predictive principal component analysis Isomura & Toyoizumi 2021
VAE-SNE Graving & Couzin (2220) propose VAE-SNE that incorporates t-SNE to regularize the latent space of the variational autoencoder (VAE). VAE-SNE is similar to Moor et al. (020) in that it seeks to regularize the latent space of an autoencoder to have a meaningful and probably more interpretable latent reprosentation. The regularization torm of VAE-SNE that is added to the (variant of) VAE loss is a probabilistic expression of the i-SNE loss. Therefore, the design of VAE-SNE aims to learn an autoencoder that has a latent representation similar to t-SNE. In our numerical study, we focus on comparing with t-SNE,

---

Published in Transactions on Machine Learning Research (12/2024)
S3 The Datasets
We give details about the datasets used in our numerical study. The Python package of iGLoMAP includes the data generating code for all simulated datasets.
Scurve We adopted the Scurve datasct from the Python package scikit-lcarn (Pedregosa et al. 2011 Let
be a vector of uniform samples from (- 2 () Also, let u be uniform samples from (0, 2) of the same size. We can think that the original data in the lower dimensional space (2-dimensional) is a matrix [t. y). Now we transform this data matrix into higher dimension (3-dimensional), The first dimension is defined by = sin t, where the sin is an element-wise sin operator. The second dimension is simply y u. The third dimension is defined by vector = sin(t) (cos(t) - 1). The resulting 3-dimensional data is matrix [x, y, z]. We use = 6000.
Severed Sphere The Severed Sphere dataset is also obtained by the Python package scikit-learn (Pe- dregosa et al., 2011). Let u be a vector of uniform samples from (-0.55, 2 - 0.55). Also, let be a vector uniform samples from (0, 2x). The 2-dimensional data matrix [t, y] transformed into three dimension first by transform, and then by point selection. First, the transformation [x. y. =] = (sin(t) cos(u), sin(t) sin(u), cos(u)). Now only the rows of the data matrix such that lected for t E t. We use 6000.
< 7t are se-
Eggs The Eggs data is made up of 5982 data points in the three-dimensional space. It has 12 half-spheres (empty inside) and rectangle with 12 holes. When we locate the 12 half-spheres on the holes on the rectangle, we obtain the shape of a two-dimensional surface, where the half spheres and the boundaries of the wholes are seamlessly connected. On the rectangular surface, the points on the flat area are little sparser than in the curved arca; we uniformly distribute 2130 points on the rectangle [-16, 16] x [-4.4] and remove the points on the 12 circles with radius 1, centered al [[-13, -2), (-13, (-,
(-3, 2), (2, +2),
(7, -2), (12, 2). (-8, +2), (-3, -2), (2, 2). (7, +2), (12, 22)]. Depending the amount of points removed can vary. Therefore, in our setting, we use fixed random generating seed nunber so that the training set is always the same, and always the number of remaining points is 1266. Each half-sphere of radius has 348 uniformly distributed points. Therefore, the dataset. in total has 12 x 348 + 1266 = 5982.
the random uniform generation,
Hierarchy The hierarchy dataset developed by Wang al. (2021). The five macro centers are generated from (0, 100 1so) where 150 a 50x50 identity matrix. We call each macro center as M, for i L...., 5. Now, for each macro center, 5 meso centers are generated from NM,, 1000Isa). We call the meso centers Mij where = 1,..,.. 5. Now, for each meso center, 5 micro centers are generated from N N(M,, 1007so) We call the micro centers Mijk. where k = 1,..., 5. Now for each micro center, local cluster is generated from N 10/5). In our experiment, each local cluster consists of 48 points so that in total n = 6000.
Spheres The spheres dataset is designed by Moor et al. 2020 It has one large outer sphere on which half of the dataset uniformly distributed and len smaller inner spheres on which the remaining points are uniformly distributed. Let the center an inner sphere be denoted by u, where generated from (00,0.5/mm) Now, 5% of the dataset is uniformly distributed on the sphere of radius centered at u, The large outer sphere is centered at the origin and has radius of 25. The 50% of the data set is uniformly distributed on this outer sphere. In our case, we use 10000.
1,.., 10. Then, u, is

---

Published in Transactions on Machine Learning Research (12/2024)
[+] Plat of 0, me
[bjr -
[c)r- 0.5
[d] 0.1
1.
1:1
7-0.5
T=0.1
0.6
5-0.05
0.4
8.1
0.0
3.2
3.4
0.6
0.8
1.0
Figure S10: GLoMAP without T tempering on the hierarchical dataset. A larger fixed finds more global shapes, and smaller fixed r's find more local shapes while missing global clusters.
$4 Learning Configurations
Learning Configuration for Example 1. We apply UMAP and GLoMAP; where for both methods, the number of neighbors is set K = 15 (default) for the spheres, and K 250 for the hierarchical dataset. The latter is large to make the graph connected at least within each of the macro-level clusters. We fix all de to 1 (default), while T is scheduled to decrease from 1 to 0.1 (default).
Learning Configuration for Section 5 Typically, we set de at 1 (default) to showcase performance without tuning. However, for MNIST, we opt for tighter clustering by setting Xe at 0.1. In the case of iGLoMAP applied to the S-curve, the shape initially remains linear, then expands suddenly at the end. To address this, we adjusted the starting to be four times smaller as outlined in Remark | For similar reasons, we made adjustments on the Eggs and Severed datasets, allowing shapes to form carlier and providing sulficient time for delail development. In the MNIST datasel, where both GLoMAP and iGLoMAP Lend linger in the noise, we reduced the starting by a quarter. Apart from these specific cases, we maintain the default schedule (from 1 to 0.1). All other learning hyperparameters are set to their defaults in the iGLoMAP package (learning rate decay 0.98, Adam's initial learning rate = 0.01, initial particle learning rate = 1, number of neighbors K=15, and mini-batch size= 100). GLoMAP was optimized for 300 epochs (500 epochs for MNIST), and iGLoMAP was trained for 150 epochs.
S5
Additional Discussions
S5.1 The effect of tempering
In Example 1 it seems tempering is vital to discover the hicrarchical clustering structure in the data. Figure $10 (a) depicts the effect of decreasing temperatures on n² (d) = exp(-d/7)- For a given d, a decreasing 7 reduces (d), requiring the corresponding pair on the visualization space to be more distanced. This makes the local clusters stay close at the carly stage while forming the global shape, and soparates them at the late stages, forming the detailed local structures. The same progression from global shape to detailed localization does not happen without the tempering (when 7 is kept as constant) as Figure S10 (b-d). A larger fixed (r 1) finds global shapes, and smaller fixed r's find more local shapes while missing the global clusters.
S5.2 The effect of the aesthetics parameter X
For Example I lo see the effect of the aesthetics parameter Ae in controlling the attractive and repulsive forces, we vary de for a wide range in Figure [SI] and [S12 We observe that similar development patterns occur across wide range of X₂ values. However, smaller Xa more strongly condenses data points within the cluster, and vice versa. For an extremely large de, the cluster shape may not appear, suggesting a possibility that optimization did not occur properly.
8

---

Published in Transactions on Machine Learning Research (12/2024)
Initialiiation
Epoch 50
Epoch
Epoch
Epach 200
Epoch 225
A- 01
Initialization
Epoch 50
Epoch 100
Epoch
Epoch 200
Epoch 225
Epoch 300
A-
Initielliaaton
Eooch 50
Epoch 100
Epoch 150
Epoch 200
Epoch 225
Epoch 300
A--0.3
Initialiization
Epoch 50
Epoch 100
Epoch 150
Epoch 200
Epoch 225
Epoch 300
Initie lization
Epoch so
Epoch 100
Spach 150
Epach 200
Epoch 225
Epach 300
Initializatton
Eooch 50
Fpoch 100
Epoch
Epoch 200
Fpach 775
Initie lization
so
Epach 100
Epech
Epoch 200
Epoch 225
Epoch 300 13 t
Initialization
Epoch 50
Epoch 100
Epoch
Epoch 200
Epoch 225
Epoch
Figure S11: The scnsitivity of de of the transductive GLoMAP on the hicrarchical datasct (Example D A larger d tends to make local cluster more spread. However, the general lendency of the development from global structures to local structures is similar across a wide range of X values. The scale was reduced from 1 to 0.1
9

---

Published in Transactions on Machine Learning Research (12/2024)
Initialization
Epoch 25
Epoch
Epoch
Epoch 150
Epoch
0.01
initialization
Epoch 25
Epoch
Epoch 100
Epoch 150
Epoch 200
Au 7o-0.05
mntiaalization
Epoch 50
Epoch 100
Epoch 150
Epoch 200
Epoch
Au Ao-0.1
Initialization
Epoch
Epoch
Epoch
Epoch
Epoch
Initialization
Epoch
Epoch 50
Epoch 100
Epoch 150
Epoch 200
A.-5
Initialization
Epoch 25
Epoch 50
Epoch 100
Epoch 150
Epoch 200
1--10
Initializetion
Epoch 25
Fpoch
Epoch 100
Epoch 150
Epoch
50
Figure S12: The sensitivity of Ae of the transductive GLoMAP on the spheres dataset (Example 1 A larger
de tend to make a local cluster more spread. However, the general tendency of the development from global local structures similar across wide range of X values. The 7 scale was reduced from 0.1.
10

---

Published in Transactions on Machine Learning Research (12/2024)
partial
partial
partial and
partial and
partial and mu
partoal and
Top: the exact loss, Middle: simplified Dato is used (K-neave [K-nearest neighbor distance matrix of Dglo is used instead of Deto), Bottom: simplified Dgto used and (1 14j) is approximated by 1. Number of data points: Spheres 10,000, S-curve 8,000, Eggs 6,000, Severed 4,000. We set K = 15m, where [n/100].
Figure S13: GLoMAP faster variants results (Section $5.3
$5.3 Computational cost reduction
While we have reduced the computational cost for local distance estimation, managing the global distances. conversely, increases the cost. Besides the shortest path search, the neighbor sampling scheme (line g in Algorithm 2 incurs costs comparable to the normalization
t-SNE; The sampling involves summing
membership scores over n distances, given that all data points are connected. The cost of the sampling scheme can be reduced by instead considering the K-nearest neighbor distance matrix of Dgins for example, with K 20K. To further reduce the computational cost, we could also ignore the difference between (1-)4y) values, but consider them all as 1. This saves time in retrieving the Pij values from the x (sparse) matrix. Since (u.) is only n 1 vector, it does not take much time to look up. In such case, the loss function is L == Eies M4. log 4ij, >eE Ejes log (1 4:)). For examples of these approximations' results, see Figure [S13 for the visualization and Figure S14 for the computational time comparison. These
figures demonstrate a high similarity to the results obtained from the exact loss computation, and the reduction computational cost becomes more evident for larger datasets.
S6 Additional Experiments
In this section, we discuss the performance of our methods on an interesting dataset, called Fishbowl. In addition, we also empirically investigate the sensitivity of iGLoMAP against the capacity choice of deep neural networks for the mapper.
Fishbowl Data. It is an interesting problem how dimensional reduction method performs a datasct, which not homeomorphic to R&², for example, a sphere. In such a case, there is no way to map onlo the two dimensional space while preserving all the pairwise distances in the data. Now, we slightly change the problem. We consider that we are given data on a half-sphere. This the famous crowding problem, and in this case also, there no way map onto the two dimensional space while preserving all the pairwise distances. Intuitively, may want to smash (or, stretch) the half sphere to make it flat the
11

---

Published in Transactions on Machine Learning Research (12/2024)
GLoMAP time by Dataset
full
400
partial
partial and mu approx
300
Time (5)
200
100
spheres, 10K
scurve, 8K
eggs, 6K
severe, 4K
Tralls
Full: the exact loss, Partial: K-nearest neighbor distance matrix of Dglo is used instead of Dglo- Partial and mu approx: K- nearest neighbor distance matrix and (1 Pij) is approximated by 1. The effect of using K becomes more evident for larger datasets.
Figure $14: Run time comparison of GLoMAP and faster variants in Section S5.3
(a) Height =0.6
(b) Height =0.8
(c) Height =0.55
(d) Height
Figure S15: The fishbowl dataset (n=6000).
two dimensional space. Now, we turn our attention a dataset on something between a sphere and a half-sphere, called a fishbowl (Silva & Tenenbaum, 2002), which has more than half of the sphere preserved. We generate uniformly distributed dataset for {0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.975, 1}. The data is illustrated in Figure $15 When 7 = 1, the data are equivalent to a uniform sample on a sphere. Although there is no consensus on what type of visualization must be ideal, in this case the exact pairwise distance is impossible. All learning parameters and hyperparameters are set to their default values, except for the initial 7 value for iGLoMAP, which was reduced 0.5. This adjustment was necessary because, under the default value, iGLoMAP remains in a linear (non-meaningful) state until very late (see Remark []. The results of GLoMAP and iGLoMAP are shown in Figure $25. For GLoMAP, we some recovery of the original disk until 7 S 0.95. Then, when 0.975 (when the fishbowl is closer lo sphere), GLoMAP simply shows side image. For iGLoMAP, the flat disc shape is made until = 0.975. The result on sphere is in Figure $25 (e) for GLoMAP and Figure $25 (i) for iGLoMAP.
fishbowl F, {(x (, E R 1 y² + +² 1, S 7
Sensitivity analysis on the deep neural network capacity In order to see the impact of network size, we use the same fully connected deep neural network (four layers) with varying network width. The network width (which controls the network size) varies {2" = 2, 4, 6, 8, 10, 11}, of which the range is intentionally chosen to be extremely wide. We enumcrate the corresponding capacities as to Width 4 is impractically small; When networks are this small, the network may not be expressive. Width 2048 is the extreme opposite. Note that width has 66 parameters to learn in the network, width 16 has 646, width 64
12

---

Published in Transactions on Machine Learning Research (12/2024)
height 0.5
(b) height 0.7
[c]
height 0.95
height 0.975
(e)
height
GLOMAP
If
height= = 0.5
(g)
height 0.7
[h)
height = 0.95
(I
height = 0.975
height
IGLOMAP
Figure S16: The result of GLoMAP on the fishbowl dataset. The number on each panel indicates the height of fish bowl (the threshold on the z-axis).
has 8,706, width 256 has 133,122, width 1024 has 2,105,346, and width 2048 has 8,404,994. We recall that in Section 5 we used width 64 for all simulation datasets. We set the hyperparameters of iGLoMAP same as in Section 5.2 except halving the starting 5 0.5 for Spheres since for smaller networks, the expansion of visualization is observed too late.
The visualizations of the results are in Figure S17 We that increasing the network size improves the visualization quality from width 4 to width 64. On the other hand, among larger networks, results, concluding that for a good range of network widths the visualizations are fairly similar. Therefore, we see that for a wide range of network width (of the fully connected deep neural network that we use here), the performance of iGLoMAP stable. Those visual inspections are supported by the numerical measures shown in Figures S18 and (599 which generally show slightly better performance of larger network. This result implics that we should avoid using too small networks, but much less caution needed about using too large networks.
very similar
13

---

Published in Transactions on Machine Learning Research (12/2024)
Capacity
Capacity
Capacity 2
Capacity
Capacity
Capacity 5
Capacity
Capacity
Capacity
Capacity
Capacity
Capacity 5
Capacity
Capacity
Capacity 2
Capacity
Capacity
Capacity 5
Capacity
Capacity 1 xB
Capacity 2
Capacity 3
Capacity 4
Capacity 5
d x
Capacity 0
Capacity 1
Capacity 2
Capacity 3
Capacity 4
Capacity 5
Figure S17: Sensitivity analysis the deep neural network capacity (n=6000). The same fully connected deep neural network (four layers) is used with varying layer width. The range of width is intentionally extreme (from to 2048).
Spheres
Herarchy Macro
Hierarchy Meso
Herarchy Micro
1.00
1600
06
17733
256
1024
5.000
$5905
300
302
200
100
220
300 300
Figure S18: Sensitivity analysis the deep neural network capacity. x-axis: the number of neighbors K. y-axis: the KNN measure analogous to Figure The numbers in the legend are the layer width of the corresponding deep neural network. From Spheres, see that larger capacity is generally better.
14

---

Published in Transactions on Machine Learning Research (12/2024)
Scurve, Density kl
Severed, Density kl
Eggs, Density. kl
10
10a²
16
10"1
10
256
10
256
1024
10
2048
2048
10
10
256
64
10-3
10'
10
1024
2048
10
0.1
0.01
0.001
10
0.1 sigma
0.01
0.001
10
0.1 Sgma
0.01
0.001
sigma
Scurve, Correlation
Severed, Correlation
Eggs, Correlation
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
296
1024
2048
236
1024
2048
236
1124
2000
Figure $19: Sensitivity analysis on the deep neural network capacity. The KL divergence (first row) and correlation (second row) defined in Section 5.1.1 The numbers in the legend are the layer width of the corresponding deep neural network. From S-curve and Severed Sphere, it looks larger capacity is generally better, while the performance measures show similar patterns.
Eggs
Method
CLoMAP
150
Method
GLoMAP
Method
CLoMAP
Method
GLOMAP
Isomap
homap
homep
Method
Isemap
200
LMAP
UMAP
UMAP
150
Isomap
GLaMAP
300
UMAP
100
UMAP
100
50
50
2000
6000
4000
4000
Number
Figure S20: Comparison of computational time. There is room for improvement in the GLoMAP implemen- tation, as it currently relics solely on Python without optimization through languages/ Cython, or C++. Additionally, the neighborhood search algorithm basic version rather than a faster approximation.
iingages/interfacee /interfacess like Numba,
15

---

Published in Transactions on Machine Learning Research (12/2024)
S7 Additional Measures
In Van Assel et al. 22024) the Silhouctte coefficient Roussccuw 1987 and the trustworthiness score Venna & Kaski 2001) are used to assess the quality of dimensional reduction. The Silhouette coefficient measures both the cohesion within clusters and separation between clusters, defined as b-a/ max(a, b), where a the mean intra-cluster distance, and the mean nearest-cluster distance. The trustworthiness score quantifies how well the K-nearest neighbors the low-dimensional representation aligns with the rank of among the Euclidean distances in the input space. Both scores computed using the Seikit-learn Python package Buitinck et al. 20133.
The full results are shown in Figure S27 and S26 while Table S1 shows the case when n 6000 with K = 5 for trustworthiness measure. In Figure S27 For the Hierarchical dataset, when K is small, Isomap performs poorly under the Trustworthiness measure, while for larger K values, UMAP exhibits lower performance. GLoMAP demonstrates competitive performance overall. This consistent competence is also shown in the Silhouette coefficient as in Figure S26 For the Spheres dataset, however, GLoMAP performs the worst on this Trustworthiness measure and improves the Silhouette coefficient. The corresponding visualization is which we believe remains acceptable
presented in Figure 521
desirable.
N=500
N=1000
N=200
N=3000
N=4000
N=5000
N=6000
CLOMAP
Isomia
SNNE
Figure $21: Comparison of visualizations for increasing data sizes on the Spheres dataset. The corresponding Silhouette coofficients and trustworthiness scores are presented in Figure S27 and Table S1.
16

---

Published in Transactions on Machine Learning Research (12/2024)
N=500
N=4300
N=5000
N-1000
N=2000
N-6000
GLoMAP
1-
UMAP
Figure S22: Comparison of visualizations for increasing data sizes on the Scurve dataset. The corresponding Silhouette coefficients and trustworthiness scores are presented in Figure $27 and Table S1.
1=1000
N=
N=5000
N=6000
N-00
N-500
N=4000
BLOMAP
SONE
UMAP
Figure S23: Comparison of visualizations for increasing data sizes on the Severed dataset. The corresponding
Silhonette coefficients and trustworthiness scores are presented in Figure S27 and Table S1.
17

---

Published in Transactions on Machine Learning Research (12/2024)
N=500
N=1000
N-2000
N=3000
N=4000
N=5000
N=6000
GLaMAP
Somaa
4
UMAP
Figure S24: Comparison of visualizations for increasing data sizes on the Hicrarchical dataset. The corresponding Silhouette coefficients and trustworthiness scores are presented in Figure S27 and Table S1. For GLoMAP, Isomap, UMAP, to make the graph connected among higher-level clusters, we use n neighbors=250.
Trustworthiness
Silhouette
Method
GLoMAP
Isomap
UMAP
(-SNE
GLoMAP
Isomap
UMAP
t-SNE
Eggs
0.998
0.999
1.000
1.000
Hicrarchical (Macro)
0.997
0.989
0.997
0.999
0.413
0.424
-0.059
0.226
Hierarchical (Meso)
0.997
0.989
0.997
0.999
0.741
0.614
-0.198
0.059
Hierarchical (Micro)
0.997
0.989
0.997
0.999
0.907
0.489
0.991
0.930
Scurve
0.998
1.000
1.000
1.000
Severed
0.999
1.000
1.000
1.000
Spheres
0.615
0.633
0.660
0.681
0.016
-0.028
-0.022
0.002
Table S1: The trustworthiness score and Silhouette coefficient for varions datasets with n = 6000. The full results are Figure S27 The Silhouette coefficient. is computed only for the Hierarchical and Spheres datascts, as it requires the class information.
S8 Additional Visualizations
18

---

Published in Transactions on Machine Learning Research (12/2024)
N=3000
N=5000
N=4000
N=500
N=1000
N N-2C00
N=6000
BLOMAP
M-NNE
UNAP
Figure S25: Comparison of visualizations for increasing data sizes on the Eggs dataset. The corresponding Silhouette coefficients and trustworthiness scores are presented in Figure S27 and Table S1.
Silhouette, Spheres
Silhouette, Hier micro
Silhouette, Hier meso
Silhouette, Hier macro
Method
1.0
Nethod GLoMAP
GLoMAP
0.8
0.8
0.02
0.6
0.00
Stoouette
Method Isomaap UMMP
Shouette
0.4
0.4
0.002
02
lane
-0.04
0.2
CLoMAP
Isomap
UMAP
0.0
-02
2000
4200 Number Samplees
6000
2000
4200
8000
2000
4000
6000
2000
4000
6000
Number of Samples
Number Samples
Number of Samples
Figure S26: The Silhouette coefficient (Roussceuw 1987 Buitinck al. 2013 are evaluated for an increasing number of samples. For the Hierarchical dataset, GLoMAP shows consistently competitive result for all levels of clusters.
19

---

Published in Transactions on Machine Learning Research (12/2024)
S9 Comparison with C-Isomap
To see the usefulness of our distance in equation 6 we plug-in our global distance into the Isomap framework, i.e., apply an MDS onto our global distance matrix. As a baseline, we choose C-Isomap (Silva & Temenbaum 2002) among many Isomap variants to improve the local distance because C-Isomap is a scalable option as it also provides a closed-form local distance estimator. C-Isomap applies shortest path search over the local distances and then Multidimensional Scaling (MDS). Since MDS does not allow any pair having the distance, imputed 1.5 times of the maximun of pairwise distances for such pairs. As shown in Figure separation between the purple and the other classes. When
538 for C-Isomap, when K is large then K is small, the smaller classes are doted, and each class may compose multiple clusters in visualization depending on the size of On the other hand, when C-Isomap is using our distance, we can see separation.
Algorithm 2 Our choice of designing the loss similar to that of UMAP (as in Algorithun 2 was also significant, and novel if we see it from the perspective Isomap. When comparing Figure I we can see that using Algorithm instead of MDS brings a better clustering effect for those ten inner clusters.
Our GLoMAP corrosponds to Algorithm
20

---

Published in Transactions on Machine Learning Research (12/2024)
K= Hier
K=15, Hier
K=50, Hier
K= 1 100. Hier
1.000
1.0000
1.00
1.00
0.9975
0.95
0.95
0
Tustertheess
0.990
0.90
0.90
0.85
0 9994
019925
0.85
0.80
CLAMAP
0 0.92
0:9900
0.75
UMAP
Hettod
Method
0.990
0:9875
0.70
Iscmao
toomap
0.75
isomao
0.65
0.70
0.60
1000
2000
5000
4000
5000
6002
3000
2000
5000
4000
5000
6000
1000
2005
3000
4000
5000 600p
3000
2000
3000
4300
5000
Number of Samples
Number of Samples
Number of Samples
Number Samples
K-5, Scurve
K-15, Scurve
K=50, Scurve
K- K=100, Scurve
1.000
1.000
0.999
0.531
0.9975
0.990
0.916
0.5850
Tolecttrcc
Tusberthress
0 998
0.977
0996
0.934
0.9900
0.99 9997
0.9875
Method
GLMMAP
0194
GU
0.50
GLiMAP
GLoMAP
0.99
UMAP
0.93
0.9825
UMAP
0.5000
1000
2000
3000
#000
5000 6000
1000
2000
3000 4000
5000
1000
1000
2000
3000
4000
5000
0000
1000
2000
3000
4000
5000
0000
Samples
Number of Samples
Number Samples
Number Samples
K=5, Severe
K=15, Severe
K=50, Severe
K=100, Severe
1.0000
1.000
1995
0.999
8.99
0. 0.995
0.910
0.996
0.592
0
0.977
0.994
0.585
0.5080
0.9
0990
0.5975
Methed
Method
0910
Method
Methed
GZ
0:955
GLoMAP
GLOMAP
GLOMAP
0.997
Isomap
hamap
8988
1somap
homap
UMAP
0.944
UMAP
UMAP
0.970
UMAP
0.9955
0986
0.965
4000
3000
6000
2000
3000
4000
5000 6000
3000
2000
4000
5000
Samples
Samplen
Semples
K=5, Eggs
K=15, Eggs
K=50, Eggs
K= 1000 Eggs
1.000
1.000
1.002
0.999
0.9GG
0.999
lotavelince
0 998
0.956
0.94
0.985
0 5994
0.94
0.992
0.980
Method
Method
Method
Mettodd
GL
GLONAP
0990
GLaMAP
GLOMAP
Isomap
0.90
Isomap
isomap
Isomap
0.988
UMU
UMAP
8980
(MA
UMU
tone
09888
time
bone
4000
6000
2005
5000
3000
Number Samples
Number
Number
Number Samples
5-5, Spheres
K-15, Spheres
K-50, Spheres
K-100, Spheres
0.72
8.800
Method
Method
Method
Method
CLOMAP
0.775
0.75
GLaMAP
GLOMAP
0.70
Isomoo
Isomap
isomsa
Iserno
0.750
0.750
Tuseeithiees
0.50
0.725
5ine
0.5
Tudwortereess
0.66
0.700
0.000
0.675
0.75
0:64
0.600
0650
0:2
0.25
3000
2000
3000
4000
5000
6000
2000
3000
4000
6200
1000 2000
4000 5000
0000
1200
2000
4000 Number Samples
5000
Number Samples
Number of Sampres
Number Samples
Figure S27: The trustworchiness scores (Venna Kaski 2001 Buitinck et al., 2013) are evaluated for an increasing number of samples. This score depends on a hyperparameter, K, which measures the correspon- dence of K-nearest neighbors between the input and visualization spaces.
21

---

Published in Transactions on Machine Learning Research (12/2024)
XA
Xa
X
Y
fa
[-]
far
Coprod
Xa!
Figure $28: The effect of equivalence relation as a coequalize. For simplicity and visual clarity, we illustrate the coproduct between only X, and Na' rather than all pscudo-metric spaces..
(a) Plot (x), = -00
(b)r
[C]T 0.5
1.0
T=0.5
Tw0.1
0.6
0=0.55
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure $29: iGLoMAP without - tempering. Even when small 7 used for the entire optimization, the global information is still found.
22

---

Published in Transactions on Machine Learning Research (12/2024)
Scurve, Density
Severed, Density kd
Eggs, Density
0.07
glomap Isomap
0.32
glmap isomap
016
dlomp
0.44
isomap
0.06
bne
0.30
bne
bine
0.05
pacmap
0.08
pecmap
0.10
pacmap
0.04
0.06
0.08
0.04
0.04
0.02
0.02
0.00
0.1
0.01
0.001
0.1
0.01
0.001
10
0.01
0.001
sigma
sagma
sigma
Scurve, Correlation
Severed. Correlation
Eggs, Correlation
0.6
0.6
0.6
0.4
0.4
0.4
@omap
unap
ghate
pacmep
Homap
unap
phate
parmap
unap
Figure $30: The global preservation measures. Top: KLo (smaller better), Bottom: distance correlation (larger is better)
(a) Initialization
(b) Epoch
IGLoMAP
IGLoMAP
Hierarchical Dataset
Hierarchical Dataset
Figure S31: iGLoMAP on the hierarchical dataset using the default. K 15 neighbors, which is generally too few for meso level cluster connectivity. However, the macro and meso clusters are still preserved from the start. This suggests the deep neural network might inherently encode some location information. (a) The random initialization of the deep neural network. shows many levels clusters. (b) At the epoch 5, already all the levels of clusters are found.
23

---

Published in Transactions on Machine Learning Research (12/2024)
Ag=0.01
=000.05
A,=0.1
A,5
A==1
4==
1=
Soheres
A.00.01
A,-0.05
A.-0.1
A.-
A-1
Ap-
1=
Hicrorchcial
Figure S32: Hyperparameter sensitivity of iGLoMAP. Initial T is and sent to 0.1 for all cases (default).
Scurve train
Severed train
Eggs train
Scurve test
Severed test
Eggs test
Figure $33: The iGLoMAP generalizations for the S-curve, Severed Sphere, Eggs dataset. The generalization the test set is almost identical to the original DR the training set..
24

---

Published in Transactions on Machine Learning Research (12/2024)
Scurve, Density.
Severed, Density
Eggs. Density
IGLoMAP
IGLoMAP
IGLoMAP
0.06
0.08
PUMAP
1ppAEE
TopoEE
0.20
TopoAE
DIMAL
DIMAL
DIMAL
0.06
0.15
0.04
0.02
0.02
0.01
0.00
10
0.1
0.01
0.001
10
0.1
0.01
0.001
10
0.1
0.01
0.001
Scurve, Correlation
Severed, Correlation
Eggs, Correlation
1.0
1.0
1.0
0.8
0.6
0.4
0.4
0.2
0.2
0.0
0.0
(GLOMAP
PUMAP
RopaEE
DIMAL
(GLOMAP
PUMAP
DIMAL
IGLoMAP
PUMAP
RooAE
DIMAI
Figure S34: Numerical comparison with other models that utilize deep neural network.
Spheres
Hierarchy Micro
MNIST
1.00
10
IGLoMAP
0.95
TopoAE
0.9
0.8
0.90
iGLoMAP
0.8
iGLoMAP
0.85
PUMAP
PUMAP
0.80
TppoE
0.7
TopoA
DIMAL
0.4
DIMAL
0.75
0.6
0.2
0.70
0.65
0.0
0.5
100
200
300
0
100
200
300
0
500
1000
1500
2000
Figure S35: Numerical comparison with other models utilizing deep neural networks. For the hierarchical dataset, macro and meso-level performance metrics are omitted, iGLoMAP, PUMAP, and TopoAE all achieve 100% performance.
25

---

Published in Transactions on Machine Learning Research (12/2024)
(a) Parametric UMAP (Eggs)
(b) iGLoMAP (Eggs)
(c) GLoMAP (Eggs)
GLoMAP (Scurve)
Figure S36: (a) Parametric UMAP: The majority runs paramotric UMAP resulted such a shape, so we cherry picked the best one for comparison as in Figure S (b-d) Depending on the run or choice of the hyperparameters, GLoMAP and iGLoMAP may result in twisted visualization. However, we did observe any case having two separated partial visualizations.
Figure S37: The iGLoMAP result on the Fashion MNIST dataset (Xiao et al. 2017). Left: The visualization result on the training data (n=60000). Right: Generalization result on the test data (n=10000).
26

---

Published in Transactions on Machine Learning Research (12/2024)
n. neighbor- 15
5e
neighbo--220
CIsoMAP
neighbor=15
50
-
Alg1 + MDS
Figure S38: The effect of applying global distance to C-Isomap instead of its original global distance estimates, which corresponds to the distance computation by Algorithm and applying MDS in the resulting distance matrix. C-Isomap shows the separation of the purple class when K (n je__eirgbbor is set as large.
27


Reviews:
[{"review_id": "VEi3S62pV4", "reviewer": "Reviewer_X2sp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well written.\n- The paper addresses a key issue in manifold learning: capturing both global and local structures. This balance is often lost in methods like t-SNE and UMAP, which tend to favor local structures.\n- The progression from global to local structure during optimization provides intuitive and interpretable results, as shown in the experiments.\n- The inductive version, iGLoMAP, offers significant scalability and generalizability to unseen data without retraining.\n- Experimental results demonstrate competitive or superior performance on various datasets.\n\nWeaknesses:\n- The cost of computation is only discussed. It would be interesting to plot a comparison of computational time of GLoMAP with t-SNE and UMAP for different datasets (and thus different numbers of data).\n- Some recent papers such as [1] compute Silhouette and Trustworthiness scores (which are available in sklearn). Adding a table of these scores for GLoMAP, t-SNE and UMAP would add quantitative results to the paper.\n\n[1] Van Assel, H., Vayer, T., Flamary, R. and Courty, N., 2024. Snekhorn: Dimension reduction with symmetric entropic affinities. Advances in Neural Information Processing Systems, 36.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces two novel algorithms for dimensional reduction and visualization: GLoMAP (Global and Local Manifold Approximation and Projection) and iGLoMAP (its inductive version). GLoMAP improves upon existing manifold learning techniques by capturing both global and local structures of high-dimensional data and exhibiting a progression from global to local structure during optimization. iGLoMAP extends GLoMAP's transductive approach to inductive learning by utilizing a deep neural network for generalization to unseen data. The authors demonstrate the effectiveness of these methods through experiments on both simulated and real-world datasets, comparing them to state-of-the-art techniques such as t-SNE and UMAP.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Address the two weaknesses:\n- a plot of computational time of GLoMAP with t-SNE and UMAP for different datasets (and thus different numbers of data),\n- a table of quantitative results such as [1]: compute Silhouette and Trustworthiness scores (which are available in sklearn) for GLoMAP, t-SNE and UMAP.\n\n[1] Van Assel, H., Vayer, T., Flamary, R. and Courty, N., 2024. Snekhorn: Dimension reduction with symmetric entropic affinities. Advances in Neural Information Processing Systems, 36.", "broader_impact_concerns": "The paper’s focus on dimensional reduction and visualization methods has broad implications for data analysis, particularly in fields where interpretability and exploratory data analysis are key (biologie, neuroscience, …).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gaeFflOEqK", "reviewer": "Reviewer_JCaC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The authors address both local and global distance estimates to improve dimension reduction.\n\n2. They provide theoretical justification for the design of the proposed method.\n\n3. Experiments on both synthetic and real datasets demonstrate the method's superiority over existing techniques and robustness across different K values.\n\nWeaknesses:\n\n1. The contribution seems limited. The authors mainly combine existing ideas from Isomap's use of Dijkstra’s algorithm for global distances with UMAP's approach, adding a different rescaling method for local distance estimates.\n\n2. The paper is poorly presented, making it difficult to understand. For example, in Section 1, paragraph 3, the authors are supposed to explain how the algorithm captures local and global details but instead compare the proposed method to UMAP, creating inconsistency. Similar issues appear in paragraph 4. Additionally, the relationship between $\\hat{\\sigma}_x$ and the global rescaler in Section 4.2 is unclear. Theorem 1 introduces several concepts, but weak sentence connections and scattered logic make it difficult to follow.\n\n3. The authors should include more experiments on realistic datasets, such as FashionMNIST [1], and GoogleNews word vectors [2], etc, to better validate the method’s generalizability.\n\n[1] Xiao et al, Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. CoRR, abs/1708.07747, 2017.\n\n[2] Mikolov et al, Distributed representations of words and phrases and their compositionality. NeurIPS 2013.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work focuses on dimension reduction for visualization, aiming to preserve both local and global distance estimates. The method constructs local distances between sample pairs by considering only the K-nearest neighbors and computes global distances using Dijkstra's algorithm to find the shortest paths between pairs. The final low-dimensional representation is optimized by minimizing the KL divergence between the high- and low-dimensional distances. Stochastic gradient descent is employed instead of using the full dataset, and an inductive approach is introduced using a deep neural network. Theoretical justification is provided for both the local and global distance strategies. Experiments on synthetic and real datasets demonstrate the method's effectiveness compared to existing approaches, with robustness validated by varying K.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The use of Dijkstra’s algorithm for global distance estimation is interesting, but the presentation makes it hard to fully appreciate the contributions, which seem mostly to combine existing ideas. I suggest major revisions to better highlight the novel aspects, improve the clarity, and include more experiments.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1Qe3L0vsR5", "reviewer": "Reviewer_yBN5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n - The submission is very well-written and clear.\n - The ability for (i)GLoMAP to capture both local and global structures of data is valuable in applications.\n - The theoretical results are varied, and interesting. Proposition 1 and Theorem 1 give confidence in the training procedure for (i)GLoMAP. The theory and discussion contained in section 4.2 is elegant and gives a nice interpretation for the design of the algorithm.\n - The numerical experiments are varied and extensive.\n\nWeaknesses:\n - Some very minor typos/questions listed below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission describes a novel manifold learning method in two versions. The first is a transductive algorithm called GLoMAP and the second an inductive version called iGLoMAP. GLoMAP is a dimensionality reduction technique able to capture both global and local structures. The submission also equips iGLoMAP with a particle-based algorithm to allow for it to be trained in conjunction with a (deep) encoder trained via gradient decent, without the need for additional evaluations/gradient computations of the encoder. It also present theoretical results showing consistency of the new local geodesic estimator, a key part of both algorithms. Finally, it demonstrates the usefulness of GLoMAP and iGLoMAP by comparing its performance against state-of-the-art methods on synthetic and real-world data. The authors present extensive numerical results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are no submission-critical adjustments requested. I do have some very minor questions/suggestions on the submission, though. The authors may accept or reject the suggestions are they see fit.\nSuggestions:\n - Page 4 paragraph 3\n  Replace \"This radically removes the need for normalization...\"\n  with \"This removes the need for normalization...\"\n - Algorithm 2, Line 7\n  Format n_iter as $n_{\\mathrm{iter}}$.\n - Page 7 paragraph 3\n  Replace:\n  \"This stochastic optimization approach is highly sought, especially in our...\"\n  with:\n  \"This stochastic optimization approach is highly sought after, especially in our...\"\n - Page 9 Figure 3 caption\n  Replace:\n  \"...with the outer shell (purple) scatters around.\"\n  with:\n  \"...with the outer shell (purple) scattered around.\"\n - Page 11, Last sentence before Eqn. (11)\n  Replace:\n  \"Therefore, any pair (x,y) in a convex $U_u$,...\"\n  with:\n  \"Therefore, any pair (x,y) in a geodesically convex $U_u$,...\"\n - Page 12, Final paragraph of that page\n  Reword\n  \"...where an island is made up of points that are connected with a finite distance from others.\"\n  The use of the word \"with\" is confusing.\n - Page 13, First sentence\n  Replace:\n  \"where $q = [-]$ is an equivalence relation with $x \\sim x'$...\"\n  with:\n  \"where $q = [-]$ is an equivalence relation on $Z$ with $x \\sim x'$...\"\n - Page 1 of Appendix in the proof of Proposition 1\n  Replace:\n  \"\\sum^n_{i = 1}\\mu_i \\log q_{ij_{i}} upto a constant...\"\n  with:\n  \"\\sum^n_{i = 1}\\mu_i \\log q_{ij_{i}} up to a constant...\"\n\nQuestion:\n - Algorithm 1 (Line 10) and Algorithm 2 (lines 1 and 6)\n  Why does $D_{\\mathrm{glob}}$ have subscript glob? $\\mathcal L$ and $\\mathcal d$ use subscript glo to stand for global. Why does $D$ differ?\n - Algorithm 1 (Line 6)\n  What does \"Calculate $n$ distinct $\\sigma^2$ by row-wise mean...\" mean? Is $\\sigma$ the mean or variance of the rows of $D_K$ for each of its rows?\n - Page 10 first paragraph in Section 4.\n  In the sentence \"Then, in Section 4.2, we proceed our heuristic to construct...\" what does \"we proceed our heuristic\" mean?\n - Page 10 first paragraph of Section 4.1\n  Is there some compactness or boundedness assumption needed to ensure that $M$ has finite volume? Otherwise, the uniform distribution may not be defined, as is needed in A2.\n - Page 10 Assumption A1\n  Could you please define or else give a reference to the scale, $\\lambda_u$?\n - Page 11 Theorem 1 part (b)\n  The assumption that $\\lambda_u > 0$ is given explicitly, but it seems that it is already required for Assumption A1.\n - Page 12:\n  In the statement of Theorem 2, what does the notation $\\ceil{*}$ mean?\n - Page 12, Final sentence of the first paragraph in section 4.2\n  About the sentence \"The advantage of this global construction is its ability to connect two locally disconnected points with a finite global distance\". What is meant by the phrase \"locally disconnected points?\" Is not connected-ness a global property?\n - Page 12, Final paragraph of that page\n  The sentence \"The space $X_A$ is like a space of islands, as depicted...\" What does the phrase \"space of islands\" mean here? I don't know if the words \"space\" and \"island\" are referencing a standard mathematical structure (e.g. metric space) or else the phrase is meant to be understood by its common English meaning.", "broader_impact_concerns": "There are no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers found the idea to combine global and local distance in controlling the low-dimensional projections interesting, and the authors have done a good job in addressing the questions from the reviewers. The manuscript is in a much better shape after revision. All reviewers suggested acceptance.
Decision: Accept (poster)