Navigating the Effect of Parametrization for Dimensionality Reduction
Authors: Haiyang Huang
Yingfan Wang
Cynthia Rudin
Venue: NeurIPS 2024 poster (2024)
Keywords: Data visualization
Dimensionality reduction
Primary area: interpretability_and_explainability

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.

Navigating the Effect of Parametrization for Dimensionality Reduction
Haiyang Huang" Yingfan Wang" Cynthia Rudin
Duke University
Ohyhuang, yw416, cynthia] duke. edu
Abstract
Parametric dimensionality reduction methods have gained prominence for their ability to generalize to unseen datasets, an advantage that traditional approaches typically lack. Despite their growing popularity, there remains a prevalent mis- conception among practitioners about the equivalence in performance between parametric and non-parametrie 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 pairs, 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 loss function that applies a strong repulsive force. This new method achieves state-of-the-an per- formance on local structure preservation for parametric methods without sacri- ficing the fidelity of global structural representation. Our code is available at httpss//ggituub..om///aaaaaaaa
https://githut: wwt. www.w/o/wwwoooo////o/oo htwph//aaaaaaoaaaaaeeeell.ooo
1 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 [T]. text documents [2] 3. and biological datasets [4-8]. The successes of modern DR methods mostly be attributed to neighborhood embedding (NE), which is the basis for modern DR methods [9] including I-SNE, Large Vis, UMAP, and PaCMAP [1]
13]. These algorithms aim optimize the low-dimensional layout of the data, such that the high dimensional local structure (i.c., neighborhoods) are preserved.
A major weakness of existing NE algorithms is that they struggle with adaptability to large, incre- mentally updated datasets. These algorithms depend on a K-Nearest Neighbor graph, encompassing the entire dataset, generate the embedding. Consequently, the introduction of new data necessitates a complete re- re-comuutation of the embedding, leading to significant time and computational resource demands for large datasets. Although recent adaptations have been developed optimize only the additional data 14 [3], these modifications potentially alter the original algorithm's 's objective function, thereby compromising the embedding's 's quality.
Addressing these challenges, recent developments in combining neural networks with NE algorithms have shown promise. These algorithms maintain the same objectives traditional NE methods but leverage neural networks to optimize the projection of high-dimensional data into lower-dimensional spaces [8). The integration of neural networks allows these NE algorithms 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, shown in Fig. [ despite the similarity in loss
Equual contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Info SNE
NCVIs
UNAP
PsCMAP
PeramResplior
Param Info-NC-t-SM
Param NCVIs
Param UMMP
Param PaCMAP
Figure 1: Dimensionality reduction results on the MNIST digit dataset [15] (bottom row) fail 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.
Parametric methods
functions between the non con-parmetrric 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 non- parametric methods while surpassing existing parametric approaches in preserving both local and global structure. It offers 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 comprehensive analysis of the impact of parametrization the performance of DR methods, demonstrating that it may compromise local structure. Our findings attribute this issue to insufficient repulsive forces negative pairs in the parametric setting. Notably, algo- rithms 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, 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 novel, fast algorithm that achieves excellent local structure preservation while maintaining global structure.
Fundamentals of Neighborhood Embedding Algorithms and Contrastive Learning
provide essential background on Neighborhood Embedding (NE) methods and notation. We notate the high dimensional data as X X1 X,, E RD, where is the number of data points, and is the dimension. NE algorithms aim to preserve predefined high-dimensional similarities within low-dimensional embedding to reveal the local and global structure of X. Specifically,

---

NE methods identify mapping function fo that constructs the corresponding low dimensional embedding = =Y -I..... .n. E R2, where y: fo(x;). We will use y, and fo(x.) interchangably. For nonparametric DR methods, the function So is not defined outside of x1,.... Xx, though it is possible to interpolate. For visualization purposes, d 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, Sij. is captured by a similarity function xx,, related their distance. Due to the curse of dimensionality, the Euclidean distance metric fails to accurately represent distances along the data manifold high-ding digh-eimensional spaces [19]. A common solution this issue to only consider similarities between K nearest neighbors: Sij is set to be non-zero iff x; or x; are within the K nearest neighbors of each other, where K a hyperparameter, usually 15-30.
Embedding Optimization Phase. After constructing the graph, NE algorithms try to optimize a function fe. The objective is encoded by loss function (()):
(I) where CNN denotes the loss for j.j that are similar (among the K-nearest neighbors), and LFP denotes the loss for pairs that are not nearest neighbors the high-dimensional space. Typically, LNN decreases when lyy - yylll decreases, and LFP decreases when |ly; y&llz increases. Their gradients therefore act like forces that attract or repulse the NN or FP pairs, respectively.
(0) (NNENNCNN(lJfo(x
fo(x))ll2) + EugNNCFp((If((e: -fxx))) fo(x))ll2),
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 (NCH) [21], Info-Noise
Contrastive Estimation (InfoNCH) 22 or Negative Sampling (NEG) 23
Using the framework above, we dive into details of t-SNE 10 NCVis
224]
UMAP [2] and
PaCMAP 13,, which are four major recent NE algorithms.
2.1 NCE/InfoNCE- t-SNE and NCVis
Both NCE- and InfoNCE- approaches assume the high-dimensional data similarities (the sij 's) follow an underlying data similarity pattern, represented by an unknown distribution p. These methods learn function fo that generates similar low-dimensional similarity pattern, described by a distribution g. aiming 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, must be normalized to ensure all possibilities sum up to 1. The only difference is that NCE uses logistic loss, whereas InfoNCE uses cross-entropy loss for the data distribution match.
Approximating p a Bernoulli distribution 24 with value 1 for NN pairs and O for FP pairs. Assuming that for each step in the optimization, we optimize batch that contains one NN pair and m FP pairs, 9 should minimize:
CNCE -EijeNN. ENN log
Tīj
m log 1
T
qij + E Pike
Qih +
Pike
LInfoNCE = =- -BijENN NNN NNN log log
Σ
Gis +
Pike
(3)
C= L...m
I-SNE, the most popular NE algorithm. utilizes a loss defined over the full data set. The raw t- SNE loss 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 [8] notes
that the exact values of the P.y 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]. Denoting d2(i,) = [x;))) - fo [x(x,) [x2) +
ly
ys + the t-SNE loss function can be rewritten as an InfoNCE loss:
C - SNE (0) -EGENN ENN [log dz(i,
dzli, k.) ))
log dz(i,.)
+ Σ
(4)
c=1..m
3

---

Following [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 dataset, and is challenging to incorporate that into the mini-batch parametric DR framework.
NCVis 24
uses NCE 21 loss. We denote the number of negative pairs in batch m, and set
q.j
(.))
The NCVis loss is:
1
(NC Nik NNN
log
m log
1
do(i,)) 1 Eost... (2(,,
d2(1.1)
1+ l.... dz(t,Ro)
(5)
18 provides modern implementation for both algorithms. also provides parametric versions that adopt multilayer perceptrons (MLP) with [100, 100, 100] hidden neurons and ReLU activation.
NEG-based: UMAP
Negative Sampling (NEG) 23 simplifies the modeling process. Define qu to be similarity function
the low dimensional space:
N EG (0) - EIJENN log
9.j
mBBajes log
(6)
1 qig
1 1+ 9i3
UMAP 12 is DR algorithm that utilizes the NEG loss
[8. Its loss function is
M
MMPP (MM))).)) ) mm NNNN log
(1+ 1
C CUMAP (0) EIjENN log
g MMMP (1.5) (7)
1 do
which is NEG with the similarity kernel d MMMP (i, d2(t,))-I
2.3 PaCMAP
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 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:
LijENN WNN dz(i.))
d2( + LIKEP WeF (ei,j)++C,
in which the W weights change based on the epoch, and C₁ and C2 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 nigh-dimensional input to the low-dimensional embedding. We refer to the resulting parametric algorithm ParamPaCMAl Implementation details are in Appendix F.
3 Effect of Parametrization on DR Results
Machine learning practitioners have long believed that parametric NE algorithms behave similarly to their non-parametric counterparts [7 18]. In this section, we investigate the performance of the aforementioned parametric and non-parametric versions 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.c., a linear model), hidden layer, or 2 hidden layers projector. We fix the number of neurons for each layer to 100.
Observation 1: Parametric NE algorithms typically lead worse visual effeets well worse local structure preservation. Our results indicate that parametric NE algorithms often fail to produce embeddings of the same quality as their non-paramen paraamamttiic counterparts, even on simple datasets such as MNIST [15] The non- parammemet 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 MNIST are actually separated. These blurred boundaries result in poorer preservation of local structure, with the possible exception of Parametric PaCMAP.

---

