## 2 Similarity Graphs  
Given a set of data points \(x_{i},\cdots,x_{n}\) and some notion of similarity \(s_{ij}\geq 0\) between all pairs of data points \(x_{i}\) and \(x_{j}\), the intuitive goal of clustering is to divide the data points into several groups, so that points in the same group are similar and points in different groups are dissimilar to each other. If we do not have more information than similarities between data points, a nice way of representing the data is in the form of the similarity graph \(G=(V,E)\). Each vertex \(v_{i}\) in this graph represents a data point \(x_{i}\). Two vertices are connected if the similarity \(s_{ij}\) between the corresponding data points \(x_{i}\) and \(x_{j}\) is positive or larger than a certain threshold and the edge is weighted by \(s_{ij}\). The problem of clustering can now be reformulated by using the similarity graph: we want to find a partition of the graph so that the edges between different groups have very low weights and the edges within a group have high weights.  
The goal of constructing similarity graphs is to model the local neighborhood relationships between the data points. As far as we know, the Gaussian kernel function is still an important construction method; and the important feature of the Gaussian kernel function is that the construction form is based on the Gaussian kernel model, which can be defined as Equation (1).  
\[S_{ij}=\left\{\begin{array}{cl}\exp(-\,d\,(i,j)^{2}\,\big{/}\sigma^{2}\,)&i \
eq j\\ 1&i=j\end{array}\right. \tag{1}\]  
Where, the \(d(i,j)\) is the Euclidean distance between \(x_{i}\) and \(x_{j}\), and \(\sigma\) is the kernel parameter, which is a fixed parameter and cannot vary with the change of the surroundings. [PERSON] _et al._ proposed a local scale parameter \(\sigma_{i}\) for each point to replace the fixed parameter \(\sigma\)[14], which allows the similarity self-tuning capability. Usually, \(\sigma_{i}=d(x_{i},x_{n})\), where \(x_{m}\) is the \(m\)-th closest neighbor of the point \(x_{i}\), and the similarity function is defined as Equation (2).  
\[S_{ij}=\left\{\begin{array}{cl}\exp(-\,d\,(i,j)^{2}\,\big{/}(\sigma_{i}\, \sigma_{j}))&i\
eq j\\ 1&i=j\end{array}\right. \tag{2}\]  
[PERSON] _et al._ proposed a conception of the shared nearest neighbor, which is used to characterize the local density of different vertices [18]. Supposing the closest _kd_ nearest neighbors of point \(x_{i}\) can construct a set \(N(x_{i})\) and point \(x_{j}\) can construct a set \(N(x_{j})\), then the shared neighbor vertexes between \(x_{i}\) and \(x_{j}\) are defined as Equation (3).  
\[SNN\,(x_{i},x_{j})=\left|N(x_{i})\cap N(x_{j})\right| \tag{3}\]  
[PERSON] _et al._ assumed that vertexes in the same manifold have a higher similarity and a higher local density region than those in different manifolds. They used the number of the shared nearest neighbors to characterize the similarity between vertex \(x_{i}\) and \(x_{j}\)[15]. The construct similarity function is defined as Equation (4).  
\[SNN_{ij}=\left\{\begin{array}{cl}\exp(-\,d\,(i,j)^{2}\,\big{/}(\sigma_{i} \sigma_{j}\,(SNN(x_{i},x_{j})+1)))&i\
eq j\\ 1&i=j\end{array}\right. \tag{4}\]  
According to this method, the similarity between two vertexes is higher if there are more common shared nearest neighbors. Due to the non-homogeneity of the network topology, the importance of eachnode in the network is different, and the similarity of two vertices relates to not only the number of neighbors shared, but also closely to the importance of the shared neighbor vertices.