Graph-Unfolded, Inversion-Free Beamforming with Locally Certified Step Sizes

Base stations with many antennas choose how to steer each user's signal by solving an optimization problem. The classical solvers either invert large matrices at every step, which costs cubic time in the antenna count, or avoid inversion but must then compute the largest eigenvalue of a large matrix to pick a safe step size. That eigenvalue costs the same cubic time. A recent fix, DeepFP, trains a neural network to predict the step sizes directly. It is fast, but it uses fixed-size feed-forward layers that cannot move to a different network layout, and its learned steps no longer guarantee that each iteration improves the objective. This proposal builds the step-size predictor as a graph neural network over the interference graph. A graph neural network is a model that updates each node by summing messages from its neighbors, so the same weights apply to any number of cells or users.

The main point is structural. The matrix whose largest eigenvalue sets the safe step for a given base station is a sum of rank-one contributions, one for each user that station's beams reach. That sum is laid out along the edges of the interference graph. Summing messages over a node's incident edges therefore has the same shape as the quantity being estimated. A cheap test then catches the learned steps that overshoot. Each iteration checks whether the objective went up, and if it did not, the step falls back to a conservative bound computed in quadratic time. Finally, a lightweight per-run diagnostic, borrowed from landscape analysis of black-box optimizers, decides whether a given channel instance should stop early or be handed to a slower solver. A colleague's two-sentence version is this: replace DeepFP's feed-forward step predictor with message passing over the interference graph, because the safe step is itself an edge-wise sum; then add a cheap ascent test so learned steps never make things worse.

Core Claim

Consider the inversion-free fractional-programming solver (FastFP) as described in DeepFP. For base station $i$, the update stays safe if its step parameter satisfies

$$\lambda_i \ge \lambda_{\max}\Big(\sum_{k \in \mathcal{N}(i)} w_k\, H_{ki}^H y_k y_k^H H_{ki}\Big).$$

Here $\mathcal{N}(i)$ is the set of users whose received signal depends on station $i$'s beams, which are its neighbors in the interference graph. $H_{ki}$ is the channel from station $i$ to user $k$, $y_k$ is user $k$'s auxiliary receive variable from the quadratic transform, and $w_k$ is user $k$'s rate weight. We will re-derive the exact matrix from FastFP's update before building anything; the proposal relies only on its sum-of-outer-products form.

That form gives two facts. First, the trace of the matrix, $\sum_k w_k \|H_{ki}^H y_k\|^2$, is always a valid bound and costs $O(N_t)$ per edge, where $N_t$ is the antenna count. Second, the trace is loose by up to a factor equal to the effective rank of the matrix, which produces timid steps. We claim that a graph neural network can learn a step that is tighter than the trace bound and nearly as tight as the true eigenvalue. It does this by aggregating per-edge features such as the norms above and pairwise inner products between the $H_{ki}^H y_k$ vectors of a node's strongest neighbors. Because this predictor is permutation-equivariant, it should transfer across cell counts, user counts and antenna counts without retraining. A per-iteration ascent test restores the monotone improvement that DeepFP gave up, and we will measure how often the test fires.

Relation to Prior Work

Two unfolded wireless solvers motivate the gap from opposite sides. Deep Graph Unfolding for Beamforming in MU-MIMO Interference Networks unrolls the classical WMMSE algorithm (weighted minimum mean squared error, an iterative beamforming method) into layers driven by a complex-valued graph neural network. It reports zero-shot transfer from 20 to 100 users and a 24x speedup, 54 ms versus 1,305 ms per sample. However, it keeps the matrix inversions inside each WMMSE layer. DeepFP removes both the inversions and the eigenvalue computation, but it predicts step sizes with feed-forward blocks and gives up monotone convergence. We take DeepFP's algorithmic skeleton and UWMMSE's relational parameterization. The new ingredient is the observation that the eigenvalue being replaced decomposes over graph edges. That observation gives a principled reason for using message passing here rather than merely a convenient one.

The inversion-approximation literature supplies the stress tests. Neumann-series FPGA detection works when channel columns are nearly orthogonal, a regime called channel hardening. Tridiagonal approximation shows that spatial correlation breaks diagonal dominance. LcgNet shows that learned step sizes speed up an unrolled conjugate-gradient solver but are fixed across channel draws. We expect the gap between the trace bound and the true eigenvalue to vary sharply with correlation. A step predictor that ignores channel structure, like LcgNet's fixed steps, should therefore fail exactly there, and that is where our method has to prove itself.

Landscape analysis supplies the per-run diagnostic. Per-run algorithm selection with warm-starting extracts features from the first $30 \cdot D$ evaluations of CMA-ES, where $D$ is the problem dimension, and uses them to hand off to a better solver mid-run. Fitness landscape analysis for RIS beamforming shows that sum-rate landscapes become rugged as arrays grow, with fitness-distance correlation dropping toward zero. That work only characterizes landscapes offline. We use trajectory features of the unrolled layers themselves, such as per-layer objective gains, the ratio of predicted step to trace bound, and how often the ascent test fires. These features predict whether an instance will end far from what a longer FastFP run reaches. The setting differs from the black-box one because our "solver trajectory" comes free with the forward pass, so the sampling-overhead problem of landscape analysis disappears.

Conflict graphs play a supporting role. Mahajan's mesh-network study and the channel-access work reduce interference to binary edges. That is too coarse for beamforming, but it is a useful way to sparsify which users enter $\mathcal{N}(i)$. Sparsification is safe here only because the trace bound tells us how much eigenvalue mass a dropped edge can carry. This replaces the hand-tuned threshold of EGNN's edge drop with a certified one. We do not attempt the submodular scheduling of Chekuri et al.; that is a separate problem.

