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.