PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Wireless Resource Allocation with Random Edge Graph Neural Networks

Mark Eisen, Alejandro Ribeiro

arXiv:1909.01865v4eess.SP

TL;DR

Wireless resource allocation is difficult because constrained, non-convex problems must operate over large networks with randomly varying channels. The paper introduces REGNNs, trains them with an unsupervised model-free primal-dual method, and reports strong performance relative to heuristics together with transfer across network sizes and topologies.

  • Problem

    Large-scale wireless resource allocation involves constrained, generally non-convex optimization, while scalable policies must handle varying network realizations.

  • Method

    REGNNs parameterize allocation policies by applying graph convolutions to random fading-interference graphs, with weights trained using an unsupervised model-free primal-dual algorithm.

  • Results

    REGNNs substantially outperform heuristic baselines in the reported simulations, including WMMSE in larger and higher-SNR settings, while using 40 parameters in the cited experiment.

  • Takeaways & Limitations

    Permutation equivariance and node-count-independent parameters enable REGNN policies trained on moderate networks to transfer to different networks and execute on systems with hundreds of nodes.

Abstract

from arXiv · show

We consider the problem of optimally allocating resources across a set of transmitters and receivers in a wireless network. The resulting optimization problem takes the form of constrained statistical learning, in which solutions can be found in a model-free manner by parameterizing the resource allocation policy. Convolutional neural networks architectures are an attractive option for parameterization, as their dimensionality is small and does not scale with network size. We introduce the random edge graph neural network (REGNN), which performs convolutions over random graphs formed by the fading interference patterns in the wireless network. The REGNN-based allocation policies are shown to retain an important permutation equivariance property that makes them amenable to transference to different networks. We further present an unsupervised model-free primal-dual learning algorithm to train the weights of the REGNN. Through numerical simulations, we demonstrate the strong performance REGNNs obtain relative to heuristic benchmarks and their transference capabilities.

I. INTRODUCTION

Wireless resource allocation is a constrained, generally intractable optimization problem whose scale motivates model-free statistical learning and scalable graph-based policies. The paper introduces REGNNs, establishes permutation-based transfer properties, and trains them with an unsupervised primal-dual method.

  • Large wireless resource allocation balances utilities and constraints over randomly varying channels, but the resulting problems are generally non-convex and intractable.
  • Supervised neural policies depend on heuristic solutions and therefore are limited by heuristic availability and suboptimality.
  • REGNN filters and learned policies have permutation invariance or equivariance properties that support transfer across permuted or sufficiently similar network topologies.
  • Experiments train REGNNs on networks with a few tens of nodes and execute them with good performance on networks containing hundreds of nodes.
  • REGNNs parameterize allocation policies using random fading links as graph edges, extending convolutional architectures with dimensionality that scales independently of network size.
  • An unsupervised, model-free primal-dual algorithm trains REGNN weights without requiring explicit knowledge of the system model.

A. Examples

The formulation covers wireless resource-allocation examples involving interference-limited capacity, user demand, fairness, and wireless control. These examples combine fading channels with node states and long-term utility objectives or constraints.

  • Multiple access AWGN channel: In multiple-access AWGN channels, capacity depends on transmission powers, channel states, noise, and multiuser interference.
  • Multiple access AWGN channel: Power constraints and utility choices can express objectives such as sum-rate maximization or minimum average capacity for fairness.
  • Multiple access with user demand: User-demand formulations use node states for information-generation or data-arrival rates and constrain average capacity to exceed target collection rates.
  • Multiple access with user demand: Fairness formulations use node states representing users’ achieved lifetime rates to construct weighted sum-rate objectives.
  • Random access wireless control systems: Wireless control systems model random access, packet collisions, plant states, and stable or unstable state evolution through channel-dependent transmission outcomes.

III. RANDOM EDGE GRAPH NEURAL NETWORKS

