Seeded graph matching via large neighborhood statistics

We study a noisy graph isomorphism problem, where the goal is to perfectly recover the vertex correspondence between two edge-correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. We show that it is possible to achieve the information-theoretic limit of graph sparsity in time polynomial in the number of verticesn. Moreover, we show the number of seeds needed for perfect recovery in polynomial-time can be as low asn epsilon in the sparse graph regime (with the average degree smaller thann epsilon) and omega(logn)in the dense graph regime, for a small positive constant epsilon. Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds.