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.

Although lots of clustering models have been proposed recently, k-means and the family of spectral clustering methods are both still drawing a lot of attention due to their simplicity and efficacy. We first reviewed the unified framework of k-means and graph cut models, and then proposed a clustering method called k-sums where a k-nearest neighbor ( k-NN) graph is adopted. The main idea of k-sums is to minimize directly the sum of the distances between points in the same cluster. To deal with the situation where the graph is unavailable, we proposed k-sums-x that takes features as input. The computational and memory overhead of k-sums are both O(nk), indicating that it can scale linearly w.r.t. the number of objects to group. Moreover, the costs of computational and memory are Irrelevant to the product of the number of points and clusters. The computational and memory complexity of k-sums-x are both linear w.r.t. the number of points. To validate the advantage of k-sums and k-sums-x on facial datasets, extensive experiments have been conducted on 10 synthetic datasets and 17 benchmark datasets. While having a low time complexity, the performance of k-sums is comparable with several state-of-the-art clustering methods.

Most spectral clustering algorithms obtain firstly the embedding based on the similarity matrix of the input data and then discretize the embedding to get the final clustering result. So, their performance is greatly affected by the noise of the similarity matrix, and the two-step strategy may lead to a suboptimal result. In this article, a novel Rank-Constrained clustering algorithm with Adaptive Embedding called RCAE is proposed, where the spectral embedding and the clustering structure are learned simultaneously, so, the influence of noise on performance is greatly reduced. In addition, a rank constraint is adopted in our model, thus, the connectivity matrix with exactly c (the number of clusters to construct) connected components can be learned, therefore, the final clustering result can be obtained according to the connected components. Experiments on several benchmark datasets validate the superiority of the proposed methods, compared to the several state-of-the-art clustering algorithms [GitHub].

How to effectively cluster large-scale image data sets is a challenge and is receiving more and more attention. To address this problem, a novel clustering method called fast clustering with co-clustering via discrete non-negative matrix factorization, is proposed. Inspired by co-clustering, our algorithm reduces computational complexity by transforming clustering tasks into co-clustering tasks. Although our model has the same form of objective function as normalized cut, we relax it to a matrix decomposition problem, which is different from most graph-based approaches. In addition, an efficient optimization algorithm is proposed to solve the relaxed problem, where a discrete solution corresponding to the clustering result can be directly obtained. Extensive experiments have been conducted on several synthetic data sets and real word data sets. Compared with the state-of-the-art clustering methods, the proposed algorithm achieves very promising performance.

Spectral clustering and $k$-means, both as two major traditional clustering methods, are still attracting a lot of attention, although a variety of novel clustering algorithms have been proposed in recent years. Firstly, a unified framework of $k$-means and ratio-cut is revisited, and a novel and efficient clustering algorithm is then proposed based on this framework. The time and space complexity of our method are both linear with respect to the number of samples, and are independent of the number of clusters to construct, more importantly. These properties mean that it is easily scalable and applicable to large practical problems. Extensive experiments on 12 real-world benchmark and 8 facial datasets validate the advantages of the proposed algorithms compared to the state-of-the-art clustering algorithms. In particular, over 15x and 7x speed-up can be obtained with respect to $k$-means on the synthetic dataset of 1 million samples and the benchmark dataset (CelebA) of 200k samples, respectively [GitHub].