Electronic medical documents contain valuable information and present challenges for information extraction due to their substantial unstructured natural language text. Named Entity Recognition (NER) and Relation Extraction (RE) are critical tasks usually addressed with machine learning and rule-based methods. Recent advances include Graph Neural Network (GNN) based models, which are under-explored in architecture and feature selection. This paper introduces GREED (GNN-based Relation Extraction with Exhaustive Dependency Structure Analysis), employing GNN to convert sentences into weighted graphs via dependency parsing. Two GNN-based models were evaluated on clinical records (i2b2/VA 2010): Graph Convolutional Network (GCN) and Graph Attention Network (GAT). Comprehensive experimental results demonstrate that the GCN-based model outperforms the GAT-based model achieving an F1-score of \(82.09\%\) , highlighting its superior performance for this task. Furthermore, it outperforms other state-of-the-art methods.