Linear SVM: 0.46
Hicden Layer
2 Hidden Layer SVME 0.54
3 Hidden Layer SVM: 0.93
Non param SWMi: 0.95
SWIM: 0:45
NCVIS Info-NC-t:SI
SVW: 0.52
0.50
SVIE 0.69
SVM: 0.88
SWM: O
1
2
3
SVM:
0.75
SVM: 9.
5
LIMAP
6
7
8
SVM:
SUM: 0.80
SVM:
SVM: 0
PRCMAP
Figure 2: Embeddings of the MNIST [13] dataset generated by various DR methods with different numbers of hidden layers: 0 (Linear), 2, or 3, or non-parametric variant. See Section (.T for details of SVM Acc. It is helpful to envision these images in black and white (without labels) clusters would be difficult to visually separate. More datasets/methods can be found App. C
when
The challenge of accurately preserving local structure 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.T) Fig. 3 further quantifies the observation. Here, 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. For each embedding, we scale the distance with respect 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 the non non-porann con-paraettric methods, all the parametric counterparts (App. H.I have smaller FP distance ratio, meaning further pairs are positioned closer together, which explains the blurred boundaries between clusters.
NE algorithms with NEG loss perform better when parameterized. A widely ac- cepted explanation for the failure of small neural network projectors, such as those used here, is that they lack the capacity to capture the com- plexity of the data. While adding more layers to the projector is be- lieved effectively mitigate the loss in local structure preservation, our ex- perimental 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-sut such as the number of nearest neighbors used in NN-graph construction- also had minimal impact on the resulting embeddings. all cases, the visual quality of the embedding remained suboptimal compared to nonparametric DR methods.
PaCMAP
Param PaCMAP
ParamRepulsor
Observation 2:
Low Dim Dist
0.0
NN:
MN:
FP:
NN:
MN:
FP:
NY.
MVV
FP. 7.074
1.000
7.470
7.852
1.000
6.146
6.559
1.000
7.505
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), gener-
ated by PaCMAP, ParamPaCMAP, and ParamRepulsor (other
methods in App. H.I
See definitions in Sec. &
5

---

While all four algorithms achieve comparable performance on the MNIST dataset in the non- parametric setting, their ability 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-I-SNE and NCVis). As illustrated in the first four columns of F 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.
We found that PaCMAP's loss is a generalized NEG loss, with separate similarity function qo defined for 1j E NN and ij FP. We now state this formally.
Theorem 3.1. The loss of PaCMAP is generalized NEG with low-dimensional similarity functions NN and %0 96
CPCMMAP (0) - -RjENN log
4o NN (y),
-mE log
(1+
(1 (f (8)
1
1+ NN (yt,,,)
in which the functions qg NN and q8
FP are
exp( d-(1,))
1 1- exp( dg(1o)+C2
do(t.j)
NN (y.,,,) 46
PP (y+yy))))
exp( +2())
90
= exp( (2.))+C)
dz(1.))
Proof: see Appendix [
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 consistently in the form of log Pay- 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 depends on a negative pair, ensuring that the gradient is large when the negative pair becomes close.
) and for PaCMAP is dz(is)+(a'' This term solely
This is in contrast to both NCE and InfoNCE losses, where each negative pair term is based on all pairs. Theoretical studies 226 (77 in standard contrastive learning have found that such design of loss functions may lead to reduced gradient and worse performance under 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.
4 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 PuramRepulsor, novel parametric algorithm built upon our ParAMPaCMAP. Pseudocode for ParamRepulsor is found in Alg. T and detailed in Alg. 2 in App.
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] 22), 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 known be problematic for contrastive learning [31 30). We show that MN pairs are ideal candidates for negatives they rarely become false negatives.

---

