Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks

Alejandro Ribeiro; Navid Naderializadeh; Romina Garcia Camargo; Zhiyang Wang

REVIEW 4 major objections 6 minor 61 references

Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks

T0 review · 4 major / 6 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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

desk verdict 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. read the letter →

arxiv 2607.18480 v1 pith:Y62L2LAL submitted 2026-07-20 eess.SP

Romina Garcia Camargo , Zhiyang Wang , Navid NaderiAlizadeh , Alejandro Ribeiro This is my paper · ORCID

classification eess.SP

keywords wirelesslinkschedulinglong-horizonoptimizationLagrangiandualitydualsubgradientdescentstateaugmentationgraphneuralnetworksprimaryinterferencemodelper-linkrateconstraints

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

Where 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.

Separately, 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.

Overall: 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.

Referee Report

4 major / 6 minor

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.

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 (4)

[Section IV, Eqs. (18)-(21), and Algorithm 2] 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
[Appendix A, proof of Proposition 2, Eq. (31)] 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.
[Appendix B, Proposition 4, Eq. (49)] 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 V-A and Eq. (22)] 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.

minor comments (6)

[Section II, first paragraph] Typographical errors: 'Tolearnsolutions' should be 'To learn solutions' and 'and and online' should be 'and an online'.
[Proposition 3 and Eq. (39)] 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.
[Appendix A, Eq. (26)] The summation has a typesetting error: 'vX t=v' should be 'Σ_{t=v}^{v}' or simply the instantaneous Lagrangian M(s(v),λ).
[References] 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.
[Algorithm 1, Step 6] The notation 'M(H(n),λ)' does not match Eq. (18), where the loss is M(Φ(A,λ;H),λ). Please align the notation.
[Section V-A] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No equation-level circularity: Prop. 3 is a self-contained dual-subgradient bound for exact Lagrangian maximizers; SAGNN's Lagrangian loss is a design/approximation choice. Main weaknesses are an unproven approximation guarantee and an invalid proof step in Prop. 2—correctness gaps, not circular reductions.

full rationale

The derivation chain is: (i) Prop. 3 bounds the average rate of a sequence of exact instantaneous Lagrangian maximizers under dual subgradient updates (13); (ii) SAGNN is trained to maximize E_{A,λ}[M(Φ(A,λ;H),λ)] (Eq. 19); (iii) the paper asserts SAGNN inherits Prop. 3 when trained to small loss. Step (i) does not reduce to its inputs: (34) uses only the definition of s‡ as an exact maximizer of M, and (38)–(41) telescope the projection/step-size recursion with ||g|| ≤ ||M−Δ||; no fitted quantity is renamed as a prediction. Step (ii) is not circular—using M as the training loss is the natural way to imitate the oracle—but it is incomplete: no bound is given on ε_t = max_s M(s,λ(t)) − M(Φ(A,λ(t);H*),λ(t)), so the inheritance claim is an unproven implication rather than a circular one. The paper's own text contains two caveats that should be weighed: Appendix A, Eq. (31) proves Prop. 2 by asserting r(s‡) ≥ (1/T)Σ r(s†) ≥ Δ under 'assuming constraints are not violated,' which contradicts Section III-A's infeasibility discussion and is an invalid/omitted proof step; and Section V-A/Appendix E shows the λ-training distribution is partly generated by the model's own evaluation trajectories (Eq. (13)/(21)), so the training distribution is self-referential. The experiments also use the resilient update (22), not the analyzed (13). These are correctness/robustness concerns, not fitted-input/predicted-output identities. Citations to the authors' state-augmentation work [25], [26], [29], [32] motivate the architecture but are not load-bearing for the theorem, which is proved in the paper. Score 2 reflects only the minor self-referential training loop and the gap between the theorem and the deployed algorithm; no significant circularity.

Assumptions & free parameters 6 free parameters · 6 assumptions · 0 invented entities

