Multiway p-spectral graph cuts on Grassmann manifolds

Area of Science:

• Machine Learning
• Graph Theory
• Numerical Analysis

Background:

• Spectral clustering methods are popular for data partitioning.
• Nonlinear reformulations offer improved numerical benefits and mathematical rigor.
• Existing methods may lack efficiency or robustness in multiway partitioning.

Purpose of the Study:

• To develop a novel direct multiway spectral clustering algorithm.
• To leverage the p-Laplacian for enhanced graph partitioning.
• To achieve sparser solutions and optimal graph cuts.

Main Methods:

• Recasting eigenvector computation for the graph p-Laplacian as a Grassmann manifold minimization problem.
• Employing a pseudocontinuous reduction of 'p' to promote sparsity.
• Monitoring balanced graph cut decrease for solution quality.

Main Results:

• Demonstrated effectiveness and accuracy on artificial datasets.
• Achieved high-quality clusters using balanced graph cut metrics.
• Showcased superior performance compared to state-of-the-art methods in labelling accuracy.
• Validated applicability on real-world facial image and handwritten character classification.

Conclusions:

• The proposed nonlinear spectral clustering algorithm offers significant improvements in efficiency and accuracy.
• The method effectively handles multiway graph partitioning and real-world classification tasks.
• The p-Laplacian approach provides a robust framework for advanced clustering.