One-Step Pairwise Constrained Multi-View Clustering in Linear Time

Pairwise constrained clustering, which employs the pairwise constraints to boost clustering performance, has been widely used in many applications such as face clustering and image retrieval. Due to the prevalence of multi-view data, pairwise constrained multi-view clustering has attracted increasing attention. Nevertheless, existing methods suffer from at least one of the three issues, i.e., expensive time consumption, two-stage clustering and inadequate use of pairwise constraints. To address the above issues, this paper proposes a Pairwise Constrained Bipartite Graph (PCBG) learning method for efficient one-step pairwise constrained multi-view clustering. Concretely, to encode must-link constraints, a novel comprehensive bipartite graph is elegantly designed. Meanwhile, a cannot-link regularization is derived and imposed on the comprehensive bipartite graph, which enforces cannot-link constraints to be realized with theoretically provable guarantees. Moreover, the comprehensive bipartite graph is constrained to exhibit explicit clustering partition by its connected components. Then, an efficient and convergent algorithm with theoretically proved accelerating techniques is derived for optimization, which has linear time complexity to the sample size. Extensive experimental results demonstrate the advantages of PCBG in both clustering performance and time complexity compared with state-of-the-art baselines.