# Laplacian Eigenmaps Dimensionality Reduction Based on Clustering-Adjusted Similarity
## 2 Methodology
### Clustering-Adjusted Similarity  
The GEDR methods often resort to a typical similarity metric to capture the similarity between samples and structure among them. In this paper, we start with the widely used Gaussian heat kernel as follows:  
\[\mathbf{W}_{ij}=\exp\left(-\frac{\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\| ^{2}}{\sigma_{m}^{2}}\right) \tag{1}\]  
where \(\sigma_{m}>0\) is Gaussian hear kernel width. \(\mathbf{W}_{ij}\in(0,1]\) represents the similarity between \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\), and \(\mathbf{W}_{ii}=1\). \(\mathbf{W}\in\mathbb{R}^{n\times n}\) can be viewed as a weighted adjacency matrix of a graph, which stores the pairwise similarity between \(n\) samples. This way of graph construction is proved to be a simple and effective solution by previous studies [13]. However, for pairs of instances located close to the decision boundary but from different classes, they have a high similarity (see two instances in different clusters but with high similarity 0.9674 in Figure 1a), which mislead them being close in the projected subspace. To mitigate the problem, we aim  
Figure 1: Comparisons between two types of similarities between samples, shown as **(a)** and **(b)**. The clustering-adjusted similarity clearly tunes down the Euclidean-based similarity between two instances from different clusters. at reducing the similarity between instances close to decision boundary, which are from different clusters, while remaining the high similarity between samples of the same cluster. To reach that target, we apply CAS as described below. CAS is based on the idea that samples in the same cluster are similar and those in different clusters should be dissimilar as much as much possible. To explore the clusters of the origin instances, we perform kernel \(k\)-means clustering on all instances. Suppose the set of the final clusters is \(\mathcal{C}=\{\mathcal{C}_{1},\mathcal{C}_{2},\ldots,\mathcal{C}_{m}\}\), \(m\) is the number of clusters and \(\mathcal{C}_{h}\) represents the \(h\)-th cluster. \(\mathcal{C}_{h_{1}}\cap\mathcal{C}_{h_{2}}=\emptyset\) (\(\forall h_{1}\
eq h_{2},h_{1},h_{2}=1,2,\ldots,m\)), and \(\cup_{h=1}^{m}\mathcal{C}_{h}=\mathbf{X}\). The cluster centroids (\(\mathbf{u}_{h}\in\mathbb{R}^{d}\)) of the \(h\)-th cluster is:  
\[\mathbf{u}_{h}=\frac{\sum_{\mathbf{x}_{i}\in\mathcal{C}_{h}}\mathbf{x}_{i}}{| \mathcal{C}_{h}|} \tag{2}\]  
\(|\mathcal{C}_{h}|\) is the number of instances placed into the \(h\)-th cluster. Then the similarity between two cluster centroids is similarly defined based on the Gaussian heat kernel as follows:  
\[\mathbf{S}_{h_{1}h_{2}}=\exp\left(-\frac{\left\|\mathbf{u}_{h_{1}}-\mathbf{u }_{h_{2}}\right\|^{2}}{\sigma_{m}^{2}}\right) \tag{3}\]  
\(\mathbf{S}_{h_{1}h_{2}}\in(0,1)\) is the Gaussian heat kernel similarity between \(\mathbf{u}_{h_{1}}\) and \(\mathbf{u}_{h_{2}}\). Obviously, the similarity between two cluster centroids is small when the distance in Euclidian measurement is large. To facilitate the clustering-based adjustment, we define \(\mathbf{I}\) as follows:  
\[ \begin{split}\mathbf{I}_{i}=h,\text{if}&\mathbf{x}_{i }\in\mathcal{C}_{h};i=1,2,3,\ldots,n\\ h=& 1,2,3,\ldots,m\end{split}  \tag{4}\]  
\(\mathbf{I}\in\mathbb{R}^{n\times d}\) is the label indicator matrix, each row corresponds to an instance and each column for a distinct label. \(d\) represents the number of clusters of the whole instances. If instance \(\mathbf{X}_{i}\) belong to the \(h\)th cluster, \(\mathbf{I}_{i}=h\), otherwise, \(\mathbf{I}_{i}=0\). Finally, the original Gaussian heat kernel similarity data matrix \(\mathbf{W}\) is adjusted into \(\hat{\mathbf{W}}\) as follows:  
\[\tilde{\mathbf{W}}_{ij}=\mathbf{S}_{\mathbf{I}_{i}\mathbf{I}_{j}}\mathbf{W}_{ij} \tag{5}\]  
From the definition of \(\mathbf{I}\) and \(\mathbf{S}\), we can find that for two samples (\(i\) and \(j\)) placed into the same cluster \(\mathbf{S}_{ij}=1\), since \(\mathbf{I}_{i}=\mathbf{I}_{j}\), \(\hat{\mathbf{W}}_{ij}=\mathbf{W}_{ij}\).