Generative Adversarial Networks For Graph Data Imputation From Signed\n Observations

Amarlingam Madapu, Santiago Segarra, Sundeep Prabhakar Chepuri, Antonio G. Marqués

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.

Introduction

In many real-world network scenarios, such as sensor arrays or social networks, data is often incomplete and coarsely quantized. A common challenge is recovering continuous graph signals when observations are both sparse and reduced to one-bit "signs" (indicating if a value is above or below a threshold). Traditional signal processing methods, which typically assume linear, continuous measurements, struggle with the non-linearity of sign functions and the absence of geometric context. This paper introduces a graph-regularized Generative Adversarial Network (GAN) designed to impute missing values by leveraging the underlying graph structure.

Methodology

The proposed framework extends the Generative Adversarial Imputation Nets (GAIN) by integrating graph-specific priors into the learning process.

Architecture of the proposed graph-aware GAN for data imputation from signed observations.

Model Components

  1. Generator ($G_\theta$): Maps observed signed signals and random noise to a continuous estimate of the original signal.
  2. Discriminator ($D_\psi$): Distinguishes between real observed nodes and imputed values, aided by a "hint" vector to provide partial information about the mask and stabilize training.
  3. Graph-Aware Losses: The generator's objective function includes two critical constraints:
  4. Sign Consistency: Ensures the generated signal's signs match the observed data.
  5. Graph Smoothness: Uses the Graph Laplacian to penalize large signal differences between connected nodes, enforcing the prior that signals vary smoothly across the network.

Experimental Setup

The model was evaluated using the MNIST dataset. Images were modeled as graph signals where pixels are nodes connected via a k-nearest neighbors (k-NN) graph ($k=20$). To simulate extreme data loss, 50% of pixels were removed, and the remaining 50% were converted to binary signs (+1 for bright, -1 for dark).

Results and Discussion

The proposed method significantly outperformed standard GAIN and iterative gradient descent baselines.

Comparison of training/testing loss and error curves between the proposed method and the standard GAIN framework.
  • Quantitative Performance: The proposed model achieved a Mean Squared Error (MSE) of 0.36, compared to 1.12 for GAIN and 0.49 for gradient descent.
  • Convergence and Stability: As shown in the loss curves, the inclusion of graph-specific losses led to faster and more stable convergence. The discriminator and generator reached an equilibrium more effectively than the baseline GAIN, which struggled to learn meaningful representations from signed data alone.
  • Visual Fidelity: Reconstructed digits were clear and recognizable, demonstrating that graph smoothness is a powerful regularizer for recovering continuous information from binary observations.

Conclusion

By baking graph structural priors directly into a GAN's loss function, this work demonstrates that it is possible to accurately impute missing values from highly degraded, signed observations. Future work will explore multi-bit quantization and the integration of Graph Convolutional Networks (GCNs) to further enhance reconstruction quality.

Summary updated

Abstract

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