Graph-Based Clustering via Group Sparsity and Manifold Regularization

Abstract

Clustering refers to the problem of partitioning data into several groups according to the predefined criterion. Graph-based method is one of main clustering approaches and has been shown impressive performance in many literatures. The core issue of graph-based clustering is how to construct a good adjacency graph. A large number of works employ the sparse representation of data as the similarity measure by ℓ1 regularization. However, due to the flat nature of the ℓ1 norm, such methods solve the sparse representation of each data point individually, which do not take into account the global structure of data. To exploit the global and essential structure in data, in contrast to existing methods, we propose to learn a graph with group sparsity. To incorporate more information into the graph, we also use the manifold regularization with adaptive similarity during the process of group sparse self-representation. The resulting model is handled by Alternating Direction Method of Multipliers (ADMM). Further, we employ Iterative Re-weighted Least Squares (IRLS) algorithm and threshold operator to solve the ADMM subproblems. Experimental results on real-world datasets demonstrate the superiority of our method compared to the competing clustering methods.

Keywords

• Clustering
• graph
• group sparsity