标题： 相关随机块模型的高效图匹配 显示英文标题

标题： Efficient Graph Matching for Correlated Stochastic Block Models

摘要： 我们研究在两个平衡社区的关联随机块模型上的学习问题。 我们的主要结果给出了在此设置下图匹配的第一个高效算法。 在平均度数随顶点数对数增长的最有趣情形中，当边相关参数$s$满足$s^2 > \alpha \approx 0.338$时，该算法以高概率正确匹配几乎所有顶点，其中$\alpha$是 Otter 的树计数常数。 此外，我们将其扩展为一种高效算法，在信息论上可行时实现精确图匹配，从而正面解决了 Rácz 和 Sridhar（NeurIPS 2021）提出的一个开放问题。 我们的算法推广了 Mao、Wu、Xu 和 Yu（STOC 2023）最近的突破性工作，该工作基于称为吊灯的大量树结构的中心子图计数。 我们克服的主要技术挑战是处理由于在相关参数范围内，从单个图中无法精确恢复潜在社区划分而必然存在的额外估计误差。 作为我们结果的应用，我们在信息论上仅使用单个图无法做到的情况下，给出了一个利用多个相关图进行精确社区恢复的高效算法。 显示英文摘要

摘要： We study learning problems on correlated stochastic block models with two balanced communities. Our main result gives the first efficient algorithm for graph matching in this setting. In the most interesting regime where the average degree is logarithmic in the number of vertices, this algorithm correctly matches all but a vanishing fraction of vertices with high probability, whenever the edge correlation parameter $s$ satisfies $s^2 > \alpha \approx 0.338$, where $\alpha$ is Otter's tree-counting constant. Moreover, we extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible, positively resolving an open problem of R\'acz and Sridhar (NeurIPS 2021). Our algorithm generalizes the recent breakthrough work of Mao, Wu, Xu, and Yu (STOC 2023), which is based on centered subgraph counts of a large family of trees termed chandeliers. A major technical challenge that we overcome is dealing with the additional estimation errors that are necessarily present due to the fact that, in relevant parameter regimes, the latent community partition cannot be exactly recovered from a single graph. As an application of our results, we give an efficient algorithm for exact community recovery using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph.