research-article

Multiview Clustering: A Scalable and Parameter-Free Bipartite Graph Fusion Method

Authors:

Feiping NieAuthors Info & Claims

IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 44, Issue 1

Pages 330 - 344

https://doi.org/10.1109/TPAMI.2020.3011148

Published: 01 January 2022 Publication History

Abstract

Multiview clustering partitions data into different groups according to their heterogeneous features. Most existing methods degenerate the applicability of models due to their intractable hyper-parameters triggered by various regularization terms. Moreover, traditional spectral based methods always encounter the expensive time overheads and fail in exploring the explicit clusters from graphs. In this paper, we present a scalable and parameter-free graph fusion framework for multiview clustering, seeking for a joint graph compatible across multiple views in a self-supervised weighting manner. Our formulation coalesces multiple view-wise graphs straightforward and learns the weights as well as the joint graph interactively, which could actively release the model from any weight-related hyper-parameters. Meanwhile, we manipulate the joint graph by a connectivity constraint such that the connected components indicate clusters directly. The designed algorithm is initialization-independent and time-economical which obtains the stable performance and scales well with the data size. Substantial experiments on toy data as well as real datasets are conducted that verify the superiority of the proposed method compared to the state-of-the-arts over the clustering performance and time expenditure.

References

[1]

C. Wang, M. Pelillo, and K. Siddiqi, “Dominant set clustering and pooling for multiview 3D object recognition,” in Proc. Brit. Mach. Vis. Conf., 2017, pp. 64.1–64.12.

[2]

L. Zhao, Q. Hu, and W. Wang, “Heterogeneous feature selection with multi-modal deep neural networks and sparse group lass,” IEEE Trans. Multimedia, vol. 17, no. 11, pp. 1936–1948, Nov. 2015.

Digital Library

[3]

X. Cao, C. Zhang, C. Zhou, H. Fu, and H. Foroosh, “Constrained multiview video face clustering,” IEEE Trans. Image Process., vol. 24, no. 11, pp. 4381–4393, Nov. 2015.

Digital Library

[4]

X. Cao, C. Zhang, H. Fu, S. Liu, and H. Zhang, “Diversity-induced multiview subspace clustering,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., 2015, pp. 586–594.

[5]

Q. Yin, S. Wu, R. He, and L. Wang, “Multiview clustering via pairwise sparse subspace representation,” Neurocomputing, vol. 156, pp. 12–21, 2015.

Digital Library

[6]

C. Zhang, et al., “Generalized latent multiview subspace clustering,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 42, no. 1, pp. 86–99, Jan. 2020.

Digital Library

[7]

Q. Yin, S. Wu, and L. Wang, “Multiview clustering via unified and view-specific embeddings learning,” IEEE Trans. Neural Netw. Learn. Syst., vol. 29, no. 11, pp. 5541–5553, Nov. 2018.

[8]

Z. Kang, W. Zhou, Z. Zhao, J. Shao, M. Han, and Z. Xu, “Large-scale multiview subspace clustering in linear time,” in Proc. 34th AAAI Conf. Artif. Intell., 2020, pp. 4412–4419.

[9]

Z. Kang, et al., “Partition level multiview subspace clustering,” Neural Netw., vol. 122, pp. 279–288, 2020.

Digital Library

[10]

J. Liu, C. Wang, J. Gao, and J. Han, “Multiview clustering via joint nonnegative matrix factorization,” in Proc. SIAM Int. Conf. Data Mining, 2013, pp. 252–260.

[11]

L. Zong, X. Zhang, L. Zhao, H. Yu, and Q. Zhao, “Multiview clustering via multi-manifold regularized non-negative matrix factorization,” Neural Netw., vol. 88, pp. 74–89, 2017.

[12]

J. Xu, J. Han, F. Nie, and X. Li, “Re-weighted discriminatively embedded k-means for multiview clustering,” IEEE Trans. Image Process., vol. 26, no. 6, pp. 3016–3027, Jun. 2017.

Digital Library

[13]

H. Zhao, Z. Ding, and Y. Fu, “Multiview clustering via deep matrix factorization,” in Proc. 31st AAAI Conf. Artif. Intell., 2017, pp. 2921–2927.

[14]

S. Bickel and T. Scheffer, “Multiview clustering,” in Proc. IEEE Int. Conf. Data Mining, 2004, pp. 19–26.

[15]

D. Zhou and C. J. Burges, “Spectral clustering and transductive learning with multiple views,” in Proc. 24th Int. Conf. Mach. Learn., 2007, pp. 1159–1166.

[16]

