🤖 machine learning

Rethinking Incompleteness: Formalizing Protocol Divergence and Train-Once Learning for Robust IMVC

This paper identifies a critical flaw in standard Incomplete Multi-View Clustering (IMVC) evaluation where identical missing rates can mask vastly different data structures, and proposes CRAFT, a novel architecture that achieves robust, train-once learning by shifting the burden of handling missing data from the loss function to the model design.

Original authors: Haolu Liu, Xiyue Wang, Xuanting Xie, Liangjian Wen, Zhao Kang

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haolu Liu, Xiyue Wang, Xuanting Xie, Liangjian Wen, Zhao Kang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Missing Puzzle" Trap

Imagine you are trying to solve a giant jigsaw puzzle, but some pieces are missing. In the world of AI, this is called Incomplete Multi-View Clustering (IMVC). Imagine you have photos of a cat taken from different angles (front, side, top). Sometimes, the "front" photo is missing, or the "top" one is blurry. The AI's job is to group these photos into the right categories (e.g., "Cat," "Dog," "Bird") even when some pictures are incomplete.

For years, researchers have been trying to solve this by building a special "repair shop" for each specific type of missing piece.

The Old Way: If you are missing 10% of the "front" photos, you train a specific AI model for that. If you are missing 30% of the "side" photos, you train a completely different model. If the missing pattern changes slightly, you have to throw away the old model and build a new one.
The Paper's Discovery: The authors found that this "build a new model for every scenario" approach is hiding a massive flaw. They discovered that two scenarios that look like they have the same amount of missing data can actually be completely different underneath.

The Hidden Trap: "The Complete Sample" Count

The authors introduced a new way to measure missing data. Instead of just asking, "How many pieces are missing?" they asked, "How many samples have at least two pieces?"

Think of it like a group of people trying to solve a mystery.

Scenario A: Everyone is missing one clue, but everyone still has two other clues. They can talk to each other and solve it.
Scenario B: Everyone is missing one clue, but for half the group, they are missing all their clues except one. These people are stuck; they have nothing to compare their one clue against.

The paper calls this the "Complete-Sample Proportion" ( $p_c$ ). They found that existing AI methods rely entirely on people who have at least two clues to learn how to solve the mystery. If the number of people with two clues drops below a tiny threshold (about 1%), the AI's "learning signal" vanishes. It's like trying to teach a class when 99% of the students have their textbooks ripped out; the teacher (the AI) stops learning and starts guessing randomly.

The authors proved that many current AI models crash and burn in these "Scenario B" situations, even if the total amount of missing data looks the same as a successful scenario.

The Solution: CRAFT (The "Universal Translator")

To fix this, the authors built a new AI architecture called CRAFT (Complete-data Robust Attention-masked Fusion Transformer).

Instead of trying to "repair" the missing pieces (which requires having a complete set to learn from), CRAFT changes the rules of the game:

It ignores the missing pieces entirely: Instead of guessing what a missing photo looks like, CRAFT simply says, "Okay, we don't have that photo. Let's just look at the ones we do have."
It works like a smart team huddle: Imagine a team meeting where everyone raises their hand to speak. If someone is missing, the team leader (the AI) simply doesn't call on them. The meeting continues smoothly with whoever is present.
Train Once, Use Everywhere: Because CRAFT doesn't rely on having a "perfect" set of data to learn the rules, you only need to train it once on perfect data. After that, you can throw it into any situation—whether 10% or 90% of the data is missing, or the missing pattern is weird—and it just works.

The Results: One Model vs. Sixteen Models

The authors tested this on seven different datasets (like groups of images or handwritten digits).

The Old Way: To test 16 different missing-data scenarios, researchers had to train 16 separate models. This takes a huge amount of time and computer power.
CRAFT: They trained one single model. This one model handled all 16 scenarios perfectly.

The Payoff:

Speed: CRAFT reduced the training time by 8.8 times.
Reliability: While the old models crashed when the data got too sparse (the "danger zone" where $p_c < 1\%$ ), CRAFT kept working, maintaining high accuracy even when the data was very incomplete.

The Takeaway

The paper argues that the field of AI has been focusing on the wrong thing. We've been trying to build better "repair tools" for missing data, but the real issue is the architecture itself. By designing a system that naturally handles missing information (like a conversation that continues even if someone leaves the room), we can make AI that is robust, faster to train, and doesn't need to be retrained every time the data changes.

In short: Don't try to fill in the blanks; just learn to read the page with the blanks already there.

Technical Summary: Rethinking Incompleteness in IMVC

Problem Definition
Incomplete Multi-View Clustering (IMVC) addresses the challenge of clustering data where views (modalities) are missing for subsets of samples. The dominant paradigm in current IMVC research relies on cross-view reconstruction, where missing views are recovered using complete samples as supervision. However, the paper identifies two critical flaws in the current evaluation and theoretical understanding of these methods:

