Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm
This addresses a specific bottleneck in spectral clustering for researchers and practitioners by providing a more principled discretization method, though it is incremental as it builds on existing spectral clustering frameworks.
The paper tackles the problem of discretizing relaxed solutions in spectral clustering, which existing methods do by ignoring the original objective, and proposes a non-heuristic algorithm that bridges the original problem and discretization, achieving more reliable solutions with preferable loss values as shown in experiments.
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.