In traditional machine learning, we view tabular data as a rigid grid. Each row is a sample, each column is a feature, and every cell is a value. When a value is missing, the grid breaks. We are forced to either discard the row or fill the hole with a "best guess"—like the mean or median—which often ignores the complex relationships between different variables.
A growing body of research suggests a more flexible alternative: treating the data matrix not as a grid, but as a bipartite graph. By reimagining samples and features as interconnected nodes, researchers are finding that missing data is no longer a "hole" to be patched, but a structural property of a network that can be solved through relational reasoning.
The Bipartite Transformation
The core intuition behind this approach, pioneered by Jiaxuan You and Jure Leskovec in their work on GRAPE, is to represent a dataset as two distinct sets of nodes. One set represents the observations (e.g., patients or experimental trials), and the other represents the features (e.g., symptoms or gene expressions).
An edge exists between a "sample node" and a "feature node" only if that specific value was actually observed. The value itself (the measurement) becomes an attribute of that edge.
This shift in perspective solves several problems at once:
- Sparsity is natural: In Electronic Health Records (EHRs), where a patient might only have 10 codes out of 70,000 possibilities, a matrix is 99% empty. In a bipartite graph, as noted by Jer Hayes and Ramón Viñas Torné 0001 in A Graph-based Imputation Method for Sparse Medical Records, we only store the "oases" of data. The "desert" of zeros simply doesn't exist as edges.
- Imputation becomes Link Prediction: Filling in a missing value is no longer a statistical estimation problem; it is a link prediction problem. We are asking the model: "Given the existing connections in this network, what is the most likely value for a connection that doesn't exist yet?"
Why It Works: Global Relational Reasoning
Standard imputation methods usually look at local statistics—for example, "What is the average blood pressure for people of this age?" Bipartite graph models, however, use Graph Neural Networks (GNNs) to perform message passing across the entire population.
As Zhongyi Yu and S.-H. Gary Chan explain in M3-Impute, this allows the model to capture high-order correlations. A sample node receives information from all its observed feature nodes, which helps define the "type" of sample it is. Simultaneously, feature nodes receive information from all samples that possess them, defining the "behavior" of that feature.
By passing these messages back and forth, the model learns that if Patient A and Patient B share several rare symptoms, they are likely to share others, even if those symptoms haven't been recorded for Patient B yet. This global connectivity allows GRAPE to reduce imputation error by up to 20% compared to traditional methods.
Handling Missing Modalities
This framework is particularly powerful for multimodal data, where entire categories of information (like a genomic sequence or an MRI scan) might be missing for certain individuals.
In CenSurv, Hailin Yue and colleagues show that by treating modalities as nodes in a bipartite graph, they can predict cancer survival without needing to "impute" the missing modality itself. The model simply processes the edges that do exist. This "missing-aware" architecture, also explored by Zhenbang Wu in Multimodal Patient Representation Learning with Missing Modalities and Labels, prevents the model from failing when clinical records are incomplete.
Scaling and Complexity
While powerful, bipartite graphs can become massive. Recent work has focused on making these models scalable for real-world use:
- Temporal Smoothing: For longitudinal data (data collected over time), Ziqi Chen and Hongtu Zhu developed SHT-GNN, which uses mini-batch sampling and temporal smoothing to handle irregular observation schedules.
- Hybrid Architectures: In BCGNN, Hongtu Zhu and Zhaoyang Zhang combine the bipartite graph with a complete directed graph of features. This allows the model to learn not just sample-to-feature relationships, but also direct dependencies between the features themselves (e.g., how smoking directly influences lung capacity).
By moving away from the rigid matrix and toward the fluid graph, these researchers are turning the "messiness" of real-world data into a structured map of relationships, allowing models to see the signal even when most of the data is missing.