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 imputation 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 fundamental challenge in data science, as real-world tabular datasets often contain missing entries that can bias results and degrade model performance. Traditional statistical methods like MICE or machine learning approaches like MissForest are widely used but often fail to capture the complex, non-linear dependencies inherent in high-dimensional data.

Recently, Graph Neural Networks (GNNs) have emerged as a powerful alternative by treating data rows as nodes in a graph and leveraging inter-row similarities. However, standard GNN approaches for MDI suffer from two main limitations: they do not scale well to large datasets due to the quadratic complexity of full-graph construction, and they typically rely on fixed, pre-defined similarity metrics (e.g., Euclidean distance) to establish graph topology, which may not be optimal for the imputation task.

Methodology

The proposed EdGe Generation Graph AutoEncoder (EGG-GAE) addresses these limitations by learning the graph structure dynamically within mini-batches. The architecture consists of feature propagation followed by multiple EGG blocks that perform node projection, differentiable edge sampling, and GNN-based feature updates.

The EGG-GAE architecture overview, showing the flow from input data X and mask M through feature propagation and EGG blocks to the final imputation and task heads.

The core innovation is the EGG block, which uses a Gumbel-Softmax trick to sample edges between nodes in a mini-batch, making the graph topology a learnable parameter optimized for imputation. To enhance stability and provide global context, the authors introduce "prototype nodes"—learnable anchor nodes that are included in every mini-batch to act as archetypal patterns. Furthermore, an ensembling strategy is employed during inference to average results across multiple stochastic edge samplings, leading to more robust and stable final imputations.

Experimental Results

EGG-GAE was evaluated on 15 diverse datasets from the UCI repository, covering numerical, categorical, and mixed data types. The experiments considered three missingness mechanisms: Missing Completely at Random (MCAR), Missing at Random (MAR), and Missing Not at Random (MNAR), with missingness levels ranging from 10% to 50%.

Unified performance metrics across 15 datasets: (a) count of wins and (b) average ranking for various imputation methods under different missingness mechanisms.

As shown in the unified performance metrics, the $k$-EGG-GAE variant—which restricts each node to exactly $k$ neighbors—consistently achieves the highest count of wins and the best average ranking across all scenarios. Notably, it maintains superior performance even in challenging MNAR settings. Unlike previous GNN-based imputers, EGG-GAE scales effectively to large datasets like SUSY (25,000 samples) and Connect (67,000 samples) because it operates on mini-batches rather than the full dataset graph.

Discussion and Conclusion

The success of EGG-GAE highlights the importance of learning graph topology rather than defining it statically. By letting the model optimize connections specifically for the imputation task, it discovers relationships that simple distance metrics might miss. The use of prototype nodes further stabilizes this process by providing consistent "data anchors" across different mini-batches.

While EGG-GAE solves global scaling issues, the pairwise calculations within the EGG block remain $O(n^2)$ relative to the batch size, suggesting a limit on batch size. Future work could explore alternative distance metrics or iterative sampling processes to further refine the learned neighborhoods. Overall, EGG-GAE represents a significant step forward in scalable, high-performance graph-based imputation for tabular data.

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 imputation 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