{"id":"65c10b3c-856d-4be3-aa08-5e438b5d9ace","arxiv_id":"2412.08296","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A graph diffusion model trained on suboptimal heuristic solutions matches or beats solvers and discriminative baselines on the multi-server computation offloading problem, with claimed near-optimal convergence.","lead":"This paper introduces GDSG, a graph-based diffusion model that generates high-quality solutions to a hard multi-server computation offloading problem after training only on cheap, suboptimal examples. The method could make AI-based network optimization practical when optimal training data is too expensive to produce.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central near-optimality claim relies on 'gt' test labels whose generation for large scales is undescribed; if those labels are heuristic, Table I measures imitation of the heuristic, not convergence to the optimum.","rationale":"The paper has real strengths: the code and datasets are open-sourced, the comparison protocol on the suboptimal training sets is reproducible, and the padding-edge gating improvement is a concrete engineering contribution. My concern is not about the internal mechanics of the diffusion training but about the yardstick used for the paper's central empirical claim. The largest test scales are labeled 'gt,' yet no exact generation method for them is described; the same section says no optimal solver is available. If those labels are heuristic, Table I's Exceed ratios cannot distinguish 'near-optimal' from 'close to the heuristic label set,' which undercuts the abstract's convergence claim. The reader's weakest assumption, E(Theta_x)=theta*, is also genuine and likely false for the MCMF heuristic, so I agree that Sec. III-B is not a solid proof; however, I see the label-generation gap as the more load-bearing issue because it affects the main empirical evidence directly. The existing CONDITIONAL verdict remains appropriate: the authors should either document how large-scale 'gt' labels were produced and verify a subset against independent exact solutions, or soften the optimal-convergence claim. If the proposed checks fail, the verdict should move to REJECT.","tokens_in":34280,"tokens_out":12068,"duration_ms":128494,"concrete_test":"Take a mid-scale test scale (e.g., gt7s24u or gt10s31u) from the open-sourced dataset and independently compute a certified upper bound on the true optimal cost for those instances, using a custom branch-and-bound/MINLP solver or a substantially stronger heuristic with a proven gap bound. Compare the provided 'gt' labels with those bounds. If the labels are not within a small gap of the certified optimum, recompute Table I's Exceed ratios against the true optimal costs; if GDSG's ratios rise above about 1.5 or GDSG no longer beats HEU, the optimal-convergence claim is unsupported. As a complementary check on the theory, on small gt3s6u instances compare the empirical mean of MCMF-generated suboptimal parameterizations with theta*; if the mean is far from theta*, Eq. (9) cannot be invoked.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that GDSG converges to the optimal solution is supported mainly by Table I, where the Exceed ratio is computed against labels of test sets named gt7s24u, gt7s27u, gt10s31u, gt10s36u, gt20s61u, and gt20s68u. Section V-A explains how small-scale ground-truth labels are produced by exhaustive search, but it does not describe any exact method for the 7-20 server test scales, and it states that an optimal solver is not available. If those labels were generated by the same MCMF heuristic used to create the suboptimal training sets (perhaps with more random restarts), then HEU's Exceed ratio above 1 would only reflect label selection, and GDSG's ratios near 1.1-1.2 would show that the model reproduces the heuristic labels, not that it approaches the true optimum. That would make the 'converging to the optimal solution' claim circular. The separate assumption E(Theta_x)=theta* in Sec. III-B is likewise unverified and likely false for MCMF data, but even a repaired proof cannot validate the empirical numbers without true labels for the large test scales.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GDSG, a graph-diffusion-based generative model for the multi-server multi-user computation offloading (MSCO) problem in MEC networks. The central claim is that GDSG can be trained on suboptimal datasets, produced cheaply by an MCMF heuristic, and still generate solutions that converge to the optimal solution with high probability. The authors reformulate the optimization as solution-distribution learning, provide a theoretical argument based on Chebyshev's inequality that repeated sampling from a learned distribution near the optimal parametrization can hit the optimum, and introduce a multi-task GNN with a padding-edge gating mechanism. Experiments on synthetic datasets report Exceed ratios below 1.1 on most test scales, with cost savings up to 56.62% over a discriminative GNN on ground-truth training data and 41.06% on suboptimal training data. The paper also claims near-100% task orthogonality between discrete and continuous diffusion tasks. The code and datasets are open-sourced.","tokens_in":34495,"tokens_out":8327,"duration_ms":79548,"significance":"If the central claims hold, the work would be a practically valuable contribution: it offers a way to train an optimization solver from cheap suboptimal data, avoiding the need for expensive ground-truth labels, and it provides an open-source dataset and implementation. The empirical comparison against a same-architecture discriminative GNN is a strength, and the padding-edge gating mechanism appears to improve generalization on non-fully-connected graphs. However, the theoretical guarantee rests on an unverified unbiasedness assumption E(Theta_x)=theta*, and the evaluation on large test scales relies on labels whose provenance is not described. The orthogonality claim, as written, is internally inconsistent because orthogonality corresponds to cosine 0, not 1. These issues leave the main contributions currently under-supported.","major_comments":[{"comment":"The test sets gt7s24u, gt7s27u, gt10s31u, gt10s36u, gt20s61u, and gt20s68u are named 'gt' (ground-truth), but Section V-A only describes exhaustive generation for small-scale ground-truth datasets and explicitly states that 'an optimal solver is not available.' The method used to produce the labels for the larger test scales is not disclosed. If those labels are generated by the same MCMF heuristic, possibly with more restarts, then the Exceed ratios in Table I measure agreement with the heuristic's choices rather than closeness to the true optimum, and the central claim that GDSG 'converges to the optimal solution' is not supported by the data. Please specify the exact label-generation procedure for every test scale, or rename these sets and adjust the claims accordingly.","section":"Section V-A, Table I"},{"comment":"The convergence argument assumes E(Theta_x)=mu=theta*, i.e., that the mean of the suboptimal parameterizations equals the optimal parameterization. This assumption is not derived from the MCMF heuristic and is not tested in Section V-B; the empirical measurement of the model output variance (on the order of 1e-4) addresses spread but not bias. If the heuristic is systematically biased toward certain allocation patterns, Chebyshev's inequality with respect to theta* fails, and the repeated-sampling argument for hitting y* collapses. Please verify the mean condition on the actual generated datasets, or replace the guarantee with a bias-aware bound involving |E(Theta_x)-theta*|.","section":"Section III-B, Eq. (9)"},{"comment":"Orthogonal gradient vectors have cosine 0, yet the text and the figure caption state that 'cosine values approaching 1' and 'orthogonal gradient proportions approaching 100%' indicate good orthogonality, and DiGNN is criticized for having cosine values 'far away from 1.' As written, the reported numbers are internally contradictory: a cosine near 1 means the gradients are nearly parallel, not orthogonal. Please clarify the metric actually computed (e.g., 1 - |cos|, or the angle itself) and re-state the claim; otherwise, the task-orthogonality contribution is not interpretable.","section":"Section V-C, Fig. 4"},{"comment":"The derivation of the lower bound on the number of samples n is not rigorous. The quantity p_epsilon is a probability determined by the distribution, not a free parameter, and replacing Chebyshev's '>=' with '>' on the grounds that the distribution is not three-point does not provide a uniform margin, so the passage from Eq. (11) to Eq. (12) is not justified. Moreover, Eq. (12) depends on the unknown p_epsilon, making it not a computable lower bound. The paper should either provide a clean derivation (e.g., using a bias-aware or union-bound argument) or present this as a heuristic scaling argument rather than a proof.","section":"Section III-B, Eqs. (11)-(13)"}],"minor_comments":[{"comment":"The phrase 'converging to the optimal solution large probably' in the abstract should read 'with high probability' to match the full text.","section":"Abstract"},{"comment":"The sentence 'we use exhaustive methods to generate small-scale ground-truth datasets but the time complexity is very high (over 30sec for a single instance of 80 nodes)' is confusing because 80 nodes is not a small scale relative to the listed small-scale sets (e.g., gt3s6u has 9 nodes). Please clarify which scales were solved exhaustively and what '80 nodes' refers to.","section":"Section V-A"},{"comment":"The parametrization of the discrete solution space with theta*_i0 and theta*_i1 is inconsistent with the earlier definition of theta in R^N; please unify the notation.","section":"Section III-A"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the journal's scope and the open-sourcing of code and datasets is commendable. However, the central near-optimality claim currently depends on two unresolved issues: the provenance of the large-scale 'gt' test labels, and the unverified unbiasedness assumption E(Theta_x)=theta*. Both are fixable in principle by adding experiments or by softening the claims. The orthogonality metric in Section V-C must also be corrected before publication. I would support publication after these load-bearing points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a useful empirical paper with a concrete engineering contribution, but the headline theoretical claim is not established. The core evidence that GDSG 'converges to the optimal solution' is Table I, and the paper never explains how the large-scale ground-truth labels (gt7s24u, gt10s31u, gt20s61u, etc.) were generated. Exhaustive search is only claimed for small scales; for 20 servers and 61 users that approach is infeasible. If those labels are just MCMF heuristic outputs with more restarts, the Exceed ratios measure imitation of the label generator, not distance to a true optimum. That is the load-bearing soft spot.\n\nWhat is genuinely new: GDSG is the first graph diffusion solver aimed at MSCO with multi-task discrete/continuous generation, and the padding-edge gating idea is a small but real fix for non-fully-connected graphs. The code and datasets are open-sourced, and the empirical comparison against DiGNN and HEU is consistent. The padding-edge ablation is a solid engineering result.\n\nThe convergence theory in Sec. III-B is weaker than the abstract implies. It assumes E(Theta_x)=theta*, which is neither derived from MCMF nor checked on the generated data. MCMF with random resource initialization likely has systematic bias, so the Chebyshev bound just moves the problem. Also, the orthogonality claim in Fig. 4 is internally confused: cosine close to 1 means gradients are aligned, not orthogonal, so reporting that as near-100% orthogonality is a sign the metric needs rethinking.\n\nProportionally, the empirical method is plausible and reproducible, and the paper deserves a serious referee. But the claims need to be scaled back and the label-generation process disclosed. I would send it to review with a request for major revision, not desk reject it. I would not cite the convergence guarantee as established, though the open dataset and padding-edge gating are worth remembering.","headline":"Open-sourced graph diffusion solver for MSCO shows a real engineering gain, but its headline 'converges to optimal' claim rests on undisclosed large-scale test labels and an unverified unbiasedness assumption.","tokens_in":35070,"tokens_out":3163,"would_cite":false,"duration_ms":36567,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a graph diffusion model trained only on suboptimal heuristic samples can generate near-optimal solutions to the multi-server multi-user computation offloading problem with high probability.","keywords":["graph diffusion","computation offloading","multi-access edge computing","suboptimal training data","generative diffusion model","graph neural network","multi-task learning","solution distribution learning"],"falsifier":"On a fixed instance, measure the average of the model's output parameter vectors over many parallel samples; if that average is far from the optimal solution's parameterization (for example, when the training heuristic always favors one server), the Exceed ratio should stay well above 1, contradicting the claim that sampling converges to optimal. The paper's own variance measurement (σ² ≈ 10⁻⁴) is only on outputs, not on the bias E(Θ_x) − θ*, so measuring that bias directly would settle the question.","tokens_in":34044,"feed_emoji":"📡","tokens_out":8332,"duration_ms":80974,"temperature":0.7,"pith_summary":"Many optimization problems in mobile edge computing are NP-hard and have no efficient approximation algorithm, so labeled optimal solutions are scarce. The paper tries to show that this scarcity need not block learning: a graph diffusion model trained only on cheap suboptimal solutions can still converge to the optimal solution with high probability. The key move is to treat optimization as distribution learning—parameterize the solution space, learn the distribution of suboptimal parameterizations, and sample repeatedly. If correct, GDSG would let network operators train near-optimal solvers from data that is easy to generate, and the paper reports that it beats both the heuristic that produced its training data and a same-architecture discriminative GNN.","feed_headline":"Suboptimal data alone trains near-optimal offloading","feed_subtitle":"GDSG learns solution distributions and beats discriminative GNNs, with no optimal-label training set.","key_machinery":"The argument rests on a solution-space parametrization: each feasible solution $y$ is assigned probability $p_\\theta(y|x) \\propto \\exp(\\sum_i y_i \\theta_i)$, and the optimal solution corresponds to a parameter vector $\\theta^*$. The model learns the distribution $p(\\Theta_x)$ of suboptimal parameterizations, then repeatedly samples solutions $y \\sim p_{\\theta'}(y|x)$; a Chebyshev bound plus a finite-sampling hitting argument shows that enough samples make the probability of hitting the optimum near one. The generative engine is a graph neural network run as a two-head diffusion model—one head uses categorical (Bernoulli) transitions for binary offloading decisions, the other uses Gaussian transitions for resource-allocation ratios. Two engineering additions carry the experiments: a padding-edge gating flag that suppresses nonexistent edges in non-fully-connected graphs, and the observation that the two diffusion tasks' gradients are nearly orthogonal, so joint training does not suffer negative interference.","core_discovery":"GDSG is a multi-task graph diffusion model that takes a network graph as input and generates both discrete offloading decisions and continuous resource-allocation ratios. The paper's central claim is that training this model on a dataset of suboptimal solutions—produced cheaply by a randomized minimum-cost-maximum-flow heuristic—is enough for it to learn the distribution of high-quality solutions, so that parallel sampling from the learned distribution converges to the optimal solution with high probability. On ten test scales, the generated solutions' costs sit within about 10% of the ground-truth optimal costs (Exceed ratios mostly below 1.1), which beats the heuristic generator, a same-architecture discriminative GNN, and prior diffusion-based combinatorial solvers. The reported savings reach up to 56.62% of the target cost when trained on an optimal dataset and 41.06% when trained on a suboptimal dataset, compared with discriminative baselines.","pith_inferences":["If the heuristic is systematically biased, the paper's convergence proof does not guarantee optimality, but the diffusion sampler might still concentrate probability mass near good solutions; measuring the gap between the sample-mean parameterization and the optimal one on a biased instance would test this.","The same pipeline—cheap suboptimal samples, a parametrized solution space, and a multi-task diffusion model—could transfer to other graph-structured MEC problems such as routing, scheduling, or spectrum allocation, where ground-truth labels are equally scarce.","The near-total gradient orthogonality between the discrete and continuous heads suggests that diffusion objectives can sidestep standard multi-task interference, which would make joint discrete-continuous optimization easier for other network problems.","Because the heuristic generates an 80-node instance in about 0.6 seconds while GDSG inference is roughly 0.03–0.4 seconds, the practical bottleneck shifts to dataset coverage; randomizing the heuristic's initialization is a cheap way to broaden the distribution the model learns."],"forward_implications":["A model trained purely on suboptimal MCMF-generated data achieves Exceed ratios below 1.1 on most tested scales, so near-optimal decisions can be obtained without ground-truth labels.","GDSG outperforms the heuristic that generated its training data, showing the model generalizes beyond its data generator.","GDSG beats a same-architecture discriminative GNN on both suboptimal and ground-truth training datasets, with substantial cost savings.","The discrete and continuous diffusion tasks share parameters with near-100% gradient orthogonality, so multi-task training avoids negative interference; the paper attributes this to the diffusion loss rather than the GNN architecture.","Padding-edge gating lets one trained model generalize across graph sizes, substantially improving the Exceed ratio over a vanilla GNN backbone."],"supporting_citations":[{"why":"Supplies the denoising diffusion probabilistic model and variational loss that GDSG's continuous head extends.","marker":"[39]"},{"why":"Provides the categorical transition matrices used for the discrete offloading-decision diffusion head.","marker":"[42]"},{"why":"Graph-diffusion solver for combinatorial optimization whose GNN backbone GDSG starts from and whose performance it beats.","marker":"[43]"},{"why":"Combines distribution learning with gradient search; cited as inapplicable to MSCO because the offloading objective is non-differentiable.","marker":"[44]"},{"why":"Introduces the parametrized solution-space / energy view that GDSG's distribution-learning formulation builds on.","marker":"[58]"},{"why":"Provides the Chebyshev inequality used to bound the gap between sampled suboptimal parameterizations and the optimal one.","marker":"[59]"},{"why":"Multi-task learning approach for computation offloading used as a baseline and as the source of the multi-task formulation.","marker":"[38]"},{"why":"DDIM is used to cut the number of denoising inference steps while preserving generation quality.","marker":"[73]"},{"why":"Benchmark study motivating the GNN architecture and the over-smoothing/padding-edge concerns addressed by gating.","marker":"[65]"},{"why":"Multinomial diffusion formulation supporting the discrete-state diffusion machinery used for binary decisions.","marker":"[62]"}],"fun_headline_variants":["Suboptimal data yields near-optimal MEC offloading via graph diffusion","Graph diffusion turns suboptimal solutions into near-optimal offloading","Training on suboptimal data: GDSG beats discriminative GNNs for offloading","GDSG: Learn from suboptimal data, generate near-optimal MEC offloading","Suboptimal training data suffices for near-optimal computation offloading"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The suboptimal solutions' parameterizations must be centered on the optimal parameterization, so that random mistakes cancel out rather than pushing the learned distribution toward a systematically wrong solution.","fun_headline_variants_meta":{"raw":{"variants":["Suboptimal data yields near-optimal MEC offloading via graph diffusion","Graph diffusion turns suboptimal solutions into near-optimal offloading","Training on suboptimal data: GDSG beats discriminative GNNs for offloading","GDSG: Learn from suboptimal data, generate near-optimal MEC offloading","Suboptimal training data suffices for near-optimal computation offloading"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000209,"raw_usage":{"total_tokens":1465,"prompt_tokens":1058,"completion_tokens":407,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":306}},"tokens_in":674,"tokens_out":407,"duration_ms":4057,"temperature":1.0,"reasoning_tokens":306,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:58:52.509668+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a fixed instance, measure the average of the model's output parameter vectors over many parallel samples; if that average is far from the optimal solution's parameterization (for example, when the training heuristic always favors one server), the Exceed ratio should stay well above 1, contradicting the claim that sampling converges to optimal. The paper's own variance measurement (σ² ≈ 10⁻⁴) is only on outputs, not on the bias E(Θ_x) − θ*, so measuring that bias directly would settle the question.","supporting_citations":[{"cited_title":"DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems,","cited_arxiv_id":null,"evidence_quote":"Introduces the parametrized solution-space / energy view that GDSG's distribution-learning formulation builds on."},{"cited_title":"Denoising Diffusion Probabilistic Models,","cited_arxiv_id":null,"evidence_quote":"Supplies the denoising diffusion probabilistic model and variational loss that GDSG's continuous head extends."},{"cited_title":"Structured Denoising Diffusion Models in Discrete State-Spaces,","cited_arxiv_id":null,"evidence_quote":"Provides the categorical transition matrices used for the discrete offloading-decision diffusion head."},{"cited_title":"DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization,","cited_arxiv_id":null,"evidence_quote":"Graph-diffusion solver for combinatorial optimization whose GNN backbone GDSG starts from and whose performance it beats."},{"cited_title":"T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization,","cited_arxiv_id":null,"evidence_quote":"Combines distribution learning with gradient search; cited as inapplicable to MSCO because the offloading objective is non-differentiable."},{"cited_title":"Chebyshev inequality with estimated mean and variance,","cited_arxiv_id":null,"evidence_quote":"Provides the Chebyshev inequality used to bound the gap between sampled suboptimal parameterizations and the optimal one."},{"cited_title":"Computation offloading in multi-access edge computing: A multi-task learning approach,","cited_arxiv_id":null,"evidence_quote":"Multi-task learning approach for computation offloading used as a baseline and as the source of the multi-task formulation."},{"cited_title":"Denoising Diffusion Implicit Models,","cited_arxiv_id":null,"evidence_quote":"DDIM is used to cut the number of denoising inference steps while preserving generation quality."},{"cited_title":"Benchmarking graph neural networks,","cited_arxiv_id":null,"evidence_quote":"Benchmark study motivating the GNN architecture and the over-smoothing/padding-edge concerns addressed by gating."},{"cited_title":"Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions,","cited_arxiv_id":null,"evidence_quote":"Multinomial diffusion formulation supporting the discrete-state diffusion machinery used for binary decisions."}],"review_version":1}