  We develop a formalism to address statistical pattern recognition of graph
valued data. Of particular interest is the case of all graphs having the same
number of uniquely labeled vertices. When the vertex labels are latent, such
graphs are called shuffled graphs. Our formalism provides insight to trivially
answer a number of open statistical questions including: (i) under what
conditions does shuffling the vertices degrade classification performance and
(ii) do universally consistent graph classifiers exist? The answers to these
questions lead to practical heuristic algorithms with state-of-the-art finite
sample performance, in agreement with our theoretical asymptotics.
