PaperlayerView exact revision on arXiv

Source-linked AI summary

Missing Data Imputation with Adversarially-trained Graph Convolutional Networks

Indro Spinelli, Simone Scardapane, Aurelio Uncini

arXiv:1905.01907v2cs.LGstat.ML

TL;DR

Missing-data imputation must handle incomplete datasets, but existing approaches may use global statistics or model instances independently. This paper introduces a graph denoising autoencoder that uses similarity-based neighborhood information, global data context, and adversarial training. Across benchmark and real-world evaluations, the method is competitive or superior, especially with high missingness, while remaining robust to downstream classifier choice.

  • Problem

    Missing-data imputation is needed for incomplete real-world datasets, while existing methods may use global statistics or predictive models operating independently on instances.

  • Method

    The paper uses a graph convolutional autoencoder that represents examples with similarity-based graph connections and reconstructs the full dataset from corrupted inputs.

  • Results

    The method matches or outperforms existing approaches, especially with high artificial missingness, and remains robust to downstream classifier selection.

  • Takeaways & Limitations

    Graph-based imputation can combine similar-example information with global dataset modeling for multivariate missing-data reconstruction.

  • Takeaways & Limitations

    The similarity graph construction is one empirically effective choice, but the framework permits alternatives and does not analyze them here.

Abstract

from arXiv · show

Missing data imputation (MDI) is a fundamental problem in many scientific disciplines. Popular methods for MDI use global statistics computed from the entire data set (e.g., the feature-wise medians), or build predictive models operating independently on every instance. In this paper we propose a more general framework for MDI, leveraging recent work in the field of graph neural networks (GNNs). We formulate the MDI task in terms of a graph denoising autoencoder, where each edge of the graph encodes the similarity between two patterns. A GNN encoder learns to build intermediate representations for each example by interleaving classical projection layers and locally combining information between neighbors, while another decoding GNN learns to reconstruct the full imputed data set from this intermediate embedding. In order to speed-up training and improve the performance, we use a combination of multiple losses, including an adversarial loss implemented with the Wasserstein metric and a gradient penalty. We also explore a few extensions to the basic architecture involving the use of residual connections between layers, and of global statistics computed from the data set to improve the accuracy. On a large experimental evaluation, we show that our method robustly outperforms state-of-the-art approaches for MDI, especially for large percentages of missing values.

1. Introduction

Missing-data imputation is needed because many real-world datasets are incomplete, while existing methods may rely on global statistics or independent predictive models. The paper proposes a graph convolutional network framework that combines similarities among examples with global modeling and evaluates several extensions across benchmark and real-world datasets.

  • Missing-data imputation replaces absent input values with predicted values to produce a complete dataset for downstream machine learning.
  • Existing imputation approaches use global statistics, similar data points, or predictive models built independently for each instance.
  • The proposed framework represents examples as a similarity graph and uses a graph convolutional autoencoder to reconstruct the dataset under artificial noise.
  • The architecture combines standard losses with an adversarial loss and adds residual connections and global dataset statistics as extensions.
  • Across artificial-noise benchmarks and three real-world datasets, GINN matches or outperforms existing methods, particularly with high missingness, while remaining robust to downstream classifier choice.The evaluation includes two biomedical datasets and one time-series dataset.

Organization of the paper

The paper reviews missing-data imputation and graph-neural-network foundations before presenting and evaluating a graph-based imputation framework. Its GCN layers combine feature transformations with neighborhood information propagated through the graph.

  • Related work: The paper reviews multivariate imputation methods, including MICE, predictive algorithms, and recent deep-learning approaches.
  • Graph neural networks: It introduces graph neural networks and graph convolutional networks as foundations for modeling relationships among examples.
  • Graph construction: Each dataset example becomes a graph node, with adjacency derived from feature-vector similarities adapted to missing data.
  • Graph convolutional networks: The graph Laplacian is eigendecomposed to define graph-domain transforms, although the direct Fourier-based convolution is costly and impractical.
  • Graph convolutional networks: A canonical GCN layer applies trainable feature coefficients and propagates information across neighboring nodes through the graph operator.
  • Graph convolutional networks: Stacking L graph-convolution layers makes each node's output depend on neighbors up to degree L.

