ESIMCE: Efficient and simple incomplete multi-view clustering via ensembles

Despite recent advances, previous incomplete multi-view clustering (IMVC) methods still suffer from four critical limitations. (1) They often exhibit high computational complexity, limiting their applicability to large-scale problems. (2) They frequently struggle with intractable hyper-parameter tuning. (3) They generally fail to leverage the complementarity of multi-view data for imputing missing information. (4) They typically perform information fusion at an early stage (e.g., through graph fusion), which may lead to early information loss and overlook the potential for higher-level fusion. To address these challenges, we propose an efficient and robust IMVC method, termed Efficient and Simple Incomplete Multi-view Clustering via Ensembles (ESIMCE). ESIMCE achieves almost linear time complexity without dataset-specific parameter tuning, recovers missing information by exploiting cross-view consistency, and performs information integration at the partition-level. Specifically, we first construct multiple partial bipartite (anchor) graphs for incomplete views using a shared anchor set, and recover missing entries by leveraging complementary information across views. The recovered graphs are further sparsified via K-nearest anchors to enhance reliable connections. Then, each graph is independently partitioned, leading to multiple base clusterings that capture diverse high-level clustering structures. Finally, inspired by ensemble clustering, these base clusterings are fused at the partition-level through a unified bipartite graph, which is efficiently partitioned to obtain the final clustering result. Extensive experiments on real-world multi-view datasets demonstrate the robustness and efficiency of the proposed method.