MAP IT to Visualize Representations

Dear reviewer L3aD,

Thank you for your review! I have marked changes in blue in the revised manuscript.

Section 3.1, $Z_q$ and $Z_p$ not formally defined: In order to motivate the theory in Section 3 on CS as a projective divergence, I take as a starting point $q_{ij} = \left[ 1+||\vec z_i-\vec z_j||^2 \right]^{-1} / Z_q$ where $Z_q = \sum_{n, m} \left[ 1+||\vec z_n-\vec z_m||^2 \right]^{-1}$ is an explicit normalization factor. Furthermore, $p_{ij} = \exp\left(-\kappa_i ||\vec x_i-\vec x_j||^2 \right)/ Z_p$, with normalization factor $Z_p = \sum_{n, m} \exp(-\kappa_i ||\vec x_n-\vec x_m||^2)$. This is now made explicit on page 2.

Most important question: With the above starting point and definitions, the MAP IT cost function will basically align the degrees of corresponding nodes in the target space versus the input space. However, in order to use the same way to create input space similarities for t-SNE and MAP IT, to have a similar underlying foundation, I discuss in Appendix C, page 22 that in practise symmetrized probabilities are used such that $p_{ij} = \frac{p_{i|j} + p_{j | i}}{2n}$ with $p_{j|i} = \frac{\exp\left(-\kappa_i ||\vec x_i-\vec x_j||^2 \right)}{\sum_{n \neq i} \exp(-\kappa_i ||\vec x_i-\vec x_n||^2)}$ and likewise for $p_{i|j}$. The projective property with respect to $Z_q$ is still in force. You are right that this basically creates unit node degrees in the input space and thus more uniform marginal input space probabilities. This means that the target space marginal probabilites will be optimized towards a more uniform distribution too. The node degree is a quantity that relates a point to all other points it is connected by the strength (weights) on the connections. A node degree forced to be one seems to me as a means to avoid very small weights or very strong hubs and such properties should be beneficial to transfer to the target space.

Lack og quantitative evaluations: I agree that this should have been included from the start, thanks. I included both results for knn recall (input space vs. target space) and for class-wise knn recall in the target space. You can find this on Appendix C, page 22 in the revised manuscript.

Conceptual question 1: Thanks for raising these conceptual questions. The use of a projective divergence is what makes direct normalization of probabilities unnecessary, either for a cost function only based on pairwise affinities or for a cost function based on marginal affinities. Actually, in Proposition 11 I do show that MAP IT as a special case reduces to the CS divergence used with only pairwise affinities. However, your question regarding potentially having marginal probabilities for the KL loss is intriguing. In that case, the direct normalization of probabilities would be needed since the KL is not projective. I added a paragraph in Appendix C, page 26 where I indicate that in future work, Definition 4 may be extended to a map KL divergence.

Conceptual question 2: Thanks for pointing out the N^2 term. As mentioned to reviewer vQ36, the use of the CS divergence to derive MAP IT does render explicit normalization of probabilities unnecessary. But as you point out, a quadratic complexity still arises in the (entropy) weighting and in future work the impact of these weighting factors and how they relate to each other should be further studied. I toned down the claim about MAP IT being inherently scalable in Abstract, etc, for that reason. I did perform a preliminary analysis where I computed these quantities by only using nearest neighbors of points in the computation, where the nearest neighbors are defined with respect to the input space. This is explained on page 25 and the result is shown in Figure 14. This relates to the discussion in Section 3.4 MAP IT via local neighborhoods.

Perplexity: The perplexity is related to the Gaussian bandwith $\kappa_i$ parameter for computing $p_{ij}$. It is not related per se to the use of $k=10$ nearest neighbors for the computation of the attractive and repulsive forces, as discussed in Figure 3 and in Appendix C. However, I included in Appendix C, page 22 a more detailed discussion of the definition of perplexity and the $\kappa_i$.

Scalable implementation: In Appendix C, page 25 implementation details are discussed. The current code is not very efficient, and I can of course only agree that it would have been better to have a large-scale implementation. Hopefully, there is room to have the fundamentally different ideas that MAP IT represents and the current demonstrations published even if the implementation can still be improved.

MINOR issues Thanks for these good suggestions! They have all been implemented/fixed. For instance, including a motivation in Section 3.3, discussing Damrich (2023), discussing t-SNE vs Laplacian eigenmaps in Appendix A.

Thank you for your response. I am only going to respond to my main confusion, because I am afraid I still don't follow:

With the above starting point and definitions, the MAP IT cost function will basically align the degrees of corresponding nodes in the target space versus the input space.

Just to clarify. The way you define p_ij on page 2 ensures that marginal p_i (row sums) will all be exactly identical (because kappa_i values are adjusted to make each row sum to 1). Is that right? (I understand that in practice you use symmetric affinities which are slightly different, but as you say this is not important.)

If so, your loss function is DATA INDEPENDENT: q_i's need to match a constant vector of identical values p_i, whatever the original dataset was!

I don't understand how this can possibly result in anything useful. In fact embeddings of all datasets with the same sample size should be all identical. But clearly this is not the case in the figures in your paper. How come?

You are right that this basically creates unit node degrees in the input space and thus more uniform marginal input space probabilities. This means that the target space marginal probabilities will be optimized towards a more uniform distribution too. The node degree is a quantity that relates a point to all other points it is connected by the strength (weights) on the connections. A node degree forced to be one seems to me as a means to avoid very small weights or very strong hubs and such properties should be beneficial to transfer to the target space.

Here you are arguing that the fact that "target space marginal probabilities will be optimized towards a more uniform distribution" is a good thing and not a bad thing. But there is no other term in the loss function! That's all there is that you are optimizing. If the entire algorithm is: "make q_i values uniform", then how can it work?

