Multi-view clustering (MVC) aims to group data points by integrating information across multiple distinct modalities or "views"—such as clustering web pages based on both their text content and their inbound hyperlinks. Traditional graph-based and spectral multi-view clustering methods achieve high accuracy by constructing a full sample-to-sample similarity matrix for each view.
However, this approach hits a hard computational wall. For a dataset with $n$ samples, a full similarity graph requires $O(n^2)$ space to store and $O(n^3)$ time to compute spectral decompositions. When $n$ scales to hundreds of thousands or millions, these algorithms suffer from out-of-memory errors and prohibitive execution times.
To bypass this bottleneck, a powerful paradigm has emerged: anchor-based multi-view clustering. By replacing dense sample-to-sample graphs with sparse sample-to-anchor bipartite graphs, this approach reduces both time and space complexity to a linear relationship with the number of samples ($O(n)$), enabling multi-view clustering to scale to massive datasets.
The Core Mechanism: Bipartite Anchor Graphs
The fundamental intuition behind anchor-based scaling is that we do not need to compare every data point to every other data point to understand the global geometry of a dataset. Instead, we can select a small set of $m$ representative points, called anchors (where $m \ll n$), to serve as landmarks across the data space.
Traditional Graph (O(n²)):
[Sample 1] <---> [Sample 2] <---> [Sample 3] ... <---> [Sample N]
Anchor-Based Bipartite Graph (O(nm)):
[Sample 1] ----\
[Sample 2] ----+---> [Anchor 1]
[Sample 3] ----/
[Sample 4] ----+---> [Anchor 2]
... /
[Sample N] ---/
Instead of constructing an $n \times n$ similarity matrix, anchor-based methods construct an $n \times m$ matrix $\mathbf{B}$, which forms a bipartite graph between the $n$ samples and the $m$ anchors.
- Each row $i$ in $\mathbf{B}$ represents a sample's similarity to the $m$ anchors.
- This $n \times m$ matrix effectively serves as a low-rank approximation of the full $n \times n$ graph.
- If two samples share similar connection patterns to the same set of anchors, they are implicitly close to each other in the underlying data manifold.
By fusing these $n \times m$ bipartite graphs across multiple views, algorithms can learn a shared consensus representation or directly generate cluster partitions. As shown by Han Lu et al. in Centerless Multi-View K-means Based on the Adjacency Matrix, this optimization allows multi-view integration to scale linearly, making it possible to process large-scale datasets that would otherwise crash standard spectral or graph-based clustering methods.
Resolving the Anchor Alignment Problem
While anchor graphs solve the scalability issue, they introduce a new challenge when applied to multi-view data: anchor misalignment. If anchors are selected independently for each view (for example, by running K-means on each view's feature space separately), the $j$-th anchor in View 1 will not correspond to the $j$-th anchor in View 2. Stacking or fusing unaligned $n \times m$ matrices results in a structural mismatch that degrades clustering performance.
To fix this "Anchor-Unaligned Problem," Jiaqi Jin et al. developed a framework in Align then Fusion: Generalized Large-scale Multi-view Clustering with Anchor Matching Correspondences that aligns independently learned anchor sets using both feature and structural information before performing cross-view fusion.
Similarly, Yi Wen et al. proposed Scalable Incomplete Multi-View Clustering with Structure Alignment, which introduces a dedicated structure alignment module to map disparate anchor spaces into a unified coordinate system while strictly preserving linear time complexity.
Rather than aligning anchors post-hoc, another strategy is to learn a single, shared set of anchors directly from the data. For instance, Siwei Wang et al. in Highly-efficient Incomplete Largescale Multiview Clustering with Consensus Bipartite Graph bypass the alignment step entirely by optimizing a single consensus bipartite graph across all views simultaneously.
Optimizing Anchor Geometry
The performance of an anchor-based algorithm depends heavily on the quality of its anchors. If the anchors are poorly distributed, redundant, or concentrated in a single dense region of the data space, the bipartite graph will fail to capture the true boundaries between clusters.
Recent work focuses on mathematically enforcing desirable geometric properties on the anchor selection process:
- Diversity and Balance: Pei Zhang et al. introduced the MAGIC framework in Max-Mahalanobis Anchors Guidance for Multi-View Clustering, which utilizes fixed geometric anchors optimized for diversity, balance, and compactness. This ensures that anchors are uniformly distributed across the data manifold, preventing non-uniform sampling issues.
- Semantic Structure: Chao Zhang et al. proposed CAMVC in Learning Cluster-Wise Anchors for Multi-View Clustering, which forces a specific cluster-wise structure onto the anchors themselves. This ensures that the anchors are not just geometric landmarks, but semantically meaningful representations of the underlying clusters.
- Deep Learnable Anchors: Moving beyond static selection methods like K-means or random sampling, Xuelong Li et al. developed DMAC in Towards Learnable Anchor for Deep Multi-View Clustering, which treats anchors as continuous, learnable parameters within a deep neural network, optimizing them end-to-end alongside the data representations.
Handling Incomplete and Unpaired Views
In real-world applications, multi-view data is rarely perfect; datasets frequently suffer from missing views (e.g., a patient might have an MRI scan but lack a corresponding CT scan). Anchor graphs provide an elegant mechanism for handling these incomplete scenarios without requiring computationally expensive data imputation in the original high-dimensional feature space.
Because the anchor graph maps samples to a lower-dimensional latent space, missing values can be handled directly at the similarity level. For example, Chao Zhang developed the ASCR framework in Fast Incomplete Multi-view Clustering with Adaptive Similarity Completion and Reconstruction, which unifies anchor-based graph learning and missing-similarity completion into a single optimization step.
Furthermore, Shengju Yu demonstrated in A Non-parametric Graph Clustering Framework for Multi-View Data that fusing information at the anchor level rather than the graph level allows algorithms to maintain linear scalability even when dealing with highly irregular, large-scale multi-view distributions.
By decoupling the complexity of the graph from the total number of samples, anchor-based methods transform multi-view clustering from a computationally prohibitive task into a highly scalable, linear-time operation capable of processing millions of real-world data points.