Javascript must be enabled

Joshua Vogelstein : Consistent Graph Classification applied to Human Brain Connectome Data



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.

Please select playlist name from following

Report Video

Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn’t appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don’t do it.


Comments Disabled For This Video