Random graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This can be viewed as an average-case and noisy version of the well-known graph isomorphism problem. For the correlated Erd\"os-R\'enyi model, we prove an impossibility result for partial recovery in the sparse regime, with constant average degree and correlation, as well as a general bound on the maximal reachable overlap. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise. Our proof technique relies on a careful application of the probabilistic method to build automorphisms between tree components of a subcritical Erd\"os-R\'enyi graph.


翻译:随机图形对齐是指恢复两个带有相关边缘的随机图形之间的顶点对应。 这可以视为已知的图形形态问题的普通和吵闹版本。 对于相关的 Erd\"os- R\' enyi 模型, 我们证明在稀疏的状态下无法部分恢复, 且具有恒定的平均程度和关联性, 以及受最大可达性重叠约束的一般。 在无噪音的案例中, 我们的界限很紧( 图形的形态问题), 我们推测它仍然与噪音紧密。 我们的证据技术依赖于谨慎地应用概率法来在亚临界的 Erd\" os- R\' enyi 图形的树块之间构建自动形态。

0
下载
关闭预览

相关内容

【开放书】应用信号处理,498页pdf,Applied Signal Processing
专知会员服务
45+阅读 · 2021年6月15日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
已删除
将门创投
11+阅读 · 2019年4月26日
Arxiv
14+阅读 · 2020年12月17日
Arxiv
6+阅读 · 2019年11月14日
Pluralistic Image Completion
Arxiv
8+阅读 · 2019年3月11日
Arxiv
3+阅读 · 2018年2月7日
VIP会员
相关资讯
已删除
将门创投
11+阅读 · 2019年4月26日
Top
微信扫码咨询专知VIP会员