Partial Recovery in the Graph Alignment Problem
  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.
