A Greedy Strategy for Graph Cut

We propose a novel Greedy Graph Cut (GGC) algorithm to address the graph partitioning problem. The algorithm begins by treating each data point as an individual cluster and iteratively merges cluster pairs that maximize the reduction in the global objective function until the desired number of clusters is achieved. We provide a theoretical proof of the monotonic convergence of the objective function values throughout this process. To improve computational efficiency, the algorithm restricts merging operations to adjacent clusters, resulting in a computational complexity that scales nearly linearly with the sample size. A significant advantage of our greedy approach is its deterministic nature, which ensures consistent results across multiple runs. This stands in contrast to many existing algorithms that are sensitive to random initialization effects. We demonstrate the effectiveness of the proposed algorithm by applying it to the Normalized Cut (N-Cut) problem, a well-studied variant of graph partitioning. Extensive experimental results show that GGC consistently outperforms the conventional two-stage optimization approach—which involves eigendecomposition followed by k-means clustering—in solving the N-Cut problem. Furthermore, comparative analyses reveal that GGC achieves superior performance compared to several state-of-the-art clustering algorithms.