Effective Clustering via Structured Graph Learning

Given an affinity graph of data samples, graph-based clustering aims to partition these samples into disjoint groups based on the affinities, and most previous works are based on spectral clustering. However, two problems among spectral-based methods heavily affect the clustering performance. First, the randomness of post-processing procedures, such as $K$K-means, affects the stability of clustering. Second, the separated stages of spectral-based methods, including graph construction, spectral embedding learning, and clustering decision, lead to mismatched problems. In this paper, we explore a structured graph learning (SGL) framework that aims to fuse these stages to improve clustering stability. Specifically, SGL adaptively learns a structured affinity graph that contains exact $k$k connected components. Each connected component corresponds to a cluster so clustering assignments can be directly obtained according to the connectivity of the learned graph. In this way, SGL avoids the randomness brought by reliance on traditional post-processing procedures. Meanwhile, the graph construction and structured graph learning procedures happen simultaneously, which alleviates the mismatched problem effectively. Moreover, we propose an efficient algorithm to solve the involved optimization problems and discuss the connections between this work and previous works. Numerical experiments on several synthetic and real datasets demonstrate the effectiveness of our methods.