Source-linked AI summary
Auto-weighted Multi-view Clustering for Large-scale Data
Xinhang Wan, Xinwang Liu, Jiyuan Liu, Siwei Wang, Yi Wen, Weixuan Liang, En Zhu, Zhe Liu, Lu Zhou
TL;DR
Existing multi-view clustering methods can be computationally costly, while matrix-factorization approaches may rely on fixed dimensions and hyperparameters. AWMVC learns embeddings at different dimensions and fuses them into an automatically weighted consensus matrix. The paper reports efficient, excellent performance on benchmark datasets.
Problem
Many multi-view clustering methods have high time complexity, while matrix-factorization methods may use fixed-dimension embeddings or hyperparameters that limit representational power and large-scale practicality.
Source: Introduction · p. 1, MF-based Multi-view Clustering · p. 2, The Proposed Method · p. 3Method
AWMVC learns coefficient matrices from view-specific base matrices at diverse dimensions and automatically fuses the embeddings into a consensus matrix without hyperparameters.
Source: Introduction · pp. 1–2, The Proposed Method · p. 3Results
Experiments on various benchmark datasets demonstrate AWMVC's efficiency and excellent clustering performance.
Source: Introduction · p. 2Takeaways & Limitations
The authors present AWMVC's linear-time complexity and parameter-free design as making it suitable for large-scale applications.
Source: Introduction · p. 2
Abstract
from arXiv · showhide
Multi-view clustering has gained broad attention owing to its capacity to exploit complementary information across multiple data views. Although existing methods demonstrate delightful clustering performance, most of them are of high time complexity and cannot handle large-scale data. Matrix factorization-based models are a representative of solving this problem. However, they assume that the views share a dimension-fixed consensus coefficient matrix and view-specific base matrices, limiting their representability. Moreover, a series of large-scale algorithms that bear one or more hyperparameters are impractical in real-world applications. To address the two issues, we propose an auto-weighted multi-view clustering (AWMVC) algorithm. Specifically, AWMVC first learns coefficient matrices from corresponding base matrices of different dimensions, then fuses them to obtain an optimal consensus matrix. By mapping original features into distinctive low-dimensional spaces, we can attain more comprehensive knowledge, thus obtaining better clustering results. Moreover, we design a six-step alternative optimization algorithm proven to be convergent theoretically. Also, AWMVC shows excellent performance on various benchmark datasets compared with existing ones. The code of AWMVC is publicly available at https://github.com/wanxinhang/AAAI-2023-AWMVC.
Introduction
The paper motivates multi-view clustering as a way to use complementary information across data sources, while identifying scalability and fixed-dimension or hyperparameter constraints in existing approaches. AWMVC learns embeddings at diverse dimensions, fuses them into a consensus matrix, and is reported to perform well on benchmark datasets.
Introduction
- Multi-view clustering uses complementary information across views to uncover data structure for clustering.The paper notes applications such as recommender and decision-support systems.Source: Introduction · p. 1
Related Work
- Existing multi-view clustering approaches include subspace, kernel, graph-based, and matrix factorization methods, with the first three categories facing square or cubic time complexity.The paper presents NMF-based methods as a lower-complexity response, while noting hyperparameter and fixed-dimension limitations in prior factorization approaches.Source: Introduction · p. 1
Introduction
- Extensive experiments on various datasets demonstrate AWMVC's efficiency and excellent clustering performance.The paper also describes the algorithm as linear-time and parameter-free.Source: Introduction · p. 2
MF-based Single-view Clustering
- Single-view NMF factorizes a data matrix into base and coefficient matrices, while later work removes nonnegativity to address less discriminatory embeddings.The NMF coefficient matrix can be used with k-means to obtain cluster assignments.Source: MF-based Single-view Clustering · p. 2
MF-based Multi-view Clustering
- MF-based multi-view clustering seeks a consensus matrix, but fixed-dimensional embeddings can limit representational power and complementary information across views.Some earlier methods also use hyperparameters to balance loss and regularization terms.Source: MF-based Multi-view Clustering · p. 2
Optimization
- The paper formulates an alternating optimization procedure that updates variables in turn while holding the others fixed.It presents the methodology as a six-step algorithm and discusses its time complexity and convergence.Source: Methodology · p. 2, Optimization · p. 3
The Proposed Method
- AWMVC projects each view into multiple latent dimensions and automatically weights their contributions, avoiding a fixed embedding dimension and regularization hyperparameters.The method learns coefficient matrices at different dimensions and fuses them into a consensus matrix.Source: The Proposed Method · p. 3
M Subproblem
- The M subproblem is solved using SVD, with computational complexity described as O.The supplied passage does not provide the remainder of the complexity expression.Source: M Subproblem · p. 3
Wp Subproblem
The Wp subproblem is solved efficiently using singular value decomposition (SVD).
Wp Subproblem
- With other variables fixed, Wp is updated using SVD.The passage describes the solution as efficient but does not provide a complete complexity expression.Source: Wp Subproblem · p. 3
Zp Subproblem
AWMVC alternates updates to its variables, then applies k-means to the consensus coefficient matrix. The section also discusses its linear-in-sample-count complexity, convergence, and extension to diverse latent dimensions.
Zp Subproblem
- The Zp subproblem is reformulated after irrelevant variables are dropped and is solved via SVD.The supplied passages do not give a complete complexity expression for this update.Source: Zp Subproblem · p. 3
αp Subproblem
- The alternating loop updates the coefficient and consensus matrices, then updates α and β until convergence.After obtaining consensus matrix M, the algorithm uses k-means for final cluster assignments.Source: αp Subproblem · p. 4
Discussion
- The discussion covers AWMVC's time complexity, theoretical convergence, and possible extension.Source: Discussion · p. 4
Time complexity
- Each iteration has time complexity linear in the number of data points n, and AWMVC is free of hyperparameters.Source: Time complexity · p. 4
Convergence
- The objective decreases monotonically during alternating optimization, and the authors establish that it has a lower bound.They conclude that AWMVC converges theoretically.Source: Convergence · p. 4
Extension
- AWMVC maps features into distinct latent dimensions and fuses their embeddings into a consensus matrix that captures more complementary information than a fixed dimension.The authors also state that the approach can extend to various fields, including multi-view clustering.Source: Extension · p. 4
Experimental Results
The experiments compare AWMVC with existing methods on large-scale benchmarks using four clustering metrics. The section describes the datasets and evaluation setup but provides no comparative outcomes in the supplied passages.
Experiment Settings
- The seven datasets include Flower171, AwA2, Caltech2563, MNIST4, VGGFace25, TinyImageNet6, and YouTubeFace507; the largest has more than 100,000 samples.Source: Experiment Settings · pp. 4–5
- The evaluation runs k-means 50 times, tunes hyperparameters by recommended grid search, and sets m = 3 with dimensions ranging from k to mk.The compared implementations are run without changes.Source: Experiment Settings · p. 5
Experiment Results
- AWMVC is compared with eight algorithms on seven benchmarks using ACC, NMI, purity, and Fscore.The supplied passage refers to Table 2 for results but does not provide its comparative outcomes.Source: Experiment Results · p. 5
1. The proposed method
AWMVC exceeds competitors on four named datasets and is comparable elsewhere; the section also examines convergence, dimension weights, runtime, and component ablations.
1. The proposed method
- AWMVC consistently exceeds competitors on Flower17, Caltech256, VGGFace2, and YouTubeFace50, with comparable results on other datasets.Table 2 compares eight baselines across seven datasets using ACC, NMI, Purity, and Fscore.Source: §1 · p. 5, Table 2 · p. 6
Convergence and Evolution
- The objective decreases monotonically and converges in fewer than ten iterations, while clustering performance improves and then stabilizes.The objective and consensus-matrix evolution are shown for AwA and VGGFace2.Source: Convergence and Evolution · p. 6, Figure 1 · p. 6
Dimension Weights
- Across seven datasets, higher-dimensional embeddings receive larger optimized weights, supporting discriminatory integration of complementary information.Figure 2 shows weights for dimensions k, 2k, and 3k.Source: Dimension Weights · p. 6, Figure 2 · p. 7
Running Time Comparison
- AWMVC takes less time than SMVSC and FPMVS-CAG on almost all datasets except YouTubeFace50, with better clustering results.The comparison also notes that AWMVC can handle large-scale situations, although it is time-consuming relative to graph-based methods.Source: Running Time Comparison · p. 7, Table 3 · p. 7
Ablation Study
- Clustering performance declines when either multiple-dimension mapping or discriminatory weighting is removed, supporting both components’ contributions.AWMVC-P uses one embedding at dimension k; AWMVC-α assigns equal weights to embeddings.Source: Ablation Study · p. 7, Table 4 · p. 7
Conclusion
- AWMVC combines coefficients from diverse latent spaces into a consensus matrix using a convergent six-step alternating algorithm, and the paper proposes extending dimension mapping to existing methods.The authors identify incomplete-view handling as future work.Source: Conclusion · p. 7