{"id":"bd9070f8-6946-4306-9dea-12d0931e4618","arxiv_id":"2607.18480","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A state-augmented GNN that imitates dual subgradient descent produces near-optimal, constraint-satisfying long-horizon wireless link schedules.","lead":"A graph neural network scheduler for wireless device-to-device links alternates which links transmit over time, so that every link meets a minimum long-term rate while total throughput stays high. The network takes each link's constraint penalty as an input and is shown in simulation to match the throughput of optimal per-slot scheduling while cutting runtime by orders of magnitude.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's guarantees are proven for an exact Lagrangian-maximizing oracle, but Algorithm 2 executes a thresholded GNN, and no bound connects the GNN to the oracle; the central claim that SAGNN inherits Prop. 3 is therefore unestablished.","rationale":"The reader's verdict is conditional largely because of the same oracle-GNN gap; I agree with that primary concern. However, the secondary concern about Eq. 31 is less load-bearing than the reader implies: Prop. 2 can be proven directly without Eq. 31 by using Prop. 1 to equate all time-slot maximizers, so the analysis need not collapse if that inequality is fixed. The unresolved issue is the absence of any quantitative link between training loss and per-slot maximality, which is required for Prop. 3 to apply. The experiments are genuine but cannot substitute for the missing bound; a concrete MWIS-based audit of ε_t would settle whether the gap matters in practice. Since the reader already conditions acceptance on addressing this gap, no change to the verdict is needed.","tokens_in":20913,"tokens_out":5638,"duration_ms":53033,"concrete_test":"On 3–5 test graphs (K≈500), for T=200 run Algorithm 2 and at each t compute the true instantaneous maximizer s*(t) with the same MWIS solver used as baseline, weighted by 1+λ(t). Record ε_t = M(s*(t),λ(t))−M(s_SAGNN(t),λ(t)), the achieved average rate, and the constraint-violation vector. Then check whether (1/T)Σ_t ε_t is small relative to η∥M−Δ∥²/2 and whether adding −(1/T)Σ_t ε_t to Eq. 15 still leaves the observed sum rate within the promised bound. If ε_t is large or the corrected bound fails, the oracle theory does not account for SAGNN's reported performance.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Prop. 3 (Eqs. 15–16) is the backbone of the paper's claim that sequences of dual-subgradient schedules are near-optimal and asymptotically feasible. Its proof begins from Eq. 34: at every slot t, s‡(t) must exactly maximize M(s,λ(t)) as defined in Eq. 11. Algorithm 2 replaces this oracle by s(t)=Φ(A,λ(t);H⋆) (Eq. 20), trained with stochastic gradient ascent on the expected Lagrangian (Eq. 19). At execution, further binarization via a 0.5 threshold is applied (Sec. V-A), and a resilience term with α=0.05 changes the actual dual update to Eq. 22, not Eq. 13. None of these steps is accompanied by a bound on the per-step Lagrangian suboptimality ε_t = max_s M(s,λ(t)) − M(Φ(A,λ(t);H⋆),λ(t)). Equation 34 can only be replaced by a version with an additive −ε_t term; unless Σ_t ε_t is O(1) (or at most controlled by η), the O(η) gap in Eq. 15 and the O(1/T) feasibility slack in Eq. 16 do not follow for SAGNN. Training to low expected loss over p_λ does not imply low ε_t for the particular λ-trajectory generated during execution, because p_λ is partly empirical and changes with epochs. Thus the paper's central claim—that SAGNN 'imitates dual gradient descent provided trained to small loss'—has no theorem. Independently, App. A's proof of Prop. 2 contains Eq. 31, which asserts componentwise r(s‡)≥(1/T)Σr(s†)≥Δ by 'assuming constraints are not violated'; this contradicts Sec. III-A's infeasibility discussion. The proposition itself is salvageable via a direct subgradient argument using Prop. 1, so the main load-bearing gap is the unquantified oracle approximation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses long-horizon wireless link scheduling in device-to-device networks under per-link average-rate constraints. The authors formulate the problem as a constrained integer program over schedules (Eq. 3), study its Lagrangian dual, and show that a sequence of instantaneous Lagrangian maximizers generated by dual subgradient updates is asymptotically near-optimal and feasible (Proposition 3). They then train a Graph Neural Network, SAGNN, whose input is the adjacency matrix augmented by the current dual variable, to maximize the instantaneous Lagrangian (Eqs. 18-19), and execute it with dual updates (Algorithm 2). Numerical experiments on random geometric graphs report low constraint violations, competitive sum rates, faster runtime than FPLinQ and MWIS baselines, and generalization across requirements.","tokens_in":21511,"tokens_out":9914,"duration_ms":94826,"significance":"If the theoretical guarantee for SAGNN were established, the paper would offer a scalable learned scheduler for an NP-hard problem with a provable long-horizon optimality/feasibility gap, which is an attractive contribution. The paper's strengths include a clear problem formulation, a conceptually useful dual-subgradient interpretation, public code, and reasonably extensive experiments plus an ablation of the training distribution for the dual variable. However, the central theoretical bridge — from the exact-oracle analysis of Proposition 3 to the actual thresholded, resilient, finite-capacity GNN executed in Algorithm 2 — is missing. The proof of Proposition 2 also contains a false componentwise inequality. These issues are load-bearing for the paper's main claim that SAGNN 'imitates dual gradient descent provided that the learning parameterization is trained to a small loss.'","major_comments":[{"comment":"Proposition 3's proof begins at Eq. (34), which is valid only because s‡(t) exactly maximizes the instantaneous Lagrangian M(·, λ(t)) in Eq. (11). Algorithm 2 replaces this oracle with the thresholded GNN output s(t)=Φ(A,λ(t);H⋆) from Eq. (20), trained by stochastic gradient ascent on the expected Lagrangian (Eq. 19). No bound is given on the per-step suboptimality ε_t = max_s M(s,λ(t)) − M(Φ(A,λ(t);H⋆),λ(t)). Training to low expected loss over pλ does not control ε_t along the particular execution trajectory, especially since pλ is partly empirical and changes with training (Section V-A). The statement in Section I that state-augmented learning 'works because it imitates dual gradient descent provided that the learning parameterization is trained to a small loss' is therefore not a theorem. The authors should either provide a cumulative/per-step suboptimality condition that yields a con","section":"Section IV, Eqs. (18)-(21), and Algorithm 2"},{"comment":"The proof asserts the componentwise inequality s‡(u)⊙[1−As‡(u)]_+ ≥ (1/T)Σ_t s†(t)⊙[1−As†(t)]_+ ≥ Δ, justified by 'assuming constraints are not violated.' The second inequality claims that average Lagrangian-maximizing schedules are feasible, which directly contradicts Section III-A, where such schedules are shown to be infeasible in general; the first inequality is also false for vector rates. The proposition itself can be proved by the standard subgradient argument (a constant sequence of instantaneous maximizers maximizes the average Lagrangian, so g(λ(u)) is a subgradient of d at λ(u)), but the proof as written is invalid. This lemma is used in Appendix B for boundedness of the dual iterates, so it should be replaced with a correct proof.","section":"Appendix A, proof of Proposition 2, Eq. (31)"},{"comment":"The boundedness of λ(T), which underpins the asymptotic feasibility part of Proposition 3, is established through Proposition 4. That proof assumes the strict feasibility condition d(λ(u))−d(λ*) ≥ ε||λ(u)−λ*|| and gives no justification. The dual function of this integer scheduling problem is piecewise linear and will not generally satisfy such a condition. Without a valid boundedness argument, Eq. (16) is not justified even for the exact-oracle algorithm. Please either prove boundedness under a verifiable condition or use a direct argument that does not rely on strong-convexity-type assumptions.","section":"Appendix B, Proposition 4, Eq. (49)"},{"comment":"The experiments deviate from the analyzed algorithm in several unmodeled ways: the actual dual update is Eq. (22) with the resilience term λα and α=0.05, not Eq. (13) or Eq. (21); the GNN output is binarized with a 0.5 threshold during evaluation; and after the first epoch the training distribution pλ is empirical and policy-dependent rather than the fixed distribution in Eq. (19). None of these modifications is covered by Proposition 3. The authors should either analyze the resilient/binarized variant or clearly present it as an additional heuristic whose guarantees are not claimed by the theory.","section":"Section V-A and Eq. (22)"}],"minor_comments":[{"comment":"Typographical errors: 'Tolearnsolutions' should be 'To learn solutions' and 'and and online' should be 'and an online'.","section":"Section II, first paragraph"},{"comment":"M is described in the statement as 'the size of the maximum independent set' but Eq. (39) treats M as a binary vector in {0,1}^K. Please define unambiguously, e.g., let M be a maximum independent set incidence vector, and write ||M−Δ||² explicitly.","section":"Proposition 3 and Eq. (39)"},{"comment":"The summation has a typesetting error: 'vX t=v' should be 'Σ_{t=v}^{v}' or simply the instantaneous Lagrangian M(s(v),λ).","section":"Appendix A, Eq. (26)"},{"comment":"References [26] and [29] are the same paper (NaderiAlizadeh, Eisen, and Ribeiro, IEEE Transactions on Signal Processing, vol. 70, 2022). Duplicate entries should be removed or merged.","section":"References"},{"comment":"The notation 'M(H(n),λ)' does not match Eq. (18), where the loss is M(Φ(A,λ;H),λ). Please align the notation.","section":"Algorithm 1, Step 6"},{"comment":"The text says 'For more details on the resilient formulation, see Appendix D,' but Appendix D describes the network architecture and implementation, not the resilient formulation. Please add the missing derivation or point to the correct appendix.","section":"Section V-A"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the scope of the journal and I found no issues with citation ethics beyond the duplicate reference noted above. The main technical problem is the missing oracle-to-GNN approximation analysis; if the authors cannot supply such a bound, they should substantially weaken the theoretical claims and present SAGNN as an empirical approximation. I believe the revisions above are feasible within a major-revision cycle."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a solid engineering paper with a real theoretical gap. The long-horizon scheduling problem is well formulated, and Prop. 3 is a genuinely nice observation: if you can compute exact instantaneous Lagrangian maximizers each slot, then dual subgradient updates give near-optimal average rates and asymptotic feasibility, without combinatorial search over the time horizon. That is a useful result and, as far as I can tell, not in the earlier state-augmentation papers. The SAGNN implementation is a reasonable way to approximate those maximizers, and the experiments are careful: multiple requirement levels, benchmarks against p-persistent, FPLinQ, and MWIS, generalization checks, and the code is available. I believe the empirical claims.\n\nWhere it gets soft: the paper says SAGNN inherits Prop. 3 when trained to a small loss, but no theorem connects the GNN to the oracle. Prop. 3 starts from Eq. (34), which requires exact per-slot maximizers. Algorithm 2 uses a thresholded GNN output, and the resilience term in Eq. (22) changes the dual update itself. There is no bound on epsilon_t = max_s M(s, lambda(t)) - M(Phi(A, lambda(t); H*), lambda(t)). Training to low expected loss over a distribution p_lambda that is partly empirical does not control epsilon_t along the particular lambda trajectory seen in execution. So the inheritance claim is unproven. The right fix is to present Prop. 3 as an oracle benchmark and SAGNN as a learned heuristic motivated by it, or to give a real approximation bound.\n\nSeparately, the proof of Prop. 2 is not right as written: Eq. (31) asserts a componentwise inequality and says \"assuming constraints are not violated,\" which is exactly what Section III-A says is not true for Lagrangian maximizers. I think the proposition can be salvaged with a direct subgradient argument using Prop. 1, but the appendix needs a rewrite. Prop. 4 also assumes a strong-convexity-type condition without establishing it, so the boundedness argument is incomplete.\n\nOverall: this is for people building learning-based schedulers for dense D2D networks and people interested in dual methods for constrained combinatorial scheduling. The reviewer should not reject on grounds of novelty or empirics; they should require the theory to be squared with the actual algorithm. I would send it to peer review with a request for substantial but bounded revisions.","headline":"Useful algorithm and careful experiments, but the main theoretical guarantee is proven for an exact oracle, not for the deployed GNN, and the proof of Prop. 2 has a spot that is wrong as written.","tokens_in":21914,"tokens_out":3767,"would_cite":true,"duration_ms":43188,"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 long-horizon link scheduling problem with per-link rate constraints can be solved by running dual subgradient updates that sample a sequence of instantaneous Lagrangian maximizers, and a state-augmented graph neural network can imitate th","keywords":["wireless link scheduling","long-horizon optimization","Lagrangian duality","dual subgradient descent","state augmentation","graph neural networks","primary interference model","per-link rate constraints"],"falsifier":"On a small conflict graph where the optimum is computable by exhaustive search, run the dual-subgradient sequence with exact Lagrangian maximizers for increasing horizons T; if the average-rate gap and constraint violation do not decay at the predicted O(1/T) rate, Proposition 3's bound is wrong. Additionally, inspect the inequality in the proof of Proposition 2 by searching for a graph and multiplier sequence where the average Lagrangian-maximizer rate falls below Δ, which would invalidate the subgradient claim.","tokens_in":20848,"feed_emoji":"📡","tokens_out":5955,"duration_ms":112589,"temperature":0.7,"pith_summary":"The paper targets link scheduling in large wireless networks where each link must transmit a minimum fraction of time without colliding with interfering links. The original optimization is combinatorial in the product of the number of links and the time horizon, so solving it directly is intractable. The paper establishes that a sequence of schedules obtained by repeatedly maximizing the instantaneous Lagrangian, with Lagrange multipliers updated by dual subgradient steps, is asymptotically near-optimal and feasible as the horizon grows. That makes the long-horizon problem easier than expected: each slot only requires solving a combinatorial problem in the number of links, not in horizon length. The paper then trains a graph neural network to approximate these maximizers, feeding the current dual variable as input, and argues the learned policy inherits the dual-descent guarantees when trained to small loss.","feed_headline":"Dual updates yield near-optimal long-horizon schedules","feed_subtitle":"Feeding dual variables into a graph network meets per-link rate targets at low runtime","key_machinery":"The load-bearing object is the instantaneous Lagrangian M(s,λ)=(1+λ)^T[s⊙(1−As)_+]−λ^TΔ, defined on a single schedule s given the conflict graph A and multiplier λ. Its maximizer is a K-variable combinatorial problem, and the dual subgradient g(λ)=s⊙(1−As)_+−Δ with update λ←[λ−ηg(λ)]_+ turns that fixed maximizer into a time-varying sequence. The paper names state augmentation the technique of feeding the current dual variable λ as an input to the graph neural network, so the policy output changes over time and attends to links whose constraints are most violated.","core_discovery":"On the paper's own terms, the central discovery is Proposition 3: if at every slot you pick a schedule maximizing the instantaneous Lagrangian M(s,λ)=(1+λ)^T[s⊙(1−As)_+]−λ^TΔ and update multipliers by λ←[λ−η(s⊙(1−As)_+−Δ)]_+, then the time-averaged rates of the resulting sequence satisfy 1^T r̄ ≥ P*_T − (η/2)‖M−Δ‖² − |λ(1)|²/(2ηT) and r̄ ≥ Δ − λ(T)/(ηT). The first bound says the average sum rate approaches the optimal long-term rate; the second says constraint violations shrink like 1/T. A single Lagrangian maximizer is time-invariant and infeasible for problems with positive per-link requirements, which is why the paper emphasizes the sequence rather than the schedule. The state-augmented G","pith_inferences":["The O(1/T) term in the bounds suggests that for a fixed desired gap, the dual step size η can be chosen small and the horizon long; a natural next experiment is to test whether η scaling as 1/T yields the predicted trade-off.","The same state-augmented trick, making a time-varying input out of a Lagrange multiplier, transfers to other constrained combinatorial scheduling problems such as edge coloring or frequency assignment, where a time-varying policy is required but a stationary network function is not.","If the gap between the graph network's output and the true Lagrangian maximizer were bounded by measuring per-slot Lagrangian regret, Proposition 3 would extend formally to the learned policy; that measurement is absent and is the most direct next step.","The masking post-processing shows collision-free schedules can be recovered cheaply, but its effect on the dual-subgradient guarantees is not analyzed; the paper's theory covers the un-masked policy only."],"forward_implications":["Average rates from the dual-subgradient schedule sequence approach the optimal long-term sum rate within a gap bounded by O(η) plus O(1/ηT).","Per-link rate requirements are met up to a violation that shrinks as λ(T)/(ηT), so feasibility improves with horizon length.","The per-slot scheduling decision costs combinatorial effort in the number of links, not in links times slots, making long horizons computationally affordable.","A graph neural network trained to maximize the instantaneous Lagrangian, with dual variables as inputs, can be executed with millisecond-scale inference and satisfies constraints for the large majority of links.","The same trained model can be evaluated under different per-link minimum rate requirements than it was trained on, with only modest degradation."],"fun_headline_variants":["State-augmented GNN hits long-horizon rate targets","Dual variables in GNN yield near-optimal schedules","Long-horizon link scheduling via dual-augmented GNN","GNN with dual inputs balances rates and constraints","Augmenting GNN with duals improves scheduling"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The central theorem assumes every slot's schedule exactly maximizes the instantaneous Lagrangian; the deployed graph network only approximates that maximizer and no bound on the approximation error is given, and the proof of Proposition 2 also assumes the averaged rates already meet the rate requirement, which contradicts the paper's own observation that Lagrangian maximizers are infeasible.","fun_headline_variants_meta":{"raw":{"variants":["State-augmented GNN hits long-horizon rate targets","Dual variables in GNN yield near-optimal schedules","Long-horizon link scheduling via dual-augmented GNN","GNN with dual inputs balances rates and constraints","Augmenting GNN with duals improves scheduling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000198,"raw_usage":{"total_tokens":1202,"prompt_tokens":737,"completion_tokens":465,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":481,"completion_tokens_details":{"reasoning_tokens":383}},"tokens_in":481,"tokens_out":465,"duration_ms":7727,"temperature":1.0,"reasoning_tokens":383,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T15:17:32.066734+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small conflict graph where the optimum is computable by exhaustive search, run the dual-subgradient sequence with exact Lagrangian maximizers for increasing horizons T; if the average-rate gap and constraint violation do not decay at the predicted O(1/T) rate, Proposition 3's bound is wrong. Additionally, inspect the inequality in the proof of Proposition 2 by searching for a graph and multiplier sequence where the average Lagrangian-maximizer rate falls below Δ, which would invalidate the subgradient claim.","supporting_citations":[],"review_version":1}