Navigating the Effect of Parametrization for Dimensionality Reduction

Authors: haiyang  huang
yingfan  wang
cynthia  rudin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 05:48:36

Abstract: Parametric dimensionality reduction methods have gained prominence for their ability to generalize to unseen datasets, an advantage that traditional non-parametric approaches typically lack. Despite their growing popularity, there remains a prevalent misconception among practitioners about the equivalence in performance between parametric and non-parametric methods. Here, we show that these methods are not equivalent -- parametric methods retain global structure but lose significant local details. To explain this, we provide evidence that parameterized approaches lack the ability to repulse negative samples, and the choice of loss function also has an impact.
Addressing these issues, we developed a new parametric method, ParamRepulsor, that incorporates Hard Negative Mining and a loss function that applies a strong repulsive force. This new method achieves state-of-the-art performance on local structure preservation for parametric methods without sacrificing the fidelity of global structural representation. Our code is available at https://github.com/hyhuang00/ParamRepulsor.

Main paper: 
 introduction: 
 Dimension reduction (DR) methods are incredibly useful for data analysis. They provide a bird's eye view of a dataset that shows clusters and their relationships. These algorithms have been used for examining and processing images [1] , text documents [2, 3] , and biological datasets [4] [5] [6] [7] [8] . The successes of modern DR methods can mostly be attributed to neighborhood embedding (NE), which is the basis for modern DR methods [9] including t-SNE, LargeVis, UMAP, and PaCMAP [10] [11] [12] [13] . These algorithms aim to optimize the low-dimensional layout of the data, such that the high dimensional local structure (i.e., neighborhoods) are preserved.A major weakness of existing NE algorithms is that they struggle with adaptability to large, incrementally updated datasets. These algorithms depend on a K-Nearest Neighbor graph, encompassing the entire dataset, to generate the embedding. Consequently, the introduction of new data necessitates a complete re-computation of the embedding, leading to significant time and computational resource demands for large datasets. Although recent adaptations have been developed to optimize only the additional data [14, 13] , these modifications potentially alter the original algorithm's objective function, thereby compromising the embedding's quality.Addressing these challenges, recent developments in combining neural networks with NE algorithms have shown promise. These algorithms maintain the same objectives as traditional NE methods but leverage neural networks to optimize the projection of high-dimensional data into lower-dimensional spaces [16] [17] [18] . The integration of neural networks allows these NE algorithms to be effectively trained on large datasets and generalize to unseen data. Throughout this paper, we refer to this class of algorithms as parametric algorithms. However, as shown in Fig. 1 , despite the similarity in loss Figure 1 : Dimensionality reduction results on the MNIST digit dataset [15] . Parametric methods (bottom row) fail to preserve the local structure of the dataset compared to their non-parametric counterparts (top row). Our method, ParamRepulsor, effectively resolves this problem via Hard Negative Mining. functions between the non-parametric and parametric versions, their outcomes are often completely different, and such difference has been largely overlooked by machine learning practitioners. This paper aims to illuminate and explain these differences, highlighting that parametrization often leads to worse local structure and visualization. Our investigation reveals that parameterized approaches lack the ability to identify cluster boundaries and separate negatives compared to nonparametric approaches. We further show that DR algorithms using Negative Sampling (NEG)-style loss functions exhibit greater adaptability to parametrization than others using Noise Contrastive Estimation (NCE) or InfoNCE loss. This observation is noteworthy as such discrepancies are not observed in nonparametric approaches.Building on these insights, we propose a novel parametric DR method that effectively mines hard negatives without relying on labels. Our approach incorporates additional repulsive forces, placing even greater emphasis on pairs we identify as hard negatives. This enhancement ensures better separation and structure preservation, significantly improving the performance of parametric DR. We select a loss function tailored for optimizing the parametric case, addressing local structure preservation. Our new DR algorithm, ParamRepulsor, approaches the performance of leading nonparametric methods while surpassing existing parametric approaches in preserving both local and global structure. It offers a functional mapping from high-to low-dimensional space, ensuring superior scalability, adaptability, and generalization to unseen data.To summarize, our contributions in this study are:• We conduct a comprehensive analysis of the impact of parametrization on the performance of DR methods, demonstrating that it may compromise local structure. Our findings attribute this issue to insufficient repulsive forces on negative pairs in the parametric setting. Notably, algorithms employing NEG-style loss functions (e.g., UMAP, PaCMAP) exhibit greater adaptability to parametrization than those using NCE-style loss functions (e.g., InfoNC-t-SNE, NCVis). • Inspired by contrastive learning, we propose ParamRepulsor, a new method that uses hard negative sampling to improve the handling of negative pairs, combined with a contrastive loss tailored for the parametric setting. ParamRepulsor is a novel, fast algorithm that achieves excellent local structure preservation while maintaining global structure.NE methods identify a mapping function f θ that constructs the corresponding low dimensional embedding Y = y 1 . . . y n ∈ R d , where y i = f θ (x i ). We will use y i and f θ (x i ) interchangably. For nonparametric DR methods, the function f θ is not defined outside of x 1 , . . . , x n , though it is possible to interpolate. For visualization purposes, d is usually set to 2 or 3. Since the introduction of t-SNE [10] , these algorithms have become widely used due to their ability to identify clusters and manifolds within high-dimensional data. They typically have two stages:Similarity Construction Phase. For all pairs of points (i, j), their high-dimensional similarity, s ij , is captured by a similarity function Φ(x i , x j ) related to their distance. Due to the curse of dimensionality, the Euclidean distance metric fails to accurately represent distances along the data manifold in high-dimensional spaces [19] . A common solution to this issue is to only consider similarities between K nearest neighbors: s ij is set to be non-zero iff x i or x j are within the K nearest neighbors of each other, where K is a hyperparameter, usually 15-30.Embedding Optimization Phase. After constructing the graph, NE algorithms try to optimize a function f θ . The objective is encoded by a loss function L(θ):EQUATIONwhere L N N denotes the loss for i, j that are similar (among the K-nearest neighbors), and L F P denotes the loss for pairs that are not nearest neighbors in the high-dimensional space. Typically, L N N decreases when ∥y i -y j ∥ 2 decreases, and L F P decreases when ∥y i -y k ∥ 2 increases. Their gradients therefore act like forces that attract or repulse the N N or F P pairs, respectively.Relationship to Contrastive Learning. The similarity of the decomposition to self-supervised contrastive learning has recently been noted by [20, 18] . Specifically, loss functions of major NE algorithms can be considered as cases of Noise Contrastive Estimation (NCE) [21] , Info-Noise Contrastive Estimation (InfoNCE) [22] or Negative Sampling (NEG) [23] .Using the framework above, we dive into details of t-SNE [10] , NCVis [24] , UMAP [12] and PaCMAP [13] , which are four major recent NE algorithms. 
