Application of the information-percolation method to reconstruction problems on graphs

DOI10.4171/MSL/10MaRDI QIDQ2176072zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 4 May 2020

Published in Mathematical Statistics and Learning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.04195

zbMATH Keywords

community detectioncorrelated recoverygroup synchronizationinformation-percolation methodspiked Wigner modelstrong data processing inequality

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Inequalities; stochastic orderings (60E15) Communication theory (94A05) Information theory (general) (94A15)

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.

Review text

Summary: 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 \textit{E. Abbe} and \textit{E. Boix} [``An information-percolation bound for spin synchronization on general graphs, Preprint, \url{arXiv:1806.03227}]), and establishes new impossibility result for community detection on the stochastic block model with \(k\) communities.

Recommendations

• An information-percolation bound for spin synchronization on general graphs
• Fundamental limits of symmetric low-rank matrix estimation
• Asymptotic mutual information for the balanced binary stochastic block model

Cites work

• A proof of the block model threshold conjecture
• An information-percolation bound for spin synchronization on general graphs
• Asymptotic mutual information for the balanced binary stochastic block model
• Broadcasting on trees and the Ising model.
• Comparison of Channels: Criteria for Domination by a Symmetric Channel
• Component behavior near the critical point of the random graph process
• Dissipation of Information in Channels With Input Constraints
• Elements of Information Theory
• Group synchronization on grids
• scientific article; zbMATH DE number 3562959 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• scientific article; zbMATH DE number 3200971 (Why is no real title available?)
• Modern Coding Theory
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Reconstruction and estimation in the planted partition model
• Signal propagation and noisy circuits
• Strong data-processing inequalities for channels and Bayesian networks
• The critical probability of bond percolation on the square lattice equals 1/2

Cited in

(9)

• On the computational tractability of statistical estimation on amenable graphs
• An information-percolation bound for spin synchronization on general graphs
• On the benefits of representation regularization in invariance based domain generalization
• Multi-reference alignment in high dimensions: sample complexity and phase transition
• Information Recovery in Shuffled Graphs via Graph Matching
• Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Combinatorial statistics and the sciences
• Mutual information for the sparse stochastic block model
• On a nonhierarchical generalization of the perceptron GREM

This page was built for publication: Application of the information-percolation method to reconstruction problems on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176072)