Clearing Kidney Exchanges via Graph Neural Network Guided Tree Search (Student Abstract)

2020-06-02

Proceedings of the AAAI Conference on Artificial Intelligence, 34

Volume

Vol. 34 No. 10: Issue 10: AAAI-20 Student Tracks

Student Abstract Track

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.

10.1609/aaai.v34i10.7267