Statistical limits of correlation detection in trees

Luca Ganassali

Date(s) : 15/11/2022   iCal
14 h 30 min - 15 h 30 min

L. Ganassali, L. Massoulié, G. Semerjian. Statistical limits of correlation detection in trees, 2022, submitted.

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.

Site Nord, CMI, Salle de Séminaire R164 (1er étage)


Retour en haut 

Secured By miniOrange