nce/infonce-based: t-sne and ncvis: 
 Both NCE-and InfoNCE-based approaches assume the high-dimensional data similarities (the s ij 's) follow an underlying data similarity pattern, represented by an unknown distribution p. These methods learn a function f θ that generates a similar low-dimensional similarity pattern, described by a distribution q, aiming to match p. q decreases as the pairwise distances in the low-dimensional space increase, though their exact relationship can vary. Since q represents a probability distribution, it must be normalized to ensure all possibilities sum up to 1. The only difference is that NCE uses a logistic loss, whereas InfoNCE uses a cross-entropy loss for the data distribution match.Approximating p as a Bernoulli distribution [24] with value 1 for NN pairs and 0 for FP pairs. Assuming that for each step in the optimization, we optimize a batch that contains one NN pair and m FP pairs, q should minimize:L N CE = -E ij∈N N,ikc=1...m / ∈N N log q ij q ij + c=1...m q ikc -m log 1 - q ij q ij + c=1...m q ikc(2)EQUATIONt-SNE, the most popular NE algorithm, utilizes a loss defined over the full data set. The raw t-SNE loss is usually written as the KL-divergence between high-dimensional and low-dimensional conditional probability distributions p and q. Here, we separate the loss following [25, 13] . [18] notes that the exact values of the p ij 's have limited impact and can be treated as binary weights without impacting outcomes. To simplify the calculation and allow for mini-batch stochastic gradient descent, [18] rewrote this loss as an InfoNCE loss [22] . Denotingd 2 (i, j) = ∥f θ (x i ) -f θ (x j )∥ 2 2 + 1 = ∥y i -y j ∥ 22 + 1, the t-SNE loss function can be rewritten as an InfoNCE loss:EQUATIONFollowing [18] , we call the mini-batch variant Info-NC-t-SNE. We will use it from now on since the vanilla t-SNE loss requires computing pairwise distances between all points in a dataset, and it is challenging to incorporate that into the mini-batch parametric DR framework.NCVis [24] uses an NCE [21] loss. We denote the number of negative pairs in a batch as m, and set q ij = 1 d2(i,j) . The NCVis loss is:L N CV is (θ) = -E ij∈N N,ik1...m / ∈N N   log 1 1 + c=1...m d2(i,j) d2(i,kc) -m log   1 - 1 1 + c=1...m d2(i,j) d2(i,kc)     .(5) [18] provides a modern implementation for both algorithms. It also provides parametric versions that adopt multilayer perceptrons (MLP) with [100, 100, 100] hidden neurons and ReLU activation.Negative Sampling (NEG) [23] simplifies the modeling process. Define q θ to be a similarity function in the low dimensional space:EQUATIONUMAP [12] is a DR algorithm that utilizes the NEG loss [18] . Its loss function isEQUATIONwhich is NEG with the similarity kernelq U M AP θ (i, j) = 1 d2(i,j)-1 .PaCMAP [13] is another recent DR algorithm that achieves high-quality data visualization. Compared to other NE algorithms, PaCMAP's loss function is designed to follow several mathematical design principles, but does not have a probabilistic explanation. The loss function (omitting the mid-near pairs term, as it is only relevant during the initial epochs, see Appendix D) is defined as follows:L ij∈N N = W N N d 2 (i, j) d 2 (i, j) + C 1 , L ik∈F P = W F P 1 d 2 (i, j) + C 2in which the W weights change based on the epoch, and C 1 and C 2 are set to 10 and 1, respectively.To study the effect of parametrization on DR algorithms, we extend the PaCMAP framework to incorporate an MLP to map the high-dimensional input to the low-dimensional embedding. We refer to the resulting parametric algorithm as ParamPaCMAP. Implementation details are in Appendix F.. 
effect of parametrization on dr results: 
 Machine learning practitioners have long believed that parametric NE algorithms behave similarly to their non-parametric counterparts [17, 18] . In this section, we investigate the performance of the aforementioned parametric and non-parametric versions of these algorithms. To understand the effect of parametrization more thoroughly, for each parametric DR method, we additionally implemented three new versions, using a neural network with 0 hidden layers (i.e., a linear model), 1 hidden layer, or 2 hidden layers as a projector. We fix the number of neurons for each layer to 100.Observation 1: Parametric NE algorithms typically lead to worse visual effects as well as worse local structure preservation. Our results indicate that parametric NE algorithms often fail to produce embeddings of the same quality as their non-parametric counterparts, even on simple datasets such as MNIST [15] . The non-parametric methods in the rightmost column of Fig. 2 are able to separate the clusters fairly well, but from the first four columns of Fig. 2 , we see that all four parametric algorithms generate clusters that are densely packed with indistinct boundaries, despite the fact that clusters in MNIST are actually separated. These blurred boundaries result in poorer preservation of local structure, with the possible exception of Parametric PaCMAP. [15] dataset generated by various DR methods with different numbers of hidden layers: 0 (Linear), 1, 2, or 3, or non-parametric variant. See Section 5.1 for details of SVM Acc. It is helpful to envision these images in black and white (without labels) to see when clusters would be difficult to visually separate. More datasets/methods can be found in App. C.The challenge of accurately preserving local structure is exacerbated in scenarios where ground truth labels are unknown, especially in large-scale biological and chemical data, where dimensionality reduction is widely used for data exploration. In these scenarios, users may struggle to identify potential clusters within the large, indistinct conglomerates produced by the NE algorithms.Figure 2 quantitatively evaluates the quality of the embedding via the SVM accuracy, which measures local structure preservation (described in Section 5.1.) Fig. 3 further quantifies the observation. Here, we sample three kinds of pairs from the points with labels "3" and "8" from the embedding, and calculate the pairwise distance for each kind of pair. NN denotes the pairs of points that are 10-nearest neighbors, and FP denotes pairs of points that are uniformly sampled from the population. MN denotes "mid-near" pairs that are further than NNs but still relatively close (detailed in Sec. 4.) For each embedding, we scale the distance with respect to the scale of the embedding, and calculate the ratio of the mean FP distance to NN distance, as well as the mean MN distance to NN distance. Our analysis reveals that, in comparison to the non-parametric methods, all the parametric counterparts (App. H.1) have a smaller FP distance ratio, meaning further pairs are positioned closer together, which explains the blurred boundaries between clusters. ParamRepulsor Figure 3 : The low-dimensional scaled distance distribution between various types of point pairs with labels "3" and "8" in the embedding of the MNIST digit dataset [15] Observation 2: NE algorithms with NEG loss perform better when parameterized. A widely accepted explanation for the failure of small neural network projectors, such as those used here, is that they lack the capacity to capture the complexity of the data. While adding more layers to the projector is believed to effectively mitigate the loss in local structure preservation, our experimental results in App. A shows that adding additional layers beyond three yields diminishing returns. As we discuss in App. B, adjusting hyperparameters for parametric DR algorithms-such as the number of nearest neighbors used in NN-graph construction-also had minimal impact on the resulting embeddings. In all cases, the visual quality of the embedding remained suboptimal compared to nonparametric DR methods. While all four algorithms achieve comparable performance on the MNIST dataset in the nonparametric setting, their ability to adapt to the parametric setting varies significantly. Specifically, NE methods that optimize the NEG loss (UMAP and PaCMAP) perform substantially better than those that optimize the InfoNCE/NCE loss (Info-NC-t-SNE and NCVis). As illustrated in the first four columns of Figure 2 , Info-NC-t-SNE and NCVis continue to struggle with local structure preservation in the embeddings when the number of hidden layers is one or two, whereas UMAP and PaCMAP are already capable of grouping similar samples together effectively. Why is this the case? We hypothesize that it is because UMAP and PaCMAP use NEG losses rather than InfoNCE/NCE losses. areEQUATIONProof: see Appendix D.To better understand the difference in performance between the NCE, InfoNCE and NEG losses, we compare their terms (Eq 2, 3, 6). The term that attracts the nearest neighbors in these algorithms is consistently in the form of log q ij . This similarity is also evident in the fact that UMAP and t-SNE share the same loss function for nearest neighbors. The key distinction lies in the treatment of negative pairs or points that are not nearest neighbors. For NEG-based UMAP, the FP loss for each negative pair (i, j) is -log 1 -1 d2(i,j) , and for PaCMAP it is1 d2(i,j)+C2. This term solely depends on a negative pair, ensuring that the gradient is large when the negative pair becomes close. This is in contrast to both NCE and InfoNCE losses, where each negative pair term is based on all pairs. Theoretical studies [26, 27] in standard contrastive learning have found that such design of loss functions may lead to a reduced gradient and worse performance under a multi-layer perceptron (MLP) model. On the other hand, the NEG loss effectively penalizes the proximity of negative pairs, enhancing the separation between dissimilar points. 
paramrepulsor: 
 While our ParamPaCMAP algorithm preserves better local structure, the embedding space remains suboptimal, with some clusters that should be distinct still merged together. To solve the problem from its root cause, we propose ParamRepulsor, a novel parametric algorithm built upon our ParamPaCMAP. Pseudocode for ParamRepulsor is found in Alg. 1 and detailed in Alg. 2 in App. F.There are several major differences of ParamRepulsor from other methods, the major one being the use of Hard Negative Mining in the repulsive terms. Our goal is to learn from Hard Negative (HN) Samples -pairs whose DR projections are close but should be far apart. Efficiently sampling HNs could be challenging. Existing approaches either rely on ground truth labels that are not applicable in the unsupervised DR setting [28, 29] , or rely on the InfoNCE loss [30] which is less useful for NEG losses. We select mid-near (MN) pairs for HN sampling (for the opposite purpose they are used in PaCMAP, where they exert attractive forces). A MN point for point i is identified through the following process: 1) sample h ∼ Uniform{1, n} points from the high-dimensional data, and 2) select the second closest point from the sampled set. Here, we use h = 6. We justify the use of MN pairs as HN samples based on two key observations. Observation 3: Using MN for HN sampling reduces the probability for false negatives. Existing DR algorithms sample the negative pairs from an (approximately) uniform distribution over all possible pairs. While this approach enhances computational efficiency, it often results in false negatives, which is known to be problematic for contrastive learning [31, 30] . We show that MN pairs are ideal candidates for negatives as they rarely become false negatives.Algorithm 1 Simplified Pseudocode for ParamRepulsor Require:X, n N B , n M N , n F P , n epochs , f θ , η, bsz, w N B , w M N , w F P 1: Initialize neural network projector f θ with parameter θ 2: for i ← 1 to N do for batch ← 1 to n batches do 7:Sample x = x 1 . . . , x bsz from training data, x N N = N N (x 1 . . . , x bsz ) from nearest neighbors of each point in x, x M N = M N (x 1 . . . , x bsz ) from mid-near points (see Sec.4). Sample x F P = F P (x 1 . . . , x bsz ) from uniform distribution.8: Calculate y = f θ (x), y N N = f θ (x N N ), y M N = f θ (x M N ), y F P = f θ (x F P ). 9: L = 0. 10: for k ← 1 to b do 11: L = L + w N B t=1...n N B d2(y k ,y N N t k ) 10+d2(y k ,y N N t k ) -w M N t=1...n M N d2(y k ,y M N t k ) 1+d2(y k ,y M N t k ) - w F P t=1...n F P d2(y k ,y F P t k ) 1+d2(y k ,y F P t k ) .12:end for 13:Calculate gradients ∇ θ L.Update parameters θ using Adam optimizer.end for 16: end for 17: return f θ (X) Theorem 4.1. The probability that a sampled MN point is a false negative in a dataset of size n converges to 0 at a rate of O( 1n 2 ). Corollary 4.2. MN points are less likely to be false negatives than uniformly sampled points in datasets with n ≳ 10 3 . See Appendix E for empirical results and Fig. 21 in Appendix E for projection.Proof: see Appendix E. Theorem 4.1 and Corollary 4.2 state that the likelihood for an MN to be a false negative is low. Furthermore, the simplicity of MN sampling ensures efficiency: the sampling cost is still constant for each mid-near point.Observation 4: MN pairs are challenging negatives that provide better gradients for local structure preservation. The shallow parametrization used in NE DR methods ensures that distances in the high-dimensional space remain correlated with those in the low-dimensional embedding. As shown in Fig. 3 , in the blurred boundaries of clusters "3" and "8," MN pairs tend to be closer than normal FP pairs in the embeddings of all methods (see Fig. 22 in App. H.1 for other methods). This proximity makes MN pairs challenging negatives for the algorithm, resulting in large gradients during the loss calculation. Fig. 4 illustrates the representations learned by repulsing MN hard negatives. Our approach improves the boundaries between clusters, while maintaining the proximity between close clusters. It not only achieves state-of-the-art cluster separation in parametric methods but also outperforms several non-parametric methods.  
