Discretize Relaxed Solution of Spectral Clustering via a Nonheuristic Algorithm

Area of Science:

• Machine Learning
• Graph Theory
• Optimization Algorithms

Background:

• Spectral clustering typically involves graph construction and solution relaxation, followed by heuristic discretization.
• Existing discretization methods like k-means (KM) and spectral rotation (SR) do not optimize the original objective function, leading to suboptimal solutions.

Purpose of the Study:

• To develop a non-heuristic method for spectral clustering discretization that directly optimizes the original objective.
• To improve the reliability and performance of discrete solutions in spectral clustering.

Main Methods:

• Introduced a novel first-order term inspired by optimization algorithms to bridge the original problem and discretization.
• Developed a non-heuristic approach that considers the original graph cut problem during discretization.

Main Results:

• The proposed non-heuristic method yields more reliable discrete solutions with preferable loss values.
• Theoretical analysis confirms the benefit of the continuous optimum for discretization algorithms.
• Experimental results demonstrate the superiority of the proposed method over existing heuristic techniques.

Conclusions:

• The novel first-order term provides a theoretically sound and practically effective approach to spectral clustering discretization.
• This non-heuristic method enhances solution quality and reliability compared to traditional heuristic algorithms.