Recent years have witnessed significant progress in applying graph-based machine learning techniques to analyze Electronic Health Record (EHR) data. These methods leverage the interconnected nature of EHR data to extract valuable insights and make predictions at various levels. This paper provides a comprehensive overview of recent advancements in graph-based machine learning approaches for EHR analysis. Specifically, we examine eight models from the literature, comparing their performance on the eICU-CRD dataset. These models encompass a range of techniques, including Graph Convolutional Networks (GCN), Long Short-Term Memory Networks (LSTM), self-attention mechanisms, and reinforcement learning. Additionally, we introduce a novel algorithm designed to address specific challenges posed by EHR data, such as class imbalance and erroneous entries. Our comparative analysis demonstrates the proposed algorithm's effectiveness relative to existing models, highlighting significant improvements in predicting in-hospital mortality. Furthermore, we outline future research directions, including synthesizing existing approaches to develop more generalizable frameworks for EHR diagnosis tasks. This survey provides insights into state-of-the-art methods and potential avenues for advancing graph-based machine learning in EHR analysis. © 2024 IEEE.