A Greedy Strategy for Graph Cut.

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• Graph partitioning is a fundamental problem in computer science with applications in various fields.
• Existing algorithms often suffer from sensitivity to random initialization, leading to inconsistent results.
• Efficient and deterministic graph partitioning methods are needed for large-scale data analysis.

Purpose of the Study:

• To propose a novel Greedy Graph Cut (GGC) algorithm for graph partitioning.
• To ensure deterministic and computationally efficient graph partitioning.
• To demonstrate the effectiveness of GGC on the Normalized Cut (N-Cut) problem.

Main Methods:

• The Greedy Graph Cut (GGC) algorithm iteratively merges clusters to minimize a global objective function.
• Merging operations are restricted to adjacent clusters for improved computational efficiency.
• Theoretical proof of monotonic convergence of the objective function is provided.

Main Results:

• GGC demonstrates deterministic convergence, ensuring consistent results across multiple runs.
• The algorithm exhibits near-linear scaling of computational complexity with sample size.
• GGC consistently outperforms the conventional eigendecomposition followed by k-means clustering approach for N-Cut.
• Comparative analyses show GGC surpasses several state-of-the-art clustering algorithms.

Conclusions:

• The proposed Greedy Graph Cut (GGC) algorithm offers an effective and efficient solution for graph partitioning.
• GGC provides a deterministic alternative to existing methods, ensuring reliable results.
• GGC shows superior performance in solving the Normalized Cut (N-Cut) problem compared to established techniques.