Seeded graph matching for correlated ErdosRenyi graphs

We study the consistency of graph matching for estimating a latent alignment function be-tween the vertex sets of two graphs, as well as subsequent algorithmic implications when the latent alignment is partially observed. In the correlated Erdos-Renyi graph setting, we prove that graph matching provides a strongly consistent estimate of the latent alignment in the presence of even modest correlation. We then investigate a tractable, restricted-focus version of graph matching, which is only concerned with adjacency involving vertices in a partial ob-servation of the latent alignment; we prove that a logarithmic number of vertices in the known partial latent alignment is sufficient for this restricted-focus version of graph matching to yield a strongly consistent estimate of the latent alignment of the remaining vertices. Lastly, we show how Frank-Wolfe methodology for approximate graph matching, when there is a known partial latent alignment, inherently incorporates this restricted-focus graph matching