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\"os-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. These conditions are compact, easily interpretable, and cover a vast majority of the parameter space .
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\"os-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 .
R
partial recovery
partial recovery
R
These conditions are compact, easily interpretable, and cover a vast majority of the parameter space
In particular, we show that it is possible to achieve partial recovery in the nqs=\Theta(1) regime under certain additional assumptions