Deep neural networks have greatly improved medical image classification in a variety of applications and modalities. However, designing these networks manually is often time-consuming and suboptimal. This process can be done automatically by using Neural Architecture Search (NAS), which may offer the potential to identify more efficient and effective models. This paper presents an innovative approach that combines Variational Graph Autoencoders (VGAE) and Evolutionary Algorithms (EA) to optimize the NAS framework, with the goal of efficiently finding deep learning models for medical image classification tasks. Specifically, we leverage the NAS-Bench-101 dataset as the candidate architecture pool and utilize the VGAE model to encode and decode the architecture information of the neural network, thereby simplifying the architecture search process. Additionally, we integrate an evolutionary algorithm to explore the latent space, enhancing the model performance. Our method is validated on several datasets under MedMNIST. Experimental results demonstrate the effectiveness of our framework.