Abstract Missing data imputation (MDI) is crucial when dealing with tabular datasets across various domains. Autoencoders can be trained to reconstruct missing values, and graph autoencoders (GAE) can additionally consider similar patterns in the dataset when imputing new values for a given instance. However, previously proposed GAEs suffer from scalability issues, requiring the user to define a similarity metric among patterns to build the graph connectivity beforehand. In this paper, we leverage recent progress in latent graph learning to propose a novel EdGe Generation Graph AutoEncoder (EGG-GAE) for missing data imputation that overcomes these two drawbacks. EGG-GAE works on randomly sampled mini-batches of the input data (hence scaling to larger datasets), and it automatically infers the best connectivity across the mini-batch for each architecture layer. We also experiment with several extensions, including an ensemble strategy for inference and the inclusion of what we call prototype nodes, obtaining significant improvements, both in terms of imputation error and final downstream accuracy, across multiple benchmarks and baselines.
Introduction
Missing data imputation (MDI) is a persistent challenge in real-world data science. While standard statistical approaches like MICE or MissForest are effective in many cases, they often fail to capture the complex, non-linear relationships present in high-dimensional tabular data. Graph Neural Networks (GNNs) offer a powerful alternative by treating each data instance (row) as a node and using similarities between instances to "pass messages" to fill in missing values.
However, existing GNN-based imputers face two major hurdles:
- Scalability: They typically require computing a similarity matrix for the entire dataset, an $O(N^2)$ operation that is prohibitive for large datasets.
- Static Topology: They often rely on a pre-defined, hand-crafted graph structure. If the initial distance metric is poor, the resulting imputation suffers.
The EGG-GAE Framework
The EdGe Generation Graph AutoEncoder (EGG-GAE) addresses these issues by learning optimal row-to-row connectivity on-the-fly within mini-batches. This approach allows the model to scale to large datasets while automatically discovering a task-specific topology.
The EdGe Generation (EGG) Block
The core of the architecture is the EGG block, which replaces fixed graphs with a learnable generation pipeline:
- Node Projection: Each row in a mini-batch is projected into a latent graph embedding space.
- Differentiable Sampling: The model computes pairwise edge probabilities. To maintain end-to-end trainability, the Gumbel-Softmax trick is employed, allowing the model to sample discrete edges while gradients flow back during training.
- GNN Head: A standard GNN (such as GCN or EdgeConv) operates on this generated graph to update node features.
- k-EGG Variant: A more efficient version that restricts each node to its top-$k$ most similar neighbors, ensuring graph sparsity and improved performance.
Key Extensions
To further enhance robustness, EGG-GAE introduces prototype nodes—learnable, global representations added to every mini-batch. These act as reliable "anchors," ensuring that even small, random mini-batches have high-quality neighbors to learn from. Additionally, an ensemble strategy is used during inference, where multiple stochastic passes are averaged to produce a more stable and accurate final imputation.
Experimental Results
The model was validated on 15 diverse UCI datasets under three missingness mechanisms: Missing Completely at Random (MCAR), Missing at Random (MAR), and Missing Not at Random (MNAR).
Key Insights
- Task-Specific Latent Graphs: By training graph generation and imputation jointly, the model learns a topology optimized for predicting missing values and downstream labels, rather than just relying on raw feature similarity.
- Mini-batching as a Regularizer: Working on mini-batches forces the model to learn robust local relationships, preventing over-reliance on potentially noisy global structures.
- Performance and Utility: EGG-GAE and $k$-EGG-GAE consistently outperformed baselines like GAIN, MICE, and MissForest. Notably, the model showed significant improvements in downstream task accuracy, proving that the imputed values preserve the underlying data structure better than traditional methods.
Conclusion
EGG-GAE provides a scalable, end-to-end framework for tabular data imputation. By moving from static to learnable, mini-batch-based graphs, it overcomes the scalability and topology constraints of previous GNN methods. While internal batch complexity remains $O(n^2)$, the integration of prototype nodes and ensembling makes EGG-GAE a robust and high-performing solution for modern data challenges.
Summary updated