Biology – Quantitative Biology – Quantitative Methods
Scientific paper
2011-12-23
Biology
Quantitative Biology
Quantitative Methods
7 pages, 1 figure
Scientific paper
In this work, we investigate the extent to which shuffling vertex labels can hinder classification performance, and for which random graph models one might expect this shuffling to be impactful. Via theory we demonstrate a collection of results. Specifically, if one "shuffles" the graphs prior to classification, the vertex label information is irretrievably lost, which can degrade classification performance (and often does). A specific graph-invariant classifier is shown to be Bayes optimal. Moreover, this classifier may be induced by training data consistently and efficiently. Unfortunately, both computational and sample size burdens make this "plugin" classifier impractical. A graph-matched Frobenius norm k nearest neighbor (kNN) classifier, however, is also universally consistent as the number of training samples goes to infinity, and is computationally tractable. Finally, we apply this approach to a connectome classification problem (a connectome is brain-graph where vertices correspond to (collections of) neurons). The graph-matched kNN classifier on the shuffled graphs performs better than a typical graph-invariant kNN strategy, but not quite as well as the kNN on the labeled graphs, on a real connectome classification problem. Thus, we demonstrate the practical utility of the theoretical derivations herein. Extending these results to weighted and (certain) attributed random graph models is straightforward.
Priebe Carey E.
Vogelstein Joshua T.
No associations
LandOfFree
Shuffled Graph Classification: Theory and Connectome Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Shuffled Graph Classification: Theory and Connectome Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shuffled Graph Classification: Theory and Connectome Applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-191865