# A Spectral Clustering Algorithm for Non-Linear Graph Embedding in Information Networks
## 2 Related Work  
### Spectral Clustering  
Spectral clustering is an algorithm derived from graph theory and has been widely utilized in clustering. The primary aim is to represent all nodes using a Laplacian matrix. In this matrix, the edge weights between nodes that are far apart are lower; in contrast, those that are closer are higher. The Laplacian matrix is then subjected to eigenvalue decomposition to identify its k-smallest eigenvalues, which are utilized to derive a reduced-dimension representation of the network. Finally, the K-means algorithm is employed for clustering. The process is illustrated in Figure 1.  
There are three methods for constructing the similarity graph in the Laplacian matrix: the adjacency method, the KNN method, and the fully connected method. The adjacency method sets a distance threshold and then measures the similarity between any two nodes using the Euclidean distance. The KNN algorithm traverses all sample points, selecting the nearest k points as neighbors for each sample in order to calculate their similarity. The fully connected method calculates the similarity values between all points.  
The objective of spectral clustering is to partition the graph into k-disconnected subgraphs while minimizing the graph cut. The normalized cut criterion [19] is defined as follows:  
Definition 1: (Normalized Cut Criterion)  
\[Normalized-Cut(C_{1},C_{2},\ldots,C_{k})=\sum\limits_{i=1}^{k}\frac{cut(C_{i}, \overline{C_{i}})}{vol(C_{i})}, \tag{1}\]  
where \(vol(C_{i})=\sum\limits_{v\in C_{i}}d_{v},C_{i}\cap C_{j}=\Phi,\cup_{i=1}^{k}C_{ i}=V\), \(\overline{C_{i}}\) denotes the complement of \(C_{i}\) and \(cut(C_{i},\overline{C_{i}})\) represents the number of connections between the two subgraphs \(C_{i}\) and \(\overline{C_{i}}\).  
Figure 1: Structural diagram of the spectral clustering algorithm.  
Solving the normalized cut set is an NP-hard problem; according to _Normalized_--\(Cut(C_{1},C_{2},\ldots,C_{k})=\sum_{i=1}^{k}h_{i}^{T}Lh_{i}=\sum_{i=1}^{k}(H^{T}LH)_ {ii}=tr(H^{T}LH)\), its approximation can be described as a trace function minimization Formula (2).  
\[\operatorname*{arg\,min}_{H}tr(H^{T}LH)\,s.t.\,H^{T}DH=I, \tag{2}\]  
where \(L=D-S\), \(D=diag(d_{1},d_{2},\ldots,d_{n})\), and properties of the Laplacian matrix L are as follows:  
* L is a symmetric and positive semi-definite matrix;
* The number of graph connections equals the number of eigenvalues equal to zero, i.e., Rank(L) = \(n-k\);
* For vector \(f\in R^{n}\), there is \(f^{T}Lh=\frac{1}{2}\sum\limits_{i,j=1}^{n}S_{ij}(f_{i}-f_{j})^{2}\).  
This objective function calculates the eigenvectors of the matrix L. According to the matrix computation Theorem 1, H is composed of the eigenvectors corresponding to the k-smallest non-negative singular values of the normalized Laplacian matrix. The final clustering result is obtained by running the K-means algorithm on the graph's embedding matrix H.  
**Theorem 1**.: _(Eckart-Young-Mirsky Theorem) Given an r-rank matrix \(P\), its SVD: \(P=V\Sigma U^{T}\), where \(V^{T}V=I\), \(U^{T}U=I\) and then_  
\[\operatorname*{arg\,min}_{rank(\overrightarrow{P})=k}||P- \overrightarrow{P}||_{F}=V\overrightarrow{\Sigma}U^{T}, \tag{3}\]  
_where \(\overrightarrow{\Sigma}\); besides only containing the k largest singular values and replacing other singular values with 0, the rest remains the same as the matrix \(\Sigma\). This theorem indicates that reconstructing the matrix using the k largest singular vectors from singular value decomposition provides the best rank-k approximation of the original matrix._  
The effectiveness of spectral clustering depends on the similarity matrix, making it very effective for clustering sparse data, a task that is challenging for the K-means algorithm. Moreover, due to the utilization of dimensionality reduction techniques, spectral clustering handles the complexity of high-dimensional clustering more effectively than traditional clustering methods such as K-means.