Algorithm Simplified Pseudocode for ParamRepulsor
Require:
X, B, RMNN, ReP,, Repochs fo. 7, bsz, WNB. WMN, WPP
1: Initialize neural network projector fo with parameter 0
2: for + to N do
3: Sample neerete neighbors, aMN mid-near points.
4: end for
Neeochh do 6: for batch + 1 to Thatches do
5: for epoch
7:
Sample
I1 .... Thes from training data, NN\ NN .... Tbss) from nearest
neighbors of each point in x, I = M (Z Thez) from mid-near points (see Sec 4).
Sample FF ( ... Ibsz) from uniform distribution.
8:
Calculate = fo(x). y NN fo
NN) y.y fo(x ", fo(x
9:
0.
10:
for k - 1 to b do
de de NNE) 10+d2(ue N
daluve MeNe)
L f+ WNB E Ei=I..
WMN Ei=L.. BACN 1+d2(un MoNe)
da Wv
WFP Ei Ei.I.. Ppp 1+da(wn.9 Pt)
end for
13:
Calculate gradients VoC.
Update parameters 9 using Adam optimizer.
15: end for
end for
17:
return fo(X)
Theorem 4.1. The probability that sampled MN point is false negative in a dutaset of size converges to at a rate of (
Corollary 4.2. MN points are less likely to be false negatives than uniformly sampled points in datasets with Z 10 See Appendix for empirical results and Fig. 27 in Appendix for projection.
see Appendix E Theorem 4.1 and Corollary 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.
Proof:
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 cow-dimensional embedding. As shown in Fig. in the blurred boundaries clusters "3" and "8," MN pairs tend to be closer than normal FP pairs in the embeddings of all methods (see Fig. 22 in H.. for other methods). This proximity makes MN pairs challenging negatives for the algorithm, resulting in large gradients during the loss calculation. Fig, 4 illusttrasss 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.
MN Weight = 0.00
MN Weight = 0.25
MN Weight = 0.50
MN Weight = 0.75
MN Weight = 1.00
Figure 4: Effect of Hard Negative Mining MNIST, We progressively increase the coefficient of the repulsive force applied to MN hard negatives. Close clusters are circled. Results indicate that Hard Negative Mining alone effectively preserves local structure while maintaining relative proximities.
Besides adopting Hard Negative Mining, we made other technical improvements to further enhance repulsive forces. More details can be found in Appendix F
7

---

5
Experiments
Here, we evaluate the performance of our ParamPaCMMP 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 BS 36 [77 [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 Gaussian Lineage, and Gaussian Hierarchical 43 were integrated into our analysis. See
41 42.
Section G. for more details. This multifaceted dataset compilation enables a thorough examination of the DR algorithms'' performance across spectrum of datasets.
Algorithms. Besides the two algorithms we proposed in this work, ParamPaCMAP (P-PaCMAP) and Pepamoe (P-Rep), also perform experiments other recent Parametric NE algorithms: Parametric UMAP (P-UMAP) [7]. Parametric Info-NC-t-SNE (P-I(SNE) [8], Parametric Neg-t- SNE (P-NiSNE), and Parametric NCVis (P- (P-NCVis) [24] [8] Besides NE algorithms, we also compare against Geometric Autoencoder (GeoAE) 44], an nutoencoder-basee DR algorithm. While we note that there are many other parametric DR algorithms, they either aim to serve
intermediate representation for downstream tasks (i.e., not visualization) [45] [46. or focus only on image dataset only (I). We refer readers to Section 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 fully-connected neural network as their parametric projector fe.
Other setup. For each experiment, we ran each DR algorithm 10 times using different random seeds 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.
5.1 Local Structure Evaluation
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,
[3 43 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--N Accuracy. Here, DR is performed and the labels are revealed afterwards. A N-NN model then classifies points in the DR projection, with its accuracy the metric of interest. We perform leave-one-one ont 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 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 [ 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- highett accuracy on the remaining datasets. These results demonstrate that ParamRepulsor attains state-of-the 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 h: = 30 to provide a more robust estimate of neighborhood preservation ability. Using a larger 30 value ensures that even if the first nearest neighbor in the high-dimensional space is placed as the tenth nearest neighbor in
8

---

Table I: 10-NN Accuracy of DR methods measured on various datasets. The absence of values indicate the method failed to produce a valid embedding.
METHOD
P- UMAP
P-ITSNE
P-NTSNE
P-NCVIS
GEOAE
P-PACMAP
P-REP
MNIST
0,965
0.830
0.862
0.829
0.791
0.968
0.969
F-MNIST
0.733
0.714
0.714
0.626
0.718
0.744
0.778
USPS
0.957
0.939
0.940
0.938
0.846
0.960
0.957
C0
0,84.
0.724
0.853
0.887
COIL-100
0.145
0.611
0.896
0.928
20NG
0.505
0.340
0.401
0.442
0.061
0.437
0.460
KANG
0,954
0,956
0.956
0.955
0.468
0,960
0.961
KAZER
0,939
0.937
0.937
0.937
0.700
0.940
0.939
MURARO
0,960
0.961
0.961
0.961
0.565
0.961
0.962
STUART
0.851
0.854
0.853
0.854
0.394
0.855
0.856
CIRCLE
0.901
0,900
0.904
0.911
0.898
0,904
0.895
MAMMOTH
0.934
0.916
0.914
0.915
0.962
0.915
0.938
LINEAGE 1.000
1.000
1.000
1.000
1.000
1.000
1.000
HIERARCHY 1.000
1.000
1.000
1.000
0.976
1.000
1.000
the embedding, 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 App. demonstaess that ParamRepulsor achieves the highest accuracy on 10 out of 14 datasets and nearly the highest 3 others, showcasing its strong performance in preserving local structure, Additionally, our implementation ParamPaCMAP performs comparably to the best methods on all but 2 datasets.
5.2 Global Structure Evaluation
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 and rank all other centroids based on low-dimensional distance 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 the result, shown in Table 4 in App. H.3 Out of the 14 datasets, ParamPaCMAP achieves the highest correlation 5 of them, whereas ParamRepulsor achieves the highest on These results suggest our ideas are powerful for global structure preservation.
6 Related Work
The evolution of DR algorithms can be broadly categorized into two distinct phases. the initial phase, the focus techniques this category include Principal Components Analysis (PCA) [49] Multidimensional Scaling [50], and Non-negative Matrix Factorization [5T]. 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.
the development of methods that preserved only global structure. Key
Subsequent DR methods were developed to address the shortcomings by emphasizing the preservation of local structure, specifically focusing preserving & 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- aigh-dimensional space that are difficult to see any other way.
NE methods are typically non-parametric, creating low-dimensional embedding that maps each data point location in 2D, but there does not exist function that maps from the original (high- dimensional) space the embedding space. To map new points to the low dimensional space, one

---

typically creates nonparametric map from high to low dimensions that places new points near their high-dimensional neighbors (assuming one does not want 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-dimennsionll space into a low-dimensional embedding, typically using neural network. Examples of this approach include the Multi-layer Perceptron based Parametric t-SNE [6]. DEC [55], kernel t-SNE [56] and Parametric UMAP [17]. Furthermore, recent advanceennss have integrated concepts from Contrastive Learning and Representation Learning. with significant contributions from TopoAE [57] GeoAE 44 t-SimCNE M and Parametric InfoNC-t-SNE [18].
Recently, [3 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 not discussed previous works.
Learning from Hard Negatives has proven effective in supervised learning 28 metric learning 22)]. as well 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.
7 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 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 broad spectrum of scientific inquiry.
We note that 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.
Code and data availability
Implementations of ParamRepuloo/PraanPPCCAM discussed in this paper, along with the code for the experiments, available hhtts:://iitub: com www/coom/h/ccccc wwtphuangoO/Paraaeppulla. The datasets used in our study are publicly accessible from their original publications.
Acknowledgement
We acknowledge funding from the National Science Foundation under grants IIS-2130250, IIS- 2147061, DGE-2022040 and the National Institutes of Health under grant SR01-DA054994.
References
[1] Böhm, J. N., P. Berens, D. Kobak. Unsupervised visualization of image datasets using contrastive learning. In International Conference on Learning Representations, 2023.
[2] Mu, J., S. Bhat, P. Viswanath. All-but-the-Top: Simple and Effective Postprocessing for Word Representations. In International Conference on Learning Representations: 2018.
[3] Raunak, V., V. Gupta, F. Metze. Effective Dimensionality Reduction for Word Embeddings. In Proceedings of the 4th Workshop on Representation Learning for NLP RRpPLANLP-2019 pages 235-243. 2019.
[4] Cao, J., M. Spielmann, Qiu, et al. The single-cell transcriptional landscape of mammalian organogenesis. Nature, 496-7755 2019.
10

---

[5] Becht, E., L. McInnes, J. Healy, et al. Dimensionality reduction for visualizing single-cell data using UMAP. Nature Biotechnology, 37(1):38-44 04.38844,224 2019.
[6] Amezquita, R. A., A. T. Lun, E. Becht, et al. Orchestrating Single-Cell Analysis with Biocon- ductor. Nature Methods, 17(2):137-145, 2020.
[7] Dries, R., Q. Zhu, R. Dong, et al. Giotto: toolbox for integrative analysis and visualization of spatial expression data. Genome Biology, 22:1-31, 2021.
[8] Atitey, K., A. A. Motsinger-Ren B. Anchang. Model-based evaluation of spatiotemporal data reduction methods with unknown ground truth through optimal visualization and interpretability metrics. Briefings in Bioinformatics, 25(1):bbad455, 2024.
[9] Böhm, J. N., P. Berens, D. Kobak. Attraction Repuuiion Spectrum in Neighbor Embeddings. Journal of Machine Learning Research, 23(1):4118 4149, 2022.
[10] van der Maaten, L., G. Hinton. Visualizing Data using t-SNE. Journal of Machine Learning Research, 9:2579-2605, 2008.
[11] Tang, J., J. Liu, M. Zhang, et al. Visualizing Large-Scale and High-Dimensions Data. In Proceedings of the 25th International Conference on the World Wide Web, pages 287-297. 2016.
[12] McInnes, L., J. Healy, J. Melville. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv e-prints, ww..iv:182..04444 2018.
[13] Wang, Y., H. Huang, C. Rudin, et al. Understanding How Dimension Reduction Tools Work: An Empirical Approach Deciphering I-SNE, UMAP, TriMAP, and PaCMAP for Data Visualization. Journal of Machine Learning Research, 22, 2021.
[14] McInnes, Leland. Github Imcinnes//mapap: Uniform Manifold Approximation and Projection (UMAP), http:s///gaaaaaooccooo///aamaaaa 2020.
[15] LeCun, Y., C. Cortes, C. Burges. MNIST handwritten digit database. ATT Labs [Online]. Available: http://yann. lecun. com/exdb/unist, 2, 2010.
[16] van der Maaten, L. Learning a Parametric Embedding by Preserving Local Structure. In Artificial Intelligence and Statistics, pages 384-391. PMLR, 2009.
[17) Sainburg. T., L. Mclnnes, T. Q. Gentner. Parametric UMAP embeddings for representation and semisupervised learning. Neural Computation, 33(1 1-2907, 2021.
[18) Damrich, S., J. N. Böhm, F. A. Hamprecht, et al. From t-SNE to UMAP with contrastive learning. In International Conference on Learning Representations. 2023.
[19] Aggarwal, C. C., A. Hinneburg, D. A. Keim, On the Surprising Behavior of Distance Metrics High Dimensional Space. In Database Theory-ICDT 2001: 8th International Conference London, UK, January 4-6, 200! Proceedings 8, pages 420 434. Springer, 2001.
[20] Hu, T., Z. Liu, Zhou, et al. Your Contrastive Learnnn is Secretly Doing Stochastic Neighbor Embedding. In International Conference on Learning Representations. 2023.
[21] Gutmann, M., A. Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 297-304. 2010.
[22] Oord, A. v. d., L. O. Vinyals. Representation Learning with Contrastive Predictive Coding. arXiv preprint arXiv: 1000 03748, 2018.
[23] Mikolov, T., Sutskever, K. Chen, et al. Distributed Representations of Words and Phrases and their Compositionality. Advances in Neural Information Processing Systems, 26, 2013.
[24] Artemenkov, A., M. Panov. Nevis: Noise Contrastive Approach for Scalable Visualization. In Proceedings of The Web Conference, pages 2941-2947. 2020.

---

[25] van der Maaten, L. Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research, 15:3221-3245. 2014.
[26] Yeh, C.-H., C.-Y. Hong, Y.-.. Hsu, et al. Decoupled contrastive learning. In European Conference Computer Vision, pages 668-668880 684. Springer, 2022.
[27] Tian, Y. Understanding deep contrastive learning via coordinate wise optimization. Advances in Neural Information Processing Systems, 35:19511-19522, 2022.
[28] Schroff, F., D. Kalenichenko, J. Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 815 823. 2015.
[29] Oh Song, H., Y. Xiang. S. Jegelka, et al. Deep metric learning via lifted structured feature em- bedding. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4004 4012. 2016.
[30] Robinson, D., C.-Y. Chuang. S. Sra, et al. Contrastive learning with hard negative samples. In International Conference Learning Representations. 2020.
[31] Chuang. C.-Y., J. Robinson, Y.-C. Lin, et al. Debiased contrastive learning. Advances in Neural Information Processing Systems, 33:8765-8777 2020.
[32] Xiao, H., K. Rasul, R. Vollgraf. Fashion- Novel Image Dataset for Benchmarking Machine Learning Algorithms. arXiv preprint arXiv:1708.0774 2017.
[33] Nene, S. A., S. K. Nayar, H. Murase. Columbia Object Image Library (coil-20). Tech. rep., Technical Report LUCS-005-96, 1996.
[34] - Columbia Object Image Library (coil-100), Tech, rep., Technical Report CUCS-006-96, 1996.
[35] Kang, H. M., M. Subramaniam, S. Targ, al. Multiplexed droplet single-cell RNA-sequencing using natural genetic variation. Nature Biotechnology, 36(1):89, 2018.
[36] Kazer, S. W., P. Aicher, D. M. Muema, et al. Integrated single-cell analysis of multicellular immune dynamics during hyperacute HIV-1 infection. Nature Medicine, 26(4):511-515 2020.
[37] Muraro, M. J., G. Dharmadhikari, D. Grün, et al. A single-cell transcriptome atlas of the human pancreas, Cell Systems, 3(4)3385-394, 2016.
[38] Stuart, T., A. Butler, Hoffman, et al. Comprehensive integration of single-cell data. Cell, 1788))1188-1102 2019.
[39] Lang, K. Newsweeder: Learning Filter Netnews. In Proceedings of the International Conference on Machine Learning, pages 331-339. 1995.
[40] Townes, F. W., S. C. Hicks, M. J. Aryee, et al. Feature selection and dimension reduction for single-cell ma-seq based on a multinomial model. Genome Biology, 20(1): 2019.
[41] The Smithsonian http://aasssieeeeepppppaataaaaaa
Institute.
Mammuthus primigenius (blumbach).
2020.
[42] Coenen, A., A. Pearce. Understanding UMAP. understanding-uus umap// 2019.
https://pair-code http://arrrccode.iiiibb.b.. io/
[43] Huang, H., Y. Wang, C. Rudin, et al. Towards a comprehensive evaluation of dimension reduction methods for transcriptomic data visualization. Communications Biology, 5(1):719, 2022.
[44] Nazari, P., S. Damrich, F. A. Hamprecht. Geometric autoencoders you see is what you decode. Proceedings of International Conference on Machine Learning, pages 25834-25857. PMLR, 2023,
12

---

[45] Kiani, B. T., R. Balestriero, Y. Chen, et al. Joint Embedding Self-supervised Learning in the Kernel Regime. arXiv preprint arXiv:2209. 14884, 2022.
[46] Balestriero, R., Y. LeCun. Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding methods. Advances in Neural Information Processing Systems, 35:26671 1-6655,, 2022.
[47] Kobak, D., P. Berens. The art of using t-SNE for single-cell transcriptomics. Nature Communi- cation, 10:5416, 2019.
[48] Amid, E., M. Warmuth. TriMAP: Large-scale Dimensionality Reduction Using Triplets. arXiv e-prints, arXiv:1910.00220 2019.
[49] Pearson, K. On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 2(11):559-572. 1901.
[50] Torgerson, W. Multidimensional scaling: Theory and method. Psychometrika, 17(4):401-419 1952.
[51] Lee, D. D., H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6655) -991 1999.
[52] Tenenbaum, J. B., V. de Silva, J. C. Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 29065500):2319-2323, 2000.
[53] Roweis. S. K. Saul. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 290(5500):2333-22366 2000.
[54] Belkin, M. P. Niyogi. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. Advances Neural Information Prucessing Systems, vol. 14, pages 585-591. MIT Press, 2001.
[55] Xie, J., R. Girshick, A. Farhadi. Unsupervised Deep Embedding for Clustering Analysis. In Proceedings of International Conference on Machine Learning, pages 478-487. PMLR, 2016.
[56] Gisbrecht, A., A. Schulz, B. Hammer. Parametric nonlinear dimensionality reduction using kernel t-SNE, Neurocomputing, 147:71-82, 2015.
[57] Moor, M., M. Horn, B. Rieck, al. Topological Autoencoders. In International Conference on Machine Learning, pages 7045-7054. PMLR, 2020.
[58] Wattenberg, M., F. Viégas, I. Johnson. How to use t-SNE effectively. Distill, 1(10)=e2, 2016.
[59] Belkina, A. C., C. O. Ciccolella, R. Anno, et al. Automated optimized parameters for t- distributed stochastic neighbor embedding improve visualization and analysis of large datasets. Nature Communications, 10(5415), 2019.
[60] Cao, Y., L. Wang. Automatic selection of t-SNE perplexity. arXiv preprint arXiv:1708.03229, 2017.
[61] He, K., X. Zhang, S. Ren, et al. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778. 2016.
[62] Kingma, D. J. Ba. Adam: A Method for Stochastic Optimization. International Conference on Learning Representations, 2015.
[63] Hull, J. A database for handwritten text recognition research. IEEE Transactions Pattern Analysis and Machine Intelligence, 16(5):550 -5544, 1994.
[64] Pedregosa, F., G. Varoquaux, A. Gramfort, et al. Scikit-leamn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[65] Zheng, X., M. Terry, P. Belgrader, et Massively parallel digital transcriptional profiling of single cells. Nature Communications, 8(1):1-12, 2017. 2017.
13

---

A Discussion on the Depth of of Neural Network Projector
PuSSE Layers
PASSEE Lagees
PAISEE LAyaI
PARSKE Leyers
PNESUE 5 Layers
Layerr
Layers
Ioca:0.77 10.1
local 0.85
lccal0.99 clobatt3.02
Iocat0.97 0.0el0..00
Iocal00.77 globato.cc
IccarD 27 glowil
local 0.93 global su
local globelrl.ez
localto gubalttlee
local global-i..0
Figure 5: Effect of the number of layers on the MNIST dataset. As supplement to Fig. 2 the number of layers beyond three for Into-NC-t-SNE, UMAP and PaCMAP. Here, the local metric represents 10-NN accuracy, while the global metric denotes the random triplet preservation. Results 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.
we extend
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-I(SNE) [8]. 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.
14

---

B Discussion on the Hyperparameter settings of Parametric DR algorithm
IISNE NN=80 0.49 global:0.65
FIRSNE
FIRSNE local:0.83 globall0.66
P-MSNE local:0.4 g.0bal:0.63
PItSNE NN=4
local:0.81 globalk0.63
local:0.82 global.0 63
P-UMAP NN=60
P-UMAP NN--30
P-UMAP Ni-115
P-IMAP NNw-8
P-UMAP NNm4
local:0.96 globel:0.61
local:0.96 globel:0.61
local:0.97 global:0.61
local:0.97 gobbl00.6
local:0.92 global:0 61
lacalin..95
local:0.97
globali..60
local:0.
Figure 6: Impact of varying the number of nearest neighbors during NN-graph construction on the MNIST dataset. As in Fig. evaluate the embeddings using 10-NN accuracy and random triplet preservation to assess local and global structure retention, respectively. The results indicate that, unlike non-parametric algorithms, altering the number of nearest neighbors has minimal effect on the embedding's s quality, except for Info-t-SNE, which exhibits structural distortion when NN = 60.
Fig. iillustrates the effect of varying the number of nearest neighbors (NN) in P-IINNE, P-UMAP, and P-PaCMAP. Adjusting the number NNs during NN-graph construction commonly regarded as key mechanism for controlling the local-global structure trade-ofi off in nonparametric DR algorithms 60) Nevertheless, in the parametric setting, modifying the number of NNs had minimal influence on the resulting embeddings. Notably, increasing the number of NNs beyond the typical range (c.g..
to 60) can severely disrupt the structure, as observed in the P-IISNE case.
C Visualizations from all DR methods
In this section provide visualizations for the output of all DR methods. Fig. visualizes the output of ParamRepulsor. Notably, ParamRepulsor performs well on all datasets and achieves state-of-the-at 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, it is able keep the structure of the mammoth on Mammoth dataset, and keep the structure the hierarchy on the Hierarchy dataset.
15

---

MNIST Repullep
F-MNIST Repulso
COIL-20 RepumRe
ParamRepulsor
Newsaroups PeramReculsor
Kang ParamRepulsor
PeramRepulsor
Reppltr
ParamRepultar
Paramiopuuttr
ParamRapulsor
ParamRepultor
Hierarchy Paramieguisor
Toramoepuisor
Figure 7: dimensionality reduction results of PeramRepulsor.
16

---

MNIST
F-MNIST
COIL-20
Newsaroups
Kang
ParemUMAP
ParamJMAP
Murero ParamUMAF
Stuart ParamUMAP
ParamUJMAP
ParamLMMP
ParamUMAP
PeramUAAP
Figure 8: All dimensionality reduction results of PMP.
17

---

MNIST
F.MNIST
COIL-20
ParamInfo-NC-4ee
PuremiifO-NC-USSEE
Beraminfo-NC---SM
Bareminfo-NC-t-SNE
COIL-190 SwaaminfoNC--tSMM
Newsgroups PareminnooNC---SSE
Kang
Kazer
Peraminto-NC--U5NE
Pareminno-NC---SNE
Stuart
Gircle Paraminto NC-t-SNE
Paraminfo- SaaminfoNVE:E.MM SEE
Paraminno NC.E.SNE
Lineage SWra-Info-VC---SVE
Hiera PNr
Figure 9: All dimensionality reduction results of Paramlnfo-NCC4-SNE.
18

---

MNIST
F-MNIST
COIL-20
MMMPP
Newsgroups
Kang
PeramPECINAP
PaCAP
Stuart
ParamPaCMAP
ParamPaCMAP
PararPPCMMAP
Pai ParaPPCMMPP
Hiera rchy ParamPaCMAP
PeramPECNAP
Figure 10: All dimensionality reduction results of ParamPaCMAP.
19

---

MNIST
F-MNIST
COIL-20
Newsgroups
Kang ParamNCVis
ParsmNCViis
ParamNCVis
Murero ParamiCCIis
Stuart ParamNCVIs
ParamNICVis
ParamMCVVs
Hierarchy AeramNCVIs
AeramiiCvis
Figure All dimensionality reduction results of PCramNCVis.
20

---

MNIST ParamNeeg-L-SMe
F-MNIST
COIL-20 PeramNeg---SSE
Paramieeg-t-S
PeramiNeg---SEE
Newsgroups ParamNeg-ttSNE
Kang ParamiNeg--SNE
Pat-m
PeramNeg-t-SME
Paramiin
ParamNog-tt-ii
PeramNeg-t-Sh
Hierarchy PeramNeg-t-SNE
Param
Figure 12; All dimensionality reduction results of Param-Neg--SSNE
21

---

MNIST
COIL-20
ParamPaCMAP
Newsgroups
ParamPaCMAP
ParamPaCMAP
ParamPaCMMPP
ParamPaCIMAP Linear
ParamPaCMAP Linear
ParamPaCMAP
ParamPaCMMP
Hiara ParamPaCMAP Linear
ParamPuCMA/ Linear
Figure 13: All dimensionality reduction results ParamPaCMAP with a linear projector.
22

---

F.MNIST
COIL-20
Layer
Layer
Newsgroups Layer
Kang
Layer
ParamPaCMAP
ParamPaCMAP Layer
ParamPaCMAP
ParamPaCIAA Layer
Hiara rhyy ParamPaCMMPP
ParamPaCMMP
Figure 14: All dimensionality reduction results ParamPaCMAP with I hidden layer.
23

---

MNIST
F.MNIST ParamPaCMAP Layers
COIL-20 Layers
Layers
ParamFaCMAP Layers
Newsaroups ParamPaCMAP Layers
Kang ParemPaCMAP Layers
Layers
Mommoth
ParamPaCMAP
ParamPaCMAP Layers
ParamFaCMAP Layers
ParamPaCCMP w/ Layers
Hiararchy
ParamPaCMAP Layers
ParamPsCMAP w/
Figure 15: All dimensionality reduction results ParamPaCMAP with hidden layers.
24

---

MNIST Nomparerettrcc UMAP
F.MNIST Nonpar emeetic UMAP
USPS Nonparametric
COIL-20 Nonperametrr UMAP
COIL-190 Nompararettric UMAP
Newsgroups Nonpar eemmrticc UMAP
Kang Nonparametric
Nonperametric UMAP
Muraro Nonparametric UMAP
Stuart Nonparamettric UMAP
Girile Nonparametric UMAP
Mommoth Nonparametric UMAP
Hiara rchy Nonparemetric UMAP
Nomparameticc UMAP
Figure 16: All dimensionality reduction results of nonparametric UMAP.
25

---

MNIST
F.MNIST
COIL-20 Nonparametri
Nonparemetric
Nomperametric
Nomparaaetrrc
Newsgroups Nonperametric
Kang Nonparametric
Nomparemetric PeCMAP
Nonparametri
Stuart Nanparametric PaCMAP
Memmoth Nanparametrc PaCMAP
Nonparametric PaCMAP
PaCMAP
i
Lineage Nonparemetric PaCMAP
Hiara rchy
Nonperametric PaCMAP
Figure 17: All dimensionality reduction results of nonparametric PaCMAP.
26

---

F.MNIST
COIL-20 parameetiii
Nonparametric
Nenperameinc
Nomparametric NC----E
Newsgroups Nonparametric Info-NC-t-SNE
Kang Nomparametric Info-NC-t-SNE
Nonparametric Info-NC-U-SNE
parametrii
Murero Nonparametric NC-t-C---
Stuart Nonparamoiri Info-NC. SNE
Mommoth
Nomparametric NC.E-
parammtii Info NC..-SNF
Hiara rhy Nenperametric Info-NC-t-SNE
Nonparametric Iifo-NC-L-SNE
Figure 18: All dimensionality reduction results nonparametric Info-NC-I-SNE.
27

---

MNIST Nomparemetric NCVis
F-MNIST
USPS Nonparametric
COIL-20 Nonperametric NCVis
Nomparametric
Newsaroups Nonparametric
Kang
Nomparerretric NCVis
Nonparametric
Nonperametric NCVIs
Muraro Nonparametric NCVIs
Stuart Nonparamatric NCVss
Mommoth Nonparametric NCVIs
Lineage Nomparameticc NCVIs
Hiara rhy Nonparametric NCVIs
Figure 19: All dimensionality reduction results of nonparametric NCVis.
28

---

MNIST Nomparametric Neg-t-SNE
F-MNIST
COIL-20 Nomperametric Neg-t:SNE
Nenparametri Neg
Nonparemetric Neg-t-SNE
Newsaroups Nenparametric Neg-t-SNE
Kang Nonparametric Neg-t-SNE
honparametric Neg-t-SNE
Nomparametric Neg-t:SNE
Muraro Kanparamatriz Nog-t-SNE
Stuart Nenparametri Nag
Mommoth Nanperametric t-SNE
Nonparametric Nog.
Lineage komparametric Neg-t-SNE
Hiara Nenparametri Neg-t-SNE
Figure 20: All dimensionality reduction results nonparametric Neg-t-SNE.
29

---

D Proof that PaCMAP's loss follows NEG
Recall that the NEG loss follows the form
go(y).
)
1
NEG (0) N log
mlajee log
(10)
1 go (yr,
( go(
where is the number of negative samples of each batch and qo 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 the early exaggeration used in t-SNE and UMAP [[3]. Therefore we consider only the last stage of the PaCMAP optimization process that involves only the NN and FP losses:
L PaCMAP (0) = LIJENN + LUEFP= = E d2(i.j) BENN d2(1,)) +
Σ iJEFP d2(i,))+1 (1I)
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 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 NN. Thus, we have:
d2(i,,) JENN de(i,)) + 10
I, PPCMAP (0)
Σ
+ Σ
(12)
dz(i,)) +1
WEFP
di
#NN EijENN d2(1, 10
+ mlEiEEE dz(i,)) +
(13)
d2(1,)) + -.EiEE dz +1
x ENJENN dz(i, + 10
(14)
10
dz(i,))
x EEEENN d2(i, () 10
mlBajes dz(i. j) +
(15)
10
d2(i.
EEeENN log exp
d2(1.) + 10
-mEijeg log exp
(16)
de(i, +
Due to the different choices of normalizing constant in the NN loss and the FP loss, the PaCMAP actually utilizes different kernel to model the similarity between the NN and FPs. Solving for the functions 46 NN and y5 FP we have the result:
exp(
-10
NN (y:,,,) 40
d2(1.f)+10
(17)
exp(
--eexp(
da(i.))
T (y..y))
(1.))
(18)
dati.)
exp( d205)+1)
E Proof that the Mid-Near Hard Negative False Negative Rate converges to 0 quadratically
For simplicity, consider dataset of size + 1, that each point will sample from pool of points. For each point, we consider its 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 pool of 6 points. Denote the event that mid-near point being a false negative
30

---

as A. A essentially means that there exist more than one point from the l nearest neighbors being sampled. Therefore, we know that A means there is at most one point in the samples comes from the k nearest neighbors, which essentially gives us:
I0
10
P(A)
(19)
All points sampled NN
Only point NN
6! - 6) - 10)!
6!(n 6))(n 10)! 10
(20)
n!6!(n 16)!
n15.(n 15)!
(n (n--))(m)) 10)!
60
(n - -))!(n 10)!
+
(21)
m!(n 16)!
n
15
n!)n-16)
n 45
(n 6))(n 10)!
(22)
n 15
n!(n 16)!
(n 4n 10) 11) - 14)
13)
(23)
n(n 1)(n - 2) - 3n 4) - 5)
n 15n 1265n + +0(n²)
(24)
n 15m + 85n* + O
It follows that lim, P(A) = 1, and it converges at the rate of O ( Because P(A) = P(A).
we know that P(A) also converges to 0 at the rate of O 3 ).
This is much faster than the uniform sampling. For uniform sampling, the false negative probability is always 10 which is linear. This is particularly bad for DR algorithmss: the number of negative samples usually linear w.r.t. n. Fig. 21 illustrates the probability of false negatives sampled from 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 particularly small number to achieve in the era of big data.
10a
10-2
False Negative Prob
10-1
10-6
Mid-near Hard Negative Sampling Uniform Negative Sampling
10-a
10-10
10-12
10a
10a
10a
10a
10a
10a
10
10a
Dataset Size
Figure 21: Expectation the number false negatives generated by Uniform Sampling and Mid-near Hard Negative Sampling different dataset sizes.
F Implementation details for ParamRepulsor and Baseline Parametric PaCMAP
ParamRepulsor and ParamPaCMMP are implemented with PyTorch 2.0.0, Numba 0.57.0 and CUDA 11.7. We provide our implementation alongside the submission. detailed algorithm is provided in Alg. 2
31

