Working memory (WM) load-dependent changes of functional connectivity networks have previously been investigated by graph theoretical analysis. However, the extraordinary number of nodes represented within the complex network of the human brain has hindered the identification of functional regions and their network properties. In this paper, we propose a novel method for automatically extracting characteristic brain regions and their graph theoretical properties that reflect load-dependent changes in functional connectivity using a support vector machine classification and genetic algorithm optimization. The proposed method classified brain states during 2- and 3-back test conditions based upon each of the three regional graph theoretical metrics (degree, clustering coefficient, and betweenness centrality) and automatically identified those brain regions that were used for classification. The experimental results demonstrated that our method achieved a >90% of classification accuracy using each of the three graph metrics, whereas the accuracy of the conventional manual approach of assigning brain regions was only 80.4%. It has been revealed that the proposed framework can extract meaningful features of a functional brain network that is associated with WM load from a large number of nodal graph theoretical metrics without prior knowledge of the neural basis of WM.