Semi-Supervised Spectral Clustering using the Signed Laplacian

Abstract

Data clustering is an important step in numerous real-world problems. The goal is to separate the data into disjoint subgroups (clusters) according to some similarity metric. We consider spectral clustering (SC), where a graph captures the relation between the individual data points and the clusters are obtained from the spectrum of the associated graph Laplacian. We propose a semi-supervised SC scheme that exploits partial knowledge of the true cluster labels. These labels are used to create a modified graph with attractive intra-cluster edges (positive weights) and repulsive inter-cluster edges (negative weights). We then perform spectral clustering using the signed Laplacian matrix of the resulting signed graph. Numerical experiments illustrate the performance improvements achievable with our method.