Link Scheduling Using Graph Neural Networks

Zhongyuan Zhao, Gunjan Verma, Chirag Rao, Ananthram Swami, Santiago Segarra

TL;DR

This paper introduces a way to solve the notoriously difficult "link scheduling" problem in wireless networks using Graph Neural Networks (GNNs). By training GNNs via reinforcement learning to understand network topology, the authors created schedulers that are significantly more efficient than traditional greedy algorithms while remaining fast enough for real-time use in both centralized and distributed environments.

What Problem Does This Paper Address?

In a wireless multihop network, you can’t have every link transmitting at once; if two nearby links use the same frequency, they interfere, and data gets lost. Deciding which links should transmit at any given time to maximize total throughput is known as link scheduling.

Mathematically, this maps to the Maximum Weighted Independent Set (MWIS) problem. You represent links as nodes in a "conflict graph" and draw edges between links that interfere. Your goal is to pick a set of nodes (links) that aren't connected to each other (an "independent set") and have the highest combined weight (utility).

The catch? MWIS is NP-hard. Finding the perfect schedule takes exponentially longer as the network grows. Practical systems currently rely on "greedy" heuristics—basically picking the link with the highest weight and moving on. However, these greedy methods are "topology-blind"; they don't realize that picking one high-weight link might block ten other medium-weight links, leading to poor overall performance.

Methods

The authors propose two main GCN-based (Graph Convolutional Network) architectures:

  1. GCN-CRS (Centralized): This uses a GCN to guide a tree search. Instead of exploring every possible combination, the GCN predicts which nodes are most promising. It then uses a "1-step rollout"—looking one move ahead using a fast heuristic—to quickly find a near-optimal solution without the massive computational overhead of traditional search algorithms.
  2. GCN-LGS (Distributed): Designed for ad-hoc networks where there is no central controller. Here, each node uses a local GCN to generate a "topology-aware embedding" ($z$). The node multiplies its raw utility ($u$) by this factor to get a new weight ($w = z \cdot u$). This effectively "downscales" links that cause too much interference and "upscales" links in quiet areas. Nodes then run a standard Local Greedy Solver (LGS) using these smarter weights.

The Training Innovation: Because the greedy solvers used after the GCN are non-differentiable (you can't do standard backpropagation through a discrete "pick or don't pick" decision), the authors developed a custom Reinforcement Learning (RL) scheme. They used a deterministic policy gradient that rewards the GCN based on how much better its solution is compared to a standard greedy baseline.

Datasets

The researchers evaluated their models on:

  • Synthetic Random Graphs: Erdős-Rényi (ER) and Barabási-Albert (BA) models, ranging from 100 to 300 nodes with varying densities.
  • Wireless Simulations: Simulated multihop networks with 100 users randomly placed in a square area, featuring realistic effects like Poisson traffic arrivals, fading, and lognormal shadowing.

Key Insights and Ideas

  • Topology is a Force Multiplier: A link’s value isn't just its data rate; it's its location. The GCN learns to identify "bottleneck" nodes that, if activated, would silence too many neighbors.
  • Shallow is Better: Surprisingly, a 1-layer GCN was often sufficient for the distributed solver. This is great for hardware implementation because it keeps communication overhead (the number of "hops" nodes must talk to neighbors) very low.
  • Generalization is Key: Models trained on small, simple random graphs (ER) performed remarkably well when tested on larger, more complex "scale-free" graphs (BA) and realistic wireless topologies. This suggests the GCN is learning fundamental geometric properties of interference.

Key Results

  • Closing the Gap: The distributed GCN-LGS reduced the "suboptimality gap" (the distance from the perfect theoretical solution) of standard greedy solvers by nearly 50%.
  • Speed vs. Quality: The centralized GCN-CRS reached near-optimal solutions (approximation ratios > 0.98) orders of magnitude faster than previous GNN-based tree search methods.
  • Network Stability: In throughput-optimal scheduling simulations, the GCN-based approach significantly reduced average queue lengths (backlog) compared to traditional baselines, especially as the network approached saturation.

Limitations and Future Work

While powerful, the approach assumes the conflict graph is known or can be accurately estimated. In highly dynamic environments with rapid mobility, maintaining an accurate conflict graph adds overhead.

The authors suggest several paths forward:

  1. Non-orthogonal channels: Moving beyond simple "on/off" scheduling to handle overlapping signals.
  2. Online Learning: Developing schemes where the GCN can continue to learn and adapt to real-world network conditions after deployment.
  3. Causal Modeling: Better accounting for how a scheduling decision in one time slot affects the network state in the next.

Summary updated

Abstract

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.
BibTeX
@article{zhao2023link,
  author = {Zhongyuan Zhao and Gunjan Verma and Chirag Rao and Ananthram Swami and Santiago Segarra},
  title = {{Link Scheduling Using Graph Neural Networks}},
  journal = {IEEE Trans. Wireless Communications},
  year = {2023},
  url = {https://openreview.net/forum?id=CNyRHT5cWe},
}

Loading related content...

Figure