Navigating the Effect of Parametrization for Dimensionality Reduction

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:

• Rationale behind the choice for shallow neural network, and generalizability to deep neural networks.

Increasing 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.

• Why is the limited capacity of the shallow neural network not the sole reason for the loss of local structure?

While 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.

We 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.

The 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.

• How does our optimization perform in the non-parametric setting?

Please check common response 2.

• Evaluation with more metrics.

We 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.

[1] Robinson, Joshua, et al. "Contrastive learning with hard negative samples." ICLR 2021.

[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.

[3] Kobak, et al. "The art of using t-SNE for single-cell transcriptomics." Nature communications 10.1 (2019): 5416.

[4] Cakir, et al. "Comparison of visualization tools for single-cell RNAseq data." NAR Genomics and Bioinformatics 2.3 (2020).

[5] Sun, et al. "Accuracy, robustness and scalability of dimensionality reduction methods for single-cell RNA-seq analysis." Genome biology 20 (2019): 1-21.

[6] Nguyen, et al. "Ten quick tips for effective dimensionality reduction." PLoS computational biology 15.6 (2019): e1006907.

[7] Espadoto, et al. "Toward a quantitative survey of dimension reduction techniques." IEEE transactions on visualization and computer graphics 27.3 (2019): 2153-2173.

We thank the reviewer for the detailed review. Here are our response to each question or concern:

• Mid-near sampling is not new.

While 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.

• Unclear how the proposed change affects the parametrization. Will this change behave similarly in non-parametric settings as well?

See common response 2.

• 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?

To 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.

• Comparison against non-parametric methods.

See common response 1.

• Too many hyperparameters to tune.

To 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.

• False negative definition and validity of Theorem 4.1.

In 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.

• How robust is observation 1 under different network settings?

Observation 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.

• Do observations 3 and 4 apply to non-parametric cases?

Yes, 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.

• Is it possible to extend the k-NN graph construction to the online setting?

It 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.

• Applying entropy affinity graphs as in t-SNE?

We 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.

[1] Van der Maaten, et al. "Visualizing data using t-SNE." JMLR (2008). [2] McInnes, et al. "Umap: Uniform manifold approximation and projection for dimension reduction." arXiv:1802.03426. [3] Linderman, et al. "Fast interpolation-based t-SNE for improved visualization of single-cell RNA-seq data." Nature Methods (2019) [4] Wang, et al. "Understanding how dimension reduction tools work." JMLR 2021 [5] Damrich, et al, “From t-SNE to UMAP with contrastive learning”, ICLR 2023 [6] Van Assel, et al. "SNEKhorn: Dimension reduction with symmetric entropic affinities." NeurIPS 2023.

Thank you for your response, though I feel the tone could have been more respectful. To clarify, I’d like to briefly summarize my point.

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

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

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

Thank you for the discussion. I will not further discuss with authors.

We strongly disagree with the assessment of our paper. Here's our detailed reply:

The proposed method is limited to PACMAP.

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

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

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

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

We thank the reviewer for the detailed and encouraging review. Here are our detailed response to each question or concern raised by the reviewer:

• What is the computational time of ParamRepulsor compared to other methods?

We 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.

• What are the limitations of ParamRepulsor?

While 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.

We thank the reviewer for the detailed review and suggestions. Here are our detailed response to each question or concern raised by the reviewer:

• Are parametric methods comparable to non-parametric methods?

See common response 1.

• How does the weight on MN sampling affect the global structure?

To 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). In 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.

• How do other NE algorithms react to parameters related to the global-local trade-off?

Non-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.

• Effectiveness of Hard Negatives with Increasing Dimensionality.

Yes, 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].

• What are the limitations of ParamRepulsor?

While 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.

[1] Robinson, Joshua, et al. "Contrastive learning with hard negative samples." ICLR 2021.

[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.

[3] Liu, Minghua, et al. "Openshape: Scaling up 3d shape representation towards open-world understanding." NeurIPS 2023.

[4] Radenovic, Filip, et al. "Filtering, distillation, and hard negatives for vision-language pre-training." CVPR 2023.