In this paper we address the problem of testing whether two observed trees $(t,t’)$ are sampled independently or from a joint distribution in which they are correlated.
This problem, called correlation detection in trees, plays an important role in the study of graph alignments of two correlated random graphs. Motivated by the alignment of the graphs, we investigate the existence conditions of a one-sided test, i.e., a test with vanishing Type I error and non-vanishing power in the limit of large tree depths.
For a correlated Galton-Watson model with mean $\lambda>0$ and Poisson descendants with correlation parameters $s \in (0,1)$, $s = \sqrt{ \alpha}$, where $\alpha \ sim 0.3383$ is Otter’s constant. That is, no such test exists for $s \leq \sqrt{\alpha}$, and if $s > \sqrt{\alpha}$, if $\lambda$ is large enough Always prove that such a test exists.
This result sheds new light on the problem of graph alignment in the sparse regime ($O(1)$ average node degree) and the performance of the MPAlign method studied by Ganassali et al. (2021), Piccioli et al. (2021), especially proving the conjecture of Piccioli et al. (2021) that MPAlign succeeds in partial recovery tasks with correlation parameters $s>\sqrt{\alpha}$ when the average node degree $\lambda$ is large enough.
