<p>The human brain is an intricate and diverse network, characterized by its complexity and the abundance of information it processes. As a result, researchers in this field are continually seeking effective solutions to identify significant features and reduce data dimensionality, thereby improving classification performance. Two emerging techniques in brain signal processing are graph signal processing and meta-heuristic evolutionary tactics. In this study on EEG motor imagery classification, two distinct brain graph structures were explored: a geometric structure and a mixed structure. Weights of the edges in the mixed structure were determined using a combination of geometric distance and correlation measures. To lower the dimensionality of the graph, a weighted degree metric was used, along with a combination of the Kron reduction method and the graph Fourier transform. Feature extraction was accomplished using Ledoit–Wolf shrinkage estimation and tangent space mapping. Furthermore, to further reduce the dimensionality of the extracted features, principal component analysis and differential evolution methods were employed. Ultimately, the selected features were fed into various well-known ML classifiers. To assess the effectiveness of the recommended approach, database IVa from BCI competition III was utilized as a benchmark. Results showed that the structural-functional graph (SFG) produced better classification results than the structural graph. In addition, features selected by differential evolution yielded better classification results than those selected by classical principal component analysis (PCA). The best classification accuracy was obtained by integrating the structural-functional graph (SFG), the differential evolution method, and the decision tree classifier, which is equal to 96.26% for electroencephalogram (EEG) motor imagery classification.</p>