PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalability of Graph Neural Network Policies in Wireless Communication Networks

Romina Garcia Camargo, Zhiyang Wang, Alejandro Ribeiro

arXiv:2609.06066v1eess.SP

TL;DR

Formal scalability guarantees for GNNs do not directly cover sparse wireless graphs with spatial geometry. The paper models RGGs as perturbations of DGGs and extends the analysis to conflict graphs; its bounds establish scale transferability across these settings, with simulations evaluating power allocation and link scheduling.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) offer scalable solutions for wireless resource allocation, yet existing formal performance guarantees across varying scales for spatial and sparse graphs do not directly apply to these settings. Scalability theories rely on dense graphon limits or continuous manifold approximations, both of which fail under the sparse, bounded-degree regimes and Euclidean metric constraints of physical wireless environments. This paper establishes a theoretical framework for GNN transferability over sparse Random Geometric Graphs (RGGs), capturing distance-dependent channel decay and spatial interference. We model sparse RGGs as spatial perturbations of regular Deterministic Grid Graphs (DGGs) and employ spatial windowing operators to compare networks across differing scales. Assuming Lipschitz continuity of GNN architectures and signal stationarity, we prove scalability over DGGs and bound same-scale transferability between DGGs and RGGs. Combining these results establishes formal scalability bounds across sparse RGG topologies. Finally, we extend this framework to conflict graph models, deriving equivalent scalability guarantees for link-level resource allocation policies. We verify our results for scalability with two experiment settings: power allocation and wireless link scheduling. The simulations show GNNs exhibit the expected scalable behavior, and analyze the relevance of our theoretical assumptions in practical deployment.

I. INTRODUCTION

The paper addresses the lack of formal GNN scalability guarantees for sparse wireless topologies with spatial geometry. It develops a DGG-to-RGG analysis and extends it to conflict graphs, alongside evaluations on power allocation and link scheduling.

I. INTRODUCTION

  • Existing graphon and manifold-based scalability frameworks do not directly cover sparse wireless graphs with bounded degree and spatially embedded channel physics.Graphon approaches model dense networks, while manifold guarantees rely on node density that practical sparse wireless topologies lack.Source: §I · p. 1
  • The framework models sparse RGGs as spatial perturbations of DGGs and combines DGG scalability with same-scale RGG–DGG transferability bounds.Its analysis uses spatial windowing and assumes graph-filter and activation Lipschitz continuity alongside signal stationarity.Source: §I · p. 1
  • The framework extends to link-level policies by applying the perturbation analysis to conflict-graph formulations of wireless scheduling.The extension yields equivalent scalability guarantees for link-level resource allocation policies.Source: §I · p. 2
  • Simulations evaluate power allocation on sparse RGGs and link scheduling on conflict graphs, reporting GNN outperformance of heuristic baselines across scales.The experiments also test the relevance of topological closeness and Lipschitz-continuous graph-filter assumptions.Source: §I · p. 2

II. SCALABILITY OF WIRELESS POLICIES PARAMETERIZED VIA GRAPH NEURAL NETWORKS

  • Wireless resource allocation is formulated as maximizing long-term network utility subject to system constraints, with interference limiting user rates.Power allocation maximizes expected sum rate under a network-wide average power budget; link scheduling seeks successful transmission rates while ensuring channel access.Source: §II · p. 2
  • The channel-interference graph represents pairwise channel gains, while the conflict graph connects distinct links that share a user.The former captures channel effects including path loss and fading; the latter models potential transmission collisions.Source: §II · p. 2

A. Learning Resource Allocation Policies on Graphs

GNNs parameterize wireless resource-allocation policies using graph filters and pointwise nonlinearities. The section defines transferability and scalability through comparisons across graphs and scales, with spatial windowing used to compare corresponding portions of larger and smaller graphs.