The free parameters are mostly standard hyperparameters (learning rates, architecture) plus problem constants (Δ, η, α) chosen without sensitivity analysis. The axioms include standard convex-analysis facts and the primary-interference domain model; two ad-hoc assumptions appear in the proofs (componentwise inequality in Prop 2 and the strict-feasibility condition in Prop 4), and the crucial unquantified step is assuming the GNN approximates the exact MWIS oracle well enough for the dual theory to hold.

free parameters (6)

dual step size η = 2
Constant stepsize in dual subgradient update (13)/(21); chosen by hand, no sensitivity analysis. It appears in the O(η) optimality bound and O(1/(ηT)) feasibility bound.
resilience factor α = 0.05
Added in (22) as L1 regularization to mitigate infeasible links; fixed for all Δ, no justification.
primal learning rate ζ = 5e-5
Adam learning rate for GNN training (Section V-A), chosen by hand.
transmission requirement Δ = 0.1, 0.125, 0.15 (per-link uniform)
Problem instances; chosen to be feasible. These are problem inputs, but the paper tunes them and they are not part of a broader sensitivity study.
GNN architecture hyperparameters = 3 layers, 256 features, filter order 3
Architecture choices in Appendix D; not justified by theory.
training λ distribution pλ = U[0,2] then empirical
Sampling distribution for dual variables during training (Algorithm 1); Appendix E shows performance depends on this choice.

assumptions (6)

standard math Lagrangian dual function is convex and subgradient methods converge (Boyd and Vandenberghe; Bertsekas)
Used in Section III and Appendix A for Props 3 and 4.
domain assumption Primary interference model: two links interfere iff they share a device; successful transmission is r(s)=s⊙(1−As)_+
The entire problem formulation (Section II) and the MWIS equivalence rest on this model.
domain assumption The scheduling problem is equivalent to finding maximum-weight independent sets each slot
Implicit in the Lagrangian maximization (11), though not formally stated; used throughout.
ad hoc to paper GNN approximates the exact MWIS oracle well enough for dual-subgradient analysis to apply
The theory (Prop 3) requires exact Lagrangian maximizers; SAGNN only approximates them (Section IV), and no error bound is provided.
ad hoc to paper Componentwise inequality r(s‡) ≥ (1/T)Σ r(s†) ≥ Δ in Prop 2 proof
Assumed in Eq. (31) with the note 'we are assuming constraints are not violated', contradicting Section III-A's infeasibility result. Unjustified assumption.
ad hoc to paper Strict feasibility condition d(λ(u))−d(λ*) ≥ ε||λ(u)−λ*|| for some ε
Introduced in Prop 4 proof (Appendix B) without definition or proof; needed for the boundedness of λ.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks." pith.science (2026). https://pith.science/paper/Y62L2LAL

@misc{pith2026260718480,
  author       = {Pith},
  title        = {Pith review of: Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y62L2LAL}},
  note         = {Machine review of arXiv:2607.18480}
}

read the original abstract

We address optimal link scheduling in large-scale wireless networks. The goal is to schedule transmissions over a time horizon so that to maximize sum rate while ensuring that average rates of each customer attain a minimum rate requirement. To this end, we formulate a constrained optimization problem and solve it using Lagrangian duality. Common primal-dual approaches lead to time invariant policies. Our constraint requires all links transmit a fraction of the time while avoiding interference, which calls for time-varying policies across time slots. We propose an iterative algorithm to sample optimal sequences of schedules and dual variables. The scheduling decisions are parameterized using a Graph Neural Network. We incorporate state-augmentation techniques to learn said parameterization, introducing dual variables as dynamic inputs to the policy. This augmentation enables the GNN to adapt scheduling decisions over time, balancing constraint satisfaction with performance maximization. We validate our approach through extensive numerical simulations, benchmarking against several baselines and considering varying constraint levels.

Figures

Figures reproduced from arXiv: 2607.18480 by the authors.

