Computational Universality for Community Detection

-
Guy Bresler, MIT
Fine Hall 214

We consider the problem of detecting existence of a single hidden community of size K in a graph where edges between members of the community have label X drawn i.i.d. according to P and all other edges have labels drawn i.i.d. according to Q. We show that for a broad class of distributions P and Q both the information limits and the computational hardness (based on planted clique) are determined by the KL-divergence between P and Q. We additionally show how to reduce general P and Q to the case P = Ber(p) and Q = Ber(q) and vice versa, while losing only logarithmic factors in the divergence, giving a direct approximate computational equivalence. This is joint work with Matthew Brennan and Wasim Huleihel.