Abstract:Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming.
| Comments: | ICML 2026 |
| Subjects: | Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Neural and Evolutionary Computing (cs.NE); Machine Learning (stat.ML) |
| Cite as: | arXiv:2602.13155 [cs.LG] |
| (or arXiv:2602.13155v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2602.13155 arXiv-issued DOI via DataCite |
Submission history
From: Christopher Morris [view email]
[v1]
Fri, 13 Feb 2026 18:08:23 UTC (91 KB)
[v2]
Wed, 13 May 2026 09:47:05 UTC (107 KB)