## Seeded Graph Matching for Correlated Erdos-Renyi Graphs

*Vince Lyzinski, Donniell E. Fishkind, Carey E. Priebe*; 15(Nov):3693−3720, 2014.

### Abstract

Graph matching is an important problem in machine learning and
pattern recognition. Herein, we present theoretical and
practical results on the consistency of graph matching for
estimating a latent alignment function between the vertex sets
of two graphs, as well as subsequent algorithmic implications
when the latent alignment is partially observed. In the
correlated Erdős-Rényi 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 observation of the latent alignment; we
prove that a logarithmic number of vertices whose alignment is
known is sufficient for this restricted-focus version of graph
matching to yield a strongly consistent estimate of the latent
alignment of the remaining vertices. We show how Frank-Wolfe
methodology for approximate graph matching, when there is a
partially observed latent alignment, inherently incorporates
this restricted-focus graph matching. Lastly, we illustrate the
relationship between seeded graph matching and restricted-focus
graph matching by means of an illuminating example from human
connectomics.

[abs][pdf][bib]