Supervised and Semi-Supervised Diffusion Maps with Label-Driven Diffusion

Questions

1. Dimensionality reduction range: Thank you for your question. You are correct that the number of reduced dimensions could be treated as a hyperparameter, and we could select the best number for each algorithm. However, we chose to reduce the dimensionality to a range of 1 to 30 dimensions to demonstrate that our method is insensitive to the choice of this parameter and performs well not only for the optimal number of dimensions but also across a broader range of dimensions. This helps highlight the robustness of our method. We have further elaborated on this aspect in Appendix E.4, where we show the performance of our method across different dimensionalities.

2. Choice of distance metrics for data and label kernels: Thank you for your question. The choice of distance metric should ideally be based on the nature of the data and labels. For example, in the toy problem presented in Section 6, where the labels represent rotation angles, we used angular distance due to the cyclic nature of angles. We also observed that the Euclidean distance, although slightly worse, still produced reasonable results. For the real-world datasets evaluated in Section 6, we used the Euclidean distance for both the data and label kernels for simplicity. However, we acknowledge that carefully selecting more suitable distance metrics for each dataset could further improve the results.

Thanks for your constructive feedback. We appreciate your time and the helpful comments you've provided.

1. Framework figures and comparison with related work: Thank you for your comment. In response to your feedback, we have added Appendix A.2 to the revised paper, which includes preliminary block diagram figures for both SDM and SSDM. We plan to enhance these diagrams for the camera-ready version, including improvements such as adding an illustration to show how $\mathbf{D}$ is constructed from the samples and $\mathbf{P}$ from the available labels.

Regarding comparison with related work, section 2 (Related Work) discusses common approaches for incorporating supervision (labels) into manifold learning techniques. The key distinction of our method lies in our new approach of integrating supervision by treating the labels as a second modality. Furthermore, our approach builds on the unsupervised Diffusion Maps framework and introduces a label-driven diffusion process. This process extracts the shared geometry between the data and the labels, which significantly enhances the resulting embedding as we show on multiple real-world datasets in Section 6, especially for downstream tasks such as classification and regression.

We have made changes in the revised version of the paper to more clearly highlight these differences, as you suggested. Additionally, we have added a new Appendix G, in which we extend the Related Work section and provide additional information about alternating diffusion. Furthermore, in the new Appendix C.1 of the revised version, we compare the performance of our label-driven diffusion against standard diffusion (used in the unsupervised Diffusion Maps) using new heatmap visualizations of the kernels. These results highlight the effectiveness of our approach.

2. Elaborating on alternating diffusion: Thank you for your suggestion. In response, we have added a new Appendix G in the revised version of the paper, where we extend the Related Work section and provide a more detailed explanation of the alternating diffusion process, and . We hope this additional content will help to better clarify and expand on this important aspect of our method.

3. Evaluation on additional datasets: Thank you for your suggestion. In the revised version, we have included additional evaluations of SSDM on the datasets previously reported for SDM. The results are now presented in Table 5 of the new Appendix E.3. Furthermore, in the new Appendix F, we evaluate 6 more large datasets, providing both the evaluation results and runtime comparisons. We kindly refer you to a separate post in this thread, where we present these results.

4. Discussion of future work: Thank you for your suggestion and valuable input. As suggested, in the revised version of the paper, we have added more details about possible future work in Appendix G.3.

One promising direction involves incorporating our multi-view approach for integrating labels into manifold learning methods, and applying it to other multi-view algorithms as we have done here with alternating diffusion.

Additionally, we aim to explore other kernel interpolation schemes for combining data and label information. While the current approach works effectively, other interpolation methods could offer more flexibility and improve performance in different settings.

Another potential direction is to move beyond the power mechanism we use for adjusting the influence of spectral components (eigenvalues). Instead of raising the eigenvalues to powers $t$ and $1-t$, we could learn the amplitude of each eigenvalue explicitly. This would allow us to modify the order and influence of spectral components dynamically, potentially leading to better performance by adjusting the contributions of each component to the learned embedding.

Furthermore, as we have demonstrated the effectiveness of our label-driven diffusion in a graph setting, we believe it could also be beneficial to explore its incorporation in the context of geometric deep learning.

