# A Spectral Clustering Algorithm for Non-Linear Graph Embedding in Information Networks
###### Abstract  
With the development of network technology, information networks have become one of the most important means for people to understand society. As the scale of information networks expands, the construction of network graphs and high-dimensional feature representation will become major factors affecting the performance of spectral clustering algorithms. To address this issue, in this paper, we propose a spectral clustering algorithm based on similarity graphs and non-linear deep embedding, named \(SEG\_SC\). This algorithm introduces a new spectral clustering model that explores the underlying structure of graphs through sparse similarity graphs and deep graph representation learning, thereby enhancing graph clustering performance. Experimental analysis with multiple types of real datasets shows that the performance of this model surpasses several advanced benchmark algorithms and performs well in clustering on medium- to large-scale information networks. information networks; spectral clustering; deep embedding +
Footnote †: journal: Applied Sciences  
0000-0001-9993-3899-389  
The k-nearest neighbor (KNN) graph is a manifold graph construction learning method, which includes methods such as Isomap [7] and local linear embedding [8]. This particular model has good generalization capabilities and can map topological manifolds. If high-dimensional manifolds are embedded in low-dimensional manifold spaces, the properties of Euclidean space still exist locally. The KNN algorithm is known for its stability, simplicity, and efficiency. However, it presents limitations when handling large datasets or high-dimensional data, which can result in increased computational complexity and limited clustering results. In recent years, considering nearest neighbor search methods, [PERSON] et al. [1; 3; 9] improved the KNN graph by introducing a KNN graph clustering algorithm that utilizes representative points. These representative points represent each cluster during computation, and noise has minimal influence on this approach. Moreover, for KNN graph construction, the representative point graph has been applied in spectral clustering. By computing a low-rank approximation of the affinity tensor graph, the initial unified affinity matrix is refined with reliable information from the confidence affinity matrix. For low-dimensional vector representation, there are many effective methods available. Most models [10; 11] that learn graph construction first use linear encoding and then apply singular value decomposition (SVD) [12] for linear dimension reduction. Linear encoding [6; 13] produces sparse representation, where each data point is represented as a linear representation of a small number of base vectors. Mathematically, linear encoding is defined as finding two matrices U and Z, whose product can best approximate the data \(X\approx UZ\). Large-scale sparse coding clustering (LSC) [9] combines linear encoding, SVD, and K-means into a spectral clustering method. It has a solid theoretical basis and has contributed to significant advancements in clustering research on large-scale data. GraRep [14] is a novel model designed for learning weighted graph vertex representations by generating low-dimensional vectors to represent graphs. However, these methods all involve the use of SVD for linear dimension reduction, and more effective non-linear dimension reduction techniques have yet to be explored. In recent years, deep learning [4; 15] has been widely applied in graph representation learning. Implementing a greedy layer training strategy can improve computational performance. Stacked autoencoders [16] are considered an effective method for mapping from the original representation space to low-dimensional spaces, with the capability to produce highly non-linear projections. More recently, sparse autoencoders have been used to replace the SVD step in spectral clustering. [PERSON] et al. [17] proposed a deep architecture called DLC for fast graph clustering with linear encoders.