  While many multiple graph inference methodologies operate under the implicit
assumption that an explicit vertex correspondence is known across the vertex
sets of the graphs, in practice these correspondences may only be partially or
errorfully known. Herein, we provide an information theoretic foundation for
understanding the practical impact that errorfully observed vertex
correspondences can have on subsequent inference, and the capacity of graph
matching methods to recover the lost vertex alignment and inferential
performance. Working in the correlated stochastic blockmodel setting, we
establish a duality between the loss of mutual information due to an errorfully
observed vertex correspondence and the ability of graph matching algorithms to
recover the true correspondence across graphs. In the process, we establish a
phase transition for graph matchability in terms of the correlation across
graphs, and we conjecture the analogous phase transition for the relative
information loss due to shuffling vertex labels. We demonstrate the practical
effect that graph shuffling---and matching---can have on subsequent inference,
with examples from two sample graph hypothesis testing and joint spectral graph
clustering.
