Cross-View Graph Matching for Unsupervised Learning With Unaligned Multi-View Clustering

Multi-view clustering (MVC) leverages complementary information across heterogeneous views to improve unsupervised partitioning. Nevertheless, the majority of existing MVC methods critically assume that samples are fully aligned across views, an assumption frequently violated in practice when multi-view data are collected from independent sources without any correspondence. This gives rise to Completely Unaligned multi-view Clustering (CUC), where cross-view sample correspondences are entirely unknown, fundamentally impeding effective multi-view fusion. Prior CUC-oriented methods typically infer inter-view relations from distance/similarity matrices; however, severe cross-view heterogeneity often induces over-smoothing in such matrices, leading to unreliable matching signals and degraded clustering performance. To address these issues, we propose Cross-view Graph Matching for Completely Unaligned multi-view Clustering (CGM-CUC), a unified framework that couples structure-aware representation learning with progressive cross-view alignment. Specifically, CGM-CUC introduces a bipartite graph-based sample re-encoding mechanism to enhance discriminative structural cues, and an iterative cross-view matching network that progressively refines permutation matrices to recover latent correspondences. Moreover, we develop an alignment-guided optimization strategy that mitigates the over-smoothing effect in similarity estimation, thereby stabilizing the matching process and improving downstream clustering. Extensive experiments on multiple benchmark datasets demonstrate that CGM-CUC consistently achieves superior performance over state-of-the-art baselines, with particularly notable gains under fully unaligned view settings.