TY - JOUR

T1 - Information Limits for Recovering a Hidden Community

AU - Hajek, Bruce

AU - Wu, Yihong

AU - Xu, Jiaming

N1 - Funding Information:
Manuscript received January 24, 2016; revised September 20, 2016; accepted December 15, 2016. Date of publication January 17, 2017; date of current version July 12, 2017. This work was supported in part by the National Science Foundation under Grant ECCS 10-28464, Grant IIS-1447879, Grant CCF-1409106, and Grant CCF-1527105 and in part by the Strategic Research Initiative on Big-Data Analytics of the College of Engineering at the University of Illinois, DOD ONR under Grant N00014-14-1-0823 and Grant 328025 through the Simons Foundation. This paper was presented at the 2016 IEEE International Symposium on Information Theory, Barcelona, Spain [29].
Publisher Copyright:
© 1963-2012 IEEE.

PY - 2017/8

Y1 - 2017/8

N2 - We study the problem of recovering a hidden community of cardinality K from an n × n symmetric data matrix A, where for distinct indices i,j, Aij ∼ P if i, j both belong to the community and Aij ∼ Q otherwise, for two known probability distributions P and Q depending on n. If P= Bern(p) and Q= Bern(q) with p>q, it reduces to the problem of finding a densely connected K-subgraph planted in a large Erdös-Rényi graph; if P= N(μ,1) and Q= N(0,1) with μ >0, it corresponds to the problem of locating a K × K principal submatrix of elevated means in a large Gaussian random matrix. We focus on two types of asymptotic recovery guarantees as n to: 1) weak recovery: expected number of classification errors is o(K) and 2) exact recovery: probability of classifying all indices correctly converges to one. Under mild assumptions on P and Q, and allowing the community size to scale sublinearly with n, we derive a set of sufficient conditions and a set of necessary conditions for recovery, which are asymptotically tight with sharp constants. The results hold, in particular, for the Gaussian case, and for the case of bounded log likelihood ratio, including the Bernoulli case whenever (p/q) and (1-p)/(1-q) are bounded away from zero and infinity. Previous work has shown that if weak recovery is achievable; then, exact recovery is achievable in linear additional time by a simple voting procedure. We provide a converse, showing the condition for the voting procedure to succeed is almost necessary for exact recovery.

AB - We study the problem of recovering a hidden community of cardinality K from an n × n symmetric data matrix A, where for distinct indices i,j, Aij ∼ P if i, j both belong to the community and Aij ∼ Q otherwise, for two known probability distributions P and Q depending on n. If P= Bern(p) and Q= Bern(q) with p>q, it reduces to the problem of finding a densely connected K-subgraph planted in a large Erdös-Rényi graph; if P= N(μ,1) and Q= N(0,1) with μ >0, it corresponds to the problem of locating a K × K principal submatrix of elevated means in a large Gaussian random matrix. We focus on two types of asymptotic recovery guarantees as n to: 1) weak recovery: expected number of classification errors is o(K) and 2) exact recovery: probability of classifying all indices correctly converges to one. Under mild assumptions on P and Q, and allowing the community size to scale sublinearly with n, we derive a set of sufficient conditions and a set of necessary conditions for recovery, which are asymptotically tight with sharp constants. The results hold, in particular, for the Gaussian case, and for the case of bounded log likelihood ratio, including the Bernoulli case whenever (p/q) and (1-p)/(1-q) are bounded away from zero and infinity. Previous work has shown that if weak recovery is achievable; then, exact recovery is achievable in linear additional time by a simple voting procedure. We provide a converse, showing the condition for the voting procedure to succeed is almost necessary for exact recovery.

KW - Community detection

KW - large deviation

KW - maximum likelihood

KW - rate distortion theory

KW - stochastic block model

KW - submatrix localization

UR - http://www.scopus.com/inward/record.url?scp=85028999440&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028999440&partnerID=8YFLogxK

U2 - 10.1109/TIT.2017.2653804

DO - 10.1109/TIT.2017.2653804

M3 - Article

AN - SCOPUS:85028999440

SN - 0018-9448

VL - 63

SP - 4729

EP - 4745

JO - IRE Professional Group on Information Theory

JF - IRE Professional Group on Information Theory

IS - 8

M1 - 7820122

ER -