REGNNs treat fading-channel matrices as random graph shift operators and process node states through graph-filter layers with pointwise nonlinearities. Their architecture captures multi-hop interference structure while preserving permutation equivariance and compact parameterization.

  • REGNNs reinterpret node states as graph signals and the fading channel matrix as an adjacency representation linking transmitters to receivers associated with nodes.
  • Graph filters combine powers of the graph shift, so each filter tap aggregates information from a corresponding multi-hop neighborhood.
  • A REGNN composes graph-filter operations with pointwise nonlinearities across multiple layers and feature channels.
  • The random graph H is an input to the REGNN operator, with edge weights given by fading realizations and self-loops included.
  • With layer, feature, and filter dimensions fixed, the parameter count is independent of the number of network nodes and is much smaller than for fully connected networks.
  • Graph-filter equivariance aligns with the optimal allocation policy’s permutation structure, supporting transfer across permuted network realizations.

IV. PERMUTATION INVARIANCE AND EQUIVARIANCE

REGNNs can be executed on networks with different dimensions, shapes, and state distributions because their filter tensors are reused across graphs. Under permutation-related assumptions, optimal REGNN filters are invariant to network permutations, enabling transfer without loss of optimality.

  • Transference: A trained GNN can be executed on networks independently of their dimension or shape, including networks drawn from a different distribution.The same filter tensors are applied after substituting graphs and states from the new distribution.
  • Permutation transformations: Permutation matrices reorder vector entries and matrix rows and columns, providing the transformation used to compare network distributions.The transformed network and states are defined as ˆH = ΠT H Π and ˆx = ΠT x.
  • Assumptions: The utility, constraints, and reward are assumed to be respectively permutation invariant or equivariant under consistent node and allocation reordering.The paper states that the utility and constraint assumptions are satisfied by usual choices, while the reward condition depends on the physical model.
  • Theorem 1: Theorem 1 states that networks related by a permutation have the same optimal REGNN filters.A REGNN trained on one network distribution can transfer to the permuted distribution without loss of optimality.
  • Theorem 1: The transfer result follows because both the resource-allocation problem and REGNNs are equivariant to permutations.The theorem connects the equivariance results established for the optimization problem and the architecture.

A. Permutation equivariance of optimal resource allocation

The optimal resource-allocation problem is permutation equivariant when the network distributions, utilities, constraints, and reward satisfy the stated symmetry conditions. Consequently, permuting network nodes produces correspondingly permuted optimal allocations without changing utility.

  • Proposition 1: Under Assumptions 1–3, the optimal resource allocations in the statistical optimization problem are permutation equivariant.The result applies when the network distributions are related by the same permutation matrix.
  • Proof: Permuting network states and allocations produces a correspondingly permuted expected reward.The proof uses a change of variables together with reward equivariance and the distributional permutation relation.
  • Proof: The optimization problem remains feasible with equal utility after consistent permutations of the network and resource-allocation function.This establishes the equality needed for the optimal-policy result.
  • Interpretation: The permutation property is natural because node labels are generally arbitrary and the policy structure should reflect that.The paper also identifies this structure as potentially reducing the dimensionality of the parameterization search.

B. Equivariance of Random Edge Graph Neural Networks

REGNNs preserve permutation equivariance through their graph-convolutional architecture: permuting the graph and input signal permutes the output while leaving filter weights unchanged. This structure supports transfer across permuted networks, though it limits handling of heterogeneous agents.

  • Equivariance: REGNN outputs are permutation equivariant: permuting the graph and input signal produces an equally permuted output.The property follows through each graph-filter layer and pointwise nonlinearity, then extends to the composition of layers.
  • Equivariance: The equivariance arises from the multiplicative relationship between channel states and node states in the graph filter.In wireless networks, relabelling transmitters permutes power allocations without permuting filter weights.
  • Transference: Theorem 1 transfers optimal filter tensors between permuted network distributions because REGNN outputs and optimal policies share permutation structure.The proof shows feasibility and equal utility in both directions, forcing the transferred tensor to remain optimal.
  • Transference: REGNN permutation invariance does not require knowledge of the permutation relating the two network distributions.This distinguishes the architecture from simply undoing a known permutation before applying an operator.
  • Limitation: Permutation invariance hinders handling heterogeneous agents when utilities assign different weights to different agents.A weighted utility wT r violates the permutation-invariance assumption by changing the weight assignment under reordering.

