Seeded Graph Matching via Large Neighborhood Statistics

Abstract

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 Erdos-R\'enyi 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.

Tasks

Reproductions