Scalable Graph-Based Clustering for Unaligned Multi-View Data

In most existing multi-view clustering scenarios, samples of the same object across views are typically assumed to be strictly aligned, forming a key prerequisite for cross-view consistency. In practice, however, view-wise data acquisition and processing are often independent, making the View-unaligned Problem (VuP) ubiquitous and non-negligible. Several pioneering methods have been proposed to address VuP, but their computational efficiency remains a major bottleneck in large-scale applications. Therefore, there is an urgent need for more efficient solutions to the VuP in multi-view clustering. Motivated by this bottleneck, we propose an efficient solution to the VuP in multi-view clustering, termed Scalable Graph-Based Clustering for Unaligned Multi-View Data (SGCU). Specifically, SGCU aligns samples across views via sample permutation and learns a cross-view consensus bipartite graph: it models the sample permutation matrix of each view as an entropy-regularized optimal transport (OT) plan and incorporates a Probabilistic Sparse Sinkhorn solver for efficient optimization. This solver maintains an unbiased approximation to the full solution while reducing the sample alignment complexity to near-linear in sample size. Moreover, the proposed SGCU model can be seamlessly integrated into existing VuP-oriented clustering frameworks to enhance computational efficiency. Extensive experiments on multiple real-world datasets demonstrate its effectiveness, efficiency, and robustness.