New approach for learning structured graph with Laplacian rank constraint

Many existing graph-clustering methods get results in a two-stage manner, including constructing a graph from data and partitioning it. It always leads to sub-optimal performances. To address the drawbacks, imposing rank constraint on the graph's Laplacian matrix is an effective way. It can learn a structured graph that connected components are exactly equal to the cluster numbers. According to separate connected components, it directly obtains clustering assignments. However, previous works heuristically solve it during the optimization without any theory guarantee. To handle this issue, we propose a novel solver to optimize this problem with theoretical advantages, enabling the structured bipartite graphs to directly indicate clustering results. Initially, we discover that pairwise and bipartite graphs exhibit the same connected components after undergoing a specific operation. Then, we derive an efficient algorithm to optimize two different clustering models with rank constraints based on this property. Moreover, our proposed method exhibits linear computational complexity to the data scale. Extensive empirical results on both synthetic and real benchmark data demonstrate that the proposed method outperforms existing methods.