4. Proposed framework for missing data imputation

The framework imputes missing values with a graph denoising autoencoder whose graph connects similar examples using only jointly observed features. It combines graph construction, denoising, and reconstruction objectives, with optional global statistics and alternative graph designs.

  • Graph construction: Each data example becomes a graph node, and edges encode similarities derived from feature vectors with missing entries handled explicitly.The similarity graph is the method’s first fundamental step and supports graph-based imputation.
  • Extensions and scope: The framework permits supervised labels as additional imputation inputs and supports alternative similarity-graph construction methods.The paper lists binary weights, heat-kernel similarity, fixed-neighbor selection, and cosine similarity on pretrained embeddings as alternatives left for future analysis.
  • Graph construction: Pairwise Euclidean distances use only features observed in both examples, then row-wise percentile pruning produces a sparse graph.The experiments use the 97.72nd percentile, discarding around 95% of possible connections.
  • Autoencoder and training: The GINN uses a graph denoising autoencoder that maps corrupted inputs to an overcomplete representation before reconstructing the dataset.During training, inverted dropout randomly removes 50% of remaining inputs, while reconstruction loss combines MSE for numerical and cross-entropy for categorical variables.
  • Autoencoder and training: Training minimizes reconstruction error on observed elements, with a weighting parameter α balancing numerical and categorical losses.α is initialized as the ratio of numerical columns to total columns and may alternatively be tuned.

Computational cost of the model

The model’s computational cost is concentrated in constructing the similarity graph and applying GCN layers, while adversarial training and architectural extensions shape reconstruction behavior.

  • Computational cost: The main computational costs are one-time similarity-graph construction and replacing feedforward layers with GCN layers.The paper relates graph construction to large-scale similarity search and discusses GCN cost separately.
  • Computational cost: With early stopping, GINN training including graph construction is significantly faster than alternative neural approaches and comparable to MICE.This comparison is reported for the authors’ implementation and benchmark setting.
  • Adversarial training: The adversarial component uses a critic trained with Wasserstein distance and gradient penalty to guide imputed outputs toward real-data distributions.The critic is updated five times for each autoencoder update, and the autoencoder balances fooling the critic with reconstruction error.
  • Skip connections: A skip graph-convolution layer aggregates immediate neighbors without self-loops, preventing the autoencoder from learning the identity function.The resulting decoding operation uses an adjacency-derived operator without self-loops.
  • Global statistics: Global dataset statistics such as means or modes can be incorporated as graph-level attributes in the final node-update layer.When differentiable, these global attributes can also receive an additional loss term weighted by γ.

5. Experimental evaluation

The evaluation spans UCI datasets with artificial and pre-existing missingness, testing imputation accuracy, downstream classification, ablations, unseen-data transfer, and computational cost. GINN generally performs strongly, particularly as missingness increases, while remaining more resilient to classifier choice and faster than alternative neural methods.

  • Experimental setup: The benchmark uses 20 UCI datasets with categorical, numerical, and mixed attributes, plus three real-world datasets containing pre-existing missing values.The UCI datasets range from 150 to 30,000 observations and from 4 to nearly 40 attributes.
  • 5.1. Imputation Performance: At 30% missingness, GINN achieves the best imputation performance in almost half of the datasets and is second-best in nearly all remaining datasets.The comparison includes MICE, MIDA, MissForest, mean imputation, matrix factorization, and k-NN imputation, using MAE and RMSE.
  • 5.1. Imputation Performance: Aggregated at 30% and 50% missingness, GINN is best in 50% of MAE cases versus 27.5% for MissForest, and in 47.5% of RMSE cases versus 20%.At 10% and 20% missingness, GINN is nearly on par with MissForest; its advantage grows at higher missingness.
  • 5.2. Predictive Performance: GINN records the highest classification accuracy in 85.62% of cases and outperforms competitors across the tested classification algorithms.Its gains are especially pronounced with SVC and random forest and at increasing missingness levels, while it is slightly below the state of the art at 10% for logistic regression and k-NN.
  • 5.2. Predictive Performance: Friedman tests find significant differences for RMSE (p-value 1.11e−11) and classifier accuracy, including random forest (p-value 1.01e−10).Nemenyi post-hoc tests further confirm significant differences between GINN and all other methods for random-forest classification.
  • 5.3. Ablation study: Ablations show that adding the graph and graph-convolution operation substantially improves imputation over a standard autoencoder, with subsequent components further refining accuracy and convergence.On unseen data, GINN achieves state-of-the-art imputation without additional training and improves further after 500 fine-tuning epochs; it is faster than neural alternatives but slower than k-NN.