5. Computational complexity: We provide a detailed analysis of the time and space complexity of both SDM and SSDM in the new Appendix F. The complexity of SDM is $O(n^4)$, making it impractical for large or medium-sized datasets, while SSDM has a complexity of $O(n^3)$, suitable for datasets up to 10,000 samples.

The optimized SSDM, also detailed in the new Appendix F, has a complexity of $O(k^2 \cdot n)$, making it scalable for very large datasets (over 100,000 samples). Additionally, it is implemented using torch to leverage GPU acceleration.

For comparison, t-SNE has a complexity of $O(n^2)$ (optimized versions: $O(n \cdot \log n)$), and UMAP has a time complexity of $O(d \cdot n^{1.14})$, where $d$ is the data dimensionality. Our method, for smaller values of $k$, is more time-efficient than these alternatives.

3. Scaling up: We appreciate your comment regarding our method scale to larger datasets and higher-dimensional spaces, and we have addressed these concerns in the revised version of our paper.

In response, we have added a new Appendix F where we provide a detailed analysis of the time and space complexity of both SDM and SSDM. The complexity of SDM is $O(n^4)$, which makes it impractical for large or even medium-sized datasets. Conversely, SSDM has a complexity of $O(n^3)$, making it more feasible for medium-sized datasets, up to approximately 10,000 samples.

In general, large datasets pose a known challenge in kernel methods like ours. Typically, using sparse kernels reduces both computational and storage demands. However, since our method involves kernel matrix multiplication and since the multiplication of two sparse matrices may result in a dense matrix, this approach is not suitable for scaling up our method. One possible solution is the "landmark" [1] approach, which has been adapted for alternating diffusion in recently [2]. This approach approximates the eigenvectors of large alternating diffusion kernels by sampling $k$ landmark data points, computing the eigenvectors for the small $k \times k$ kernel, and then expanding them to the entire dataset.

To address this limitation, we have implemented a simpler sampling approach to create an optimized version of SSDM that is suitable for large-scale datasets. For example, on our basic hardware (described in Appendix B), the optimized SSDM processes datasets like MNIST and Fashion-MNIST (each containing 70,000 samples) in just 8 seconds. Additionally, the Rice dataset, which contains 3,810 samples and took 55 seconds to process with SSDM (as reported in Table 6), is now processed in just 0.03 seconds using the optimized SSDM. The optimized SSDM efficiently handles high-dimensional data, as demonstrated by its performance on MNIST (784 features), Fashion-MNIST (784 features), and Isolet (617 features).

In the optimized version, rather than constructing the label and data kernels $\mathbf{P}$ and $\mathbf{D}$ with dimensions $n \times n$, we randomly sample $k$ labeled samples from the training set. This results in a label kernel $\mathbf{P}$ of size $k \times k$ and a data kernel $\mathbf{D}$ of size $k \times n$, where $k$ is set to $0.01 \cdot n$ if $n > 10,000$ and to $0.1 \cdot n$ if $n \leq 10,000$ in our experiments. Through empirical testing, we found that a small proportion of labeled samples can effectively represent the space in large datasets. If $n$ becomes very large, $k$ can be set to any fixed small value, smaller than $0.01 \cdot n$. Apart from adjusting the kernel dimensions, the other steps of the optimized SSDM remain identical to those in SSDM. This modification reduces the complexity of the optimized SSDM to $O(k^2 \cdot n)$, making it scalable for very large datasets (greater than 100,000 samples). Additionally, the optimized SSDM is implemented using torch, which leverages GPU acceleration.

For comparison, t-SNE has a time complexity of $O(n^2)$, with optimized versions having a complexity of $O(n \cdot \log n)$, while UMAP has a time complexity of $O(d \cdot n^{1.14})$, where $d$ is the dimensionality of the data. As such, for smaller values of $k$, our method is more time-efficient than these alternatives.

In the newly added Appendix F, we provide a comprehensive description of the optimized SSDM, along with detailed performance and runtime comparisons based on the procedure outlined in the Experimental Results section. Additionally, we wish to kindly refer you to our general post in this thread, where we present both evaluation results and runtime comparisons on large datasets, comparing between optimized SSDM, unsupervised Diffusion Maps, and semi-supervised UMAP. In which our SSDM achieves the best performance on 3 out of the 6 datasets, and is significantly faster than semi-supervised UMAP across all datasets. We will upload the code for the optimized SSDM in the supplementary materials within the next few days.