A. Kumar, P. Rai, and H. Daume, “Co-regularized multiview spectral clustering,” in Proc. 24th Int. Conf. Neural Inf. Process. Syst., 2011, pp. 1413–1421.

[17]

Y. Wang, L. Wu, X. Lin, and J. Gao, “Multiview spectral clustering via structured low-rank matrix factorization,” IEEE Trans. Neural Netw. Learn. Syst., vol. 29, no. 10, pp. 4833–4843, Oct. 2018.

[18]

R. Xia, Y. Pan, L. Du, and J. Yin, “Robust multiview spectral clustering via low-rank and sparse decomposition,” in Proc. 28th AAAI Conf. Artif. Intell., 2014, pp. 2149–2155.

[19]

C. Lu, S. Yan, and Z. Lin, “Convex sparse spectral clustering: Single-view to multiview,” IEEE Trans. Image Process., vol. 25, no. 6, pp. 2833–2843, Jun. 2016.

Digital Library

[20]

X. Zhu, S. Zhang, W. He, R. Hu, C. Lei, and P. Zhu, “One-step multiview spectral clustering,” IEEE Trans. Knowl. Data Eng., vol. 31, no. 10, pp. 2022–2034, Oct. 2019.

[21]

Z. Hu, F. Nie, R. Wang, and X. Li, “Multiview spectral clustering via integrating nonnegative embedding and spectral embedding,” Inf. Fusion, vol. 55, pp. 251–259, 2020.

[22]

F. Nie, J. Li, and X. Li, “Parameter-free auto-weighted multiple graph learning: A framework for multiview clustering and semi-supervised classification,” in Proc. 25th Int. Joint Conf. Artif. Intell., 2016, pp. 1881–1887.

[23]

F. Nie, G. Cai, J. Li, and X. Li, “Auto-weighted multiview learning for image clustering and semi-supervised classification,” IEEE Trans. Image Process., vol. 27, no. 3, pp. 1501–1511, Mar. 2018.

[24]

Z. Kang, et al., “Multi-graph fusion for multiview spectral clustering,” Knowl.-Based Syst., vol. 189, 2020, Art. no.

[25]

K. Zhan, F. Nie, J. Wang, and Y. Yang, “Multiview consensus graph clustering,” IEEE Trans. Image Process., vol. 28, no. 3, pp. 1261–1270, Mar. 2019.

Digital Library

[26]

J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888–905, Aug. 2000.

Digital Library

[27]

Y. Li, F. Nie, H. Huang, and J. Huang, “Large-scale multiview spectral clustering via bipartite graph,” in Proc. 29th AAAI Conf. Artif. Intell., 2015, pp. 2750–2756.

[28]

L. Feng, L. Cai, Y. Liu, and S. Liu, “Multiview spectral clustering via robust local subspace learning,” Soft Comput., vol. 21, no. 8, pp. 1937–1948, 2017.

Digital Library

[29]

H. Wang, Y. Yang, and B. Liu, “GMC: Graph-based multiview clustering,” IEEE Trans. Knowl. Data Eng., vol. 32, no. 6, pp. 1116–1129, Jun. 2020.

[30]

Z. Zhang, L. Liu, F. Shen, H. T. Shen, and L. Shao, “Binary multiview clustering,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 41, no. 7, pp. 1774–1782, Jul. 2019.

[31]

Z. Kang, H. Pan, S. C. Hoi, and Z. Xu, “Robust graph learning from noisy data,” IEEE Trans. Cybern., vol. 50, no. 5, pp. 1833–1843, May 2020.

[32]

Z. Kang, L. Wen, W. Chen, and Z. Xu, “Low-rank kernel learning for graph-based clustering,” Knowl.-Based Syst., vol. 163, pp. 510–517, 2019.

[33]

F. Nie, X. Wang, M. I. Jordan, and H. Huang, “The constrained laplacian rank algorithm for graph-based clustering,” in Proc. 30th AAAI Conf. Artif. Intell., 2016, pp. 1969–1976.

[34]

A. Y. Ng, M. I. Jordan, and Y. Weiss, “On spectral clustering: Analysis and an algorithm,” in Proc. 14th Int. Conf. Neural Inf. Process. Syst., 2001, vol. 14, pp. 849–856.

[35]

S. X. Yu and J. Shi, “Multiclass spectral clustering,” in Proc. 9th IEEE Int. Conf. Comput. Vis., 2003, pp. 313–319.

[36]

L. Zelnik-Manor, “Self-tuning spectral clustering,” in Proc. 17th Int. Conf. Neural Inf. Process. Syst., 2004, vol. 17, pp. 1601–1608.

[37]

