Shuffled Graph Classification: Theory and Connectome Applications

Details Shuffled Graph Classification: Theory and Connectome Applications Shuffled Graph Classification: Theory and Connectome Applications

2011-12-23

arxiv.org/abs/1112.5506v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-191865