Random Intersection Graphs and Missing Data

Dror Salti, Yakir BerchenkoAAAI 2020 · OpenReview

Introduction

Missing data is a pervasive challenge in empirical research, often addressed through iterative algorithms like Expectation-Maximization (EM). While it is well-understood that excessive missingness degrades performance, the precise structural limits of these tools have remained elusive. This paper bridges random graph theory and statistics to identify "phase transitions"—mathematical tipping points where statistical algorithms suddenly slow down or fail.

Methodology: Reducing Missingness to Graphs

The core innovation of this work is treating a missing-data matrix as the incidence matrix of a bipartite graph. As shown in Figure 2, a "missingness matrix" (where entries are marked as missing or observed) can be mapped to a bipartite graph connecting variables and observations.

Mapping missingness patterns to bipartite and projection graphs.

By projecting this bipartite structure, the authors map statistical properties to graph-theoretic ones:

  • Identifiability: The ability to estimate parameters corresponds to graph connectivity.
  • Algorithm Convergence: The speed of EM convergence is linked to the emergence of a "giant component" and the presence of cycles within the graph. When the missingness pattern is tree-like, the imputation step is computationally simple; however, the emergence of large cycles leads to "loopy" dependencies that drastically increase iteration counts.

Phase Transitions and Threshold Analysis

Using established proofs from random graph theory, the authors identify critical values for the probability of missingness ($p$). Statistical performance does not degrade linearly; instead, it exhibits threshold phenomena.

Phase diagram illustrating convergence regimes based on missingness probability and signal-to-noise ratio.

As illustrated in Figure 6, two primary thresholds are identified:

  1. The Convergence Threshold ($p^*$): Defined as $p^* = \sqrt{1/mn}$. Below this value, the missingness pattern is largely tree-like, allowing EM to converge in linear time. Above $p^*$, a "giant component" with complex cycles emerges, causing the number of iterations to spike.
  2. The Identifiability Threshold ($p^{**}$): Defined as $p^{**} = \sqrt{\ln(m)/mn}$. Beyond this point, the graph becomes disconnected, making it mathematically impossible to link certain variables and resulting in a total loss of model identifiability.

Experimental Validation

The theoretical thresholds were validated using synthetic datasets and linear regression simulations ($y = x\beta + \epsilon$). Simulations confirmed that as $p$ approaches $p^{**}$, estimation error and EM cycles grow exponentially. Interestingly, the authors noted a "SNR Paradox" where a high Signal-to-Noise Ratio (SNR) can sometimes increase the number of EM cycles needed near the threshold. These results remained consistent across different data distributions (Normal and Uniform), suggesting that the phenomenon is a fundamental property of the missingness structure rather than specific data values.

Conclusion and Future Work

This research highlights that the structure of missingness is as critical as the data values themselves. While the current work focuses on data Missing Completely At Random (MCAR), future research will explore Missing At Random (MAR) and Missing Not At Random (MNAR) scenarios. Additionally, the authors suggest these findings could be applied to data privacy, determining the exact amount of redaction required to prevent dataset reconstruction.

Summary updated

Abstract

Random-graphs and statistical inference with missing data are two separate topics that have been widely explored each in its field. In this paper we demonstrate the relationship between these two different topics and take a novel view of the data matrix as a random intersection graph. We use graph properties and theoretical results from random-graph theory, such as connectivity and the emergence of the giant component, to identify two threshold phenomena in statistical inference with missing data: loss of identifiability and slower convergence of algorithms that are pertinent to statistical inference such as expectation-maximization (EM). We provide two examples corresponding to these threshold phenomena and illustrate the theoretical predictions with simulations that are consistent with our reduction.
BibTeX
@inproceedings{salti2020random,
  author = {Dror Salti and Yakir Berchenko},
  title = {{Random Intersection Graphs and Missing Data}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=yKFtYwo41d},
}
Figure