6. Conclusions and future work

The paper presents a graph convolutional autoencoder for missing data imputation, enhanced with adversarial loss and global dataset information. Its results show good imputation performance and robustness to downstream classifier choice, while future work targets broader architectures and computational limitations.

  • The proposed method uses a graph convolutional autoencoder to reconstruct the full dataset for missing data imputation.
  • Adversarial loss and global dataset information are introduced as improvements to the imputation technique.
  • The method significantly outperforms competitors in experiments with large levels of artificial noise.
  • Future work includes different graph neural architectures, other noisy data types, alternative similarity measures, and end-to-end classification training.
  • The method requires computing a data similarity matrix and has difficulty with mini-batching graph-based data.

Detailed RMSE results (Section 5.1)

The supplementary RMSE results organize imputation performance across 20 datasets, methods, and levels of artificial corruption. MAE results are reported as similar and are available separately.

  • Table 8 reports RMSE imputation values for 20 datasets, with rows representing datasets and columns representing imputation methods.
  • Results are separated by the level of artificial corruption added to the original dataset.
  • The suffix xx denotes xx% artificially added missing values.
  • MAE results are described as similar and are available in the online repository.

Detailed accuracy for regression/classification (Section 5.2)

The supplementary results report downstream classification or regression accuracy for different techniques after imputation, stratified by artificial corruption levels. Results for methods beyond random forest are summarized as similar and provided online.

  • Table 9 reports downstream classification or regression accuracy for each classification or regression technique after imputation.
  • The results are presented separately according to the level of artificially added missing values.
  • Random forest results are provided, while results for other methods are described as similar and supplied in the online repository.

Detailed results for the statistical tests

The supplementary statistical analysis provides average rankings and p-values for pairwise Nemenyi post-hoc tests. It covers both imputation results and downstream random-forest classification results corresponding to the main tables.

  • Figure 7 reports average rankings and p-values from Nemenyi post-hoc tests across algorithm pairs for the results corresponding to Table 2.
  • Figure 8 reports average rankings and p-values for statistical tests on the random forest classifier corresponding to Table 9.

Ablation study with a computational budget (Section 5.3)

Under a fixed computational budget, the GCN baseline converges to a better result than a standard denoising autoencoder, while the adversarial loss slightly improves the final result at substantially higher cost.

  • The GCN baseline without adversarial loss converges to a significantly better result than a standard DAE in a fraction of the time.
  • The adversarial loss slightly improves the final result but requires 3−4 times the baseline computational budget.

Detailed results for the evaluation on real-world datasets

On three real-world datasets, GINN achieves the best random-forest classification accuracy and consistency, while its imputation time falls between trained neural methods and training-free approaches. Statistical tests confirm significant accuracy differences among methods.

  • GINN achieves the best random-forest accuracy and consistency across the Mammographic mass, Cervical cancer, and Air quality datasets.The evaluation includes cases where imputed training labels are used to train the classification model.
  • GINN is considerably faster than alternative neural approaches and missForest, but slower than approaches without a training phase.GINN timing includes similarity-graph construction.
  • Friedman tests find statistically significant classifier-accuracy differences for Cervical cancer, Mammographic mass, and Air quality, with p-values of 1.6e−7, 1.3e−7, and 1.2e−9, respectively.
  • The evaluation reports RMSE imputation performance and random-forest classification accuracy across datasets and percentages of missing elements.
Loading 1905.01907v2…