EGGS: Eigen-Gap Guided Search For Automated Spectral Clustering
  The performance of spectral clustering heavily relies on the quality of
affinity matrix. A variety of affinity-matrix-construction (AMC) methods have
been proposed but they have hyperparameters to determine beforehand, which
requires strong experience and lead to difficulty in real applications
especially when the inter-cluster similarity is high or/and the dataset is
large. In addition, we often need to choose different AMC methods for different
datasets, which still depends on experience. To solve these two challenging
problems, in this paper, we present a simple yet effective method for automated
spectral clustering. The main idea is to find the most reliable affinity matrix
among a set of candidates given by different AMC methods with different
hyperparameters, where the reliability is quantified by the
\textit{relative-eigen-gap} of graph Laplacian introduced in this paper. We
also implement the method using Bayesian optimization.We extend the method to
large-scale datasets such as MNIST, on which the time cost is less than 90s and
the clustering accuracy is state-of-the-art. Extensive experiments of natural
image clustering show that our method is more versatile, accurate, and
efficient than baseline methods.
