Graph Neural Networks with No Supervision and Heuristics for the Kidney-Exchange Problem

We introduce a new deep learning (DL) approach for approximately solving the Kidney-Exchange Problem (KEP), an NP-hard problem on graphs. Given a pool of kidney donors and patients waiting for donations, we seek to optimally select a set of donations to optimize transplants performed while respecting a set of constraints about donations. Our technique consists of two steps: First, a Graph Neural Network (GNN) trained without supervision; second, a deterministic non-learned search heuristic that uses the output of the GNN to find a valid solution. To validate our work, we implemented and tested an exact solution using integer programming, two greedy search heuristics without the machine learning module, and the GNN alone. We show that the learning-based two-stage approach has the best solution quality, approximating solutions on average 1.1 times more valuable than the deterministic heuristic alone, showing that DL and GNN shed new light in solving this and related problems.