experiments: 
 Here, we evaluate the performance of our ParamPaCMAP and ParamRespulsor algorithms empirically. To contextualize our findings, we juxtapose our results against those obtained from other contemporary parametric DR algorithms. Visualization for the embeddings generated by all algorithms can be found in App. C.Datasets. We use a wide-ranging collection of datasets across various disciplines. For image analysis, we analyzed the MNIST [15] and Fashion-MNIST (F-MNIST) [32] datasets, along with COIL-20 [33] and COIL-100 [34] . In the domain of computational biology, our assessment leveraged single-cell RNA-sequencing (scRNA-seq) datasets from studies by [35] , [36] , [37] , [38] . Further diversifying our dataset selection, the 20 Newsgroups (20NG) [39] text dataset was included for textual data analysis. The preprocessing of scRNA-seq datasets adhered to the methodology outlined by [40] . Additionally, simulated datasets featuring predefined known structures -such as Circle, Mammoth [41, 42] , Gaussian Lineage, and Gaussian Hierarchical [43] -were integrated into our analysis. See Section G.1 for more details. This multifaceted dataset compilation enables a thorough examination of the DR algorithms' performance across a spectrum of datasets.Algorithms. Besides the two algorithms we proposed in this work, ParamPaCMAP (P-PaCMAP) and ParamRepulsor (P-Rep), we also perform experiments on other recent Parametric NE algorithms: Parametric UMAP (P-UMAP) [17] , Parametric Info-NC-t-SNE (P-ItSNE) [18] , Parametric Neg-t-SNE (P-NtSNE), and Parametric NCVis (P-NCVis) [24, 18] . Besides NE algorithms, we also compare against Geometric Autoencoder (GeoAE) [44] , an autoencoder-based DR algorithm. While we note that there are many other parametric DR algorithms, they either aim to serve as an intermediate representation for downstream tasks (i.e., not visualization) [45, 46] , or focus only on image dataset only [1] . We refer readers to Section 6 for more details. We compare these algorithms on local and global structure preservation. For each algorithm, we use the hyperparameter settings and the network structure suggested in their implementation. Coincidentally, all the parametric algorithms in our experiment (except for GeoAE) are equipped with a 3-layer 100-neuron fully-connected neural network as their parametric projector f θ .Other setup. For each experiment, we ran each DR algorithm 10 times using different random seeds to obtain 10 embeddings. We report the average metric measured across these 10 embeddings, highlighting the highest value in bold. An independent t-test with a significance level of p = 0.05 was conducted to assess significant differences between methods. Metrics not significantly different from the highest value are in italics.We first look into the local structure of the embedding, which examines DR algorithms' ability to discover the cluster structure. Following previous works [47, 48, 13, 43] , we evaluate local structure using three approaches, with results below. All visualizations can be found in App. C. We achieve state-of-the-art performance in local structure preservation.Local Structure 1: k-NN Accuracy. Here, DR is performed and the labels are revealed afterwards. A k-NN model then classifies points in the DR projection, with its accuracy as the metric of interest. We perform leave-one-out cross validation, and utilize a k-NN classifier to predict the label of the point. For embedding data with good local structure, points that belong to the same class should be close to each other, which would yield a higher k-NN accuracy. In this study, we use k = 10. Table 1 presents the 10-NN accuracy of each DR algorithm. ParamRepulsor achieves the highest accuracy on 10 out of 14 datasets and comes close to the highest accuracy on the remaining datasets, demonstrating its strong performance in preserving local structure.Local Structure 2: SVM Accuracy. Table 2 in App. H.3 illustrates the SVM accuracy, estimated using 5-fold cross-validation with an SVM classifier. ParamRepulsor achieves the highest accuracy on 9 out of the 14 datasets and achieves near-highest accuracy on the remaining datasets. These results demonstrate that ParamRepulsor attains state-of-the-art performance in preserving local structure.Local Structure 3: Nearest Neighbor Kept. We further evaluate the ability of DR methods to maintain high-dimensional k-NN in the low-dimensional space. We use k = 30 to provide a more robust estimate of neighborhood preservation ability. Using a larger k = 30 value ensures that even if the first nearest neighbor in the high-dimensional space is placed as the tenth nearest neighbor in the embedding, it is still considered preserved. This approach mitigates the effects of the reduced dimensionality of the embedding, where small shifts can otherwise result in the loss of neighborhood relationships. Table 3 in App. H.3 demonstrates that ParamRepulsor achieves the highest accuracy on 10 out of 14 datasets and nearly the highest on 3 others, showcasing its strong performance in preserving local structure. Additionally, our implementation of ParamPaCMAP performs comparably to the best methods on all but 2 datasets.We evaluate global structure by evaluating the preservation of cluster-level triplet relationships. Cluster-level triplet relationship preservation is important, particularly for computational biologists performing lineage analysis. Following [43] , the metric for this is a Spearman (rank correlation). To compute it, we take one cluster centroid c and rank all other centroids based on low-dimensional distance to c. We also repeat this for all C cluster centroids and place these rankings in a single vector. We repeat the process for the high-dimensional space and place these rankings in another vector. The Spearman correlation between these two vectors is the result, shown in Table 4 in App. H.3. Out of the 14 datasets, ParamPaCMAP achieves the highest correlation on 5 of them, whereas ParamRepulsor achieves the highest on 4. These results suggest our ideas are powerful for global structure preservation. 
