Abstract
Multi-view clustering (MVC) integrates diverse data sources to improve grouping accuracy but often suffers from prohibitive computational costs and suboptimal discretization steps. This paper introduces Fast Multi-view Discrete Clustering (FMDC), a framework that achieves linear-time complexity $O(n)$ by leveraging anchor graphs and direct discrete optimization. Experiments on large-scale datasets demonstrate that FMDC significantly outperforms state-of-the-art methods in both accuracy and efficiency.
Introduction
Multi-view clustering (MVC) is essential for modern data analysis where samples are described by multiple feature sets, such as image pixels and textual tags. However, traditional graph-based MVC methods face two critical hurdles. First, the $O(n^2)$ or $O(n^3)$ computational complexity of building full similarity graphs and performing eigen-decomposition makes them unscalable for large datasets. Second, the "discretization gap"—where continuous spectral solutions are post-processed via $k$-means—often leads to suboptimal cluster assignments that deviate from the original objective.
The FMDC Framework
FMDC addresses these issues through a three-pronged approach:
- Anchor-Based Graph Construction: Instead of an $n \times n$ matrix, FMDC generates $m$ representative anchors ($m \ll n$) using a modified Balanced K-means based Hierarchical K-means (BKHK) with $k$-means++ initialization. This results in a sparse $n \times m$ anchor graph, reducing storage and computation to linear scales.
- Direct Discrete Optimization: FMDC bypasses continuous relaxation by directly optimizing the discrete cluster assignment matrix $Y$. This unified objective function incorporates both RatioCut and Normalized Cut principles, staying closer to the actual clustering goal.
- Automated View Weighting: The model learns an optimal weight for each view, automatically prioritizing informative sources while mitigating the impact of noisy or irrelevant data.
Experimental Evaluation
The authors evaluated FMDC against six benchmark datasets, including large-scale sets like NUS-WIDE (20,721 samples) and Reuters2 (15,000 samples).
Key Results
- Superior Accuracy: FMDC consistently reached the highest metrics across nearly all tested datasets. For instance, on the WebKB dataset, it achieved an ACC of 0.9657, outperforming all competitors.
- Efficiency and Scalability: The linear-time complexity provides massive speedups. On the Reuters2 dataset, FMDC completed in approximately 25 minutes (1,537s), whereas competing methods like MVGL required over 72 hours. Furthermore, FMDC avoided the "Out-of-Memory" errors that plagued other state-of-the-art methods on large datasets.
- Rapid Convergence: The iterative optimization typically converges in fewer than 10 iterations, ensuring practical utility for real-world applications.
Conclusion
FMDC represents a significant advancement in multi-view clustering by providing a linear-time solution that does not sacrifice accuracy. By solving the primal discrete problem directly on anchor graphs, it bridges the gap between theoretical optimality and large-scale applicability. While the method is sensitive to the initial number of anchors, it remains a robust and highly efficient choice for modern high-dimensional data clustering.
Summary updated