Source-linked AI summary
Large-scale Multi-view Subspace Clustering in Linear Time
Zhao Kang, Wangtao Zhou, Zhitong Zhao, Junming Shao, Meng Han, Zenglin Xu
TL;DR
Existing MVSC methods often have quadratic or cubic complexity, limiting their use on large-scale data. LMVSC learns smaller graphs for each view and integrates them so spectral clustering operates on a small graph. Experiments validate its effectiveness and efficiency, and the method also applies to single-view data.
Problem
Existing MVSC methods typically require quadratic or cubic computation, making large-scale application difficult.
Method
LMVSC learns a smaller graph for each view from anchors, integrates the graphs, and performs spectral clustering on the resulting small graph.
Results
Experiments on large-scale benchmark data sets validate LMVSC’s effectiveness and efficiency, with reported accuracy improvements of at least 7% over the second-highest value.
Takeaways & Limitations
LMVSC provides a linear-complexity approach to large-scale MVSC and also applies to single-view subspace clustering.
Takeaways & Limitations
Spectral clustering on the full graph still requires at least O(n^2k) time, motivating LMVSC’s reduced-graph strategy.
Abstract
from arXiv · showhide
A plethora of multi-view subspace clustering (MVSC) methods have been proposed over the past few years. Researchers manage to boost clustering accuracy from different points of view. However, many state-of-the-art MVSC algorithms, typically have a quadratic or even cubic complexity, are inefficient and inherently difficult to apply at large scales. In the era of big data, the computational issue becomes critical. To fill this gap, we propose a large-scale MVSC (LMVSC) algorithm with linear order complexity. Inspired by the idea of anchor graph, we first learn a smaller graph for each view. Then, a novel approach is designed to integrate those graphs so that we can implement spectral clustering on a smaller graph. Interestingly, it turns out that our model also applies to single-view scenario. Extensive experiments on various large-scale benchmark data sets validate the effectiveness and efficiency of our approach with respect to state-of-the-art clustering methods.
Introduction
Multi-view subspace clustering combines complementary feature views but remains difficult to scale because existing methods incur quadratic or cubic costs. LMVSC addresses this by learning smaller per-view graphs, integrating them, and clustering on a reduced graph.
- Computational challenge: Spectral subspace clustering methods typically require O(n^2) or O(n^3) time for representation learning and O(n^3) or at least O(n^2k) for spectral clustering.These costs hinder application to large-scale data sets.
- Research gap: Existing acceleration techniques target single-view subspace clustering and cannot handle multi-view data because of view heterogeneity.This leaves large-scale MVSC insufficiently addressed.
- Motivation: Multi-view data provide different feature sets that characterize complementary information, motivating methods that incorporate multiple views.Examples include heterogeneous image features and multilingual article descriptions.
- Proposed approach: LMVSC selects a small number of anchors, builds a smaller graph for each view, integrates the graphs, and performs spectral clustering on the reduced graph.The design targets both large-scale graph construction and expensive spectral clustering.
- Contributions: The proposed method is presented as a linear-time approach for large-scale multi-view subspace clustering and also applies to single-view clustering.Experiments are reported as validating its effectiveness and efficiency.
Preliminaries
Subspace clustering learns a similarity graph from data, while MVSC extends this framework across multiple views. Anchor graphs reduce construction cost, but fixed kernel choices can limit graph quality; LMVSC instead learns a smaller graph adaptively.
- Subspace clustering: Subspace clustering represents each data point as a linear combination of other points and treats the resulting coefficients as similarities.The similarity graph has size n × n, creating a scalability challenge.
- Subspace clustering: The similarity coefficients are constrained to be nonnegative and each column sums to one, with regularization controlled by α > 0.The regularizer f(·) determines properties of the solution.
- Multi-view extension: MVSC learns graph representations across views and can model shared clustering, complementarity, or consistency and specificity between views.Existing MVSC methods generally require at least O(n^2k) time.
- Anchor graph: Anchor graphs select m ≪ n landmarks and construct a sparse affinity matrix between original data points and anchors, requiring only O(mn) distances.A Gaussian kernel and nearest-anchor relationships are used in the described construction.
- Anchor graph: The anchor graph’s quality depends heavily on its exponential kernel and kernel parameter, which may not fit the data structure without supervision.This can degrade downstream performance.
- LMVSC: LMVSC adaptively learns a smaller graph Z from raw data to approximate the full n × n graph matrix.This replaces the fixed-kernel heuristic with a data-driven optimization approach.
Methodology
LMVSC replaces full n × n multi-view graphs with compact anchor-based graphs, combines them through a concatenated representation, and obtains the clustering embedding without eigendecomposing the full graph. Its construction and embedding costs remain linear in the number of data points when the number of anchors and views are small.
- Methodology: LMVSC uses k-means landmarks to construct a smaller matrix Zi ∈ R^n×m for each view, approximating the full similarity matrix Si.Here m ≪ n, so graph construction uses similarities involving the anchors rather than all n^2 pairs.
- Methodology: The learned view-specific graphs are merged by forming a concatenated matrix ¯Z, rather than directly applying spectral clustering to the non-square Zi graphs.The concatenation is normalized by 1/√v across the v views.
- Methodology: Eigen decomposition of the full graph requires at least O(n^2k), whereas LMVSC computes the embedding through a low-dimensional matrix with mv ≪ n.The proposed alternative avoids the full-graph eigendecomposition bottleneck.
- Methodology: The k-dimensional embedding Q is computed from the k left singular vectors of ¯Z, which correspond to the eigenvectors of the combined graph matrix.This follows the stated equivalence between the SVD of ¯Z and the eigendecomposition of ¯S.
- Methodology: The algorithm solves the graph-learning problem, constructs ¯Z, computes Q by SVD, and applies k-means to Q for final clustering.The procedure also applies to single-view data by setting v = 1 and ¯Z = ˆZ.
- Methodology: LMVSC costs time only linear in n, with graph construction O(nm^3v), embedding O(m^3v^3 + 2mnv), and final k-means O(nk^2t).The construction of Zi can also be parallelized over multiple cores.
Experiment on Multi-View Data
Experiments on benchmark multi-view data evaluate LMVSC’s clustering quality, efficiency, and scalability against recent methods. The results report strong accuracy, substantially lower runtime and memory demands, and sensitivity to anchor selection and α.
- Experimental Setup: LMVSC is evaluated on Handwritten, Caltech-101 subsets, Reuters, and NUS-WIDE-Object benchmark data sets.The experiments use Caltech7, Caltech20, Handwritten, Reuters, and NUS data.
- Scalability: Many comparison methods cannot run on Reuters and NUS because of out-of-memory issues, demonstrating LMVSC’s lower space complexity.These data sets contain more than 10,000 samples.
- Clustering Performance: LMVSC constantly outperforms other methods in accuracy, with an average improvement of at least 7% over the second-highest value.For NMI and purity, it achieves comparable or better performance than the other methods.
- Running Time: 13 hours versus 3 minutes: MSC IAS requires almost 13 hours on NUS, while LMVSC completes it in 3 minutes.LMVSC finishes all data sets in several minutes and is up to several orders of magnitude faster than other multi-view methods on large data sets.
- Robustness Study: On noisy 70,000-sample MNIST, LMVSC is 20 times faster than SSCOMP and achieves better performance in all reported metrics.Only SSCOMP and LMVSC can handle the large data sets in the robustness experiments; other recent multi-view methods fail.
- Parameter Analysis: Increasing α or using too many anchors degrades performance because excessive anchors become less representative and introduce extra errors.The number of anchors and α are tuned by grid search.
Experiment on Single-View Data
The single-view experiments evaluate the method on large data sets and noisy multi-view constructions derived from MNIST. Results indicate improved performance with reasonable computation time, while robustness is tested across several noise types and levels.
- Data and evaluation: The single-view evaluation uses large-scale data sets, including Reuters and CovType, with results summarized in Tables 8 and 9.Reuters contains newswire stories, while CovType contains cartographic instances for forest-cover prediction.
- Parameter analysis: Sensitivity analyses examine the method's parameters on the Handwritten and MNIST data sets.The analyses are presented in Figures 5 and 6.
- Results: The method improves performance significantly on the single-view data while maintaining reasonable computation time.For CoverType, k-means runs fast because the cluster number is small.
Conclusion
The paper presents LMVSC as a linear-complexity approach to large-scale multi-view subspace clustering. It builds smaller anchor-based graphs, integrates them before eigendecomposition, and also applies to single-view data.
- Conclusion: LMVSC addresses large-scale multi-view subspace clustering with linear computation complexity.The paper describes it as the first effort targeting the large-scale multi-view problem.
- Conclusion: For each view, the method builds a smaller graph between raw data points and generated anchors.This reduces the graph size relative to directly constructing a full graph.
- Conclusion: A novel integration mechanism merges the view-specific graphs and accelerates eigendecomposition, while the method also applies to single-view data.Experiments verify effectiveness, efficiency, and robustness against other state-of-the-art techniques.