Wireless Link Scheduling with Graph Signal Diffusion

arXiv:2611.08274 · eess.SP · Submitted 2026-11-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Electrical Engineering. The day in electrical engineering: signals, systems and the hardware that carries them.

Rosa: We're looking at the paper: "Wireless Link Scheduling with Graph Signal Diffusion".

Dev: Here's the gist of the paper. We solve long-horizon wireless link scheduling with per-link minimum transmission constraints via a diffusion framework to achieve near-optimal performance by sampling scheduling decisions conditioned on the network topology and constraint levels.

Rosa: Problem Formulation and Expert Dynamics The problem involves determining the active subset of links in a time-shared channel to minimize interference while satisfying per-link minimum transmission requirements.

Dev: The network is represented by a conflict graph where edges join conflicting links, and successful transmissions correspond to independent sets in this graph.

Rosa: An optimal policy seeks to maximize the expected sum throughput while satisfying minimum transmission requirements over all distributions on the state space (A, δ).

Title and authors: Rosa: Let's talk about the title and who did this. It’s "Wireless Link Scheduling with Graph Signal Diffusion," written by Teresa Shang, Romina Garcia Camargo, Yigit Berkay Uslu, and Alejandro Ribeiro from the University of Pennsylvania.

Dev: They set up a diffusion framework specifically for long-horizon wireless link scheduling with per-link minimum transmission constraints. It’s about finding a good balance between serving everyone fairly and getting the best overall performance.

Taro: For me, what's interesting is that they are using this graph signal diffusion thing to handle the complexity of how links interact on a network over many time steps at once.

Rosa: Exactly. The U-Graph Neural Network, or U-GNN, is their specific tool for parameterizing this process. It’s essentially a specialized encoder and decoder that works on graphs, which they adapt from power control to link scheduling decisions.

Dev: That U-GNN acts as the engine for generating these schedules offline. It’s what lets them learn the relationship between the graph structure of the network and the actual transmission decisions made by each link.

The paper's summary: Rosa: So, to summarize what they did, they train this diffusion model to imitate a dual gradient descent expert. This means it learns how an optimal policy would behave by sampling schedules that are conditioned on the network topology and those specific constraint levels you give it.

Dev: They use the U-GNN as their parameterization method because it lets them leverage the relationship between graphs and wireless networks effectively for learning these scheduling decisions.

Taro: So, when they generate these schedules, they’re not just picking random links; they are generating a distribution of schedules that tries to maximize throughput while respecting those minimum transmission rates.

Rosa: That's right. The goal is to find this optimal policy that maximizes the expected sum rate over all possible distributions on the network state, which involves satisfying those minimum transmission requirements for every link across all time steps.

Dev: They show that this approach achieves near-optimal performance by sampling these scheduling decisions, and they demonstrate how robust it is when dealing with different network topologies and constraint levels than what they trained on.

The paper's improvements: Rosa: One of the key improvements they highlight is that the U-GNN based diffusion model generalizes really well to requirements and network sizes that were totally unseen during their training process. It shows this robustness when you test it with different constraint levels and different network sizes.

Dev: That generalization capability is important because it means you don't have to retrain the whole thing every time you change the problem setup slightly, which is a big deal for practical applications where things keep changing.

Taro: I like what they say about fairness here. They claim that this U-GNN can sample schedules that combine high throughput with strong fairness performance across different constraint levels without needing to look back at past schedules or signals from the dual dynamics when it's actually making a decision.

Rosa: That’s because the diffusion process, guided by the U-GNN, captures how those expert dual dynamics induce scheduling opportunities. It's not just guessing; it’s sampling based on that learned behavior.

Dev: And from an engineering standpoint, they also found that this method is faster than the expert method at every evaluated network size. They generate ten schedules at a time for a total of one hundred time steps, which is quite efficient when you compare it to other methods like the SAGNN.

Conclusion: Rosa: So, wrapping up on "Wireless Link Scheduling with Graph Signal Diffusion," the main point is that this learned scheduling distribution captures how expert dual dynamics allocate transmission opportunities and can deliver near-optimal performance while handling varying constraints.

Dev: It supports learning these distributions as an effective way to handle long-horizon resource allocation problems in wireless networks. The U-GNN provides a powerful parameterization for this diffusion process, making it adaptable to different network structures.

Taro: I just think the robustness across different constraint levels and network sizes is what really matters here, because if it breaks when you introduce a new kind of requirement, it’s not very useful for real-world deployment.

Rosa: And that's the point about generalization—it holds up even when requirements are something you haven't seen before. It shows the learned structure is more important than just memorizing past data points.

Dev: We need to keep pushing on how these models handle those failure modes when the world misbehaves, so we can build in stronger safety cases for these kinds of complex scheduling decisions.

