In neuroimaging, brain activity is commonly represented through a connectivity network computed for each subject. Predicting a clinical outcome of interest, for example disease status, leads to the problem of prediction from network-valued observations. While edge weights can always be vectorized and fed into a standard classifier, this type of "massive univariate" approach ignores the network nature of the predictors. Constructing an interpretable prediction rule is important in neuroimaging, and even if variable selection is performed, individual selected edges are usually hard to interpret. However, it is well known that connectivity patterns are grouped by brain regions, and finding predictive regions instead of edges is more interpretable. Instead of using fixed regions, we simultaneously train the prediction algorithm and find the regions whose connectivity (either within a region or between them) is most predictive. Our approach uses an efficient optimization algorithm with a block-structured penalty, and produces interpretable and highly accurate solutions on fMRI data from schizophrenics and healthy controls.