Deciding which wireless links may transmit at the same time is a hard combinatorial problem. Two links that interfere cannot both be on, so the task becomes picking the most valuable set of mutually compatible links on a "conflict graph", where links are nodes and interference is an edge. Fast local solvers, including graph neural networks (GNNs, networks that pass messages between neighboring nodes), usually solve a relaxed version in which each link gets a fractional activation between 0 and 1. In dense, near-symmetric neighborhoods they often stall at undecided fractional states, and existing systems then break ties with ad-hoc randomness or greedy rounding. Coding theory has a precise account of this failure and a fix. Local iterative decoders stall at suboptimal fixed points. If the problem is laid out as a chain of coupled blocks and a few boundary blocks are made easy ("seeded"), a front of correct decisions travels inward and the local decoder reaches the optimal threshold. This effect is called threshold saturation. The same line of work proved that a global linear-programming (LP) relaxation gets no benefit from seeding, because it optimizes everything at once and ignores boundaries.
This proposal carries that asymmetry over to scheduling. Geometric wireless networks are already spatially coupled: interference is local, and a region's decisions depend only on nearby regions. We propose to fix exact decisions in a thin seed strip, solve the rest with a local relaxed message-passing solver, and freeze links as they become confident. The claim is that a front of committed decisions then sweeps across the network, reaches better schedules than unseeded local relaxation or global LP-plus-rounding, and keeps feasibility by construction. The prediction that makes this falsifiable comes directly from the coding result: seeding should help the local solver and should do nothing for the global LP.
Core Claim
On geometric conflict graphs with bounded interference range, seeded local relaxation with progressive freezing produces a propagating decision front. This seeded solver closes most of the gap between unseeded local relaxation and the exact maximum-weight independent set (MWIS) schedule. The gain comes from the interaction between seeds and local dynamics, not from sweeping in a fixed order and not from the relaxation alone. Three further predictions follow. First, the gain should vanish on graphs without spatial locality, such as Erdős–Rényi graphs. Second, the gain should vanish for a global LP solver given the same seeds. Third, a front should either travel at positive speed or stall ("pin"), depending on interference density. That third prediction is the scheduling analogue of the threshold separating saturated and unsaturated regimes.
Grounding in Prior Work
The mechanism comes from the threshold-saturation literature. Threshold Saturation for Spatially Coupled LDPC and LDGM Codes on BMS Channels proves, with a potential-function argument, that boundary seeds remove the barrier states that trap local decoders. The sparse-regression work (Threshold Saturation of Spatially Coupled Sparse Superposition Codes for All Memoryless Channels) shows the same effect as a traveling decoding wave. The glassy phase of Gallager codes describes the metastable traps that uncoupled message passing falls into. These papers supply the mechanism and the analysis tools. None of them treats resource allocation, where the coupling structure is given by geometry rather than chosen by the designer.
The constraint and the main test come from Linear Programming Decoding of Spatially Coupled Codes. It proves that LP decoding of spatially coupled codes has exactly the graph-cover threshold of the base code, so coupling brings no saturation. The authors attribute this to global optimization over the whole polytope and suggest that local, LP-inspired message passing might behave differently. We take that suggestion literally in a new domain. We also build our key ablation from their negative result: seeded global LP is expected to perform no better than unseeded LP.
The motivating evidence for the gap comes from scheduling. Spatial Deep Learning for Wireless Scheduling refines soft schedules over feedback stages and needs stochastic updates to break symmetry between conflicting links. That is exactly the stall we target, handled there by randomness rather than structure. Link Scheduling using Graph Neural Networks casts scheduling as MWIS. It turns GCN outputs into schedules through greedy selection trained by reinforcement learning (GCN-LGS), or through tree search (GCN-CRS). Neither has a propagation structure or feasibility-by-construction beyond greedy selection.
The local solver we reuse is supplied by two papers. Unfolding WMMSE Using Graph Neural Networks for Efficient Power Allocation unrolls an optimization algorithm into a few GNN layers. Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis shows that message-passing GNNs are equivalent to distributed local algorithms and transfer from 50 to 1,000 links. We reuse these architectures but change how they are run: with seeds, freezing and a moving front. Finally, Congruence Decomposition with Neural Block Solvers for Large-Scale PCI Assignment rounds a GNN-parameterized relaxation by conditional expectation and reaches zero constraint violations. It is our representative of the "global relaxation then round" strategy. It is instance-wise and blind to boundaries, which is exactly the property the coding result says limits such approaches.
Research Program
The base problem is MWIS on a conflict graph with link weights $w_i$ (queue-length times rate, as in the MWIS scheduling literature). Its relaxation is
$$\max_{x \in [0,1]^N} \sum_i w_i x_i \quad \text{s.t.} \quad x_i + x_j \le 1 \text{ for every conflict edge } (i,j).$$
This relaxation is known to have half-integral optimal vertices. In ambiguous dense regions its optimum is therefore the uninformative all-one-half state. That is a concrete instance of the boundary-indifferent global behavior identified by Bazzi et al.
The local solver is a projected, penalized ascent in which each link updates using only its neighbors' current activations. We use two versions of it. The first is hand-written. The second is unrolled into a small GNN with learned step sizes and penalties, in the style of UWMMSE.
Freezing works as follows. A link is fixed to 1 once $x_i > 1-\delta$ and all its conflicting neighbors are either frozen at 0 or below $\delta$. A link is fixed to 0 once a neighbor is frozen at 1. Frozen links then act as boundary conditions for their neighbors. The frozen set is always an independent set, so the output is feasible without any rounding step. Links still fractional when the iteration budget runs out are finished by a local greedy pass.
Seeds are thin strips, of width comparable to the interference range, solved exactly by a small integer program. We vary where the seeds sit (one edge, two opposite edges, or a lattice of seed strips) and how far apart they are.
The analysis has three parts. In one-dimensional "highway" deployments, the conflict graph has bounded bandwidth, so exact MWIS is computable by dynamic programming. There we measure front speed and pinning directly. We also test whether a potential-style condition, namely that the seeded local optimum dominates the stalled fractional state, predicts which way the front moves.
In two-dimensional random geometric deployments we measure the tradeoff between seed spacing and quality. Seeds cost two things: seeded links are decided with only local information, which plays the role of rate loss, and dense seeding shortens the front's travel distance, which reduces latency. We expect quality to degrade gracefully as seeds get denser and latency to fall roughly linearly with seed spacing, because the front moves a bounded distance per iteration.
We also extend the method to a per-channel budget, where at most $k$ links may be active per band. Mass-conserving pairwise swaps within the active front, borrowed from A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint, keep that linear constraint invariant. Because swaps happen only among the few undecided links at the front, we avoid that paper's impractical constants.
Baselines
The naive reference point is topology-blind distributed greedy MWIS, together with independent randomized rounding of the relaxed solution followed by conflict repair. Greedy is what deployed systems use. Link Scheduling using Graph Neural Networks reports that GCN guidance roughly halves greedy's suboptimality gap. Any method that fails to beat plain greedy on geometric graphs is not worth its complexity.
The strongest existing learned competitors are that paper's two GCN schedulers. GCN-CRS is reported to exceed an approximation ratio of 0.98, and GCN-LGS is the distributed variant. We run both on the paper's Erdős–Rényi and Barabási–Albert graphs, with Poisson arrivals, and on our geometric graphs. They get the same training distribution and the same wall-clock inference budget as our unrolled solver. Approximation ratios are computed against an exact integer-program solution on instances small enough to solve.
On distributed, latency-constrained operation, beating GCN-LGS at equal message rounds is the meaningful bar. For centralized use, beating it means matching the reported 0.98 while using local computation only. On the sum-rate side, the strongest model-based reference is FPLinQ from Coordinated Scheduling and Spectrum Sharing via Matrix Fractional Programming, which reports nearly double FlashLinQ's sum-rate. The file gives no absolute sum-rate value for FPLinQ, so we rerun it ourselves on its 1 km² ITU-1411 setup with up to 900 links. The spatial deep learning scheduler is reported to reach over 92% of FPLinQ with no channel state information. We will count reaching or exceeding FPLinQ's sum-rate, with channel information and at lower latency, as beating it.
The "global relaxation then round" competitor is the MWIS LP solved exactly and rounded by conditional expectation, as in MMD-GPO. It is run with the same seeds our method gets.
Three ablations isolate the key ingredient. The first is local relaxation with random symmetry breaking and no seeds. The second is a seeded spatial sweep that makes greedy decisions in the front's order with no relaxation. The third is seeded global LP.
Why not just…?
Why not just sweep across the network greedily in spatial order? This is the most serious threat. A seeded front might be nothing more than a well-chosen greedy ordering. The seeded-sweep ablation uses exactly the same ordering and seeds without relaxation dynamics. If it matches our method, the relaxation contributes nothing and we will report that. We expect a gap in dense regions, because the relaxation lets undecided links ahead of the front negotiate before committing, whereas the sweep commits one link at a time.
Why not just solve the LP or integer program globally and round? At moderate sizes an integer-program solver can be run, and we use it as ground truth. The problem is millisecond latency at 1,000 links or more. Bazzi et al. show that global LP cannot use boundary information, and the half-integral MWIS relaxation gives rounding almost nothing to work with in ambiguous regions. The seeded-global-LP ablation tests this directly. We predict no gain from seeds, mirroring $\xi_{SC} = \xi_{GC}$. Seeded LP improving substantially would refute the transfer.
Why not just train a deeper end-to-end GNN and let it learn symmetry breaking? Scalability results for such GNNs (Graph Neural Networks for Scalable Radio Resource Management) rest on bounded receptive fields. The spatial deep learning scheduler still needed injected randomness to break ties. Depth alone does not give global coordination, and it gives no feasibility guarantee. We will nonetheless include a GNN with matched depth and parameters, trained end-to-end without seeds. If it matches our method, then the seeds are unnecessary.
Proposed Experiments
The first decisive check is the three-way factorial on one-dimensional highways, where ground truth is exact. The factors are seeds versus no seeds and local versus global solver, with sweep greedy as an extra arm. The expected signature is an interaction: seeds help only the local solver. We will also measure front speed and pinning as interference range grows relative to link spacing.
The second check uses two-dimensional random geometric graphs. Training follows the 50-pair setup used in prior work. Testing covers the FPLinQ 900-link configuration and the 1,250-link, 25×-area extrapolation from spatial deep learning. We report approximation ratio against exact MWIS on solvable instances, sum-rate and queue stability under Poisson traffic, message rounds and wall-clock latency, and quality as a function of seed spacing.
The third check is a negative control on Erdős–Rényi and Barabási–Albert graphs, which have no spatial locality. The seeded advantage should largely disappear there. A seeded advantage that persists on these graphs would mean the gain comes from something other than front propagation.
A final stress test uses dense deployments with long-range interference. The bounded-neighborhood assumption fails in that regime, and we expect pinning. Mapping where pinning begins is itself a result, because it would give the first operational analogue of a saturation threshold for scheduling.
References
- Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
- Threshold saturation of spatially coupled sparse superposition codes for all memoryless channels
- The glassy phase of Gallager codes
- Linear Programming Decoding of Spatially Coupled Codes
- Spatial Deep Learning for Wireless Scheduling
- Link Scheduling Using Graph Neural Networks
- Unfolding WMMSE Using Graph Neural Networks for Efficient Power Allocation
- Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis
- Congruence Decomposition with Neural Block Solvers for Large-Scale PCI Assignment
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Optimization of MIMO Device-to-Device Networks via Matrix Fractional Programming: A Minorization-Maximization Approach