A. Learning Resource Allocation Policies on Graphs

  • Graph filters diffuse input signals across a graph through powers of the graph shift operator, and pointwise nonlinearities combine with filters to form a GNN.The filter order limits diffusion to a finite-hop neighborhood; the learned GNN acts as a resource-allocation policy.Source: A. Learning Resource Allocation… · p. 3
  • A learned GNN policy can be executed without online optimization after its parameters are trained to maximize network utility.The paper frames this parameterization as a learning task for the resource-allocation objective.Source: A. Learning Resource Allocation… · p. 3

B. Scalability of Graph Neural Networks on Wireless Networks

  • Transferability compares a trained model's performance on another graph, while scalability asks whether deployment on larger graphs preserves performance.The GNN parameter dimensions are independent of graph size, but robust performance when moving from smaller training graphs to larger test graphs is the property at issue.Source: B. Scalability of Graph Neural… · p. 3
  • Scalability is measured by comparing the large-graph output projected through a window with the model output on the smaller graph; a bounded gap supports small-network training and larger-network deployment.The window selects a subset statistically close to the smaller graph, and the paper targets sparse graphs and conflict graphs using RGGs with DGGs as a proxy.Source: B. Scalability of Graph Neural… · p. 3

III. SCALABILITY OF GRAPH NEURAL NETWORKS ON RANDOM GEOMETRIC GRAPHS

The analysis uses DGGs as regular spatial counterparts to sparse RGGs, then establishes GNN scalability on DGGs under structural, signal, and architectural assumptions. Boundary effects govern the finite-graph bound and diminish asymptotically.

III. SCALABILITY OF GRAPH NEURAL NETWORKS ON RANDOM GEOMETRIC GRAPHS

  • DGGs connect neighboring points on a regular grid, whereas RGGs connect uniformly sampled spatial points within a fixed radius.The paper treats an RGG as obtainable by perturbing DGG node positions and redrawing edges, while assuming their topologies are sufficiently close for its analysis.Source: §III · pp. 3–4

A. Scalability of Graph Neural Networks on DGGs

  • DGG scalability compares a GNN on a larger grid with its output projected onto a spatially adjacent sub-grid, preserving the smaller grid's structure.The signal is assumed bounded and stationary with respect to the graph shift operator, and the architecture uses normalized Lipschitz nonlinearities.Source: A. Scalability of Graph Neural… · p. 4
  • Under Assumptions 2–4, Theorem 1 bounds the scalability gap for a GNN trained on a smaller DGG and evaluated on a larger DGG.The bound also uses the filter coefficients and the input-signal magnitude.Source: A. Scalability of Graph Neural… · p. 4
  • Finite-grid transfer incurs localized approximation error because boundary nodes lack complete filter-radius neighborhoods.This truncation of filtering operations explains the bounded performance degradation when deploying a policy trained on a finite DGG on a larger one.Source: A. Scalability of Graph Neural… · p. 4
  • As grid size grows, the proportion of boundary nodes vanishes, so the boundary-effect constant and generalization gap tend to zero.The paper also notes that training on larger DGGs can narrow the scalability gap.Source: A. Scalability of Graph Neural… · pp. 4–5

B. Transferability of Graph Neural Networks between RGG and DGG

The section bounds transfer between structurally close RGGs and DGGs, then combines that result with DGG scalability to establish bounded-degradation transfer across expanding RGG scales.

B. Transferability of Graph Neural Networks between RGG and DGG

  • RGGs are formed by Gaussian perturbations of DGG node coordinates, with edges between perturbed nodes within a fixed radius; their topology must remain sufficiently close.This closeness makes DGGs an analytical proxy for RGGs.Source: B. Transferability of Graph Neural… · p. 5
  • The transfer bound depends on bounded input signals, few GNN layers, filter smoothness, and topological distance; smaller filter Lipschitz constant tightens it but limits frequency-response expressivity.The topological distance ε can be reduced by evaluating increasingly similar graph structures.Source: B. Transferability of Graph Neural… · p. 5
  • Under Assumptions 1, 3–5, transfer between same-scale RGGs and DGGs has a bounded performance gap in either direction.The bound is the same whether training on an RGG and transferring to a DGG or vice versa.Source: B. Transferability of Graph Neural… · p. 5

