A survey on graph partitioning approach to spectral clustering

Abstract

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.