V. PRIMAL-DUAL LEARNING

The paper trains REGNN resource-allocation policies by seeking a Lagrangian saddle point with stochastic primal-dual updates. Network probing supplies reward observations, allowing the method to avoid explicit knowledge of the reward model and state distribution.

  • Lagrangian formulation: The REGNN training objective is formulated through a Lagrangian with multipliers for expected-reward and utility constraints.The policy-feasibility constraint is enforced at the REGNN output layer rather than included in the Lagrangian.
  • Primal-dual updates: Because the optimization is nonconvex, the algorithm performs a local search and need not find the globally optimal filter tensor.The paper notes that several saddle points may exist and reports good empirical results despite this limitation.
  • Primal-dual updates: Training alternates gradient-ascent updates for primal variables and gradient-descent updates for dual variables.The updates use a stepsize and include projection to keep the nonnegative multiplier feasible.
  • Stochastic training: Stochastic updates estimate expectation-based gradients by sampling network states from the state distribution.The same sampling idea is used for multiplier and filter-tensor updates.
  • Model-free learning: The model-free updates require observing network states, executing the current REGNN policy, and probing the resulting reward.The filter update uses a randomized policy and a likelihood-ratio identity because reward gradients cannot be directly queried.
  • Model-free learning: The resulting filter update is model-free because it does not require explicit knowledge of the reward model or state distribution.This is achieved by computing updates from observed reward outcomes and system probing.
  • Algorithm 1: Algorithm 1 repeatedly samples states, probes the system, updates primal and dual variables, and repeats until convergence.The training architecture and initial variables are specified before the iterative loop.

VI. NUMERICAL RESULTS

The numerical study evaluates model-free REGNN policies for wireless resource allocation against heuristic baselines, including WMMSE, under constrained power-control settings. REGNN performance is compared using sum-capacity in simulated networks.

  • The study evaluates REGNN policies against WMMSE and other heuristic approaches for canonical wireless resource-allocation problems.The comparisons include equal-power and random full-power-selection heuristics where applicable.
  • The evaluated binary power-control problem maximizes sum-rate capacity subject to a shared maximum average power budget.Each transmitter either transmits with power p0 or does not transmit.
  • The problem is instructive because it is well studied and has numerous heuristic solutions available as baselines.The formulation does not use node state x or an associated cost constraint.

A. Ad-hoc networks

In randomly generated ad-hoc wireless networks, model-free REGNN policies are trained and evaluated across network sizes and SNR regimes. The experiments show compact REGNNs can outperform heuristics, match FCNN performance with far fewer parameters, and transfer across networks.

  • Network and training setup: The simulations generate random geometric ad-hoc networks with m transmitter/receiver pairs and time-varying Rayleigh fading.Transmitter locations are sampled uniformly, while channel states combine path-loss and fast-fading components.
  • Network and training setup: The REGNN uses model-free policy-gradient training with 8 hidden layers, one graph filter per layer, filter length 5, ReLU activations, and a sigmoid output.The sigmoid-normalized outputs parameterize the policy distribution.
  • Performance comparisons: With q = 40 parameters, REGNN matches an FCNN using approximately 4000 parameters in the medium-scale comparison.The FCNN uses fully connected layers of sizes 64 and 32, while REGNN training requires more iterations in this example.
  • SNR behavior: REGNN gains over WMMSE increase in higher average-SNR regimes, whereas at low average SNR it matches WMMSE.Average SNR is varied through the AWGN noise parameter 1/σ2 over {0.5, 1, 2}.
  • Transference: A REGNN trained on one randomly generated network is evaluated on another network of equal size using empirical sum-rate distributions over many random iterations.The experiment investigates transfer to randomly drawn networks with fixed density.

