Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks

Technical Summary: Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks

Problem Formulation
The paper addresses the problem of optimal link scheduling in large-scale device-to-device wireless networks. The objective is to maximize the long-term average sum rate over a time horizon $T$ while ensuring that every link $i$ achieves a minimum average rate requirement $\Delta_i$. Unlike traditional approaches that focus on maximizing instantaneous sum rates, this problem requires time-varying policies to satisfy temporal constraints and avoid interference.

The network is modeled under a primary interference model, where two links interfere if they share a common device. This is represented by a conflict graph $G(V, E)$ with adjacency matrix $A$. The scheduling problem is formulated as a constrained combinatorial optimization problem (Equation 3) where the decision variables are binary vectors $s(t) \in \{0, 1\}^K$ for each time slot $t$. The total search space is combinatorial in the product of the number of links $K$ and the time horizon $T$, making exact solutions computationally intractable for large-scale networks.

Methodology
The authors propose a learning-based approach grounded in Lagrangian duality and state augmentation. The methodology proceeds in three main theoretical and practical steps:

1. Dual Domain Analysis and Primal Infeasibility:
   The authors first analyze the problem using the Lagrangian dual. They demonstrate that the Lagrangian maximizers for a fixed dual variable $\lambda$ are time-invariant (Proposition 1). That is, the optimal schedule $s^\dagger(t, \lambda)$ does not change over time. Consequently, a static policy derived from a single optimal dual variable cannot satisfy the minimum rate requirements for all links simultaneously, as it fails to alternate transmissions to avoid interference. This renders the standard primal-dual approach of finding a single optimal $\lambda^\star$ and a corresponding static schedule insufficient for the long-horizon problem.

2. Dual Gradient Descent Dynamics:
   To overcome the time-invariance limitation, the paper investigates dual gradient descent dynamics. By iteratively updating the dual variable $\lambda(u)$ based on constraint violations (subgradients) and computing the corresponding Lagrangian maximizer $s^\ddagger(u)$ at each step, the algorithm generates a sequence of schedules. Theoretical analysis (Proposition 3) shows that while individual schedules in this sequence may not be optimal, the average rate of the sequence $s^\ddagger(1:T)$ is asymptotically optimal and feasible as $T \to \infty$. This suggests that the solution to the long-horizon problem lies in learning a policy that mimics the trajectory of dual gradient descent.

3. State-Augmented Graph Neural Networks (SAGNN):
   To implement this efficiently without solving the NP-hard Lagrangian maximization at every step, the authors propose a parametric policy $\Phi(A, \lambda; H)$ using a Graph Neural Network (GNN).

   • State Augmentation: The key innovation is treating the dual variable $\lambda(t)$ as an internal state (or input signal) to the GNN, alongside the network topology $A$. This allows the policy to adapt scheduling decisions dynamically based on the current level of constraint violation.
   • Training (Offline): The GNN parameters $H$ are trained offline to maximize the instantaneous Lagrangian $M(s, \lambda)$ over a distribution of network topologies and dual variables. The loss function penalizes constraint violations weighted by the sampled $\lambda$.
   • Execution (Online): During execution, the trained GNN generates a schedule $s(t)$ based on the current network state $A$ and the current dual variable $\lambda(t)$. The dual variable is then updated online using the subgradient of the constraint violation (Equation 21), creating a closed-loop system that mimics the dual gradient descent dynamics.

Key Contributions

• Theoretical Insight: The paper establishes that while optimal Lagrangian maximizers are time-invariant and thus infeasible for the constrained long-horizon problem, the sequence of maximizers generated by dual gradient descent yields asymptotically optimal average rates.
• Algorithm Design: The authors introduce a State-Augmented GNN (SAGNN) that learns to approximate the Lagrangian maximizers. By incorporating dual variables as dynamic inputs, the policy learns to vary scheduling decisions over time, effectively balancing constraint satisfaction and performance maximization.
• Scalability: The approach decouples the complexity of the time horizon $T$ from the learning parameterization. The GNN learns a mapping for a single time step, avoiding the need to learn a sequence of length $T$ directly, which would be computationally prohibitive.

Results
Extensive numerical simulations were conducted on Random Geometric Graphs (RGGs) with approximately 500 links.

• Constraint Satisfaction: The proposed algorithm successfully satisfies minimum rate constraints for the vast majority of links. For the few under-scheduled links, the constraint violations are minor.
• Performance: The method outperforms several baseline heuristics in terms of average sum rate and achieves faster runtime.
• Generalization: The learned policy demonstrates robustness, generalizing across different transmission requirements and adapting effectively over time. The policy successfully alternates between non-interfering links, prioritizing those with higher constraint violation levels as the dual variables evolve.

Significance and Claims
The paper claims that its primary significance lies in bridging the gap between the theoretical optimality of dual gradient descent and the practical need for efficient, learning-based scheduling policies. It argues that state augmentation is a necessary technique to enable GNNs to learn time-varying policies required for long-horizon constraints, a task that standard time-invariant policies or direct sequence learning (which is too expensive) cannot effectively solve. The work validates that learning to mimic dual dynamics allows for the solution of high-dimensional, constrained combinatorial problems in wireless networks with computational efficiency.