ABSTRACT
This chapter introduces the definitions for different formulations of graph Laplacians and specific procedures for several kinds of spectral clustering algorithms. It analyzes the spectrum of both unnormalized and normalized Laplacian matrices. The word spectral is used to denote the fact that the clustering results are obtained by analyzing the spectrum of the graph Laplacian. The Laplacian eigenmap algorithm is a very successful method for dimensionality reduction and is closely related to spectral clustering. One of the most popular dimensionality reduction algorithms is Principal Component Analysis which gives the solution by projecting the original high-dimensional data onto the low-dimensional linear subspace spanned by the leading eigenvectors of the data’s covariance matrix. The basic idea of Laplacian eigenmap is also based on spectral graph theory. The general spectral clustering method needs to construct an adjacency matrix and calculate the eigen-decomposition of the corresponding Laplacian matrix.
