Luca Ganassali (INRIA Paris): Statistical limits of correlation detection in trees
2022-11-15 14:30 - 15:30 (Europe/Paris) | I2M Chateau-Gombert - CMI, Salle de Séminaire R164 (1er étage), 39 Rue Joliot Curie, 13013 Marseille, France, Campus Château-Gombert,
Luca Ganassali: L. Ganassali, L. Massoulié, G. Semerjian. Statistical limits of correlation detection in trees, 2022, submitted.
[arXiv]
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.
