论文标题
图形对准问题中的部分恢复
Partial Recovery in the Graph Alignment Problem
论文作者
论文摘要
在本文中，我们考虑图形对齐问题，这是恢复两个图的问题，在两个图中，在节点之间的一对一映射，最大化边缘重叠。这个问题可以看作是众所周知的图形同构问题的嘈杂版本，并出现在许多应用中，包括社交网络脱位和蜂窝生物学。我们这里的重点是部分恢复，即，我们寻找一个一对一的映射，该映射在图表的一小部分而不是所有图形上都正确，并且我们假设问题的两个输入图是相关的erdős-rényi图表$（n，q，q，s）$。然后，我们的主要贡献是为$（n，q，s）$提供必要的条件，在该条件下，由于节点的数量$ n $变为无限，因此可以以很高的可能性为例。特别是，我们表明，在某些其他假设下，有可能在$ NQS =θ（1）$制度中实现部分恢复。
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ős-Rényi 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=Θ(1)$ regime under certain additional assumptions.
