Clearing Kidney Exchanges via Graph Neural Network Guided Tree Search (Student Abstract) | Proceedings of the AAAI Conference on Artificial Intelligence

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. Login to access subscriber-only resources. Part of the PKP Publishing Services Network Copyright ©

Authors Zeyu Zhao Montgomery Blair High School John P. Dickerson University of Maryland DOI: https://doi.org/10.1609/aaai.v34i10.7267 Abstract 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…

saved by

• Zach Zhao

related reading

• A Gentle Introduction to Graph Neural Networksdistill.pub
• Deep Knowledge Tracingstanford.edu
• OptiTree: Hierarchical Thoughts Generation with Tree Search for LLM Optimization Modelingarxiv.org
• Understanding Convolutions on Graphsdistill.pub
• [2604.18002] Neural Garbage Collection: Learning to Forget while Learning to Reasonarxiv.org
• [2505.17373] Value-Guided Search for Efficient Chain-of-Thought Reasoningarxiv.org
• A Neural Network Framework for Discovering Closed-form Solutions to Quadratic Programs with Linear Constraintsarxiv.org
• Monte Carlo Tree Search: An Introduction | Towards Data Sciencetowardsdatascience.com
• Stream of Search (SoS): Learning to Search in Languagearxiv.org
• [2303.13948] Knowledge Graphs: Opportunities and Challengesarxiv.org
• IROS22-DMMAS_paper_7852.pdfdcslgatech.github.io
• Relating Graph Neural Networks to Structural Causal Modelsarxiv.org