The Per-Configuration Retraining Trap: Existing methods are typically evaluated by retraining a separate model for every specific combination of missing-data protocol and missing rate. This approach is computationally prohibitive for real-world deployment, where missing-data distributions are often non-stationary or unknown.
Incompleteness Divergence: The paper argues that the "nominal missing rate" ( $r$ ) is an insufficient metric for characterizing data incompleteness. Different evaluation protocols with the same nominal $r$ can result in drastically different proportions of fully observed samples ( $p_c$ ). The authors formalize this as incompleteness divergence, showing that protocols can differ by up to 50 $\times$ in $p_c$ at the same nominal rate.

Theoretical Insights: The Trainability Bound
The authors prove that for the broad class of reconstruction-based methods (Class 1, denoted as $\mathcal{F}_{rec}$ ), learning becomes structurally ill-posed when the proportion of complete samples ( $p_c$ ) falls below a critical threshold (specifically, when $p_c \to 0$ ).

Mechanism: Reconstruction losses derive supervision primarily from cross-view co-occurrence within the same sample. If a sample has fewer than two views, it contributes no gradient signal to the reconstruction objective.
Consequence: As $p_c$ decreases, the expected gradient signal vanishes. The paper proves that for protocols where $p_c \to 0$ , the expected parameter displacement is bounded by terms proportional to $p_c$ , leading to near-random clustering accuracy regardless of hyperparameter tuning. This collapse is a structural property of the loss family, not a tuning artifact.
Distinction: The paper distinguishes between trainability failure (gradient signal vanishes due to low $p_c$ , affecting $\mathcal{F}_{rec}$ ) and capability failure (information-theoretic limits where observed views simply lack sufficient information about the cluster labels, affecting all methods).

Methodology: CRAFT
To bypass the trainability bound, the authors propose CRAFT (Complete-data Robust Attention-masked Fusion Transformer). CRAFT is designed to satisfy two structural conditions that allow a single model trained on complete data to generalize to any missing pattern at inference:

Per-Sample Independence (C1): The representation for sample $i$ is computed solely from its own observed views and shared parameters. It does not rely on the observation patterns of other samples or cross-sample co-occurrence.
Mask-Aware Variable-Length Fusion (C2): Missing views are excluded from internal computation via attention masking rather than being zero-padded or hallucinated. This ensures that missing views contribute exactly zero to the fused representation, preventing the injection of noise or invalid signals.

Architecture Details:

Per-View Encoding: View-specific MLPs map each view to a shared embedding space.
Transformer Fusion: A Transformer encoder processes the sequence of view embeddings (plus a learnable [CLS] token). At inference, a key-padding mask sets attention logits to $-\infty$ for missing views, effectively removing them from the attention mechanism.
Two-Stage Training on Complete Data:
- Stage 1: Learns representations using a per-view reconstruction loss and a cross-view consistency loss (SimSiam-style) on complete samples.
- Stage 2: Fine-tunes the cluster head using self-labeled cross-entropy, entropy regularization, and optional Masked Fine-Tuning (MFT) to align training distribution with inference-time missing patterns.

Key Contributions

Formalization of Incompleteness Divergence: Introduction of effective missing rate ( $\hat{r}$ ) and complete-sample proportion ( $p_c$ ) as distinct causal variables, revealing that standard protocols obscure the trainability risks of reconstruction-based methods.
Theoretical Proof of Collapse: Rigorous proof that reconstruction-based learning is structurally bounded by $p_c$ , explaining why existing methods fail in sparse-data regimes (where $p_c < 1\%$ ).
CRAFT Architecture: A Transformer-based framework that achieves robust IMVC through architectural design (C1 and C2) rather than loss function engineering, enabling a "Train-Once, Deploy-Many" paradigm.
Empirical Validation: Extensive experiments on seven benchmarks (including CUB, HandWritten, MultiFashion, and YTF-31) across four distinct evaluation protocols.

Results

Collapse of Baselines: Standard $\mathcal{F}_{rec}$ baselines (e.g., COMPLETER, DCP, DCG, HSACC) uniformly collapse to near-random accuracy (often $<40\%$ ) when evaluated under stringent protocols where $p_c \to 0$ , even if the nominal missing rate is moderate.
CRAFT Performance: A single CRAFT checkpoint, trained once on complete data, matches or outperforms per-configuration retrained baselines across all 16 tested (protocol, rate) configurations.
Efficiency: CRAFT reduces training overhead by 8.8 $\times$ compared to the baseline approach of retraining separate models for each configuration.
Robustness: CRAFT maintains high accuracy even when $p_c = 0$ , demonstrating that robustness to missing data can be an inherent architectural property.

Significance and Claims
The paper claims that the current "per-configuration retraining" paradigm in IMVC is fragile and obscures a fundamental vulnerability in reconstruction-based methods. By shifting the burden of robustness from the loss function to the architecture, CRAFT demonstrates that it is possible to achieve robust IMVC without retraining for specific missing-data distributions. The authors suggest that future IMVC research should report $p_c$ as a standard metric and prioritize architectural refinements (like per-sample independence and mask-aware fusion) over algorithmic recovery mechanisms. The work is limited to unsupervised IMVC with cross-view reconstruction losses; the authors note that extending these principles to supervised multi-view classification or other multi-modal settings remains a direction for future work.