Such cost functions are often NP-hard [1]}, [2]}, [3]}. However, the respective optimal solution can be approximated in some way. A category of methods work based on eigenvector analysis of the Laplacian matrix. Spectral Clustering [4]}, [5]} was the first method which exploits the information from eigenvectors. It forms a low-dimensional embedding by the bottom eigenvectors of the Laplacian of the similarity matrix and then applies \(K\) -means to produce the final clusters. A more recent method, called Power Iteration Clustering (PIC) [6]}, instead of embedding the data into a \(K\) -dimensional space, approximates an eigenvalue-weighted linear combination of all the eigenvectors of the normalized similarity matrix via early stopping of the power iteration method. P-Spectral Clustering (PSC) [7]} is another spectral approach that proposes a non-linear generalization of the Laplacian and then performs an iterative splitting method based on its second eigenvector.
