Pith. sign in

REVIEW 3 major objections 4 minor 45 references

The paper claims that replacing the back-pressure backlog with a learned, bounded graph-neural-network backlog and scheduling with Sinkhorn optimal transport preserves drift-plus-penalty optimality while consistently reducing queue ratio (d

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

A GNN-learned backlog plus optimal-transport scheduling reduces delay in drift-plus-penalty network routing while claiming to keep throughput guarantees.

T0 review reviewed 2026-08-04 challenge →

load-bearing objection A promising no-penalty result and a clever Sinkhorn scheduling trick, but the penalty weight V never enters the described algorithm, so the paper's main DPP trade-off claim is not supported as written. the 3 major comments →

arxiv 2509.09637 v1 pith:AHAFFMU3 submitted 2025-09-11 eess.SY cs.SY

A neural drift-plus-penalty algorithm for network power allocation and routing

Ahmed Rashwan , Keith Briggs , Chris Budd This is my paper
classification eess.SY cs.SY
keywords drift-plus-penaltyback-pressure routinggraph neural networksSinkhorn algorithmoptimal transportpower allocationLyapunov optimizationqueue stability
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

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 aims to show that the classical drift-plus-penalty method for network routing can be made both safer and faster by learning its backlog function with a graph neural network and by solving its scheduling subproblem with an entropy-regularized optimal-transport routine (Sinkhorn). Its core theoretical result is that any backlog function within a bounded distance of the true queue lengths is throughput-optimal and approaches the optimal penalty as the penalty weight grows, so a bounded neural backlog keeps the guarantees. Empirically, the learned backlog and Sinkhorn scheduler consistently improve the queue ratio (a proxy for delay) over back-pressure, shortest-path, and QSP baselines under no-penalty, power-consumption, and energy-efficiency objectives. This matters because drift-plus-penalty methods are known to have poor delay under light load, and the paper shows the trade-off can be relaxed without sacrificing the Lyapunov-style guarantees.

Core claim

The central claim is that drift-plus-penalty optimality survives a learned backlog. Theorem 1 states that if the backlog function U(t) stays within a uniform bound B of the actual queue vector Q(t) at every time, then the DPP algorithm is throughput-optimal for every penalty weight V and drives the expected penalty to the optimum p* as V goes to infinity. The paper then constructs two neural backlogs from a GNN: Neural-B with a sigmoid output that enforces the bound, and Neural with a linear output that does not. Scheduling is posed as a discrete optimal transport problem, solved approximately with Sinkhorn iterations, which is fully differentiable and restores gradients for training. Experi

What carries the argument

The load-bearing objects are (i) the backlog function U, which replaces the raw queue difference in the drift-plus-penalty weight W = U_i,c - U_j,c and thereby controls route selection; (ii) Theorem 1, a sufficient condition linking a uniform bound on U-Q to throughput optimality and penalty optimality; and (iii) the Sinkhorn-based solver for the entropy-regularized optimal transport formulation of the scheduling LP, which computes a differentiable approximate max-weight schedule. The backlog bound is what converts a learned heuristic into a provably stabilizing controller; the Sinkhorn entropy term is what makes the schedule differentiable and spreads traffic across paths.

Load-bearing premise

The paper's theoretical and experimental claims hold only if the implemented algorithm actually incorporates the penalty weight V that the drift-plus-penalty objective names; as written, Algorithm 1 never receives V, so the penalty trade-off curves rest on an unspecified mechanism for V entering the power or scheduling choices.

What would settle it

Run Algorithm 1 with two different penalty weights V (e.g., V=0.05 and V=0.4) on identical inputs and check whether the output power and schedule are identical; if the forward pass is invariant to V, then the claimed DPP penalty trade-off is not implemented and the Section VI-C curves cannot be attributed to the drift-plus-penalty mechanism.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Any bounded backlog function, including a learned one, inherits the throughput-optimality and asymptotic penalty-optimality guarantees of drift-plus-penalty control.
  • The Sinkhorn-based scheduler provides a differentiable surrogate for max-weight scheduling, enabling end-to-end unsupervised training of the backlog from a network model.
  • At low data rates, where classical back-pressure suffers random-walk delays, Sinkhorn scheduling with neural backlogs yields the largest queue-ratio gains.
  • The method extends naturally to time-varying network topologies and out-of-distribution arrival rates without retraining per topology.
  • The entropy regularization parameter eta acts as an additional congestion-control knob: lower eta spreads traffic and improves weak backlogs like BP and QSP.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The paper's finding that the unbounded Neural backlog often outperforms the bounded Neural-B suggests the uniform-bound condition may be sufficient but not necessary; a relaxed bound might be enough in practice, though the guarantees would then need a separate argument.
  • If the penalty weight V truly does not enter the forward pass as written in Algorithm 1, the penalized curves in Section VI-C should be reread as comparing methods at the same nominal V rather than as demonstrations of the DPP trade-off; a corrected implementation would pass V into the power network or scheduling objective.
  • The entropy-regularized schedule could be viewed as an implicit load-balancing mechanism; this suggests a testable extension where eta is annealed or learned per-node rather than fixed.
  • The sparse, batched Sinkhorn implementation points to a practical GPU deployment path for distributed routing, and the same architectural pattern could be applied to other LP-based network controllers.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper proposes a learned variant of the drift-plus-penalty (DPP) method for joint transmit-power allocation and multi-hop routing. A GNN computes a neural backlog U_N and a power allocation f_phi; link scheduling is then posed as an optimal-transport problem and solved approximately with Sinkhorn iterations. Theorem 1 gives a sufficient condition for throughput optimality and asymptotic penalty optimality when the learned backlog is uniformly close to the true queue. Experiments on random geometric networks compare neural backlogs against SP, QSP, and BP baselines, reporting queue-ratio (delay) improvements under several penalties, out-of-distribution rates, and time-varying topologies.

Significance. If the theoretical and experimental claims hold, the paper would make a useful contribution: a differentiable, distributed DPP implementation that can be trained end-to-end while retaining stability guarantees, plus an OT-based scheduling surrogate with entropy regularization. The idea of learning a bounded backlog function is natural and the empirical gains in the no-penalty setting appear plausible. However, the manuscript as written has a load-bearing gap: the penalty weight V is never used in the described implementation, so the penalized DPP experiments are not internally consistent. The proof of Theorem 2 also contains a suspicious construction. These issues are fixable but need to be addressed before the central claims can be accepted.

major comments (3)
  1. [§V, Algorithm 1, §VI-C] Algorithm 1's inputs are (Q, S, η, G, z_U, z_P); the power network f_phi(G, Q, U, S) does not take V; the scheduling objectives (W)/(E) contain W+·μ and entropy but no -V p(P, S); and φ is trained to maximize (E). Thus, for fixed inputs, the outputs P and μ are independent of V. Yet §VI-C reports average penalty and queue ratio versus V and states that methods achieve 'different balance' at the same V. The paper never specifies a mechanism by which V enters the power network, the scheduling weights, or the training loss. As written, the penalized experiments do not implement D(U, V), so the V-curves cannot support the DPP trade-off claim of Theorem 1.
  2. [§IV-A, Theorem 1 and Appendix A] Theorem 1 states throughput optimality for all V≥0 and p→p* as V→∞ without qualification. The proof in Appendix A relies on an 'optimal S-only algorithm' satisfying E[δ_i,c+λ_i,c]<0 for i≠c, an assumption stated only there. This assumption is load-bearing for the penalty part of the theorem: it supplies the θ·Q term in the drift bound. The assumption should either be stated in the theorem statement or proved from standard capacity-region conditions; otherwise the theorem overclaims.
  3. [Appendix B, proof of Theorem 2] The construction of a feasible solution to (T) from a solution of (W) is invalid as written. Step 2 says 'We set M_ij=0 for all elements where row i or column j is saturated.' If a row is saturated by a positive entry placed in Step 1, zeroing the entire row destroys the row sum; similarly for columns. The residual subproblem cannot then restore the original row and column targets. Since Theorem 2 is used to justify the clipping step after Sinkhorn, a correct proof is needed.
minor comments (4)
  1. [Algorithm 1 caption] The caption says 'The for-loop over V is shown for only for simplifying the exposition', but the algorithm contains a for-loop over nodes i∈V, not over the penalty weight V. This is confusing because V is also used for the penalty weight.
  2. [§IV-B3 and §VI] The bound B in Theorem 1 is called A=10 in the experiments without comment. Also, the sigmoid output layer for Neural-B is said to 'satisfy the bound ||Q−U_N||∞≤B', but the exact construction that guarantees this bound is not given.
  3. [§IV-B3 and §VI] The neural backlogs are trained to minimize ||Q||_1, which is also the basis of the queue-ratio evaluation metric. This makes the no-penalty comparisons partly a fitting-to-the-target exercise. The out-of-distribution and time-varying results help, but the paper should acknowledge this circularity and, if possible, report a metric not directly optimized.
  4. [§VI-A] No code or detailed hyperparameters are provided. Given the V-omission issue, the experimental penalty results are not reproducible from the text alone. Please add an implementation appendix or release code.

Circularity Check

2 steps flagged

Neural backlog is trained on the same queue-size metric used as the headline delay metric, and the described DPP implementation never passes the penalty weight V into any trained component.

specific steps
  1. fitted input called prediction [Section IV-B.3 (Neural backlogs) and Section VI (Performance metrics)]
    "neural backlogs are trained to minimise the queue-size loss L(Q(t)) = ||Q(t)||1 ... r = E[ ||Q(tmax)||1 / Ptmax−1 i=0 ||A(i)||1 ] = Ei̸=c[Qi,c(tmax)] / (λ0 tmax) ∈ [0,1], which measures the total proportion of data still queued in the network after tmax time-steps."

    The training objective L(Q(t)) = ||Q(t)||_1 is exactly the numerator of the evaluation metric r, up to the constant normalization by total arrivals. Thus the no-penalty queue-ratio improvements reported for Neural/Neural-B are, in-distribution, the metric those backlogs were explicitly optimized against, rather than an independent prediction of delay. The out-of-distribution and time-varying experiments are outside the training distribution and supply some independent grounding, so this is partial circularity rather than a full reduction.

  2. other [Section V (Algorithm 1, V-A, V-B) and Section VI-C]
    "Algorithm 1: Input: Q, S, η, G, zt_U, zt_P ... P=f_ϕ(G,Q,U,S) ... ϕ is trained to maximise the objective of (E) ... For the power consumption and energy efficiency penalties, we recorded both the average penalties and queue ratios across different values of the penalty weight V≥0."

    The DPP problem (D) includes −V p(P,S) and Theorem 1's penalty-optimality is controlled by V, but Algorithm 1's input list contains no V, f_ϕ receives no V, and the training objective (E) contains no −V p(P,S) term. Hence for fixed (Q,S,G,η,z_U,z_P) the described outputs P and µ are independent of V. The Section VI-C curves labeled by V therefore do not implement the claimed DPP trade-off; either V is injected by an unspecified mechanism or the penalty experiments are unsupported as evidence for the paper's central penalty claim. This is a missing load-bearing mechanism rather than a formal equivalence, but it prevents the penalty results from being supported by the described method.

full rationale

The theoretical anchor, Theorem 1, is not circular: it is a standard Lyapunov sufficient-condition argument proved in Appendix A using an external lemma, and the Sinkhorn/OT scheduling contribution has its own independent Theorem 2. There is no load-bearing self-citation chain and no imported uniqueness theorem. The two concerns are: (1) the headline delay metric coincides with the neural training objective, making the in-distribution delay improvements largely self-fulfilling, although the OOD and mobility experiments provide independent empirical support; (2) the penalty weight V is absent from the described forward pass and training losses, so the penalized experiments lack a specified mechanism for the V trade-off they claim to show. These issues make the empirical claims partially circular and partially unsupported, but the overall derivation is not equivalent to its inputs by construction. A score of 4 reflects partial circularity in the empirical evaluation plus a load-bearing missing mechanism, while acknowledging the independent content in the theory and OOD tests.

Axiom & Free-Parameter Ledger

2 free parameters · 6 axioms · 0 invented entities

The paper introduces no new physical or conceptual entities beyond a learned backlog function, which is a trainable map, not a postulated entity. The free parameters are the hand-chosen bound B and the Sinkhorn entropy weight eta. The main load-bearing assumptions are the i.i.d./stationarity and differentiability assumptions inherited from the DPP framework.

free parameters (2)
  • Neural-B bound B (called A=10 in the text) = 10
    Hand-fixed bound on ||U_N - Q||_infinity in Section VI: 'For the Neural-B backlog, we fix A=10'; larger B gives more flexibility at the cost of robustness per the Theorem 1 discussion.
  • Sinkhorn regularization parameter eta = 0.5 and 1 (experiments)
    Hand-chosen in Section VI; controls entropy regularization strength in (E) and is shown to affect queue ratio, e.g., BP goes from 0.953 (eta=1, Max-weight) to 0.887 (eta=0.5).
axioms (6)
  • domain assumption External arrivals A(t) and network state S(t) are i.i.d. with finite first and second moments.
    Section II, used to guarantee the existence of stationary S-only policies in the proof of Theorem 1; time-variable networks in Section VI-E violate this, so the theoretical guarantee does not cover that experiment.
  • domain assumption There exists an optimal S-only algorithm achieving minimum penalty p* with E[delta_i,c + lambda_i,c] < 0 for i != c.
    Appendix A, first paragraph; the paper notes this assumption is not needed in the no-penalty case but is required for the penalized optimality claim.
  • domain assumption Data is continuous (fluid) and the penalty and capacity functions p, kappa are differentiable w.r.t the power allocation P.
    Section II; these smoothness assumptions are needed for the end-to-end differentiability of the training pipeline.
  • standard math The standard Lyapunov drift condition (Lemma 1) from Neely [27].
    Appendix A, Lemma 1, used to turn the drift bound (5) into a stability conclusion.
  • domain assumption GNN message passing with a single layer is sufficient for distributed execution and generalizes across topologies.
    Section III; the inductive bias claim is not proven, only asserted with citations [10,37].
  • domain assumption Sinkhorn iterations converge to a good approximation of (E), and thresholding (4) transfers the OT solution to (W).
    Theorem 2 proves the thresholding for exact solutions of (T), but the implementation uses the entropy-regularized (E), so the exactness does not carry over; convergence and approximation quality are assumed.

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of A neural drift-plus-penalty algorithm for network power allocation and routing." pith.science (2026). https://pith.science/paper/AHAFFMU3

@misc{pith2026250909637,
  author       = {Pith},
  title        = {Pith review of: A neural drift-plus-penalty algorithm for network power allocation and routing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AHAFFMU3}},
  note         = {Machine review of arXiv:2509.09637}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The drift-plus-penalty method is a Lyapunov optimisation technique commonly applied to network routing problems. It reduces the original stochastic planning task to a sequence of greedy optimizations, enabling the design of distributed routing algorithms which stabilize data queues while simultaneously optimizing a specified penalty function. While drift-plus-penalty methods have desirable asymptotic properties, they tend to incur higher network delay than alternative control methods, especially under light network load. In this work, we propose a learned variant of the drift-plus-penalty method that can preserve its theoretical guarantees, while being flexible enough to learn routing strategies directly from a model of the problem. Our approach introduces a novel mechanism for learning routing decisions and employs an optimal transport-based method for link scheduling. Applied to the joint task of transmit-power allocation and data routing, the method achieves consistent improvements over common baselines under a broad set of scenarios.

Figures

Figures reproduced from arXiv: 2509.09637 by Ahmed Rashwan, Chris Budd, Keith Briggs.

Figure 1
Figure 1. Figure 1: Plots of queue ratio as a function of data rate [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Average penalty and queue ratios for the power [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Results for out-of-distribution and time-variable net [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 8 linked inside Pith

  1. [1]

    5G D2D networks: Tech- niques, challenges, and future prospects

    Rafay Iqbal Ansari et al. “5G D2D networks: Tech- niques, challenges, and future prospects”. In:IEEE Systems Journal12.4 (2017), pp. 3970–3984

    2017

  2. [2]

    Back-pressure-based packet-by-packet adaptive routing in communication networks

    Eleftheria Athanasopoulou et al. “Back-pressure-based packet-by-packet adaptive routing in communication networks”. In:IEEE/ACM transactions on networking 21.1 (2012), pp. 244–257

    2012

  3. [3]

    Optimal oblivious routing in poly- nomial time

    Yossi Azar et al. “Optimal oblivious routing in poly- nomial time”. In:Proceedings of the thirty-fifth an- nual ACM symposium on Theory of computing. 2003, pp. 383–388

    2003

  4. [4]

    Relational inductive biases, deep learning, and graph networks. arXiv 2018

    Peter W. Battaglia et al. “Relational inductive biases, deep learning, and graph networks. arXiv 2018”. In: arXiv preprint arXiv:1806.01261(1806)

    Pith/arXiv arXiv 2018

  5. [5]

    Combinatorial optimization and reasoning with graph neural networks

    Quentin Cappart et al. “Combinatorial optimization and reasoning with graph neural networks”. In:Journal of Machine Learning Research24.130 (2023), pp. 1–61

    2023

  6. [6]

    Cross-layer congestion control, rout- ing and scheduling design in ad hoc wireless networks

    Lijun Chen et al. “Cross-layer congestion control, rout- ing and scheduling design in ad hoc wireless networks”. In:Proceedings IEEE INFOCOM 2006. 25TH IEEE In- ternational Conference on Computer Communications. IEEE. 2006, pp. 1–13

    2006

  7. [7]

    Enhancing the delay performance of dynamic backpressure algo- rithms

    Ying Cui, Edmund M Yeh, and Ran Liu. “Enhancing the delay performance of dynamic backpressure algo- rithms”. In:IEEE/ACM Transactions on Networking 24.2 (2015), pp. 954–967

    2015

  8. [8]

    Sinkhorn distances: Lightspeed com- putation of optimal transport

    Marco Cuturi. “Sinkhorn distances: Lightspeed com- putation of optimal transport”. In:Advances in neural information processing systems26 (2013)

    2013

  9. [9]

    A note on two problems in con- nexion with graphs

    Edsger W Dijkstra. “A note on two problems in con- nexion with graphs”. In:Edsger Wybe Dijkstra: his life, work, and legacy. 2022, pp. 287–290

    2022

  10. [10]

    Optimal wireless resource allocation with random edge graph neural networks

    Mark Eisen and Alejandro Ribeiro. “Optimal wireless resource allocation with random edge graph neural networks”. In:IEEE Transactions on Signal Processing 68 (2020), pp. 2977–2991

    2020

  11. [11]

    Multi-agent Q-learning aided back- pressure routing algorithm for delay reduction

    Juntao Gao et al. “Multi-agent Q-learning aided back- pressure routing algorithm for delay reduction”. In: arXiv preprint arXiv:1708.06926(2017)

    Pith/arXiv arXiv 2017

  12. [12]

    Resource allocation and cross-layer control in wireless networks

    Leonidas Georgiadis, Michael J. Neely, Leandros Tassi- ulas, et al. “Resource allocation and cross-layer control in wireless networks”. In:Foundations and Trends® in Networking1.1 (2006), pp. 1–144. 8

    2006

  13. [13]

    Understanding pooling in graph neural networks

    Daniele Grattarola et al. “Understanding pooling in graph neural networks”. In:IEEE transactions on neural networks and learning systems35.2 (2022), pp. 2708–2718

    2022

  14. [14]

    A survey of actor-critic reinforce- ment learning: Standard and natural policy gradients

    Ivo Grondman et al. “A survey of actor-critic reinforce- ment learning: Standard and natural policy gradients”. In:IEEE Transactions on Systems, Man, and Cyber- netics, part C (applications and reviews)42.6 (2012), pp. 1291–1307

    2012

  15. [15]

    Delay-optimal back-pressure routing algorithm for multihop wireless networks

    Long Hai et al. “Delay-optimal back-pressure routing algorithm for multihop wireless networks”. In:IEEE Transactions on Vehicular Technology67.3 (2017), pp. 2617–2630

    2017

  16. [16]

    Efficient gather and scatter oper- ations on graphics processors

    Bingsheng He et al. “Efficient gather and scatter oper- ations on graphics processors”. In:Proceedings of the 2007 ACM/IEEE Conference on Supercomputing. 2007, pp. 1–12

    2007

  17. [17]

    Weihua Hu et al.Strategies for Pre-training Graph Neural Networks. 2020. arXiv: 1905.12265[cs.LG]. URL: https://arxiv.org/abs/1905.12265

    Pith/arXiv arXiv 2020

  18. [18]

    Delay- based back-pressure scheduling in multihop wireless networks

    Bo Ji, Changhee Joo, and Ness B Shroff. “Delay- based back-pressure scheduling in multihop wireless networks”. In:IEEE/ACM Transactions on Networking 21.5 (2012), pp. 1539–1552

    2012

  19. [19]

    Learning skillful medium-range global weather forecasting

    Remi Lam et al. “Learning skillful medium-range global weather forecasting”. In:Science382.6677 (2023), pp. 1416–1421

    2023

  20. [20]

    Graph Matching Networks for Learning the Similarity of Graph Structured Objects

    Yujia Li et al. “Graph Matching Networks for Learning the Similarity of Graph Structured Objects”. In:CoRR abs/1904.12787 (2019). arXiv: 1904.12787.URL: http: //arxiv.org/abs/1904.12787

    Pith/arXiv arXiv 1904

  21. [21]

    Software avail- able from tensorflow.org

    Mart ´ın Abadi et al.TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. Software avail- able from tensorflow.org. 2015.URL: https : / / www . tensorflow.org/

    2015

  22. [22]

    Learning latent permutations with Gumbel-Sinkhorn networks

    Gonzalo Mena et al. “Learning latent permutations with Gumbel-Sinkhorn networks”. In:arXiv preprint arXiv:1802.08665(2018)

    Pith/arXiv arXiv 2018

  23. [23]

    Hard-Constrained Neural Networks with Universal Ap- proximation Guarantees

    Youngjae Min, Anoopkumar Sonar, and Navid Azizan. Hard-Constrained Neural Networks with Universal Ap- proximation Guarantees. 2024. arXiv: 2410 . 10807 [cs.LG].URL: https://arxiv.org/abs/2410.10807

    arXiv 2024

  24. [24]

    Playing Atari with deep reinforcement learning

    V olodymyr Mnih et al. “Playing Atari with deep reinforcement learning”. In:arXiv preprint arXiv:1312.5602(2013)

    Pith/arXiv arXiv 2013

  25. [25]

    Routing without routes: The back- pressure collection protocol

    Scott Moeller et al. “Routing without routes: The back- pressure collection protocol”. In:Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks. 2010, pp. 279–290

    2010

  26. [26]

    Random- ized algorithms

    Rajeev Motwani and Prabhakar Raghavan. “Random- ized algorithms”. In:ACM Computing Surveys (CSUR) 28.1 (1996), pp. 33–37

    1996

  27. [27]

    Stability and probability 1 con- vergence for queueing networks via Lyapunov opti- mization

    Michael J. Neely. “Stability and probability 1 con- vergence for queueing networks via Lyapunov opti- mization”. In:Journal of Applied Mathematics2012.1 (2012), p. 831909

    2012

  28. [28]

    Dynamic power allocation and routing for time varying wireless networks

    Michael J. Neely, Eytan Modiano, and Charles E Rohrs. “Dynamic power allocation and routing for time varying wireless networks”. In:IEEE INFOCOM 2003. Twenty- second Annual Joint Conference of the IEEE Com- puter and Communications Societies (IEEE Cat. No. 03CH37428). V ol. 1. IEEE. 2003, pp. 745–755

    2003

  29. [29]

    A highly adaptive distributed routing algorithm for mobile wire- less networks

    Vincent Douglas Park and M Scott Corson. “A highly adaptive distributed routing algorithm for mobile wire- less networks”. In:Proceedings of INFOCOM’97. V ol. 3. IEEE. 1997, pp. 1405–1413

    1997

  30. [30]

    Adam Paszke et al.PyTorch: An Imperative Style, High-Performance Deep Learning Library. 2019. arXiv: 1912.01703[cs.LG].URL: https://arxiv.org/abs/1912. 01703

    Pith/arXiv arXiv 2019

  31. [31]

    Ad-hoc on- demand distance vector routing

    Charles E Perkins and Elizabeth M Royer. “Ad-hoc on- demand distance vector routing”. In:Proceedings WM- CSA’99. Second IEEE Workshop on Mobile Computing Systems and Applications. IEEE. 1999, pp. 90–100

    1999

  32. [32]

    Monotonic value function factori- sation for deep multi-agent reinforcement learning

    Tabish Rashid et al. “Monotonic value function factori- sation for deep multi-agent reinforcement learning”. In: Journal of Machine Learning Research21.178 (2020), pp. 1–51

    2020

  33. [33]

    The graph neural network model

    Franco Scarselli et al. “The graph neural network model”. In:IEEE transactions on neural networks20.1 (2008), pp. 61–80

    2008

  34. [34]

    Position-based routing in ad hoc networks

    I. Stojmenovic. “Position-based routing in ad hoc networks”. In:IEEE Communications Magazine40.7 (2002), pp. 128–134.DOI: 10 . 1109 / MCOM . 2002 . 1018018

    2002

  35. [35]

    Value-Decomposition Networks For Cooperative Multi-Agent Learning Based On Team Reward

    Peter Sunehag et al. “Value-Decomposition Networks For Cooperative Multi-Agent Learning Based On Team Reward”. In:Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Sys- tems. AAMAS ’18. Stockholm, Sweden: International Foundation for Autonomous Agents and Multiagent Systems, 2018, pp. 2085–2087

    2018

  36. [36]

    Stability properties of constrained queueing systems and schedul- ing policies for maximum throughput in multihop radio networks

    Leandros Tassiulas and Anthony Ephremides. “Stability properties of constrained queueing systems and schedul- ing policies for maximum throughput in multihop radio networks”. In:29th IEEE Conference on Decision and Control. IEEE. 1990, pp. 2130–2132

    1990

  37. [37]

    Understanding over-squashing and bottlenecks on graphs via curvature

    Jake Topping et al. “Understanding over-squashing and bottlenecks on graphs via curvature”. In:International Conference on Learning Representations. 2022

    2022

  38. [38]

    Rayen: Imposition of hard convex constraints on neural networks

    Jesus Tordesillas, Jonathan P. How, and Marco Hutter. “Rayen: Imposition of hard convex constraints on neural networks”. In:arXiv preprint arXiv:2307.08336(2023)

    Pith/arXiv arXiv 2023

  39. [39]

    LinSATNet: the positive linear satisfiability neural networks

    Runzhong Wang et al. “LinSATNet: the positive linear satisfiability neural networks”. In:International Confer- ence on Machine Learning. PMLR. 2023, pp. 36605– 36625

    2023

  40. [40]

    On combining shortest-path and back- pressure routing over multihop wireless networks

    Lei Ying et al. “On combining shortest-path and back- pressure routing over multihop wireless networks”. In: IEEE/ACM Transactions on Networking19.3 (2010), pp. 841–854

    2010

  41. [41]

    Biased backpressure routing us- ing link features and graph neural networks

    Zhongyuan Zhao et al. “Biased backpressure routing us- ing link features and graph neural networks”. In:IEEE Transactions on Machine Learning in Communications and Networking(2024). 9 APPENDIX A. Proof of Theorem 1 We define anS−only routing algorithm to be any algorithm which determines link powerP(t)and transmit dataµ(t) independently ofQ(t). If such an...

    2024

  42. [42]

    Since the objective is strictly increasing inµ W ijc, this contradicts the optimality ofµ W i

    Assume that neither equality holds at some(j, c)∈E +, it is then possible to incrementµ W ijc by min   κij(P, S)− X c′ µW i,j,c′, Qi,c − X j′ µW i,j′,c    >0, while retaining feasibility. Since the objective is strictly increasing inµ W ijc, this contradicts the optimality ofµ W i . Proof of Theorem 2.Sinceγ, σ≥0, it can be seen thatµ W i is feasibl...

  43. [43]

    By Lemma 2, each element(j, c)∈E + saturates either the row or column constraint (or both) atM j,c

    First, we setµ ′ i,j,c =µ ∗ i,j,c for all(j, c)∈E +. By Lemma 2, each element(j, c)∈E + saturates either the row or column constraint (or both) atM j,c

  44. [44]

    We setM ij = 0for all elements where rowior column jis saturated

  45. [45]

    Its row/column sum constraints are corresponding subvectors ofT i, Ii

    LetM ′ be the residual submatrix obtained after remov- ing saturated rows and columns from M. Its row/column sum constraints are corresponding subvectors ofT i, Ii. Choose any feasibleM ′ that satisfies these targets (such anM ′ exists by the feasibility balance above). SinceMthen satisfies the row and column sum constraints, the corresponding values of(µ...

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.