Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic
  Algorithm
Hongyuan Zhang Xuelong Li
Spectral clustering and its extensions usually consist of two steps: (1)
constructing a graph and computing the relaxed solution; (2) discretizing
relaxed solutions. Although the former has been extensively investigated, the
discretization techniques are mainly heuristic methods, e.g., k-means, spectral
rotation. 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 non-heuristic to the best of our
knowledge. Since the non-heuristic 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.