When many radio links share a band, a receiver fails when the total interference from all active transmitters crosses a threshold. It can fail even when no single interferer would cause trouble by itself. Learned schedulers today describe the network as an ordinary graph with one edge per pair of links. Examples include graph neural networks (GNNs, models that pass messages along graph edges) that decide which links may transmit. When the full, exact channel gains are available, this pairwise description is enough: the interference sum is just a sum of pairwise terms, and a GNN that sums incoming messages can compute it. Real systems, however, rarely deliver full precise gains. Receivers feed back a few bits, or a scheduler works from a binary "these two links conflict" map. Once the edge weights are thresholded or quantized, pairwise structure no longer determines which groups of transmitters jointly knock out a receiver. That group information is exactly what binary scheduling needs.
We propose to represent interference for threshold-based scheduling as an outage hypergraph. This is a hypergraph, meaning a graph whose edges can join any number of nodes. Here each edge is a minimal set of transmitters whose simultaneous activation drives some receiver below its target signal-to-interference-plus-noise ratio (SINR). Two things make this representation natural. First, it is exact: because interference only grows as transmitters are added, the infeasible schedules form an upward-closed family, and a family like that is fully described by its minimal members. Second, it is non-uniform by construction: in sparse areas the minimal outage sets are pairs, and in dense clusters they contain five or ten links. The core question is practical and falsifiable. Suppose each receiver has a fixed feedback budget. Is it better to spend those bits reporting a few truncated outage sets, or reporting quantized pairwise gains? We also ask whether a learned scheduler can consume variable-size sets without the workarounds that current non-uniform hypergraph networks rely on.
Core Claim
Our claim is that, at equal feedback bits per receiver, a scheduler that reads truncated outage hyperedges serves more links at the target SINR, with fewer outage violations, than a scheduler that reads quantized pairwise gains or a pairwise conflict graph. We expect the advantage to grow with link density, because dense networks have larger minimal outage sets. The intersection of the two directions in the file is essentially empty: no paper applies non-uniform hypergraphs to wireless resource management. We have deliberately not proposed the obvious version, "replace the pairwise channel graph with a hypergraph for power control under full channel knowledge." That version would lose to a sum-aggregating pairwise GNN on its own terms, since the interference denominator is additive in pairwise gains.
The motivation comes from two places. Partial and Exact Recovery of a Random Hypergraph from its Graph Projection shows that multi-way structure becomes unrecoverable from an unweighted pairwise projection above a sharp density threshold. Its analysis covers random uniform hypergraphs, so we do not claim its threshold transfers to geometric interference. We treat it as the reason to measure projection ambiguity directly in wireless instances. Map2Schedule supplies the regime: it builds a pairwise link-conflict graph from predicted radio maps and schedules links on and off with a GNN. That is precisely where aggregate interference from several links can slip past pairwise conflict tests.
Research Program
The first piece is the representation and the feedback protocol. Receiver $i$ knows its own received interference powers. Given nominal transmit powers, it computes locally the minimal sets $S$ of transmitters satisfying
$$p_i g_{ii} < \gamma \Big(\sigma^2 + \sum_{j \in S} p_j g_{ji}\Big),$$
where $g_{ji}$ is the channel power gain from transmitter $j$ to receiver $i$, $p_j$ is transmit power, $\sigma^2$ is noise power, and $\gamma$ is the SINR target. Each such set, together with $i$, becomes a hyperedge. Enumerating these sets is cheap for small sizes, because sorting interferers by received power bounds the search. The receiver then reports as many hyperedges, up to size $r$, as fit in $B$ bits, each costing about $|S|\log_2 n$ bits. The pairwise competitor spends the same $B$ bits on its strongest interferers' identities plus quantized gains. We will also study a hybrid that splits the budget between the two formats, because the optimal split is itself an informative result.
The second piece is a scheduler that handles any hyperedge size with one set of weights. Tensorized Hypergraph Neural Networks handles non-uniform hyperedges in two ways. One adds a global dummy node, which it reports worsens over-smoothing and limits depth to two layers. The other trains one branch per hyperedge size, so parameters grow with the number of sizes present. Neither suits a network whose set sizes shift continuously with density. Our message function applies a shared permutation-invariant set encoder to the members of each hyperedge, conditioned on a learned embedding of the set size, so parameter count does not depend on how many sizes appear.
Training is unsupervised. Following the idea in Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering of attaching a set function to each hyperedge rather than a uniform cut cost, each outage hyperedge $e$ gets the penalty "all members active." The continuous relaxation of that penalty over activation probabilities $x \in [0,1]^n$ is $\min_{j \in e} x_j$. This handles arbitrary cardinality natively, with no padding. The training loss is the negative expected number of served links plus a learned multiplier on the summed hyperedge penalties. This follows the primal-dual style that Optimal Wireless Resource Allocation With Random Edge Graph Neural Networks uses for constrained allocation.
The third piece is a diagnostic that asks whether the phenomenon is even present. Before training anything, we will measure on each benchmark three quantities as a function of density: the fraction of SINR violations under a pairwise-feasible schedule that come from sets of size three or more, and how often distinct outage hypergraphs share the same thresholded pairwise conflict graph. If higher-order outages are rare at realistic densities, the proposal stops here and reports a negative result. That result would still be useful, because it would say pairwise conflict graphs are adequate.
Baselines
The naive reference points are "schedule every link" and the distance-based scheduling that Map2Schedule reports reaching only about 50% of potential capacity in urban settings. Both run on the same instances and cost no feedback.
The strongest method on the pairwise-conflict side is the structure2vec link-embedding scheduler of Map2Schedule. That paper reports reaching over 90% of the sum-rate of the physical-model baseline FPLinQ, and scheduling 50 links in 0.2 seconds. It is the strongest competitor because it is the only method in the file built for binary link scheduling over a learned conflict structure. We will rerun it on our instances with its conflict threshold tuned for our SINR target.
The strongest competitor on the quantized-gain side is a sum-aggregating pairwise GNN that reads quantized gain edges. It follows the design of WCGCN from Graph Neural Networks for Scalable Radio Resource Management, with sum aggregation in place of max so that it can represent aggregate interference, and it is retrained with our binary-scheduling loss. For power control, WCGCN is reported to achieve roughly 97% to 103% of WMMSE sum-rate. There is no reported result found on Lacuna for any method on outage-constrained binary scheduling under a feedback budget, so these numbers anchor plausibility, not the target.
As an upper reference, the same GNN reads full-precision gains. We also run FPLinQ and a greedy scheduler that checks SINR exactly with full channel knowledge.
Fairness conditions apply to every comparison. All learned methods share the same training instances, the same number of gradient steps, the same hyperparameter search budget (an equal number of trials), and parameter counts within a factor of two. All budget-limited methods receive identical $B$.
Two ablations isolate our ingredients. The first replaces each hyperedge by its clique, keeping our hypergraph information but forcing it into pairwise form. The second swaps our shared, size-conditioned encoder for the one-branch-per-size design of THNN, holding everything else fixed.
We count the proposal as beating the baselines if the hypergraph scheduler serves significantly more links at target SINR than the best pairwise method at the same $B$, across multiple seeds, in the dense regime, without a higher outage rate. We also require it to reach within a few percent of the full-channel upper reference at a budget where pairwise formats fall clearly short.
Why not just…?
Why not just feed quantized pairwise gains to a sum-pooling GNN? This is the real threat. With enough bits, quantized gains let the network approximately add up interference, and the hypergraph format would add nothing. Nothing in the file settles this. The equal-budget sweep over $B$ is designed exactly to answer it. If the pairwise curve matches or beats the hypergraph curve at every budget and density, the core claim is false, and we will report it that way. Our prior for why hyperedges could win is that outage sets spend bits only on the combinations near the decision boundary. Quantized gains spend bits uniformly, including on precision that never changes a decision.
Why not just use a more conservative pairwise conflict threshold? Lowering the threshold at which two links are declared in conflict does suppress aggregate outages, but it also forbids many pairs that would have been fine together. Aggregate outage depends on which other links are active, and no single pairwise threshold can express that. The Map2Schedule baseline with a tuned threshold measures this directly, as a trade-off curve between served links and outage rate. Our method has to lie strictly above that curve.
Why not just use THNN's multi-branch model on the hyperedges? Its authors report that it works on non-uniform 3D-object hypergraphs. It may work here too. Our costs are that it needs a branch per hyperedge size, which is unknown in advance in wireless networks, and that its numerical behavior degrades beyond two layers. The branch-architecture ablation, together with a train-sparse, test-dense transfer experiment, decides whether our shared encoder is actually needed. A reasonable concern is REGNN's reported fragility under density shifts, which suggests size-specific structure may fail to transfer. That is precisely the transfer our experiment tests.
Why not just run a centralized greedy SINR check? Given full channel knowledge, it is simple and exact. It is not an alternative under a feedback budget, however, since it requires all gains at one place. We include it as the upper reference rather than as a competitor.
Proposed Experiments
We use two settings. The first is the synthetic random-geometric ad hoc setting of Unfolding WMMSE Using Graph Neural Networks for Efficient Power Allocation: Rayleigh fading, path-loss exponent 2.2, and 20 pairs for training. We vary density by fixing the area and sweeping link counts upward, and we test on held-out channel draws. The second is urban vehicle-to-vehicle scheduling on RadioMapSeer, whose 56,000 radio maps across 700 cities are used in Map2Schedule, with gains taken from the maps. CKMImageNet serves as a held-out environment set for transfer.
Metrics are the number of links meeting the SINR target, the sum-rate of served links, the outage-violation rate, feedback bits per receiver, and inference time.
The decisive checks come in order. First is the diagnostic: the density at which higher-order outages become common, and how often thresholded pairwise conflict graphs are ambiguous about the underlying outage sets. Second is the equal-budget curves of served links against $B$ at low, medium, and high density. Our claim predicts that the gap over quantized pairwise feedback is near zero at low density and widens with density. A gap that is flat, or that appears at low density, would indicate the gain comes from something other than higher-order structure. Third is the clique-expansion ablation, which separates "better information" from "better format." Fourth is zero-shot transfer from sparse to dense and from RadioMapSeer to CKMImageNet environments, comparing the shared-encoder and per-size designs.
References
- Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
- Map2Schedule: An End-to-End Link Scheduling Method for Urban V2V Communications
- Tensorized Hypergraph Neural Networks
- Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
- Optimal Wireless Resource Allocation With Random Edge Graph Neural Networks
- Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis
- Unfolding WMMSE Using Graph Neural Networks for Efficient Power Allocation
- CKMImageNet: A Dataset for AI-Based Channel Knowledge Map Toward Environment-Aware Communication and Sensing