Massoulié - Planting trees in graphs, and finding them back

In this talk we  consider detection and reconstruction of planted structures in Erdős-Rényi random graphs. For planted line graphs, we establish the following phase diagram. In a low density region where the average degree λ of the initial graph is below some critical value λc, detection and reconstruction go from impossible to easy as the line length K crosses some critical value f(λ)ln(n), where n is the number of nodes in the graph. In the high density region λ>λc, detection goes from impossible to easy as K goes from o(\sqrt{n}) to ω(\sqrt{n}), and reconstruction remains impossible so long as K=o(n). We show similar properties for planted D-ary trees. These results are in contrast with the corresponding picture for detection and reconstruction of low rank planted structures, such as dense subgraphs and block communities: We observe a discrepancy between detection and reconstruction, the latter being impossible for a wide range of parameters where detection is easy. This property does not hold for previously studied low rank planted structures.