Some neural networks compute their output by repeating one layer until the result stops changing. These are called equilibrium or implicit models. To guarantee that this repetition settles to a single answer, practitioners make the layer a contraction: every pass shrinks differences between inputs by at least a fixed factor $\kappa<1$. In a multi-hop wireless network, where relays forward packets for one another over several radio links, this guarantee has a direct physical cost. Each repetition of the layer is one round of messages exchanged between neighboring radios. Information from a node $h$ hops away arrives attenuated by roughly $\kappa^h$, and a node's sensitivity to channel-measurement errors grows like $1/(1-\kappa)$. Under the usual way of enforcing contraction, one factor $\kappa$ therefore sets three things at once: how far information can travel, how many communication rounds are needed, and how robust the output is. This is the stability-expressivity tradeoff stated in network terms.
Our claim is that a contraction budget can be spent unevenly, and that spending it unevenly removes much of the reach penalty. Existing equilibrium graph networks spread each node's budget across all of its neighbors. A node with $d$ neighbors then passes on roughly $\kappa/d$ of any one neighbor's signal, which washes out long-range information. If each node instead puts its budget on one or two incoming links, those links become "highways" that carry a specific distant signal with gain near $\kappa$ per hop. The guarantee, the round count, and the robustness bound stay exactly the same. The hard part is deciding which links become highways. Once a link is excluded, it receives no gradient, so the choice locks in early. Dynamic sparse training was developed for exactly this lock-in problem: it periodically drops weak connections and regrows promising ones. We repurpose it to train the sparse propagation graph of a certified equilibrium model. We then use that model to predict link schedules for delay-aware routing in multi-hop wireless networks.
Core Claim
We build on Implicit Graph Neural Networks (IGNN). IGNN solves $X=\phi(WXA+B(U))$ and guarantees a unique solution whenever $\|W\|_\infty<\lambda_{pf}(A)^{-1}$, where $\lambda_{pf}$ is the largest eigenvalue of the nonnegative coupling matrix $A$. We replace the fixed adjacency $A$ with a learned, gated coupling $G$:
$$X=\phi\big(WXG+B(U)\big),\qquad \sum_j G_{ij}\le 1 \ \text{and}\ |\{j: G_{ij}>0\}|\le k \ \text{for every node } i,\qquad \|W\|_\infty\le\kappa<1.$$
Here $X$ is the matrix of node states, $U$ the node and link features (channel gains, conflict relations, queue statistics), $B$ an input encoder, and $\phi$ a non-expansive activation. Each entry $G_{ij}\ge 0$ is the gate on the message from node $j$ to node $i$. It is produced by a small edge scorer and kept nonzero only on node $i$'s top-$k$ candidate links. A nonnegative matrix's largest eigenvalue is at most its largest row sum, so the row cap gives $\lambda_{pf}(G)\le 1$ for any graph. IGNN's well-posedness condition therefore holds for every network size and density.
This matters for scaling. With raw physical coupling, a model trained on 60-node graphs has no guarantee on denser 110-node graphs, because $\lambda_{pf}(A)$ grows. Row-normalizing $A$ avoids that problem but discards the interference magnitudes that scheduling depends on. Our gated coupling keeps the magnitudes as scorer inputs while making the guarantee independent of graph size.
The same construction gives two budgets that do not depend on network size. Distributed execution to tolerance $\varepsilon$ needs about $\log(1/\varepsilon)/\log(1/\kappa)$ message rounds with at most $kn$ messages per round. A perturbation $\Delta U$ of the channel inputs moves the fixed point by at most $L_B\|\Delta U\|/(1-\kappa)$, where $L_B$ is the encoder's Lipschitz constant. Both bounds follow from the Banach contraction argument. The sparsity level $k$ appears in neither the guarantee nor the robustness bound. It only changes where the budget goes. That is why we expect concentration to improve reach without costing stability.
Research Program
The work has three parts.
Reach analysis. We first show the reach effect where it can be isolated cleanly. On a chain graph, IGNN's bound with unnormalized adjacency ($\lambda_{pf}\approx 2$) limits the per-hop gain to about $1/2$. Concentrating each node's budget on its upstream neighbor allows a gain near $\kappa$. The predicted gap in usable chain length is roughly a factor of $\log 2/\log(1/\kappa)$, which is large when $\kappa$ is near 1. We will test this prediction quantitatively, not just observe that "concentration helps."
Training rule. The second part is the training rule for $G$. Hard top-$k$ selection, and also its differentiable relative sparsemax, give zero gradient to links outside the current support. We adopt the remedy from Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win (RigL), which showed that periodically regrowing connections with large dense gradients restores gradient flow in sparse networks. Every $\Delta T$ steps, we compute the implicit-gradient signal on all candidate links. At each node we drop the lowest-contribution active gates and boost the scores of the excluded links with the largest gradients. The row cap is kept throughout, so the model stays certified at every step of training, not only at the end.
Two prior results shape this rule. Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training argues that exploring many supports over time recovers dense-like capacity, which motivates measuring how much of the candidate graph is ever visited. Fantastic Weights and How to Find Them shows that a too-short $\Delta T$ prunes connections before they mature. Equilibrium models add a specific reason for caution here. A rewiring event moves the fixed point by at most $\|\Delta G\|$ times a constant over $(1-\kappa)$, so we cap the gate mass changed per event. This keeps warm-started solvers within a few iterations of the new solution, which addresses the rewiring-instability concern raised for constrained architectures.
Application. The third part targets a concrete multi-hop task. Delay-aware Backpressure Routing Using Graph Neural Networks and Biased Backpressure Routing Using Link Features and Graph Neural Networks train a dense feedforward GNN on the link conflict graph to predict each link's scheduling duty cycle $x_e$. They then bias backpressure routing, which forwards packets according to local queue differences, using $1/x_e$ as a distance. We substitute our certified sparse equilibrium model for the duty-cycle predictor and leave the rest of their routing pipeline unchanged. This gives three things the dense predictor lacks: a stated message-round budget for distributed execution, a hard sensitivity bound on how channel-estimation errors propagate into routing biases, and well-posedness on networks larger than those seen in training.
Two further papers mark what we take and what we do not. Exploring the impact of adaptive rewiring in Graph Neural Networks applies dynamic sparse training to GNN weight matrices for parameter efficiency. We rewire the message graph of an implicit model in order to allocate a contraction budget, which is a different object and a different goal. Stability Analysis of Unfolded WMMSE for Power Allocation derives perturbation bounds for an unfolded power-allocation GNN; WMMSE is the standard iterative power-control algorithm. Its bounds come from truncated Taylor expansions and hold only approximately. We obtain an exact bound by construction, at the risk of it being looser.
Baselines
The naive reference point is the original duty-cycle-biased backpressure system of Biased Backpressure Routing Using Link Features and Graph Neural Networks. It uses a dense explicit GNN with no stability constraint and is retrained on our simulator with the authors' training range of 20–60 nodes and test sizes up to 110. It is the strongest existing method on this exact task. Under bursty traffic its expQ variant delivers "99%+" of packets, where basic backpressure delivers under 15%. The delay-aware version reports roughly 50–66% latency reduction over hop-count-biased backpressure (EDR-10) under unit-disk interference (Delay-aware Backpressure Routing Using Graph Neural Networks). We do not expect large gains in latency or delivery over this baseline. Beating it means matching its delivery rate and staying within a few percent of its latency at 110 nodes, while using a stated, smaller number of message rounds and messages, and holding a certified sensitivity bound that it cannot provide. Losing means a latency gap that persists after equal tuning.
The strongest constrained competitor is IGNN itself, run with the same encoder and the same $\kappa$. It is used two ways: with dense physical coupling, which is uncertified at larger test sizes, and with row-normalized coupling, which is certified but blind to interference magnitudes. This baseline isolates the claim that concentrating the budget is what matters. On generic graphs the reported IGNN figure is 97.6% Micro-F1 on PPI, against 97.3% for GAT and 59.2% for GCN. On Chains it maintains "near-perfect accuracy," with no exact number reported on Lacuna, while GCN and GAT fall to chance (Implicit Graph Neural Networks).
Three ablations isolate the training ingredient. The first is hard top-$k$ selection without regrowth. The second is budgeted sparsemax gating. The third is a static mask that keeps each node's $k$ strongest-interference links by channel gain. All variants share the scorer architecture, hyperparameter search budget (equal trials per method), training steps, and simulator seeds. They are compared at matched $k$ and $\kappa$.
Why not just…?
Why not just keep each node's $k$ strongest-interference links and skip learned rewiring? This is the most serious threat. Physically strong couplings may well be the right highways. The cited literature does not settle the question for message graphs: the static-versus-adaptive comparison in Exploring the impact of adaptive rewiring in Graph Neural Networks concerns weight masks. Our reason to expect a gap is task-specific. A link's duty cycle depends on downstream bottlenecks along routes to destinations, and those need not be the strongest interferers. If the static gain mask comes within noise of the learned one on the conflict-graph benchmark, we will report that the contribution reduces to the budget-concentration principle plus a physical heuristic. That would still be useful, but it would be a narrower result.
Why not just use softmax or sparsemax attention, which already sums to the budget? Softmax with each row scaled to $\kappa$ satisfies the same certificate. However, it never produces exact zeros, so the message count per round stays at full degree. Sparsemax does produce exact zeros, but it gives zero gradient outside the support, which is the same lock-in that RigL's regrowth is designed to break. The sparsemax ablation at $k\in\{1,2\}$ is the experiment that decides whether regrowth earns its place. If the two match, we drop dynamic sparse training from the method.
Why not just use a deep explicit GNN, or a weight-tied recurrent one run for more rounds? An explicit network reaches only as many hops as it has layers, and it oversmooths when stacked deeper (Implicit Graph Neural Networks). A weight-tied recurrent GNN run for more rounds at test time than in training has no convergence or sensitivity guarantee. The 110-node generalization test and the channel-perturbation test show directly whether these failure modes appear in practice.
Why not just loosen the contraction uniformly toward $\kappa\to1$? Lipschitz Multiscale Deep Equilibrium Models shows that the tradeoff is real in both directions. Relaxing the constraint to $L=1$ recovers accuracy only partially (91.44%, compared with 90.47% at $L=0.03$ and 93.23% unconstrained on CIFAR-10). It also gives up speed, from a 4.75× speedup at $L=0.03$ to 3.33× at $L=1$. In our setting, the bounds above make the cost explicit: $1/(1-\kappa)$ worsens robustness and the round count grows. We sweep $\kappa$ for the dense and concentrated models together. The hypothesis is that, at matched accuracy, the concentrated model needs a smaller $\kappa$ and therefore fewer rounds and a tighter robustness bound.
Decisive Experiments
On Chains, we plot accuracy against chain length at fixed $\kappa\in\{0.5,0.8,0.95\}$. The predicted outcome is that the concentrated model extends the usable chain length by roughly the factor derived above, while dense IGNN at the same $\kappa$ degrades earlier. On PPI, concentration should cost no more than a fraction of a point relative to IGNN's 97.6%. This checks that the method does not damage performance on graphs where reach is not the bottleneck.
On the 2D point-process conflict-graph benchmark, we run interface and unit-disk interference models with stationary and mobile topologies. We train on 20–60 nodes and test up to 110. We report end-to-end latency, delivery rate under bursty traffic, message rounds, and messages per decision.
We then inject channel-estimation errors of increasing size and measure two things: the change in predicted duty cycles against our certified bound, and the resulting change in latency. As a reference point for bound tightness, the Taylor bound for unfolded WMMSE fit about 66% of nodes tightly and was violated in about 4% of cases (Stability Analysis of Unfolded WMMSE for Power Allocation). We expect zero violations and will report how loose our bound is.
The project succeeds if three things hold together. Concentration must beat uniform coupling at matched $\kappa$. Regrowth must beat sparsemax and the static gain mask at small $k$. Routing performance must stay near the dense baseline while using fewer rounds and holding a certificate. If concentration helps on Chains but not on the wireless task, that tells us duty-cycle prediction is not limited by reach, and that negative result is worth publishing on its own.
References
- Implicit Graph Neural Networks
- Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win
- Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training
- Fantastic Weights and How to Find Them: Where to Prune in Dynamic Sparse Training
- Delay-Aware Backpressure Routing Using Graph Neural Networks
- Biased Backpressure Routing Using Link Features and Graph Neural Networks
- Exploring the impact of adaptive rewiring in Graph Neural Networks
- Stability Analysis of Unfolded WMMSE for Power Allocation
- Lipschitz Multiscale Deep Equilibrium Models: A Theoretically Guaranteed and Accelerated Approach