---

In order to faithfully reflect the impact of parametrization on the embedding, our baseline parametric PaCMAP is written way keep as much detail unchanged from the non-parametri, version. ParamRepulson implementation is written based on the Parametric PaCMAP, but many changes are made 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, utilize 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 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 embedding layer the projector that the network behavior similar to non-parametric version.
Initialization. As 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, ParamRepulsor and ParamPaCMAP, we initialize all our neural network parameters with Kaiming Initialization (61).
longer use this initialization. For both
Optimization Schedule. Since our neural network optimization schedule is performed by mini- batch stochastic gradient descent, we are unable optimize the full embedding at once as in con-parametric PaCMAP. Therefore, at each step. we sample a batch of points, and find NN, MN, and FP points for each element 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 3 (0.9, 0.999) and batch size of 1024. Refer to the algorithm below for more details.
G Experimental Details
G.1 Datasets Used
MNIST. MNIST (SS) is 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 dataset containing 70,000 grayscale fashion
images of the shape 28 x28. The images are flattened.
USPS. USPS 63 is dataset containing 9298 written digit images of the shape 16x 16. The images are flattened.
COIL-20 The COIL-20 33 dataset is is a database of 1440 gray-scale images of 20 objects. The
images are flattened.
COIL-100 The COII-110 images are flattened.
dataset a is database of 7200 color images of 100 objects. The 34
20NG The 20NewsGroup 39 dataset contains about 18000 newsgroups posts on 20 topics. We utilize scikit-lear 64 TF-IDF vectorizer to convert each post into a vector.
Kang al. The Kang et al. genes, with 13 types identified by scientists. The first 50 principal components from the raw data are used.
335 dataset contains scRNA-seq data from 13999 cells and 14053
Kazer et al. The Kazer et al. 36 dataset contains scRNA-seq data from 59286 cells and 16980 genes, with types identified by scientists. The first 50 principal components from the raw data are used.
32

