Solving the kidney exchange problem via graph neural networks with no supervision

• Published in: Neural computing & applications 2024-09, Vol.36 (25), p.15373-15388
• Main Authors: Pimenta, Pedro F., Avelar, Pedro H. C., Lamb, Luís C.
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Computational Biology/Bioinformatics; Computational Science and Engineering; Computer Science; Data Mining and Knowledge Discovery; Exact solutions; Graph neural networks; Heuristic; Heuristic methods; Image Processing and Computer Vision; Integer programming; Kidneys; Machine learning; Neural networks; Optimization; Original Article; Probability and Statistics in Computer Science; Transplants
• ISSN: 0941-0643; 1433-3058
• DOI: 10.1007/s00521-024-09887-5

This paper introduces a new learning-based approach for approximately solving the Kidney-Exchange Problem (KEP), an NP-hard problem on graphs. The KEP 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 major 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 a valid solution. 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.