Learning to Approximate Uniform Facility Location via Graph Neural Networks

AI summary

Overview

Research area: Machine learning for combinatorial optimization, specifically a bridge between classical approximation algorithms and message-passing graph neural networks (MPNNs) applied to the Uniform Facility Location problem (UniFL).

Technical level: Advanced. The paper assumes familiarity with approximation algorithms, MPNNs, metric spaces, and unsupervised loss design.

Scope: The paper introduces a fully differentiable, unsupervised MPNN whose parameters can be initialized to reproduce a known approximation algorithm for UniFL, while remaining trainable to improve empirical performance and generalize to larger instances.

What This Paper Is About

Classical approximation algorithms for UniFL give rigorous worst-case guarantees but are distribution-agnostic and non-differentiable, while learned solvers can adapt to data but often need expensive supervision, reinforcement learning, or gradient estimators, and usually come without guarantees. This paper asks whether the two can be merged: a neural architecture that is differentiable and trainable without solver supervision, yet still provably approximates the optimal solution. The authors build such an architecture for UniFL by embedding the local decision rules of a known approximation algorithm (radius computation and randomized facility opening) into an MPNN, then refine those parameters by training on an unsupervised expected-cost loss.

Key Contributions

1. A fully differentiable, unsupervised MPNN for UniFL. The architecture mirrors the structural components of classical approximation algorithms — local radius estimation, opening-probability computation, and facility opening via sampling. A slight change to the cost function (replacing distance with squared Euclidean distance in the last term of the loss) enables end-to-end k-means clustering.

2. Parameters that provably recover a constant-factor-style guarantee. The authors show how to initialize the model with parameters that yield approximation guarantees matching the non-learned algorithm, and that these parameters can be improved during training, bridging approximation algorithms and neural heuristics.

3. Training on finite data with a generalization guarantee. They show that a finite training set plus a differentiable regularization term suffices to learn parameters that simulate the target algorithm on UniFL instances of the same size (Proposition 5), with the guarantee holding for all instances of that size.

4. Empirical gains. The architecture is reported to outperform classical non-learned approximation algorithms and to be competitive with a state-of-the-art branch-and-cut solver, while generalizing reliably to instances significantly larger than those seen in training.

Main Findings

• Radius-based approximation is the anchor. Following Mettu and Plaxton (2003), the radius r_x of a point x is defined by requiring the sum of r_x − d(y, x) over all y in X within B(x, r_x) to equal 1. Lemma 1 (Bădoiu et al., 2005) states that the sum of these radii lies in Θ(Opt_S), so knowing radii gives a constant-factor approximation of the optimum value.

• A simple distributed algorithm attains O(log n). The algorithm SimpleUniformFL computes each radius, opens a facility at x independently with probability min(1, c · ln n · r_x) for c ≥ 2, and then opens a facility at any point without an open facility strictly within distance 1. Proposition 2 establishes expected cost O(log n) · Opt_S.

• An MPNN can reproduce that algorithm exactly in the limit. Proposition 3 shows that for every n there is a discretization 0 = a_0 < a_1 < ... < a_k = 1 and a parameter assignment θ* for an MPNN mpnn_θ : V(G_n) → [0,1] such that the induced opening probabilities satisfy E[cost(X, p)] ≤ O(log n) · Opt_S on every UniFL instance of order n.

• There is a fundamental limitation for deterministic MPNNs. Proposition 4 states that for any deterministic MPNN that takes an edge-weighted graph encoding a UniFL instance and outputs opening probabilities, there is an n_0 such that for every n ≥ n_0 some instance of size n satisfies E[|F| + Σ min{1, dist(p, F)}] ≥ (ln n / 2) · Opt_S. Constant-depth deterministic MPNNs therefore cannot reach an O(log n) factor.

• A recursive variant reaches constant-factor approximation in expectation. The algorithm UniformFLRecursionStart repeatedly calls RecursiveUniformFL, which opens facilities with probability min{1, c · d(x, F), c · r_x}, assigns a point x to its closest open facility f when d(x, f) ≤ 6 r_x, and otherwise returns x as unassigned for the next round. The paper argues the combined solution over recursive calls is a constant approximation in expectation.

• Generalization from finite data is provable. Proposition 5 states that for every n there exists an MPNN, a finite training set T_{n,ε} of pairs ((G, v), p_v) with p_v the opening probability from Proposition 3, and a differentiable regularization term r_n, such that a small training error plus regularization implies the predicted probability vector is within ε of the target for all instances of size n.

• Training loss is the expected cost itself. The unsupervised loss in Equation 5 sums expected opening cost (Σ p_f plus Σ Π (1 − p_x) over points within distance 1) and expected connection cost (Σ Σ dist(x, f) · p_f · Π (1 − p_z) over closer points). For a graph with maximum degree d, evaluating this loss costs O(n d²).

• Experimental setup. Synthetic random geometric graphs are generated in 2, 5, and 10 dimensions with 1000 vertices each, sampled from a Gaussian mixture with 100 isotropic Gaussian components with random centroids and edges within unit Euclidean distance; 10,000 such graphs per dataset are split 8:1:1 into training, validation, and test sets, with additional test sets ranging from 2000 to 10,000 vertices for size generalization. A city map dataset from Liang et al. (2025) of four large-scale metropolitan road networks (vertices = junctions, weighted edges = roads, normalized so the maximum road length is 1) is used for real-world applicability.

