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

Authors: Harel Mendelman, Ronen Talmon
Primary area: learning on graphs and other geometries & topologies
Keywords: Manifold Learning, Diffusion Maps, Supervised dimension reduction, Multi-view learning

Abstract:
In this paper, we introduce Supervised Diffusion Maps (SDM) and Semi-Supervised Diffusion Maps (SSDM), which transform the well-known unsupervised dimensionality reduction algorithm, Diffusion Maps, into supervised and semi-supervised learning tools. The proposed methods, SDM and SSDM, are based on our new approach that treats the labels as a second view of the data. This unique framework allows us to incorporate ideas from multi-view learning. Specifically, we propose constructing two affinity kernels corresponding to the data and the labels. We then propose a multiplicative interpolation scheme of the two kernels, whose purpose is twofold. First, our scheme extracts the common structure underlying the data and the labels by defining a diffusion process driven by the data and the labels. This label-driven diffusion produces an embedding that emphasizes the properties relevant to the label-related task. Second, the proposed interpolation scheme balances the influence of the two kernels. We show on multiple benchmark datasets that the embedding learned by SDM and SSDM is more effective in downstream regression and classification tasks than existing unsupervised, supervised, and semi-supervised nonlinear dimension reduction methods.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1729514599294

thread_type:
official_review

<thread_object>
creator: reviewer_oug2

<content>
summary:
This paper proposes constructing two affinity kernels corresponding to the data and the labels. The authors then propose a multiplicative interpolation scheme of the two kernels, whose purpose is twofold. First, their scheme extracts the common structure underlying the data and the labels by defining a diffusion process driven by the data and the labels. This label-driven diffusion produces an embedding that emphasizes the properties relevant to the label-related task. Second, the proposed interpolation scheme balances the influence of the two kernels. We show on multiple benchmark datasets that the embedding learned by SDM and SSDM is more effective in downstream regression and classification tasks than existing unsupervised, supervised, and semi-supervised nonlinear dimension reduction methods.

strengths:
1. Originality. This paper presents Supervised Diffusion Maps (SDM) and Semi-Supervised Diffusion Maps (SSDM), which are supervised and semi-supervised variants of Diffusion Maps. Unlike existing supervised and semi-supervised manifold learning methods,
the authors present a new approach, where they view the labels as an additional data modality and employ concepts of multimodal manifold learning. Concretely, the authors propose to construct a separate affinity kernel for the labels, allowing us to capture the underlying geometry of the labels in addition to that of the data. 
2. Quality and Clarity. There are no technical errors, and the presentation and writing are satisfied.
3. Significance. The authors show on multiple benchmark datasets that the embedding learned by SDM and SSDM is more effective in downstream regression and classification tasks than existing unsupervised, supervised, and semi-supervised nonlinear dimension reduction methods.

weaknesses:
I am absolutely not in this field and the comments from me are not relatively professional. The comments in the following are just raised from the presentation or organization.                       

1. The authors are expected to give the figure of the framework based on Supervised Diffusion Maps (SDM) and Semi-Supervised Diffusion Maps (SSDM) and highlight the major differences between the proposed method and the most related work.

2. The authors use a new subsection termed alternating diffusion in Background part. However, there are just small amount of lines in this subsection. I think the authors can further improve this aspect for this paper.

3. For the evaluation results, the authors report NMSE for regression and Misclassification Rate for classification based on S/SDM for supervised SDM and semi-supervised SSDM on the given datasets. I think the authors can add more datasets for comparison in the experiment.

4. In the conclusion part, the authors explore the futher work by exploring the utility and adaptation of fusion of data and label kenels. The authors can add a new subsection to discuss the futher work in details here.

questions:
1. Why the authors reduce the original data dimensionality to a range of 1 to 30 dimensions for each dataset and algorithm in the experiment?

2. Why the authors choose Euclidean distance in the data kernel and angular distance in the label kernel?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730475701867

thread_type:
official_review

<thread_object>
creator: reviewer_hxos

<content>
summary:
The paper proposes Supervised Diffusion Maps (SDM) and Semi-Supervised Diffusion Maps (SSDM) as extensions of the classical Diffusion Maps algorithm. By treating labels as a secondary view of the data, the authors employ a multi-view learning framework to enhance the dimensionality reduction process. The proposed methods introduce a multiplicative kernel interpolation scheme to integrate data and label information. Experimental results on benchmark datasets are used to demonstrate the effectiveness of SDM and SSDM compared to existing manifold learning techniques.

strengths:
1) The paper presents a clear motivation for addressing the limitations of traditional manifold learning methods that lack mechanisms to incorporate label information.
2) Treating labels as an additional data modality and leveraging a multi-view framework can provide some new insights to the community.
3) Both empirical and theoretical analyses are provided to justify the proposed method.