related work: 
 The evolution of DR algorithms can be broadly categorized into two distinct phases. In the initial phase, the focus was on the development of methods that preserved only global structure. Key techniques in this category include Principal Components Analysis (PCA) [49] , Multidimensional Scaling [50] , and Non-negative Matrix Factorization [51] . While these methods effectively maintain the global layout of the data, their primary limitation is that they often fail to retain the inherent neighborhoods and clusters of the data.Subsequent DR methods were developed to address the shortcomings by emphasizing the preservation of local structure, specifically focusing on preserving k nearest neighbor relationships in the original dataset. These local methods, such as Isomap [52] , Local Linear Embedding (LLE) [53] , Laplacian Eigenmap [54] , and more recent Neighborhood Embedding (NE) algorithms like t-SNE [10] and UMAP [12] , are particularly adept at maintaining cluster structure. However, they may not adequately preserve the overall spatial layout of clusters. NE methods are more frequently used because they show clusters and manifolds in the high-dimensional space that are difficult to see any other way.NE methods are typically non-parametric, creating a low-dimensional embedding that maps each data point to a location in 2D, but there does not exist a function that maps from the original (highdimensional) space to the embedding space. To map new points to the low dimensional space, one typically creates a nonparametric map from high to low dimensions that places new points near their high-dimensional neighbors (assuming one does not want to rerun the algorithm when adding new points). This approach creates crowding problems, where many high-dimensional points map to the same location in low dimensions.To address the challenges posed by non-parametric NE algorithms, parametric NE algorithms have emerged as an effective solution. These algorithms focus on learning a function that maps data from a high-dimensional space into a low-dimensional embedding, typically using a neural network.Examples of this approach include the Multi-layer Perceptron based Parametric t-SNE [16] , DEC [55] , kernel t-SNE [56] and Parametric UMAP [17] . Furthermore, recent advancements have integrated concepts from Contrastive Learning and Representation Learning, with significant contributions from TopoAE [57] , GeoAE [44] , t-SimCNE [1] , and Parametric InfoNC-t-SNE [18] .Recently, [13] , [1] and [18] discussed the effect of the loss function forces in NE algorithms. Our work differs from them; in our work, we discuss the effect of parametrization, which is not discussed in previous works.Learning from Hard Negatives has proven effective in supervised learning [28] , metric learning [29] , as well as contrastive learning [30] . To the best of our knowledge, our work is the first that explores the effect of Hard Negative Mining in dimensionality reduction.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Experimental setting is disclosed and can be found in our implementation.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
