Exact recovery threshold in the binary censored block model

Bruce Hajek, Yihong Wu, Jiaming Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given a background graph with n vertices, the binary censored block model assumes that vertices are partitioned into two clusters, and every edge is labeled independently at random with labels drawn from Bern(1 - ϵ) if two endpoints are in the same cluster, or from Bern(ϵ) otherwise, where ϵ [0; 1/2] is a fixed constant. For Erd's-Rényi graphs with edge probability p = a log n/n and fixed a, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold equation for exactly recovering the partition from the labeled graph with probability tending to one as n → ∞. For random regular graphs with degree scaling as a log n, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold aD(Bern(1/2)Bern(ϵ)) > 1, where D denotes the Kullback-Leibler divergence.

Original languageEnglish (US)
Title of host publicationITW 2015 - 2015 IEEE Information Theory Workshop
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages99-103
Number of pages5
ISBN (Electronic)9781467378529
DOIs
StatePublished - Dec 17 2015
EventIEEE Information Theory Workshop, ITW 2015 - Jeju Island, Korea, Republic of
Duration: Oct 11 2015Oct 15 2015

Publication series

NameITW 2015 - 2015 IEEE Information Theory Workshop

Other

OtherIEEE Information Theory Workshop, ITW 2015
CountryKorea, Republic of
CityJeju Island
Period10/11/1510/15/15

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'Exact recovery threshold in the binary censored block model'. Together they form a unique fingerprint.

  • Cite this

    Hajek, B., Wu, Y., & Xu, J. (2015). Exact recovery threshold in the binary censored block model. In ITW 2015 - 2015 IEEE Information Theory Workshop (pp. 99-103). [7360742] (ITW 2015 - 2015 IEEE Information Theory Workshop). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITWF.2015.7360742