  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.