C. Scalability of Graph Neural Networks over RGG over scales

  • Combining DGG scalability with same-scale RGG–DGG transfer proves that a GNN trained on a small RGG can run on larger RGGs with bounded performance degradation.The bound depends on structural approximation error ε and input-signal energy, assumed bounded as network dimension increases.Source: C. Scalability of Graph Neural… · pp. 5–6
  • For cross-scale RGG comparisons, windowing must select a localized subgraph statistically close to a small RGG; an adjacent m-node section satisfies Assumption 6.This preserves properties such as degree distribution and local edge connectivity.Source: C. Scalability of Graph Neural… · pp. 5–6

IV. SCALABILITY OF GRAPH NEURAL NETWORKS ON CONFLICT GRAPHS

The section extends scalability analysis to conflict graphs for edge-level tasks and shows that GNN performance gaps on conflict graphs of DGGs vanish asymptotically despite their greater density.

IV. SCALABILITY OF GRAPH NEURAL NETWORKS ON CONFLICT GRAPHS

  • A conflict graph represents original-graph edges as nodes, connecting distinct edges that share an endpoint; the analysis focuses on unweighted graphs.The framework is extended to conflict graphs corresponding to RGGs.Source: §IV · p. 6

A. Scalability of Graph Neural Networks on conflict graphs of DGGs

  • Conflict graphs of DGGs retain block-circulant adjacency structure, although interior-node degree rises from 4 to 6.The boundary also expands, with two concentric layers along the perimeter having degrees from 3 to 5.Source: A. Scalability of Graph Neural… · p. 6
  • The scalability analysis evaluates the GNN in the larger dimension and windows the graph and input to match the smaller conflict DGG.Architectural stability is imposed on the L-layer GNN trained at scale c.Source: A. Scalability of Graph Neural… · p. 6
  • As network size c grows, the performance gap between small-scale training and large-scale testing on conflict DGGs asymptotically vanishes despite their greater density.Border effects also become insignificant as c grows.Source: A. Scalability of Graph Neural… · p. 6

B. Transferability of Graph Neural Networks between conflict graphs of RGGs and DGGs

The paper establishes transferability bounds between conflict graphs of RGGs and DGGs, then combines them to prove scalability across conflict RGGs. Experiments examine power allocation and link scheduling across network scales.

B. Transferability of Graph Neural Networks between conflict graphs of RGGs and DGGs

  • Zero-padding conflict-graph adjacency matrices to a common dimension preserves their spectral-distance comparison; Theorem 5 bounds same-scale transfer loss between conflict RGGs and DGGs.The bound applies to transfer in either direction between the two structures.Source: B. Transferability of Graph Neural… · p. 7

C. Scalability of Graph Neural Networks on conflict graphs of RGGs

  • Under Assumptions 1–6, GNNs trained on smaller conflict RGGs generalize to larger ones with bounded loss, and the bound decreases with 1/√c.Increasing the training graph size further improves transferability to larger graphs.Source: C. Scalability of Graph Neural… · p. 7

V. NUMERICAL EXPERIMENTS

  • Experiments test node-level power allocation on RGGs and link-level scheduling on conflict graphs generated from spatially perturbed DGGs.The average node degree is approximately constant across scales and perturbation levels.Source: §V · pp. 7–8

