PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Multi-view Clustering via Ensembles: Towards Scalability, Superiority, and Simplicity

Dong Huang, Chang-Dong Wang, Jian-Huang Lai

arXiv:2203.11572v4cs.LGstat.ML

TL;DR

Previous multi-view clustering methods face computational, fusion-stage, and dataset-specific tuning limitations. FastMICE addresses these with random view groups and hybrid early-late fusion, achieving almost linear complexity and strong results across 22 datasets without dataset-specific tuning.

  • Problem

    Multi-view clustering remains challenged by high computational complexity, limited exploration of multi-stage fusion, and frequent dataset-specific hyperparameter tuning.

  • Method

    FastMICE forms random view groups, uses three levels of diversity for early-stage bipartite graphs, and combines diversified base clusterings through late-stage consensus fusion.

  • Results

    FastMICE has almost linear time and space complexity and demonstrates scalability, superiority, and simplicity across 22 multi-view datasets without dataset-specific tuning.

  • Takeaways & Limitations

    The approach supports robust and accurate clustering on general-scale and large-scale multi-view datasets without dataset-specific hyperparameter tuning.

  • Takeaways & Limitations

    The ensemble-generation graph-partitioning step can require O((N + p̄^(m)V^(m))^3) time via SVD, which is computationally expensive for large-scale datasets.

Abstract

from arXiv · show

Despite significant progress, there remain three limitations to the previous multi-view clustering algorithms. First, they often suffer from high computational complexity, restricting their feasibility for large-scale datasets. Second, they typically fuse multi-view information via one-stage fusion, neglecting the possibilities in multi-stage fusions. Third, dataset-specific hyperparameter-tuning is frequently required, further undermining their practicability. In light of this, we propose a fast multi-view clustering via ensembles (FastMICE) approach. Particularly, the concept of random view groups is presented to capture the versatile view-wise relationships, through which the hybrid early-late fusion strategy is designed to enable efficient multi-stage fusions. With multiple views extended to many view groups, three levels of diversity (w.r.t. features, anchors, and neighbors, respectively) are jointly leveraged for constructing the view-sharing bipartite graphs in the early-stage fusion. Then, a set of diversified base clusterings for different view groups are obtained via fast graph partitioning, which are further formulated into a unified bipartite graph for final clustering in the late-stage fusion. Notably, FastMICE has almost linear time and space complexity, and is free of dataset-specific tuning. Experiments on 22 multi-view datasets demonstrate its advantages in scalability (for extremely large datasets), superiority (in clustering performance), and simplicity (to be applied) over the state-of-the-art. Code available: https://github.com/huangdonghere/FastMICE.

1 INTRODUCTION

Existing multi-view clustering methods face scalability, fusion-stage, and dataset-specific tuning challenges. FastMICE addresses these through random view groups and a hybrid early-late fusion strategy designed for efficient, robust clustering.

  • Research challenges: Previous MVC methods face high computational complexity, limited multi-stage fusion, and frequent dataset-specific hyperparameter tuning.Affinity construction can require O(N^2d) time and O(N^2) space, while spectral partitioning can require O(N^3) time and O(N^2) space.
  • Research challenges: Most existing MVC algorithms use either early fusion or late fusion, leaving multi-stage fusion comparatively unexplored.Early fusion combines views in a unified model, whereas late fusion combines view-specific base clusterings at the final stage.
  • FastMICE approach: FastMICE introduces random view groups to investigate view-wise relationships in a diversified manner.Each group contains a random number of views, extending multiple views into many flexible view organizations.
  • FastMICE approach: Its hybrid early-late fusion jointly uses feature-, anchor-, and neighborhood-level diversity to build bipartite graphs and diversified base clusterings before final consensus clustering.Early-stage view-sharing bipartite graphs are partitioned efficiently, then the resulting base clusterings form a unified bipartite graph for late-stage clustering.
  • Reported advantages: FastMICE has almost linear time and space complexity, requires no dataset-specific tuning, and outperforms state-of-the-art methods across 22 multi-view datasets.The evaluation includes 10 general-scale and 12 large-scale datasets, supporting the reported scalability, performance, and application simplicity.

2 RELATED WORK

The related work organizes multi-view clustering around early or late fusion, while highlighting gaps in multi-stage fusion, scalability, and multi-view ensemble generation.

  • Multi-view Clustering: Early-fusion methods combine information from all views in a unified model, whereas late-fusion methods first obtain view-specific base clusterings and then learn a consensus.
  • Multi-view Clustering: Most existing multi-view clustering methods perform fusion in a single stage and do not explore multi-stage fusion formulations.
  • Multi-view Clustering: Many previous methods have quadratic or cubic computational complexity, limiting their feasibility for large-scale datasets.
  • Ensemble Clustering: FastMICE combines multi-view clustering and ensemble clustering by fusing multiple base clusterings into a unified clustering result.
  • Ensemble Clustering: Most ensemble-clustering methods target single-view datasets, while MVEC and M2VEC generate base clusterings separately without exploiting multi-view complementarity.

