A survey on graph partitioning approach to spectral clustering

Cluster analysis is an unsupervised technique of grouping related objects without considering their label or class. The objects belonging to the same cluster are relatively more homogeneous in comparison with other clusters. The application of cluster analysis is in areas like gene expression analysis, galaxy formation, natural language processing and image segmentation etc. The clustering problem can be formulated as a graph cut problem where a suitable objective function has to be optimized. This study uses different graph cluster formulations based on graph cut and partitioning problems. A special class of graph clustering algorithm known as spectral clustering algorithms is used for the study. Two widely used spectral clustering algorithms are applied to explaining solution to these problems. These algorithms are generally based on the Eigen-decomposition of Laplacian matrices of either weighted or non-weighted graphs.