discussion and limitations: 
 Parameterization of DR methods has major practical advantages. It allows for new data to be mapped directly from the high-dimensional space to the low-dimensional space by a function. We introduced a new method called ParamRepulsor, which demonstrates enhanced preservation of local structure without compromising global structure metrics, making it applicable across a broad spectrum of scientific inquiry.We note that our method also exhibit limitations. Although ParamRepulsor outperforms Parametric UMAP in terms of speed, it requires more computational time than Parametric Info-NC-t-SNE. Other open questions that are not resolved by this work include the design of evaluation metrics that better reflect performance, and choosing the optimal architecture for both preservation and generalization.A Discussion on the Depth of of Neural Network Projector show that further increasing the number of layers beyond increasing the number of layers beyond three yields only diminishing and negligible improvements in local structure on all three methods. Fig. 5 shows the effect of further increasing the number of hidden layers beyond three in the neural network projector for Parametric Info-NC-t-SNE (P-ItSNE) [18] , UMAP (P-UMAP) [17] , and PaCMAP (P-PaCMAP). P-ItSNE receives little benefits from further increasing layers, while P-UMAP and P-PaCMAP do not receive any further improvements. The magnitude of local structure accuracy increase is rapidly diminishing, and the visual effect is still suboptimal compared to their non-parametric counterpart.B Discussion on the Hyperparameter settings of Parametric DR algorithm In this section we provide visualizations for the output of all DR methods. Fig. 7 visualizes the output of ParamRepulsor. Notably, ParamRepulsor performs well on all datasets and achieves state-of-the-art on both local and global structure preservation. On MNIST, ParamRepulsor is the only parametric algorithm that separates the clusters with clear boundaries. Compared to nonparametric algorithms, ParamRepulsor has better global structure preservation, as it is able to keep the structure of the mammoth on Mammoth dataset, and keep the structure of the hierarchy on the Hierarchy dataset. Recall that the NEG loss follows the formEQUATION)where m is the number of negative samples of each batch and q θ is the similarity function defined in the low dimensional space. Now, we consider the PaCMAP loss. While the PaCMAP loss optimization process involves three stages with different emphasis on the loss terms, the first two stages are essentially equivalent to the early exaggeration used in t-SNE and UMAP [13] . Therefore we consider only the last stage of the PaCMAP optimization process that involves only the NN and FP losses:EQUATION)While PaCMAP samples the repulsion using a pre-defined set of further pairs, the further pairs themselves are uniformly sampled from all the points that are not nearest neighbors. The number of neighbors are usually tiny compared to the size of the dataset. In our experiments, adding the nearest neighbors back to the further pairs candidate set does not generate any major impact to the datasets. Therefore, here we consider it to be essentially the same as sampling from ij ∈ E.Since the purpose of the loss function is to find θ that minimizes it, applying any affine transformation will not affect the optimum. Recall that in PaCMAP, the set F P is m times of the size of N N . Thus, we have:EQUATIONEQUATIONDue to the different choices of normalizing constant in the NN loss and the FP loss, the PaCMAP actually utilizes a different kernel to model the similarity between the NN and FPs. Solving for the functions q N N θ and q F P θ , we have the result:EQUATIONEQUATION)E Proof that the Mid-Near Hard Negative False Negative Rate converges to 0 quadraticallyFor simplicity, we consider a dataset of size n + 1, so that each point will sample from a pool of n points. For each point, we consider its k = 10 nearest neighbors as its positive points, and the rest of the points as negative points. Now, we consider the mid-near sample process. Recall that the mid-near point samples the second closest point from a pool of 6 points. Denote the event that a mid-near point being a false negative as A. A essentially means that there exist more than one point from the k nearest neighbors being sampled. Therefore, we know that Ā means there is at most one point in the samples comes from the k nearest neighbors, which essentially gives us:EQUATIONAll points sampled are not NNEQUATIONOnly one point comes from NN (19)EQUATION)It follows that lim n→∞ P( Ā) = 1, and it converges at the rate of O( 1 n 2 ). Because P(A) = 1 -P( Ā), we know that P(A) also converges to 0 at the rate of O( 1n 2 ). This is much faster than the uniform sampling. For uniform sampling, the false negative probability is always 10 n , which is linear. This is particularly bad for DR algorithms: the number of negative samples is usually linear w.r.t. n. Fig. 21 illustrates the probability of false negatives sampled from a dataset. We found that as long as we have more than 1330 points in our dataset, mid-near sampling can generate less false negatives than uniform sampling. This is a particularly small number to achieve in the era of big data. In order to faithfully reflect the impact of parametrization on the embedding, our baseline parametric PaCMAP is written in a way to keep as much detail unchanged from the non-parametric version.ParamRepulsor implementation is written based on the Parametric PaCMAP, but many changes are made to enhance the performance on local structure.Network Structure. In line with existing parametric DR method implementation [17, 18] , we parametrize the projector with a shallow Multi-layer Perceptron (MLP). Unless otherwise specified, we utilize a network of three hidden layers with [100, 100, 100] neurons. ParamRepulsor utilizes SiLU as the activation function, whereas ParamPaCMAP utilizes ReLU just as the other methods.Besides utilizing basic MLP as the projector, both ParamRepulsor and ParamPaCMAP can use other network structures. We provide implementation for MLP with residual connection, convolutional neural networks, We also allow using an embedding layer as the projector so that the network behavior is similar to non-parametric version.Initialization. As a non-parametric algorithm, PaCMAP directly optimizes the low-dimensional embedding, and utilizes the first two principal components of the data as its initialization. After the introduction of the neural network projector, we can no longer use this initialization. For both ParamRepulsor and ParamPaCMAP, we initialize all our neural network parameters with Kaiming Initialization [61] .Optimization Schedule. Since our neural network optimization schedule is performed by minibatch stochastic gradient descent, we are unable to optimize the full embedding at once as in non-parametric PaCMAP. Therefore, at each step, we sample a batch of points, and find NN, MN, and FP points for each element in the sample.All the points sampled will be sent to the neural network to calculate the standard PaCMAP loss. We adopt the Adam Optimizer [62] with β = (0.9, 0.999) and a batch size of 1024. Refer to the algorithm below for more details.G.1 Datasets Used MNIST. MNIST [15] is a hand-written digits dataset containing 70,000 grayscale images of the shape 28×28. The images are flattened.F-MNIST. Fashion-MNIST (F-MNIST) [32] is a dataset containing 70,000 grayscale fashion images of the shape 28×28. The images are flattened.USPS. USPS [63] is a dataset containing 9298 written digit images of the shape 16×16. The images are flattened.The COIL-20 [33] dataset is a is a database of 1440 gray-scale images of 20 objects. The images are flattened.The COIL-100 [34] dataset is a is a database of 7200 color images of 100 objects. The images are flattened.The 20NewsGroup [39] dataset contains about 18000 newsgroups posts on 20 topics. We utilize scikit-learn [64] TF-IDF vectorizer to convert each post into a vector.Kang et al. The Kang et al. [35] dataset contains scRNA-seq data from 13999 cells and 14053 genes, with 13 types identified by scientists. The first 50 principal components from the raw data are used.Kazer et al. The Kazer et al. [36] dataset contains scRNA-seq data from 59286 cells and 16980 genes, with 7 types identified by scientists. The first 50 principal components from the raw data are used.Algorithm 2 Detailed Pseudocode for ParamRepulsor Require: X -high-dimensional data matrix of the shape (N, D). n N B , n M N , n F P -the number of neighbor pairs, mid-near pairs, further pairs n epochs -the number of epochs for optimization p θ -neural network projector with parameter θ. η -learning rate. b -mini batch size. w N B , w M N , w F P -the weights associated with neighbor, mid-near, and further pairs at epoch t. 1: Initialize neural network projector p θ with parameter θ 2: for i ← 1 to N do 12:x N N = N N (x 1 . . . , x b ) from the nearest neighbors of x.x M N = M N (x 1 . . . , x b ) from the mid nears of x.14:x F P = F P (x 1 . . . , x b ), in which x F P k = x t , t ∼ Uniform(1, n). 15: Calculate y = f θ (x), y N N = f θ (x N N ), y M N = f θ (x M N ), y F P = f θ (x F P ). 16: L = 0. 17: for k ← 1 to b do 18: L = L + w N B t=1...n N B d2(yi,y N N t i ) 10+d2(yi,y N N t i ) -w M N t=1...n M N d2(yi,y M N t i ) 1+d2(yi,y M N t i ) - w F P t=1...n F P d2(yi,y F P t i ) 1+d2(yi,y F P t i ) . 19:end for 20:Calculate gradients ∇ θ L.Update parameters θ using Adam optimizer.end for 23: end for 24: return f θ (X) Muraro et al. The Muraro et al. [37] dataset contains scRNA-seq data from 2282 cells and 18962 genes, with 9 types identified by scientists. The first 50 principal components from the raw data are used.Stuart et al. The Stuart et al. [38] dataset contains scRNA-seq data from 30672 cells and 17009 genes, with 25 types identified by scientists. The first 50 principal components from the raw data are used.Circle The Circle dataset comprises of 5000 points uniformly sampled from a 2D circle with radius 1. The circle is divided into ten arcs of the same length, and each point receives a label that represents the index of the arc it belongs to.Mammoth The mammoth dataset [42, 41] contains 10k points from a 3D woolly mammoth skeleton.Lineage The Gaussian Lineage dataset [5, 43] contains 10000 points in twenty 50-dimensional Gaussians, equally separated on a line.Hierarchy The Gaussian Hierarchical Dataset [43] contains 12500 points. The points belongs to 125 micro clusters, arranged into 5 macro and 25 meso clusters. Each micro cluster includes 100 observations.All experiments are conducted with an Exxact TensorEX 2U Server with 2 Intel Xeon Ice Lake Gold 5317 Processors @ 3.0GHz. We limit the RAM usage to be 32GB. Parallel computation are performed over a single Nvidia RTX A5000 GPU.Fig. 22 provides a comprehensive analysis over distances between different kinds of pairs, generated by multiple DR algorithms. We can see that all parametric methods generate a shorter FP distance compared against their non-parametric counterpart. MN pairs, though should be classified as FPs, tend to be harder to optimize, resulting in a shorter distance on average. As datasets grows larger, scalability becomes more important. We evaluate the time consumed by ParamInfo-NC-t-SNE, ParamRepulsor and ParamUMAP on two extremely large datasets, from [65] and [4] . The dataset sizes are 1, 306, 127 and 2, 058, 652, respectively. The results are shown in Figure 23 . We can see that ParamRepulsor outperforms ParamUMAP in terms of scalability. While ParamRepulsor is slower than ParamInfo-NC-t-SNE, the speed is still comparable in terms of magnitude. We note that ParamInfo-NC-t-SNE utilizes smaller number of epochs, which gives it a higher speed, but at the cost of an underoptimized embedding, as shown in Section 5. The computational efficiency of ParamRepulsor can be further improved by a better optimization schedule as well as computational improvements, which we leave for future works. Table 2,  3, 5, 4 measure the SVM accuracy, k-nearest neighbor preservation ratio, Triplet preservation ratio, and cluster centroid distance correlation. We note that GeoAE performs particularly well on Triplet preservation. This is expected: as an autoencoder-based method, GeoAE aims to preserve the geographical distance information in the high-dimensional space, usually at the cost of the local structure. As a result, its local structure performance is particularly low. However, our method, ParamPaCMAP and ParamRepulsor, achieve comparable result on this metric. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: We conduct multiple rounds of experiments and performed t-test over the results to ensure statistical significance.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: There is no specific societal impact of the work. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The paper does not pose such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: Existing assets are properly cited and we also provide details on dataset and implementation used in the appendix.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: The paper presents a well-motivated problem and introduces a decent technical contribution with new methods. It also provides thorough experimental evaluation to support the claims made. The reviews are largely positive, with the exception of Reviewer bihR, who raised several concerns. I believe the authors have addressed these concerns as comprehensively as possible. Given the positive reception from the other reviewers, I recommend a  **weak accept** for this paper.

