  Mining human-brain networks to discover patterns that can be used to
discriminate between healthy individuals and patients affected by some
neurological disorder, is a fundamental task in neuroscience. Learning simple
and interpretable models is as important as mere classification accuracy. In
this paper we introduce a novel approach for classifying brain networks based
on extracting contrast subgraphs, i.e., a set of vertices whose induced
subgraphs are dense in one class of graphs and sparse in the other. We formally
define the problem and present an algorithmic solution for extracting contrast
subgraphs. We then apply our method to a brain-network dataset consisting of
children affected by Autism Spectrum Disorder and children Typically Developed.
Our analysis confirms the interestingness of the discovered patterns, which
match background knowledge in the neuroscience literature. Further analysis on
other classification tasks confirm the simplicity, soundness, and high
explainability of our proposal, which also exhibits superior classification
accuracy, to more complex state-of-the-art methods.
