This work addresses the critical requirement for accurate and explainable methods for brain tumor classification from Magnetic Resonance Imaging (MRI). Though Graph Neural Networks (GNNs) adequately capture the complex, non-Euclidean connections challenging traditional Convolutional Neural Networks (CNNs), their inherent “black-box” nature makes them unsuitable for clinical applications where transparency is of utmost importance. This work proposes two GNN-based models: a Superpixelize GAT model for intra-image structure representation and a GAT Clustering model for inter-image relation representation. Performance metrics show that the Superpixelize GAT model has a test accuracy of 96.11% and the GAT Clustering model has an accuracy of 84%. To ensure clinical trust, we integrated GNNExplainer and GraphLIME to produce explainable model predictions. This paper provides model explanations consistent with available clinical diagnostic criteria.