Brain state classification by applying deep learning techniques on neuroimaging data has become a recent topic of research. However, unlike domains where the data is low dimensional or there are large number of available training samples, neuroimaging data is high dimensional and has few training samples. To tackle these issues, we present a sparse feedforward deep neural architecture for encoding and decoding the structural connectome of the human brain. We use a sparsely connected element-wise multiplication as the first hidden layer and a fixed transform layer as the output layer. The number of trainable parameters and the training time is significantly reduced compared to feedforward networks. We demonstrate superior performance of this architecture in encoding the structural connectome implicated in Alzheimer's disease (AD) and Parkinson's disease (PD) from DTI brain scans. For decoding, we propose recursive feature elimination (RFE) algorithm based on DeepLIFT, layer-wise relevance propagation (LRP), and Integrated Gradients (IG) algorithms to remove irrelevant features and thereby identify key biomarkers associated with AD and PD. We show that the proposed architecture reduces 45.1% and 47.1% of the trainable parameters compared to a feedforward DNN with an increase in accuracy by 2.6 % and 3.1% for cognitively normal (CN) vs AD and CN vs PD classification, respectively. We also show that the proposed RFE method leads to a further increase in accuracy by 2.1% and 4% for CN vs AD and CN vs PD classification, while removing approximately 90% to 95% irrelevant features. Furthermore, we argue that the biomarkers (i.e., key brain regions and connections) identified are consistent with previous literature. We show that relevancy score-based methods can yield high discriminative power and are suitable for brain decoding. We also show that the proposed approach led to a reduction in the number of trainable network parameters, an increase in classification accuracy, and a detection of brain connections and regions that were consistent with earlier studies.