An Exploration of Optimizing Kidney Exchanges with Graph Machine Learning

The Kidney Exchange Problem (KEP) determines organ exchange chains and cycles amongst a pool of patient-donor pairs (PDP) and non-directed donors (NDD) allowing for the maximum number of kidney transplants. The problem is complicated by optimization occurring over a sparsely connected, directed graph. The presence of an edge in this graph suggests a feasible transplant from a NDD or PDP to another PDP. Many traditional approaches treat the presence of edges in the exchange pool as known and certain. However, the certainty of edges in the exchange is unknown until optimization has been completed and transplants are offered. Edges that are thought to be present may fail because of physician preference, patient behavior, or previously unknown biological incompatibility. As a result, a disparity exists between the number of exchanges planned in optimal solutions and the number of exchanges that take place in the real world. Therefore, this work proposes an integrated KEP optimization methodology that learns a representation of features that affect the realization of optimized solutions. This methodology uses graph machine learning and allows for the integration of additional patient-donor attributes and collaboration between the optimization process and physician behavior. To evaluate this solution method an approach for simulating the implementation of KEP solutions is developed. An analysis of the required data inputs for both the solving and assessment methodology is noted and the potential benefits of the framework are described. A discussion of the limitations of the work is presented and directions for future works are proposed.