In this paper, we consider the graph alignment problem, which is the problem of recovering, given two graphs, a one-to-one mapping between nodes that maximizes edge overlap. This problem can be viewed as a noisy version of the well-known graph isomorphism problem and appears in many applications, including social network deanonymization and cellular biology. Our focus here is on partial recovery, i.e., we look for a one-to-one mapping which is correct on a fraction of the nodes of the graph rather than on all of them, and we assume that the two input graphs to the problem are correlated Erd\H{o}s-R\'enyi graphs of parameters $(n,q,s)$. Our main contribution is then to give necessary and sufficient conditions on $(n,q,s)$ under which partial recovery is possible with high probability as the number of nodes $n$ goes to infinity. In particular, we show that it is possible to achieve partial recovery in the $nqs=\Theta(1)$ regime under certain additional assumptions.
翻译:在本文中, 我们考虑图形对齐问题, 也就是在两个图中, 恢复一个对一个点之间的一对一映射, 使边缘重叠最大化。 这个问题可以被看成是众所周知的图形地貌化问题的响亮版本, 并出现在许多应用中, 包括社交网络去匿名化和细胞生物学。 我们这里的焦点是部分恢复, 也就是说, 我们寻找一个一对一的映射, 这在图形节点的一小部分上是正确的, 而不是在所有节点上是正确的。 我们假设, 问题的两个输入图是相关的 Erd\ H{ { o}s- R\'enyi 参数图 $ (n, q, s) 。 我们的主要贡献是给$ (n, q, s) 提供必要和充分的条件, 美元( q, s) 下部分恢复的可能性很大, 因为ndes $ (n, $) 到无限。 我们特别表明, 在某些额外假设下, 在 $ {theta (1) 制度下实现部分回收的可能性。