When dealing with real-world datasets, missing values are an inevitable nuisance. The traditional approach to handling this issue is intuitive but flawed: first, fill in the missing values using an imputation algorithm (such as mean substitution, $k$-nearest neighbors, or a generative model), and second, run a clustering algorithm on the completed dataset.
This strategy is known as a decoupled or two-stage pipeline. While simple, it suffers from a fundamental limitation: the imputation step is completely blind to the downstream task. If an imputation model fills in missing features based purely on global data distributions or local smoothness, it risks blurring the very boundaries that separate different clusters. Errors introduced during this blind reconstruction phase propagate downstream, permanently degrading clustering performance.
To overcome this, a major research direction focuses on unifying data recovery and clustering into a single, joint optimization framework. The core insight is that if we know the data belongs to distinct clusters, we can use the emerging cluster structure to guide the imputation of missing values. Conversely, as the imputation becomes more accurate, the cluster boundaries become sharper.
┌──────────────────────────────┐
│ Better Imputation │
└──────────────┬───────────────┘
│
▼
┌──────────────────────────────┐
│ Sharper Cluster Boundaries │
└──────────────┬───────────────┘
│
▼
┌──────────────────────────────┐
│ More Informed Imputation │
└──────────────────────────────┘
The Failure of Decoupled Pipelines
Why exactly does the "impute-then-cluster" pipeline fail? Consider the geometry of high-dimensional data. Clusters typically exist as dense, localized manifolds separated by low-density voids.
When a decoupled imputation method encounters a missing value, it optimizes for a general statistical property, such as minimizing mean squared error across the entire dataset. Geometrically, this pulls the missing point toward the center of the global data cloud. This often lands the point squarely in the void between clusters, or drags it into an incorrect cluster entirely.
As a result, the subsequent clustering algorithm receives data where the true group structures have been ironed out. To prevent this error propagation, the data recovery process must be explicitly tailored to preserve the underlying cluster partitions.
Mechanism 1: Graph and Affinity Matrix Completion
In spectral and subspace clustering, data relationships are captured via an affinity matrix that dictates how strongly data points resemble one another. When data is incomplete, traditional methods build a corrupted graph.
Joint frameworks fix this by forcing graph construction and cluster segmentation to update iteratively. Li et al. demonstrated this with the Structured Sparse Subspace Clustering ($S^3C$) framework, showing that allowing data segmentation to directly inform affinity learning prevents noise from corrupting the graph.
When entire views or features are missing, this concept extends to completing the graph structure itself. Zhuge et al. introduced MSCIG, a framework that integrates similarity matrix completion with spectral embedding into a single optimization problem. By doing so, low-dimensional embeddings directly guide the recovery of missing graph edges, ensuring that the completed graph inherently respects the cluster manifold.
Mechanism 2: Multi-View Tensor Alignment
Multi-view datasets—where samples are observed through multiple distinct lenses, such as text descriptions and accompanying images—frequently suffer from missing views. Decoupled pipelines perform poorly here because they fail to leverage cross-view synergies during the imputation phase.
Incomplete Views Kernel Tensor Completion Downstream Objective
┌───────────┐ ┌───────────┐
│ View 1 ├───┐ ┌───────────────────┐ │ │
└───────────┘ │ │ Low-Rank t-SVD │ │ Optimized │
┌───────────┐ ├─► [Stack Tensor] ──►│ Captures Cross- ├─► [Joint Loss] ─► Joint │
│ View 2 │ │ │ View Structures │ │ Clustering│
└───────────┘ │ └───────────────────┘ │ │
┌───────────┐ │ └───────────┘
│ (Missing) ├───┘
└───────────┘
To capture these relationships, frameworks like IMVTSC-MVI by Wen et al. and LRKT-IMVC by Wu et al. stack incomplete views or kernel matrices into high-order 3D tensors. By applying low-rank constraints (such as tensor singular value decomposition, or t-SVD), these methods capture high-order correlations across all views simultaneously.
Crucially, this tensor completion is optimized alongside the clustering objective. Ding et al. refined this with their HSACC framework, using hierarchical semantic alignment to ensure that even when up to 70% of the views are missing, the cooperative completion process remains strictly constrained by the final grouping goal.
Mechanism 3: Cluster Labels as Imputation Prompts
Perhaps the most direct way to couple these tasks is to use the latent cluster assignments themselves to condition the imputation model.
In the Attribute-Missing Graph Clustering Network (AMGC), the authors treat clustering labels as "prompts" that actively guide feature completion. Instead of guessing a missing attribute based on global averages, the network infers it using the specific profile of its currently assigned cluster.
For sequential data, where missingness can break temporal dependencies, Ma et al. developed CRLI. This framework uses a soft $K$-means objective to shape a latent space while an adversarial strategy ensures realistic imputations, guaranteeing that the generated features are explicitly "cluster-friendly."
Even in tasks that extend beyond pure clustering, such as time-series classification, Cao et al. showed with BRITS that treating missing values as learnable variables within a bidirectional RNN prevents the error propagation inherent to traditional sequential pipelines, aligning the imputation with the ultimate analytical goal.
Why It Works: Geometric Intuition
To see why joint optimization consistently outperforms traditional workflows, look at how missing values are pulled geometrically under different loss functions:
| Imputation Strategy | Optimization Objective | Geometric Effect on Missing Points |
|---|---|---|
| Decoupled (Two-Stage) | Global statistical properties (e.g., variance, global MSE) | Pulled toward the center of the entire data cloud, often landing in low-density voids between clusters. |
| Joint Optimization | Local neighborhood preservation & cluster separation | Constrained to move along the specific, localized manifold of its true cluster. |
By focusing on local sample neighborhoods—as explored by Zhu et al. in their localized kernel clustering approach (LI-MKKM)—joint methods ensure that missing values are filled in without collapsing the distance between distinct groups. The final result is a completed dataset where clusters remain compact, well-separated, and perfectly preserved for downstream analysis.
Key Foundational Work
Melancholic Depression Prediction by Identifying Representative Features in Metabolic and Microarray Profiles with Missing Values (2015) — contributed 1 concept elements to this direction.
Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework (2016) — contributed 1 concept elements to this direction.