Shuffled graph classification: theory and connectome applications

DOI10.1007/S00357-015-9170-6zbMATH Open1331.62318arXiv1112.5506OpenAlexW1977463935MaRDI QIDQ2353142FDOQ2353142

Authors: Joshua T. Vogelstein, Carey E. Priebe 

Publication date: 8 July 2015

Published in: Journal of Classification (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1112.5506

Recommendations

• Network classification with applications to brain connectomics
• Classification on large networks: a quantitative bound via motifs and graphons (research)
• Machine learning application to human brain network studies: a kernel approach
• Seeded graph matching for correlated Erdős-Rényi graphs
• Universally consistent vertex classification for latent positions graphs

zbMATH Keywords

graph matchingrandom graphsstatistical pattern recognitionconnectomics

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Consistent nonparametric regression. Discussion
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• gBoost: a mathematical programming approach to graph classification and regression
• Discriminative prototype selection methods for graph embedding

Cited In (6)

• Universally consistent vertex classification for latent positions graphs
• Machine learning application to human brain network studies: a kernel approach
• Network classification with applications to brain connectomics
• A class of doubly stochastic shift operators for random graph signals and their boundedness
• Classification on large networks: a quantitative bound via motifs and graphons (research)
• High-dimensional Bayesian network classification with network global-local shrinkage priors

Uses Software

• OEIS
• gBoost

This page was built for publication: Shuffled graph classification: theory and connectome applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353142)