# Link Scheduling using Graph Neural Networks

arXiv: https://arxiv.org/abs/2109.05536 · HTML: https://mlsanity.com/paper/2109.05536/

## 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 (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Deep Learning in Mobile and Wireless Networking: A Survey](https://mlsanity.com/paper/1803.04311/) (2018)
- [Convolutional Neural Network Architectures for Signals Supported on Graphs](https://mlsanity.com/paper/1805.00165/) (2018)
- [Optimal Wireless Resource Allocation with Random Edge Graph Neural Networks](https://mlsanity.com/paper/1909.01865/) (2019)
- [Multi-Agent Deep Reinforcement Learning for Dynamic Power Allocation in Wireless Networks](https://mlsanity.com/paper/1808.00490/) (2018)
- [Unfolding WMMSE using Graph Neural Networks for Efficient Power Allocation](https://mlsanity.com/paper/2009.10812/) (2020)
- [Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP](https://mlsanity.com/paper/1809.02721/) (2018)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [HodgeNet: Graph Neural Networks for Edge Data](https://mlsanity.com/paper/1912.02354/) (2019)
- [Deep Reinforcement Learning for Dynamic Multichannel Access in Wireless Networks](https://mlsanity.com/paper/1802.06958/) (2018)
- [Spatial Deep Learning for Wireless Scheduling](https://mlsanity.com/paper/1808.01486/) (2018)
- [Distributed Scheduling using Graph Neural Networks](https://mlsanity.com/paper/2011.09430/) (2020)
- [Learning Heuristics over Large Graphs via Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03332/) (2019)
- [Scheduling Policies for Minimizing Age of Information in Broadcast Wireless Networks](https://mlsanity.com/paper/1801.01803/) (2018)
- [Adaptive Contention Window Design using Deep Q-learning](https://mlsanity.com/paper/2011.09418/) (2020)
- [The Internet of Battle Things](https://mlsanity.com/paper/1712.08980/) (2017)
- [Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs](https://mlsanity.com/paper/1810.10834/) (2018)
- [Energy-Efficient Subchannel and Power Allocation for HetNets Based on Convolutional Neural Network](https://mlsanity.com/paper/1903.00165/) (2019)
- [Enhancing Geometric Deep Learning via Graph Filter Deconvolution](https://mlsanity.com/paper/1810.00661/) (2018)

## Built on by (most cited first, 26 of 26)

- [Learning Resilient Radio Resource Management Policies with Graph Neural Networks](https://mlsanity.com/paper/2203.11012/) (2022)
- [State-Augmented Learnable Algorithms for Resource Management in Wireless Networks](https://mlsanity.com/paper/2207.02242/) (2022)
- [Scalable Implicit Graphon Learning](https://mlsanity.com/paper/2410.17464/) (2024)
- [Deep Graph Unfolding for Beamforming in MU-MIMO Interference Networks](https://mlsanity.com/paper/2304.00446/) (2023)
- [Distributed Link Sparsification for Scalable Scheduling Using Graph Neural Networks](https://mlsanity.com/paper/2203.14339/) (2022)
- [Delay-aware Backpressure Routing Using Graph Neural Networks](https://mlsanity.com/paper/2211.10748/) (2022)
- [Learning to Transmit with Provable Guarantees in Wireless Federated Learning](https://mlsanity.com/paper/2304.09329/) (2023)
- [Congestion-aware Distributed Task Offloading in Wireless Multi-hop Networks Using Graph Neural Networks](https://mlsanity.com/paper/2312.02471/) (2023)
- [GraSSRep: Graph-Based Self-Supervised Learning for Repeat Detection in Metagenomic Assembly](https://mlsanity.com/paper/2402.09381/) (2024)
- [Fully Distributed Online Training of Graph Neural Networks in Networked Systems](https://mlsanity.com/paper/2412.06105/) (2024)
- [Fast State-Augmented Learning for Wireless Resource Allocation with Dual Variable Regression](https://mlsanity.com/paper/2506.18748/) (2025)
- [Graph Neural Networks over the Air for Decentralized Tasks in Wireless Networks](https://mlsanity.com/paper/2302.08447/) (2023)
- [Biased Backpressure Routing Using Link Features and Graph Neural Networks](https://mlsanity.com/paper/2407.09753/) (2024)
- [Graph Neural Networks for Edge Signals: Orientation Equivariance and Invariance](https://mlsanity.com/paper/2410.16935/) (2024)
- [Generative Diffusion Models of Stochastic Graph Signals](https://mlsanity.com/paper/2607.06833/) (2026)
- [Robust MIMO Detection using Hypernetworks with Learned Regularizers](https://mlsanity.com/paper/2110.07053/) (2021)
- [A State-Augmented Approach for Learning Optimal Resource Management Decisions in Wireless Networks](https://mlsanity.com/paper/2210.16412/) (2022)
- [Graph Neural Networks for Physical-Layer Security in Multi-User Flexible-Duplex Networks](https://mlsanity.com/paper/2402.05378/) (2024)
- [Model-Driven Graph Contrastive Learning](https://mlsanity.com/paper/2506.06212/) (2025)
- [Distributed Link Sparsification for Scalable Scheduling Using Graph Neural Networks (Journal Version)](https://mlsanity.com/paper/2509.05447/) (2025)
- [From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learning](https://mlsanity.com/paper/2510.03690/) (2025)
- [MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment](https://mlsanity.com/paper/2511.09324/) (2025)
- [A Differentiable Digital Twin of Distributed Link Scheduling for Contention-Aware Networking](https://mlsanity.com/paper/2512.10874/) (2025)
- [Limit Analysis of Graph Neural Networks with Wireless Conflict Graphs](https://mlsanity.com/paper/2606.03794/) (2026)
- [Congruence Decomposition with Neural Block Solvers for Large-Scale PCI Assignment](https://mlsanity.com/paper/2608.21485/) (2026)
- [MANET-GNN: Learned Decentralized Optimization of Power Allocation in Multi-Channel MANETs](https://mlsanity.com/paper/2609.40170/) (2026)

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