Structure sparsity-induced bipartite graph learning for multi-view clustering

Abstract

Bipartite graph-based multi-view clustering conducts clustering of samples in accordance with the relationships between samples and anchors, and has demonstrated significant advancements in recent years. Predefined bipartite graphs with fixed anchors may not reflect the underlying clustering structure accurately, leading to the degradation of clustering performance. To address this problem, we propose a Structure Sparsity-Induced Bipartite Graph (SSBG) learning method to dynamically construct view-specific bipartite graphs with automatically learned anchors. Concretely, representative anchors of each view are learned by integrating key samples selected by introducing a selection matrix with structure sparsity. Meanwhile, the feature matrix of each view is reconstructed by the learned anchors and the corresponding bipartite graph in a self-representation manner. Due to the representativeness of the anchors and the advantages of the self-representation model in representing complex relationships, the consistent bipartite graph fused from multiple views possesses enhanced ability to represent the underlying clustering structure. A converged iterating algorithm is developed to optimize for the objective function, and the final clustering partition can be directly obtained according to the connected components of the fused consistent bipartite graph. Extensive experimental results demonstrate the advantages of SSBG in clustering performance across various benchmark datasets.

Graphical abstract

Keywords

multi-view clustering / adaptive anchor construction / structure sparsity / bipartite graph learning

References

[1] Yang Y, Wang H . Multi-view clustering: a survey. Big Data Mining and Analytics, 2018, 1( 2): 83–107

[2] Tao H, Hou C, Qian Y, Zhu J, Yi D . Latent complete row space recovery for multi-view subspace clustering. IEEE Transactions on Image Processing, 2020, 29: 8083–8096

[3] Liu J, Wang C, Gao J, Han J. Multi-view clustering via joint nonnegative matrix factorization. In: Proceedings of the 2013 SIAM International Conference on Data Mining. 2013, 252−260

[4] Zhang C, Fu H, Hu Q, Cao X, Xie Y, Tao D, Xu D . Generalized latent multi-view subspace clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 42( 1): 86–99

[5] Kloft M, Blanchard G. The local rademacher complexity of Lp-norm multiple kernel learning. In: Proceedings of the 25th Annual Conference on Neural Information Processing. 2011, 2438−2446

[6] Liu X . SimpleMKKM: simple multiple kernel k-means. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45( 4): 5174–5186

[7] Cai X, Huang D, Zhang G Y, Wang C D . Seeking commonness and inconsistencies: a jointly smoothed approach to multi-view subspace clustering. Information Fusion, 2023, 91: 364–375

[8] Qin Y, Tang Z, Wu H, Feng G . Flexible tensor learning for multi-view clustering with Markov chain. IEEE Transactions on Knowledge and Data Engineering, 2024, 36( 4): 1552–1565

[9] Wan X, Liu J, Gan X, Liu X, Wang S, Wen Y, Wan T, Zhu E . One-step multi-view clustering with diverse representation. IEEE Transactions on Neural Networks and Learning Systems, 2025, 36( 3): 5774–5786

[10] Tao H, Hou C, Zhu J, Yi D. Multi-view clustering with adaptively learned graph. In: Proceedings of the 9th Asian Conference on Machine Learning. 2017, 113−128

[11] Nie F, Cai G, Li X. Multi-view clustering and semi-supervised classification with adaptive neighbours. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence. 2017, 2408−2414

[12] Kang Z, Lu X, Yi J, Xu Z. Self-weighted multiple kernel learning for graph-based clustering and semi-supervised classification. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. 2018, 2312−2318

[13] Li Y, Nie F, Huang H, Huang J. Large-scale multi-view spectral clustering via bipartite graph. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015

[14] Qiang Q, Zhang B, Wang F, Nie F. Fast multi-view discrete clustering with anchor graphs. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021, 9360−9367

[15] Kang Z, Zhou W, Zhao Z, Shao J, Han M, Xu Z. Large-scale multi-view subspace clustering in linear time. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020

[16] Yang B, Zhang X, Nie F, Wang F, Yu W, Wang R . Fast multi-view clustering via nonnegative and orthogonal factorization. IEEE Transactions on Image Processing, 2021, 30: 2575–2586

[17] Zhao K, Lin Z, Zhu X, Xu W . Structured graph learning for scalable subspace clustering: from single view to multiview. IEEE Transactions on Cybernetics, 2022, 52( 9): 8976–8986

[18] Li X, Zhang H, Wang R, Nie F . Multiview clustering: a scalable and parameter-free bipartite graph fusion method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44( 1): 330–344

[19] Xia W, Gao Q, Wang Q, Gao X, Ding C, Tao D . Tensorized bipartite graph learning for multi-view clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45( 4): 5187–5202

