Multi-view clustering aims to group data points by integrating information from multiple distinct sources or modalities—such as combining an image's visual features, textual tags, and audio descriptions. Traditionally, the most powerful way to capture the complex, non-linear relationships within these views has been graph-based or spectral clustering.
However, these traditional approaches hit a hard computational wall when scaled to large datasets. As noted by Jie Xu et al. in their work on Multi-VAE, graph-based multi-view clustering algorithms typically suffer from quadratic $O(n^2)$ or cubic $O(n^3)$ computational complexity relative to the number of data points $n$. This scaling behavior stems from the need to construct full $n \times n$ similarity matrices and perform expensive eigen-decompositions on them. If a dataset contains 100,000 samples, a single full similarity matrix requires 10 billion entries—leading to severe memory overhead and computational bottlenecks.
To solve this scalability crisis, a prominent research direction replaces full data graphs with compact anchor graphs, reducing the computational complexity from quadratic or cubic down to strictly linear $O(n)$.
The Core Intuition: From Full Graphs to Bipartite Matrices
To understand why anchor graphs work, consider how a traditional graph models a dataset. In a standard similarity graph, every data point is a node, and every pair of nodes shares an edge weighting their similarity. This creates an $n \times n$ matrix.
Anchor-based methods break this bottleneck through a simple realization: you do not need to compare every data point to every other data point to understand the global geometry of the data. Instead, you can select a small set of $m$ representative points called anchors (where $m \ll n$).
Instead of building an $n \times n$ graph, the algorithm constructs an $n \times m$ bipartite graph. In this graph, edges only exist between data points and anchors, never between data points themselves.
Traditional Graph (n x n) Anchor Graph / Bipartite Graph (n x m)
[Point 1] --- [Point 2] [Point 1] \ / [Anchor 1]
| | [Point 2]
[Point 3] --- [Point 4] [Point 3] / \ [Anchor 2]
Mathematically, this $n \times m$ matrix acts as a low-rank approximation of the full data manifold. As Qianyao Qiang et al. demonstrate with Fast Multi-view Discrete Clustering with Anchor Graphs, performing matrix operations and label propagation on this smaller bipartite structure bypasses the need for full eigen-decomposition. The complexity drops to linear with respect to the number of samples, allowing algorithms to effortlessly process large-scale datasets.
Resolving the Anchor Alignment Problem
While anchor graphs solve the scalability problem for a single view, integrating them across multiple views introduces a unique challenge: anchor unalignment.
If you generate anchors for View A (e.g., image pixels) and View B (e.g., text tags) independently using standard techniques like k-means, the resulting anchor sets will inhabit entirely different feature spaces. Anchor #1 in View A will not correspond to Anchor #1 in View B. Fusing these unaligned matrices directly would distort the underlying data relationships.
To address this, Jiaqi Jin et al. introduced the FMVACC framework. Their approach aligns independently learned anchor sets across different views using both feature and structural information before performing cross-view fusion. By establishing explicit anchor matching correspondences, they ensure that the consensus representation preserves geometric consistency across all modalities.
Alternatively, instead of forcing strict alignment after the fact, some frameworks alter how anchors capture information. Shengju Yu et al. propose a non-parametric framework (NpGC) that utilizes a dual-anchor strategy. This strategy simultaneously maintains anchors dedicated to capturing view-specific features and anchors dedicated to capturing view-common features, allowing the model to scale linearly while preserving the unique nuances of each data source.
Bypassing Post-Processing with Direct Label Optimization
In traditional spectral clustering, obtaining the final cluster assignments requires a multi-step pipeline: first, you learn a continuous low-dimensional embedding, and then you run an entirely separate clustering algorithm (like K-means) on those embeddings. For massive datasets, this secondary post-processing step can still introduce significant computational lag.
To create a truly streamlined linear pipeline, researchers have focused on directly optimizing for discrete cluster labels within the anchor graph framework. For example, Zhenwen Ren proposes SMGC, which introduces a priori anchor label supervision. This technique ensures that the representative anchors are distributed uniformly and discriminatively across the target clusters, preventing the non-uniform sampling issues that often degrade standard anchor selection. By directly mapping the bipartite graph to discrete cluster labels, the method eliminates the need for continuous embedding post-processing entirely.
Scaling to Imperfect and Incomplete Data
In real-world applications, large-scale multi-view data is rarely pristine. Often, datasets suffer from missing views—such as a patient dataset where some individuals have MRI scans but lack corresponding genetic profiles.
Standard incomplete multi-view clustering methods often attempt to impute the missing data back into full-scale kernel or similarity matrices, which re-introduces quadratic or cubic overhead. To maintain scalability, the anchor paradigm shifts the imputation process into the compact anchor space.
Siwei Wang et al. developed a highly efficient framework for this scenario, known as IMVC-CBG. Instead of imputing raw data or massive matrices, their method learns a shared, consensus set of anchors across the incomplete views to form a unified consensus bipartite graph. Because the optimization scales linearly with the number of samples, the framework can successfully cluster incomplete datasets containing over 100,000 samples without exceeding hardware memory limits.