A Model-Based Approach to Rounding in Spectral Clustering
  In spectral clustering, one defines a similarity matrix for a collection of
data points, transforms the matrix to get the Laplacian matrix, finds the
eigenvectors of the Laplacian matrix, and obtains a partition of the data using
the leading eigenvectors. The last step is sometimes referred to as rounding,
where one needs to decide how many leading eigenvectors to use, to determine
the number of clusters, and to partition the data points. In this paper, we
propose a novel method for rounding. The method differs from previous methods
in three ways. First, we relax the assumption that the number of clusters
equals the number of eigenvectors used. Second, when deciding the number of
leading eigenvectors to use, we not only rely on information contained in the
leading eigenvectors themselves, but also use subsequent eigenvectors. Third,
our method is model-based and solves all the three subproblems of rounding
using a class of graphical models called latent tree models. We evaluate our
method on both synthetic and real-world data. The results show that our method
works correctly in the ideal case where between-clusters similarity is 0, and
degrades gracefully as one moves away from the ideal case.
