Graphs are becoming a favorite mathematical object for representation of data. Yet, statistical pattern recognition has focused almost entirely on vector valued data in Euclidean space. Graphs, however, live in graph space, which is non-Euclidean. Thus, most inference techniques are not even defined for graph valued data. Previous work in the classification of graph-valued data typically follows one of two recipes. (1) Vectorize the adjacency matrices of the graphs, and apply standard machine learning techniques. (2) Compute some number of graph invariants (e.g., clustering coefficient, or degree distribution) for each graph, and then apply standard machine learning techniques. We follow a different recipe based in the probabilistic theory of pattern recognition. First, we define a joint graph-class model. Given this model, we derive classifiers which we prove are consistent; that is, they converge to the Bayes optimal classifier. Specifically, we build two consistent classifiers for graph valued data, a parametric and a non-parametric version. In a sense, these classifiers span the spectrum of complexity, the former is consistent for graphs sampled from relatively simple random graph distributions, the latter is consistent for graphs sampled from (nearly) any random graph distribution. Although both classifiers assume that all our graphs have labeled vertices, we generalize these results to also incorporate unlabeled graphs, as well as weighted and multigraphs. We apply these graph classifiers to human brain data. Specifically, using diffusion MRI, we can obtain large brain-graphs (10,000 vertices) for each subject, where vertices correspond to voxels. We then coarsen the graphs spatially to obtain smaller (70 vertex) graphs per subject. Using <50 subjects, we are able to achieve nearly 85% classification accuracy, with results interpretable to neurobiologists with regard to the brain regions of interest.