Solving the kidney exchange problem using graph neural networks trained with no supervision

Abstract

This work introduces a new machine learning-based approach for 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 kidney donations so as 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 one 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 a valid solution. To allow for comparisons, we have also developed and experimented with an exact solution method that uses integer programming, two greedy search heuristics without the machine learning module, and the GNN alone with no heuristic. Finally, we analyze and compare the methods ac curacy and performance and conclude that the learning-based two-stage approach is the best one in terms of solution quality, as it outputs approximate solutions on average 1.1 times better than the ones from the deterministic heuristics alone.

Esse trabalho introduz um método baseado em aprendizado de máquina para resolver aproximadamente o problema de troca de rins (Kidney Exchange Problem), um problema NP-difícil em grafos. A técnica proposta consiste em dois principais passos: o primeiro é uma rede grafo-neural treinada sem supervisão que prediz um score para cada aresta do grafo de entrada; o segundo é uma heurística de busca sem aprendizado que usa esses scores para construir uma solução válida. Para fins de comparação, também foi implementado um método de solução exata que usa programação inteira e duas heurísticas de busca usadas sem o módulo de aprendizado, assim como uma versão da GNN sem uma heurística. Os métodos são analisados e comparados entre si, e é concluido que o método de dois passos baseado em aprendizado de máquina atinge os melhores resultados em termos de qualidade, construindo soluções aproximadas em média 1.1 vezes melhores que as de uma heurística sozinha.