mlsanityData to 14 Oct 2026

Link Scheduling using Graph Neural Networks

arXiv 2109.05536 ↗First posted 12 Sep 2021eess.SP cs.LGcited by 26

Not on the map. Why?

Abstract (arXiv)

Efficient scheduling of transmissions is a key problem in wireless networks. The main challenge stems from the fact that optimal link scheduling involves solving a maximum weighted independent set (MWIS) problem, which is known to be NP-hard. In practical schedulers, centralized and distributed greedy heuristics are commonly used to approximately solve the MWIS problem. However, most of these greedy heuristics ignore important topological information of the wireless network. To overcome this limitation, we propose fast heuristics based on graph convolutional networks (GCNs) that can be implemented in centralized and distributed manners. Our centralized heuristic is based on tree search guided by a GCN and 1-step rollout. In our distributed MWIS solver, a GCN generates topology-aware node embeddings that are combined with per-link utilities before invoking a distributed greedy solver. Moreover, a novel reinforcement learning scheme is developed to train the GCN in a non-differentiable pipeline. Test results on medium-sized wireless networks show that our centralized heuristic can reach a near-optimal solution quickly, and our distributed heuristic based on a shallow GCN can reduce by nearly half the suboptimality gap of the distributed greedy solver with minimal increase in complexity. The proposed schedulers also exhibit good generalizability across graph and weight distributions.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). Builds on 27 of its 84 references that are in the map. First posted on arXiv 12 Sep 2021.

Builds on

27 of 84 references.

References · 27

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  3. 2018Relational inductive biases, deep learning, and graph networkscited by 1,360
  4. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  5. 2019Differentiation of Blackbox Combinatorial Solverscited by 226
  6. 2013Ising formulations of many NP problemscited by 207
  7. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 200
  8. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 183
  9. 2020A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learningcited by 162
  10. 2018Deep Learning in Mobile and Wireless Networking: A Surveycited by 118
  11. 2018Convolutional Neural Network Architectures for Signals Supported on Graphscited by 95
  12. 2019Optimal Wireless Resource Allocation with Random Edge Graph Neural Networkscited by 90
15 more
  1. 2018Multi-Agent Deep Reinforcement Learning for Dynamic Power Allocation in Wireless Networkscited by 70
  2. 2020Unfolding WMMSE using Graph Neural Networks for Efficient Power Allocationcited by 61
  3. 2018Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSPcited by 58
  4. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  5. 2019HodgeNet: Graph Neural Networks for Edge Datacited by 39
  6. 2018Deep Reinforcement Learning for Dynamic Multichannel Access in Wireless Networkscited by 37
  7. 2018Spatial Deep Learning for Wireless Schedulingcited by 32
  8. 2020Distributed Scheduling using Graph Neural Networkscited by 27
  9. 2019Learning Heuristics over Large Graphs via Deep Reinforcement Learningcited by 23
  10. 2018Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networkscited by 22
  11. 2020Adaptive Contention Window Design using Deep Q-learningcited by 13
  12. 2017The Internet of Battle Thingscited by 11
  13. 2018Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphscited by 9
  14. 2019Energy-Efficient Subchannel and Power Allocation for HetNets Based on Convolutional Neural Networkcited by 5
  15. 2018Enhancing Geometric Deep Learning via Graph Filter Deconvolutioncited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 4; 2024: 6; 2025: 6; 2026: 4.

26 papers.

Sort:

By area:

  1. 2022Learning Resilient Radio Resource Management Policies with Graph Neural Networkscited by 17
  2. 2022State-Augmented Learnable Algorithms for Resource Management in Wireless Networkscited by 14
  3. 2024Scalable Implicit Graphon Learningcited by 9
  4. 2023Deep Graph Unfolding for Beamforming in MU-MIMO Interference Networkscited by 6
  5. 2022Distributed Link Sparsification for Scalable Scheduling Using Graph Neural Networkscited by 4
  6. 2022Delay-aware Backpressure Routing Using Graph Neural Networkscited by 3
  7. 2023Learning to Transmit with Provable Guarantees in Wireless Federated Learningcited by 3
  8. 2023Congestion-aware Distributed Task Offloading in Wireless Multi-hop Networks Using Graph Neural Networkscited by 3
  9. 2024GraSSRep: Graph-Based Self-Supervised Learning for Repeat Detection in Metagenomic Assemblycited by 3
  10. 2024Fully Distributed Online Training of Graph Neural Networks in Networked Systemscited by 3
  11. 2025Fast State-Augmented Learning for Wireless Resource Allocation with Dual Variable Regressioncited by 3
  12. 2023Graph Neural Networks over the Air for Decentralized Tasks in Wireless Networkscited by 2
14 more
  1. 2024Biased Backpressure Routing Using Link Features and Graph Neural Networkscited by 2
  2. 2024Graph Neural Networks for Edge Signals: Orientation Equivariance and Invariancecited by 2
  3. 2026Generative Diffusion Models of Stochastic Graph Signalscited by 2
  4. 2021Robust MIMO Detection using Hypernetworks with Learned Regularizerscited by 0
  5. 2022A State-Augmented Approach for Learning Optimal Resource Management Decisions in Wireless Networkscited by 0
  6. 2024Graph Neural Networks for Physical-Layer Security in Multi-User Flexible-Duplex Networkscited by 0
  7. 2025Model-Driven Graph Contrastive Learningcited by 0
  8. 2025Distributed Link Sparsification for Scalable Scheduling Using Graph Neural Networks (Journal Version)cited by 0
  9. 2025From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learningcited by 0
  10. 2025MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environmentcited by 0
  11. 2025A Differentiable Digital Twin of Distributed Link Scheduling for Contention-Aware Networkingcited by 0
  12. 2026Limit Analysis of Graph Neural Networks with Wireless Conflict Graphscited by 0
  13. 2026Congruence Decomposition with Neural Block Solvers for Large-Scale PCI Assignmentcited by 0
  14. 2026MANET-GNN: Learned Decentralized Optimization of Power Allocation in Multi-Channel MANETscited by 0