Scalable Graph Discrete Reconstruction for Efficient Multi-View Clustering

Multi-view clustering (MVC) with bipartite graph has been extensively studied to rapidly handle multi-source heterogeneous information via sparse anchors. However, most existing methods follow a two-stage learning paradigm that first learns continuous label matrix and then discretizes it, not only bringing extra trade-off parameters but yielding suboptimal solutions. Also, numerous methods still exhibit limited scalability for large-scale problems. Thus, this paper proposes two novel models for discrete, trade-off parameter-free and rapid MVC. First, the Bipartite Graph Discrete Reconstruction (BGDR) model uniquely leverages the discrete label matrices of both samples and anchors to dynamically reconstruct a consensus bipartite graph across views. This concise reconstruction style eliminates redundant computations, and anchor labels enable to enrich cluster partition information during reconstruction, enhancing both accuracy and efficiency. The final clustering outcomes are directly acquired via discrete sample labels. Second, to free the optimization time overheads from the limitation of sample size, we further devise the Compact Graph Discrete Reconstruction (CGDR) model, which reconstructs a smaller compact affinity graph among anchors for significant acceleration. Original sample labels are then gained by label propagation. Systematic experiments illuminate that both models reach superior outcomes in term of efficacy and efficiency.