Dear reviewer vQ36,

Many thanks for your review! Your review was very useful to me, also pointing out some literature which I hadn't cited (Artemenkov, Panov) and also making me go deeper into papers I had already cited (Böhm et al. (2022) and Damrich et al. (2023).

Quadratic complexity: The use of the CS divergence to derive MAP IT does render explicit normalization of probabilities unnecessary. But as you point out, a quadratic complexity still arises in the (entropy) weighting of the attractive and repulsive forces and in future work the impact of these weighting factors and how they relate to each other should be further studied. I toned down the claim about MAP IT being inherently scalable in Abstract, etc, for that reason. I did perform a preliminary analysis where I computed these quantities by only using nearest neighbors of points in the computation, where the nearest neighbors are defined with respect to the input space. This is explained on page 25 and the result is shown in Figure 14. This relates to the discussion in Section 3.4 MAP IT via local neighborhoods. This is however a question which merits further work and analysis.

Timings: On page 25 it is explained that the current implementation is based on a matrix operation $(\boldsymbol{D}- \boldsymbol{M}) \boldsymbol{X}$ where $\boldsymbol{M}$ encodes attractive and repulsive forces according to and where $\boldsymbol{D}$ is the diagonal degree matrix of $\boldsymbol{M}$. The matrix $\boldsymbol{X}$ stores all data points as rows. I am working on a more efficient knn graph implementation, although the main idea and concept is conveyed. This is why timing is not explicitly reported.

Suggested papers: I have included the suggested papers both in Section 2, page 3, in Appendix A, page 13 and other places too.

Optimization parameters for SNE, Belkina et al. (2019): Thanks for pointing me to this paper. I appreciate it a lot. Since the benchmark datasets studied in the paper are quite typical of the type of datasets that state-of-the-art implementations of t-SNE, UMAP, PacMap, etc, have been developed for an optimized for with their hyperparameters, I opted for those. I have however on page 25 included a paragraph where I discuss Belkina et al. (2019). I agree that it may be that e.g. t-SNE could perhaps benefit from some more parameter tuning. At the same time, I tried to keep MAP IT very clean, not even using early exaggeration to not end up not optimizing a true divergence, and to stay close to the basic t-SNE type of approach. MAP IT could probably be improved by optimizing hyperparameters more.

Delta-bar-delta: I chose the delta-bar-delta since it was common in the t-SNE literature. I observed slightly faster growing of structure in the MAP IT embedding when using this approach.

Current approaches not sufficient?: Thank you for this question, I can see why you would ask it. I am not necessarily saying that the current approaches are not sufficient. But I observe some differences for MAP IT compared to the alternatives, and I think it is because MAP IT is fundamentally different in its approach.

Thanks again, I appreciate your review and your efforts!

Dear reviewer LbLf,

Let me first thank you for the review and for appreciating my efforts to provide a new perspective to dimension reduction. This is much appreciated. I have made several changes in the manuscript and in the experimental part to try to make the paper better. I have marked changes in blue in the revised manuscript.

Typos: I thank you for pointing out the typos. I have fixed these and I hope that I have avoided adding new ones as I have worked on the revision.

Normalization constants: I realized when reading your comment, and also when reading comments by reviewer L3aD, that I should have been more precise. I have now added definitions for the normalizing constants $Z_q$ and $Z_p$ in relation to Eq. (1), page 2, in Definition 1, just before Eq. (7) as well as several places in Appendix C.

Thank you again for your review!

Dear reviewer BmiL,

I sincerely thank you for the review. This is much appreciated. I have made several changes in the manuscript and in the experimental part in order to accommodate your suggestions and comments. I have marked changes in blue in the revised manuscript.

Quantitative results: Thank you very much for proposing to add quantitative results. I agree that this should have been included from the start. I included both results for knn recall (input space vs. target space) and for class-wise knn recall in the target space. You can find this on page 22 in the revised manuscript. The quantitative results for MNIST shed light on MAP IT showing that the method is probably somewhat better at capturing cluster structure compared t-SNE and UMAP, maybe at the expense of capturing more continuous manifold-like structures. This makes intuitive sense when looking at Figure 1.

Normalization: You are right that normalization is not required by e.g. UMAP and I tried to be a bit more specific to say that the MAP IT theory shows when normalization is not needed when a statistical divergence is the base for the dimensionality reduction. For instance, in Appendix C, concluding remark, it now reads The role of normalization for divergences to be used as dimensionality reduction methods follows directly from the MAP IT theory.

Local neighborhoods: Preservation of local neighborhoods is also a key part of e.g Laplacian eigenmaps and t-SNE itself, but via pairwise similarities only. For instance, on page 21 I included the sentence this shows that MAP IT is able to capture information in wider local neighborhoods compared to CS t-SNE which only captures local information via pairwise affinities, a property it shares with its KL counterpart t-SNE and methods such as Laplacian eigenmaps \citep{Belkin2003}.

t-SNE and kernel density: Actually, in Bunte, Haase and Villmann (2012) "Stochastic neighbor embedding (SNE) for dimension reduction and visualization using arbitrary divergences" a form of t-SNE kernel density variant was discussed, but this it quite different from MAP IT.

However, I have been pondering your question "Can you explain why kernel smoothing doesn't apply to t-SNE?" I think that similar to the new quantity I propose, which I called the map CS divergence (Definition 4) a map KL divergence can also be possible. This would probably yield a related KL-based interpretation, but it would be in terms of the marginal probabilities and not the pairwise similarities which standard t-SNE optimizes. I added a paragraph about this on page 26, as a potential interesting avenue for future research.

Thanks again!