Insurance companies have focused on medicare fraud detection to reduce financial losses and reputational harm because medicare fraud causes tens of billions of dollars in damage annually. This study demonstrates that medicare fraud detection can be significantly enhanced by introducing graph analysis with considering the relationships among medical providers, beneficiaries, and physicians. We use open-source tabular datasets containing beneficiary information, inpatient claims, outpatient claims, and indications about potential fraudulent providers. We then aggregated them into a single dataset by converting them into a graph structure. Furthermore, we developed medicare fraud detection models using two approaches to reflect graph information, i.e., graph neural network (GNN) models and traditional machine learning models using graph centrality measures. Therefore, the machine learning model with graph centrality features showed improved precision of 4 percent point (%p), recall of 24 %p, and F1-score of 14 %p compared to the best GNN model. The improvement in recall to this extent could result in substantial cost savings of 3.1 billion euros and 5 billion dollars in the United States and Europe, respectively, benefiting governmental institutions and insurance companies involved in healthcare insurance operations. Furthermore, the required learning time of the best GNN model was approximately 250–300 times more than that of the best machine-learning model. This outcome suggests that successful and efficient detection of medicare fraud can be achieved if graph centrality measures are used to capture the relationships among medical providers, physicians, and beneficiaries.