A. Kumar and H. D. Iii, “A co-training approach for multiview spectral clustering,” in Proc. 28th Int. Conf. Mach. Learn., 2011, pp. 393–400.

[38]

F. Nie, J. Li, and X. Li, “Self-weighted multiview clustering with multiple graphs,” in Proc. 26th Int. Joint Conf. Artif. Intell., 2017, pp. 2564–2570.

[39]

K. Zhan, C. Zhang, J. Guan, and J. Wang, “Graph learning for multiview clustering,” IEEE Trans. Cybern., vol. 48, no. 10, pp. 2887–2895, Oct. 2018.

[40]

W. Liu, J. He, and S.-F. Chang, “Large graph construction for scalable semi-supervised learning,” in Proc. 27th Int. Conf. Mach. Learn., 2010, pp. 679–686.

[41]

D. Cai and X. Chen, “Large scale spectral clustering via landmark-based sparse representation,” IEEE Trans. Cybern., vol. 45, no. 8, pp. 1669–1680, Aug. 2015.

[42]

M. Wang, W. Fu, S. Hao, D. Tao, and X. Wu, “Scalable semi-supervised learning by efficient anchor graph regularization,” IEEE Trans. Knowl. Data Eng., vol. 28, no. 7, pp. 1864–1877, Jul. 2016.

[43]

P. Tseng, “Convergence of a block coordinate descent method for nondifferentiable minimization,” J. Optim. Theory Appl., vol. 109, no. 3, pp. 475–494, 2001.

Digital Library

[44]

K. Fan, “On a theorem of weyl concerning eigenvalues of linear transformations I,” Proc. Nat. Acad. Sci. United States of America, vol. 35, no. 11, pp. 652–655, 1949.

[45]

D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods. Cambridge, MA, USA: Academic Press, 1982.

[46]

Z. Lin, M. Chen, and Y. Ma, “The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices,” Tech. Rep. UILU-ENG-09-2215, UIUC, 2009,.

[47]

Z. Lin, R. Liu, and Z. Su, “Linearized alternating direction method with adaptive penalty for low-rank representation,” in Proc. 24th Int. Conf. Neural Inf. Process. Syst., 2011, pp. 612–620.

[48]

F. Du, Q.-Y. Dong, and H.-S. Li, “Truss structure optimization with subset simulation and augmented lagrangian multiplier method,” Algorithms, vol. 10, no. 4, 2017, Art. no.

[49]

A. K. Jain, “Data clustering: 50 years beyond k-means,” Pattern Recognit. Lett., vol. 31, no. 8, pp. 651–666, 2010.

Digital Library

[50]

D. Cai and X. Chen, “Large scale spectral clustering via landmark-based sparse representation,” IEEE Trans. Cybern., vol. 45, no. 8, pp. 1669–1680, Aug. 2015.

[51]

J. Winn and N. Jojic, “LOCUS: Learning object classes with unsupervised segmentation,” in Proc. 10th IEEE Int. Conf. Comput. Vis., 2005, pp. 756–763.

[52]

D. Dheeru and E. Karra Taniskidou, “UCI machine learning repository,” 2017. [Online]. Available: http://archive.ics.uci.edu/ml

[53]

F. Li, F. Rob, and P. Peitro, “Learning generative visual models from few training examples: An incremental Bayesian approach tested on 101 object categories,” Comput. Vis. Image Understanding, vol. 106, no. 1, pp. 59–70, 2005.

[54]

L. Deng, “The MNIST database of handwritten digit images for machine learning research [best of the web],” IEEE Signal Process. Mag., vol. 29, no. 6, pp. 141–142, Nov. 2012.

[55]

T.-S. Chua, J. Tang, R. Hong, H. Li, Z. Luo, and Y.-T. Zheng, “NUS-WIDE: A real-world web image database from National University of Singapore,” in Proc. ACM Conf. Image Video Retrieval, 2009, Art. no.

[56]

C. Apté, F. Damerau, and S. M. Weiss, “Automated learning of decision rules for text categorization,” ACM Trans. Inf. Syst., vol. 12, no. 3, pp. 233–251, 1994.

Digital Library

[57]

A. Strehl and J. Ghosh, “Cluster ensembles – A knowledge reuse framework for combining multiple partitions,” J. Mach. Learn. Res., vol. 3, pp. 583–617, 2002.

[58]

H. W. Kuhn, “The hungarian method for the assignment problem,” Naval Res. Logistics, vol. 2, no. 1/2, pp. 83–97, 2010.

[59]

A. H. Sherman, “On newton-iterative methods for the solution of systems of nonlinear equations,” SIAM J. Numerical Anal., vol. 15, no. 4, pp. 755–771, 1978.

