Supervised and Semi-Supervised Diffusion Maps with Label-Driven Diffusion
Authors: Harel Mendelman
Ronen Talmon
Venue: ICLR 2025 Poster (2025)
Keywords: Manifold Learning
Diffusion Maps
Supervised dimension reduction
Multi-view learning
Primary area: learning on graphs and other geometries & topologies

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.

Published as a conference paper at ICLR 2025
SUPERVISED AND SEMI-SUPERVISED DIFFUSION MAPS WITH LABEL-DRIVEN DIFFUSION
Harel Mendelman, Ronen Talmon
Viterbi Faculty of Electrical and Computer Engineering, Technion harel.men@ memeeeeeann campus. technion ac.il,
il, ronenêee wwchnien.ceecc.c romerdee.cachnionn.cc
ABSTRACT
In this paper, we introduce Supervised Diffusion Maps (SDM) and Semi- Supervised Diffusion Maps (SSDM), which transform the well-known unsuper- vised 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 second view of the data. This unique framework allows to incorporate ideas from multi-view learning. Specifically, we propose constructing two affinity kernels corresponding to the data and the labels. We then propose 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 diffusion process driven by the data and the labels. This label-driven diffusion produces an embedding that emphasizes the properties relevant the label-related task. Second, the proposed interpolation scheme balances the influence of the two kernels. We show on mul- tiple benchmark datasets that the embedding learned by SDM and SSDM is more effective in downstream regression and classification tasks than existing unsuper- vised, supervised, and supi-super nonlinear dimension reduction methods.
INTRODUCTION
Manifold learning has emerged powerful approach for uncovering the underlying structure of complex high-dimensional datasets. Aiming to mitigate the "curse of dimensionality", the core idea behind manifold learning is the manifold assumption, i.e., assuming that high nigh-diimesiooal data lies on or near a lower-dimensional manifold, which captures the essential features of the data. This lower-dimensional representation can reveal patterns, relationships, and intrinsic geometries obscured in the original ambient high-dimensional space.
Manifold learning techniques are designed discover these low-dimensional manifolds by lever- aging the geometric properties of the data. Unlike linear dimensionality reduction methods, such as Principal Component Analysis (PCA) (Pearson 1901), manifold learning algorithms non-linear and can model more complex structures. These methods are particularly effective when data is gen- erated by non-linear processes, making them well-suited for applications in many applied science fields, such as bioinformatics, biomedical, and neuroscience (aiao-Papo et al. 2021 Sulam et al. 2017 Dimitriadis et al. 2018).
Even with recent advances in deep learning, manifold learning methods remain relevant for their interpretability, effectiveness with small datasets, lower risk overfitting, and lower computational requirements. Additionally, their concepts have influenced geometric deep learning, with ongoing research promising further advancements in that area.
Numerous manifold lcarning algorithms have been developed in the last two decades. Some of the most prominent techniques include Isomap (Tenenbaum et al. 2000), Locally Linear Embedding
(LLE) (Roweis & Saul 2000). Laplacian Eigenmaps (LE) (Belkin & Niyogi 2003). Diffusion Maps
(DM) (Coifman & Lafon 2006), t-Distributed Stochastic Neighbor Embedding (t-SNE) (Van der
Maaten & Hinton| 2008). and UMAP MMeInnes et al. 2018)..
Despite their advantages, standard manifold learning methods have limitations such as parameter selection, noise sensitivity, and computational complexity in large-scale datasets, which have already

---