3 PROPOSED FRAMEWORK

The proposed framework introduces the FastMICE components and organizes them from view-group formation through graph construction, base-clustering generation, consensus fusion, and complexity analysis.

  • FastMICE is described through notation, random view-group formation, view-sharing bipartite-graph construction, diversified base-clustering generation, and unified consensus fusion.
  • The framework concludes with a highly efficient consensus function that fuses base clusterings into a unified clustering.
  • The time and space complexity of FastMICE are analyzed as part of the proposed framework.

3.1 Notations

The notation section defines datasets and multi-view data matrices, then frames robust and efficient multi-view fusion as the central challenge for large-scale settings.

  • A dataset X contains N samples, with x_i denoting the i-th sample.
  • A multi-view dataset is represented as X = {X^1, X^2, · · ·, X^V}, where X^v is the data matrix for view v with dimension d_v.
  • The paper focuses on robustly fusing multi-view information while maintaining efficiency and practicality when the sample size N is very large.

3.2 Early-Stage View Group Formation

FastMICE replaces the conventional single-or-all view organization with random view groups, enabling diversified view-wise processing and hybrid early-late fusion.

  • Early-Stage View Group Formation: Random view groups contain randomly selected subsets of views and serve as the basic units for view-wise diversification and hybrid early-late fusion.
  • Early-Stage View Group Formation: Each view group contains between V_min = 1 and V_max = V view members, allowing group sizes from one view through all views.
  • Early-Stage View Group Formation: Repeating the randomization produces M view groups, and each group generates one base clustering, making M the ensemble size.
  • Early-Stage View Group Formation: Conventional early fusion is recovered with one group containing all views, while late fusion is recovered with one single-view group per view.

3.3 View-Sharing Bipartite Graph Construction

FastMICE constructs view-sharing bipartite graphs through random feature, anchor, and neighborhood diversification across view groups. Sparse sample–anchor links support efficient graph construction while retaining multiple view-specific representations.

  • Early-stage fusion: Early-stage fusion builds multiple view-sharing bipartite graphs rather than seeking one-shot optimal fusion.The graphs are constructed across multiple random view groups to preserve diversified view relationships.
  • Diversification: Three diversification levels jointly vary features, anchors, and neighborhoods during bipartite graph construction.Feature sub-sampling uses randomized ratios, while anchor and nearest-neighbor contributions are distributed across view members.
  • Anchor and neighborhood allocation: Each view member contributes approximately ⌈p/V^(m)⌉ anchors and ⌈K/V^(m)⌉ nearest neighbors to its view group.The allocation is designed to distribute anchor and neighborhood construction across the views in each group.
  • Sparse graph construction: Each sample links to its nearest anchors, producing sparse cross-affinity matrices with N·K̄^(m) nonzero entries per view member.The resulting sparsity benefits later matrix computations.

3.4 Ensemble Generation in View Groups

FastMICE partitions each view-sharing bipartite graph into a diversified base clustering using a reduced anchor graph. This avoids the full graph’s cubic spectral decomposition while retaining efficient clustering generation.

  • Base-clustering generation: The ensemble stage generates one diversified base clustering for each of the M view groups.The cluster count k^(m) is randomly selected within [k_min, k_max] for each group.
  • Full-graph bottleneck: Full spectral partitioning of a view-sharing graph would require O((N + p̄^(m)V^(m))^3) time via SVD.Because p̄^(m)V^(m) ≈ p ≪ N, this cost is computationally expensive for large datasets.
  • Reduced-graph partitioning: FastMICE reduces the eigen-decomposition to a smaller graph whose nodes are the view group’s anchors.The reduced graph uses the anchor-side affinity matrix derived from the sparse cross-affinity matrix.
  • Clustering output: The resulting eigenvectors are stacked as feature vectors and discretized with k-means to obtain the view group’s base clustering.Generating a base clustering takes O(N(k^2t + K^2 + Kk) + p^3) time and O(N(k + K)) space.

3.5 Late-Stage Consensus Function

