Traditional multi-view clustering (MVC) algorithms face a fundamental scaling wall. As Jia-Qi Lin and colleagues note in their literature review, most classic approaches rely on constructing full similarity graphs or kernel matrices. These structures require $O(n^2)$ space and often $O(n^3)$ time for eigen-decomposition, where $n$ is the number of samples. In an era of million-sample datasets, these cubic and quadratic costs are prohibitive.
To break this bottleneck, a new generation of research focuses on anchor-based representations and late fusion strategies. These methods reduce complexity from cubic to linear ($O(n)$), allowing multi-view analysis to scale to hundreds of thousands of samples on standard hardware.
The Anchor Paradigm: From $n \times n$ to $n \times m$
The core intuition behind scalable MVC is to avoid comparing every data point to every other data point. Instead, researchers like Qianyao Qiang and Feiping Nie in FMDC utilize a small set of $m$ "anchors"—representative points that summarize the data distribution.
By constructing a bipartite graph between $n$ samples and $m$ anchors (where $m \ll n$), the complexity of graph construction drops to $O(nm)$. This transition transforms the problem from a dense $n \times n$ affinity matrix to a sparse, rectangular representation. Yi Wen and Siwei Wang demonstrate in EMVGC-LG that this approach can preserve both local and global structures while maintaining linear scalability.
Aligning the Anchors
A significant challenge in anchor-based methods is that anchors learned independently for different views (e.g., image features vs. text tags) may not correspond to each other. This is known as the "Anchor-Unaligned Problem."
Jiaqi Jin and Xinwang Liu addressed this in FMVACC by introducing a matching correspondence step. By aligning these representative points across views before fusion, the model ensures that the consensus representation is built on a shared structural foundation. Similarly, Shengju Yu proposed NpGC, a non-parametric framework that uses a dual-anchor strategy to capture both view-specific and shared characteristics without requiring manual hyper-parameter tuning.
Late Fusion and One-Pass Optimization
Beyond graph reduction, researchers have optimized the fusion process itself. Traditional "early fusion" combines raw features or kernels, which is computationally heavy. "Late fusion" instead aligns the partition results (the cluster assignments) of each view.
Siwei Wang and En Zhu showed in MVC-LFA that maximizing the alignment between individual view partitions and a global consensus can achieve state-of-the-art accuracy with linear complexity.
This was further refined into "one-pass" methods. In OP-LFMVC, Xinwang Liu and colleagues collapsed the traditional two-step process—learning a consensus matrix and then running K-means—into a single optimization problem. This eliminates the need for expensive post-processing and ensures that the learned representation is directly optimized for the final clustering task.
Handling Messy, Large-Scale Data
Real-world large-scale data is rarely perfect; views are often missing or unaligned.
- Incomplete Views: Siwei Wang introduced IMVC-CBG, which uses a consensus bipartite graph to handle missing data views in datasets exceeding 100,000 samples.
- Unpaired Data: For cases where we don't know which sample in View A matches which sample in View B, the FUMC framework uses inverse local manifold learning and bipartite matching to achieve nearly $O(n)$ complexity for fully unpaired data.
By shifting from global sample-to-sample relationships to local sample-to-anchor relationships, these researchers have transformed multi-view clustering from a boutique technique for small datasets into a robust tool for large-scale data analysis.