Taro: Yeah, I think that’s where the next steps should be—looking at how this system recovers when things go sideways in a dynamic environment.

Teresa Shang, Romina Garcia Camargo, Yigit Berkay Uslu, Alejandro Ribeiro

University of Pennsylvania

eess.SP

Submitted: 2026-11-05

Updated: 2026-11-05

Code: https://github.com/tshang21/graph_diffusion_link_schedulin

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 85/100

The gist: We solve long-horizon wireless link scheduling with per-link minimum transmission constraints via a diffusion framework to achieve near-optimal performance by sampling scheduling decisions…

Key concepts

Diffusion Model for Stochastic Scheduling Policies
A diffusion model is trained to generate scheduling decisions by imitating a dual gradient descent expert. This allows the system to produce stochastic signals that respect both the network structure (topology) and the minimum transmission requirements, effectively learning how to allocate resources over time.
U-Graph Neural Network (U-GNN)
The U-GNN acts as an encoder-decoder architecture specifically adapted for link scheduling. It uses graph signals to process the communication network's conflict graph, enabling the model to generate scheduling decisions offline and parameterize the diffusion process effectively.
Generalization Across Constraints and Network Sizes
The learned policy is robust; it can sample schedules that satisfy high throughput and fairness across various minimum transmission requirements not seen during training. Furthermore, the model maintains performance on unseen network sizes (up to 5000 links), demonstrating strong transferability.
DDIM Sampler for Inference
During inference, a deterministic DDIM sampler is used to draw clean scheduling samples from the noisy data generated by the diffusion process. This process allows for efficient estimation of the actual resource allocation decisions at runtime.

Terminology

Summary

We solve long-horizon wireless link scheduling with per-link minimum transmission constraints via a diffusion framework to achieve near-optimal performance by sampling scheduling decisions conditioned on the network topology and constraint levels. p. 0

Where the paper says it

of Electrical and Systems Engineering University of Pennsylvania Philadelphia, PA, USA ABSTRACT We solve long-horizon wireless link scheduling with per-link minimum transmission constraints. Fair distribution of resources across links and time steps requires stochastic scheduling, motivating a diffusion framework.

Problem Formulation and Expert Dynamics

The problem involves determining the active subset of links in a time-shared channel to minimize interference while satisfying per-link minimum transmission requirements. The network is represented by a conflict graph where edges join conflicting links, and successful transmissions correspond to independent sets in this graph. p. 0

Where the paper says it

Under the primary interference model [7, 20], two links conflict if they share a common device. We represent these conflicts by a conflict graph whose nodes are the links and whose edges join conflicting links.

An optimal policy seeks to maximize the expected sum throughput while satisfying minimum transmission requirements over all distributions on the state space (A, δ). p. 1
Where the paper says it

Throughout, we omit the conditioning on (A, δ) when clear from context. An optimal policy D ⋆ x maximizes the expected sum throughput in (1) while satisfying the minimum transmission requirements over all distributions on {0, 1} N : D ⋆ x ∈ argmax Dx EDx 1 ⊤ N r(x, A) subject to EDx r(x, A) ≥ δ.

Diffusion Model Training and Parameterization

The stochastic scheduling policy is parameterized as a conditional diffusion model trained to imitate a dual gradient descent expert. This parameterization is achieved through a U-Graph Neural Network (U-GNN) which acts as a GNN-based encoder–decoder architecture adapted from power control to link scheduling. p. 0

Where the paper says it

In the dual gradient descent expert, the multipliers act as adaptive link weights that time-share the channel among links. Parameterizing the diffusion model with a U-Graph Neural Network (U-GNN) [17], a GNN-based encoder–decoder architecture that we adapt from power control to link scheduling, we generate scheduling decisions offline as graph signals over the communication network’s conflict graph [18].

The model generates scheduling decisions offline as graph signals over the communication network’s conflict graph. p. 0
Where the paper says it

In the dual gradient descent expert, the multipliers act as adaptive link weights that time-share the channel among links. Parameterizing the diffusion model with a U-Graph Neural Network (U-GNN) [17], a GNN-based encoder–decoder architecture that we adapt from power control to link scheduling, we generate scheduling decisions offline as graph signals over the communication network’s conflict graph [18].

Inference and Generalization Capabilities

The diffusion process corrupts an expert schedule with Gaussian noise over M steps, and a noise predictor is trained to undo this corruption by removing the noise from the noisy signal and network state. At inference, samples are drawn by running a deterministic DDIM sampler to estimate the clean sample at each step. p. 1

Where the paper says it

