Inferring Hidden Structures in Random Graphs

We study the two inference problems of detecting and recovering an isolated community of general structure planted in a random graph. The detection problem is formalized as a hypothesis testing problem, where under the null hypothesis, the graph is a realization of an ErdHos-R'enyi random graph G(n,q) with edge density q∈(0,1); under the alternative, there is an unknown structure Gammak on k nodes, planted in G(n,q), such that it appears as an induced subgraph. In case of a successful detection, we are concerned with the task of recovering the corresponding structure. For these problems, we investigate the fundamental limits from both the statistical and computational perspectives. Specifically, we derive lower bounds for detecting/recovering the structure Gammak in terms of the parameters (n,k,q), as well as certain properties of Gammak, and exhibit computationally unbounded optimal algorithms that achieve these lower bounds. We also consider the problem of testing in polynomial-time. As is customary in many similar structured high-dimensional problems, our model undergoes an "easy-hard-impossible" phase transition and computational constraints can severely penalize the statistical performance. To provide an evidence for this phenomenon, we show that the class of low-degree polynomials algorithms match the statistical performance of the polynomial-time algorithms we develop.