An Information-Percolation Bound for Spin Synchronization on General Graphs

Abstract

This paper considers the problem of reconstructing $n$ independent uniform spins $X_1,\dots ,X_n$ living on the vertices of an $n$-vertex graph $G$, by observing their interactions on the edges of the graph. This captures instances of models such as (i) broadcasting on trees, (ii) block models, (iii) synchronization on grids, (iv) spiked Wigner models. The paper gives an upper-bound on the mutual information between two vertices in terms of a bond percolation estimate. Namely, the information between two vertices' spins is bounded by the probability that these vertices are connected in a bond percolation model, where edges are opened with a probability that "emulates" the edge-information. Both the information and the open-probability are based on the Chi-squared mutual information. The main results allow us to re-derive known results for information-theoretic non-reconstruction in models (i)-(iv), with more direct or improved bounds in some cases, and to obtain new results, such as for a spiked Wigner model on grids. The main result also implies a new subadditivity property for the Chi-squared mutual information for symmetric channels and general graphs, extending the subadditivity property obtained by Evans-Kenyon-Peres-Schulman [EKPS00] for trees.

arXiv commentThe results of this paper are from Enric Boix's undergraduate senior thesis, advised by Emmanuel Abbe. The results were presented at the Workshop on Combinatorial Statistics, Montreal, May 2018

References in corpus (14)

• Message Passing Algorithms for Compressed Sensing
• Stochastic Block Models and Reconstruction
• Phase Transitions in Semidefinite Relaxations
• Information-theoretic thresholds from the cavity method
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Community Detection in the Labelled Stochastic Block Model
• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Information-theoretic thresholds for community detection in sparse networks
• Belief propagation, robust reconstruction and optimal recovery of block models
• Estimation in the spiked Wigner model: A short proof of the replica formula
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• Spectral Detection in the Censored Block Model
• Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization

Cited by in corpus (3)

• Provable limitations of deep learning
• Poly-time universality and limitations of deep learning
• Application of information-percolation method to reconstruction problems on graphs