• Baselines and protocol. Comparisons are against an integer-linear program, SimpleUniformFL, UniformFLRecursionStart (with constant c tuned by grid search), and Algorithm 3.1 (O(1)-UFL) from Gehweiler et al. (2014) as a tuning-free baseline. Stochastic baselines are averaged over 1000 samples with fixed seeds; the neural model is trained with the Equation 5 loss across 5 seeds, and inference guides sampling in SimpleUniformFL with expected cost over 1000 samples. A k-means variant replaces the distance in the last loss term with squared Euclidean distance and is compared against k-means and k-medoids with k fixed to the MPNN's predicted facility count.

• Reported cost components from the experiment table. For the ILP solver on the five synthetic settings, Table 1 lists opening cost 366.302, connection cost 279.827, total 646.129, and time 0.263 for Geo-1000-2; 369.884, 403.072, 772.956, and 0.299 for Geo-1000-5; 291.488, 520.611, 812.099, and 0.689 for Geo-1000-10; 686.578, 265.496, 952.074, and 0.089 for Geo-1000-10-sparse; and 158.483, 509.294, 667.777, and 8.179 for Geo-1000-10-dense. The SimpleUFL opening costs shown are 512.082 for Geo-1000-2 and 523.173 for Geo-1000-5. The remainder of Table 1 and the other result tables are cut off in the provided content, so the full numerical comparison against the MPNN, the ILP optimality ratios, and the runtime comparisons are not reported here.

• Hardware. Neural and stochastic methods were run on an NVIDIA L40S GPU; the ILP and k-means were run on an Intel Xeon Silver 4510 CPU.

• Problem hardness context. UniFL remains NP-hard even with identical opening costs, and general facility location is APX-hard: no polynomial-time algorithm can achieve a factor better than 1.463 unless P = NP (Guha and Khuller, 1999). The paper notes that KMeans++-style scalable clustering methods are among the practical alternatives it compares against.

Methodology in Plain English

The authors start from a simple, well-understood randomized approximation algorithm for UniFL. That algorithm has two ingredients: a per-point "radius" that measures how much demand a facility at that point would serve if the opening cost is 1, and a rule that opens a facility at a point with probability proportional to that radius (times ln n), with a fallback that opens any point left unserved within distance 1.

They then rewrite each of those steps as differentiable neural operations. Radius computation, which is a sum of ReLU-shaped contributions from a point's neighbors, is computed by a two-layer feed-forward network applied to a discretized set of thresholds. Opening probabilities become another two-layer network of n and the estimated radius. Because the whole pipeline is differentiable and the loss is the analytically computed expected cost of the randomized solution (rather than a single sampled discrete solution), training needs no optimal solutions, no solver calls, and no straight-through or Gumbel-style gradient estimators. Training simply minimizes the expected cost over a distribution of instances; a separate regularization term controls how close the learned parameters stay to the guaranteed-correct ones. For a larger recursion, the authors add a second mechanism where a point's opening probability also depends on its distance to already-opened facilities, and points not assigned within 6 r_x are passed to the next round.

The empirical work follows a standard protocol: generate synthetic geometric graphs and real road networks, train with the unsupervised loss, then at inference sample from the learned probabilities and average the resulting cost over 1000 samples, comparing against the non-learned algorithms, an ILP optimum, and clustering baselines.

Why This Matters

Impact on research. The paper targets a gap that most learning-for-optimization work leaves open: methods that are simultaneously differentiable, cheap to train, and equipped with worst-case guarantees. Proposition 3 shows a guarantee can be recovered by a neural architecture, and Proposition 4 shows a hard limit on what deterministic MPNNs of that form can do, which sharpens the boundary between what learning can and cannot add on top of classical approximation. Proposition 5 ties training on a finite dataset to a guarantee over all instances of the same size, which is unusual in this literature and directly addresses out-of-distribution robustness.

Real-world applications (as listed in the paper):

• Logistics and transportation planning
• Supply-chain design
• Clustering and data summarization
• Network design

Industry relevance. Facility location underlies warehouse siting, server and content-delivery placement, and sensor or service-point deployment. A method that trains on a distribution of instances without calling an ILP solver and still carries approximation guarantees is attractive where solver calls are too slow or where instance families repeat, such as in recurring planning pipelines. The k-means variant extends the same machinery to a ubiquitous clustering primitive.

Future Directions

• A differentiable version of the recursive, constant-factor algorithm. The learned model is trained for the O(log n) SimpleUniformFL procedure, while UniformFLRecursionStart provides the constant-factor guarantee but is used only as a stochastic baseline. Neuralizing the recursion, with its distance-to-open-facility term and 6 r_x assignment rule, is the natural next step toward learned solutions with a constant-factor guarantee.

• Working around the Proposition 4 impossibility. Since deterministic constant-depth MPNNs cannot achieve an O(log n) factor in that setting, it remains open which relaxations — randomization inside the architecture, greater depth, or different output structures — recover stronger guarantees.

• Extending beyond uniform opening costs. UniFL is a simplified case; general (non-uniform) metric facility location, with per-facility opening costs, is the broader problem class and is not addressed by the current architecture.

• Broader empirical validation. The real-world evaluation uses four road-network graphs from one city map dataset, and these graphs violate the triangle inequality. Testing on more diverse non-metric and metric instance families, and reporting full comparative tables against branch-and-cut solvers and clustering baselines, would clarify how far the empirical advantage extends.

Target Audience

Researchers and graduate students working at the intersection of machine learning and combinatorial optimization, particularly those interested in neural combinatorial solvers, unsupervised losses for discrete problems, and algorithms with predictions. It is also relevant to approximation-algorithms researchers curious about how local decision rules like radius-based facility opening transfer into neural architectures, and to practitioners in logistics, supply chain, and network planning who need learnable methods that retain quality guarantees.

Authors’ 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.