---

Algorithm 2 Detailed Pseudocode for ParamRepulsor
Require:
X high-dimenn nigh-dimensional data matrix of the shape (N, D).
NNB, n.N,, nPP the number of neighbor pairs, mid-neat pairs, further pairs Pepochs the number of epochs for optimization
Pe neural network projector with parameter learning rate.
b- mini batch size.
WMN, WFP - the weights associated with neighbor, mid hear, and further pairs at epoch t. Initialize neural network projector pe with parameter
2: for i + 1 to N do
3: Sample n2. B- neighbors
4: for - to NMN do
5: Sample points
6: Select the second closest point as the j-th mid-near point
7: end for
8: end for
9:
for +- Nepochss do
10:
for t- 1 to Albatches do
11:
Sample x = 01 ................................ I6 from training data.
12:
N. MN MN(x1
(N .... 2b) from the nearest neighbors of x.
13:
2b) from the mid nears x.
14:
FF FP( .e.......y Tb), in which xP Ze, Uniform(1,n).
Calculate y fo(x). NN fo(w MN MN), S fo C= O.
15:
16:
17:
for k 1 to b do
delma L = C + WNR Ei (viin Ner
d2lwen 24.1)
WMN Et= 12 (e)
do(un FPi) WFP El=L.mer 1+da(un P1
end for
20:
Calculate gradients VeL.
Update parameters 0 using Adam optimizer.
22: end for
end for
24:
return fX(
Muraro et al. The Muraro et al. 37 dataset contains seRNA-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 al. The Stuart et al. 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 used.
The Circle dataset comprises of 5000 points uniformly sampled from 2D circle with radius The circle is divided into ares of the same length, and each point receives label that represents the index of the are it belongs to.
Circle
Mammoth skeleton.
The mammoth dataset
42
contains 10k points from 3D woolly mammoth
Lineage The Gaussian Lineage dataset
5
45 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 macro and meso clusters. Each micro cluster includes 100 observations.
33

---

G.2 Computation Platforms
All experiments are conducted with Exxact TensorEX 2U Server with 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.
H Additional Experiments, Tables and Figures
H.1
Additional Analysis on Distance Distribution in Embedding
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 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 shorter distance average.
Distance Distribution of NN/MNFF Pairs
Info-NC-t-SNE
Info-NC-t-SNE
Low Dim Diet
NN:
MtN:
FiP: 6.056
NN:
MNC 4.358
FP: 4.838
1,000
5.574
NCVis
Param NCVis
Low Dist
UMAP
Param UMAP
Low 0m DSt
0.4
0.2
0.0
MN:
FP:
FP: 5.896
1.000
6.316
6.772
1.000
5,541
PaCMAP
Law Dm Det
0.4
0.2
0.0
NNN 1,000
MNV 7,470
FP: 7,852
NN.
MNN 6.146
FP: 6.559
1.000
Figure 22: The low-dimensional scaled distance distribution between various types of point pairs with labels "3" and "8" in the embedding the MNIST digit dataset [15], generated Info-NC-t-SNE, NCVis, UMAP, PaCMAP, and their parametric counterpart. See definition in Sec. 2 4
H.2
Computational Speed Evaluation
As datasets grows larger, scalability becomes more important. We evaluate the time consumed by ParamInfo-NC-t-NNE. ParamRepulsor and ParamUMAP on two extremely large datasets, from 655 and [4] The dataset sizes are 1, 306, 127 and 2, 058, 652, respectively. The results are shown Figure 23 We can see that ParamRepulsor outperforms ParamUMAP in terms of scalability. While ParamRepulsor is slower than ParamInfo-NC+tsSEE the speed is still comparable in terms of magnitude. We note that Paramlnfo-NN-+-SSN utilizes smaller number of epochs, which gives it a higher speed, but at the cost of an underoptimized embedding, computational efficiency of ParamRepulsor can further improved by better optimization schedule well computational improvements, which leave for future works.
shown in Section 5 The
34

---

Comparison of Running Time
Zheng et. al
10a
Cao al
10a
Time (s)
102
10
10a
Paraminfo-NC+t-SNE
ParamRepulsor Methods
ParamUMAP
Figure 23: Time consumed by parametric DR methods compared to the size of the dataset. Para- mUMAP cannot finish the Cao al dataset under the time constraint of 6 hours.
H.3 Additional Tables
Table 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-baase 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, local structure performance particularly low. However, our method, ParamPaCMAP and ParamRepulsor, achieve comparable result on this metric.
Table 2: SVM Accuracy of DR methods measured on various datasets. indicates that the method failed to produce valid embedding.
The absence of values
METHOD
P-UMAP
P-ITSNE
P-NTSNE
P-NCVIs
GEOAE
P-PACMAP
P- P-REP
MNIST
0.964
0.836
0.865
0.836
0.787
0.966
0.968
F-MNIST
0.725
0.716
0.716
0.640
0,714
0.719
0.749
USPS
0,953
0.931
0.934
0.933
0.835
0,948
0.955
COIL-20
0.813
0.661
0,822
0,856
COII.-100
0.237
0.493
0.825
0.862
20NG
0.462
0.355
0.384
0.416
0.065
0.419
0.457
KANG
0,931
0,936
0.936
0.932
0,482
0.947
0.955
KAZER
0.938
0.935
0.935
0.936
0.758
0.930
0.935
MURARO
0.955
0.961
0.961
0.957
0.589
0.960
0.961
STUART
0.768
0.832
0.834
0.832
0.425
0.789
0.832
CIRCLE
0,899
0.904
0.902
0.910
0.894
0.905
0.894
MAMMOTH
0.902
0.886
0.886
0.891
0,936
0.887
0.895
LINEAGE 1.000
0,999
0,999
1.000
1.000
1.000
1.000
HIERARCHY 0.345
0.424
0.424
0.357
0.200
0.555
0.622
Additional Global Structure Preservation: Preservation of Triplets Preservation of global struc- ture also involves the preservation of distances. Particularly, would like the relative relationship of distances to be preserved: point A and are closer than A and in the high dimensional space, they should be closer in the embedding well. Following [3]. evaluate each method's ability to preserve distance relationships between randomly sampled triplets. The result in Table 5 in
App. H3
35

---

Table 3: Ratio 30-NN kept by the embedding measured on various datasets.
METHOD
P-UMAP
P-ITSNE
P-NTSNE
P-NCVIS
GEOAE
P-PACMAP
P-REP
MNIST
0.084
0.055
0.071
0.038
0.074
0.090
0.106
F-MNIST
0.088
0.079
0.044
0.043
0.081
0.097
0.121
USPS
0.317
0.313
0.286
0.298
0,224
0.280
0,306
COIL-20
0.710
0,490
0.701
0.713
COIL-100
0.067
0.348
0.523
0.593
20NG
0.220
0.156
0.180
0.192
0.003
0.140
0.105
KANG
0,100
0.113
0.100
0.111
0.008
0.094
0.121
KAZER
0.051
0.059
0.050
0.057
0,004
0.047
0.065
MURARO
0,393
0.416
0.368
0.321
0,062
0.387
0.429
STUART
0.081
0.099
0.086
0.098
0.005
0.083
0.099
CIRCLE
0.901
0.896
0.899
0.896
0.895
0.898
0.901
МАMMОTH 0,559
0.559
0.552
0.555
0.593
0.545
0.571
LINEAGE 0,077
0.095
0.076
0.094
0.076
0.076
0.095
HIERARCHY 0.367
0.370
0.364
0.367
0.352
0.362
0.365
Table 4: Centroid Distance Correlation of DR methods measured on various datasets. The absence of values indicates that the method failed to produce valid embedding. The highest values are displayed bold. Values that has no significant difference from the highest (measured by an independent t-test) are shown in italics.
METHOD
P-UMAP
P-ITSNE
P-NTSNE
P-NCVIS
GEOAE
P-PACMAP
P-REP
MNIST
0.707
0.697
0.705
0.663
0.759
0.784
0.732
F-MNIST
0.920
0.897
0.897
0.894
0.864
0.922
0.907
USPS
0,911
0.851
0.910
0.917
0.843
0.879
0.816
C0IL-20
0,538
0,780
0.767
0.824
COIL-
0.607
0.677
0.697
0.760
20NG
0.751
0,811
0.799
0.768
0.319
0.832
0.686
KANG
0.549
0.556
0.556
0.515
0.547
0.521
0,457
KAZER
0.682
0.647
0.643
0.678
0,554
0.618
0.544
MURARO
0.754
0.795
0.776
0.755
0,587
0.658
0.576
STUART
0.292
0.391
0.329
0.357
0.295
0.432
0.322
CIRCLE
0.957
0.879
0.898
0.969
0.937
0.918
0.953
MAMMOTH
0.929
0.986
0.987
0.974
0.908
0.972
0.972
LINEAGE 1.000
1.000
1.000
1.000
0.996
1.000
1.000
HERARCHY 0.350
0.464
0.571
0.489
0.647
0.708
0.738
Table 5: Triplet Preservation of DR methods measured various datasets. The absence of values indicates that the method failed to produce a valid embedding. The highest values are displayed in bold. Values with statistically significant difference from the highest (as determined by independent t-test) are highlighted in italics.
METHOD
P-UMAP
P-ITSNE
P-NTSNE
P-NCVis
GEOAE
P-PACMAP
P-REP
MNIST
0.600
0.611
0.615
0.588
0.628
0.604
0.605
F-MNIST
0,720
0.738
0.738
0.747
0.789
0.722
0,706
USPS
0.663
0.665
0.669
0.672
0.686
0.651
0.658
COTI--20
0.612
0.739
0.678
0.719
CO1L--100
0.615
0.730
0.687
0.720
20NG
0.655
0.674
0.666
0.658
0.528
0.678
0.607
KANG
0.772
0.746
0.755
0.775
0.638
0.792
0.772
KAZER
0.768
0.770
0.771
0.774
0.752
0.784
0.761
MURARO
0.693
0.719
0.717
0.663
0.763
0.742
STUART
0.628
0.688
0.689
0.660
0.629
0.739
0.713
CIRCLE
0,980
0.900
0.905
0.983
0.945
0.932
0.975
MAMMOTH
0.878
0.933
0.934
0.915
0.864
0.917
0,905
LINEAGE
0.995
0.995
0.995
0.995
0.991
0.994
0.993
HIERARCHY
0.625
0.707
0.736
0.674
0.741
0.788
0.789
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We provide detailed analysis and experimental results, both in main text as well as the appendix, to support the observation, theoretical, and experimental results in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
We discussed limitation of our work the discussion section and the appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
37

---

Answer: [Yes]
Justification: Detailed proof is provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide implementation alongside our submission so that the experi- mental results can be reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
38

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provided our implementation the methods described in this paper alongside the submission. Preprocessed datasets come from previously published work from others.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
y /nips. /nips.cc///pp wttps/ccccccggguudeeesseeeeeee/e gealcc/guuess//ee htwblii/cgiidees/ddduubiiiii
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/ettails
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary 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 the core the paper to 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We conduct multiple rounds of experiments and performed t-test over the results 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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
39

---

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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide compute resource details in our appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Experiments and research conducted conform with the NeurIPS code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
40

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 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 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).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 usage guidelines 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: Existing assets are properly cited and we also provide details dataset and implementation used in the appendix.
Guidelines:
The answer NA means that the paper does 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 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.
41

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: New code comes with proper documentation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects nor crowdsourcing experiments involved.
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No human subjects nor crowdsourcing experiments involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
42

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
43


Reviews:
[{"review_id": "vFnlP8MzSV", "reviewer": "Reviewer_Tz9e", "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.", "questions": "Please see above", "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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is well written generally and easy to follow. The motivation for their method is laid out clearly following the limitations of existing parametric and non parametric methods. \n* The proposed mid-near sampling to identify hard negatives seems simple to implement, and has a tangible impact in reducing the false negatives. \n* Good empirical performance from the proposed method supports the argument that including a negative repulsion loss improves local and global structure preservation.", "weaknesses": "* 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. \n* 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.\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review and suggestions. Here are our detailed response to each question or concern raised by the reviewer:\n- **Are parametric methods comparable to non-parametric methods?**\n\nSee common response 1.\n\n\n- **How does the weight on MN sampling affect the global structure?**\n\nTo clarify, the weight on the MN is not a parameter that controls the global-local tradeoff and should not be tuned by users in practice. Here, MN is only adjusted to demonstrate the effectiveness of hard negatives. As shown in Figure 4, while adjusting the MN sampling weight improves the local structure, the global relative ordering of the clusters is still preserved (see lines 216-218 and the caption).\nIn our common response PDF, Figure 1 row 3 presents a thorough experiment on MNIST using 10-NN accuracy and random triplet preservation as local and global metrics, respectively (see lines 259 and 609 for definitions). We found that the weight on the MN does not significantly impact the global structure, indicating that this is not necessarily a trade-off.\n\n- **How do other NE algorithms react to parameters related to the global-local trade-off?**\n\nNon-parametric NE algorithms typically use the number of nearest neighbors to balance the global-local trade-off. To analyze how parametric NE algorithms react to the parameter change, we varied the number of nearest neighbors for ParamUMAP (P-UMAP) and ParamInfoNC-t-SNE (P-ItSNE) from 60, 30, 15 (default), 8, to 4, shifting the focus from global to local structure preservation. We then perform the evaluation for ParamRepulsor on these embeddings, visualized in common response Fig.1 row 1&2. Unlike the non-parametric case, both visual quality and quantitative metrics showed little variation. (Most likely due to the parameterization making the embedding less flexible.) In most cases, a smaller number of nearest neighbors did not result in improved local structure or degraded global structure.\n\n\n- **Effectiveness of Hard Negatives with Increasing Dimensionality.**\n\nYes, L2 metrics are unreliable as global similarity measures in high-dimensional datasets, but we think the intuition is slightly different from what you described. For a neural network projector, a small L2 distance indicates that the **network perceives the inputs as similar** Selecting hard negative pairs with small L2 distance encourages the projector to differentiate between these similar samples. Our empirical results, spanning dimensionalities from 2 to 784 (see Appendix E), consistently show improvement over ParamPaCMAP, our baseline without hard negative sampling. Additionally, our findings align with existing research, which demonstrates that utilizing hard negatives is an effective strategy across various datasets and modalities, including those with much higher dimensionalities [1-4].\n\n- **What are the limitations of ParamRepulsor?**\n\nWhile ParamRepulsor creates embedding with better visual quality in general, it is not the fastest Parametric DR method. Although ParamRepulsor is faster than ParamUMAP, it requires a longer computational time, compared to ParamInfo-NC-t-SNE. \n\n[1] Robinson, Joshua, et al. \"Contrastive learning with hard negative samples.\" ICLR 2021.\n\n[2] Wang, Yuyang, et al. \"Improving molecular contrastive learning via faulty negative mitigation and decomposed fragment contrast.\" Journal of Chemical Information and Modeling 62.11 (2022): 2713-2725.\n\n[3] Liu, Minghua, et al. \"Openshape: Scaling up 3d shape representation towards open-world understanding.\" NeurIPS 2023.\n\n[4] Radenovic, Filip, et al. \"Filtering, distillation, and hard negatives for vision-language pre-training.\" CVPR 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p6B79JBDf1", "reviewer": "Reviewer_9imm", "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.", "questions": "- What is the computational time of ParamRepulsor compared to the other methods?\n- What are the limitations of ParamRepulsor?", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- DR problem is important as it is the main tool to visualize experiments and getting intuitions.\n- The paper presents detailed experiments to support the conclusions\n- The problem tackled is clear and well-motivated", "weaknesses": "See below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed and encouraging review. Here are our detailed response to each question or concern raised by the reviewer:\n\n- **What is the computational time of ParamRepulsor compared to other methods?**\n\nWe made a comparison of the computational time in Appendix Sec. F.2, and detailed results can be found in Figure 21. ParamRepulsor is faster than ParamUMAP, but slower than ParamInfoNC-t-SNE (which utilize the ParamCNE framework) on the two large dataset selected for comparison. ParamInfoNC-t-SNE converges faster at the cost of worse local and global structure preservation.\n\n\n- **What are the limitations of ParamRepulsor?**\n\nWhile ParamRepulsor creates embedding with better visual quality in general, it is not the fastest Parametric DR method. Although ParamRepulsor is faster than ParamUMAP, it requires a longer computational time, compared to ParamInfo-NC-t-SNE.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TAqCI28wy1", "reviewer": "Reviewer_bihR", "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.", "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 ?\n* Do observation 3 and 4 also apply in the non-parametric setting ? Could you discuss more the effect of parametrization on these.\n* 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?\n* 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": "/", "rating": 2, "confidence": 5, "soundness": 1, "presentation": 3, "contribution": 1, "strengths": "* code is provided.\n* the experimental section is rich with a good variety of datasets and metrics. Conducted experiments seem to make sense.\n* section 2 is clear and efficient.", "weaknesses": "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:\n\n* the sampling procedure to obtain mid-near pair is taken from PACMAP is not a new contribution. \n* 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. \n* 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.\n* 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.\n* 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):\n    if epoch < 200:\n        w_nn = 4.0\n        w_fp = 8.0\n        w_mn = 0.0\n    else:\n        w_nn = 1.0\n        w_fp = 8.0\n        w_mn = -12.0\n    weight = np.array([w_nn, w_fp, w_mn])\n    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.\n\nMore minor comments:\n* false negatives should be clearly defined before theorem 4.1 .\n* theorem 4.1 is an asymptotic result thus it doesn't bring true insights about practical guarantees of the methods.\n* I wouldn't put Corollary 4.2. in the form of a corollary as there is no associated proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review. Here are our response to each question or concern:\n\n- **Mid-near sampling is not new.**\n\nWhile the sampling process of the hard negatives roots from the mid-near sampling proposed by PaCMAP, in our work, we utilize them for a completely different purpose - and MN pairs even create forces in the opposite direction in our work. PaCMAP utilizes the mid-near pairs to increase global structure preservation, whereas in our work, we use it to encourage separation of clusters particularly in the parametric setting.\n\n- **Unclear how the proposed change affects the parametrization. Will this change behave similarly in non-parametric settings as well?**\n\nSee common response 2.\n\n- **What does it mean for NEG loss to have a negative term that is not based on all pairs? How would it affect the non-parametric case?**\n\nTo clarify, we are discussing the calculation of the loss for each individual pair, not the sampling process. For NEG loss, the loss and gradient for each individual pair are independent of the distances of any other pair. This independence is useful in the parametric case because the neural network projector correlates high-dimensional and low-dimensional distances, leading to potential inaccuracies in estimating the average distance between repulsive pairs. In the case of NCE loss, the loss value of any individual pair is determined by the pair's distance and a global average. This dependency prevents the generation of sufficient repulsive gradients.\n\n- **Comparison against non-parametric methods.**\n\nSee common response 1.\n\n- **Too many hyperparameters to tune.**\n\nTo clarify, the piece of code you mentioned is actually an optimization parameter schedule that is **not** meant to be tuned by users on each dataset. Applying a multi-stage loss schedule during the optimization process is a common practice in ML and DR. Examples include the most prominent algorithms in this field, including t-SNE [1], UMAP [2], and recent algorithms such as FIt-SNE [3], PaCMAP [4] and InfoNC-t-SNE [5]. All of these methods have numerous parameters to set, it’s just that the user often doesn’t have the option to control them. Sections 3 and 4 explain why our parameters are set as they are: the NN loss is decreased similarly to t-SNE's early exaggeration, and the hard negative loss is increased to overcome the lack of gradient in repulsion pairs due to parametrization. Empirical evaluation across 14 datasets coming from four different modalities show that our optimization schedule (all parameters unchanged across all datasets) can consistently produce embedding of high quality agnostic to the data. The results are robust to small to moderate changes in the parameter values, indicating that the general forces and balance between terms are what truly matter.\n\n- **False negative definition and validity of Theorem 4.1.**\n\nIn this context, a false negative is defined as a pair of points that should be nearest neighbors but are incorrectly sampled as a negative pair. To illustrate the effectiveness of theorem 4.1, we conduct a new empirical experiment with 10 repeated trials on the MNIST dataset. The results show that, when sampling 20 pairs for each point, a naive sampling method results in an average of 201.5 false negative pairs. In contrast, our hard negative sampling approach reduces this to an average of 0.8 false negatives.\n\n- **How robust is observation 1 under different network settings?**\n\nObservation 1 is pretty robust across different learning rates, batch sizes, and architecture in our experiments. Due to space constraints, Figure 3 in the shared PDF only visualizes ParamInfo-NC-t-SNE with different learning rates (3e-4, 1e-3, 3e-3), ParamPaCMAP with different network architectures (3-layer MLP with 100 neurons, 3-layer MLP with residual connections, a tiny 3-layer CNN), and ParamUMAP with different batch sizes (1024, 2048, 4096). All nine cases demonstrated worse visual effects and local structure preservation, verifying our observation.\n\n- **Do observations 3 and 4 apply to non-parametric cases?**\n\nYes, observation 3 and 4 still holds for non-parametric cases, as the pair sampling is separate from whether the model is parametric or non-parametric. It should be noticed that non-parametric algorithms do not suffer from the gradient diminishing problem, so applying the Repulsor changes are unnecessary for non-parametric cases.\n\n- **Is it possible to extend the k-NN graph construction to the online setting?**\n\nIt is possible to update the embedding, but certain difficulties remain. The graph needs to be reconstructed, and newly added points may become k-NN of points in the original data. Consequently, the embeddings of the original points no longer represent the similarities between neighbors and need to be updated as well. In contrast, parametric methods do not experience such problems.\n\n- **Applying entropy affinity graphs as in t-SNE?**\n\nWe choose to use k-NN graphs out of concerns on scalability, since naive affinity computation for all pairs in a dataset of size N will lead to a space complexity of $O(N^2)$, and a computational complexity of $O(N^2logN)$. Nevertheless, we note that recent methods such as SNEKhorn [6] have successfully extended the affinity graph approach with GPU. We will include discussion on these works into the related work section if the paper is accepted.\n\n[1] Van der Maaten, et al. \"Visualizing data using t-SNE.\" JMLR (2008).\n[2] McInnes, et al. \"Umap: Uniform manifold approximation and projection for dimension reduction.\" arXiv:1802.03426.\n[3] Linderman, et al. \"Fast interpolation-based t-SNE for improved visualization of single-cell RNA-seq data.\" Nature Methods (2019)\n[4] Wang, et al. \"Understanding how dimension reduction tools work.\" JMLR 2021\n[5] Damrich, et al, “From t-SNE to UMAP with contrastive learning”, ICLR 2023\n[6] Van Assel, et al. \"SNEKhorn: Dimension reduction with symmetric entropic affinities.\" NeurIPS 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RqGzK11J2E", "reviewer": "Reviewer_QK23", "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. \n\nTo address these issues, the authors propose a new parametric method called ParamRepulsor with two key improvements:\n\nHard Negative Mining: This technique focuses on identifying and repulsing the most challenging negative pairs, improving the separation between dissimilar points.\nModified 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.\n\nIn experiments, ParamRepulsor is shown to outperform other parametric methods on various datasets.", "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": "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.\n\nThe 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.\n\nSuggestions to enhance the impact and relevance of this work:\n\nExpanding the scope: Investigate the behavior of ParamRepulsor and other parametric methods with deeper networks.\nDeveloping Non-Parametric Repulsor: Create a non-parametric version of ParamRepulsor for direct comparison and to isolate the effect of the proposed modifications.\nDeeper 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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Novel Insight: The paper provides a novel perspective on the differences between parametric and non-parametric dimensionality reduction methods, highlighting the issue of local structure preservation in parametric methods.\n\nTechnical Contribution: The introduction of ParamRepulsor, a new parametric method with hard negative mining and a modified loss function, is a significant technical contribution. The paper demonstrates its superior performance in preserving local structures compared to other parametric methods.\n\nThorough Evaluation: The paper includes a comprehensive evaluation of ParamRepulsor and other dimensionality reduction methods on a diverse range of datasets, providing strong empirical evidence for the effectiveness of the proposed approach.\n\nClear Presentation: The paper is well-written and easy to read.", "weaknesses": "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.\n\nInsufficient 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.\n\nAbsence 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.\n\nLimited 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.\n\nEvaluation 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very detailed and encouraging review, especially the suggestions made to enhance our paper. Here are our detailed response to each question or concern raised by the reviewer:\n\n- **Rationale behind the choice for shallow neural network, and generalizability to deep neural networks.**\n\nIncreasing the number of layers empirically gives diminishing returns in terms of local quality improvement. While the performance gap between the non-parametric and parametric method reduces when we increase the number of layers from 0 to 3, such performance gaps stop to reduce when we further increase the number of layers. Fig. 2 in the common response PDF compares the performance of P-ItSNE, P-UMAP and P-PaCMAP with 4 or 5 layers. P-ItSNE receives minimal increase in quality, whereas for P-UMAP and P-PaCMAP, the embeddings do not change significantly. In all three cases, the performance is not as good as their non-parametric counterpart. Given that increasing the number of layers significantly hurts scalability, which is important for DR algorithms, only shallow neural networks were used in our main experiments. See common response Fig. 3 for discussion on other network architecture.\n\n- **Why is the limited capacity of the shallow neural network not the sole reason for the loss of local structure?**\n\nWhile we believe that parametrization contributes to this issue, as stated on lines 211-212, it is not the only factor. As shown in Figure 2 of the response PDF, increasing the number of layers does not completely restore the local structure. If network capacity were the sole issue, we would expect a complete restoration of local structure with additional layers.\n\nWe found that the problem in DR methods is similar to issues identified in ordinary contrastive learning by [1], where the repulsive force is insufficient. This problem also resonates with the violation of the strong repulsion principle of DR discussed by [2]. Therefore, we introduced hard negative mining into DR to solve this problem, which is used in contrastive learning for the same purpose - they also don’t have a theoretical explanation for it. \n\nThe closest we can get to a theoretical explanation is to refer back to the theoretical principles in [2], specifically Principle 5 states that the repulsion force needs to be strong when further pairs are close (gradient should be strong when further pairs are close), and Principle 2 states that the gradient should be weak when further pairs are far apart. This means scaling is important: if the scaling is incorrect, we have a weak repulsive force when we should have a strong one. We believe this is the problem with parametric approaches - they produce an incorrect scale. We tried several different ways to handle this, including rescaling the axes, but the hard negatives remedy the problem more effectively because they directly increase the gradients for informative negative pairs so that Principles 2 and 5 are obeyed. \n\n- **How does our optimization perform in the non-parametric setting?**\n\nPlease check common response 2.\n\n- **Evaluation with more metrics.**\n\nWe thank the reviewer for acknowledging that evaluation metrics used in the paper are standard in the field. Beyond the empirical results discussed in the main text, we also conducted experiments on other global-based metrics in Appendix Sec. F.  Indeed what makes DR challenging to evaluate is that there is no single metric. Many people have thought about this, and many papers have been written about this issue [3-7]. Consequently, we adhere to the current standards in the field.\n\n[1] Robinson, Joshua, et al. \"Contrastive learning with hard negative samples.\" ICLR 2021.\n\n[2] Wang, et al. \"Understanding how dimension reduction tools work: an empirical approach to deciphering t-SNE, UMAP, TriMAP, and PaCMAP for data visualization.\" JMLR 2021.\n\n[3] Kobak, et al. \"The art of using t-SNE for single-cell transcriptomics.\" Nature communications 10.1 (2019): 5416.\n\n[4] Cakir, et al. \"Comparison of visualization tools for single-cell RNAseq data.\" NAR Genomics and Bioinformatics 2.3 (2020).\n\n[5] Sun, et al. \"Accuracy, robustness and scalability of dimensionality reduction methods for single-cell RNA-seq analysis.\" Genome biology 20 (2019): 1-21.\n\n[6] Nguyen, et al. \"Ten quick tips for effective dimensionality reduction.\" PLoS computational biology 15.6 (2019): e1006907.\n\n[7] Espadoto, et al. \"Toward a quantitative survey of dimension reduction techniques.\" IEEE transactions on visualization and computer graphics 27.3 (2019): 2153-2173.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank reviewers for providing us with valuable feedback. 
We have taken note of the concerns raised by each reviewer and addressed them in detail. Here, we provide responses to the most shared questions, as well as responses that require an additional PDF page. We then provide a detailed response to each reviewer's concern in the rebuttal.

1. **How does parametric method compare against non-parametric method? (KMqC, bihR)**

Non-parametric DR algorithms struggle to map new data directly into the DR plot, making them unsuitable for large, incrementally updated datasets. This weakness hinders their application in important DR application areas, such as in analyzing dataset for recommendation systems and transcriptomics. Parametric DR algorithms address this by creating a mapping from one space to another. Thus, parametric and non-parametric methods are not direct competitors, and parametric methods don't need to outperform non-parametric methods in every aspect, although we strive for that.

Our work identifies that parametric methods fall short in local structure preservation compared to non-parametric methods. This is the first study to highlight this difference and propose optimizations that enhance local structure preservation without compromising global structure. While parametric methods currently underperform in local structure preservation metrics, they excel in global structure preservation, both quantitatively and visually. Table 1 in the PDF shows the performance on random triplet accuracy for both methods. Figure 4 in the PDF visually compares selected datasets, demonstrating that parametric methods better preserve global structure in hierarchical and mammoth datasets.

2. **Would our changes be useful in a non-parametric setting? (bihR, QK23)**

In this paper, we address the performance discrepancy between parametric and nonparametric DR algorithms. Section 3 discusses how parametrization can lead to insufficient repulsive gradients, which our hard negative sampling aims to resolve. Since nonparametric DR algorithms do not face this issue, our focus was on improving parametric algorithms. However, for completeness, we also tested nonparametric repulsors and included the results in Table 1 in the PDF. Note that comparison with other parametric DR algorithms can be found in Appendix F.

Meta-review: 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.
Decision: Accept (poster)