TY - JOUR AU - Zhao, Zeyu AU - Dickerson, John P. PY - 2020/04/03 Y2 - 2024/03/28 TI - Clearing Kidney Exchanges via Graph Neural Network Guided Tree Search (Student Abstract) JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 34 IS - 10 SE - Student Abstract Track DO - 10.1609/aaai.v34i10.7267 UR - https://ojs.aaai.org/index.php/AAAI/article/view/7267 SP - 13989-13990 AB - <p>Kidney exchange is an organized barter market that allows patients with end-stage renal disease to trade willing donors—and thus kidneys—with other patient-donor pairs. The central clearing problem is to find an arrangement of swaps that maximizes the number of transplants. It is known to be NP-hard in almost all cases. Most existing approaches have modeled this problem as a mixed integer program (MIP), using classical branch-and-price-based tree search techniques to optimize. In this paper, we frame the clearing problem as a Maximum Weighted Independent Set (MWIS) problem, and use a Graph Neural Network guided Monte Carlo Tree Search to find a solution. Our initial results show that this approach outperforms baseline (non-optimal but scalable) algorithms. We believe that a learning-based optimization algorithm can improve upon existing approaches to the kidney exchange clearing problem.</p> ER -