In image restoration, total variation (TV) is a hand-crafted regularizer that penalizes the absolute differences between neighbouring pixels. It is usually criticized because it makes images piecewise constant: smooth regions become flat plateaus with sharp steps between them, an artifact called "staircasing." We propose to use that same behaviour deliberately on a different object. Instead of penalizing differences between neighbouring pixels, we penalize differences between neighbouring data rows on a nearest-neighbour graph of samples. When missing entries are filled in under this penalty, similar rows are pulled toward shared values and dissimilar groups stay separated by sharp steps. For images this is a defect. For clustering it is exactly the structure we want.
The concrete proposal is to fill in an incomplete table in two alternating steps. In the first step, a GAIN-style adversarial imputer proposes values for the missing cells. GAIN is a generative adversarial network in which a discriminator guesses, entry by entry, which cells were really observed, and a "hint" vector tells it part of the true missingness mask. In the second step, an exact convex graph-TV step fuses rows toward cluster-wise shared values. Rows that end up fused are read out directly as clusters, and sweeping the TV strength traces out a hierarchy, so the number of clusters $K$ does not have to be known in advance. The question we test is whether this explicit, hand-crafted, cluster-shaped prior repairs the known failure of likelihood-driven imputation, which is to smooth away the rare patterns that separate clusters. We also ask whether the adversarial component still earns its place once the prior is present.
Core Claim
Imputers trained only to produce plausible values drift toward high-density modes and blur cluster boundaries. What's a good imputation to predict with missing values? and Unsupervised Anomaly Detection in The Presence of Missing Values show that optimizing purely for statistical plausibility pushes boundary samples into the bulk. Our claim is that the missing ingredient is a prior on how samples relate to one another, not a better model of each row taken alone.
We treat imputation as an inverse problem in the sense of Learning Proximal Operators. The measurement operator is the observation mask. The regularizer is a sum-of-norms penalty over edges of a sample graph:
$$\min_{Z}\; \tfrac12\|M\odot(Z - Y)\|_F^2 \;+\; \lambda \sum_{(i,j)\in E} w_{ij}\,\|z_i - z_j\|_2 .$$
Here $Y$ is the data matrix, $M$ is the binary mask of observed cells, $\odot$ is elementwise product, $z_i$ is the completed row for sample $i$, $E$ is a k-nearest-neighbour edge set with weights $w_{ij}$, and $\lambda$ sets how strongly neighbours fuse. For a fixed graph this problem is convex, so the step that decides clusters has a unique solution. That contrasts with the non-convexity that the file flags for learned inverse-problem priors.
The weak point is the graph itself. At 70–90% missingness, neighbours computed from the observed cells alone are unreliable. This is where the adversarial imputer contributes: it supplies completions from which a better graph can be built. The prediction we will test is specific. Graph TV alone should match the full method at low missingness under missing-completely-at-random (MCAR) conditions. The adversarial graph refresh should matter mainly at high missingness and under missing-at-random (MAR) and missing-not-at-random (MNAR) mechanisms, where observed-cell distances are biased.
Relation to Prior Work
Methods we reuse. GAIN supplies the hint-guided entrywise discriminator. Its equilibrium result recovers the conditional distribution of each row, under MCAR, but says nothing about relations between rows; we add those relations. The proximal-splitting view of Learning Proximal Operators lets the data-fidelity step and the prior step be handled separately. Our prior step differs from theirs because it is an exact convex operator rather than a pretrained denoiser. Adversarial Regularizers in Inverse Problems, Total Deep Variation and Deep Image Prior motivate the whole line: all three replace TV because staircasing damages natural images. Adversarial Regularizers, for example, reports 26.3 dB for TV versus 28.2 dB for its learned critic on BSDS500 denoising. We invert that lesson. On a sample graph, the piecewise-constant bias of TV encodes the clustering hypothesis.
Closest existing work. Clustering-Oriented Generative Attribute Graph Imputation (CGIR) combines GAN imputation with clustering, but it needs an intact, given graph, and its number of subclusters is tied to the known class count. We build the graph from the data being imputed and obtain $K$ from the fusion path. Incomplete Multi-view Deep Clustering with Data Imputation and Alignment (IMDC-DIA) imputes missing views with deterministic decoders plus a linear alignment loss, and does not evaluate how good its imputations are. We use an adversarial imputer and report imputation error alongside clustering. DICE applies the plug-and-play idea to clustering single-cell data, but it assumes a linear PCA subspace and Gaussian noise and has no explicit mask. Our fidelity term is the mask itself.
Competing paradigm we must answer. CARD skips imputation entirely and diffuses structure over an anchor graph. It is the main threat to the premise that imputing helps at all.
Output format. FDC-LGL motivates producing discrete cluster assignments directly rather than rounding a relaxed solution. Fused rows give us that for free. Deep Plug-and-Play Clustering with Unknown Number of Clusters infers $K$ with split and merge thresholds. The $\lambda$ path is our analogue, but it lives in the imputation objective rather than in a separate module.
Research Program
The loop. We build an alternating procedure with three steps.
- A GAIN generator receives the observed cells, the mask, and the current fused estimate $Z$ as an extra input. It is trained with three terms: the hint-discriminator loss, reconstruction error on observed cells, and a proximity term pulling its output toward $Z$.
- A k-nearest-neighbour graph is rebuilt on the generator's completions. To keep cost near linear, we use anchor approximations of the kind CARD and FDC-LGL rely on.
- $Z$ is updated by solving the graph-TV problem above exactly with ADMM (the alternating direction method of multipliers). The observed-cell fidelity term keeps measured values fixed in the limit.
We iterate until the fused partition stops changing.
Mixed-type data. For categorical columns we reuse the relaxation of Categorical EHR Imputation with Generative Adversarial Nets. The TV term then acts on the relaxed one-hot encodings.
Choosing λ without labels. We hide an additional 10% of the observed cells and select $\lambda$ by imputation error on those held-out cells, combined with partition stability across bootstrap resamples. No labels are touched at any point.
Analysis. We will measure the price of staircasing directly: how much within-cluster variance the TV step erases, and what that costs in imputation root mean squared error (RMSE). Imputation RMSE and clustering accuracy are reported side by side for every method so that the trade-off cannot hide.
Baselines
Naive reference points. The do-nothing baseline is zero or mean imputation followed by k-means. The second naive baseline is complete-case deletion followed by k-means. On Breast Cancer at 70% missingness, AnyNets reports clustering accuracy 0.621 for zero imputation, which gives a floor.
Strongest tabular competitor. This is AnyNets itself. It encodes each record as a set of observed features and never imputes. It reports clustering accuracy 0.913 on Breast Cancer at 70% missingness. We run it under its own protocol (Breast Cancer and Thyroid, 10–70% artificial missingness) with the same masks as our method. Beating it means exceeding 0.913 at 70% on Breast Cancer, averaged over mask seeds.
Strongest multi-view competitor. This is IMDC-DIA, run from its released code, IMDC-DIA-code_release. It reports about 88% accuracy on HandWritten at 90% missingness. For multi-view data we concatenate the views and treat each missing view as a block of missing cells. Beating it means clearing roughly 88% at 90% missingness on HandWritten; matching it while also giving lower imputation error on held-out cells is a secondary success.
Imputation-free competitor. CARD is run on the same HandWritten and Caltech5V masks. No per-dataset reported result was found on Lacuna for CARD, so we will rerun it ourselves.
Two-stage imputation pipelines. These are GAIN, RefiDiff (reported only as best or second-best and about 4x faster than DIFFPUTER; no per-dataset metric numbers were found on Lacuna), MICE, and MissForest, each followed by k-means with oracle $K$. They receive the same hyperparameter search budget in GPU-hours as our method, and every method uses identical masks.
Ablations. Two ablations isolate the key ingredients. The first is graph TV alone, with the graph built from observed-cell distances and no adversarial step. The second is GAIN combined with a plain Laplacian (squared-difference) penalty in place of TV. This second ablation isolates whether the non-smooth, fusing part of TV is what produces the gains, rather than smoothing in general.
Why not just…?
Why not just impute with GAIN or RefiDiff and then cluster? Two-stage pipelines optimize plausibility row by row. The cited analyses of prediction-oriented imputation show that this smears boundary samples into dense modes. Our two-stage baselines test this directly. If they match our clustering accuracy at 70–90% MAR and MNAR missingness, the core claim fails.
Why not just use the convex graph-TV problem and drop the GAN? This is the most serious threat, and we expect it to win at low MCAR missingness. The experiment that settles it is the "graph TV alone" ablation swept over missingness rate and mechanism. If the adversarial graph refresh gives no gain even at 90% missingness or under MNAR, we will report the simpler convex method as the result and discard the adversarial part.
Why not just skip imputation, as CARD and AnyNets do? Both methods discard feature values that downstream users often need. AnyNets is also reported to be sensitive to small sample sizes. Still, if they cluster better, completion is not buying accuracy. For that reason both are head-to-head baselines, and we report imputed-value quality as a separate deliverable instead of claiming it improves clustering.
Why not just add a clustering loss to the imputer, as CGIR does? A contrastive or centroid loss needs $K$ fixed in advance, and CGIR's version needs a given graph. The Laplacian-penalty ablation, plus a variant of GAIN with a k-means centroid loss at oracle $K$, will show whether the fusing penalty adds anything beyond "any clustering-aware term."
Proposed Experiments
Tabular data. We use the RefiDiff datasets that carry class labels (Letter, Bean, Gesture, Adult) and the GAIN UCI sets (Breast Cancer, Letter). Masks cover MCAR, MAR, and MNAR at 30%, 50%, 70%, and 90%, with ten mask seeds each. Metrics are clustering accuracy, normalized mutual information (NMI), and adjusted Rand index (ARI) against class labels, together with RMSE on held-out cells. As a sanity check against GAIN's reported AUROC of 0.9711 on News, we also run downstream logistic regression.
Multi-view data. We use HandWritten, Caltech5V, Flower17, and MSRCV1 under the IMDC-DIA protocol, with 10–90% missing views.
Decisive checks. Four results decide the outcome.
- Clustering at high missingness. Does the full method beat both AnyNets (0.913 on Breast Cancer at 70%) and GAIN-then-k-means?
- Where the adversarial step matters. Does the gap between the full method and graph TV alone grow with missingness rate and under MNAR, as predicted? A flat gap would falsify the role we claim for the adversarial refresh.
- Fusion versus smoothing. Does TV beat the squared-difference Laplacian penalty? If not, the staircasing argument is wrong.
- Unknown K. Does the $\lambda$ path, selected only by held-out-cell error, recover the true $K$ within ±1 on most datasets? This matters because the baselines are given oracle $K$.
References
- What’s a good imputation to predict with missing values?
- Unsupervised Anomaly Detection in The Presence of Missing Values
- Learning Proximal Operators: Using Denoising Networks for Regularizing Inverse Imaging Problems
- GAIN: Missing Data Imputation using Generative Adversarial Nets
- Adversarial Regularizers in Inverse Problems
- Total Deep Variation for Linear Inverse Problems
- Deep Image Prior
- Clustering-Oriented Generative Attribute Graph Imputation
- Incomplete Multi-view Deep Clustering with Data Imputation and Alignment
- Clustering by Denoising: Latent plug-and-play diffusion for single-cell embeddings
- Contractive Anchor Resolvent Diffusion for Incomplete Multi-View Clustering
- FDC-LGL: Fast Discrete Clustering with Local Graph Learning for Large-Scale Datasets
- Deep Plug-and-Play Clustering with Unknown Number of Clusters
- Categorical EHR Imputation with Generative Adversarial Nets
- AnyNets: Adaptive Deep Neural Networks for Medical Data with Missing Values