CORRELATION DETECTION IN TREES FOR PLANTED GRAPH ALIGNMENT

被引:2
作者
Ganassali, Luca [1 ]
Lelarge, Marc [1 ]
Massoulie, Laurent [1 ,2 ]
机构
[1] PSL Res Univ, Inria, DI ENS, Paris, France
[2] MSR Inria Joint Ctr, Paris, France
关键词
Inference in random graphs; graph matching; graph alignment; hypothesis testing; RECOVERY;
D O I
10.1214/23-AAP2020
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
Motivated by alignment of correlated sparse random graphs, we introduce a hypothesis testing problem of deciding whether or not two random trees are correlated. We study the likelihood ratio test and obtain sufficient conditions under which this task is impossible or feasible. We propose MPAlign, a message-passing algorithm for graph alignment inspired by the tree correlation detection problem. We prove MPAlign to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time.1
引用
收藏
页码:2799 / 2843
页数:45
相关论文
共 26 条
[1]  
Arvind V, 2002, ANN IEEE SYMP FOUND, P743, DOI 10.1109/SFCS.2002.1181999
[2]  
Banks J, 2016, Arxiv, DOI arXiv:1607.01760
[3]  
Bollobas B., 2001, CAMBRIDGE STUDIES AD, DOI DOI 10.1017/CBO9780511814068
[4]   NONBACKTRACKING SPECTRUM OF RANDOM GRAPHS: COMMUNITY DETECTION AND NONREGULAR RAMANUJAN GRAPHS [J].
Bordenave, Charles ;
Lelarge, Marc ;
Massoulie, Laurent .
ANNALS OF PROBABILITY, 2018, 46 (01) :1-71
[5]   Thirty years of graph matching in pattern recognition [J].
Conte, D ;
Foggia, P ;
Sansone, C ;
Vento, M .
INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2004, 18 (03) :265-298
[6]  
Cullina D, 2018, Arxiv, DOI arXiv:1809.03553
[7]  
Cullina D, 2018, Arxiv, DOI arXiv:1711.06783
[8]   MATCHING RECOVERY THRESHOLD FOR CORRELATED RANDOM GRAPHS [J].
Ding, Jian ;
Du, Hang .
ANNALS OF STATISTICS, 2023, 51 (04) :1718-1743
[9]   Efficient random graph matching via degree profiles [J].
Ding, Jian ;
Ma, Zongming ;
Wu, Yihong ;
Xu, Jiaming .
PROBABILITY THEORY AND RELATED FIELDS, 2021, 179 (1-2) :29-115
[10]  
EMRE DAI O., 2019, arXiv