Generative Adversarial Networks for Graph Data Imputation from Signed Observations

Amarlingam Madapu, Santiago Segarra, Sundeep Prabhakar Chepuri, Antonio G. Marques

Abstract

This paper introduces a novel Generative Adversarial Network (GAN) architecture designed to reconstruct continuous graph signals from incomplete, "signed" (one-bit quantized) observations. By integrating graph-signal processing (GSP) priors—specifically smoothness and sign consistency—directly into the GAN’s loss function, the researchers successfully impute missing data even when the available information is non-linear and highly sparse. Experimental results on the MNIST dataset demonstrate that the proposed method significantly outperforms state-of-the-art baselines like GAIN in both reconstruction accuracy and training stability.

Introduction

In many real-world networks, such as social media or sensor arrays, data is often degraded by two simultaneous hurdles: missing values at a subset of nodes and quantization noise. Instead of precise continuous values, we frequently only have "signed" observations (e.g., a binary response or a threshold indicator). Traditional GSP methods typically rely on linear observation models and struggle with the non-linearity of one-bit quantization. Furthermore, most deep learning approaches for data imputation require complete datasets for training, which are often unavailable. This work proposes a "graph-regularized" GAN that learns to fill in missing data using only the graph structure and noisy, signed bits.

Methodology

Proposed GAN architecture for graph data imputation from signed observations.

The proposed architecture consists of two primary components:

  • The Generator ($G_\theta$): It receives observed signed signals (with zeros for missing nodes) and a noise vector as input. It outputs an estimate of the underlying continuous signal $\hat{x}$.
  • The Discriminator ($D_\psi$): Its objective is to identify which nodes were originally observed and which were imputed. To facilitate learning, it is provided with a "hint" vector $h$, revealing the mask status for all nodes except one randomly chosen node.

Graph-Aware Loss Functions

The core innovation lies in the generator's loss function, which incorporates GSP-inspired constraints:

  1. Sign Consistency ($L_{G2}$): Ensures the signs of the generated continuous values match the signs of the observed data.
  2. Smoothness ($L_{G3}$): Enforces that the generated signal varies smoothly across the graph using the Graph Laplacian quadratic form, penalizing large differences between connected nodes.

Experimental Setup

The researchers evaluated the method using the MNIST handwritten digits dataset. Each 28x28 image was vectorized into a 784-dimensional signal on a graph where pixels are nodes and edges are formed via a k-nearest neighbors approach (k=20). The data was corrupted by removing 50% of entries and quantizing the remainder into +1/-1 signs.

Results and Discussion

Comparison of training convergence (cross-entropy) and error rates between the proposed method and GAIN.

The proposed method was compared against GAIN and a non-deep iterative gradient descent approach. Key results include:

  • Accuracy: The proposed method achieved a Mean Squared Error (MSE) of 0.36, significantly outperforming GAIN (1.12) and the iterative baseline (0.49).
  • Visual Fidelity: Qualitative results showed that while GAIN produced unrecognizable blobs under 50% signed masking, the proposed method reconstructed clear, smooth digits.
  • Convergence: As shown in the training curves, the proposed method's losses stabilized much earlier and reached lower error floors than the GAIN architecture, indicating superior adversarial stability due to the graph-regularized priors.

Conclusion

By leveraging the geometry of the graph as an inductive bias, the proposed GAN framework effectively recovers high-fidelity continuous signals from sparse, non-linear observations. Future work will explore multi-bit quantization levels and the integration of Graph Convolutional Networks (GCNs) to further enhance performance in complex sensor deployment scenarios.

Summary updated

Abstract

We study the problem of missing data imputation for graph signals from signed one-bit quantized observations. More precisely, we consider that the true graph data is drawn from a distribution of signals that are smooth or bandlimited on a known graph. However, instead of observing these signals, we observe a signed version of them and only at a subset of the nodes on the graph. Our goal is to estimate the true underlying graph signals from our observations. To achieve this, we propose a generative adversarial network (GAN) where the key is to incorporate graph-aware losses in the associated minimax optimization problem. We illustrate the benefits of the proposed method via numerical experiments on hand-written digits from the MNIST dataset.
BibTeX
@inproceedings{madapu2020generative,
  author = {Amarlingam Madapu and Santiago Segarra and Sundeep Prabhakar Chepuri and Antonio G. Marques},
  title = {{Generative Adversarial Networks for Graph Data Imputation from Signed Observations}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  doi = {10.1109/icassp40776.2020.9053458},
}
Figure