Application of information-percolation method to reconstruction problems on graphs

Yury Polyanskiy, Yihong Wu

Introduction

In fields ranging from social network analysis to sensor synchronization, a fundamental challenge is the "reconstruction problem": recovering hidden labels on nodes based on noisy observations of the edges connecting them. While significant research focuses on developing algorithms to solve these problems, establishing the fundamental limits—the thresholds at which reconstruction becomes mathematically impossible for any algorithm—is notoriously difficult.

This paper introduces the "information-percolation" framework, a powerful theoretical approach that determines these impossibility thresholds by bridging Information Theory and Percolation Theory. By treating information flow as a physical process similar to fluid moving through a porous medium, the authors establish sharp bounds for several canonical problems, including community detection, group synchronization, and the spiked Wigner model.

The Information-Percolation Framework

The core of the proposed method is the mapping of information decay in a Markov Random Field (MRF) to a bond-percolation model. This is achieved through three primary mechanisms:

1. Strong Data Processing Inequality (SDPI)

While the standard Data Processing Inequality states that processing data cannot increase information, the SDPI quantifies the exact rate of information loss as it passes through a noisy channel. This loss is captured by a contraction coefficient ($\eta$), which represents the maximum possible information retention across an edge.

2. The Percolation Bound

The authors prove that the mutual information between two distant nodes in a graph is bounded by the probability that a path exists between them in a corresponding random graph. In this model, each edge of the original graph is "open" with a probability equal to the SDPI contraction coefficient. If the noise is high enough that the probability of a path existing (percolation) drops to zero, the mutual information also vanishes, rendering reconstruction impossible.

3. Channel Comparison

To handle complex noise models, the authors employ channel comparison. They demonstrate that a complex noisy channel can be compared to a simpler "erasure channel" (where data is either perfectly transmitted or completely lost). If reconstruction is impossible in the simpler erasure model, it is guaranteed to be impossible in the original, more complex model.

Applications and Theoretical Results

The framework was evaluated against several standard mathematical models used to benchmark reconstruction algorithms. Unlike empirical studies, this theoretical work focuses on establishing universal thresholds for these models:

  • Spiked Wigner Model: The method recovers the optimal "PCA threshold" ($\lambda \le 1$). This confirms that below this signal-to-noise ratio, the principal components of a noisy matrix contain no information regarding the underlying signal.
  • Group Synchronization: For $\mathbb{Z}/2\mathbb{Z}$ synchronization on a 2D square grid, the paper establishes an improved impossibility threshold of $(1-2\delta)^2 \le 1/2$.
  • Stochastic Block Model (SBM): The framework provides a simple proof for the near-optimal threshold in the 2-community case. More significantly, for $k=3$ communities, the authors establish a new state-of-the-art impossibility result, strengthening the best-known bounds for when community recovery is unattainable.

Discussion and Limitations

The information-percolation method offers a unifying perspective for both directed models (like Bayesian networks) and undirected models (like Markov Random Fields), the latter of which are prevalent in spatial statistics and physics.

However, some limitations remain. While the results for small numbers of communities are sharp, the bounds for the Stochastic Block Model become suboptimal by a logarithmic factor as the number of communities ($k$) grows very large. Additionally, many of the sharpest results assume the graph is "locally tree-like," meaning it lacks short cycles. Extending these rigorous bounds to highly clustered, "small-world" networks found in real-world social data remains an open area for future research. The authors suggest that further refinements to the channel comparison techniques may eventually close the gap between these theoretical impossibility results and known algorithmic thresholds.

Summary updated

Abstract

In this paper we propose a method of proving impossibility results based on applying strong data-processing inequalities to estimate mutual information between sets of variables forming certain Markov random fields. The end result is that mutual information between two "far away" (as measured by the graph distance) variables is bounded by the probability of the existence of an open path in a bond-percolation problem on the same graph. Furthermore, stronger bounds can be obtained by establishing mutual information comparison results with an erasure model on the same graph, with erasure probabilities given by the contraction coefficients. As applications, we show that our method gives sharp threshold for partially recovering a rank-one perturbation of a random Gaussian matrix (spiked Wigner model), yields the best known upper bound on the noise level for group synchronization (obtained concurrently by Abbe and Boix), and establishes new impossibility result for community detection on the stochastic block model with $k$ communities.
BibTeX
@misc{polyanskiy2018application,
  author = {Yury Polyanskiy and Yihong Wu},
  title = {{Application of information-percolation method to reconstruction problems on graphs}},
  year = {2018},
  eprint = {1806.04195},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.04195},
}
Figure