At inference, we sample from the trained model by drawing zM ∼ N (0, IN ) and running a deterministic DDIM sampler [22]. Specifically, we estimate the clean sample at each step m as zˆ0 = zm − √ 1 − α¯m ϵθ⋆ (zm, m; A, δ) √ α¯m , (11) and use this estimate to obtain the next iterate as zm−1 = √ α¯m−1 zˆ0 + p 1 − α¯m−1 ϵθ⋆ (zm, m; A, δ), (12) for m = M, .

The U-GNN-based diffusion model generalizes to requirements and network sizes unseen during training, demonstrating robustness. p. 0
Where the paper says it

Our approach achieves near-optimal performance, maximizing sum rate while distributing allocations across different links over time horizons. The U-GNN-based diffusion model generalizes to requirements and network sizes unseen during training, demonstrating the robustness of the approach.

Performance and Scalability Results

The proposed diffusion-based policies generate stochastic scheduling decisions with near-optimal performance, outperforming existing methods. The U-GNN keeps the average fraction of links violating their minimum transmission requirement below 1% at all evaluated thresholds up to δ = 0. p. 3

Where the paper says it

The lower tails shift towards higher transmission rates, reflecting the stricter requirements for links that transmit infrequently. As shown in Table 1, the U-GNN keeps the average fraction of links violating their minimum transmission requirement below 1% at all evaluated thresholds up to δ = 0.

10, including thresholds not seen during training. p. 3
Where the paper says it

As shown in Table 1, the U-GNN keeps the average fraction of links violating their minimum transmission requirement below 1% at all evaluated thresholds up to δ = 0. 10, including thresholds not seen during training.

Furthermore, diffusion-based link scheduling policies transfer their performance without retraining to networks with up to 5000 links while remaining faster than the expert at every evaluated size. p. 0
Where the paper says it

Moreover, GNN parameterizations inherit structural properties such as scalability and transferability [17, 19], enabling transfer across network sizes. Trained on networks with 500 links, diffusion-based link scheduling policies transfer their performance without retraining to networks with up to 5000 links, while remaining faster than the expert at every evaluated size (Section 4.

Conclusion and Future Directions

The work demonstrates that a learned scheduling distribution can capture the allocation of transmission opportunities induced by expert dual dynamics. This approach supports learning scheduling distributions as an effective method for long-horizon resource allocation. p. 3

Where the paper says it

Stochastic sampling from this distribution achieves a near-optimal long-horizon transmission objective with few minimum constraint violations. These findings support learning scheduling distributions as an effective approach to longhorizon resource allocation.

Future research could consider diverse minimum transmission requirements across links instead of uniform thresholds and explore smaller architectures to match the runtime of Graph Neural Network approaches. p. 3
Where the paper says it

An interesting future direction considers diverse minimum transmission requirements across links instead of uniform thresholds. Moreover, while the per-schedule inference time remains low, a smaller architecture may enable matching the runtime of Graph Neural Network approaches with performance trade-offs.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Diffusion model for stochastic scheduling policies: The system can sample scheduling decisions by training a diffusion model to imitate a dual gradient descent expert, allowing it to generate stochastic signals conditioned on network topology and minimum transmission requirements.

  2. U-Graph Neural Network parameterization: The use of a U-GNN as the noise predictor allows the model to parameterize the diffusion process with graph signals, enabling it to learn from and generalize based on conflict graphs.

  3. Generalization across constraints and network sizes: The approach demonstrates that U-GNN can sample schedules that combine high throughput with strong fairness performance across different constraint levels, without access to past schedules or signals from dual dynamics at inference. This means the system maintains near-optimal performance even when requirements are not seen during training and on unseen network sizes.

  4. Robustness against network scale: The model achieves transferability across network sizes, as U-GNN generates 10 schedules at a time, for a total of T = 100 steps while maintaining performance across graphs with up to 500 links, showing that training on larger graphs improves metrics across all scales.

  5. Improved inference speed: The U-GNN model requires less inference time per schedule than DGD at every evaluated graph size, offering a favorable balance among inference speed and constraint satisfaction compared to other approaches like SAGNN.

Abstract

We solve long-horizon wireless link scheduling with per-link minimum transmission constraints. Fair distribution of resources across links and time steps requires stochastic scheduling, motivating a diffusion framework. Via imitation learning, we train a diffusion model to sample scheduling decisions, conditioning generation on the network topology and constraint levels. The parameterization is achieved through a U-Graph Neural Network (U-GNN) to leverage the relationship between graphs and wireless networks for learning. Our approach achieves near-optimal performance, maximizing sum rate while distributing allocations across different links over time horizons. The U-GNN-based diffusion model generalizes to requirements and network sizes unseen during training, demonstrating the robustness of the approach.

Sources

Related papers