[60]

J. Huang, F. Nie, and H. Huang, “A new simplex sparse learning model to measure data similarity for clustering,” in Proc. 24th Int. Joint Conf. Artif. Intell., 2015, pp. 3569–3575.

Cited By

Gu ZFeng SLi ZYuan JLiu J(2024)NOODLE: Joint Cross-View Discrepancy Discovery and High-Order Correlation Detection for Multi-View Subspace ClusteringACM Transactions on Knowledge Discovery from Data10.1145/365330518:6(1-23)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3653305
Gu ZLi ZFeng SBaeza-Yates RBonchi F(2024)Topology-Driven Multi-View Clustering via Tensorial Refined Sigmoid Rank MinimizationProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672070(920-931)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3672070
Li JGao QWang QDeng CXie DBaeza-Yates RBonchi F(2024)Label Learning Method Based on Tensor ProjectionProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671671(1599-1609)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671671
Show More Cited By

Index Terms

Multiview Clustering: A Scalable and Parameter-Free Bipartite Graph Fusion Method

Index terms have been assigned to the content through auto-classification.

Recommendations

Bipartite subgraphs of triangle-free subcubic graphs

Suppose G is a graph with n vertices and m edges. Let n^' be the maximum number of vertices in an induced bipartite subgraph of G and let m^' be the maximum number of edges in a spanning bipartite subgraph of G. Then b(G)=m^'/m is called the bipartite ...
Triangle-free subcubic graphs with minimum bipartite density

A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph G is max{@e(H)/@e(G):H is a bipartite subgraph of G}, where @e(H) and @e(G) denote the numbers of edges in H and G, respectively. It is an NP-hard problem to ...
Making a C6-free graph C4-free and bipartite

We show that every C6-free graph G has a C4-free, bipartite subgraph with at least 3e(G)/8 edges. Our proof is probabilistic and uses a theorem of Fredi etal. (2006) on C6-free graphs.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

0162-8828 © 2020 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 January 2022

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gu ZFeng SLi ZYuan JLiu J(2024)NOODLE: Joint Cross-View Discrepancy Discovery and High-Order Correlation Detection for Multi-View Subspace ClusteringACM Transactions on Knowledge Discovery from Data10.1145/365330518:6(1-23)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3653305
Gu ZLi ZFeng SBaeza-Yates RBonchi F(2024)Topology-Driven Multi-View Clustering via Tensorial Refined Sigmoid Rank MinimizationProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672070(920-931)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3672070
Li JGao QWang QDeng CXie DBaeza-Yates RBonchi F(2024)Label Learning Method Based on Tensor ProjectionProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671671(1599-1609)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671671
Wu DWang PLiang JLu JXu JWang RNie F(2024)Adaptive Local Modularity Learning for Efficient Multilayer Graph ClusteringIEEE Transactions on Signal Processing10.1109/TSP.2024.338565472(2221-2232)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3385654
Zhao WLi QXu HGao QWang QGao X(2024)Anchor Graph-Based Feature Selection for One-Step Multi-View ClusteringIEEE Transactions on Multimedia10.1109/TMM.2024.336760526(7413-7425)Online publication date: 26-Feb-2024
https://dl.acm.org/doi/10.1109/TMM.2024.3367605
Zhang XLuo CWang XLi JZhao SJiang D(2024)Learnable Tensor Graph Fusion Framework for Natural Image SegmentationIEEE Transactions on Multimedia10.1109/TMM.2024.336068926(7160-7173)Online publication date: 31-Jan-2024
https://dl.acm.org/doi/10.1109/TMM.2024.3360689
Zhang HLi YLi X(2024)Constrained Bipartite Graph Learning for Imbalanced Multi-Modal RetrievalIEEE Transactions on Multimedia10.1109/TMM.2023.332388426(4502-4514)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TMM.2023.3323884
Shen QXu TLiang YChen YHe Z(2024)Robust Tensor Recovery for Incomplete Multi-View ClusteringIEEE Transactions on Multimedia10.1109/TMM.2023.332149926(3856-3870)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TMM.2023.3321499
Liu SLiao QWang SLiu XZhu E(2024)Robust and Consistent Anchor Graph Learning for Multi-View ClusteringIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336466336:8(4207-4219)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3364663
Wang SLiu XLiu STu WZhu E(2024)Scalable and Structural Multi-View Graph Clustering With Adaptive Anchor FusionIEEE Transactions on Image Processing10.1109/TIP.2024.344432033(4627-4639)Online publication date: 21-Aug-2024
https://dl.acm.org/doi/10.1109/TIP.2024.3444320
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents