{"id":"42559ff4-e3c6-468c-8e4f-d09e3504f6b1","arxiv_id":"2412.08287","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"DistrictNet learns CMST edge weights with a GNN in a decision-aware way and produces districting solutions that are about 10% cheaper on average than existing methods on real cities.","lead":"This paper introduces DistrictNet, a learning pipeline that partitions a city into delivery districts by training a graph neural network to parameterize a simplified optimization problem (the capacitated minimum spanning tree). On seven real cities, DistrictNet's districts cost about 10% less than four existing methods, and it generalizes from small training examples to much larger cities.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Table 7 contradicts 'consistently outperforms': DistrictNet is not best in 8 of 35 city/target cells and is worse than no-learning AVGTSP in 6, all in Manchester (t=3,30) and Paris (t=3-20); the 10% average is not uniform.","rationale":"I read the central claim as the empirical one in Section 5.2 and Result 2, not as a theorem. The reader's weakest_assumption about CMST surrogate fidelity is less decisive than it appears: since any feasible 0/1 CMST solution is a vertex of the convex hull of CMST solutions, there always is some edge-weight vector that makes a given target districting solution optimal; the real issue is whether the GNN's learned weights generalize. The paper's own Table 7 gives direct evidence that they do not generalize uniformly: 8 of 35 cells are not best, and 6 are worse than AVGTSP. This is a falsifiable, load-bearing problem for the wording 'consistently outperforms.' If the claim is meant only as average performance, it should be restated. I do not think this warrants rejection: the average improvements are plausible, code is public, and training on 100 tiny instances is a real contribution. But the headline claim needs per-cell uncertainty and a more modest generalization statement, which matches a CONDITIONAL verdict. Hence I keep the reader's verdict unchanged.","tokens_in":19784,"tokens_out":12544,"duration_ms":142095,"concrete_test":"Re-run the 35 test cells of Table 7 with at least 10 independent ILS restarts and independent Monte-Carlo TSP scenarios, and compute paired differences DistrictNet minus AVGTSP per city/target cell with bootstrap confidence intervals; then run the 2,000-BU experiment with the same replication protocol. If the paired one-sided test over cells does not reject a 50% win rate, or if the 2,000-BU advantage falls within the bootstrap noise, then 'consistently outperforms' and the large-OOD generalization claim should be replaced by a claim of average improvement on UK-like cities.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim in Section 5.2 ('consistently outperforms ... around 10%') is load-bearing and is directly weakened by the paper's own Appendix C.2. In Table 7, DistrictNet is not the best method on 8 of 35 test instances. It is worse than the non-learning AVGTSP baseline on Manchester t=3 (1165.72 vs 1158.66, +0.6%), Manchester t=30 (316.55 vs 299.69, +5.6%), and Paris t=3,6,12,20 (+4.7% to +9.7%); it only ties AVGTSP on Paris t=30. The average 10% reduction in Table 1 is also not uniform: relative to AVGTSP the average gain is only 4.44%, and the gain is concentrated in UK cities closer to the training distribution. The 2,000-BU result (Table 2) is a single run with no error bars and shows only +2.6% over AVGTSP, so the strong generalization claim rests on one point estimate. The theoretical surjection argument in Section 3 does not fill this gap: it shows only that some CMST weights can make a given districting solution optimal, not that the learned GNN weights will do so out of distribution.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DistrictNet, a decision-aware learning pipeline for geographical districting-and-routing. A graph neural network predicts edge weights for a capacitated minimum spanning tree (CMST) surrogate, the CMST is solved as a combinatorial optimization layer, and a Fenchel-Young loss is used to train the network by imitating optimal solutions on small synthetic instances. The method is evaluated on seven real-world cities (120--983 basic units) and on one 2,000-BU region, with claims of roughly 10% average cost reduction against existing heuristics and of strong out-of-distribution generalization.","tokens_in":20039,"tokens_out":6860,"duration_ms":81700,"significance":"If the empirical claims hold, this is a practically valuable contribution: training on small instances and solving a linear CMST surrogate in minutes is far cheaper than exact stochastic districting, and the paper's public code and careful experimental design (held-out cities, a Wilcoxon test, in-distribution optimality-gap study in Table 6, and compactness analysis in Table 8) are commendable. However, the headline claim of consistent ~10% improvement is weakened by the paper's own detailed results, and the theoretical motivation for the surrogate is not fully established. The central contribution is therefore defensible but needs revision before the claims can be accepted as stated.","major_comments":[{"comment":"The statement that 'DISTRICT NET consistently outperforms the benchmarks as it produces districting solutions with significant cost reductions of around 10% compared to all other methods' is contradicted by the paper's own Table 7. DistrictNet is not the best method on 8 of 35 test instances, and it is worse than the non-learning AVGTSP baseline on Manchester t=3 (1165.72 vs 1158.66), Manchester t=30 (316.55 vs 299.69), and Paris t=3,6,12,20 (relative losses of +4.7% to +9.7%), while tying AVGTSP on Paris t=30. Moreover, Table 1's average of 4.44% relative to AVGTSP is not 'around 10%'; the larger savings are concentrated in UK cities closer to the training distribution. Please report per-city and per-target win/loss/tie counts, add confidence intervals or error bars, and revise the 'consistently outperforms' and 'around 10%' wording to reflect the average and its variability accurately.","section":"Section 5.2, Appendix C.2 (Table 7)"},{"comment":"The assertion that 'there always exists a CMST problem such that their optimal solutions coincide' does not follow from the surjectivity argument given in Section 3. Surjectivity shows only that every districting solution can be represented as a set of subtrees; it does not establish that arbitrary district costs can be expressed as additive edge weights, nor that the optimal CMST solution for the learned weights will coincide with or well-approximate the optimal districting solution. This is the load-bearing assumption of the method, because the GNN edge weights are the only mechanism by which the surrogate can capture district costs. The paper provides no proof or approximation guarantee for this surrogate fidelity. Please either supply a precise proof with the required conditions, or explicitly state that surrogate fidelity is an empirical assumption supported solely by the experiments.","section":"Section 3, Section 4.2"},{"comment":"The claim that DistrictNet 'generalizes to even the largest real-world problems' rests on a single run on the 2,000-BU Ile-de-France instance, with no error bars or repetition. In Table 2, DistrictNet improves over AVGTSP by only 2.6% and over PRED GNN by 4.0%, which is much smaller than the average improvements reported on smaller cities. This single point estimate does not support the strong wording of Result 2. Please provide multiple runs with variance, or substantially temper the generalization claim for very large instances.","section":"Section 5.2, Table 2, Result 2"}],"minor_comments":[{"comment":"Please clarify that the relative percentages are cost increases relative to DistrictNet, with lower being better, and consider reporting the absolute costs or a boxplot in addition to the average.","section":"Table 1"},{"comment":"The text says the target CMST solution in Equation (5) is 'constructed using a single observation of our random constructor', but later states that 'the randomized target constructor uses 1,000 samples'. Please reconcile these two statements, as they affect the reported bias-variance properties of the training procedure.","section":"Appendix A.4"},{"comment":"The legend of Figure 3 lists BD, FIG, and PRED GNN but omits AVGTSP, even though the surrounding text refers to benchmark methods generally; please include AVGTSP or explain its omission.","section":"Figure 3"},{"comment":"There is a typo in the header 'A VGTSP'; it should read 'AVGTSP'. Additionally, the blue/orange highlighting in Table 7 is not accessible in grayscale print; consider adding textual markers.","section":"Table 2"}],"recommendation":"major_revision","confidential_remarks":"The underlying method and experiments are worth publishing after a revision that honestly aligns the headline claims with the detailed results in Table 7 and Table 2, and that clarifies the status of the surrogate-fidelity assumption."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nThis paper is worth your attention: it introduces a decision-aware learning pipeline for districting that is genuinely new. The authors train a GNN to predict edge weights for a capacitated minimum spanning tree, and learn with a Fenchel-Young loss against target CMST moments constructed from optimal districting solutions via a randomized Kruskal. That combination—GNN + CMST layer + randomized target constructor—is not in prior work. On the empirical side, they compare against four baselines on seven real cities, include a Wilcoxon test, report an in-distribution optimality gap of 2.3% versus 4-4.6% for baselines, and ship public code. The average cost reduction on their 35 test instances is real.\n\nBut the headline claim \"consistently outperforms\" is not supported by the paper's own Table 7. DistrictNet is not the best method on 8 of 35 city/target combinations, and it is worse than the no-learning AVGTSP baseline on Manchester t=3, t=30 and on every Paris target (t=3,6,12,20), losing by 4.7-9.7%. The average reduction versus AVGTSP is only 4.44%, not 10%. The gains are concentrated in UK cities that resemble the training distribution; Paris, with its small dense BUs, is a clear failure case. The 2,000-BU experiment is a single run with no error bars and only +2.6% over AVGTSP, so Result 2 is weaker than stated.\n\nThe theoretical framing also needs attention. Section 3 claims that because there is a surjection from CMST solutions to districting solutions, there always exists a CMST problem whose optimal solutions coincide. That is a trivial existence statement—you can always design edge weights to make any given feasible partition optimal. It does not justify that additive edge-weight costs can represent arbitrary district cost functions, nor that the learned weights will generalize. The empirical results are the only support for surrogate fidelity, and they are mixed.\n\nIf I were handling this paper, I would ask for a scope-down of the claims, error bars on the large-scale result, and a clearer separation between the existence argument and the approximation assumption. The method is solid, the code is public, and the negative results are instructive.\n\nRecommendation: send it to peer review. With revisions, it's a solid NeurIPS/ICML paper.","headline":"DistrictNet is a genuinely new decision-aware CMST surrogate with real empirical gains, but the paper overclaims consistency and the theoretical foundation is weaker than presented.","tokens_in":20621,"tokens_out":5574,"would_cite":true,"duration_ms":58842,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A GNN trained on 30-BU towns finds near-optimal districts in cities up to 2,000 BUs, with about 10% lower routing costs than four baselines.","keywords":["districting","capacitated minimum spanning tree","graph neural network","decision-aware learning","Fenchel-Young loss","combinatorial optimization layer","routing","generalization"],"falsifier":"Take a mid-size city (for example 60 BUs and 10 districts) where optimal districting is computable by full enumeration, train DistrictNet on the paper's 30-BU instances, and compare its output's true Monte-Carlo TSP cost to that exact optimum. If the CMST solution induced by learned weights is systematically more than a few percent worse than optimal districting, the surrogate-fidelity assumption fails; a cheaper check is to build a synthetic instance whose true district costs are deliberately non-additive, such as a river crossing penalty, and see whether the reported 10% margin persists.","tokens_in":1899,"feed_emoji":"🗺️","tokens_out":2508,"duration_ms":83445,"temperature":0.7,"pith_summary":"DistrictNet claims that a graph neural network can learn to solve real-world geographical districting-and-routing problems by predicting edge weights for a capacitated minimum spanning tree (CMST), then converting the optimal CMST into districts. The training is decision-aware: the model imitates optimal solutions of tiny instances, using a Fenchel-Young loss whose gradient flows through a black-box CMST solver. On seven real cities with 120 to 983 basic units and on a 2,000-unit region, the resulting solutions cost about 10% less than existing district-cost estimators embedded in local search, and the improvement is consistent across city sizes and district sizes. The paper presents this as evidence that a structured surrogate optimization layer generalizes far better than learned cost estimators alone.","feed_headline":"Trained on tiny towns, DistrictNet cuts districting costs by 10%","feed_subtitle":"One GNN plus a spanning-tree optimizer, trained on 30-node cities, generalizes to cities with up to 2,000 basic units.","key_machinery":"The machinery is the capacitated minimum spanning tree as a differentiable optimization layer: a CMST finds $k$ subtrees of bounded size minimizing the sum of edge weights, and here the edge weights $\\theta$ are predicted by a GNN. The CMST layer solves $\\max_{y \\in \\mathcal{Y}} \\theta^\\top y$ over the convex hull of feasible subtree incidence vectors, and the optimal subtree partition maps surjectively to a districting partition. Training uses the Fenchel-Young loss $L_{\\mathrm{FY}}(\\theta,\\bar{\\mu}) = \\Omega^*(\\theta) + \\Omega(\\bar{\\mu}) - \\theta^\\top \\bar{\\mu}$, with gradients estimated by perturbed optimizers, and targets $\\bar{\\mu}$ are expected CMST solutions built from optimal districts by running Kruskal with random edge weights.","core_discovery":"The central claim is that a parameterized CMST is a faithful surrogate for the districting-and-routing problem, and that a GNN can learn CMST edge weights from a handful of optimal small instances so that solving the CMST yields near-optimal districts on large out-of-distribution cities. The paper relies on a surjection from CMST solutions to district solutions: any district is the vertex set of a subtree, so for every districting problem there exists a CMST whose optimal solution coincides with the optimal districting. DistrictNet learns this CMST by minimizing a Fenchel-Young loss against target CMST moments reconstructed from optimal districting solutions via a randomized spanning-tree constructor. Empirically it reports cost reductions of roughly 10% over four benchmarks, up to 13% in the best cases, and a 2,000-BU instance solved within the same pipeline that was trained on 30-BU instances.","pith_inferences":["Beyond the paper's experiments, the same decision-aware imitation scheme could be applied to other NP-hard graph partition problems whose solutions admit a tree structure, such as school zoning or sales territory design, without redesigning the optimization layer.","The additive edge-weight model cannot represent arbitrary district cost functions exactly; the surjection guarantee only says an optimal CMST exists for some weights, not that learned weights will find it, so out-of-distribution success remains an empirical property that should be re-tested when demand distributions or district constraints change.","A testable extension is to train DistrictNet on geographies with asymmetric demand or barriers such as rivers and highways, to see whether the learned edge weights absorb these costs; if not, the 10% margin may shrink on such instances.","A controlled comparison between the Fenchel-Young imitation objective and direct cost regression, keeping the CMST structure fixed, would isolate how much of the gain comes from decision-aware training as opposed to the surrogate model itself."],"forward_implications":["Practitioners can train on 100 small optimal instances of 30 BUs and deploy the same model on cities hundreds of times larger, obtaining solutions in minutes rather than CPU-core days.","DistrictNet generalizes across city structures and target district sizes, so a single trained model can evaluate a family of districting settings before a final choice is made.","The reported cost reduction of about 10% is statistically significant against BD, FIG, PREDGNN, and AVGTSP under a fixed ILS time budget, and the margin tends to grow with district size.","Because the training pipeline only needs district partitions as targets, the same CMST surrogate could be retrained for other district cost functions, such as fairness or compactness objectives.","DistrictNet also produces more compact districts, measured by Reock's score, indicating that the learned solutions are geographically tighter and not merely cheaper in tour length."],"supporting_citations":[{"why":"Supplies the PREDGNN benchmark, the real UK city test instances, and the C++ district-cost evaluation used in all experiments.","marker":"Ferraz et al., 2024"},{"why":"Provides the differentiable perturbed optimizer whose gradient formula lets DistrictNet train through the CMST solver.","marker":"Berthet et al., 2020"},{"why":"Defines Fenchel-Young losses and their convexity and gradient properties, which justify the imitation objective.","marker":"Blondel et al., 2020"},{"why":"Links the regularized loss to the Fenchel conjugate and perturbation, giving the stochastic-gradient training scheme.","marker":"Dalle et al., 2022"},{"why":"Presents the closest alternative partial-target learning scheme for clustering with perturbed spanning forests, which DistrictNet contrasts with its randomized constructor and convex Fenchel-Young loss.","marker":"Stewart et al., 2023"},{"why":"Provides the BHH formula underlying the BD cost estimator and the general theory of tour-length estimation that motivates surrogate costs.","marker":"Beardwood et al., 1959"},{"why":"Defines the BD benchmark cost model for vehicle tours used as a baseline.","marker":"Daganzo, 1984"},{"why":"Defines the FIG benchmark cost model, an extension of BD used as a baseline.","marker":"Figliozzi, 2007"},{"why":"Supplies the graph-convolution update rule used by the GNN that predicts CMST edge weights.","marker":"Morris et al., 2019"}],"fun_headline_variants":["GNN trained on 30-node towns cuts large-city districting costs by 10%","DistrictNet: trained on 30-node towns, cuts 2,000-node city costs 10%","DistrictNet learns city districting from tiny examples, cutting costs 10%","One GNN, many districts: DistrictNet scales from 30 to 2,000 nodes","Decision-aware GNN cuts large-city districting costs by 10%"],"cache_read_input_tokens":22656,"weakest_assumption_plain":"The whole approach rests on the idea that the true cost of a district can be captured by adding up learned numbers on the edges of a tree inside that district, so the best tree partition is also the best district partition. If real district costs cannot be squeezed into that additive form, the learned model has no guarantee of matching the true optimum and only the test cities stand behind it.","fun_headline_variants_meta":{"raw":{"variants":["GNN trained on 30-node towns cuts large-city districting costs by 10%","DistrictNet: trained on 30-node towns, cuts 2,000-node city costs 10%","DistrictNet learns city districting from tiny examples, cutting costs 10%","One GNN, many districts: DistrictNet scales from 30 to 2,000 nodes","Decision-aware GNN cuts large-city districting costs by 10%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00139,"raw_usage":{"total_tokens":5585,"prompt_tokens":862,"completion_tokens":4723,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":478,"completion_tokens_details":{"reasoning_tokens":4610}},"tokens_in":478,"tokens_out":4723,"duration_ms":32497,"temperature":1.0,"reasoning_tokens":4610,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:00:45.249751+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a mid-size city (for example 60 BUs and 10 districts) where optimal districting is computable by full enumeration, train DistrictNet on the paper's 30-BU instances, and compare its output's true Monte-Carlo TSP cost to that exact optimum. If the CMST solution induced by learned weights is systematically more than a few percent worse than optimal districting, the surrogate-fidelity assumption fails; a cheaper check is to build a synthetic instance whose true district costs are deliberately non-additive, such as a river crossing penalty, and see whether the reported 10% margin persists.","supporting_citations":[{"cited_title":"(2024) does not scale well to large instances","cited_arxiv_id":null,"evidence_quote":"Supplies the PREDGNN benchmark, the real UK city test instances, and the C++ district-cost evaluation used in all experiments."}],"review_version":1}