Reviews: review: paper_summary: paper_summary: The paper addresses the problem of improving parametric neighborhood embedding (NE) methods -- i.e., techniques that optimize a neural network to project a higher dimensional dataset into a lower dimensional space. The main advantage of these being that they don't have to be recomputed for new samples, as it only involves a projection through the pre-trained encoder. However, they are generally inferior to the traditional NE techniques, the paper argues,   mainly because of failing to repulse negative pairs effectively. To address this issue, they propose a method that explicitly factors in an unsupervised hard negative mining cost, to achieve good balance of local and global structure preservation.
strength_weakness: strength_weakness: * One high level comment is that some of the experiments feel incomplete in terms of answering the main hypothesis put forward -- why parametric methods under perform their non parametric counterparts. The paper identified an issue that most parametric methods suffer from -- lack of negative pair repulsion -- and addressed it using mid-near sampling. Does this make the proposed ParamRepulsor or P-PACMAP comparable or better than existing non parametric methods? The experiments only compare parametric methods so this question remains unanswered. 
* The ablation from Figure 4 on the effect of weight on MN sampling clearly shows a preference for local structure preservation as it is increased -- how does this affect global structure? Every NE algorithm has some form of parameter to trade-off between these two properties. For a fair comparison, they should be ablated together to understand the relative sensitivity of the algorithms towards global and local structure preservation.
* MN Sampling utilizes uniform random sampling in high dimensions to identify hard negatives, and finds nearest neighbors presumably using an L2 like metric. I see some issues with these assumptions on data that is locally Euclidean but lives on some unknown curved manifold. Uniform sampling in high dimensions is challenging, and an L2 metric becomes inaccurate very quickly -- does the effect of hard negatives disappear as the dimensionality increases? Ablations on these properties will help the reader understand the limitations more clearly.
questions: questions: Please see above
limitations: limitations: Limitations of the proposed method are not entirely clarified -- rather limitations of the field in general are discussed. I think this could be expanded as I have suggested in my comments.
paper_summary: paper_summary: The paper tackles the problem of Dimensionality Reduction (DR). The authors flag a problem with the current existing parametric DR methods. It is shown with empirical evidence that parametric methods cannot capture all the local details. To mitigate this problem, the paper presents ParamRepulsor, a new parametric method that utilizes Hard Negative Mining. Empirical results show that ParamRepulsor performs strongly against the previously proposed baselines.
strength_weakness: strength_weakness: See below
questions: questions: - What is the computational time of ParamRepulsor compared to the other methods?
- What are the limitations of ParamRepulsor?
limitations: limitations: NA
paper_summary: paper_summary: Authors study the effect of parameterization in neighbor embedding algorithms. They aim to improve how these methods capture local structure in the data. To do so they propose a new algorithm building upon PaCMAP with slight modification of its loss with new weights in front of each term.
strength_weakness: strength_weakness: I am disappointed that this work does not really dive into the effects of amortization on neighbor embeddings. I was expecting more discussions on the effect of batch size, initialization, learning rates etc... Many discussions here also seem to apply to the non parametric setting, we often have the impression to move away from the initial focus of this work. The problem at hand is not correctly introduced in section 3 which makes the paper unclear to follow and understand. Here are some issues:

* the sampling procedure to obtain mid-near pair is taken from PACMAP is not a new contribution. 
* it would be helpful to state more clearly the difference between the proposed objective and the one of PACMAP. From what I understand it amounts to switching the sign of the mid-near term from attraction to repulsion. To me it not clear at all how is this change related to parameterization. It would be interesting to see how the new loss function would perform in the non-parametric setting as well. 
* About observation 2 in section 3, it is stated that NEG based methods perform better in local structure preservation and : *This is in contrast to both NCE and InfoNCE losses, where each negative pair term is based on all pairs.* . However, reading through : https://arxiv.org/pdf/2206.01816 , I have the understanding than even NEG based algorithms sample negatives pairs uniformly in all pairs. Therefore this point is not clear to me. Also I am wondering why it is related to the parametric setting and not non-parametric as well.
* In the experimental part it would also be interesting to compare with non parametric methods which are expected to perform better. This way we could measure how does this paper contribute to closing the gap between parametric and non parametric.
* one major drawback of this approach is that there are too many hyperparameters to tune with all the weight terms in the loss. Looking at the code we have : `def paramrepulsor_weight_schedule(epoch):
    if epoch < 200:
        w_nn = 4.0
        w_fp = 8.0
        w_mn = 0.0
    else:
        w_nn = 1.0
        w_fp = 8.0
        w_mn = -12.0
    weight = np.array([w_nn, w_fp, w_mn])
    return weight`. How were these values determined ? do they need to be tuned for each dataset ? From the practitioner point of view, I have strong doubts about the practical utility of such machinery.

More minor comments:
* false negatives should be clearly defined before theorem 4.1 .
* theorem 4.1 is an asymptotic result thus it doesn't bring true insights about practical guarantees of the methods.
* I wouldn't put Corollary 4.2. in the form of a corollary as there is no associated proof.
questions: questions: * in the observation 1 section 3 :  *all the parametric counterparts (App. F.1) have a smaller FP distance ratio, meaning further pairs are positioned closer together* . Woul you have more insights on why this phenomenon happen ? how robust is this observation to batch size, learning rate and architectures used ?
* Do observation 3 and 4 also apply in the non-parametric setting ? Could you discuss more the effect of parametrization on these.
* in algorithm 1 we can see that the kNN graphs are constructed once at the beginning. Would there be a way to adapt this construction to the online setting *i.e.* to easily update these graphs during iterations?
* did the authors consider using entropic affinity graphs as in TSNE instead of binary kNN graphs ? these affinities can be seen as smooth kNN graphs and they are usually faster to compute that kNN on GPUs as they are highly parallelizable.
limitations: limitations: /
paper_summary: paper_summary: The paper focuses on comparing parametric and non-parametric neighborhood embedding methods for dimensionality reduction. Non-parametric methods excel at preserving local data structures but struggle with large datasets. Parametric methods, utilizing neural networks, offer better scalability but often compromise local structure preservation. The paper reveals that parametric methods tend to prioritize global structure preservation at the expense of local details, leading to less distinct cluster boundaries. This is attributed to their inability to effectively repulse negative pairs and sensitivity to the choice of loss function. 

To address these issues, the authors propose a new parametric method called ParamRepulsor with two key improvements:

Hard Negative Mining: This technique focuses on identifying and repulsing the most challenging negative pairs, improving the separation between dissimilar points.
Modified Loss Function: The authors use a loss function that applies a stronger repulsive force, particularly on hard negative pairs, leading to better local structure preservation.

In experiments, ParamRepulsor is shown to outperform other parametric methods on various datasets.
strength_weakness: strength_weakness: Limited Generalizability: The focus of this paper is on parametric DR methods that utilize shallow neural networks. However, the generalizability of the findings to other parametric models, such as deep neural networks, remains unexplored. This is particularly relevant as the paper's results indicate that all parametric methods tend to better preserve local structures, and the performance differences between algorithms diminish as network depth increases.

Insufficient Theoretical Analysis: While the paper offers empirical evidence, it lacks a comprehensive theoretical analysis. It remains unclear why the same algorithm that performs well in its non-parametric version underperforms in the parametric version (loses local structure). Although the authors acknowledge that the limited capacity of shallow neural networks is widely accepted as an explanation for their failure, they dismiss it as the primary cause.

Absence of Non-Parametric Repulsor: The paper presents both parametric and non-parametric versions for all algorithms except ParamRepulsor. Including a non-parametric version of ParamRepulsor would provide better intuition into how the modified terms (e.g., including MN terms) affect the results. Additionally, the paper does not theoretically analyze why hard negative mining and the specific loss function are effective.

Limited Practical Impact/Advantage: While the paper demonstrates the superior performance of ParamRepulsor compared to other parametric methods in the shallow network case, this advantage might not be significant when deeper networks are used. This limitation could potentially reduce the practical impact and contribution of this work.

