Partial Recovery in the Graph Alignment Problem

  • 2020-07-30 16:45:16
  • Georgina Hall, Laurent Massouli√©
  • 0


In this paper, we consider the graph alignment problem, which is the problemof recovering, given two graphs, a one-to-one mapping between nodes thatmaximizes edge overlap. This problem can be viewed as a noisy version of thewell-known graph isomorphism problem and appears in many applications,including social network deanonymization and cellular biology. Our focus hereis on \emph{partial recovery}, i.e., we look for a one-to-one mapping which iscorrect on a fraction of the nodes of the graph rather than on all of them, andwe assume that the two input graphs to the problem are correlatedErd\"os-R\'enyi graphs of parameters $(n,q,s)$. Our main contribution is thento give necessary and sufficient conditions on $(n,q,s)$ under which partialrecovery is possible with high probability as the number of nodes $n$ goes toinfinity. In particular, we show that it is possible to achieve partialrecovery in the $nqs=\Theta(1)$ regime under certain additional assumptions.


Quick Read (beta)

loading the full paper ...