Statistical limits of correlation detection in trees

Short abstract: In this paper we address the problem of testing whether two observed trees are sampled either independently or from a joint distribution under which they are correlated. This problem, which we refer to as correlation detection in trees, plays a key role in the study of graph alignment for two correlated random graphs. Motivated by graph alignment, we investigate the conditions of existence of one-sided tests, i.e. tests which have vanishing type I error and non-vanishing power in the limit of large tree depth. For the correlated Galton-Watson model we identify a phase transition in the limit of large degrees: we prove that no such test exists below this threshold and that such a test exists whenever above the threshold, for a large enough mean degree.