Discretize Relaxed Solution of Spectral Clustering via a Nonheuristic Algorithm

Spectral clustering and its extensions usually consist of two steps: 1) constructing a graph and computing the relaxed solution and 2) discretizing relaxed solutions. Although the former has been extensively investigated, the discretization techniques are mainly heuristic methods, e.g.,
$k$
-means (KM), spectral rotation (SR). Unfortunately, the goal of the existing methods is not to find a discrete solution that minimizes the original objective. In other words, the primary drawback is the neglect of the original objective when computing the discrete solution. Inspired by the first-order optimization algorithms, we propose to develop a first-order term to bridge the original problem and discretization algorithm, which is the first nonheuristic to the best of our knowledge. Since the nonheuristic method is aware of the original graph cut problem, the final discrete solution is more reliable and achieves the preferable loss value. We also theoretically show that the continuous optimum is beneficial to discretization algorithms though simply finding its closest discrete solution is an existing heuristic algorithm which is also unreliable. Sufficient experiments significantly show the superiority of our method.