[20] Wang S, Liu X, Zhu X, Zhang P, Zhang Y, Gao F, Zhu E . Fast parameter-free multi-view subspace clustering with consensus anchor guidance. IEEE Transactions on Image Processing, 2022, 31: 556–568

[21] Ji J, Feng S. Anchor structure regularization induced multi-view subspace clustering via enhanced tensor rank minimization. In: Proceedings of 2023 IEEE/CVF International Conference on Computer Vision. 2023, 19343−19352

[22] Zhou S, Wang X, Yang M, Song W . Multi-view clustering with adaptive anchor and bipartite graph learning. Neurocomputing, 2025, 611: 128627

[23] Chen M S, Wang C D, Huang D, Lai J H, Yu P S. Efficient orthogonal multi-view subspace clustering. In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022, 127−135

[24] Li X, Sun Y, Sun Q, Ren Z, Sun Y . Cross-view graph matching guided anchor alignment for incomplete multi-view clustering. Information Fusion, 2023, 100: 101941

[25] Zhang C, Jia X, Li Z, Chen C, Li H. Learning cluster-wise anchors for multi-view clustering. In: Proceedings of the 38th AAAI Conference on Artificial Intelligence. 2024, 16696−16704

[26] Elhamifar E, Vidal R . Sparse subspace clustering: algorithm, theory, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35( 11): 2765–2781

[27] Song J, Liu B, Zhang K, Yu Y, Du S. Multi-view spectral clustering based on graph learning. In: Proceedings of the 41st Chinese Control Conference. 2022, 6527−6532

[28] Liu G, Lin Z, Yan S, Sun J, Yu Y, Ma Y . Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35( 1): 171–184

[29] Dou Y, Yun Y, Gao Q, Zhang X . Self-representation and matrix factorization based multi-view clustering. Neurocomputing, 2021, 459: 395–407

[30] Peng X, Tang H, Zhang L, Yi Z, Xiao S . A unified framework for representation-based subspace clustering of out-of-sample and large-scale data. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27( 12): 2499–2512

[31] Li L, He H . Bipartite graph based multi-view clustering. IEEE Transactions on Knowledge and Data Engineering, 2022, 34( 7): 3111–3125

[32] Wang S, Liu X, Liu S, Jin J, Tu W, Zhu X, Zhu E. Align then fusion: generalized large-scale multi-view clustering with anchor matching correspondences. In: Proceedings of the 36th International Conference on Neural Information Processing Systems. 2022

[33] Sun Y, Li X, Sun Q, Zhang M L, Ren Z. Improved weighted tensor schatten p-norm for fast multi-view graph clustering. In: Proceedings of the 32nd ACM International Conference on Multimedia. 2024, 1427−1436

[34] Nie F, Wang X, Jordan M I, Huang H. The constrained laplacian rank algorithm for graph-based clustering. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence. 2016, 1969−1976

[35] Gabay D, Mercier B . A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & Mathematics with Applications, 1976, 2( 1): 17–40

[36] Cai X, Nie F, Huang H. Exact top-k feature selection via l_2,0-norm constraint. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 2013, 1240−1246

[37] Sherman J, Morrison W J . Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. The Annals of Mathematical Statistics, 1950, 21( 1): 124–127

[38] Martinez A, Benavente R. The AR face database: CVC Technical Report. 24. 1998

[39] Lee Y J, Grauman K . Foreground focus: unsupervised learning from partially matching images. International Journal of Computer Vision, 2009, 85( 2): 143–166

[40] Zhang Y F, Xu C, Lu H, Huang Y M . Character identification in feature-length films using global face-name matching. IEEE Transactions on Multimedia, 2009, 11( 7): 1276–1288

[41] Zhang Z, Liu L, Shen F, Shen H T, Shao L . Binary multi-view clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019, 41( 7): 1774–1782

[42] Lu H, Gao Q, Wang Q, Yang M, Xia W. Centerless multi-view K-means based on the adjacency matrix. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence. 2023, 8949−8956

[43] Cai H, He Q, Han Z, Shang C. ISAR target recognition based on manifold learning. In: Proceedings of 2009 IET International Radar Conference. 2009, 238−238

[44] Strehl A, Ghosh J . Cluster ensembles — a knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research, 2003, 3: 583–617

[45] Varshavsky R, Linial M, Horn D. COMPACT: a comparative package for clustering assessment. In: Proceedings of the ISPA 2005 International Workshops, AEPP, ASTD, BIOS, GCIC, IADS, MASN, SGCA, and WISA Parallel and Distributed Processing and Applications-ISPA 2005 Workshops. 2005

RIGHTS & PERMISSIONS

Higher Education Press