A Heat Diffusion Perspective on Geodesic Preserving Dimensionality Reduction

Summary

In the paper "A heat diffusion perspective on geodesic preserving dimensionality reduction", the authors develop a new embedding method (HeatGeo), conceptually close to PHATE (Moon et al 2019) in that it performs MDS on some kind of diffusion distances. The authors make some strong claims about HeatGeo: (1) it is SOTA in preserving manifold distances; (2) it is SOTA in preserving cluster structures; (3) it can approximate both PHATE and t-SNE depending on parameters. I did not fully understand/follow all the math, but I found the paper nevertheless interesting as it gives a systematic/principled treatment of heat diffusion MDS methods. That said, I was not entirely convinced by the evaluations and especially claims (2) and (3) seem to me too strong and IMHO not sufficiently supported by the shown evidence. Also, many places were not really clear to me. Overall I am somewhat on the fence about this paper: it seems it is not fully ready yet. I am giving it a borderline score.

Strengths

* Systematic/principled mathematical treatment (which admittedly I did not fully grasp) * Benchmarks of several embedding methods on artificial datasets * Applications to real RNAseq data * Relationships between HeatGeo and existing methods (PHATE/t-SNE)

Weaknesses

* Relationship to PHATE is not very clear * Very bold claims that are not fully supported by the evidence * Insufficient evaluation, in particular many embeddings are not shown * Runtime is not discussed Now in more detail: * In spirit, the method seems very similar to PHATE. First, kNN graph is used to construct NxN distance matrix between all points (using heat diffusion). Second, MDS is used to produce the embedding. Of course there are many small differences from PHATE in how exactly all of this is setup up, and the way this paper is written, it comes across as more mathematically principled than PHATE. But in the end, I was still confused about what is the MAIN conceptual/algorithmic difference. That's very important in order to judge the relative novelty of HeatGeo. Is it conceptually a minor tweak to / simplification of PHATE, or is it conceptually a very different thing? * One bold claim is that HeatGeo outperforms other methods in preserving clusters (supported by Table 2). This is conceptually surprising to me, because I expect some trade-off between preserving geodesic distances and preserving clusters (similar trade-off was discussed in Ref [2]: https://jmlr.org/papers/v23/21-0055.html), so it's odd if the same method (HeatGeo) wins in both competitions. Also, we know that methods like t-SNE and UMAP really excel in representing clusters in high-dim data (just try them on MNIST) but more geodesic/MDS methods like Isomap or PHATE perform worse (again, just try them on MNIST). To be more convinced here, I would like to see the embeddings corresponding to Table 2. Also, I don't think "Tree" is a good dataset for clustering because we don't expect k-means to pick up the tree branches: just look at HeatGeo if Tree in Figure 1 -- How can k-means separate the branches? I don't really understand why HeatGeo performs well here in Table 2. Rather than the Tree, I would like to have some toy dataset with 100D Gaussians differently far away from each other. I would also love to see MNIST (a subset of MNIST). * Another bold claim is that HeatGeo approximates SNE/t-SNE. I was very surprised to read that, because I have never seen SNE/t-SNE formulated as an MDS problem, and assumed it is impossible. However, I don't really see much evidence that this is true. Can you do HeatGeo of MNIST that would look like t-SNE? In the EB dataset (Figure 3), can you change HeatGeo params to make it look like t-SNE? The same for the PBMC dataset (Figure 4)? * Figure 1: This is the main motivational figure showing that HeatGeo is very good at unrolling Swiss roll, whereas t-SNE creates "artifical clusters". Personally, I think it does not make much sense to apply t-SNE to an intrinsically 2D dataset because t-SNE is designed for reducing dimensionality (that's why it uses t-distribution kernel, unlike SNE). When working with intrinsically 2D data, it makes much more sense to use SNE instead of t-SNE. And indeed, SNE is much better at unrolling Swiss roll than t-SNE (example: https://jlmelville.github.io/smallvis/swisssne.html). As the authors discuss SNE in their paper anyway, I think it would be good to add SNE to the comparison tables and also to Figure 1 (can be done e.g. via openTSNE). By the way, Isomap can also unroll the Swiss roll perfectly. * As the HeatGeo relies on MDS, it constructs a dense NxN distance matrix and so has O(N^2) complexity. All the datasets used in the paper are very small. This is unlike t-SNE/UMAP which can be run on tens of millions of points easily. I think this has to be discussed, e.g. in Section 7. SMALLER POINTS AND QUESTIONS * line 124: classic MDS does not optimize objective (5). * line 148: Ref [2] shows that UMAP's effective loss function is very different from its stated loss function, so this formula is actually misleading. See also https://proceedings.neurips.cc/paper/2021/hash/2de5d16682c3c35007e4e92982f1a2ba-Abstract.html and https://openreview.net/forum?id=B8a1FcY0vi which develop this argument. * line 194: "small t can lead to disconnected graphs" -- I don't understand this sentence, I thought the graph does not depend on t, no? You first construct the graph and the laplacian L, and only later you use the diffusion time t. * line 211: Algorithm 1 -- I don't really understand how L is constructed. What is the underlying graph? Is it a kNN graph, what are the weights? What is the k value (number of neighbors)? I think this is not really spelled out in the text. PHATE used some complicated setup with alpha-kernels, are you also using this here? * Table 1: this table is missing t-SNE and UMAP rows. Also, I would like to see SNE in there, and Isomap. * Figure 3 caption: "UMAP and t-SNE do not capture the continuous manifold" -- actually UMAP looks pretty similar to HeatGeo to me. Also, Ref [2] argues that higher attraction in t-SNE leads to better manifold preservation, so UMAP is better at showing the manifold (which is what we see in your Fig 3) but one can do even better by using higher exaggeration in t-SNE. Maybe worth mentioning. * line 314: "HeatGeo interpolated to PHATE for \rho->1" -- I was confused by that. What is rho? It wasn't really discussed before, I don't see it in section 5 that discusses relation to PHATE. I do see \rho in Algorithm 1 but not in the text of Section 4. So it's mysterious. * Figure 4 does not show t-SNE, but Figure 5 in the Appendix does. I am surprised by how bad t-SNE looks. I have seen t-SNE of various PBMC RNAseq datasets many times, and t-SNE is usually very good at separating cell types. But in your appendix figure t-SNE looks very poor. Why is that?

Questions

See above

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

See above

Summary

The authors propose heat geodesic embeddings, a novel approach to perform graph embeddings that is motivated by Riemannian geometry (Varadhan's formula and the parabolic Harnack inequality), which allows for directly linking heat diffusion on graphs to manifold distances. They performed experiments to demonstrate the efficacy of their approach.

Strengths

- Originality: The proposed heat geodesic embedding and the approach is , to the best of my knowledge, original and novel. - Significance: It is certainly important to study spectral embeddings nowadays, and I find the authors' methodological contributions to be significant. - Quality: The quality of the theoretical derivations and experimental evaluations is sound, to the best of my knowledge. - Clarity: Despite the advanced mathematical material involved, the authors presented and motivated their approach in a clear and convincing manner.

Weaknesses

- there are no obvious weaknesses in the paper. The method is presented well and is straightforward. The authors performed experiments which covered most of the bases.

Questions

- see sections above.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

- no negative societal impact.

Summary

The authors develop specific heat diffusion kernels for manifold embedding. They define a heat kernel based on the Varadha formula. The authors try to weave some connections with existing methods of DR such as PHATE, t-SNE, etc. They run some experiments

Strengths

The paper is well written except for the organization, clarity, and self-containedness. The presented developments about the geodesic distance and the heat diffusion kernel are of interest for the manifold learning community. The authors quite honestly acknowledge some of the limitations of their work.

Weaknesses

The writing style is too dense, poorly structured, with a succession of (too) short sections, referring to each other too many times, and often missing key information. Isomap is not cited and not compared to (in Fig. 1 for instance; later it seems that Isomap is actually used, without saying the name and still without a bibliograpcal reference, or is 'shortest path' with stress-based MDS instead of classical MDS? This can be referenced too, most probably). The mathematical notation is misleading and unusual for manifold learning (x and y in the same space! use x_i and x_j ?). The experiments have unclear/contradictory objectives: to detect manifold structures and clusters? The COIL-20 or 100 data set should then be considered. The results in Fig. 1 are not convincing at all: Isomap does better. In experiments related to clustering, the reader might always question the purposefulness of assessing cluster separation in methods which are local and depending on graphs; a disconnected graph somehow automatically guarantees cluster separation. On the other hand, the arrangement of clusters with respect to each other might actually be more relevant. The clustering experiments on Swiss roll and tree are far-fetched (use COIL-20?), with completely artificial clusters. Over-expression of clusters or even spurious clusters have been reported with many 'local' methods of manifold learning. Assessing the preservation of distances or neighbourhoods might be less of a stretch between the focus on geodesic distances and the current interest for clustering with those methods in communities of practitioners.

Questions

What is V(x,sqrt(t)) ? please define and/or give an intuitive interpretation. The section about Varadhan's formula seems to end prematurely. Probably Vradhan could gain to be detailed more while the subsequent paragraphs in Preliminaries could be shortened or dropped (except for the quick reminder about stress-based MDS). Section 3 about related work is going too fast and lacks details (reminder of P for PHATE? drop SNE that is quite well known). In section 4, if distance order preserving matters, why not compare to non-metric MDS too? Can you clarify Section 4? Definition 4.1 is cryptic and unintuitive; what is the meaning of sigma? In proposition 4.1, what is |x-y| ? absolute value? distance like ||.||_2 elsewhere? Why come back on MDS? Merge the presentation of MDS and its specific weighting? Section 5 is also wanting to embrace everything within limited space: alonger version in appendix and more details about the core contribution of the paper Ref 33: Cédric Villani has a twin brother?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Yes. They have. No potential negative societal impact here.

Summary

The paper introduces a dimensionality reduction technique based on heat kernels and called HeatGeo. The main idea is to learn a mapping that projects points to a low-dimensional space (ideally 2 or 3-dimensional for visualization) so that relative distances between pairs of points satisfy the same order as distances on some (complete Riemannian) manifold that uses some distance based on the heat kernel.

Strengths

Originality: The idea of using heat kernels for dimensionality reduction is not new (e.g. Belkin & Niyogi [1] that proposed Laplacian eigenmaps). This paper proposes a generalization of previous techniques by exploiting Varadhan's formula (Eq. (1)) and by bounding the calculated distance on a low-dimensional complete Riemannian manifold. They show that the ordering of distances in the high-dimensional space tends to be preserved on the low-dimensional manifold. Quality and Clarity: The paper is well-written and mentions different approximation techniques that can be used to approximate the computation of the kernel matrix since the algorithmic complexity is cubic in the number of points. Overall, the paper shows that the proposed approach tends to preserve clusters and the ordering of distances in the low-dimensional space better than standard approaches such as t-SNE and UMAP. Significance: The significance of the approach is difficult to quantify. As most dimensionality reduction techniques that are often used for qualitative evaluation in the machine learning literature, the proposed approach can improve the understanding of a data set with a visualization that preserves the original general structure.

Weaknesses

I do not see a particular weakness in the formulation of the approach which has a nice theoretical justification. The main weakness of the paper is that it mainly focuses on dimensionality reduction and visualization which already have widely used techniques (e.g. t-SNE and UMAP) that are used only for qualitative evaluation in practice.

Questions

I have no questions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

This article deals with representation learning and dimensionality reduction of high dimensional noisy datasets. The proposed method relies on heat diffusion. More precisely, assuming their data can be viewed as Riemannian manifolds and based on Varadhan’s formula, the authors define the notion of heat-geodesic dissimilarity. According to the authors, using the heat equation guarantees the conservation of geodetic distances between the raw data and its integrated counterpart. This dissimilarity is then used through multidimensional scaling (MDS) to define their so-called heat geodesic embedding. Afterward, the authors theoretically compare their method to the start-of-the-are ones. In particular, in the appendix, they attempt to create a generalized framework for dimensionality reduction methods. Last, they conduct numerical experiments to test their algorithm on different data types. In particular, they want to ensure that their method effectively preserves geodetic distances. They also seek to ensure that the inherent data structures are conserved: Preserving clusters or data temporality, for instance.

Strengths

- Interesting idea, based on the solid formalist of Riemannian manifolds. - Efforts to unify different embedding approaches (especially in the appendix) with comparisons with existing methods. - Numerical experiments demonstrating the benefits of heat geodesic embedding for understanding data.

Weaknesses

There are typos and undefined notations in several places (see below). This is a disservice to the paper.

Questions

Some comments: - Line 66: $n$ not defined. - Line 67: I think it should be $\frac{n}2$ instead of $2n$. - Eq (2): $V(x,\sqrt{t})$ not defined. - Paragraph starting line 79 (Graph construction and diffusion): $n$ is not defined, although we understand it is the sample size in context. - Line 88: Notation $[n]$ not defined. - Line 94: Add references when referring to literature. - Line 160: Should the $n$ not be a $d$ here? - Line 181: they use the a distance... -> the _or_ a. - Line 304: Strange line break.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Not concerned.

reply to authors

This is to acknowledge that I have read the author's response to my review. Thanks

Thank you

I thank the authors for the detailed rebuttal to all the reviews. I am increasing my score from 4 to 5.

MNIST

> We have added experiments on MNIST and COIL-20; two datasets for which the manifold hypothesis may not be respected. Our methods show greater accuracy on the swiss roll and tree datasets, and competitive performance on the other datasets (see the full results in Tab.1 of the attached PDF). Thanks for doing this experiment. In this new Table one can clearly see that on both MNIST and COIL, t-SNE wins with a large margin. I would not call it "competitive performance" :) Just to be clear: I don't think it hurts your paper in any way! Your paper is clearly about manifold learning and MNIST is not a manifold. I would just like that this is clearly described, and that the method is not oversold.

I have read the authors' rebuttal.

I have read the authors' rebuttal.