B. Transference

REGNN policies transfer from fixed training networks to larger networks and varying network sizes, retaining strong performance when network density remains comparable. This transfer weakens as deployment density diverges substantially from training.

  • Transference across network size: A REGNN trained on m = 50 only slightly degrades relative to one trained on m′ = 100 when evaluated on random networks of size 100.This supports training on smaller networks before deployment on larger ones.
  • Scaling to larger networks: From networks of size m′ = 50 to 500, the same REGNN outperforms heuristic methods.Network density remains constant as size increases, preserving the channel-condition statistics.
  • Transfer across density: For networks no denser than the training network, REGNN performance is strong relative to heuristics, but at higher densities it fails to match WMMSE.The authors attribute this to training and execution channel statistics diverging as interference grows.

C. Incorporating user demand

The user-demand extension adds per-transmitter ergodic-capacity constraints tied to sensor collection rates. A primal-dual REGNN training experiment evaluates whether these constraints converge alongside the objective.

  • Training experiment: During training, constraint violations for all 30 sensors converge toward feasibility, while the objective converges to a local maximum.These behaviors are shown in the two panels of Figure 11.
  • Problem formulation: The extended problem requires each transmitter’s ergodic capacity to exceed the average collection rate of its associated sensor.Each transmitter maintains a local state x_i representing current capacity demand, such as packet arrival rate.
  • Problem formulation: The optimization independently enforces feasibility for every transmitter while maximizing network sum-rate in expectation.This adds per-transmitter ergodic constraints to the prior resource-allocation problem.
  • Training experiment: A REGNN with m = 30 transmitter/receiver pairs is trained using the primal-dual method, with L = 10 layers and filters of length K_l = 5.Collection rates are drawn from an exponential distribution with mean 0.05, and each layer uses F_l = 1 filters.

D. Multi-cell interference network

The multi-cell setting extends resource allocation to users served by multiple base stations. REGNN performs close to model-informed WMMSE during training and transfers well as the number of cells increases.

  • Network setting: The multi-cell interference network has n base stations serving m cellular users distributed evenly among the cells.The setting is motivated by cellular networks and its potential to scale as cells and users grow.
  • Training performance: With m = 50 users and n = 5 base stations, a REGNN with q = 40 parameters outperforms model-free heuristics but does not quite meet WMMSE.WMMSE uses model information in its implementation.
  • Training performance: During the same five-cell experiment, REGNN almost matches WMMSE without model knowledge in training or execution.The comparison is reported for the REGNN’s training performance against heuristic methods and WMMSE.

VII. CONCLUSION

The paper addresses large-scale wireless resource allocation with REGNNs, whose parameter dimension remains independent of network size and whose policies are permutation equivariant. Numerical simulations show effective resource-allocation policies for large wireless networks.

  • Conclusion: Large-scale wireless resource allocation is posed as constrained statistical learning solved by parameterizing policies and training them with a model-free primal-dual method.The paper identifies fully connected networks as unsuitable because their parameter dimension becomes prohibitively large.
  • Conclusion: REGNNs parameterize resource allocation using a graph structure with significantly smaller parameter dimension that does not scale with wireless-network size.This architecture is designed for randomly varying graph structures induced by fading channel states.
  • Conclusion: REGNN policies are permutation equivariant, enabling similar performance on networks that are close to permutations of one another.The conclusion connects this property to transfer across network structures.
  • Conclusion: Numerical simulations demonstrate effective REGNN resource-allocation policies for large-scale wireless networks.The supplied conclusion passage states this outcome without specifying a single aggregate metric.
Loading 1909.01865v4…