weaknesses:
1. While the multi-view framework and the label-driven diffusion are interesting, they rely heavily on existing concepts, such as Alternating Diffusion and classical kernel methods. Thus, the novelty of the proposed SDM and SSDM methods appears limited, as they mainly extend well-established techniques.
2. Given that the paper relies heavily on older references with minimal discussion of more contemporary work, are there recent advancements in manifold learning？
3. There is no discussion on how the proposed methods scale with larger datasets (e.g. MNIST [1] with 70000 samples) or in higher-dimensional spaces (Toxicity [2] with 1203 features), which is crucial for practical applications.
4. The related work section lacks a comprehensive overview in multi-view learning [3,4].
5. The computational complexity of the proposed methods is not well-handled, with larger computational complexity compared with other methods.

[1] LeCun Y, Bottou L, Bengio Y, et al. Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86(11): 2278-2324.  
[2] Gul S, Rahim F, Isin S, et al. Structure-based design and classifications of small molecules regulating the circadian rhythm period[J]. Scientific reports, 2021, 11(1): 18510.  
[3] Lyu G, Yang Z, Deng X, et al. L-VSM: Label-Driven View-Specific Fusion for Multiview Multilabel Classification[J]. IEEE Transactions on Neural Networks and Learning Systems, 2024.  
[4] Zhao J, Xie X, Xu X, et al. Multi-view learning overview: Recent progress and new challenges[J]. Information Fusion, 2017, 38: 43-54.

questions:
Please refer to the weakness list.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730691133455

thread_type:
official_review

<thread_object>
creator: reviewer_fvwq

<content>
summary:
This paper introduces two novel methods for manifold learning: Supervised Diffusion Maps (SDM) and Semi-Supervised Diffusion Maps (SSDM), which extend the traditional Diffusion Maps framework to supervised and semi-supervised settings. Unlike prior methods, SDM and SSDM treat labels as a secondary data modality, employing principles from multimodal manifold learning to better capture the structure of labeled data. The authors propose constructing a separate affinity kernel for the labels, enabling the model to represent the geometry of labels along with the data. Using an Alternating Diffusion (AD) approach, they introduce a kernel interpolation scheme that combines data and label affinity kernels. This creates a “label-driven diffusion” process, approximating a continuous two-step diffusion on the manifold that emphasizes features relevant to the task. 

The main contributions are as follows: 

1. Multi-View Approach: SDM and SSDM incorporate labels as an additional information source, enhancing the manifold learning process. 
2. New Kernel Interpolation Scheme: A method for combining affinity kernels to reveal shared structures between data and labels while controlling their respective contributions. 
3. Experimental Validation: Results show that SDM and SSDM outperform existing nonlinear manifold learning methods across several benchmark datasets, highlighting their effectiveness.

strengths:
This paper introduces Supervised Diffusion Maps (SDM) and Semi-Supervised Diffusion Maps (SSDM), extending Diffusion Maps to supervised and semi-supervised learning by treating labels as an additional data modality. This innovative approach uses a two-step diffusion process, first on the labels and then on the data, enabling a “label-driven diffusion” that highlights task-relevant structures. The paper presents a rigorous kernel interpolation scheme to merge data and label affinities, supported by strong theoretical justification and validated through experiments on benchmark datasets. The methodology is clear, original, and impactful, making this a valuable contribution to manifold learning.

weaknesses:
Diffusion processes are often computationally intensive, especially on large datasets. The paper would benefit from an analysis of the scalability of the proposed methods. Discussing time complexity, memory requirements, and potential optimizations or parallelization strategies could make this approach more practical for large-scale applications. Furthermore, a comparison of computational costs between SDM/SSDM and other manifold learning methods would provide a clearer picture of their efficiency.

questions:
see weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730707287762

thread_type:
official_review

<thread_object>
creator: reviewer_7ici

<content>
summary:
This paper extends traditional diffusion maps by integrating label information to create supervised and semi-supervised versions, known as Supervised Diffusion Maps (SDM) and Semi-Supervised Diffusion Maps (SSDM). The core algorithm involves constructing two affinity kernels—one for the data and one for the labels. These affinity matrices are then combined using an alternating diffusion (AD) approach, which extracts the shared structure between data and labels, producing embeddings that incorporate label information. Theoretical analysis and experimental results on several real datasets demonstrate that the proposed methods outperform existing unsupervised and supervised algorithms in classification accuracy and regression error.

strengths:
The strengths of the paper are as follows:

- Presentation: The paper is well-written and easy to follow, with clear introductions to the background, problem formulation, and related work. The proposed method is thoroughly described and demonstrated.

- Originality: The proposed method is both novel and conceptually sound. The problem is well-motivated by highlighting that unsupervised manifold learning does not fully utilize label information, often resulting in sub-optimal performance. Introducing the alternating diffusion approach with an additional parameter $t$ for fusing and balancing data and label information is an effective and innovative idea.