Research Program

The first stage is analysis. We will derive FastFP's exact per-station matrix and its trace bound. On simulated channels we will measure the ratio of the true eigenvalue to the trace bound as spatial correlation and user density vary. If that ratio stays near one everywhere, the trace bound alone suffices and the learned predictor has no purpose. We would then report that result and stop.

The second stage builds the model. Each unfolded layer is one FastFP iteration with no inversion. A shared complex-valued graph neural network reads per-edge features and outputs a multiplier $\alpha_i \in (0,1]$ applied to the trace bound. Constraining the output this way keeps every predicted step within a known safe-or-tighter range. Training maximizes weighted sum rate summed across layers.

The safeguard comes next. After each layer we evaluate the surrogate objective, which costs one pass over the edges. If it decreased, station $i$ recomputes its step with three power-iteration matrix-vector products, $O(N_t^2)$, and repeats the update.

The third stage trains the trajectory diagnostic. A small classifier reads the features from the first $L_0$ layers and outputs one of three actions: stop, continue, or hand off to FastFP warm-started from the current beams.

All costs stay at or below $O(N_t^2)$ per station per iteration. The common case is $O(N_t)$ per edge.

Baselines

The naive reference is FastFP run for 100 iterations with exact eigenvalue steps, as in DeepFP's setup. It defines the 100% weighted-sum-rate mark and the CPU-time denominator. We also include classical WMMSE run to convergence on the same channels.

The strongest existing competitor is DeepFP, which reports 97.4% of FastFP's weighted sum rate at 11.7% of its CPU time on the 7-hexagonal-cell, 64-antenna benchmark. It also reports roughly 97% optimality when tested at 16 to 56 antennas. We will reimplement it on our channel generator with the same layer count and the same training set and tuning budget as our model. Our model must match its in-distribution weighted sum rate within 0.5 percentage points. It must also beat it clearly on transfer to unseen cell counts and correlated channels, where we expect DeepFP to need retraining. A second relational competitor is UWMMSE. It is run with equal layers and parameters, and we report its accuracy together with its cost, since its layers still contain inversions.

Two cheap non-learned step rules are serious competitors. The first is FastFP with the trace-bound step. The second is FastFP with a three-step power-iteration estimate of the eigenvalue. Both receive the same iteration budget as our unrolled model.

The ablations isolate the key ingredient. The first swaps the graph network for a per-station MLP over the same features. This is essentially DeepFP with our features and tests whether the graph structure matters. The second removes the ascent safeguard. The third uses the full interference graph instead of the bound-certified sparse graph. The fourth replaces the trajectory diagnostic with a fixed rule: stop when the relative objective gain falls below a threshold.

Why not just…?

Why not just estimate the eigenvalue with a few power iterations instead of learning anything? This is the most serious threat. Three matrix-vector products per station cost $O(N_t^2)$, which is far below the $O(N_t^3)$ that DeepFP set out to remove, and no training is needed. The file contains no reported result for power-iteration-stepped FastFP, so we cannot dismiss it. The proposal runs it as a first-class baseline. Our model must reach the same weighted sum rate in fewer iterations or at lower wall-clock time, by learning steps more aggressive than the eigenvalue bound, as LcgNet's halving of iterations suggests is possible. If it cannot, we will report that the learned component is unnecessary and that safeguarded power iteration is the right practical answer.

Why not just use the trace bound, which is already $O(N_t)$? It is safe but conservative. The first-stage measurement of the eigenvalue-to-trace ratio decides this directly. Under strong correlation, few dominant interferers make the matrix nearly low-rank, so the ratio stays close to one and the bound becomes nearly tight. Under rich scattering with many users, the matrix approaches full rank, the ratio can approach $1/N_t$, and the bound becomes very loose. A large ratio spread is the precondition for this work.

Why not just keep DeepFP and retrain it for each layout? Retraining is feasible offline, but cell counts, active users and antenna subsets change online. The transfer experiments measure how much DeepFP loses without retraining. If the loss stays under one percentage point, the equivariance argument is weak in practice, and we will say so.

Why not just stop when the objective plateaus instead of using landscape features? A plateau rule cannot tell a good stationary point from a poor one. Whether the trajectory features add anything is an empirical question. The diagnostic is kept only if it reduces the fraction of runs ending more than 5% below FastFP-100, at equal average compute, relative to the plateau rule.

Proposed Experiments

The main benchmark follows DeepFP's 7-hexagonal-cell setup: 64 transmit antennas, users with 4 receive antennas, path loss, shadowing and Rayleigh fading. We add Kronecker-correlated channels following the tridiagonal-approximation paper's correlation model, and layouts with 3, 7 and 19 cells. The metrics are weighted sum rate as a percentage of FastFP-100, CPU time, multiply-accumulate count, the per-iteration rate of objective decrease, and the fraction of iterations where the safeguard fires.

The first decisive check is transfer. We train on 7 cells and 64 antennas, then test zero-shot on 3 and 19 cells, on 16 to 56 antennas, and at correlation coefficients up to 0.9. The graph model should keep at least 95% of FastFP-100 where DeepFP drops further.

The second check compares against power iteration at matched wall-clock time. This is the result that decides whether learning earns its place.

The third check tests the safeguard. Removing it should increase objective decreases mainly on correlated channels, and keeping it should cost under 10% extra time.

The fourth check tests sparsification. The bound-certified sparse graph should match full-graph accuracy at lower message cost, and should beat EGNN-style fixed-threshold pruning when the threshold is tuned on one correlation level and tested on another.

A negative outcome on the second check together with a positive outcome on the third would still be publishable. It would mean that inversion-free beamforming needs a safeguard more than it needs a learned step predictor.