The late-stage consensus function unifies the clusters produced by all view groups in a bipartite graph linking data samples to base clusters. Sparse membership links enable reduced-graph consensus computation.

  • Unified graph: FastMICE represents all clusters from the M base clusterings as right-side nodes in a unified bipartite graph.The graph links N data samples on the left to k_c base clusters on the right.
  • Membership encoding: A sample links to exactly one cluster from each base clustering, yielding exactly M nonzero entries per row of B.Consequently, the cross-affinity matrix contains N·M nonzero entries.
  • Reduced consensus: Consensus eigen-decomposition is performed on the smaller graph with affinity matrix E_s = BᵀD̂^-1B.Computing this reduced affinity matrix takes O(NM^2) time.
  • Final clustering: The final clustering is obtained by solving the reduced consensus problem and discretizing the resulting representation.The stated overall consensus costs are O(N(k^2t + M^2 + Mk) + k_c^3) time and O(N(k + M)) space.

3.6 Complexity Analysis

FastMICE’s complexity is linear in the number of samples under the large-scale regime, with linear space usage as well. Its evaluation covers 22 real-world multi-view datasets.

  • Time complexity: O(NMp^1/2V^1/2) is FastMICE’s overall time complexity when k, K, M, V ≪ p ≪ N.This complexity is linear in the data size N.
  • Space complexity: O(N(k + K + V + M)) is FastMICE’s overall space complexity.The bound includes graph construction, serial base-clustering generation, and consensus storage.

4 EXPERIMENTS

FastMICE is evaluated on 22 real-world multi-view datasets against ten MVC baselines using four standard clustering metrics, with fixed or dataset-independent settings for the proposed method.

  • Datasets: Experiments cover 22 real-world multi-view datasets, including 10 general-scale and 12 large-scale datasets.Different dataset versions provide varying data sizes for evaluating scalability.
  • Baselines: FastMICE is compared with ten MVC methods spanning large-scale, ensemble-clustering, and tuning-free baselines.The baselines include BMVC, LMVSC, SMVSC, FPMVS-CAG, MVEC, M2VECkm, M2VECspec, AMGL, SwMC, and MVSC.
  • Parameter settings: FastMICE requires no dataset-specific hyperparameter tuning across the benchmark datasets.Its parameters use common values or randomized common ranges, including feature sampling and base-clustering cluster counts.

4.3 Performance Comparison and Analysis

FastMICE delivers strong clustering performance across the benchmark datasets while maintaining scalability and robustness to ensemble, anchor, neighbor, and view-group settings.

  • Performance comparison: FastMICE achieves the best NMI on 19 of 22 datasets and outperforms the four large-scale baselines on all datasets except Movies and NUS-WIDE.The four large-scale baselines are BMVC, LMVSC, SMVSC, and FPMVS-CAG.
  • Performance comparison: FastMICE obtains average ranks of 1.23 for NMI, 1.27 for ARI, 1.55 for ACC, and 1.45 for PUR.It achieves the best scores on 18 datasets for ARI and 14 datasets for both ACC and PUR.
  • Ensemble size: FastMICE maintains consistently high-quality clustering across varying ensemble sizes and generally benefits from a relatively larger ensemble.The ensemble size M corresponds to the number of base clusterings and random view groups.
  • Number of anchors: Performance remains consistent as the number of anchors varies from 100 to 1400, with larger anchor sets often beneficial on large-scale datasets.The experiments use p = min{1000, N} anchors.
  • Nearest neighbors: A moderate number of nearest neighbors is often beneficial, and the experiments use K = 5 across all benchmark datasets.The tested range is K = 1 to 10.
  • Random view groups: Random view groups substantially improve performance on most datasets over grouping each single view or all views together.Using all views in one group performs comparably on Yale, but random groups outperform or significantly outperform the alternatives on most other datasets.
  • Time costs: On YTF-200 with 286,006 samples, FastMICE requires 263.81 seconds, while several baselines face heavy computational burdens or out-of-memory errors.More than half of the baseline methods cannot go beyond the ALOI dataset, and some large-scale methods fail on YTF-200 or YTF-400.

5 CONCLUSION AND FUTURE WORK

FastMICE combines random view groups with hybrid early-late fusion and diversity across features, anchors, and neighborhoods to support scalable multi-view clustering without dataset-specific tuning.

  • Conclusion: FastMICE forms random view groups to capture view-wise relationships and performs hybrid early-late fusion.The approach constructs view-sharing bipartite graphs early, then fuses diversified base clusterings into a unified bipartite graph late.
  • Conclusion: Feature-level, anchor-level, and neighborhood-level diversity jointly support efficient construction of view-sharing bipartite graphs.Fast graph partitioning then generates diversified base clusterings for the different view groups.
  • Conclusion: FastMICE has almost linear time and space complexity and performs robustly and accurately across general-scale and large-scale datasets without dataset-specific tuning.The conclusion reports experimental superiority over state-of-the-art methods on 22 multi-view datasets.
  • Future work: The random-view-group and diversification-and-fusion strategy may be investigated for incomplete and deep multi-view clustering in future work.This is presented as a future direction rather than an evaluated result.
Loading 2203.11572v4…