- Theory: The theoretical analysis, while based on several fundamental assumptions, is valuable and provides important insights.

weaknesses:
My concern to this paper mainly falls onto the following three aspects: 

- **Lack of Discussion on the Geometric Similarity Assumption**: A fundamental assumption in the proposed method is the strong geometric similarity between the data and labels. However, it is unclear how this similarity impacts the method's performance. For instance, if the labels are only weakly correlated with the data geometry, would the proposed method perform worse than traditional unsupervised algorithms? An empirical or theoretical study on this factor would be invaluable as a guide for real-world applications. Currently, no such study exists, and all experiments seem to assume this strong similarity.

- **Computational Complexity and Dataset Scale**: Given that the computational complexity increases with training data size, this could be a critical factor in determining the method’s applicability. A quantitative complexity analysis of the proposed method, and possibly other baseline methods, would be beneficial, in addition to the runtime reported in Table 5. Moreover, the real datasets in the paper are relatively small (<4k samples), which may not reflect the scale commonly encountered in real applications. It would be informative to evaluate both performance and runtime as dataset size grows, particularly examining the differences between SDM and SSDM under larger-scale conditions.

- **Performance Comparison between SDM and SSDM**: Given that computational complexity is crucial and that SSDM is more computationally efficient than SDM, a direct performance comparison between SDM and SSDM would be valuable. It’s important to understand if SDM consistently outperforms SSDM despite the higher complexity, or if there are cases where SSDM could exceed SDM’s performance—particularly when the geometry of the test data is beneficial in constructing the data affinity matrix.

Addressing these questions would greatly enhance the paper and make it a strong fit for this venue.

questions:
See weakness above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732102658860

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Additional experimental results including large scale datasets

comment:
In this post, we present new evaluation results on large datasets, which were not included in the original submission. These results were added to the revised version of our paper in the new Appendix F. By implementing an optimized version of SSDM, as described in Appendix F, we were able to evaluate large datasets effectively.
The new results on large datasets are presented in two tables:

1. **Table 1** shows the performance of our optimized SSDM compared to unsupervised Diffusion Maps and semi-supervised UMAP, following the procedure outlined in the Experimental Results section. We report the Misclassification Rate for each method, and our SSDM achieves the best performance on 3 out of 6 datasets.

2. **Table 2** reports runtime comparisons in seconds between our SSDM and semi-supervised UMAP. The results demonstrate that our SSDM is significantly faster across all datasets, consistent with the complexity analysis in Appendix F.  

### Table 1

| Dataset       | n      | d   | DM                         | SSUMAP                     | SSDM (ours)                |
|---------------|--------|-----|:--------------------------:|:--------------------------:|:--------------------------:|
| MNIST         | 70,000 | 784 | 0.22 ± 0.006               | **0.046 ± 0.001**          | 0.1 ± 0.003                |
| Fashion-MNIST | 70,000 | 784 | 0.33 ± 0.016               | **0.21 ± 0.006**           | 0.25 ± 0.004               |
| Isolet        | 7797   | 617 | 0.147 ± 0.003              | 0.178 ± 0.005              | **0.087 ± 0.006**          |
| Adult         | 48,842 | 14  | **0.211 ± 0.002**          | 0.212 ± 0.001              | 0.23 ± 0.003               |
| Landsat       | 6435   | 36  | 0.181 ± 0.013              | **0.127 ± 0.004**          | **0.127 ± 0.007**          |
| Nursery       | 12,960 | 8   | 0.128 ± 0.03               | 0.193 ± 0.005              | **0.082 ± 0.008**          |

### Table 2

|    Dataset    |    n    |  d  | SSUMAP | SSDM (ours)   |
|--------------|-------|---|:------:|:-------------:|
|     MNIST     | 70,000  | 784 |   35   |    **8.1**    |
| Fashion-MNIST | 70,000  | 784 |   35   |   **8.35**    |
|    Isolet     | 7,797   | 617 |    7   |    **1.2**    |
|    Adult      | 48,842  | 14  |   27   |    **1.4**    |
|   Landsat     | 6,435   | 36  |   6.3  |   **0.12**    |
|   Nursery     | 12,960  | 8   |   5.5  |    **0.4**    |
</content>
</thread_object>

</thread>
<thread>
creation date:
1733127171488

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank the reviewers for their time and effort in evaluating our work and providing valuable feedback. Their constructive comments have significantly helped us refine and improve our paper.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The reviewers originally raised concerns regarding several aspects such as methodological justification, empirical evaluation and technical novelty. Fortunately, the authors response positively to the reviews, and now all reviewers have reach consensus that the paper should be accepted. In this case, I am happy to recommend accepting the paper.