Solving the Kidney-Exchange Problem via Graph Neural Networks with No Supervision
This addresses the kidney-exchange problem for healthcare systems, offering an incremental improvement in solution quality.
The paper tackles the NP-hard Kidney-Exchange Problem by proposing a two-stage learning-based approach using an unsupervised Graph Neural Network followed by a deterministic search heuristic, achieving approximate solutions that are on average 1.1 times more valuable than those from a deterministic heuristic alone.
This paper introduces a new learning-based approach for approximately solving the Kidney-Exchange Problem (KEP), an NP-hard problem on graphs. The problem consists of, given a pool of kidney donors and patients waiting for kidney donations, optimally selecting a set of donations to optimize the quantity and quality of transplants performed while respecting a set of constraints about the arrangement of these donations. The proposed technique consists of two main steps: the first is a Graph Neural Network (GNN) trained without supervision; the second is a deterministic non-learned search heuristic that uses the output of the GNN to find paths and cycles. To allow for comparisons, we also implemented and tested an exact solution method using integer programming, two greedy search heuristics without the machine learning module, and the GNN alone without a heuristic. We analyze and compare the methods and conclude that the learning-based two-stage approach is the best solution quality, outputting approximate solutions on average 1.1 times more valuable than the ones from the deterministic heuristic alone.