One-pass Multi-view Clustering for Large-scale Data

Jiyuan Liu, Xinwang Liu, Yuexiang Yang, Li Liu, Siqi Wang, Weixuan Liang, Jiangyong ShiICCV 2021 · OpenReview

Abstract

Existing non-negative matrix factorization based multi-view clustering algorithms compute multiple coefficient matrices respect to different data views, and learn a common consensus concurrently. The final partition is always obtained from the consensus with classical clustering techniques, such as k-means. However, the non-negativity constraint prevents from obtaining a more discriminative embedding. Meanwhile, this two-step procedure fails to unify multi-view matrix factorization with partition generation closely, resulting in unpromising performance. Therefore, we propose an one-pass multi-view clustering algorithm by removing the non-negativity constraint and jointly optimize the aforementioned two steps. In this way, the generated partition can guide multi-view matrix factorization to produce more purposive coefficient matrix which, as a feedback, improves the quality of partition. To solve the resultant optimization problem, we design an alternate strategy which is guaranteed to be convergent theoretically. Moreover, the proposed algorithm is free of parameter and of linear complexity, making it practical in applications. In addition, the proposed algorithm is compared with recent advances in literature on benchmarks, demonstrating its effectiveness, superiority and efficiency.

Introduction

In the era of big data, information is frequently collected from multiple sources or "views," such as image pixels and associated text tags. Multi-view Clustering (MvC) aims to integrate these diverse views to uncover underlying patterns. However, traditional methods based on Non-negative Matrix Factorization (NMF) face three critical challenges:

  1. The Two-Step Gap: Most methods factorize data first and then apply a separate clustering algorithm (like $k$-means). This lack of integration means the factorization process is not optimized for the final clustering task.
  2. Constraint Limitations: The strict non-negativity constraint in NMF can hinder the model's ability to learn distinct, discriminative features.
  3. Scalability: Advanced graph-based methods often suffer from $O(n^2)$ or $O(n^3)$ complexity, making them unusable for large-scale datasets.

To overcome these hurdles, we introduce OPMC (One-pass Multi-view Clustering), a unified framework that eliminates non-negativity constraints and optimizes factorization and partition generation simultaneously.

Methodology

OPMC addresses the limitations of traditional MvC through a "one-pass" unified objective function. Instead of treating factorization and clustering as sequential steps, OPMC performs them concurrently, allowing the generated clusters to provide immediate feedback to the factorization process.

The OPMC framework unifying partition generation and multi-view matrix factorization.

Key innovations of the OPMC framework include:

  • Unified Objective: The model optimizes a single objective where the "hard partition" (cluster assignments) guides the factorization to produce more discriminative embeddings.
  • Constraint Relaxation: By removing the non-negativity constraint on coefficient and base matrices, the search space is expanded, enabling the discovery of more descriptive features.
  • Matrix Approximation: The coefficient matrix ($H$) is approximated as the product of a hard partition matrix ($Y$) and a centroid matrix ($C$), embedding clustering logic directly into the mathematical factorization.
  • Linear Complexity: The algorithm maintains a complexity of $O(kdn)$, where $n$ is the number of samples. This linear scalability allows OPMC to handle hundreds of thousands of data points efficiently.

Experiments and Results

The algorithm was rigorously evaluated on six diverse multi-view benchmarks, ranging from the 2,000-sample HandWritten dataset to the 101,499-sample YtVideo dataset.

Clustering accuracy (ACC) comparison on the HandWritten dataset.

Experimental results highlight OPMC's advantages:

  • Superior Accuracy: OPMC consistently outperformed state-of-the-art baselines. For instance, on the HandWritten dataset, OPMC (labeled as OMCmf in figures) achieved approximately 90% accuracy, compared to roughly 61% for standard NMF.
  • Massive Speedup: OPMC is 5 to 10 times faster than Orthogonal NMF (ONMF). On the AwA dataset, OPMC finished in 1,474 seconds, while competing methods took over 15,000 seconds or failed due to memory constraints.
  • Parameter-Free Operation: Unlike deep learning or graph-based methods that require extensive hyperparameter tuning, OPMC is essentially parameter-free, making it highly practical for unsupervised real-world applications.

Conclusion

OPMC provides a highly efficient, linear-complexity solution for large-scale multi-view clustering. By unifying factorization and partition generation into a single pass and relaxing traditional constraints, it achieves state-of-the-art accuracy and scalability. Future work may explore the integration of these one-pass principles into deep learning architectures and the use of soft partitioning for ambiguous data points.

Summary updated

Abstract

Existing non-negative matrix factorization based multi-view clustering algorithms compute multiple coefficient matrices respect to different data views, and learn a common consensus concurrently. The final partition is always obtained from the consensus with classical clustering techniques, such as k-means. However, the non-negativity constraint prevents from obtaining a more discriminative embedding. Meanwhile, this two-step procedure fails to unify multi-view matrix factorization with partition generation closely, resulting in unpromising performance. Therefore, we propose an one-pass multi-view clustering algorithm by removing the non-negativity constraint and jointly optimize the aforementioned two steps. In this way, the generated partition can guide multi-view matrix factorization to produce more purposive coefficient matrix which, as a feedback, improves the quality of partition. To solve the resultant optimization problem, we design an alternate strategy which is guaranteed to be convergent theoretically. Moreover, the proposed algorithm is free of parameter and of linear complexity, making it practical in applications. In addition, the proposed algorithm is compared with recent advances in literature on benchmarks, demonstrating its effectiveness, superiority and efficiency.
BibTeX
@inproceedings{liu2021one,
  author = {Jiyuan Liu and Xinwang Liu and Yuexiang Yang and Li Liu and Siqi Wang and Weixuan Liang and Jiangyong Shi},
  title = {{One-pass Multi-view Clustering for Large-scale Data}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2021},
  url = {https://openreview.net/forum?id=5pMGkmCiScd},
}
Figure