[1] Shen, Chao, and Hau-Tieng Wu. "Scalability and robustness of spectral embedding: landmark diffusion is all you need." Information and Inference: A Journal of the IMA 11.4 (2022): 1527-1595.

[2] Yeh, Sing-Yuan, et al. "Landmark Alternating Diffusion." arXiv preprint arXiv:2404.19649 (2024).

4. Related work: Thank you for your comment on the related work section. In response to your feedback, we have added Appendix G in the revised version of the paper, which provides a comprehensive overview of key approaches in multi-view learning. Specifically, we discuss methods such as co-training, canonical correlation analysis (CCA), multi-kernel learning methods (e.g, alternating diffusion), and multi-view deep learning.

Thank you for your time and feedback. We appreciate your suggestions and the opportunity to improve our paper.

1. The novelty in our method: We appreciate your feedback, but we believe there may be a misunderstanding regarding the novelty of our approach. While it is true that we build on alternating diffusion and kernel methods, the key innovation in our work lies in how we incorporate labels as a distinct data modality within a multi-view learning framework. To the best of our knowledge, this is the first work to introduce this novel perspective, where labels are treated as a second data modality and integrated into the dimension reduction process to guide learning. This approach has the potential to be applied to other multi-view learning algorithms as well.

Furthermore, we extend alternating diffusion to a partial alignment setting to address the challenge of handling unlabeled data, which the original alternating diffusion framework does not accommodate. Our solution, from a graph perspective, involves adding isolated nodes to the label graph to handle unlabeled samples that lack direct alignment with labels, a crucial aspect for supervised and semi-supervised settings. We also provide a theoretical justification for this extension to the partial alignment setting.

In the new Appendix C.1 in the revised version of the paper, we compare the performance of our label-driven diffusion against standard diffusion using heatmap visualizations of the kernels. These results highlight the effectiveness of our approach.

2. Comparison with recent manifold learning methods: Thank you for your comment. We believe we have addressed the most relevant work in the field. In our evaluation, we compare our method to UMAP [1], which is often considered one of the gold standards today for dimensionality reduction, along with other classical methods.

While a few newer methods such as TriMap [2], PaCMAP [3], and TopoMap [4] have garnered attention within the community, they do not currently support label incorporation, which makes them less suitable for supervised or semi-supervised settings like ours. Furthermore, while these newer approaches bring interesting ideas to the table with their own advantages and limitations, none have yet been conclusively proven to outperform UMAP or other established algorithms across all scenarios.

For these reasons, we chose to focus our comparisons on well-known algorithms that have demonstrated broad effectiveness and include established supervised and semi-supervised variants, which are more aligned with the goals of our work. Comparing our approach to methods like PaCMAP, which lacks a clear advantage over other algorithms, would not provide additional insights beyond the comparison with UMAP.

This practice of comparing to the most prominent methods in recent years is common within the manifold learning community. For example, the recently published manifold learning algorithm HeatGeo [5], presented at NeurIPS 2024, includes comparisons to UMAP [1], t-SNE [6], Isomap [7], Diffusion Maps [8], and PHATE [9]. In our work, we compare against all of them, except for PHATE. Additionally, we compare against other methods such as Laplacian Eigenmaps, Locally Linear Embedding [10], supervised and semi-supervised UMAP, and semi-supervised t-SNE.

[1]McInnes, Leland, John Healy, and James Melville. "UMAP: Uniform manifold approximation and projection for dimension reduction." arXiv preprint arXiv:1802.03426 (2018).

[2]Amid, Ehsan, and Manfred K. Warmuth. "TriMap: Large-scale dimensionality reduction using triplets." arXiv preprint arXiv:1910.00204 (2019).

[3]Wang, Yingfan, et al. "Understanding how dimension reduction tools work: an empirical approach to deciphering t-SNE, UMAP, TriMAP, and PaCMAP for data visualization." Journal of Machine Learning Research 22.201 (2021): 1-73.

