Alzheimer’s Disease (AD), the most prevalent form of dementia, requires early prediction for timely intervention. Current research meets this requirement by using machine learning methods based on patient features, yet they encounter issues with high-dimensional data and bias. To mitigate these issues, we introduce a framework for AD prediction using Graph Neural Networks (GNNs). Leveraging data from the Alzheimer's Disease Neuroimaging Initiative (ADNI), our study employs GNNs for binary and multi-class classification of Alzheimer's disease across its three stages: cognitively normal (CN), mild cognitive impairment (MCI), and Alzheimer's disease (AD). Initial steps involve creating a patient-clinical graph network considering latent relationships CN, MCI, and AD patients, followed by training several GNN-based techniques for building prediction models. By incorporating comorbidity data derived from electronic health records (EHR) into the feature set, we achieved the most effective multi-classification results. Notably, the GNN model with ChebConv layers (Chebyshev Convolutional Neural Networks) not only outperforms state-of-the-art techniques in multi-class AD classification, achieving an accuracy of 0.98, but also demonstrates remarkable stability with accuracies of 0.99, 0.93, and 0.94 in AD/CN, AD/MCI, and CN/MCI classification tasks respectively. This work contributes to the field by addressing the limitations of high-dimensional data and bias, offering a robust, accurate, and cost-effective method for early AD prediction using GNNs and EHR-derived data.