**Figure 1.** Illustration of an optimal policy for different time steps. Links scheduled for transmission are highlighted with a [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

**Figure 2.** Evolution of constraint violation during training for [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Evolution of the average successful transmissions in [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (7 more)

**Figure 5.** Figure 5: Successful transmission rates achieved by links for [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

**Figure 4.** Figure 4: Box plot of the distribution of values for links [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

**Figure 6.** Figure 6: In red, percentage of constraint violation when a [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]

**Figure 7.** Figure 7: Robustness of the model to different minimum [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]

**Figure 9.** Figure 9: Number of total and successful transmissions for [PITH_FULL_IMAGE:figures/full_fig_p010_9.png]

**Figure 10.** Figure 10: Degree distributions for conflict graphs with [PITH_FULL_IMAGE:figures/full_fig_p015_10.png]

**Figure 11.** Figure 11: Constraint violation evolution during training, [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 1 canonical work pages

[1]

Wireless link scheduling with state-augmented graph neural networks,

R. G. Camargo, Z. Wang, N. NaderiAlizadeh, and A. Ribeiro, “Wireless link scheduling with state-augmented graph neural networks,” 2025. [Online]. Available: https://arxiv.org/abs/2505.07598

arXiv 2025
[2]

FPLinQ: A cooperative spectrum sharing strategy for device-to-device communications,

K. Shen and W. Yu, “FPLinQ: A cooperative spectrum sharing strategy for device-to-device communications,” in2017 IEEE international symposium on information theory (ISIT). IEEE, 2017, pp. 2323–2327

2017
[3]

FlashLinQ: A synchronous distributed scheduler for peer-to- peer ad hoc networks,

X. Wu, S. Tavildar, S. Shakkottai, T. Richardson, J. Li, R. Laroia, and A. Jovicic, “FlashLinQ: A synchronous distributed scheduler for peer-to- peer ad hoc networks,”IEEE/ACM Transactions on Networking, vol. 21, no. 4, pp. 1215–1228, 2013

2013
[4]

ITLinQ: A new approach for spectrum sharing in device-to-device communication systems,

N. Naderializadeh and A. S. Avestimehr, “ITLinQ: A new approach for spectrum sharing in device-to-device communication systems,”IEEE Journal on Selected Areas in Communications, vol. 32, no. 6, pp. 1139– 1151, 2014

2014
[5]

Itlinq+: An improved spectrum sharing mechanism for device-to-device communications,

X. Yi and G. Caire, “Itlinq+: An improved spectrum sharing mechanism for device-to-device communications,” in2015 49th Asilomar Conference on Signals, Systems and Computers. IEEE, 2015, pp. 1310–1314

2015
[6]

Spatial deep learning for wireless scheduling,

W. Cui, K. Shen, and W. Yu, “Spatial deep learning for wireless scheduling,”IEEE Journal on Selected Areas in Communications, vol. 37, no. 6, pp. 1248–1261, 2019

2019
[7]

Grlinq: A distributed link scheduling mechanism with graph reinforcement learning,

Z. Shan, X. Yi, L. Liang, C.-S. Liao, and S. Jin, “Grlinq: A distributed link scheduling mechanism with graph reinforcement learning,” in2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 2436–2441

2024
[8]

The np-completeness of edge-coloring,

I. Holyer, “The np-completeness of edge-coloring,”SIAM Journal on Computing, vol. 10, no. 4, pp. 718–720, 1981. [Online]. Available: https://doi.org/10.1137/0210055

doi:10.1137/0210055 1981

Show all 61 references

[9]

Strong np-completeness results: Motivation, examples, and implications,

M. R. Garey and D. S. Johnson, “Strong np-completeness results: Motivation, examples, and implications,”J. ACM, vol. 25, no. 3, p. 499–508, Jul. 1978. [Online]. Available: https://doi.org/10.1145/322077. 322090

1978 doi
[10]

Shortest link scheduling algorithms in wireless networks under the sinr model,

J. Yu, B. Huang, X. Cheng, and M. Atiquzzaman, “Shortest link scheduling algorithms in wireless networks under the sinr model,”IEEE Transactions on Vehicular Technology, vol. 66, no. 3, pp. 2643–2657, 2017

2017
[11]

Wireless link scheduling with power control and sinr constraints,

S. Borbash and A. Ephremides, “Wireless link scheduling with power control and sinr constraints,”IEEE Transactions on Information Theory, vol. 52, no. 11, pp. 5106–5111, 2006

2006
[12]

Topological interference management through index coding,

S. A. Jafar, “Topological interference management through index coding,” IEEE Transactions on Information Theory, vol. 60, no. 1, pp. 529–568, 2013

2013
[13]

Link scheduling in wireless sensor networks: Distributed edge-coloring revisited,

S. Gandham, M. Dawande, and R. Prakash, “Link scheduling in wireless sensor networks: Distributed edge-coloring revisited,”Journal of Parallel and Distributed Computing, vol. 68, no. 8, pp. 1122–1134,
[14]

Efficient interference-aware tdma link scheduling for static wireless networks,

W. Wang, Y . Wang, X.-Y . Li, W.-Z. Song, and O. Frieder, “Efficient interference-aware tdma link scheduling for static wireless networks,” in Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, ser. MobiCom ’06. New York, NY , USA: Asso...

2006
[15]

Link scheduling using graph neural networks,

Z. Zhao, G. Verma, C. Rao, A. Swami, and S. Segarra, “Link scheduling using graph neural networks,”IEEE Transactions on Wireless Communi- cations, vol. 22, no. 6, pp. 3997–4012, 2023

2023
[16]

Approximation algorithms for wireless link scheduling with sinr-based interference,

D. M. Blough, G. Resta, and P. Santi, “Approximation algorithms for wireless link scheduling with sinr-based interference,”IEEE/ACM Transactions on Networking, vol. 18, no. 6, pp. 1701–1712, 2010

2010
[17]

Wireless link scheduling under a graded sinr interference model,

P. Santi, R. Maheshwari, G. Resta, S. Das, and D. M. Blough, “Wireless link scheduling under a graded sinr interference model,” inProceedings of the 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing, ser. FOW ANC ’09. New York...

2009
[18]

Wireless link scheduling under physical interference model,

P.-J. Wan, O. Frieder, X. Jia, F. Yao, X. Xu, and S. Tang, “Wireless link scheduling under physical interference model,” in2011 Proceedings IEEE INFOCOM, 2011, pp. 838–845

2011
[19]

Wireless link scheduling via parallel genetic algorithm,

M. Saad, A. El-Moursy, O. Alfawaz, K. Alnajjar, and S. Abdallah, “Wireless link scheduling via parallel genetic algorithm,”Concurrency and Computation: Practice and Experience, vol. 34, 12 2021

2021
[20]

Graph embedding-based wireless link scheduling with few training samples,

M. Lee, G. Yu, and G. Y . Li, “Graph embedding-based wireless link scheduling with few training samples,”IEEE Transactions on Wireless Communications, vol. 20, no. 4, pp. 2282–2294, 2021

2021
[21]

Geometric machine learning over riemannian manifolds for wireless link scheduling,

R. Shelim and A. S. Ibrahim, “Geometric machine learning over riemannian manifolds for wireless link scheduling,”IEEE Access, vol. 10, pp. 22 854–22 864, 2022

2022
[22]

Gblinks: Gnn- based beam selection and link activation for ultra-dense d2d mmwave networks,

S. He, S. Xiong, W. Zhang, Y . Yang, J. Ren, and Y . Huang, “Gblinks: Gnn- based beam selection and link activation for ultra-dense d2d mmwave networks,”IEEE Transactions on Communications, vol. 70, no. 5, pp. 3451–3466, 2022

2022
[23]

Link scheduling in polynomial time,

B. Hajek and G. Sasaki, “Link scheduling in polynomial time,”IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 910–917, 1988

1988
[24]

Impact of interference on multi-hop wireless network performance,

K. Jain, J. Padhye, V . N. Padmanabhan, and L. Qiu, “Impact of interference on multi-hop wireless network performance,” inProceedings of the 9th Annual International Conference on Mobile Computing and Networking, ser. MobiCom ’03. New York, NY , USA: Association for Computing ...

2003
[25]

State augmented constrained reinforcement learning: Overcoming the limitations of learning with rewards,

M. Calvo-Fullana, S. Paternain, L. F. O. Chamon, and A. Ribeiro, “State augmented constrained reinforcement learning: Overcoming the limitations of learning with rewards,” 2023. [Online]. Available: https://arxiv.org/abs/2102.11941

2023 arXiv
[27]

Boyd and L

S. Boyd and L. Vandenberghe,Convex optimization. Cambridge university press, 2004

2004
[28]

Nonlinear programming,

D. P. Bertsekas, “Nonlinear programming,”Journal of the Operational Research Society, vol. 48, no. 3, pp. 334–334, 1997

1997
[29]

State-augmented learnable algorithms for resource management in wireless networks,

N. NaderiAlizadeh, M. Eisen, and A. Ribeiro, “State-augmented learnable algorithms for resource management in wireless networks,”IEEE Transactions on Signal Processing, vol. 70, pp. 5898–5912, 2022

2022
[30]

Adam: A method for stochastic optimization,

D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,”
[31]

Resilient constrained learning,

I. Hounie, A. Ribeiro, and L. F. O. Chamon, “Resilient constrained learning,” inAdvances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, Eds., vol. 36. Curran Associates, Inc., 2023, pp. 71 767–71 798. [Online]. Av...

2023
[32]

Learning resilient radio resource management policies with graph neural networks,

N. NaderiAlizadeh, M. Eisen, and A. Ribeiro, “Learning resilient radio resource management policies with graph neural networks,”IEEE Transactions on Signal Processing, vol. 71, pp. 995–1009, 2023

2023
[33]

Finding near-optimal independent sets at scale,

S. Lamm, P. Sanders, C. Schulz, D. Strash, and R. F. Werneck, “Finding near-optimal independent sets at scale,”J. Heuristics, vol. 23, no. 4, pp. 207–229, 2017. [Online]. Available: https: //doi.org/10.1007/s10732-017-9337-x

2017 doi
[34]

Scalable kernelization for maximum independent sets,

D. Hespe, C. Schulz, and D. Strash, “Scalable kernelization for maximum independent sets,”ACM Journal of Experimental Algorithmics, vol. 24, no. 1, pp. 1.16:1–1.16:22, 2019. [Online]. Available: https://doi.org/10.1145/3355502

2019 doi
[35]

Exactly solving the maximum weight independent set problem on large real-world graphs,

S. Lamm, C. Schulz, D. Strash, R. Williger, and H. Zhang, “Exactly solving the maximum weight independent set problem on large real-world graphs,” inProceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019. SIAM, 2019, pp. 144–158. [Online...

2019 doi
[36]

Decentralized wireless resource allocation with graph neural networks,

Z. Wang, M. Eisen, and A. Ribeiro, “Decentralized wireless resource allocation with graph neural networks,” in2020 54th Asilomar Conference on Signals, Systems, and Computers, 2020, pp. 299–303

2020
[37]

Interference networks with no csit: Impact of topology,

N. Naderializadeh and A. S. Avestimehr, “Interference networks with no csit: Impact of topology,”IEEE Transactions on Information Theory, vol. 61, no. 2, pp. 917–938, 2014

2014
[38]

Topological interference management with transmitter cooperation,

X. Yi and D. Gesbert, “Topological interference management with transmitter cooperation,”IEEE Transactions on Information Theory, vol. 61, no. 11, pp. 6107–6130, 2015

2015
[39]

Topological interference management with reconfigurable antennas,

H. Yang, N. Naderializadeh, A. S. Avestimehr, and J. Lee, “Topological interference management with reconfigurable antennas,”IEEE Transac- tions on Communications, vol. 65, no. 11, pp. 4926–4939, 2017

2017
[40]

Topological interference management with decoded message passing,

X. Yi and G. Caire, “Topological interference management with decoded message passing,”IEEE Transactions on Information Theory, vol. 64, no. 5, pp. 3842–3864, 2018. 11

2018
[41]

Multilevel topological interference management: A tim-tin perspective,

C. Geng, H. Sun, and S. A. Jafar, “Multilevel topological interference management: A tim-tin perspective,”IEEE Transactions on Communica- tions, vol. 69, no. 11, pp. 7350–7362, 2021

2021
[42]

Revisiting topological interference management: A learning-to-code on graphs perspective,

Z. Shan, X. Yi, H. Yu, C.-S. Liao, and S. Jin, “Revisiting topological interference management: A learning-to-code on graphs perspective,” arXiv preprint arXiv:2502.09344, 2025

2025 arXiv
[43]

Gaussian interference channel capacity to within one bit,

R. H. Etkin, N. David, and H. Wang, “Gaussian interference channel capacity to within one bit,”IEEE Transactions on information theory, vol. 54, no. 12, pp. 5534–5562, 2008

2008
[44]

On the optimality of treating interference as noise,

C. Geng, N. Naderializadeh, A. S. Avestimehr, and S. A. Jafar, “On the optimality of treating interference as noise,”IEEE Transactions on Information Theory, vol. 61, no. 4, pp. 1753–1767, 2015

2015
[45]

Transferability Properties of Graph Neural Networks,

L. Ruiz, L. F. Chamon, and A. Ribeiro, “Transferability Properties of Graph Neural Networks,”arXiv preprint arXiv:2112.04629, 2021

2021 arXiv
[46]

Transferability of spectral graph convolutional neural networks,

R. Levie, W. Huang, L. Bucci, M. Bronstein, and G. Kutyniok, “Transferability of spectral graph convolutional neural networks,”Journal of Machine Learning Research, vol. 22, no. 272, pp. 1–59, 2021

2021
[47]

Optimal wireless resource allocation with random edge graph neural networks,

M. Eisen and A. Ribeiro, “Optimal wireless resource allocation with random edge graph neural networks,”ieee transactions on signal processing, vol. 68, pp. 2977–2991, June 2020

2020
[48]

Transferable policies for large scale wireless networks with graph neural networks,

——, “Transferable policies for large scale wireless networks with graph neural networks,” inICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, pp. 5040– 5044

2020
[49]

On the transferability of graph neural networks for resource allocation in wireless networks,

S. Fernández, R. G. Camargo, M. Eisen, A. Ribeiro, and F. Larroca, “On the transferability of graph neural networks for resource allocation in wireless networks,” in2024 IEEE URUCON, 2024, pp. 1–5

2024
[50]

Learning decentralized wireless resource allocations with graph neural networks,

Z. Wang, M. Eisen, and A. Ribeiro, “Learning decentralized wireless resource allocations with graph neural networks,”IEEE Transactions on Signal Processing, vol. 70, pp. 1850–1863, 2022

2022
[51]

Graph neural networks in large scale wireless communication networks: Scalability across random geometric graphs,

R. G. Camargo, Z. Wang, and A. Ribeiro, “Graph neural networks in large scale wireless communication networks: Scalability across random geometric graphs,” 2025. [Online]. Available: https: //arxiv.org/abs/2510.00896

2025
[52]

Convolutional neural network architectures for signals supported on graphs,

F. Gama, A. G. Marques, G. Leus, and A. Ribeiro, “Convolutional neural network architectures for signals supported on graphs,”IEEE Transactions on Signal Processing, vol. 67, no. 4, pp. 1034–1049, 2019

2019
[53]

The graph neural network model,

F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,”IEEE transactions on neural networks, vol. 20, no. 1, pp. 61–80, 2008

2008
[54]

Graph signal processing: Overview, challenges, and applications,

A. Ortega, P. Frossard, J. Kova ˇcevi´c, J. M. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,”Pro- ceedings of the IEEE, vol. 106, no. 5, pp. 808–828, 2018

2018
[55]

Graph neural networks: Architectures, stability, and transferability,

L. Ruiz, F. Gama, and A. Ribeiro, “Graph neural networks: Architectures, stability, and transferability,”Proceedings of the IEEE, vol. 109, no. 5, pp. 660–682, 2021

2021
[56]

Stability of graph scattering transforms,

F. Gama, A. Ribeiro, and J. Bruna, “Stability of graph scattering transforms,”Advances in Neural Information Processing Systems, vol. 32, pp. 8038–8048, 2019

2019
[57]

Geometric graph filters and neural networks: Limit properties and discriminability trade-offs,

Z. Wang, L. Ruiz, and A. Ribeiro, “Geometric graph filters and neural networks: Limit properties and discriminability trade-offs,”IEEE Transactions on Signal Processing, 2024

2024
[60]

Categorical reparameterization with gumbel-softmax,

E. Jang, S. Gu, and B. Poole, “Categorical reparameterization with gumbel-softmax,” 2017. [Online]. Available: https://arxiv.org/abs/1611. 01144 APPENDIX A. Proofs We present the proofs of the propositions from Section III. Proposition 1 Let s†(1 :T,λ) be a maximizing (6) sche...

2017
[61]

Available: http://arxiv.org/abs/1710.10370

[Online]. Available: http://arxiv.org/abs/1710.10370

arXiv
[2008]

Available: https://www.sciencedirect.com/science/article/ pii/S0743731508000142

[Online]. Available: https://www.sciencedirect.com/science/article/ pii/S0743731508000142
[2015]

Available: http://arxiv.org/abs/1502.03167

[Online]. Available: http://arxiv.org/abs/1502.03167

arXiv
[2017]

Available: https://arxiv.org/abs/1412.6980

[Online]. Available: https://arxiv.org/abs/1412.6980

arXiv

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

Wireless link scheduling with state-augmented graph neural networks,

R. G. Camargo, Z. Wang, N. NaderiAlizadeh, and A. Ribeiro, “Wireless link scheduling with state-augmented graph neural networks,” 2025. [Online]. Available: https://arxiv.org/abs/2505.07598

arXiv 2025

[2] [2]

FPLinQ: A cooperative spectrum sharing strategy for device-to-device communications,

K. Shen and W. Yu, “FPLinQ: A cooperative spectrum sharing strategy for device-to-device communications,” in2017 IEEE international symposium on information theory (ISIT). IEEE, 2017, pp. 2323–2327

2017

[3] [3]

FlashLinQ: A synchronous distributed scheduler for peer-to- peer ad hoc networks,

X. Wu, S. Tavildar, S. Shakkottai, T. Richardson, J. Li, R. Laroia, and A. Jovicic, “FlashLinQ: A synchronous distributed scheduler for peer-to- peer ad hoc networks,”IEEE/ACM Transactions on Networking, vol. 21, no. 4, pp. 1215–1228, 2013

2013

[4] [4]

ITLinQ: A new approach for spectrum sharing in device-to-device communication systems,

N. Naderializadeh and A. S. Avestimehr, “ITLinQ: A new approach for spectrum sharing in device-to-device communication systems,”IEEE Journal on Selected Areas in Communications, vol. 32, no. 6, pp. 1139– 1151, 2014

2014

[5] [5]

Itlinq+: An improved spectrum sharing mechanism for device-to-device communications,

X. Yi and G. Caire, “Itlinq+: An improved spectrum sharing mechanism for device-to-device communications,” in2015 49th Asilomar Conference on Signals, Systems and Computers. IEEE, 2015, pp. 1310–1314

2015

[6] [6]

Spatial deep learning for wireless scheduling,

W. Cui, K. Shen, and W. Yu, “Spatial deep learning for wireless scheduling,”IEEE Journal on Selected Areas in Communications, vol. 37, no. 6, pp. 1248–1261, 2019

2019

[7] [7]

Grlinq: A distributed link scheduling mechanism with graph reinforcement learning,

Z. Shan, X. Yi, L. Liang, C.-S. Liao, and S. Jin, “Grlinq: A distributed link scheduling mechanism with graph reinforcement learning,” in2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 2436–2441

2024

[8] [8]

The np-completeness of edge-coloring,

I. Holyer, “The np-completeness of edge-coloring,”SIAM Journal on Computing, vol. 10, no. 4, pp. 718–720, 1981. [Online]. Available: https://doi.org/10.1137/0210055

doi:10.1137/0210055 1981