[4]Doraiswamy, Harish, et al. "TopoMap: A 0-dimensional homology preserving projection of high-dimensional data." IEEE Transactions on Visualization and Computer Graphics 27.2 (2020): 561-571.

[5]Huguet, Guillaume, et al. "A heat diffusion perspective on geodesic preserving dimensionality reduction." Advances in Neural Information Processing Systems 36 (2024).

[6]Van der Maaten, Laurens, and Geoffrey Hinton. "Visualizing data using t-SNE." Journal of machine learning research 9.11 (2008).

[7]Balasubramanian, Mukund, and Eric L. Schwartz. "The isomap algorithm and topological stability." Science 295.5552 (2002): 7-7.

[8]Coifman, Ronald R., and Stéphane Lafon. "Diffusion maps." Applied and computational harmonic analysis 21.1 (2006): 5-30.

[9]Moon, Kevin R., et al. "PHATE: a dimensionality reduction method for visualizing trajectory structures in high-dimensional biological data." BioRxiv 120378 (2017).

[10] Roweis, Sam T., and Lawrence K. Saul. "Nonlinear dimensionality reduction by locally linear embedding." science 290.5500 (2000): 2323-2326.

Thanks for the rebuttals, which have addressed my concerns well. I have also read other reviewer's comments. I am willing to increase my score from 5 to 6.

3. Performance Comparison between SDM and SSDM: Thank you for the insightful question. The reason we did not directly compare SDM and SSDM is that we considered them suitable for different problem settings. SSDM operates in semi-supervised settings, while SDM in a supervised setting. As such, we considered it more fitting to focus on SSDM in the semi-supervised context and did not directly compare the two methods where SSDM would not be applicable, such as in fully supervised scenarios.

However, we agree that a comparison between SDM and SSDM would be valuable, particularly in semi-supervised settings, and where runtime is not a limiting factor. To address this, we have added such a comparison in Table 5 of the new Appendix E.3. This table includes results for both SDM and SSDM across all datasets for which results were previously reported only for SDM. As shown in the table, SDM slightly outperforms SSDM in most cases, aligning with our theoretical analysis. However, there are cases where SSDM can exceed SDM's performance. For instance, SSDM outperforms SDM on the Yacht dataset and the toy problem presented in the paper, as illustrated in Figure 3.

To better understand why SSDM can sometimes surpass SDM, we examined the components of the toy problem in Figures 11 and 12. In Figure 11, which shows SDM results with the optimal $t = 0.02$, and Figure 12, which shows SSDM results with the optimal $t = 0.8$, we observe that SDM embeddings, which are influenced by individual kernels for each data point, exhibit greater variability. This results in embeddings that are less consistent across samples. In contrast, the embeddings derived using SSDM are more consistent, as they are constructed from a single kernel.

Theoretically, this variability in SDM could be mitigated by using larger kernels. However, as we discussed earlier, SDM becomes impractical for large datasets due to its computational complexity.

In conclusion, while SSDM is significantly more time-efficient and its performance is comparable to SDM, SDM remains relevant for fully supervised settings and can achieve better performance in some cases. We have included a detailed analysis and conclusions regarding this comparison in Appendix E.3 of the revised paper.

2. Computational Complexity and Scale Up: We appreciate your comment regarding the computational complexity and scale up, and we have addressed these concerns in the revised version of our paper.

In response, we have added a new Appendix F where we provide a detailed analysis of the time and space complexity of both SDM and SSDM. The complexity of SDM is $O(n^4)$, which makes it impractical for large or even medium-sized datasets. Conversely, SSDM has a complexity of $O(n^3)$, making it more feasible for medium-sized datasets, up to approximately 10,000 samples.

In general, large datasets pose a known challenge in kernel methods like ours. Typically, using sparse kernels reduces both computational and storage demands. However, since our method involves kernel matrix multiplication and since the multiplication of two sparse matrices may result in a dense matrix, this approach is not suitable for scaling up our method. One possible solution is the "landmark" [1] approach, which has been adapted for alternating diffusion in recently [2]. This approach approximates the eigenvectors of large alternating diffusion kernels by sampling $k$ landmark data points, computing the eigenvectors for the small $k \times k$ kernel, and then expanding them to the entire dataset.

