Seeded Graph Matching via Large Neighborhood Statistics
share
We study a well known noisy model of the graph isomorphism problem. In this model, the goal is to perfectly recover the vertex correspondence between two edge-correlated Erdős-Rényi random graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. For seeded problems, our result provides a significant improvement over previously known results. We show that it is possible to achieve the information-theoretic limit of graph sparsity in time polynomial in the number of vertices n. Moreover, we show the number of seeds needed for exact recovery in polynomial-time can be as low as n^3ϵ in the sparse graph regime (with the average degree smaller than n^ϵ) and Ω( n) in the dense graph regime. Our results also shed light on the unseeded problem. In particular, we give sub-exponential time algorithms for sparse models and an n^O( n) algorithm for dense models for some parameters, including some that are not covered by recent results of Barak et al.
READ FULL TEXT