{"id":"1e6f8dfd-3a34-444d-a40d-f09bbfc6f057","arxiv_id":"2505.07598","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A state-augmented GNN scheduler, which feeds Lagrangian dual variables to the policy, learns to meet per-link minimum transmission quotas while maximizing average throughput in grid network simulations.","lead":"A graph neural network that tracks how underserved each wireless link is (via learned penalty signals) produces fair, conflict-free transmission schedules in simulated ad-hoc networks. The paper reports gains over simple random and heuristic baselines, but not over state-of-the-art learned schedulers.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claim that SAGNN satisfies per-link minimum transmission requirements is not established: execution dual variables can leave the U[0,2] training range, and the paper's own Fig. 5 shows residual violations.","rationale":"Read in good faith, the paper proposes a sensible state-augmented GNN and provides code and experiments. The central claim, however, is the per-link feasibility/fairness result. That claim has two unsecured supports: (i) the policy is only trained on lambda in [0,2], but the enforcement mechanism can take lambda outside this box, and no analysis or experiment checks this; (ii) the paper's own Fig. 5 contradicts the unqualified 'minimum transmission satisfied for each link' statement. The reader's weakest assumption identified (i); I agree with that and add that (ii) is not a mere modeling caveat but an internal inconsistency that must be resolved by a feasibility analysis. Because the concern is concrete and addressable with the provided code, the reader's CONDITIONAL verdict is appropriate; I would not reject the paper outright. The proposed test -- logging lambda_t and separating feasible from infeasible links -- settles whether the claim holds in the intended sense.","tokens_in":9281,"tokens_out":10725,"duration_ms":116147,"concrete_test":"Using the released code, instrument the execution loop to record lambda_i(t) for all links over T=200 for Delta in {0.1,0.125,0.15}; report the maximum and the fraction of (link,t) pairs exceeding 2, and compare against the U[0,2] training box. Then solve a linear program for each test graph to bound each link's maximum feasible long-term success fraction under the independent-set constraints (fractional independent-set polytope: maximize per-link average schedule fraction with sum_{j in N(i)} f_j <= 1, f_i >= 0), and label links whose bound is below Delta as infeasible. Recompute the Fig. 5 violation distribution separately for feasible and infeasible links.","verdict_should_be":"UNCHANGED","load_bearing_attack":"To enforce the per-link minimums, SAGNN feeds lambda_t as inputs, but training samples lambda from U[0,2]^K while execution updates lambda_t via Eq. (18). For links whose constraint residual stays negative -- for example, links with many conflicts whose feasible long-term success fraction is below Delta -- lambda_i(t) can grow well above 2. With conflict graphs of average degree 6, some links can have a maximum schedule fraction around 1/7, which is below the tested Delta = 0.15. The paper does not report lambda_t trajectories, so it is unknown whether the policy ever receives inputs outside its training distribution. This matters because the only theoretical support, Eqs. (12)-(13) cited from [13,18], applies to the exact primal-dual algorithm, not to the learned GNN policy; the paper motivates SAGNN by the failure of those guarantees in finite time but gives no finite-time guarantee for the learned policy. The consequence is visible inside the paper: Section IV.B claims 'the minimum transmission satisfied for each link,' while Section IV.C reports that a small percentage of links fall short, attributing them to 'inherently infeasible' cases without any feasibility check. If the infeasibility explanation is correct, those links are exactly the ones whose dual variables grow without bound, leaving the trained lambda range. Thus the central fairness claim is not established by the presented evidence.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers long-term average link scheduling in wireless ad hoc networks under per-link minimum transmission requirements. It formulates a constrained binary optimization problem, introduces a Lagrangian dual formulation, and proposes a State-Augmented Graph Neural Network (SAGNN) that takes the dual variables as time-varying inputs to the scheduling policy. The policy is trained by maximizing the expected augmented Lagrangian over randomly sampled dual variables, and executed with a stochastic dual subgradient update. Experiments on grid-derived conflict graphs compare SAGNN with p-persistent and random-MIS baselines, reporting near-MIS-bound average successful transmissions and small residual constraint violations.","tokens_in":9630,"tokens_out":6802,"duration_ms":64259,"significance":"The state-augmentation idea is sensible and practically motivated: feeding constraint-violation indicators as inputs is a plausible way to make a learned scheduler adaptive to fairness constraints, and the GNN parameterization provides permutation equivariance and transferability. The paper provides a code link, uses test graphs not seen in training, and gives a clear problem formulation. If the empirical claims held, SAGNN would be a useful baseline for GNN-based constrained scheduling. However, the current evidence does not establish the central feasibility claim, the theoretical support is imported rather than proved for the learned policy, and the comparison set is too narrow. The contribution at present is a promising proposal rather than a fully validated method.","major_comments":[{"comment":"The claim in Section IV.B that 'the minimum transmission satisfied for each link' is not established by the reported evidence. Section IV.C and Fig. 5 show that a small percentage of links violate the constraint, and the paper attributes these residual violations to 'inherently infeasible' cases without performing any feasibility check. This matters because infeasible links are exactly those whose constraint residual (s_i(t) - Delta_i) remains negative, so the dual update (18) will drive lambda_i(t) upward and out of the uniform [0,2] training range. For a conflict graph with average degree 6, there can exist links whose maximum achievable schedule fraction is below the tested Delta = 0.15, so some of the reported violations are likely to correspond to out-of-distribution lambda inputs. The paper should report the empirical distribution of lambda_t during execution, provide a feasibility analysis (e.g., an upper bound on each link's achievable long-term transmission fraction), and either remove the unqualified feasibility claim or explicitly qualify it as holding only for feasible links.","section":"Section IV.B and IV.C, Fig. 5, Eq. (18)"},{"comment":"The only theoretical support for the algorithm, Eqs. (12)-(13), is imported from references [13] and [18] and applies to the exact primal-dual algorithm in the limit T -> infinity, not to the learned GNN policy with a fixed architecture and finite training. The paper explicitly motivates SAGNN by arguing that these infinite-time guarantees fail in finite time, but it provides no finite-time guarantee for the learned policy, no bound on the dual iterates, and no analysis of how the policy extrapolates beyond the lambda range used at training time. Since execution (Algorithm 2) feeds lambda_t generated by Eq. (18) into a policy trained on lambda ~ U[0,2]^K, the central claims of near-optimality and feasibility rest on an unverified generalization assumption. At minimum, the authors should empirically evaluate the trained policy on lambda inputs drawn from a much wider range (e.g., U[0,10]^K) and demonstrate that performance and constraint satisfaction do not degrade outside the training distribution.","section":"Section III, Eqs. (12)-(13) and Section IV.A"},{"comment":"The baseline set (p-persistent and random MIS, with and without collision avoidance) is too weak to support the contribution. There is no comparison to the GNN-based scheduler of reference [10], which is the most directly relevant learned baseline, nor to the original state-augmented learning algorithm of reference [13] on which the method builds. The claim that SAGNN 'outperforms heuristic baselines' is true but does not demonstrate an advantage over existing learning-based approaches. Please add these comparisons or justify why they are inapplicable. In addition, the MIS-based upper bound of about 25% of links is computed without the per-link minimum-transmission constraints and is therefore not a valid upper bound for the constrained problem; the comparison against this loose bound should be reconsidered or replaced by a constrained upper bound.","section":"Section IV, experimental comparison"},{"comment":"The statistical evidence is thin. Figures 2 and 3 are based on only three independent runs, and Figure 4 reports averages over 100 graphs without error bars, confidence intervals, or significance tests. The paper also does not report the variance of the constraint violation across links or runs, nor the number of links whose dual variables leave the training range during execution. To support the central feasibility and performance claims, please report standard errors or per-run curves, the number of seeds, and a quantitative statement of how many links remain infeasible and how their violation levels compare with the infeasibility threshold.","section":"Section IV.A and Figures 2-4"}],"minor_comments":[{"comment":"The expression lambda^T (Phi^T ⊙ ([1 - A Phi]_+ - Delta)) mixes row and column vectors inconsistently; the element-wise product should be performed between same-size column vectors, and the notation should be cleaned up throughout the Lagrangian definitions.","section":"Eq. (16) and Eq. (6)"},{"comment":"The notation '∇λ Lλ(H*)' is ambiguous because Lλ depends on λ both through the dual term and through the policy input; please specify that the update uses the partial derivative with respect to λ treating the scheduled decisions as fixed, as written explicitly in Eq. (18).","section":"Algorithm 2, line 5"},{"comment":"The text says the algorithm is evaluated on 50 unseen graphs in Section IV, but Fig. 4 states 100 graphs; please reconcile these numbers and specify how the test set is split.","section":"Section IV.A and Fig. 4"},{"comment":"References [10] and [17] are the same paper (Zhao et al.), and references [13] and [19] are also duplicates (NaderiAlizadeh et al.); please consolidate them into single entries.","section":"References"},{"comment":"The statement that 'the minimum transmission requirement is not considered during training' is confusing; clarify that Delta is a constant in the maximization over H and therefore does not affect the gradient, while the dual variable lambda encodes the constraint information.","section":"Section IV.A"}],"recommendation":"major_revision","confidential_remarks":"The paper's theoretical framing relies almost exclusively on the authors' own prior work ([13]-[15], [18]-[19]) and the convergence results are cited rather than proved for the proposed learned policy. This is not grounds for rejection, but the revised submission should make the dependency explicit and should engage with independent learning-based scheduling work. The core state-augmentation idea is reasonable, but the empirical validation gaps described in the major comments—especially the out-of-distribution lambda issue and the lack of a feasible-link analysis—must be closed before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a competent incremental application of the state-augmented GNN idea to link scheduling with per-link minimum transmission constraints, and it's worth a look, but the headline claim—that constraints are satisfied—is not backed by the evidence presented.\n\nWhat's genuinely new: the specific combination. Prior state-augmentation work from the same group covers resource management and routing; prior GNN link scheduling work doesn't include long-term minimum-transmission constraints. This paper puts those together. It's honest about inheriting the state-augmentation mechanism, provides code, and evaluates on held-out graphs rather than just training graphs. That's real work and worth credit.\n\nWhere it falls short: the baselines are weak. p-persistent and random MIS are not serious competitors; there's no comparison against the GNN scheduler of [10] or the original state-augmented method [13], which are the natural benchmarks. Only three runs for the main figures, and the resilience factor is tuned per Delta value, adding a free parameter.\n\nThe deeper problem is the dual-variable distribution. Training samples lambda from U[0,2]^K, but at execution lambda_t evolves via Eq. (18), and for hard or infeasible links it will climb above 2. With average degree 6, some links max out below the tested Delta=0.15, so these duals are going to leave the training range. The paper doesn't report lambda trajectories, so we don't know how often that happens. The convergence guarantees quoted from [13,18] apply to the exact primal-dual algorithm, not the learned GNN policy. And the paper contradicts itself a bit: Section IV.B says 'the minimum transmission satisfied for each link,' while Section IV.C acknowledges residual violations, blaming infeasibility without checking feasibility. If those links are infeasible, they're exactly the ones whose duals blow up.\n\nThese are addressable. Add stronger baselines, report lambda trajectories, do a proper feasibility check, and run more than three seeds. If the fairness claim survives that, you have a useful paper for the scheduling community. If not, it's an interesting negative result.\n\nBottom line: worth a serious referee, but I'd expect heavy revision. This is for people working on learning-based resource management, not a general audience. I wouldn't cite it as established fact yet, but I'd read the revised version.","headline":"A competent incremental application of state-augmented GNNs to fair link scheduling, but the constraint-satisfaction claim is not established by the current evidence.","tokens_in":10098,"tokens_out":3181,"would_cite":false,"duration_ms":28993,"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":"A graph neural network that receives Lagrangian dual variables as time-varying inputs can schedule wireless links to meet per-link minimum transmission requirements while staying close to the maximum-independent-set performance bound.","keywords":["link scheduling","graph neural networks","state augmentation","Lagrangian duality","constrained optimization","wireless ad hoc networks","fairness","maximum independent set"],"falsifier":"Run the execution phase on a conflict graph where one link's minimum requirement $\\Delta$ exceeds what any conflict-free schedule can give it, and record that link's dual variable; if the dual grows far beyond the training interval $[0,2]$ and scheduling decisions for neighboring links degrade, the unverified extrapolation assumption is the failure point.","tokens_in":9091,"feed_emoji":"📡","tokens_out":7316,"duration_ms":64372,"temperature":0.7,"pith_summary":"The paper tries to establish that a learned link-scheduling policy can maximize long-run successful transmissions in a wireless ad hoc network while guaranteeing each link at least a preset minimum average transmission rate. It does this by making the scheduling policy a graph neural network whose input includes a running penalty signal, the Lagrangian dual variable, so the policy can react to which links are falling behind. If true, this would give a practical, scalable scheduler that approaches the theoretical maximum-independent-set bound while enforcing fairness, something greedy or probabilistic heuristics do not achieve. The evidence is numerical: on unseen conflict graphs with roughly 500 links, the learned policy stays close to the MIS upper bound and keeps most per-link violations under 10% of the requirement.","feed_headline":"GNN scheduler meets per-link fairness near the theoretical limit","feed_subtitle":"A Lagrangian-penalty input lets a graph neural network adapt its schedule to link constraints and beat heuristic baselines.","key_machinery":"The central object is the state-augmented GNN policy $\\Phi(A,H;\\lambda)$: a graph neural network whose input graph signal is the current Lagrangian dual vector $\\lambda_t$, so the same weights produce different schedules depending on which links are short of their minimum requirement. The GNN is built from graph convolutional filters $y_l = \\sum_{k=0}^{K-1} h_{lk} A^k x_{l-1}$ followed by pointwise nonlinearities and a final sigmoid thresholded at 0.5, with the conflict graph adjacency matrix $A$ as the graph shift operator. The execution-time dual update $\\lambda_{t+1} = [\\lambda_t - \\eta_\\lambda(\\Phi(A,H;\\lambda_t)^\\top \\odot ([1_K - A\\Phi(A,H;\\lambda_t)]_+ - \\Delta))]_+$ supplies the dynamic input, so scheduling decisions react to which constraints are being violated. Training maximizes the expected augmented Lagrangian over dual vectors sampled from $\\mathcal{U}[0,2]^K$.","core_discovery":"On the paper's own terms, the central discovery is that state augmentation with Lagrangian dual variables turns a static graph-neural-network scheduler into a time-adaptive policy for a constrained time-averaged problem. The scheduling policy $\\Phi(A,H;\\lambda)$ takes the conflict graph adjacency matrix $A$ and the current dual vector $\\lambda_t$ as inputs and outputs a binary schedule; $\\lambda_t$ evolves by projected gradient descent on the Lagrangian, increasing when a link falls below its minimum transmission requirement $\\Delta$ and decreasing when the requirement is met. The training objective is the expectation over randomly sampled dual vectors of the augmented Lagrangian, so the network learns a family of schedules indexed by constraint-violation state rather than one fixed schedule. The numerical claim is that this policy keeps the average number of successful transmissions close to the maximum-independent-set upper bound, about 25% of links active, while satisfying the per-link minimum transmission constraints for the feasible majority, with residual violations concentrated below 10% of $\\Delta$ and attributed to infeasible links.","pith_inferences":["One implication the paper leaves implicit is that the dual value itself could serve as an infeasibility alarm: a link whose dual keeps growing under the online update is likely one whose minimum requirement no conflict-free schedule can meet.","Because training samples dual vectors only from $[0,2]^K$, a natural testable extension is to clip the online dual update or widen the training range and see whether performance on hard links improves.","The same dual-augmentation idea should transfer to weighted or SINR-based interference models, since the binary conflict assumption $1_K - As(t)$ is a simplification of the interference structure.","The paper evaluates graphs of roughly 500 links; GNN transferability suggests the policy may extend to larger networks, but that size extrapolation is untested here."],"forward_implications":["A single trained SAGNN can schedule unseen conflict graphs from the same distribution without computing maximum independent sets online.","Per-link fairness constraints can be enforced with a cheap online dual update, so the method scales to hundreds of links at each time step.","In the tested regime the gap to the MIS upper bound is small enough that fairness does not force a large loss in total successful transmissions.","Residual constraint violations concentrate below 10% of the requirement, suggesting the method degrades gracefully even when a few links are infeasible."],"supporting_citations":[{"why":"supplies the state-augmentation technique and the primal-dual viewpoint that the SAGNN policy builds on.","marker":"[13]"},{"why":"provides the asymptotic almost-sure feasibility and near-optimality guarantees quoted for the exact primal-dual scheduler.","marker":"[18]"},{"why":"introduces GNN-based link scheduling via maximum independent set, the performance upper bound this paper compares against.","marker":"[10]"},{"why":"defines the graph convolutional filter architecture used to parameterize the scheduling policy.","marker":"[20]"},{"why":"supplies the graph shift operator and graph-signal formalism underlying the GNN input.","marker":"[22]"},{"why":"the topology-adaptive graph convolution used in the experimental architecture.","marker":"[30]"},{"why":"resilient constrained learning used in the experiments to limit the effect of infeasible links.","marker":"[33]"}],"fun_headline_variants":["State-augmented GNN achieves adaptive fairness","State-augmented GNN for adaptive fair scheduling","Lagrangian state augments GNN for fair link schedules","Adaptive GNN scheduling via dual-variable state augmentation","State-augmented GNN approaches optimal fair scheduling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the neural network, trained only on penalty signals sampled from the range zero to two, still schedules well when those signals are updated online and drift outside that range; the paper gives no experiment or proof for that extrapolation.","fun_headline_variants_meta":{"raw":{"variants":["State-augmented GNN achieves adaptive fairness","State-augmented GNN for adaptive fair scheduling","Lagrangian state augments GNN for fair link schedules","Adaptive GNN scheduling via dual-variable state augmentation","State-augmented GNN approaches optimal fair scheduling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001303,"raw_usage":{"total_tokens":5281,"prompt_tokens":876,"completion_tokens":4405,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":492,"completion_tokens_details":{"reasoning_tokens":4328}},"tokens_in":492,"tokens_out":4405,"duration_ms":32225,"temperature":1.0,"reasoning_tokens":4328,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:12:26.399296+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the execution phase on a conflict graph where one link's minimum requirement $\\Delta$ exceeds what any conflict-free schedule can give it, and record that link's dual variable; if the dual grows far beyond the training interval $[0,2]$ and scheduling decisions for neighboring links degrade, the unverified extrapolation assumption is the failure point.","supporting_citations":[{"cited_title":"Ergodic stochastic optimization algorithms for wireless communication and networking,","cited_arxiv_id":null,"evidence_quote":"provides the asymptotic almost-sure feasibility and near-optimality guarantees quoted for the exact primal-dual scheduler."},{"cited_title":"Convolutional neural network architectures for signals supported on graphs,","cited_arxiv_id":null,"evidence_quote":"defines the graph convolutional filter architecture used to parameterize the scheduling policy."},{"cited_title":"Resilient constrained learning,","cited_arxiv_id":null,"evidence_quote":"resilient constrained learning used in the experiments to limit the effect of infeasible links."}],"review_version":1}