Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model

DOI10.1109/TIT.2021.3117264MaRDI QIDQ5030254zbMATH OpenOpenAlexFDO

Authors Min Ye

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

stochastic block modelrandom graph modelstochastic Ising block model

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random graphs (graph-theoretic aspects) (05C80)

Abstract: The stochastic block model (SBM) is a random graph model in which the edges are generated according to the underlying cluster structure on the vertices. The (ferromagnetic) Ising model, on the other hand, assigns $pm1$ labels to vertices according to an underlying graph structure in a way that if two vertices are connected in the graph then they are more likely to be assigned the same label. In SBM, one aims to recover the underlying clusters from the graph structure while in Ising model, an extensively-studied problem is to recover the underlying graph structure based on i.i.d. samples (labelings of the vertices). In this paper, we propose a natural composition of SBM and the Ising model, which we call the Stochastic Ising Block Model (SIBM). In SIBM, we take SBM in its simplest form, where $n$ vertices are divided into two equal-sized clusters and the edges are connected independently with probability $p$ within clusters and $q$ across clusters. Then we use the graph $G$ generated by the SBM as the underlying graph of the Ising model and draw $m$ i.i.d. samples from it. The objective is to exactly recover the two clusters in SBM from the samples generated by the Ising model, without observing the graph $G$. As the main result of this paper, we establish a sharp threshold $m^{a}st$ on the sample complexity of this exact recovery problem in a properly chosen regime, where $m^{a}st$ can be calculated from the parameters of SIBM. We show that when $mge{m}^{a}st$, one can recover the clusters from $m$ samples in $O(n)$ time as the number of vertices $n$ goes to infinity. When $m<m^{a}st$, we further show that for almost all choices of parameters of SIBM, the success probability of any recovery algorithms approaches $0$ as $noinfty$.

Recommendations

• Exact recovery in the Ising blockmodel
• Exact Recovery in the Stochastic Block Model
• Exact recovery in block spin Ising models at the critical line
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Belief propagation, robust reconstruction and optimal recovery of block models
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Recovery and rigidity in a regular stochastic block model
• Non-convex exact community recovery in stochastic block model
• An impossibility result for reconstruction in the degree-corrected stochastic block model
• A proof of the block model threshold conjecture

Cited in

(2)

• Fair community detection and structure learning in heterogeneous graphical models
• Exact recovery in block spin Ising models at the critical line

This page was built for publication: Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model

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