EGG-GAE: scalable graph neural networks for tabular data imputation

Lev Telyatnikov, Simone Scardapane

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:

  1. Scalability: They typically require computing a similarity matrix for the entire dataset, an $O(N^2)$ operation that is prohibitive for large datasets.
  2. 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.

Overall architecture of the EGG-GAE framework, illustrating the flow from input features and masks through EGG blocks to imputation and downstream task heads.

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).

Unified count of wins and average ranking across various missingness mechanisms, demonstrating the superior performance of EGG-GAE variants.

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

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.
BibTeX
@inproceedings{telyatnikov2023egg,
  author = {Lev Telyatnikov and Simone Scardapane},
  title = {{EGG-GAE: scalable graph neural networks for tabular data imputation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=DlP06gP7YD},
}
Figure