To address this limitation, we have implemented a simpler sampling approach to create an optimized version of SSDM that is suitable for large-scale datasets. For example, on our basic hardware (described in Appendix B), the optimized SSDM processes datasets like MNIST and Fashion-MNIST (each containing 70,000 samples) in just 8 seconds. Additionally, the Rice dataset, which contains 3,810 samples and took 55 seconds to process with SSDM (as reported in Table 6), is now processed in just 0.03 seconds using the optimized SSDM.

In the optimized version, rather than constructing the label and data kernels $\mathbf{P}$ and $\mathbf{D}$ with dimensions $n \times n$, we randomly sample $k$ labeled samples from the training set. This results in a label kernel $\mathbf{P}$ of size $k \times k$ and a data kernel $\mathbf{D}$ of size $k \times n$, where $k$ is set to $0.01 \cdot n$ if $n > 10,000$ and to $0.1 \cdot n$ if $n \leq 10,000$ in our experiments. Through empirical testing, we found that a small proportion of labeled samples can effectively represent the space in large datasets. If $n$ becomes very large, $k$ can be set to any fixed small value, smaller than $0.01 \cdot n$. Apart from adjusting the kernel dimensions, the other steps of the optimized SSDM remain identical to those in SSDM. This modification reduces the complexity of the optimized SSDM to $O(k^2 \cdot n)$, making it scalable for very large datasets (greater than 100,000 samples). Additionally, the optimized SSDM is implemented using torch, which leverages GPU acceleration.

For comparison, t-SNE has a time complexity of $O(n^2)$, with optimized versions having a complexity of $O(n \cdot \log n)$, while UMAP has a time complexity of $O(d \cdot n^{1.14})$, where $d$ is the dimensionality of the data. As such, for smaller values of $k$, our method is more time-efficient than these alternatives.

In the newly added Appendix F, we provide a comprehensive description of the optimized SSDM, along with detailed performance and runtime comparisons based on the procedure outlined in the Experimental Results section. Additionally, we wish to kindly refer you to our general post in this thread, where we present both evaluation results and runtime comparisons on large datasets, comparing between optimized SSDM, unsupervised Diffusion Maps, and semi-supervised UMAP. In which our SSDM achieves the best performance on 3 out of the 6 datasets, and is significantly faster than semi-supervised UMAP across all datasets. We will upload the code for the optimized SSDM in the supplementary materials within the next few days.

[1] Shen, Chao, and Hau-Tieng Wu. "Scalability and robustness of spectral embedding: landmark diffusion is all you need." Information and Inference: A Journal of the IMA 11.4 (2022): 1527-1595.

[2] Yeh, Sing-Yuan, et al. "Landmark Alternating Diffusion." arXiv preprint arXiv:2404.19649 (2024).

Thank you for your helpful feedback. We appreciate the time you took to review our work and provide valuable suggestions.

1. Geometric Similarity Assumption: Thank you for this insightful comment. We agree that the geometric similarity assumption is central, and your observation prompted us to elaborate further on its role in the paper.

In response to your feedback, we have added Appendix C.1, where we discuss the geometric similarity assumption and propose an alternative assumption that is more practical to quantify, as the geometric similarity can be challenging to measure for a given dataset.

Briefly, the alternative assumption can be described as follows: if two samples have similar labels (small label distance), our label-driven diffusion process should produce smaller distances and higher transition probabilities than the direct pairwise distances in the unsupervised Diffusion Maps. In cases where direct distances better represent label distances, unsupervised Diffusion Maps is likely to outperform our method.

In Appendix C.1, we test this assumption on real-world datasets and demonstrate that when it holds, our method outperforms unsupervised Diffusion Maps. At the same time, when it does not hold, Diffusion Maps may perform better. To visually evaluate whether the assumption holds, we present the kernels as heatmaps and compare our method's kernel to the unsupervised Diffusion Maps kernel. These heatmaps, sorted by label, with rows for unlabeled samples and columns for labeled samples, highlight the effectiveness of our label-driven diffusion relative to the direct pairwise distances used in Diffusion Maps. Note that an ideal heatmap for classification displays high-values in diagonal blocks corresponding to the classes. We have demonstrated in the new Appendix C.1 that our method achieves better performance when our kernel's heatmap more closely resembles the ideal block diagonal matrix than the Diffusion Maps heatmap across several datasets.

