Graph structure enhancement with local cluster guidance for discrete spectral clustering

Spectral clustering (SC), as the most popular graph clustering algorithm, is widely used in data mining due to its ability to effectively capture complex cluster structures. However, most graph-based clustering methods overlook the integration of prior information, which, although challenging to acquire in unsupervised scenarios, has the potential to enhance clustering accuracy by aligning results more closely with the ground truth. Moreover, existing SC methods usually require an additional discretization step to generate a discrete label matrix, leading to information loss. To overcome these challenges, a unified self-supervised graph clustering model called Graph Structure Enhancement with Local Cluster Guidance for Discrete Spectral Clustering (LCG-DSC) is proposed. In particular, the proposed method is characterized by the following advancements: 1) an innovative self-supervised term is used to extend the loss function of spectral clustering; 2) a novel optimization method, which alternately iterates singular value decomposition and coordinate ascent, is employed to combine spectral embedding analysis and label matrix learning into a unified framework, avoiding the information loss. Furthermore, a theoretical analysis is provided to show the roles of the self-supervised term and the extensibility of the proposed algorithm. Experimental clustering results demonstrate that LCG-DSC exhibits good effectiveness on both synthetic and real-world datasets.