Evaluation Metrics: The evaluation metrics used in the paper, although standard in the field, may not fully capture all aspects of dimensionality reduction quality, especially for complex datasets.
questions: questions: Network Depth and Embedding Structure: The paper exclusively focuses on shallow neural networks for parametric dimensionality reduction. It would be valuable to understand the rationale behind this choice. Is there a risk of overfitting with deeper networks? The authors mention that "The shallow parametrization used in NE DR methods ensures that distances in the high-dimensional space remain correlated with those in the low-dimensional embedding." Investigating how the embedding structure changes with increasing network depth could provide valuable context for interpreting the results of this work.
limitations: limitations: While the authors transparently acknowledge certain limitations, such as the need for further theoretical analysis and computational optimization of ParamRepulsor, other significant limitations remain unaddressed.

The paper's exclusive focus on shallow networks limits the generalizability of its findings. The authors do not provide a clear rationale for this choice, nor do they explore the impact of network depth on the preservation of local structures. This is particularly important given the observation that deeper networks might naturally mitigate the issues observed with shallow parametric models.

Suggestions to enhance the impact and relevance of this work:

Expanding the scope: Investigate the behavior of ParamRepulsor and other parametric methods with deeper networks.
Developing Non-Parametric Repulsor: Create a non-parametric version of ParamRepulsor for direct comparison and to isolate the effect of the proposed modifications.
Deeper Theoretical Analysis: Conduct a more in-depth analysis to understand the underlying reasons for the performance differences between parametric and non-parametric methods and the impact of network depth on local structure preservation.

Comments: title: Thank you for your response
comment: I thank the authors for the clarification and the extra figures in their response.  I'm raising the score to 6.
Thank you sincerely for taking the time to reassess our paper and for raising the score. We really appreciate your feedback and will revise our paper accordingly! Your input is invaluable to us.
Thanks for the responses. I will raise my score to 6. Only one comment regarding the confusion about parametric/non-parametric method formulation -- it maybe helpful to formulate the paper slightly differently instead of the current argument on introducing non-parametric --> parametric and then introducing the proposed method while this is the technical argument, i think the introduction can be built to emphasize on parametric methods only to avoid confusion.
> I have personally implemented and experimented with these algorithms and have also taught them to students on numerous occasions. This experience has led me to understand that PACMAP fundamentally involves three components for near, mid-near, and farther points, which is why I find it requires more tuning than other methods. Each component comes with its own sampling and weighting schedule.

We respectfully emphasize that this work is entirely distinct from PaCMAP, and we believe that any **previous biases related to an existing work** should not influence the evaluation of this new work. As noted in our previous response, our approach does not involve more tuning, as reflected in our codespace. It’s important to highlight that, as shown in [A], methods like t-SNE and UMAP often require significant hyperparameter tuning. In contrast, all our experiments were conducted using default parameters across all datasets, as reported in our rebuttal.

> "They can also handle global structure better than the non-parametric methods." There’s no basis for this claim.

We respectfully disagree with the assertion that there is no basis for our claim. We have provided specific experimental results, particularly in Table 1 and Fig. 4 in the rebuttal PDF, as well as Table 4, 5, and Fig. 5-18 in the original submission. These results clearly demonstrate the better preservation of our method and parametric methods in general in handling global structures. We kindly hope you had the opportunity to thoroughly review our rebuttal, and we are open to further clarifying or expanding upon these findings if needed. 

> "This is particularly beneficial in longitudinal studies, such as those in computational biology or recommendation systems, where the position of new data in an established embedding space is of significant interest." I strongly believe that statistical analysis should not be conducted based on such parametric embeddings. Non-parametric methods should be approached with caution, and I am convinced of the importance of considering different perspectives with various initializations, learning rates, and attraction/repulsion trade-offs. For this reason, I encourage students to compute multiple embeddings, whether using t-SNE, PACMAP, or any other method.

We hope the reviewer can provide more substantial arguments and evidence to support the belief that parametric embedding cannot be applied to parametric embeddings other than personal anecdotes. This is not the consensus of the scientific community. As we mentioned in the previous reply, statistical analysis has already been conducted with parameterized embedding and has inspired scientific discoveries, such as [E, F, G, H, I]. 



[E] Ding et al. "Interpretable dimensionality reduction of single cell transcriptome data with deep generative models." Nature Communications 2018

[F] Lopez et al. "Deep generative modeling for single-cell transcriptomics." Nature methods 2018

[G] Kulichenko et al. "Uncertainty-driven dynamics for active learning of interatomic potentials." Nature Computational Science 3.3 (2023): 230-239.

[H] Wahle et al. "Multimodal spatiotemporal phenotyping of human retinal organoid development." Nature Biotechnology 41.12 (2023): 1765-1775.

[I] Islam et al. "Revealing hidden patterns in deep neural network feature space continuum via manifold learning." Nature Communications 14.1 (2023): 8506.
Thank you for your response, though I feel the tone could have been more respectful. To clarify, I’d like to briefly summarize my point.

I have personally implemented and experimented with these algorithms and have also taught them to students on numerous occasions. This experience has led me to understand that PACMAP fundamentally involves three components for near, mid-near, and farther points, which is why I find it requires more tuning than other methods. Each component comes with its own sampling and weighting schedule.

Moreover I would like to insist on some points that I believe are incorrect and potentially very misleading:

- "They can also handle global structure better than the non-parametric methods." There’s no basis for this claim.
- "This is particularly beneficial in longitudinal studies, such as those in computational biology or recommendation systems, where the position of new data in an established embedding space is of significant interest." I strongly believe that statistical analysis should not be conducted based on such parametric embeddings. **Neighbor-embedding methods should be approached with caution**, and I am convinced of the importance of considering different perspectives with various initializations, learning rates, and attraction/repulsion trade-offs. For this reason, I encourage students to compute multiple embeddings, whether using t-SNE, PACMAP, or any other method.

Thank you for the discussion. I will not further discuss with authors.
> From my experience, the methods that gain practical adoption are those that are straightforward to implement and easy for practitioners to grasp, minimizing the use of tricks and adhering to core principles. This is especially true in unsupervised learning, where evaluating model performance is difficult. While simplicity might come at the cost of slight performance trade-offs on the toy datasets often used in ML research, principled methods tend to perform better on real-world datasets encountered by practitioners.

We agree. PaCMAP’s loss function is much simpler than t-SNE’s or UMAPs. It performs better in our experiments, which you agree to be of “rich variety of datasets and metrics” and “make sense” in your review.

> TSNE is a prime example, consistently delivering state-of-the-art results across a wide range of datasets. Similarly, LargeVis, which extends TSNE with negative sampling, is another method that is accessible to ML practitioners.

> The paper in question takes the opposite approach, which is why I believe it does not contribute value to the field of dimensionality reduction.


There is clearly not much we can say to convince you. 

While we respect the contributions of t-SNE and LargeVis, we believe it is important to highlight that **newer methods**, such as PaCMAP, **offer significant advantages** in terms of maintaining global structure and simplifying the tuning process. It is not accurate to assert that older methods inherently provide superior results. In fact, PaCMAP's simpler loss function and ability to preserve global structure without extensive tuning have been key factors in its growing adoption.

**We also reject the idea that LargeVis as a method is accessible to ML practitioners.** Its official implementation
1. has not been maintained for more than eight years from now,
2. needs to be compiled from scratch,
3. requires platform-specific handling, and 
4. does not provide a user-friendly interface that’s compatible to popular ML frameworks, such as scikit-learn. 

On the other hand, our method instead is fully compatible with existing ML frameworks such as scikit-learn and pytorch.

We also believe that parametric methods play an essential role in the field of dimensionality reduction. [C, D] have all garnered hundreds of citations and have inspired various scientific discoveries. We deeply regret your bias towards the parametric DR embeddings.

[C] Van Der Maaten L. Learning a parametric embedding by preserving local structure, AISTATS 2009: 384-391.
[D] Sainburg, Tim, Leland McInnes, and Timothy Q. Gentner. "Parametric UMAP embeddings for representation and semisupervised learning." Neural Computation 33.11 (2021): 2881-2907.
> Lack of theoretical support for the method.

> In my view, this method adds unnecessary complexity and introduces numerous steps without sufficient justification. The arguments seem to rely more on intuition than on solid theoretical backing.