A. Scalability of GNNs

  • At m = 1500, a GNN trained at m = 500 retains its performance advantage over WMMSE across the scaled topology.The comparison uses sum-rate histograms.Source: Figure 3 · p. 8, A. Scalability of GNNs · p. 8
  • Among models trained at m ∈ {500, 1000, 1500}, the m = 1500 model has violations closest to zero at m = 2500, but performs less well at m = 500.The paper defines normalized power constraint violation as (Ptotal − Pmax)/m.Source: Figure 4 · p. 8, A. Scalability of GNNs · p. 8
  • Across growing link networks, the c ≃500-trained GNN maintains near-zero constraint violations and closely matches FPLinQ’s sum-rate performance.Figure 5 compares deployment on larger networks against FPLinQ.Source: A. Scalability of GNNs · p. 8, Figure 5 · p. 9
  • Both WLS models scale stably, while the model trained at c2 = 500 yields more high-rate allocations than the model trained at c1 = 100.Figure 6 compares per-link empirical rate distributions under δ = 0.1.Source: A. Scalability of GNNs · pp. 8–9, Figure 6 · p. 9

B. Robustness to different noise levels and relevance of closeness

The experiments examine how training noise and closeness to grid structure affect wireless GNN performance, and test the integral-Lipschitz filter assumption. The conclusion reports scale generalization across node- and edge-level tasks and identifies extensions to broader graph settings.

B. Robustness to different noise levels and relevance of closeness

  • Low-noise WLS models generalize worse to irregular graphs, while high-noise models retain strong backward compatibility on near-grid structures.WLS performance also degrades as training noise increases; the FPLinQ benchmark has roughly 70–80% constraint violations because it optimizes an instantaneous rather than long-term-rate formulation.Source: B. Robustness to different noise… · p. 9, Figure 9 · p. 10
  • Models trained on RGGs closer to the underlying DGG scale better, with higher sum rates and minimal constraint violations in power allocation and link scheduling.For power allocation, unperturbed-grid training scales to larger networks while respecting the total power budget; higher training noise diminishes gains, especially at large scales, though constraint violations remain non-positive.Source: B. Robustness to different noise… · p. 9, Figure 7 · p. 9, Figure 8 · p. 10

C. Impact of the integral Lipschitz assumption

  • The integral-Lipschitz GNN scales better than the regular GNN in power allocation, with higher sum rates and power constraints closer to zero, but the differences are not significant.The comparison is between models trained at scale m = 500; Table I presents the scalability comparison.Source: C. Impact of the integral Lipschitz… · p. 9, Table I · p. 10

VI. CONCLUSIONS

  • The framework demonstrates scale generalization on sparse RGGs and conflict graphs, while future work could extend it to other sparse graphs, architectures, and dynamic topologies.The conclusion describes experiments on node- and edge-level tasks as validating the theoretical bounds and assumptions; proposed extensions include non-uniform spatial distributions and relaxing signal stationarity.Source: §VI · p. 10

APPENDIX

The appendix bounds how a GNN’s output changes across DGG scales by comparing windowed signals under Assumptions 2–4. Its proof controls boundary effects as they propagate through the network’s layers.

A. Scalability of Graph Neural Networks over DGG

  • Under Assumptions 2–4, Theorem 7 bounds GNN scalability across DGGs with different node counts.The proof proceeds by induction over GNN layers, starting with matching windowed input signals.Source: A. Scalability of Graph Neural… · p. 11
  • Windowing creates discrepancies near graph boundaries, where full-graph diffusion can differ from diffusion on the truncated graph.The proof bounds signal in the boundary region and uses the pointwise Lipschitz activation to avoid increasing the error norm.Source: A. Scalability of Graph Neural… · pp. 11–12
  • Across L layers of K-hop filters, the affected boundary region extends to nodes within LK hops, with its size bounded by 2√mLK + L^2K^2.The final error bound accounts for this expanded region and the maximum filter coefficient sum, then squares the norm and divides by m.Source: A. Scalability of Graph Neural… · p. 12

B. Scalability of Graph Neural Networks between RGG and DGG

The section bounds performance transfer between an RGG and a DGG of the same size by using graph perturbation and integral-Lipschitz filters. It extends the filter comparison to GNN outputs through the network layers.