Given the response above which has addressed my major concerns, I am happy to increase my score.

Thanks for your positive review and thoughtful comments. We appreciate your time and the effort you put into reviewing our paper.

Computational Complexity and Scale Up: We appreciate your comment regarding the computational complexity and scale up, and we have addressed these concerns in the revised version of our paper.

In response, we have added a new Appendix F where we provide a detailed analysis of the time and space complexity of both SDM and SSDM. The complexity of SDM is $O(n^4)$, which makes it impractical for large or even medium-sized datasets. Conversely, SSDM has a complexity of $O(n^3)$, making it more feasible for medium-sized datasets, up to approximately 10,000 samples.

In general, large datasets pose a known challenge in kernel methods like ours. Typically, using sparse kernels reduces both computational and storage demands. However, since our method involves kernel matrix multiplication and since the multiplication of two sparse matrices may result in a dense matrix, this approach is not suitable for scaling up our method. One possible solution is the "landmark" [1] approach, which has been adapted for alternating diffusion in recently [2]. This approach approximates the eigenvectors of large alternating diffusion kernels by sampling $k$ landmark data points, computing the eigenvectors for the small $k \times k$ kernel, and then expanding them to the entire dataset.

To address this limitation, we have implemented a simpler sampling approach to create an optimized version of SSDM that is suitable for large-scale datasets. For example, on our basic hardware (described in Appendix B), the optimized SSDM processes datasets like MNIST and Fashion-MNIST (each containing 70,000 samples) in just 8 seconds. Additionally, the Rice dataset, which contains 3,810 samples and took 55 seconds to process with SSDM (as reported in Table 6), is now processed in just 0.03 seconds using the optimized SSDM.

In the optimized version, rather than constructing the label and data kernels $\mathbf{P}$ and $\mathbf{D}$ with dimensions $n \times n$, we randomly sample $k$ labeled samples from the training set. This results in a label kernel $\mathbf{P}$ of size $k \times k$ and a data kernel $\mathbf{D}$ of size $k \times n$, where $k$ is set to $0.01 \cdot n$ if $n > 10,000$ and to $0.1 \cdot n$ if $n \leq 10,000$ in our experiments. Through empirical testing, we found that a small proportion of labeled samples can effectively represent the space in large datasets. If $n$ becomes very large, $k$ can be set to any fixed small value, smaller than $0.01 \cdot n$. Apart from adjusting the kernel dimensions, the other steps of the optimized SSDM remain identical to those in SSDM. This modification reduces the complexity of the optimized SSDM to $O(k^2 \cdot n)$, making it scalable for very large datasets (greater than 100,000 samples). Additionally, the optimized SSDM is implemented using torch, which leverages GPU acceleration.

For comparison, t-SNE has a time complexity of $O(n^2)$, with optimized versions having a complexity of $O(n \cdot \log n)$, while UMAP has a time complexity of $O(d \cdot n^{1.14})$, where $d$ is the dimensionality of the data. As such, for smaller values of $k$, our method is more time-efficient than these alternatives.

In the newly added Appendix F, we provide a comprehensive description of the optimized SSDM, along with detailed performance and runtime comparisons based on the procedure outlined in the Experimental Results section. Additionally, we wish to kindly refer you to our general post in this thread, where we present both evaluation results and runtime comparisons on large datasets, comparing between optimized SSDM, unsupervised Diffusion Maps, and semi-supervised UMAP. In which our SSDM achieves the best performance on 3 out of the 6 datasets, and is significantly faster than semi-supervised UMAP across all datasets. We will upload the code for the optimized SSDM in the supplementary materials within the next few days.

[1] Shen, Chao, and Hau-Tieng Wu. "Scalability and robustness of spectral embedding: landmark diffusion is all you need." Information and Inference: A Journal of the IMA 11.4 (2022): 1527-1595.

[2] Yeh, Sing-Yuan, et al. "Landmark Alternating Diffusion." arXiv preprint arXiv:2404.19649 (2024).