Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks
This work addresses the challenge of improving algorithm performance for a fundamental network science problem, though it appears incremental as it builds on existing data-driven methods.
The paper tackles the problem of learning to solve the Quadratic Assignment Problem by training Graph Neural Networks on previously solved instances, achieving good performance in regimes where standard relaxation techniques struggle.
Inverse problems correspond to a certain type of optimization problems formulated over appropriate input distributions. Recently, there has been a growing interest in understanding the computational hardness of these optimization problems, not only in the worst case, but in an average-complexity sense under this same input distribution. In this revised note, we are interested in studying another aspect of hardness, related to the ability to learn how to solve a problem by simply observing a collection of previously solved instances. These 'planted solutions' are used to supervise the training of an appropriate predictive model that parametrizes a broad class of algorithms, with the hope that the resulting model will provide good accuracy-complexity tradeoffs in the average sense. We illustrate this setup on the Quadratic Assignment Problem, a fundamental problem in Network Science. We observe that data-driven models based on Graph Neural Networks offer intriguingly good performance, even in regimes where standard relaxation based techniques appear to suffer.