B. Scalability of Graph Neural Networks between RGG and DGG

  • Theorem 8 bounds performance degradation when transferring a GNN between same-size RGGs and DGGs under Assumptions 1 and 3–5.The proof starts from adjacency-matrix closeness and bounds the resulting eigenvalue differences.Source: B. Scalability of Graph Neural… · p. 12
  • The filter comparison separates eigenvalues within a distance δ from those farther away and uses the integral-Lipschitz condition to bound their contributions.The proof also bounds projections onto the complementary eigenspace using the Davis–Kahan theorem.Source: B. Scalability of Graph Neural… · pp. 12–13
  • The proof extends graph-filter transferability to GNN outputs by bounding layerwise differences and unrolling the recursion across L layers.It assumes normalized non-amplifying filters and a normalized-Lipschitz pointwise activation.Source: B. Scalability of Graph Neural… · pp. 13–14

C. Scalability of Graph Neural Networks over RGG

Theorem 9 addresses scalability for a GNN trained on an RGG of size m under Assumptions 1–6. The proof begins by bounding the difference between RGG-scale outputs.

C. Scalability of Graph Neural Networks over RGG

  • Theorem 9 considers a GNN trained on an RGG of size m under Assumptions 1–6.Its proof expands the between-scale difference, applies the triangle and Cauchy–Schwarz inequalities, and invokes stationarity.Source: C. Scalability of Graph Neural… · p. 14

D. Scalability of Graph Neural Networks over conflict DGG

Under Assumptions 3–4, scalability for conflict DGG policies is bounded. The proof adapts the layerwise argument by accounting for the conflict graph’s expanded boundary.

D. Scalability of Graph Neural Networks over conflict DGG

  • Under Assumptions 3–4, Theorem 10 bounds scalability between conflict DGG policies at scales c and d.The supplied passage does not include the bound’s expression.Source: D. Scalability of Graph Neural… · p. 14
  • For the conflict graph ˆGc, expanded boundary thickness 2 yields 4√(2c) affected boundary nodes within a 1-hop neighborhood, versus the standard m-node DGG perimeter baseline of 2√m.Source: D. Scalability of Graph Neural… · p. 14
  • Across LK hops, the proof bounds affected boundary nodes by 4√cLK + L²K², then substitutes this count into the energy bound for Equation (60).Source: D. Scalability of Graph Neural… · p. 14

E. Scalability of Graph Neural Networks between conflict RGG and DGG

The conflict-graph results bound transferability between RGGs and DGGs and scalability across conflict RGG scales. Experimental details describe interference-weighted positional perturbations and the settings used for power allocation and wireless link scheduling.

E. Scalability of Graph Neural Networks between conflict RGG and DGG

  • Under Assumptions 1, 3–6, Theorem 11 states that a GNN trained on conflict graphs of RGGs with c nodes, when deployed without retraining on larger conflict graph ˆR_d at scale d > c, has bounded scalability error.Source: E. Scalability of Graph Neural… · p. 14

F. Scalability of Graph Neural Networks over conflict RGG

  • Under Assumptions 1–6, Theorem 12 bounds the error when a GNN trained on a c-node conflict RGG is deployed without retraining on a larger conflict RGG.The supplied passage does not include the bound’s expression.Source: F. Scalability of Graph Neural… · p. 15

G. Experimental Details

  • Figure 10 shows interference-weighted RGGs with increasing positional noise; the noise levels that affected scalability were experimentally smaller than those used for WLS in Figure 2.The Figure 10 examples use η = 1e−2.Source: G. Experimental Details · p. 15, Figure 10 · p. 16
  • For PA and WLS, policies maximize the Lagrangian and minimize the dual function; parameters were held across scales except PA’s Pmax, set to the device count.Dual learning rates were adapted for each noise level, while primal learning rates were fixed.Source: G. Experimental Details · p. 15, Table II · p. 16

Related papers

Loading 2609.06066v1…