Published as a conference paper at ICLR 2025
been partially resolved in recent advances, e.g., Karoui & Wu (2016); Shen & Wu (2022). In this work, we focus on another limitation the incorporation of label information. At their core, manifold learning methods are unsupervised, and therefore, they often do not provide effective solution that exploits all the information in a large body problems where some label information exists.
In this paper, present Supervised Diffusion Maps (SDM) and Semi-Supervised Diffusion Maps (SSDM), which are supervised and semi cuni-super variants of Diffusion Maps (Coifman & Lafon 2006). Unlike existing supervised and semi-supervised manifold learning methods (See Section 2). we present a new approach, where we view the labels as an additional data modality and employ concepts of multimodal manifold learning. Concretell, we 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. Then, based on Alternating Diffusion (AD) (Lederman Talmon 2018), a multimodal manifold learning method that relies on product of affinity kernels, we propose a multiplicative kernel interpolation scheme of the data and label kernels. This results in kernel representing a tran- sition probability matrix of Markov chain on the data and labels. In analogy to AD (Talmon & Wu 2019), this kernel approximates a continuous diffusion process on the manifold consisting of a two- step diffusion process: first the labels and then the data, henceforth referred to "label-driven diffusion". This approach reveals the common structure underlying the data and labels, resulting in data embedding that emphasizes only the properties relevant to the specified task related to the labels. We present theoretical justification and experimental results that show the advantages of the proposed SDM and SSDM compared existing manifold learning methods on several benchmarks.
Our main contributions are as follows:
Multi-View Approach to Supervised and Semi-Supervised Manifold Learning: View- ing labels second source of information.
New Kernel Interpolation Scheme: Interpolating affinity kernels to reveal their common- alities, while providing mechanism for weighting the contribution of each.
Experimental Results: Showing that SDM and SSDM outperform existing non-linear manifold learning algorithms on real-world benchmark datasets.
2 RELATED WORK
Numerous supervised and semi-supervised adaptations of manifold learning algorithms have been explored. These methods generally adopt one of the following approaches.
Several supervised and semi-supervised variants of manifold learning algorithms, such as LLE (Zhang 2009). Diffusion Maps (Szlam et al., (2008), and t-SNE (Hajderanj et al.] (209)), modify the similarity distance metric. Typically, the dissimilarity metric is redefined as follows:
V exp -d((s
if if Vj
D(I,,
exp (d(ELR))) a,
if ya +
where F; and 2j are the data samples, Yi and y are their corresponding labels, d(.,.) is a distance metric, and and are tunable parameters.
Another approach optimizes inter-class and intra-class objectives, as employed for example by a variant of Isomap (Yang al. 2016)), where the goal is preserve intra-class distances while in- creasing inter-class distances:
Σ (d(Is, d(z1, -B Σ ( サー
min a Z
where Z represents a intra-class and inter-class objectives.
embedding, and a and 3 control the trade-off between the
In addition, some methods like variants of LE (Ma et al. 2019) and UMAP Mclnnes et al. 2018), divides the objective into components, that focuses the data and another that incorporates
2

---

Published as a conference paper at ICLR 2025
label information. An example of such objective function is:
min (d( d(2), 2,)) + B Σ E21
where &. serves as the representative point for class c.
These three approaches often overlook the potential similarity between the geometric structures underlying the data and the labels, as they integrate label information into the data manifold, which may result in a skewed representation. Recognizing that labels and data might reside similar structures, our method introduces a new approach by learning a representation that captures the commonalities between the geometries of the data and labels.
3 BACKGROUND
3.1 DIFFUSION MAPS
Diffusion Maps, introduced by Coifman & Lafon (2006), present spectral analysis-based low- dimensional data embedding with diffusion geometry and diffusion distance.
Consider a measure space (M,du), where M is smooth Riemannian manifold and du(x)) p(z)dz is a measure with density p(æ) E (MM) Assume M is isometrically embedded in 12d, and let {z, M) _ be set of n points sampled from p(z).
Diffusion Maps begin with constructing an affinity matrix W, typically using a Gaussian kemel:
W(i,j)= exp d(Ex,) (
(4)
e
where -(---) is distance metric, and e is the kernel scale. This matrix captures local pairwise similarities between the sampled points. Then, normalization of W is applied using two diagonal matrices, D, and D2, derived from the sums of rows of W and K D, WD, respectively. The resulting normalized matrix K = D K is row-stochastic matrix, viewed as the transition probability matrix of a Markov chain on the data (Coifmann & Lafon 2006).
From the eigenvectors ty and eigenvalues μ* K. Diffusion Maps defined by (x,),)) 1 (i). where r > 0 denotes the diffusion time parameter, and = 1.2...., n. It was shown in Coifman & Lafon (2006) that the matrix represents a diffusion process on the continuous underlying manifold when a large number of points is available. The diffusion propagation of sample is modeled by iteratively applying the matrix K. Specifically, if 6, denotes a onc-hot vector with a single non-zero entry at the i-th coordinate representing initial mass concentrated at sample i, the sequence of dif- fused mass vectors given by 5! K". The diffusion distance between samples i and j is defined by (i, | K - ó, KT This distance metric not only captures the direct similarities between samples but also accounts for their connectivity throughout the Markov chain. As result, it provides a robust measure that less sensitive to local variations, outliers, and noise within the dataset. In addition, it can be approximated by the Euclidean distance between the respective Diffusion Maps, i..., [x;;) - (12
3.2 ALTERNATING DIFFUSION
Alternating Diffusion (AD) (Lederman & Talmon 2018 an extension of Diffusion Maps designed
to extract the common structure of two aligned datasets {-; pm= (1) and (r(2))=11 AD starts by building affinity matrices, (1) and ((2), for each dataset as in Eq. 4 These affinity matrices are normalized to form the diffusion operators (1) and (2) following the procedure used in Diffusion Maps (See Subsection(3.I). The AD operator defined by the product of the two diffusion operators (1))((2) consists of alternating diffusion steps via (1)) and (2) on the two datasets. Lederman & Talmon (2018) showed that the resulting diffusion process captures the common structure between the two datasets, minimizing the influence of dataset-speciffc factors.
(1) Like Diffusion Maps, this operator defines a propagation that
3

---

Published as a conference paper at ICLR 2025
4 PROPOSED METHOD
Consider a labeled training dataset ((r;; y:)) consisting of n data samples x; RRd and their corresponding labels yıu and a test dataset {- consisting of unlabeled test data samples T. E Rd. Our goal obtain an informative low dimensional representation of both the training and test datasets, given by the embedding (x;))) and { (v( |== of the samples into a Euclidean
space R l < d. Same as in many dimension reduction methods, e.g., BBllknn & Niyogi (2003); Coifman & Lafon 2006), we aim to find an embedding, whose Euclidean distances are meaningful. Specifically. following Diffusion Maps (Coifman & Lafon 2006). we build an embedding, whose Euclidean distances approximate the diffusion distances (see Subsection 3.1). Importantly, such a construction assumes unlabeled data. The main novelty in this paper that we propose to account for the given labels of the training data, such that samples with similar labels are mapped to close points in the embedding space, and samples with dissimilar labels are mapped to distant points, thereby improving the embedding, especially for downstream tasks such as classification and regression.
Seemingly, the desired embedding described above could be obtained directly using an appropriate manipulation of the classical Multidimensional Scaling (MDS) (Carroll & Arabie 1998) or other su- pervised and -uperviee dimensionality reduction techniques that minimize distances between similar labels and maximize distances between dissimilar labels (See Section 2). However, this
quires unnatural data and lahel weighting and usually has poor scalability (Ma et al. 2019). We propose different approach that mitigates these shortcomings. Our approach relies on the premise that both the data and the labels have similar underlying geometric structures, and consequently, uncovers their commonality through a diffusion process that integrates both data and labels.
For simplicity, we first describe SDM (supervised setting) in the context of a single unlabeled test sample J. We then extend this description to multiple unlabeled test samples { and fi- nally describe SSDM (semi-supervised settting). The first step is to build an affinity matrix WD in (R+++) (n+11 on the set (.; |i=1 U I, consisting of the training data and one test sample. The elements of this affinity matrix are given by
dh (Z) W WD(i.)) exp
(5)
en
where dp(::-) is distance metric in Rd, e.g., the Euclidean distance, and cD is a hyperparameter. Then, the affinity matrix is normalized twice, as described in Subsection 3.1. resulting in a data kernel, denoted by D E g(++))x(++).
Similarly, we propose to build an affinity matrix between the labels. Since the label of the test sample F is missing, we define the following affinity matrix, whose elements are given by:
de (vc.2))
exp
if In n i > n or j > n, and * j
WP(1.)) =
0,
(6)
1,
if > n and i =
where .)(:s)) is a distance metric between the labels and cp is a hyperparameter. the labels continuous (regression problem), we compute the distance between the labels using a standard distance metric, e.g., the Euclidean distance. If the labels are discrete (classification problem), we propose the following metric (other metrics may also be considered):
Epbecr ECC.CC, dD( Hgg,
if y E C.u, E I + m
dr(ye. UJ)
mpm 0,
if y yj
where C = {y y E Class O) for = I,.... C, C' is the number of classes, and ny is the size of C,. As described in Subsection 3.1 the affinity matrix Wr is normalized twice, giving rise to the label kernel P E IR 1)+(())(++)) representing the prior label information we have on the training dataset. Specifically, the construction in Eq. Badds an isolated node representing T to the transition graph P.
Once the kernels D and P are obtained, the goal is to find embeddings for 9:) and z. To exploit that both the data and labels share similar underlying geometric structures, we build on AD (Lederman & Talmon 2018) and utilize the product of kernels to uncover commonalities. Specifically, we propose the following interpolation scheme:
[(1)= ''- 0 05151.
(8)
4

---

Published as a conference paper at ICLR 2025
In this scheme, (t)) denotes the interpolated kerne,, where balances between P and D. The con- tribution of our method extends beyond the introduction of a label kernel. It enhances AD in two notable ways. First, it accommodates kernels with partial alignment as z lacks corresponding label (Eq. 66. Second, provides a mechanism for weighting the contribution of the data and the labels through the hyperparameter In Section [] we show that (t) facilitates approximation of the embedding that would have been obtained in fully aligned setting without missing labels.
We use r()) as a kernel in a manner similar Diffusion Maps (See Subsection 3.1 to obtain the embedding of { and I for t. Specifically, the embedding is given by
V (x,))) (t)
Vx(T)= P (n 1),
where k = 2, .............................. n++1 indexes the components, Ps denotes the k-thh eigenvalue and (1) denotes the i-th entry of the k-th right eigenvector of [t).. We summarize the key steps of SDM with single unlabeled test sample in Algorithm
Since the embedding of x is generated without alignment with a label, we observed a slight improvement in downstream tasks by introducing similar distortion to the embedding of the training set, ensuring better consistency with the embedding of æt For details, see Appendix B
Algorithm 1 Generate the embed- ding of {a,)%= U.z
Construct WD (Eq.
When multiple test samples (- are given, we apply the
2: Construct Wp Pp (Eq.
deseribed procedure sequentially for each sample. This results in the embedding of both the training and test samples, given
3: Obtain D, by normalizing
WD. D. Wp. p as in Sec. 3.1
by:
4: Compute I(t) for E [0.1]
(10)
(Eq. (
A summary of SDM with multiple unlabeled test samples is provided in Algorithm 2 in Appendix A.1
5: Obtain
VM
(Eq.
Considering one test sample at a time neglects possible infor- mative mutual relationships between the test samples and is computationally intensive. Instead, we propose to enhance the embedding of multiple test samples by considering a semi-supervised setting consisting of the labeled training data and all the unlabeled test data simultaneously. This will also expedite SDM, alleviating the need to construct and interpolate two affinity kernels for each training and test sample.
Concretely, instead of adding a single unlabeled sample to the training data, we append the entire test set, resulting in the union {xx] U { 1- Then, we build the data kernel D and label kernel P that correspond to this union set based on the affinities Eq. and Eq. [6] respectively, and the dual normalization, where the kernel matrices are now in IR g(*+m)x(n+n)) This construction adds m isolated nodes to the transition graph P. unlike the single isolated node added in SDM. We obtain the embedding of all training and test samples using a single kernel I(t). Specifically, the embedding is given by (x,)),)
(t) for i 1, ..... n and (I,) p4 j) for j 1, 2, ,....,th m. We term this algorithm SSDM, which results, as in SDM, in embedding as in Eq. TO Since SSDM uses single pair of affinity kernels for the entire dataset, its runtime is significantly shorter compared to SDM, as demonstrated in Section 6.2 A summary of SSDM is provided in Algorithm in Appendix A.l
THEORETICAL JUSTIFICATION
In this section, simplify the analysis, we consider the equally weighted interpolation, denoted by PD. instead of the tunable form P'-'D' (refer to Appendix [.4 for details on the tunable form). Additionally, for the purpose of the analysis, we define the inaccessible kernel representing affinities between the training labels and the unknown test label in the set /n Ug by L. Analogous to P, first compute the affinity kernel W L as follows:
(- (.. 93)
W Wi(ji) exp
Cp
for i.j = 1, .,.... n + 1, and then, apply the same normalization to obtain the inaccessible kernel L IR (n++1) In practice P as a proxy for the inaccessible L.
5

---

Published as a conference paper at ICLR 2025
Let N,D) denote the ôn-neighhoorhood of zis given by N1 {ı; (zi, x.y) < åD}. Similarly, let (x(1) denote the oz-neighborrhod of 1/s defined as N2(L) = {u, (y:. W₁) < 67). We assume
that the values of WD D and WL outside the dD te-neighborhood and oд neighborroood, respectively, are negligible.
The absolute value of the difference between any element (i,j) of the inaccessible kernel product LD and the corresponding element (i.j) of the available PD is bounded as follows:
Proposition 1.
(L) 1 n, Mi E #y E ENTR
W
[D], - PDBl
S
== +ent1. Ij E N n+1
max
r W
0
otherwise
where ry min
w and (NDD) denotes the size of the set, representing the number
|
of samples within the neighborhood of the i-th sample.
Corollary 1. If the neighborhoods N!D) and N( of each sample have at least N₃ neighbors, the bounds in Proposition 1 simplify to:
isisn, E NAt1, E EN
N
[LD,, k. [PD
i= Ij E N
N1
0
otherwise
See Appendix for the proof of Proposition I
Based on the elementwise similarity of PD and LD, we show that the eigenvectors of PD approx- imate the cigenvectors of LD, utilizing the concept of pseudo-spectrum.
Definition 1 (e-pseudo-spectrung (Trefethen) 2020)). Given a matrix M Ruxa, the e-pseudo-
spectrum for small > 0 is defined by:
oe (M) {μ E R E with ||u||2 = s.t. |I plllll ct
where (M) denotes the set of eigenvalues of M, I represents the identity matrix, and || ll2 denotes the l2 norm.
Proposition 2. Let be eigenvector of LD with corresponding eigenvalue p. If the neigh- borhwods NR and A((L) of each sample have at least N₁ neighbors and at most N2 neigh- bors, then, is e-pseudo-eigenveecor of PD with corresponding e-pseudo-eigenvalue p. iPP ju)ool S where E V
Corollary 2. If N₁ = N₂ = N, then the value of e in Proposition simplifies to = V
See Appendix C33 for the proof of Proposition
2
Combining Propositions D and 2 embedding that would have been obtained by LD is approximated by the proposed embedding based on PD.
indicates that when using P as a proxy for L, the inaccessible
We note that the analysis presented in this subsection can be straightforwardly extended to ac- commodate multiple test samples, as in the case of SSDM. In this extended setting, is given by
1+1 N where represents the maximum number of test samples j = n + 1, ....., m within
the neighborhoods A!(P) and A!(E) of each training sample = 1,...,72 n2.
Next, exploit the fact that D, L, and P could be viewed transition probability matrices of a Markov chain on the dataset (See Subsection B.I). This viewpoint was extensively studied and exploited in the context of Diffusion Maps (Coifman & Lafon 2006), where the Markov chain gives rise to a diffusion process on the data. Therefore, LD and PD are also transition probability matrices of Markov chains, where each step involves two transitions: the first the labels and the

---

Published as a conference paper at ICLR 2025
second is the data, defining "label-driven diffusion". . In this analysis, we focus on the (i, 1 elements of the matrices, representing the transition probabilities from any labeled sample i & n+1 to the (n + 1)-th unlabeled sample. While the (n + 1)-th node is isolated in P (i.e., [P],n 0), the (i, n + 1--th elements of LD and PD are given by
R+1
n+1
' Lg,DD,nn 3=1 because Pij = L for i, f n+ and Pin+1 = 0 for + 11
LD LD k,+11
PDD
Σ PryD j = > J,nt1 5-1
(11)
jm1
Thus, the (n + 1)-th node becomes reachable in PD, while the entries [LD),nt and [PD in+1 differ only by the last term the sum, Lin++1 1 The term -i ++1,++1 a
o 0 only if the (n++1)-th 1)-th sample in NT According Corollary the absolute value of this term bounded by
1/Nf. Therefore, if the (n 1o++) 1-th sample is not in M the transition probability from the i-th node to the (n + 1) node in two diffusion steps through PD is equal to that through LD. Otherwise,
the transition probabilities are approximately equal when Ni is large. Appendix [C.5 provides an example comparing label-driven diffusion to ordinary two-step diffusion solely on the data.
EXPERIMENTAL RESULTS
We present experimental results that showcase the performance of SDM and SSDM on synthetic dataset and 12 real datasets. These experiments demonstrate the effectiveness of SDM and SSDM in learning low-dimensional embeddings and their impact downstream tasks, such as regression and classification, compared to several classical and recent baselines. We provide a Python imple- mentation of SDM and SSDM
6.1 Toy PROBLEM
We generated a dataset similar to the toy problem presented in Lederman & Talmon 2018). Our dataset consists of 500 images with three figures: Superman, Spider-Man, and Flash. In each im- age, the three figures are rotated by different degrees. The images are of size 100 x 100 pix- els (i.e., 10.000-dimensional data). Each image is labeled with Superman's rotation angle, where the angles of the other two figures are viewed as nuisance factors. The dataset is divided into 50% training set and a 50% testing set, where the labels of the testing set are disregarded. Figure [ shows an example of an image with label of 54" (the angle of Superman). Our toy task is to reveal the rotation angle of Superman in unlabeled images of the three figures.
This dataset is designed to embody an explicit underlying manifold struc- ture. The rotation angle of each figure could be viewed as point one- dimensional sphere S1, such that each image, containing three independent angles, lies on the product manifold S x S S The eigenvalues and eigenfunctions of the Laplace Beltrami operator of S are (Gallier 2009):
Figure 1: Superman
Laplace-Beltrami
at a 54-degree rota- tion.
M = u
(1) cos(kz;), o
(2) sin(k2,))
(12)
providing closed form analytical expressions for the spectral components that are computed in our method in data-driven manner.
We applied SDM and SSDM to this toy problem. We used the Euclidean distance in the data kernel D and angular distance in the label kernel P to accommodate the cyclic nature of the angles.
Figure shows the evolution of the principal spectral component denoted by v/(1) from the label ker- nel P [ 0) to the data kernel D = [(l = 1) obtained by SDM. In Appendix D.I we present additional components (Figure IT] and SSDM components (Figure 12p. The x-axis represents the
angle (label), and the y-axis represents the value of the respective entry of v/("), where blue and red points indicate training and test samples, respectively. Note that each point Figure 2 (SDM) was generated using a different kernel, while the points in Figure 12 in Appendix D. (SSDM) were generated using single kernel, as described in Section
At t
0, we see that the entries of (0)
'The code is available at httphh://ggitub..ccomm
147/adm

---

Published as a conference paper at ICLR 2025
P (Label Kernel) t=0.0
(Data Kerne)) t=1.0
t=0.02
t=0.3
t=0.8
Ampitude
Ampllaude
Ampiltude
Ampittuds
Ampittude
0
-2
0
200
200
200
200
0
200
Angle
Angle
Angle
Angle
Angle
Figure 2: Progression of V from = 0 (label kernel) to (data kernel). The x-axis represents
the angle (i.c., the label) and the y-axis the value of the corresponding w/()) entry, where blue and red points for training (labeled) and test (unlabeled) samples, respectively.
are meaningless, since r(t = 0) contains no information about the unlabeled samples. At = 1, we see that the entries of v are highly noisy, [( 1) does not incorporate any label information, and the results coincide with that of the unsupervised Diffusion Maps. For 0 < t 1, we see that the entries of ( are cleaner and more similar to the spherical harmonic functions in Eq. 12 especially as decreases and [()) approaches the label kernel. To complement the presentation, in Figure in Appendix D.I we we present the two-dimensional embedding of the toy dataset obtained using SSDM with various values. We display results for both the toy problem dataset and a baseline dataset containing only images of Superman (without the nuisance figures). This visualization demonstrates that SSDM generates informative embeddings of S that are consistent with the embedding obtained by Diffusion Maps applied to the "clean" data (without the nuisance figures).
We evaluated SDM and SSDM by training a KNN regressor on the top four spectral components for each in 0.01,, ...1,...,, 1.0
using the training set and assessing performance on the test set using angular Mean Absolute Error (MAE).
Diffusion Maps
Figure 3 displays the MAE of SDM and SSDM in predicting
SSOM
Superman's 's rotation angle function of compared the baseline performance of unsupervised Diffusion Maps (DM). The results demonstrate the superiority of SDM and SSDM over DM due to the incorporation of labels. Specifically, SDM achieves the best results for small values of I, while SSDM performs better for larger values of /. in wide range, high- lighting its robustness to the tuning of the hyperparameter in addition to its superior computational efficiency.
0.0
0.2
0.4
0.6
0.8
1.0
Figure Evaluation of SDM and SSDM on the toy problem.
To demonstrate the importance of the proposed interpolation
scheme, compared it simpler interpolation method analogous to the employed by AD (Lederman & Talmon 2018). Table [ in Appendix D.2 illustrates the effectiveness of SDM and SSDM compared to this simpler approach.
To observe the effect of increasing the ratio of labeled samples in the semi-supervised setting, we analyzed SSDM performance of with varying labeled data ratios. Consistent training (100 samples, 20% of the dataset) and testing sets (100 samples) were used across experiments to ensure that the results reflect only embedding quality. The minimal MAE for the optimal is 17.42 for 20% labeled data ratio, 5.84 for 40%, 4.76" for 60%, and 4.46" for 80%. These results demonstrate the improved effectiveness of SSDM with increased labeled data. Notably, performance only slightly worsens when decreasing from 80% labels to 40%, and significantly deteriorates only when the ratio is reduced to 20%. Figure in Appendix D.I shows the MAF function of for each ratio.
6.2
REAL DATASETS
6.2.1 1 SUPERVISED SETTING
We evaluated datasets from the UCI Machine Learning Repository and Seikit-learn library (see Appendix E. for details). Each dataset underwent 50 data splits (70% training 30% testing) for
8

---

Published as a conference paper at ICLR 2025
Table 1: Evaluation results, reporting NMSE for regression ('R') and Misclassification Rate for
classification ('C'). Our algorithms are S/SDM for supervised SDM and semi-supervised SSDM.
Dataset
Unsupervised Algorithms
Semi/Supervised Algorithms
Name
Type
UMAP
Isomap
tSNE
LE
LLE
DM
S/SUMAP SSESNE S/SDM
Supervised Setting
Iris
C
0.037
0.047
0.044 0.034 0.06 0.051
0.035
0.041
0.034
Tonosphere
C
0.15
0.112
0.117
0.12 0.121
0.108
0.155
0.111
0.073
Arrhythmia
0.51
0.484
0.476
0.443 0.533
0.506
0.485
0.456
0.431
Musk
C
0.191
0.189
0.145
0.122 0.204
0.18
0.171
0.163
0.101
Yacht
R
0.549
0.395
0.451
0.208
0.498
0.43
0.549
0.12
Boston
0.084
0.087
0.074
0.083 0.08
0.096
0.083
0.068
Liver
R
0.508
0.50
0.511
0.481 0.502 0.497
0.519
0.474
Semi- Semi--Sueee Setting
Mice
C
0.029
0.03
0.01
0.045 0.002 0.162
0.029
0.047
0.016
Rice
C
0.146
0.127
0.148
0.152 0.156 0.161
0.153
0.104
Silhouettes
0.39
0.35
0.378
0.419 0.297 0.437
0.389
0.315
0.248
Raisin
0.211
0.195
0.216
0.216
0.204
0.26
0.22
0.18
0.176
Concrete
R
0.077
0.066
0.064
0.08
0.051 0.085
0.07
0.036
models--neighhors for regression and learning dimension reduction embedding and training KNN models-5 neighbors 1 neighbor for classification.
For each dataset and algorithm, we reduced the original data dimensionality to a range of 1 to 30 dimensions. We then trained KNN models and calculated the errors Normalized Mean Square Er- ror (NMSE) for regression and Misclassification Rate for classification. These errors were averaged across the 50 data splits for each dataset. We report the minimum average error achieved (within the range of 1 to 30 dimensions) and the corresponding standard deviation.
We compared the proposed SDM against several unsupervised algorithms: Diffusion Maps (Jiang & Shen 2020), UMAP (McInnes et al. 2018), Isomap (Tenenbaum et al. (2000). t-SNE (Van der Maaten Hinton 2008), Laplacian Eigenmaps (LE) (Belkin Niyogi, 2003). and Locally Lin- ear Embedding (LLE) (Roweis & Saul 2000). We also compared SDM against supervised UMAP (SUMAP) (Mclnnes et 2018) and semi-supervised t-SNE (SStSNE) (Melnnes et al. 2016). We compared SDM against semi-supervised t-SNE rather than supervised t-SNE because, to the best of our knowledge, a public implementation of supervised variant t-SNE is not available.
To ensure robustness, we selected & for SDM once the first data split and applied it consistently across all 50 splits. similar approach was used for selecting the hyperparameters of the other methods, namely, the number of neighbors in UMAP, SUMAP, Isomap, LE, and LLE, and the per- plexity t-SNE and SStSNE. For SStSNE, we do not show regression results as the method does not support continuous labels. See Appendix for additional implementation details.
Table (top part) presents the results. For the complete table, including standard deviations and with the number of dimensions that yielded the smallest error indicated in parentheses, see Table in Ap- pendix E.2 The best-performing result for each dataset among all algorithms is in bold. We see that our SDM consistently outperforms unsupervised Diffusion Maps across all datasets. Additionally, our SDM achieves the best results for all datasets.
6.2.2 SEMI-SUPERVISED SETTING
We considered five datasets from the UCI Machine Learning Repository and the Scikit-learn library. Since SSDM computes a single kernel for the entire dataset, is faster and facilitates application to larger datasets (with more than 500 samples) than those used in the supervised setting. Each dataset underwent the same processing and evaluation procedure as in the supervised setting, including generating 50 data splits and training KNN models.
We compared our SSDM against the same unsupervised algorithms as in the supervised setting. To adhere to the semi-supervised setting, learned the embedding on the entire dataset rather than

---

Published as a conference paper at ICLR 2025
30
50
20
50
50
70
20
-10
-05
-65
20
10
10
-15
V
(a) SSDM (Ours)
(b) Isomap
(c) SSUMAP
(d) I-SNE
Figure 4: Two-dimensional embedding of the Yacht dataset: dots (-) for labeled samples and pluses (+) for unlabeled samples.
the train set. Additionally, we compared our SSDM against the semi-supervised variants of UMAP (SSUMAP) (Mcinnes al. 2018) and I-SNE (SSISNE) (Melnnes et al. 2016). As in the supervised setting, we used the same approach for selecting the hyperparameters: for our SSDM and the number neighbors and perplexity for the other algorithms. SStSNE excludes the Rice dataset due to convergence issues and the Concrete dataset because it does not support regression.
Table (bottom part) presents the results. For the complete table, see Table in Appendix E.2 We see in the table that our SSDM consistently outperforms the unsupervised Diffusion Maps across all datasets. Moreover, our SSDM achieves the best result for all datasets except for Mice.
In Figure 4 we present the two-dimensional embedding of the Yacht dataset obtained by SSDM, Isomap, SSUMAP, and t-SNE. the embedding generated by SSDM, we see that the labels (rep- resented by the color) correspond to the 2D location in the embedded space, in contrast to the other embeddings, thereby demonstrating the effectiveness of our method in visually representing the data and capturing the label information.
6.3 COMPLEXITY AND RUNTIME ANALYSIS
The time complexity of SDM is O(n)), with a space complexity of On?²). where is the dataset size. This makes SDM impractical for large datasets, In contrast, SSDM has a time complexity of (nn") while maintaining a space complexity of On²²), making it more suitable for larger datasets. Table in Appendix E.5 compares the runtimes of the evaluated algorithms. While SDM is slower than other methods, SSDM achieves runtimes comparable to the alternatives.
In Appendix we propose an optimized SSDM variant with a time complexity of O(k2 n)) and space complexity of Olk - nt, where & is the number of randomly sampled labeled points. We eval- uate its performance on six large datasets, as shown in Table (Appendix Runtime comparisons in Table 8 (Appendix[F FP show that the optimized SSDM is significantly faster than SSUMAP across all datasets. detailed complexity analysis is provided in Appendix
7 CONCLUSION
In this paper, we introduce Supervised Diffusion Maps (SDM) and Semi-Supervised Diffusion Maps (SSDM), which extend the classical Diffusion Maps algorithm by incorporating label information. Treating labels as an additional view and using a multiplicative interpolation of affinity kernels, our methods effectively fuse and balance between the structures underlying data and labels. Results benchmark datasets demonstrate that SDM and SSDM give rise to low-dimensional representations that lead to superior performance in downstream regression and classification tasks compared to existing methods, showcasing their effectiveness in leveraging label information for enhanced data representation. We remark that the main limitation of SDM is computational load, as two kernels must be constructed and interpolated for each sample. This limitation was mitigated in SSDM at the expense of higher approximation error between the available partially aligned kernel and the inaccessible fully aligned kernel due to the smaller ratio between labeled and unlabeled samples, leading to less informative embedding. In future work, we plan to explore the utility and adaptation of the fusion of data and label kernels, developed in this paper, in the context of the emerging geometric deep learning.
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
This paper introduces new machine learning techniques. All datasets used in this study are publicly available and commonly employed in benchmarking machine learning algorithms. The methods developed respect the privacy and integrity of the data, and no personal or sensitive information was used.
REPRODUCIBILITY STATEMENT
The details of the experimental settings are provided in Section 6 theoretical analysis in Appendix C Additional implementation details can be found in Appendix B Our source code is available at httppp:// /ttphtgtttttttt/g comm/harellie maarel147/sah
We include detailed proofs of the
ACKNOWLEDGMENTS
The work of HM and RT was supported by the European Union's Horizon 2020 research and inno- vation programme under grant agreement No. 10733-ERCC-DIFFO.
REFERENCES
Liver Disorders. UCI Machine Learning Repository, 1990. DOI: http::/2bb.ogg11.344322/4311
Rice (Cammeo and Osmancik). http:://bbl.o/102443325MM..
UCI Machine Learning Repository, 2019. DOI:
Francis R Bach, Gert RG Lanckriet, and Michael Jordan. Multiple kernel learning, conic duality, and the smo algorithm. In Proceedings of the twenty-first international conference Machine learning, pp. 6, 2004.
Barry Becker and Ronny Kohavi.
Adult. UCI Machine Learning Repository, 1996. DOI:
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1333-1366 2003.
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI conference on artificial intelligence, vol- ume 35, pp. 3950-3957, 2021.
Margarida Cardoso. Wholesale customers. http:///doo.og/o..244//////////
UCI Machine Learning Repository, 2013. DOI:
J Douglas Carroll and Phipps Arabie. Multidimensional scaling. Measurement, judgment and deci- sion making, pp. 179-250, 1998.
David Chapman and Ajay Jain. Musk (Version 1). UCI Machine Learning Repository, 1994, DOI: http://ooo.oog/112244////////
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.09988 2020.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
Ron Cole and Mark Fanty. ISOLET. http:///oo..o//1124444///c11
UCI Machine Learning Repository, 1991. DOI:
Alex Diaz-Papkovich, Luke Anderson Anderson-Troemé and Simon Gravel. review of umap in population genetics. Journal of Human Genetics, 66(1) (661)98599 2021.

---

Published as a conference paper at ICLR 2025
George Dimitriadis, Joana P Neto, and Adam R Kampff. t-sne visualization of large-scale neural recordings. Neural computation, 30(7):1550-1774, 2018.
Guowang Du, Lihua Zhou, Yudi Yang, Kevin Lü, and Lizhen Wang. Deep multiple auto-encoder- based multi-view clustering. Data Science and Engineering, 6(3):233 2021.
R. A. Fisher. Iris. UCI Machine Learning Repository, 1988. DOI: http://doi.org1100244422///3/
Jean Gallier. Notes on spherical harmonics and linear representations of lie groups. preprint, 2009.
Onnink R. Gerritsma, J. and A. Versluis. Yacht Hydrodynamies. UCI Machine Learning Repository,
2013. DOL: https//dbb.org/0024444///XX7777
Acar Burak Muderrisoglu Haldun Guvenir, H. and R. Quinlan. Arrhythmia. UCI Machine Learning Repository, 1998. DOI: https:/ddii.org wttp:/ooo/....42//355531
Laureta Hajderanj, Isakh Weheliye, and Daqing Chen. A new supervised t-sne with dissimilarity measure for effective data visualization and classification. In Proceedings of the 8th International Conference on Software and Information Engineering, pp. 232-236, 2019.
David Harrison Jr and Daniel L Rubinfeld. Hedonic housing prices and the demand for clean air. Journal of environmental economics and management, 5(1):81-102, 1978.
Gardiner Katheleen Higuera, Clara and Krzysztof Cios. Mice Protein Expression. UCI Machine Learning Repository, 2015. DOI: hutps///oi..rr//100 http://0....o1111.2223/555522
H Hotelling. Relations between two sets of variates. Biometrika, 1936.
Bowen Jiang and Maohao Shen. Dimensionality reduction via diffusion map improved with super- vised linear projection. In 2020 IEEE International Conference on Image Processing (ICIP), pp. 1796-1800. IEEE, 2020.
Meina Kan, Shiguang Shan, Haihong Zhang, Shihong Lao, and Xilin Chen. Multi-view discriminant analysis. IEEE transactions on pattern analysis and machine intelligence, 38(1):188- 194, 2015.
Noureddine El Karoui and Hau- SluuTiien Wu. Connection graph laplacian methods can be made robust to noise. The Annals of Statistics, pp. 346-372 2016.
Abhishek Kumar and Hal Daumé. A co-training approach for multi-view spectral clustering. In Proceedings of the 28th international conference machine learning (ICML-11), pp. 393-400, 2011.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228-23324 1998.
Roy R Lederman and Ronen Talmon. Learning the geometry of common latent variables using alternating-diffusion.. Applied and Computational Harronic Analysis, 44(3):509-536, 2018.
Yongmin Li, Shaogang Gong, Jamie Sherrah, and Heather Liddell. Support vector machine based multi-view face detection and recognition. Image and Vision computing, 22(5):413-427, 2004.
Yei Fileen Lin, Ronald R Coifman, Gal Mishne, and Ronen Talmon. Tree-wasserstein distance for high dimensional data with latent feature hierarchy, arXiv preprint arXiv:2410221107, 2024.
Sitao Luan, Mingde Zhao, Chenqing Hua, Kan-Wen Chang, and Doina Precup. Complete the miss- ing half: Augmenting aggregation filtering with diversification for graph convolutional networks. arXiv preprint ar arXiv:2008.0888 2020.
Minghua Ma. Tingquan Deng. Ning Wang, and Yanmei Chen. Semi-supervised rough fuzzy lapla- cian eigenmaps for dimensionality reduction. International journal of machine learning and cybernetics, 10:397-411. 2019.
Leland McInnes, Alexander Fabisch, Christopher Moody, and Nick Travers. Semi-supervised t-sne using bayesian prior based partial labelling, 2016.
12

---

Published as a conference paper at ICLR 2025
Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint 182.0330,, 2018.
Pete Mowforth and Barry Shepherd. Statlog (Vehicle Silhouettes). UCI Machine Learning Reposi- tory. DOL: https://doi.org110224442222222
Karl Pearson. Lii. lines and planes of closest fit to systems of points in space. The London,
Edinburgh, and Dublin philosophical magazine and journal of science, 2(11):559-57,, 1901.
Vladislav Rajkovic. Nursery. http://ddb.orr/122243321$$$$
UCI
Machine
Learning Repository, 1989.
DOI:
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 290635500):5233-332 2000.
Chao Shen and Hau-Tieng Wu. Scalability and robustness of spectral embedding: landmark diffu- sion is all you need. Information and Inference: A Journal of the IMA, 11(4):1277-1555 2022.
Wing Hutton Sigillito, V. and K. Baker. Ionosphere. UCI Machine Learning Repository, 1989.
DOI:
Ashwin Srinivasan. Statlog (Landsat Satellite). UCI Machine Learning Repository, 1993. DOI: http:///6o..o/10044442//$$55
Jeremias Sulam, Yaniv Romano, and Ronen Talmon. Dynamical system classification with diffusion embedding for ecg-based person identification. Signal Processing, 130:403-411, 2017.
Arthur D Szlam, Mauro Maggioni, and Ronald Coifman. Regularization on graphs with function- adapted diffusion processes. Journal of Machine Learning Research, 9(8), 2008
Ronen Talmon and Hau-Tieng Wu. Latent common manifold learning with alternating diffusion: analysis and applications. Applied and Compulational Harmonic Analysis, 47(3):848-892, 2019.
Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric framework for non- linear dimensionality reduction. science, 290(5500):239-235 22239, 2000.
Lloyd N Trefethen. Spectra and pseudospectra: the behavior of nonnormal matrices and operators. 2020.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mniste a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprini arXiv: 170.:0077,7 2017.
Chang Xu, Dacheng Tao, and Chao Xu. A survey on multi-view learning. arXiv preprint 2013.
Bo Yang, Ming Xiang, and Yupei Zhang. Multi-manifold discriminant isomap for visualization and classification. Patlern Recognition, 55:215-230, 2016.
I-Cheng Yeh. Concrete Compressive Strength. UCI Machine Learning Repository, 2007. DOI: https://bb.org/l0.2443//33
Shi-qing Zhang. Enhanced supervised locally linear embedding. Pattern Recognition Letters, 30 (18):1208-1218. 2009.
Jing Zhao, Xijiong Xie, Xin Xu, and Shiliang Sun. Multi-view learning overview: Recent progress and new challenges. Information Fusion, 38:43-54, 2017.
Koklu Murat Çinar, ilkay and Sakir Tasdemir. Raisin. UCI Machine Learning Repository, 2023. DOI: http://doi..rg//12224222446
13

---

Published as a conference paper at ICLR 2025
A
ALGORITHMS AND BLOCK DIAGRAMS
A.1 ALGORITHMS
Algorithm 2 Supervised Diffusion Maps (SDM)
Input:
Train data: n original dimension train data samples {=+]-=1
Test data: original dimension test data samples {
Train labels: fys
Parameters:
Interpolation parameter: i E (0,
Data distance metrie: metric used to measure the distance between data samples Labels distance metric: metric used to measure the distance between labels
Output: Low-dimensional embeddings of the training and testing data
Step 1: Extract embeddings along the interpolation for the test set
1: Construct Wp (Eq. 6). Obtain P by normalizing WP p as in 3.1
2: For each E, in the test set:
Construct W D for { UTy (Eq. Obtain D by normalizing WD as in 3.1
b. Calculate (t) (Eq. 8
c. Obtain v (z (Eq.
Step 2: Extract embeddings along the interpolation for the train set
1: For each (Ii, yi) in the training set, treat it as unlabeled by ignoring yi and apply the procedure described in Step collect the embeddings of 24.
Algorithm Supi--Sue Diffusion Maps (SSDM)
Input:
Train data: n original dimension train data samples {ar));
Test data: m original dimension test data samples {
Train labels: {wi)
Parameters:
Interpolation parameter: (0,1)
Data distance metric: metric used to measure the distance between data samples
Labels distance metrie: metric used to measure the distance between labels
Output: Low-dimensional embeddings of the training and testing data
1: Construct W p for {x, J==1 U {z J (Eq. 5. Obtain D by normalizing WT as in 3.1
2: Construct W p (Eq. Obtain by normalizing Wp as 3.1
3: Calculate (t)) (Eq.
4: Obtain (x:)) i and {"))),)) where V=(x;) = (1) for i 1,2,..., and
..... ....... m. m. Here, μ4 denotes the k-th eigenvalue and (i) denotes the i-th entry of the k-th right eigenvector of T(I).
(T(T,) = Hg (n + j) for j 1,2,
14

---

Published as a conference paper at ICLR 2025
A.2 BLOCK DIAGRAMS
Apply times for each sample
Construct and
Kernel Interpolation
A "p"
Spectral Decomposition
(Label Kamal)
D (Dota Kamel)
200
200
200
200
Axyi
Angle
Figure 5: Block diagram of the SDM framework. The data kernel D and label kernel P are con- structed separately for each sample. The embeddings shown in the lower part represent the eigenvec- tors. Blue rows/columns in D and P correspond to labeled data samples, while the red row/column correspond the unlabeled data sample. Similarly, the blue embeddings correspond to labeled data, and the red embeddings correspond to unlabeled data samples.
Construct D and
Kernel Interpolation
10 'p
Spectral Decomposition
(Label Korne))
(Deta Korne)
t-0.0
two 02
tw0.3
1w1.0
200
200
200 Anga
200 Anple
Argle
Angl
Figure 6: Block diagram of the SSDM framework. The data kernel D and label kernel con- structed once for all samples. The embeddings shown in the lower part represent the eigenvectors. Blue rows/columns D and P correspond labeled data samples, while red rows/columns corre- spond to unlabeled data samples. Similarly, the blue embeddings correspond to labeled data, and the red embeddings correspond to unlabeled data samples.
15

---

Published as a conference paper at ICLR 2025
B ADDITIONAL IMPLEMENTATION DETAILS
In our study, we utilized the official Sklearn implementations for t-SNE, Isomap, LE and LLE. For UMAP, supervised UMAP, and semi-supervised UMAP we employed the official implementations. Diffusion Maps were implemented by us.
Regarding supervised I-SNE, although multiple versions have been published in academic papers, the code implementations were not released. Therefore,, we utilized the semi- sum-svieee t-SNE ver- sion (Mcinnes et al., 2016) implemented by Leland McInnes, the creator of UMAP (Mcinnes al.) 2018).
For all algorithms, we primarily used default parameters, except for selecting the number of neigh- bors parameter for UMAP, supervised UMAP, semi- semi-supervised UMAP, Isomap, LE, and LLE, and the perplexity for t-SNE and semi-supervised t-SNE.
To select the for the Gaussian kernels of the data and label kernel for SDM and SSDM, we ap- plied the following heuristie: we calculated kernels using different e values from 10-5 10 and chose the value that resulted in the kernel with the largest number of eigenvalues in the range [0.0001, 0. 0.9999]. We applied this heuristic because we observed numerical issues when the eigen- values of the kernel were too large or too small. We did not optimize over to try to improve performance on the datasets.
We selected the flow resolution parameter, which is the number of sampled kernels along the inter- polation, defining {t,]== in the interval [0, 1]. to be 101 for all evaluated datasets. This means that generated embeddings for each test and train sample along the interpolation for all kernels at 4; in 0, 0.01, 0.02, 0.99, 1.0, then selected the optimal t from this set based on the first data split, as described in Subsection 6.2.1 As for the distance metric, we used only Euclidean distance for both the data kernel and the label kernel.
As for SSDM, the optimal / is usually large (0..9 1)). This means that the interpolated kernel result is close to D. We found it effective to apply the following SVD thrinkage-based denoising tactic to the kernel D before applying SSDM. We reconstruct D with singular values sampled from sigmoid normalized between 0 and 1. Practically, we do this as follows:
Algorithm 4 Pseudocode for SVD Shrinkage-Ban Based Denoising Tactic
1: U, Σ, V SVD
2: s + 1ispacce-5,,5,0
3:
[+exp(s)
o-min(o)
4: 0 max(o))min(()
5: Σ < o
6: D t UEV
As described for SDM, the embedding of the training set for i. can be obtained straightforwardly using V (z,) = P& p. (i) for i 1,2...., n. However, since the embedding of z was generated without alignment with a label, we observed a slight improvement in downstream tasks by applying a similar distortion to the training set embeddings, ensuring greater consistency with the embedding of F. To achieve this, extend the F procedure to all training samples {z,};- using leave-one- out approach, where each sample (æ,, y4) in the training set is treated as unlabeled. In this case, we construct kernels in R=*= using the data samples {ar))i 1 Us; and the (n 1) labels (17 ) For
each sample x4, we compute the embedding as (x;) = (M)x(())
In the original Diffusion Maps algorithm, Eigenvalue Decomposition (EVD) is applied to the kernel. In our approach, we utilize Singular Value Decomposition (SVD) instead, as previously suggested for Alternating Diffusion (AD) in Talmon & Wu (2019). We chose SVD because it produces results similar EVD. but with the added advantages of faster computation and greater numerical stability in NumPy's implementation.
The hardware utilized for testing the runtimes of SDM and SSDM, as depicted in Table 6 in Ap- pendix E.3 is the ROG Strix G16 Asus laptop equipped with an Intel 19- 14900HX processor.
16

---

Published as a conference paper at ICLR 2025
C THEORETICAL JUSTIFICATION, PROOFS AND EXPLANATIONS
C.I DISCUSSION OF SHARED STRUCTURE ASSUMPTION
Our method is designed to extract the shared underlying structure between the data and labels, rely- ing on the assumption that they exhibit a common geometry. While this assumption is challenging validate directly, we propose an alternative, more practical criterion: when the labels of two sam- ples are close (i.e., the label distance is small), the distances produced by our label-driven diffusion process should be smaller than the direct pairwise distances between the data samples. This leads to higher transition probability in kernel compared to the data kernel. Conversely, if the labels are distant (i.c., the label distance is large), the distances from our label-driven diffusion process should exceed the direct pairwise distances between data samples, resulting in a lower transition probability in our kernel compared to the data kernel. If this relationship holds, it suggests that the assumption valid for the given dataset. In simpler terms, the assumption is that our label-driven diffusion more accurately reflects the label distances than the direct pairwise distances between the data samples. This assumption can be formalized follows:
Assumption 1. For any data samples and j. if the labels yi and yj are similar, i.e., dy Vj) < then [PD), > [D],s- Conversely, if the labels ys and are not similar, i.e., dp( Mj) > 1), then [PD] < [D]
where 1) is parameter that defines whether two labels are considered similar or not.
When this assumption does not hold that is, when the direct pairwise distances between data samples align better with the label distances than our diffusion distances the traditional Diffusion Maps is expected to outperform our method. such cases, the kernel D will better represent the label distances than our kernel PD.
To assess whether the assumption holds for real datasets, we propose using heatmap visualizations of both our method's kernel and the unsupervised Diffusion Maps kernel. These heatmaps, sorted by label with rows representing unlabeled samples and columns representing labeled samples, pro- vide visual means of evaluating the assumption. An ideal heatmap for classification should exhibit diagonal high-value blocks corresponding to each class, indicating that samples have high transi- tion probabilities others within the same class and low probabilities to those in other classes, as outlined in Assumption[] []]
Figures 7 and show heatmaps for our method and the unsupervised Diffusion Maps applied the Mice dataset (Higuera & Cios 2015) and the Raisin dataset (Cinar & Tasdemir 2023), respectively. In both cases, our kernel better approximates the ideal diagonal block structure compared to the unsupervised Diffusion Maps kernel. This result aligns with the Misclassification Rates reported in Table For the Mice dataset, our SSDM embedding achieves a Misclassification Rate of 0.016 + 0.009, while the unsupervised Diffusion Maps yield a Misclassification Rate of 0.162 + 0.019. Similarly, for the Raisin dataset, SSDM achieves Misclassification Rate of 0.176++0.019, comparee to 0.26 + 0.021 for the unsupervised Diffusion Maps.
Conversely, Figure / presents heatmaps for the Customers dataset (Cardoso 2013), where neither method effectively captures the label structure. The heatmaps lack the expected diagonal block pat- terns, reflecting a failure to align with the assumption. This is further reflected in the Misclassifica- tion Rates: SSDM achieves 0.328 0.044, while the unsupervised Diffusion Maps perform slightly better with a Misclassification Rate of 0.283 + 0.047. In this case, where the assumption does not hold, as evident in Figure 9 the unsupervised Diffusion Maps outperform SSDM.
17

---

Published as a conference paper at ICLR 2025
0.04
0.024
10
DL032
-0003
0.0000
700
0.0006
0.0
(a) SSDM, Misclassification Rate: 0.016 + 0.009
Diffusion Maps, Misclassification Rate: 0.162
0.019
Figure 7: Heatmap visualization of method's kernel and the unsupervised Diffusion Maps kernel for the Mice dataset.
0.0000
6.006
81
0.00150
41
0.004
125
164
162
0.03
181
193
0002
225
236
383
201
0,00000
SSDM, Misclassification Rate: 0.176 1 0.019
(b) Diffusion Maps, Misclassification Rate: 0.26
0.021
Figure 8: Heatmap visualization of our method's kernel and the unsupervised Diffusion Maps kernel for the Raisin dataset.
6,007
30
45
0.001
50
95
100
100
600002
110
110
115
115
0.001
125
125
150
130
00
(a) SSDM, Misclassification Rate: 0.328 + 0.044
(b) Diffusion Maps, Misclassification Rate: 0.283
0.047
Figure 9: Heatmap visualization of our method's kernel and the unsupervised Diffusion Maps kernel for the Customers dataset.
18

---

Published as a conference paper at ICLR 2025
C.2 PROOF PROPOSITION
Proof of Proposition] 7
We consider modifications for tractability, First, we clip negligible affinity
values by WD(1,))
exp
if (2t, S 6n
(13)
0,
if d (g) 5n
Second, we consider a different kernel normalization given by D Dj WD. where D2 diagonal matrix consisting of the sum of rows of Wp. Note that the resulting normalized data kernel is row-stochastic. In addition, was shown in Coifman Lafon (2006) that is similar to the symmetric kernel used so far when the data is uniformly distributed on the data manifold. The label kernel and the inaccessible kernel L undergo the same modifications.
Let Li denote the elements of L and Dr,; denote the elements of D. We refer to the i-th row vector of L I and the i-th column vector of D as dj. Using this notation, we can express the elements of PD and LD as follows:
[D] k. lidj,
(14)
1;dj
Li Du+ig- for < i
[PD]a
(15)
D Dn+iig
if = n +
Thus, we can relate LD and PD as E = LD PD, where the elements of E are defined by:
Lin+1 D=ti.t
for sisn if n n
E,
(16)
In+id]
Dutia:
Upper bounding ||E,]] is equivalent upper bounding the proof. Therefore, from now on, we will focus on that.
[LD]. [PD] which is the goal of
Next, define (x) and wi (1s) the row sums of W ji and W Wz(t,)). We assume that for sufficiently large n, the row sums of L and P are approximately the same, as P before row normalization only lacks the values of the last column L before row normalization. We bound wD( as follows:
(D:) = Σ exp
(
dp (I);
Σ exp (-
8n cD
i W
exp( z W
2
CD
Z)EAND)
ZyEND
(17)
where [NPP) denotes the size of the set N/D) and the transition marked by f is achived under the assumption that ån = ()
Similarly, we get that:
(L(3:) 2 (N(1))
(18)
where !A? denotes the size of the set A7(T)
Thus, based on Eq. 17 and Eq. 18 we can upper bound each element of D and as follows:
Wo(i,))
Wo((,)
Dij
<
(19)
(D(
W Wz(1,))
Wi(i,))
1
L,j
(20)
wr (xi))
W
From Eq. 20 and Eq. 19 we obtain:
L Da.
V.j.k, (1,
(21)
W W
Now, if we examine the n upper rows E, they take the form Lin+ Da+1.5. Therefore, by Eq. we have:
21
Lintt D DutLs
We [L.n [1,n+1]
(22)
Mi m+1
Ne
19

---

Published as a conference paper at ICLR 2025
The transition marked by in Eq. 22 is achieved under the assumption that every sample has least N1 samples its 6-neighborhood in both D and L. Similarly, all subsequent transitions in the proof marked with are based on the same assumption.
Considering the (n + 1)-th row of E, takes the form In+id - D Dat1y. Therefore, we can bound it follows:
In - Dnttgll & max (n+ dj. D D=t1s)-
(23)
Considering only I+11d, we can upper bound it by plugging in Eq. 21 as follows:
min (W 1,
1+ =
Dig
Σ
(24)
(2) 1
1=1
BEAR a+1
=mim
(25)
N1
Considering only D Dz+lis we can upper bound it by plugging in Eq.
19 as follows:
D S
(26)
N1
Therefore, we can conclude that:
-andd,-D S max min 1
(27)
[ (NDD01 f
[W
N1
We proceed by demonstrating when Egj O:
For sis n: The entry E, is nonzero only if ys E < n41 and xj E AVDD
n+1
For = n + 1: We have
B = In+ D Datisll
where lnt1dj EnS 1 Daj- Therefore,
| = Il=idd Dn+1,ll S max (m+t1dj, Duti.h.
Here, Int1dj is nonzero only if there are samples (4;; ys) for E [1, n. + 1] such that y: ArD and H; ,1 If such samples exist, implies that the j-th sample, for j [1, n is close to the (n 1)-th sample. For simplicity, we assume this occurs when y E n+1 and xy E (VDD) n+1*
Additionally, Dn+1J is nonzero only when xy E (DD for j E (I...., 1}.
Thus, by combining both cases, E., for i n is nonzero only when Ty A Ar(D)
Based on the analysis for the cases when Ei = 0, along with the element-wise bounds provided in Eq. 22 and Eq. 27 we conclude the proof.
20

---

Published as a conference paper at ICLR 2025
C.3 PROOF PROPOSITION
As demonstrated in the Proof of Proposition | PD can be expressed as perturbed version of LD such that PD LD E, where E is defined follows:
Proof of Proposition 2
Lin+ Dz+1.h In
for siin if = nn
E
(28)
D Detid:
By the eigen decomposition, we have LDv = Substituting LD PD + E, and noting that an eigenvector of LD with the corresponding eigenvalue μa, we get:
(PD E)u pw.
(29)
We can reorganize this as:
(PD uTyy EE.
(30)
Applying the norm on both sides, we obtain:
[P /T)ell || Eull |e||
|B|||]||
[E]]
(31)
where the last equality holds because ||a|| = 1.
We proceed by constructing the matrix (b)) as follows:
for sii n.y, E AdlL)
n+1: EN(D)
N
n+1
M E
if = n + A1D) n+1
(32)
N
0,
else
Thus, based on the proof of Proposition
E(b) provides an clement-wise bound on E by construc-
tion, such that EEyll E for all j. {1, (1..... 1}.
We continue by considering |E()) |[1 and ||, which are computed through the maximal col- umn and row respectively. We assume that each sample has at most N2 neighbors within its 9-neighborhood in both D and L. Thus, for each column vector of E()), the sum of the first entries is bounded by N₂ Nº and the (n + 1)-th entry is bounded by Ni Consequently, the maximal column sum is bounded by:
N2
(33)
N
N
Additionally, the of each of the first vectors of E is bounded by N the (n 1)-th row vector is bounded by Na N.
while the sum of Therefore, the maximal row sum bounded by:
N₂ N1
| 11
1.
(34)
The transitions marked by in Eq. to N, i..., N₁ ze zs N₂.
33 and Eq.
34
assume that N1 and N2 are approximately equal
Using the upper bound of the spectral norm [
S
E
100
we get:
N₂
N₂
2 N
E
E h
(35)
N
Since the bound of E depends on || and []]) which are computed through the maximal column and row respectively, this is also valid bound for [[]] as E(0) is an element-wise bounding matrix of E. Thus, we get:
N
N
2
E <
E
<
(36)
N2
N
21

---

Published as a conference paper at ICLR 2025
Assuming that e this expression into Eq.
and considering that N is sufficiently large, substituting N
2
N
N:
yields:
[P j | I S c.
(37)
Thus, from Definition we conclude that the eigenvector of LD is am -iseuuo-eigenveetor of PD with the corresponding eigenvalue μt.
C.4 BALANCING P AND D USING
Considering our interpolation scheme, have:
((t) = P' 0
For any matrix A E R which are similar to Symmetric Positive Definite (SPD) matrices (such as P and D when using row normalization), the fractional power a can be expressed using Eigenvalue Decomposition (EVD) as follows:
A =-=VV
where is an orthogonal matrix containing the left eigenvectors A, is an orthogonal matrix containing the right eigenvectors of A, and Σ is a diagonal matrix with the eigenvalues o; of A on its diagonal. The fractional power E is defined as:
E diag(of ......
where each eigenvalue o, is raised to the power
By raising P and to the fractional powers 1 1 and 1, respectively, we amplify the smaller eigenvalues more significantly. Since smaller eigenvalues correspond high-frequency components of graph signals, this fractional power operation effectively acts as a high-frequency amplifier. By adjusting t, we can control the balance of high-frequency amplification between P and D. When t is small, the high frequencies of D are amplified, and when t is large, the high frequencies of P dominate.
Next, we address the concepts of homophily and heterophily in the context of graphs. Homophily refers to the phenomenon where connected nodes share the same label, whereas in heterophilic graph, the labels of neighboring nodes can differ. Recent studies (Bo et al. 2222]] Chien et al.) 2020) Luan et al. (2020) have shown that high-frequency graph signals are empirically effective in tackling the challenges posed by heterophilic graphs. Given that the graph represented by the data kernel D can be heterophilic as the data may be quite noisy, amplifying the high frequencies parameter t can be effective. Similarly, if the quality of the labels is subpar, amplifying the high frequencies P may also help. In conclusion, our interpolation scheme balances the amplification of high frequencies in both P and D, which can be interpreted as interpolation in the frequency domain.
using the
22

---

Published as a conference paper at ICLR 2025
C.5 LABEL-DRIVEN DIFFUSION ILLUSTRATIVE EXAMPLE
This appendix presents simple toy problem aimed solely at illustration. Consider a dataset consist- ing of three samples ( 22,433 with corresponding labels (y1,32; v3), and suppose that only yi and 1/2 are available and is unavailable. From this dataset, we can construct three graphs with the same node set [1, 3), representing the three samples, but with three different transition kemels:: D. L, and P.
For the purpose of this analysis, we assume that the transition kernel L captures the hidden intrinsic geometry of the data as it has access to all the labels (available and unavailable). The transition kernel also captures this intrinsic geometry but is incomplete due to the absence of the label ys- The transition kernel D is noisy, as it is derived from the samples {2,, 233) without access to labels. For simplicity, we construct the graphs without normalization and without self-loops. Consequently, obtain the graphs and their corresponding transition kemelss depicted in Fig. I0
L
0.5
0
0.5
0
1
0
0
1
0
2
3
P
0.5
0
0/
0
1+6
0
2
D = 0.5
0.5 C2
0
0.5
+ 6g
1 64
Figure 10: Graphs and transition kernels for L, P. and P.
We now consider two-step diffusion from node 1 to the unlabeled node 3. The optimal value for
this diffusion given by the -)th element of L which captures the complete hidden intrinsic structure of the data:
L (1, 0.5
If we perform two-step diffusion on the dataset using the unlabeled samples through D² (as in the unsupervised Diffusion Maps), we obtain:
(L, 0.5 + e3 0.5e1 E1
When employing our method, which involves first step the labels and second the data using PD (where serves as a proxy for the inaccessible L), we have:
PD(1.3)
c3
Additionally, if consider two-step diffusion first the labels and then on the data using the inaccessible LD, which we attempt to approximate with PD, we have:
LD(1,3) = 0.5 + e3
Consequently, observe that the transition probability from node node 3 using PD in method is equal to that using the inaccessible LD. Moreover, the transition probability obtained with PD exhibits less distortion compared to the optimal transition probability from L while the distortion exhibited by D is larger.
23

---

Published as a conference paper at ICLR 2025
D ADDITIONAL EXPERIMENTAL RESULTS FOR THE TOY PROBLEM
D.1 TOY PROBLEM ADDITIONAL FIGURE
1-0.0
t=0.02
b+0.3
t-0.8
t=1,0
[Labol Karnel
-2
-2
200
200
42
-2
200
200
Figure 11: SDM progression of the first three components along the interpolation from the label kemel at the data kernel Key areas are highlighted: purple rectangle indicate noisy original Diffusion Maps components; yellow rectangle show potential optimal value components at 0.02; light blue rectangle enclose non-in -on-informetive t 0 components.
t-00
t-0.02
t-03
t-0.8
t-1.0
D iCata Kemnl]
Argditak
V.
Ands
Anga
0
Andl
Ange
Andl
Figure 12: SSDM progression the first three components along the interpolation from the label kernel at t to the data kernel at t = 1. In this case, the optimal t value is large (i.c., 0.8).
24

---

Published as a conference paper at ICLR 2025
(a)
(b) 1=0.2
(c) t=01
(d) 10.66
(e)== (DM)
(f) 1=0
(g) 10002
(h) t0.1
(i 10.6
i -= (DM)
Figure 13: Two-dimensional embedding of SSDM with various t values. The first row displays results for the toy problem dataset, detailed in Subsection 6.1 featuring three figures (Superman and two interference figures). The second row, serving as a baseline, shows results for dataset containing only images of Superman, without interference figures. Dots (+) denote labeled training samples, while pluses (+) denote unlabeled test samples.
S5DM-80
S5DM-60
80
SSDM-20
60-
14E
1.0
Figure 14: SSDM performance with varying labeled data ratios.
D.2 COMPARISON WITH AD INTERPOLATION
To demonstrate the importance of the proposed interpolation scheme, we compared it to a simpler interpolation, given by PD, which does not balance between P and D using for both supervised and semi-supervised settings. This simpler interpolation analogous to the one employed by AD (Lederman & Talmon 2018).
Table the angular MAE and R² obtained by our SDM and SSDM, as well as by a random guess baseline, DM, and the AD interpolation. The table demonstrates the effectiveness of SDM and SSDM in generating informative embeddings that consistently outperform the other methods. Notably, DM performs only slightly better than random guess, while AD in the semi-supervised setting is equivalent to a random guess.
25

---

Published as a conference paper at ICLR 2025
Table 2: Evaluation of SDM and SSDM, compared baselines and AD.
Method
Supervised MAE
Semi-supervised
R²
MAE
R²
Random guess
90"
0.0
DM (baseline)
79
0.08
AD
50.3
0.35
83.35
-0.01
Our Method
8.88
0.97
4.1"
0.99
E ADDITIONAL DETAILS AND RESULTS FOR REAL DATASETS
E. REAL DATASETS
Table presents the datasets and their properties, where n stands for the number of samples, d for the original data dimensions, and in the 'Type' column, 'C' stands for classification and 'R' for regression.
Table Datasets
Dataset
Type
d
Tris (Fisher 1988
150
lonosphere Sigilltto & Baker 1989)
351
34
Yacht (Gerritsma & Versluns 2013)
R
308
6
Boston (Harrison & Rubinteld (978)
506
Liver mms 1990)
345
5
Arrhythmia (Guvenir & Quinlan 1998)
452
279
Musk (Chapman Jain 1994)
Mice (Tiguera & Cros 2015)
1080
77
Rice (mis) (2019)
3810
7
Concrete (Yh||2007)
1030
Silhoucttes (Mowforth & Shepherd)
845
18
Raisin (Cinar & Taademmr 2023)
900
26

---

Published as a conference paper at ICLR 2025
E.2 COMPLETE RESULTS WITH STANDARD DEVIATION
Table 4: Complete evaluation results with standard deviation and with the number of dimensions
that yielded the smallest error indicated in parentheses.
S/SDM
0.03445)
0.026
0.073
1.0223
0.431
+ 0.048
0.1018)
+ 0.024
0.12())
+ 0.063
0.068(3)
+ 0.01
0.474(15)
+ 1.054
0.00 0016290
10.000
#0002
117610
0.010
04000
Semi/Supervised Algorithms
10000
=
1018
SSISNE
(
1 1.033
0.11
1.002
0.456
+ 0.038
0.163(7)
+ 0.024
2000
2000
01180
+.000
S/SUMAP
)
0.035(9)
1 0.022
0.155(24)
0.027
0.485
+ 0.033
0.171(25)
0.03
0.549(5)
+ 0.057
0.083(15)
#
0.519(8))
= +000
2000
0.153
(153(22)
+.000
0000800000
0,22122
0.022
+ + )
0.07(26)
0005
0.051
1 0.047 047
0.108(1)
1. 0.025
0.506(29)
+ 0.033
0.18(16)
- 0.032
0.43(17)
0.09
0.096(6)
10011
0.497(6)
0.051
0.162(30)
#0000
043722
0. #
00002
0.26(30) )
0.021
0.085(29)
0.007
DM
0.002((0)) (0
0.06(3)
1 0.048
0.121(7)
0.031
0.533(22)
+ 0.035
0.204(30)
#
0.498(4)
#
0.08(13)
0.013
0.502(2)
0.058
0.004
0.156(7)
+0,00
0.297(1)
0.027
0.204(4)
0.021
0.051(8)
0.005
LLE
Semi-Supervieed Setting
Supervised Setting
Unsupervised Algorithms
0.034(23)
1 0.027
0.12(27)
0.025
0.443
# 0.039
0.122(18)
0.025
0.208(30)
0.054
0.083(30)
#.01
0.481(30)
0.046
0.045(13)
0.06
0.1528)
0000
0.419(24)
0003
0.21633
0.019
0.08(30)
+ 0.006
LE
(
8
(SNE
0.047(22) 0.044(2)
0..23
0.117(2)
0.026
0.476(4)
0.041
0.145(2)
#
0.451(4)
00047
0.074(10)
#00009
0.511(2)
0.051
0.01(10)
0.000
0.148(7)
00000
0.378(16)
1000
0.216(5)
0.021
0.064(7)
0.005
Isomap
0.034
0.1125)
0.028
0.484(25)
1 0.033
0.189((3)
0.031
0.395(29)
- 0.056
0.087(16)
# 1.011
0.50(3)
0.051
0.03(28)
0.01
0.012 0.127(27)
+ 0.008 0.008
0.35(20)
0.024
0.195(26)
0.022
0.066(6)
+ 0.005
UMAP
0.037(2))
0.026
0.15(11)
0.002
0.51(23)
0.036
0.191(26)
0.029
0.549(16)
+ 0.054
0.084(7)
+ 0.011
0.508(28)
+ 0.051
0.029(30)
0.146(9)
0.39(14)
+ 0.032
0.211(18)
0.02
0,077(19)
0.005
Type
C
C
C
R
R
R
C
C
C
C
R
Dataset
lonosphere
Arrhythmia
Silhouettes
Concrete
Boston
Name
Musk
Yacht
Liver
Mice
Rice
Raisin
Iris
27

---

Published as a conference paper at ICLR 2025
E.3 COMPARISON BETWEEN SDM AND SSDM
We present a comparison between SDM and SSDM, acknowledging that SDM, in principle, can be applied in semi-supervised settings, particularly when runtime not constraint. To address this, have included a detailed comparison in T showcasing results for both SDM and SSDM across all datasets where only SDM results were previously reported. As highlighted in the table, SDM generally achieves slightly better performance than SSDM, consistent with our theoretical analysis. However, SSDM demonstrates superior performance certain cases, such as the Yacht dataset and the toy problem introduced in this paper, as illustrated in Figure 3
The reason why SSDM can surpass SDM in certain cases becomes evident when examining the components of the toy problem shown in Figures [1 and 12 Figure 11 presents the SDM results with the optimal From these figures, observe that SDM embeddings. influenced by individual kernels for each data point, exhibit greater variability, leading to embeddings that are less consistent across samples. In contrast, SSDM embeddings, constructed from single kernel, demonstrate greater consistency across samples.
0.02, while Figure [2 displays the SSDM results with the optimal = 0.8.
Theoretically, this variability in SDM could be mitigated by using larger kernels. However, 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.
Table 5: Comparison between SDM and SSDM, reporting NMSE for regression ('R') and Misclas- sification Rate for classification ('C'), along with runtimes (in seconds).
Dataset
SDM
SSDM
Name
Type
Error
Runtime
Error
Runtime
Iris
0.034
0.026
5.5
0.036
0.022
0.1
lonosphere
C
0.073 + 0.023
50
0.098 + 0.023
0.4
Arrhythmia
C
0.431 + 0.048
107
0.431
0.038
0.7
Musk
C
0.101
0.024
124
0.124
0.023
0.5
Yacht
R
0.12 + 0.063
9.3
0.008
+ 0.003
0.1
Boston
R
0.068
0.01
41
0.05
0.008
0.3
Liver
0.474 0.054
13
0.48
0.051
0.1
28

---

Published as a conference paper at ICLR 2025
E.4 ERROR RATES ACROSS DIMENSIONALITY
SDM achieves the best results for all datasets, and in some cases, its performance is superior across all chosen dimensions. For instance, as shown in Figure 13| SDM outperforms all evaluated algo- rithms for the lonosphere dataset across all dimensions from to 30.
Moreover, SSDM achieves the best result for all datasets except for Mice, and in some cases, its performance is superior across most chosen dimensions. For instance, as shown in Figure [6 our SSDM outperforms all evaluated algorithms for the Silhouettes dataset across all dimensions from 3 to 30.
ISOMAP
LE
LLE
SUMAP
TSNE
UIAP
(ours)
Error
0.25
0:2-
Number Dimensions
Figure 15: This figure depicts the rate for the lonosphere dataset the number of dimensions increases in the supervised setting.
DN
ISOMAP
LE
LLE
SSISNE
SSUMAP
TSKE
LIME
SSDIN (ours)
Error
0.3
025
Number Dimensions
Figure 16: This figure depicts the error rate for the Silhouettes dataset the number of dimensions increases in the sumi-supereiseed setting.
29

---

Published as a conference paper at ICLR 2025
E.5
RUNTIME COMPARISON
Table 6: Comparison of Runtimes [in secs]
Dataset
UMAP
Isomap
ISNE
LE
LLE
DM
SUMAP
SSUMAP
SSISNE
SDM
SSDM
Iris
2.5
0.01
0.5
0.01
0.01
0.02
4.3
2.6
0.8
5.5
0.1
Mice
0.5
47
0.5
0.2
4.1
5
3.5
29.4
934
3
Rice
2.7
110
0.7
1
16.2
8.5
7.8
N/A
N/A
55
30

---

Published as a conference paper at ICLR 2025
F COMPLEXITY ANALYSIS AND OPTIMIZED SSDM IMPLEMENTATION
For SSDM, the affinity kernels D and P are computed with time complexity of O(d n²),, where is the dimensionality of the data. The computation of D' and pl using SVD requires O(n)), and multiplying the kernels to obtain p also takes On²"). Finally, obtaining the embeddings using SVD is an additional (n²)). Therefore, the overall time complexity of SSDM is O with space complexity of (n²)).
In contrast, SDM involves applying the SSDM procedure n times, resulting in a time complexity of Onn)) and space complexity of O This analysis indicates that SDM is impractical for large or even medium-sized datasets, while SSDM remains feasible for datasets with up to approximately 10,000 samples.
To overcome this limitation, we have implemented an optimized version of SSDM that is highly suitable for large-scale datasets. In the optimized version, instead of constructing the label and data kernels P and D with dimensions n X n, we randomly sample k labeled samples from the training set. This results in label kernel P of size k x k and a data kernel D of size k n, where & is set in our experiments to 0.01 if > 10, 000 and to 0.1 n if n S 10, 000. Empirically, we have found that a small proportion of labeled samples can effectively represent the space in large datasets. For very large datasets, k can be set to any fixed small value, smaller than 0.01 n. Apart from the adjustments to 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(k2 n), making it scalable for very large datasets (larger than 100,000 samples).
Furthermore, the optimized SSDM is implemented using torch, leveraging GPU acceleration to perform matrix multiplications in parallel. This allows for significant speedups in computation, en- abling the method to process large-scale datasets efficiently.
For comparison, t-SNE has a time complexity of O(?2), with optimized versions having a com- plexity of Onn logn). nt. while UMAP has time complexity of O(d n n1.14). As such, for smaller values of k; our method is more time-efficient than these alternatives, as observed in our empirical experiments.
To evaluate the effectiveness of the optimized SSDM and the improvements in runtime, we follow the procedure outlined in Section 6 which involves reducing the dimensionality, training KNN classifier, and reporting the Misclassification Rate.
First, we compare the optimized SSDM the unoptimized SSDM the Rice dataset (3810 sam- ples), As reported in Table 66 the unoptimized SSDM takes 55 seconds. By contrast, using the optimized SSDM with senting a x 1833 improvement in runtime. The Misclassification Rate for the optimized SSDM is 0 which is slightly worse than the 0.104 + 0.009 reported for the unoptimized SSDM. However, this trade-off is accompanied by significant improvement in runtime.
0.1
381, we achieve runtime of just 0.03 seconds, repre-
In Figure 17 we present heatmap visualizations (as discussed in Appendix C.Ip comparing the unoptimized SSDM, which utilizes all training labels, to the optimized SSDM, which uses only k: 381 labels.
Next, we demonstrate the effectiveness of the optimized SSDM on large datasets that are impractical to process using the unoptimized SSDM. Specifically, we evaluate the optimized SSDM on the MNIST dataset (LeCun et al.] 1998). Fashion-MNIST (Xiao et al. 2017), Isolet (Cole & Fanty 1991). Adult (Becker & Kohavi 1996), Landsat (Srinivasan 1993). and Nursery (Rajkovic) 1989). In these experiments, the parameter k is set to 0.01 n for 10, 000 and 0.1 n for n 10, 000.
Table 7 presents the Misclassification Rate for each dataset. For comparison, we include results for the unsupervised Diffusion Maps (by using the data kernel D employed in the optimized SSDM, which has dimensions of k x n) and remi-supervised UMAP. As shown in the table, our SSDM achieves the best performance on 3 out of the 6 datasets.
Table reports the runtime comparisons. Notably, our optimized SSDM is significantly faster than semi-supervised UMAP across all datasets.
31

---

Published as a conference paper at ICLR 2025
Table 7: Evaluation on Large Datasets: Comparison of Diffusion Maps, SSUMAP, and the Opti- mized SSDM
Dataset
Misclassification Rate
Name
DM
SSUMAP
SSDM (ours)
MNIST
70,000
784
0.22 + 0.006
0.046 = 0.001
0.1 = 0.003
Fashion-MNIS,
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
48842
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
12960
0.128 + 0.03
0.193
+ 0.005
0.082
0.008
Table 8: Runtimes on Large Datasets (in seconds): Comparison of SSUMAP and the Optimized
SSDM
Dataset
Runtime
Name
SSUMAP
SSDM (ours)
MNIST
70,000
784
35
8.1
Fashion-MNN MNNIST
70,000
784
35
8.35
Isolet
7797
617
7
1.2
Adult
48842
14
27
1.4
Landsat
6435
6.3
0.12
Nursery
12960
5.5
0.4
101
0.0000
100
0.0004
0.0003
0.0003
D7
100
255
801
1000
281
0.0003
185
1050
3525
0.0000
Optimized SSDM
(b) Unoptimized SSDM
Figure 17: Heatmap visualization of the optimized SSDM kernel using only k = 381 labeled sam- plcs, compared to the unoptimized SSDM kernel utilizing all labeled samples for the Rice dataset.
32

---

Published as a conference paper at ICLR 2025
G EXTENDED REVIEW AND FUTURE DIRECTIONS
G.1 MULTI-VIEW LEARNING
Multi-view learning utilizes information from multiple representations or perspectives of the same data to enhance learning performance. These views can originate from different modalities, such as text, images, or audio, or from different transformations of the same modality (Xu et al.) (2013). Traditional approaches like co-training (Kumar Daumé 201T) focus on alternating the training of classifiers on distinct views, leveraging the mutual information between them to improve perfor- mance. Canonical Correlation Analysis (CCA) is a foundational method that identifies linear trans- formations of two views to maximize their correlation in shared subspace (Hotelling) 1936). Recent developments in multi-view deep learning have integrated these principles into neural networks, en- abling models like multi-vien autoencoders (Du et al. 2021 to jointly learn from heterogeneous data representations.
Recent advancements in multi-view learning include the emergence of co-regularization and margin- consistency algorithms (Zhao et al. 2017). Co-regularization approaches introduce constraints to ensure the consistency of predictions across views, utilizzigg methods like multi-view Support Vector Machines (SVMs) (Li et al. 2004) and multi-view linear discriminant analysis (Kan et al. 2015) align feature spaces. Margin-consistency algorithms. on the other hand, enforce agreement on decision boundaries across views, often leveraging maximum entropy discrimination frameworks (Zhao et al.) 2017). These methods demonstrate the power of multi view learning in diverse tasks such clustering, classification, and transfer learning, where the complementary information from multiple views significantly enhances performance.
A key challenge in multi-view learning is effectively integrating diverse and sometimes incomplete views in a scalable manner. Large-scale applications, such as analyzing multi-modal datasets (c.g., combining video, audio, and text), demand computationally efficient algorithms. Approaches like multi-view dimensionality reduction aim to create low-dimensional representations that preserve the shared structure among views while accounting for unique characteristics.
One branch of multi-vies learning is multi-kerna learning (Bach et al. 2004), which combines multiple kernels, each capturing specific view aspect of the data, into unified framework. By integrating diverse sources of information, kernel methods provide a flexible and powerful approach to learning relationships in complex datasets. They are partieularly well-suited for multi-view set- tings because they can model nonlinear relationships and accommodate varying feature spaces be- tween views. Kernel-based methods often employ techniques like kernel alignment or optimization of weights across kernels to balance the contributions of different views.
prominent method within the multi-kernn learning framework. Our work incorporates elements of nue learning by treating labels as a second view of the data. While we focus on alternating diffusion to integrate label information, similar strategies can be applied in other multi-view methods to incorporate labels and enhance the learning process.
Alternating diffusion (Leerman & Talmon 2018)
G.2 EXTENDED REVIEW OF ALTERNATING DIFFUSION
Alternating Diffusion (AD) (ederran & Talmon
2018) extends the Diffusion Maps framework,
and diffusion geometry (Coifman Lafon 2006 Lin al. 2024), to extract the common structure of two aligned datasets,
{1 (2)
yn
Jiz
This technique particularly useful for analyzing milti-view data where the goal is disentangle shared latent structures while suppressing view-specific variability.
The process begins by constructing affinity matrices (!)) and ( for the datasets (a(")) } and (2) p respectively. The entries of these matrices are computed using Gaussian kernel:
(z(22)
"(a."".r" (m))2)
((,)), = exp
E {1,2},
c(1)
33

---

Published as a conference paper at ICLR 2025
where -(:-)) -) is distance metric, and e(*) is the kernel scale parameter for view These affinity matrices encode local pairwise similarities within each dataset.
To construct diffusion operators, the affinity matrices normalized in two stages. First, diagonal matrix D (v) is computed from the row sums of W(+);
D 1 (i, (i, Σ (1,).
The affinity matrix then symmetrically normalized obtain:
K ( (D))))-'w()) -1
Next, a second diagonal matrix D (1))
is calculated from the row sums of K(v);
D 2 E
Finally, the row-stochastic diffusion operator is obtained as:
K (D!
This matrix, K(e), represents the transition probability matrix of Markov chain the dataset for view e.
The alternating diffusion process combines the diffusion operators from the two views. The com- bined operator, (())((), is defined as:
(() (2)).
This operator alternates between propagating information through ( and K facilitating the extraction shared structures between the datasets.
To extract the shared latent structure, spectral decomposition is performed on (1)n(2), The eigen- vectors corresponding to the largest eigenvalues provide the embedding coordinates:
K K = 1 j = 1,2,.....4
where v, are the embedding vectors, and H,y are the eigenvalues. The dominant eigenvectors repre- sent the smoothest variations that are consistent across both datasets.
In conclusion, Alternating Diffusion extends the Diffusion Maps framework to capture the common structure between two aligned datasets by using an alternating diffusion process that propagates information back and forth across the two modalities. This process can be interpreted diffusion on two distinct graphs, one for each dataset. In each diffusion step, the kernel corresponds to transition matrix on the respective graph, where mass is propagated across the vertices (samples) based the kernel's 'ss transition probabilities. As the process alternates between the two kernels, the mass spreads across both graphs, ensuring that information from both datasets influences each other. This alternating propagation gradually aligns shared structures while suppressing dataset-specific variations, resulting in a smooth representation that highlights the common features between the datasets and effectively extracts the shared latent structure while filtering out modality-speciff noise.
G.3 FUTURE WORK
One possible direction for future work is explore other kernel interpolation schemes for inte- grating data and label information. While our current method uses specific approach to combine the kernels, alternative schemes may provide better performance adapt more effectively to dif- ferent datasets. Investigating these alternatives could enhance the ficxibility and robustness of the framework.
Another promising idea is to learn the amplitude of each spectral component (eigenvalue) instead of relying on the power mechanism Our current approach maintains the relative order of the components for any value of t, with the leading eigenvalues of P and D always remaining dominant, By explicitly learning the eigenvalues,
currently use, where the eigenvalues raised to t and t.
34

---

Published as a conference paper at ICLR 2025
it would be possible to adjust the order and influence of components dynamically, potentially leading to improved performance by tailoring the spectral properties to specific tasks or datasets.
Additionally, extending multi-view approach to other algorithms, alternating diffusion, is another avenue worth exploring. By applying the same principles to methods like multi-view autoencoders, could enable these approaches better leverage label information and enhance their effectiveness classification, regression, or clustering tasks.
have done here with
Lastly, have demonstrated the effectivvness of our label-driven diffusion in graph setting, we believe it could also be beneficial to explore its incorporation in the context of geometric deep learning. Geometric deep learning methods, which work non-Fuclidean data such as graphs and manifolds, could further benefit from our approach by capturing complex relationships between data and labels in way that respects the underlying geometry of the data.
35


Reviews:
[{"review_id": "YpSFKFFgU0", "reviewer": "Reviewer_7iCi", "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.", "questions": "See weakness above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The strengths of the paper are as follows:\n\n- 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.\n\n- 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.\n\n- 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: \n\n- **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.\n\n- **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.\n\n- **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.\n\nAddressing these questions would greatly enhance the paper and make it a strong fit for this venue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ysuhpei35k", "reviewer": "Reviewer_fvWq", "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. \n\nThe main contributions are as follows: \n\n1. Multi-View Approach: SDM and SSDM incorporate labels as an additional information source, enhancing the manifold learning process. \n2. New Kernel Interpolation Scheme: A method for combining affinity kernels to reveal shared structures between data and labels while controlling their respective contributions. \n3. Experimental Validation: Results show that SDM and SSDM outperform existing nonlinear manifold learning methods across several benchmark datasets, highlighting their effectiveness.", "questions": "see weaknesses", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XZ2WmIuZ2k", "reviewer": "Reviewer_HxoS", "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.", "questions": "Please refer to the weakness list.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) The paper presents a clear motivation for addressing the limitations of traditional manifold learning methods that lack mechanisms to incorporate label information.\n2) Treating labels as an additional data modality and leveraging a multi-view framework can provide some new insights to the community.\n3) 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.\n2. Given that the paper relies heavily on older references with minimal discussion of more contemporary work, are there recent advancements in manifold learning？\n3. 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.\n4. The related work section lacks a comprehensive overview in multi-view learning [3,4].\n5. The computational complexity of the proposed methods is not well-handled, with larger computational complexity compared with other methods.\n\n[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.  \n[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.  \n[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.  \n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "btcm8TIYGZ", "reviewer": "Reviewer_oUg2", "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.", "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?\n\n2. Why the authors choose Euclidean distance in the data kernel and angular distance in the label kernel?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "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,\nthe 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. \n2. Quality and Clarity. There are no technical errors, and the presentation and writing are satisfied.\n3. 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.                       \n\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)