Limit Analysis of Graph Neural Networks with Wireless Conflict Graphs
Romina Garcia Camargo, Zhiyang Wang, Alejandro Ribeiro · 2026
Read Limit Analysis of Graph Neural Networks with Wireless Conflict Graphs by Romina Garcia Camargo, Zhiyang Wang, Alejandro Ribeiro (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03794.txt.
Introduction
Garcia Camargo, Wang, and Ribeiro set limits on how graph neural networks transfer across wireless network scales. Such networks allocate radio resources well by using graph structure. Models trained on small graphs should serve large deployments with little loss. Wireless conflict graphs are sparse: each node links to few others. The theory here covers graphs drawn from sparse random geometric graphs.
Conflict graphs model interference among links in those networks. Random geometric graphs sit close to deterministic grid graphs. That closeness bounds the loss when a policy moves across scales. Link scheduling validates the theory in practice. Learned policies beat existing benchmarks at scale, time after time. The authors also probe how their assumptions shape real performance. Network engineers get grounded guidance on when small-graph training is enough. Transfer can be trusted within the proven bounds.
Catalog record
| CREATOR | Romina Garcia Camargo, Zhiyang Wang, Alejandro Ribeiro |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.03794
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Limit Analysis of Graph Neural Networks with Wireless Conflict Graphs Romina Garcia Camargo, Zhiyang Wang, Alejandro Ribeiro Abstract Graph Neural Networks (GNNs) have emerged as a powerful tool for wireless resource allocation that leverages the underlying graph structure of communication networks. Their transferability property enables models trained on small-scale graphs to generalize to large-scale deployments with little performance deterioration, a desirable property for currently growing networks. Wireless networks are sparse regimes, where a single node is connected to a small number of other users. This work establishes theoretical results for transferability of GNNs over graphs derived from sparse Random Geometric Graphs (RGGs). In particular, we focus on conflict graphs of RGGs used to model interference among links. Our approach considers the closeness between RGGs and Deterministic Grid Graphs (DGG) to establish bounds in the performance loss when a model is transferred across scales. We validate our theoretical findings through the problem of link scheduling, demonstrating that our learned policies consistently outperform existing benchmarks at scale. Finally, we examine the impact of our theoretical assumptions on empirical performance. I Introduction Learning-based solutions are promising tools for addressing complex resource allocation challenges in next-generation networks. Graph Neural Networks (GNNs) are well-suited for these tasks, as the architecture exploits the underlying graph structure of wireless systems [ 12 , 16 , 2 ] . In particular, it allows for transferability: models trained on small graphs generalize to larger networks with minimal performance loss. While empirical studies show that GNNs successfully transfer in wireless settings [ 5 ] , these observations lack a formal foundation. Multiple works have explored the transferability of Graph Neural Networks [ 13 , 9 , 7 , 17 , 8 ] . However, most existing frameworks typically rely on limit objects such as graphons [ 13 ] or manifolds [ 17 ] , which define transferability as connectivity increases toward a dense limit. Physical constraints in wireless channels limit the number of connections per user, resulting in sparse graphs that traditional dense-limit theories fail to account for. To bridge this gap, recent work has begun analyzing transferability on sparse graphs via graphops [ 8 ] or using Random Geometric Graphs (RGGs), leveraging the geometric structure intrinsic to communication systems [ 3 ] . Resource allocation tasks such as link scheduling depend on the relationships between communication links rather than the users themselves. This is often tackled via conflict graphs, where links are modeled as nodes and edges represent interference or shared resources [ 18 , 4 ] (Section II ). However useful, it creates a specific sparse regime distinct from the underlying physical network. In this work we establish the theoretical analysis for transferability of GNNs on conflict graphs (Sections III and IV ). Extending our framework [ 3 ] , we model wireless connectivity using Random Geometric Graphs (RGGs) and prove that transferability holds via Deterministic Grid Graphs (DGGs). By leveraging their spatial periodicity, we overcome the analytical challenges posed by the topological irregularities of random node placements. Our results demonstrate that as the number of nodes increases, transferability is guaranteed for conflict graphs of RGGs that approximate conflict graphs of DGGs. We validate our theoretical framework with numerical experiments on the wireless link scheduling problem, incorporating a minimum transmission requirement per link (Section V ). The GNN is trained on conflict graphs derived from RGGs to select which links should be scheduled at each time step. Empirical results demonstrate that our transferred model consistently outperforms benchmarks at larger scales. Furthermore, we characterize the robustness of our RGG-DGG proximity assumption by analyzing model performance as the graph topology deviates from a grid-like structure. II Resource Allocation on Conflict Graphs Let {\mathbf{G}}=({\mathcal{V}},{\mathcal{E}}) be a graph with |{\mathcal{V}}|=v nodes and |{\mathcal{E}}|=e edges. Its conflict graph {\mathbf{G}}_{C}=({\mathcal{V}}_{C},{\mathcal{E}}_{C}) will have |{\mathcal{V}}_{C}|=e nodes, one for each edge in {\mathbf{G}} . An edge (i,j)\in{\mathcal{E}}_{C} will exist if edges i and j are incident on the same node in {\mathbf{G}} . Figure 1 shows an illustration of graphs and their conflict graphs. In wireless communication settings, conflict graphs are widely used to model resource allocation tasks (Section II-A , [ 5 ] ), as they represent dependencies or forbidden combinations between the edges of the original graphs [ 18 , 4 ] . In particular, these models are used to analyze the links of the network, such as via the primary interference model for wireless link scheduling [ 6 ] (Section II-B ). Figure 1 : Illustration of Random Geometric Graphs (blue) and their corresponding conflict graphs (pink) as the noise in positions increases. Observe that the RGG deviates from a grid-like structure as the positional noise increases. II-A Optimal Resource Allocation in Wireless Settings Let there be a network with m users, where each user is associated with a state at time t given by the vector \mathbf{x}_{m}(t)\in\mathbb{R}^{m} . Given the channel gains in \mathbf{S}_{m}(t)\in\mathbb{R}^{m\times m} , where [{\mathbf{S}}_{m}(t)]_{ij} is the gain from user i to user j , we are interested in allocating resources across the network. Let \mathbf{p}({\mathbf{x}}_{m}(t),{\mathbf{S}}_{m}(t)) be a mapping from network states to the instantaneous resource allocation policy across the network. The system will then return a reward given the allocation, \mathbf{f}(\mathbf{p}({\mathbf{x}}_{m}(t),{\mathbf{S}}_{m}(t));\mathbf{x}_{m}(t),\mathbf{S}_{m}(t)) . Considering the expectation over the stationary joint distribution of (\mathbf{x}_{m},\mathbf{S}_{m}) , we focus on the long-term average performance as \displaystyle\mathbf{r}_{m}=\mathbb{E}[\mathbf{f}(\mathbf{p};\mathbf{x}_{m},\mathbf{S}_{m})]. (1) Consider a utility function u_{0}(\mathbf{r}_{m}) and long-term system constraints \mathbf{u}(\cdot) . Our goal is to maximize the expected reward ( 1 ) by designing our allocation policy {\mathbf{p}}(\mathbf{x}_{m},\mathbf{S}_{m}) : \displaystyle\mathbf{p}^{\star}(\mathbf{x}_{m},\mathbf{S}_{m})= \displaystyle\argmax_{\mathbf{p}(\mathbf{x}_{m},\mathbf{S}_{m})\in\mathcal{P}(\mathbf{x}_{m},\mathbf{S}_{m})}\ u_{0}(\mathbf{r}_{m}), (2) s.t. \displaystyle\mathbf{r}_{m}=\mathbb{E}[\mathbf{f}(\mathbf{p}(\mathbf{x}_{m},\mathbf{S}_{m});\mathbf{x}_{m},\mathbf{S}_{m})], \displaystyle\mathbf{u}(\mathbf{r}_{m})\geq\mathbf{0}. The objective in Equation ( 2 ) is often nonconvex in \mathbf{p} , which makes finding a solution challenging. The common approach introduces a parameterized policy \bm{\Phi}(\mathbf{x}_{m},\mathbf{S}_{m};\mathbf{H}_{m}) , with parameters \mathbf{H}_{m}\in\mathbb{R}^{s} and learns a solution (Section III ). II-B Example: Wireless Link Scheduling Let {\mathbf{G}} be wireless network with m links, where p_{i}(t)\in\{0,1\} denotes the status of link i\in\{1,2,\dots,m\} . Entry p_{i}(t)=1 indicates that the link i is scheduled to transmit at time step t . Two links interfere each other if they are scheduled at the same time and share a common user [ 6 ] . The vector {\mathbf{p}}(t)=[p_{i}(t)]_{1\leq i\leq m}\in\{0,1\}^{m} describes the scheduling status of all links and is therefore supported on the edges of {\mathbf{G}} . Let us define {\mathbf{G}}_{C} the conflict graph of {\mathbf{G}} , then {\mathbf{p}}(t) is supported on the nodes of {\mathbf{G}}_{C} . We denote the adjacency matrix of {\mathbf{G}}_{C} as {\mathbf{A}}_{m}\in\{0,1\}^{m\times m} . The successful transmissions {\mathbf{r}}_{m}({\mathbf{p}}) resulting from a schedule {\mathbf{p}}(t) can be computed via the Hadamard product between the schedules and nonnegative projection [\mathbf{1}-{\mathbf{A}}_{m}{\mathbf{p}}(t)]_{+} , \displaystyle{\mathbf{r}}_{m}({\mathbf{p}})={\mathbf{p}}(t)\odot\big[\,\mathbf{1}-{\mathbf{A}}_{m}{\mathbf{p}}(t)\,\big]_{+}. (3) We are interested in the average rate over a time horizon. Wireless link scheduling seeks a policy that maximizes the long-term average of the sum rate {\mathbf{r}}_{m}({\mathbf{p}}) over T time steps. The policy must also satisfy the interference constraints intrinsic to the topology of the network. We incorporate a minimum transmission requirement for each link, \bm{\Delta}\in{\mathbb{R}}_{+}^{m} , such that all links must transmit at least a fraction of time: \displaystyle{\mathbf{p}}^{\star}(1:T)= \displaystyle\argmax_{{\mathbf{s}}(t)\in\{0,1\}^{K}} \displaystyle\frac{1}{T}\sum_{t=1}^{T}{\mathbf{1}}^{\top}{\mathbf{p}}(t)\odot\big[\,\mathbf{1}-{\mathbf{A}}_{m}{\mathbf{p}}(t)\,\big]_{+}, s.t. \displaystyle\frac{1}{T}\sum_{t=1}^{T}{\mathbf{p}}(t)\odot\big[\,\mathbf{1}-{\mathbf{A}}_{m}{\mathbf{p}}(t)\,\big]_{+}\geq\boldsymbol{\Delta}. (4) To solve this constrained optimization task we turn to the Lagrangian dual domain, defining a new learning objective that combines our objective function and a penalty term for