We’re not sure what you mean by “theoretical backing”. It’s hard to respond to criticism of this abstract. We provided theoretical backgrounds with the theoretical principles for loss functions in our rebuttal. It's important to note that many widely-used methods in this field, such as t-SNE, are based on **assumptions** rather than strictly theoretical foundations. For instance, there is **no definitive theory** that mandates the use of heavy-tailed Student-t distributions to represent probabilities in low-dimensional space, yet this assumption has proven effective in practice.

> As a practitioner, I already find PACMAP challenging due to its numerous parameters, and this approach seems to further complicate the field unnecessarily. I strongly disagree with the authors' assertion that other methods have similar parameter complexity.

With all due respect, we must strongly disagree with the assertion that PaCMAP presents excessive parameter complexity. PaCMAP is specifically designed to minimize the need for user intervention in parameter tuning. Its **default parameters** work fine for a wide range of datasets, providing a robust and reliable embedding without requiring the extensive tuning that is often necessary with methods like t-SNE and UMAP. These methods, while powerful, can indeed struggle [B] with preserving global structure unless carefully tuned—an issue PaCMAP addresses effectively.

This statement also raises the question of **whether the reviewer has really looked into the implementation of any DR method** as well. Every ML algorithm has lots of parameters, including the DR methods. Even simple algorithms such as k-nearest neighbor methods have parameters - what is the form of the distance metric, how many neighbors, etc. The most popular t-SNE implementation, [openTSNE](https://github.com/pavlin-policar/openTSNE), provides **20** different tunable parameters. [UMAP](https://github.com/lmcinnes/umap) has **27** different tunable hyperparameters. These numbers do not account for the various schedules and automatic hyperparameter selection mechanisms embedded within these implementations. When considering the parametric versions of these methods, the number of hyperparameters increases significantly.

[B] Kobak et al., "The art of using t-SNE for single-cell transcriptomics." Nature Communications 10.1 (2019): 5416.
> The motivations for parametric neighbor embedding are unclear.

> Neighbor embedding algorithms are incredibly efficient. Embedding a few million points can be done in a matter of seconds on a GPU using recent implementations of TSNE or LargeVis. However, this efficiency is still far from what we see in other domains like SSL, where scalability and efficiency present interesting research directions. This leads me to question the importance of developing parametric methods for neighbor embedding, particularly when practitioners typically recompute the full embeddings when new data is introduced.

> I'm curious if the authors can provide references where an amortized, differentiable model for neighbor embedding is crucial. To my knowledge, these methods are primarily used for data exploration rather than being integrated into larger pipelines that would benefit from differentiability, as is common in SSL.

> This point further limits the scope of the paper.


While we agree that nonparametric methods are indeed efficient, we believe that **efficiency is not the only criterion** to consider. Both nonparametric and parametric methods serve important roles in data exploration and analysis. In terms of uses, both nonparametric methods and parametric methods can be used for data exploration as well as analysis. However, parametric methods offer unique advantages, particularly when a map $x\rightarrow y$ between input and output spaces is needed. This capability is crucial for **comparing multiple datasets or adding new data to an existing embedding**, as demonstrated in our experiments. They can also handle global structure better than the non-parametric methods. This is particularly beneficial in **longitudinal studies**, such as those in computational biology or recommendation systems, where the position of new data in an established embedding space is of significant interest. Nonparametric methods, while efficient, lack this capability.

Furthermore, while speed is undoubtedly important, the quality of the embedding is paramount. Our work aims to achieve high-quality embeddings that serve the specific needs of the user, even if that means prioritizing aspects other than raw efficiency.

We also wish to highlight that in the code we provided, **we also support non-parametric implementations** that are compatible with both CPU and GPU, and can also achieve comparable scalability as other non-parametric GPU implementations.
We strongly disagree with the assessment of our paper. Here's our detailed reply:

> The proposed method is limited to PACMAP.

> The proposed ParamRepulsor and ParamPaCMAP are minor adaptations of the PACMAP algorithm, which is not among the most widely used neighbor embedding methods. In my view, focusing on enhancing the parametric versions of more popular algorithms like tSNE, UMAP, or LargeVis would have a much greater impact. As a result, the scope of this paper feels very limited.

With all due respect, we don’t agree with the reviewer over the contribution of our work, as well as the analysis of the scope. In this work, we have clearly demonstrated the existence of local structure preservation gaps in the parametric NE methods, provided theoretical and empirical analysis over the potential causes, and then applied our methods to create a novel parametric NE DR algorithm. As practitioners ourselves, we believe PaCMAP is more reliable, robust to parameter tuning and simpler than the methods you listed - see [A] as well as the experiment section of this work, which you also found to be “rich” and “make sense”. It also has no parameters that need tuning per dataset, unlike the older methods. Additionally, despite being a more recent method published in 2021, PaCMAP has already garnered 319 citations, a number that compares favorably to LargeVis, which has received 503 citations despite being published five years earlier. This suggests that PaCMAP is gaining significant traction within the community.

In terms of impact, we think **designing the best method** ought to have the largest impact. The focus of our work is on creating and improving methods that offer meaningful advances, and we believe that this should be the primary criterion for assessing the scope and impact of our research, **instead of what method we use as a basis**.

[A] Huang, et al. "Towards a comprehensive evaluation of dimension reduction methods for transcriptomic data visualization." Communications biology 5.1 (2022): 719.
Thank you for the rebuttal.

I still have several key concerns regarding this work:

**The proposed method is limited to PACMAP.**

The proposed ParamRepulsor and ParamPaCMAP are minor adaptations of the PACMAP algorithm, which is not among the most widely used neighbor embedding methods. In my view, focusing on enhancing the parametric versions of more popular algorithms like tSNE, UMAP, or LargeVis would have a much greater impact. As a result, the scope of this paper feels very limited.

**The motivations for parametric neighbor embedding are unclear.**

Neighbor embedding algorithms are incredibly efficient. Embedding a few million points can be done in a matter of seconds on a GPU using recent implementations of TSNE or LargeVis. However, this efficiency is still far from what we see in other domains like SSL, where scalability and efficiency present interesting research directions. This leads me to question the importance of developing parametric methods for neighbor embedding, particularly when practitioners typically recompute the full embeddings when new data is introduced.

I'm curious if the authors can provide references where an amortized, differentiable model for neighbor embedding is crucial. To my knowledge, these methods are primarily used for data exploration rather than being integrated into larger pipelines that would benefit from differentiability, as is common in SSL.

This point further limits the scope of the paper.

**Lack of theoretical support for the method.**

In my view, this method adds unnecessary complexity and introduces numerous steps without sufficient justification. The arguments seem to rely more on intuition than on solid theoretical backing.

As a practitioner, I already find PACMAP challenging due to its numerous parameters, and this approach seems to further complicate the field unnecessarily. I strongly disagree with the authors' assertion that other methods have similar parameter complexity.

From my experience, the methods that gain practical adoption are those that are straightforward to implement and easy for practitioners to grasp, minimizing the use of tricks and adhering to core principles. This is especially true in unsupervised learning, where evaluating model performance is difficult. While simplicity might come at the cost of slight performance trade-offs on the toy datasets often used in ML research, principled methods tend to perform better on real-world datasets encountered by practitioners.

TSNE is a prime example, consistently delivering state-of-the-art results across a wide range of datasets. Similarly, LargeVis, which extends TSNE with negative sampling, is another method that is accessible to ML practitioners.

The paper in question takes the opposite approach, which is why I believe it does not contribute value to the field of dimensionality reduction.

For these reasons, I am convinced that this work does not meet the bar for NeurIPS, and I am modifying my score accordingly.
Dear Reviewers,

As the discussion period is approaching its conclusion in two days, we would like to kindly remind you that we have addressed your comments in our rebuttal. We would greatly appreciate any additional feedback you may have before the deadline. If you have any further questions or concerns, please do not hesitate to reach out, and we will do our utmost to respond promptly.

Thank you for your time and consideration.

Best regards,
The Authors of Submission 13990