We study the problem supervised classification of labeled graphs (networks with labeled nodes). Although statistical analysis of a single network has received a lot of attention in the recent years, with a focus on social networks,  analysis of a sample of networks presents its own challenges which require a different set of analytic tools. The main motivation for our work is the study of brain networks, which are constructed from imaging data to represent functional connectivity between regions of the brain. Previous work has shown the potential of such networks as diagnostic biomarkers for brain disorders. Existing approaches to graph classification tend to either treat the edges as a long multivariate vector, ignoring the network structure, or focus on the graph topology while ignoring the edge weights.  Our goal here is to incorporate both the individual edge information and the overall graph structure in a computationally efficient way. We are also interested in  obtaining a parsimonious and interpretable representation of differences in brain connectivity patterns between classes, in addition to achieving high classification accuracy.  We achieve this by introducing penalties that encourage structured sparsity, and implement them via efficient convex optimization algorithms. The method shows good performance both on simulated networks and on real data from fMRI studies of schizophrenic patients.