A Novel Normalized-Cut Solver With Nearest Neighbor Hierarchical Initialization.

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• Spectral clustering methods like Normalized-Cut (N-Cut) are widely used.
• Traditional N-Cut solvers involve two stages: spectral embedding and discretization.
• Existing methods suffer from solving a relaxed problem and high computational complexity (O(n³)).

Purpose of the Study:

• To develop a novel N-Cut solver addressing limitations of traditional methods.
• To improve the accuracy and efficiency of spectral clustering.
• To provide a deterministic initialization for clustering.

Main Methods:

• A novel N-Cut solver based on the coordinate descent method is proposed.
• Accelerating strategies are employed to reduce time complexity to O(|E|).
• An efficient, deterministic initialization method is introduced to avoid random initialization issues.

Main Results:

• The proposed solver achieves significantly improved N-Cut objective values.
• Experimental results show superior clustering performance compared to traditional solvers.
• The computational complexity is reduced to O(|E|), enhancing efficiency.

Conclusions:

• The novel coordinate descent-based N-Cut solver offers a more accurate and efficient alternative.
• The method overcomes the limitations of two-stage solvers and eigenvalue decomposition.
• Deterministic initialization ensures reliable and reproducible clustering outcomes.