Multigrid-Preconditioned Neumann Layers for Global, Boundary-Respecting Context

Convolutional networks and graph networks see only a small neighborhood per layer, so information from far away must be relayed through many layers. Each relay blurs it, and the useful influence region ends up a narrow central blob rather than the whole input. A natural fix is to let each layer solve a small linear system: for a learned, edge-aware affinity between neighboring pixels or nodes, compute $(I-\alpha W)^{-1}$ applied to the features. This operation spreads information across an entire region and stops at boundaries where affinities are low, much like a random walk that cannot cross edges. The inverse can be approximated by a Neumann series, the matrix analogue of $1/(1-x)=1+x+x^2+\dots$, which needs only repeated sparse multiplications.

The obvious version of this idea fails. A plain $K$-term series over a local operator is just $K$ shared-weight local steps, and symmetric diffusion travels only about $\sqrt{K}$ pixels in $K$ steps. Reaching across a large region therefore needs a number of terms that grows with the square of its diameter, and taking $\alpha$ close to 1 makes the series converge slowly or blow up. We propose to fix exactly this failure with a coarse correction built from the same learned affinities, borrowed from algebraic multigrid. The correction preconditions the series, so a handful of terms reaches the whole region and the truncation error is set by a spectral radius we can measure and control during training.

Core Claim

A layer that computes a learned resolvent by a preconditioned, truncated Neumann expansion can match the boundary-respecting long-range transport of exact inversion. It uses linear cost and a fixed small number of sparse multiplications, and its reach no longer depends on region size. Concretely, let $W_\theta(x)$ be a sparse, row-normalized, content-dependent affinity on the 4- or 8-neighbor grid (or the graph's edges), let $b$ be the layer input, and let $C$ be a coarse-grid correction. $C$ is formed by aggregating nodes with weights derived from $W_\theta$ itself, solving the small coarse system exactly, and adding one local smoothing step. The layer output is

$$ y_K=\sum_{k=0}^{K} G^k\,C\,b,\qquad G = I - C\,(I-\alpha W_\theta), $$

where $y_K \to (I-\alpha W_\theta)^{-1}b$ as $K$ grows. The relative error after $K$ terms is bounded by $\|G\|^{K+1}$, which approaches $\rho(G)^{K+1}$ for well-behaved $G$; here $\rho(G)$ is the spectral radius of the preconditioned iteration. The multigrid property we want to establish empirically is that $\rho(G)$ stays well below 1 as regions grow, while the unpreconditioned radius $\alpha\rho(W)$ approaches 1. Three things would be new together: the resolvent is learned and content-dependent; the coarse level acts as a preconditioner whose errors are corrected at the fine level rather than baked in; and convergence is monitored and regularized through $\rho(G)$.

Where This Sits

Two papers motivate the design by showing the two halves separately. NRKNet unrolls a truncated Neumann series of a spatially varying blur operator for defocus deblurring. It evaluates higher-order terms on downsampled maps, which shows that coarse resolution is needed to make the series reach far. However, its operator is a fixed physics model, its cross-scale fusion is heuristic, and it gives no convergence control. We replace the heuristic fusion with an algebraic preconditioner and the physics operator with a learned affinity. IM-MPNN widens the reach of graph networks by running message passing on Graclus-coarsened graphs linked by mixing layers. It frames coarsening as raising a diffusion constant, but the fixed clustering can merge unlike nodes, and nothing undoes that error. In our layer, coarse aggregation is driven by the learned affinities, and the fine-level Neumann terms correct whatever the coarse solve gets wrong.

The Neumann line also constrains the design. The multiplication-only inversion for Gated DeltaNet shows that truncated series made only of matrix multiplications run 5.2x faster than forward substitution on NPUs. That paper also shows the trick relied on nilpotent triangular matrices and that higher powers overflowed FP16 at larger sizes. Our layer must therefore keep $\rho(G)$ small, which bounds the dynamic range of $G^k$ for the same reason. Graph sampling via Neumann series expands graph-filter inverses into low-pass polynomial powers on static graphs. We reuse the shift-and-expand idea but make the operator learned and precondition it. Finally, Unperturbed and low-rank inverse perturbation bounds show that Neumann and contour expansions give much tighter error tracking under random noise than worst-case bounds. We use them only as an analysis lens for how input noise propagates through $y_K$, not as the mechanism.

Learned spatial-propagation layers exist in the broader literature but are not in this file. Our novelty claim therefore rests on the preconditioned, convergence-controlled form, not on resolvent propagation alone.

Research Program

We will build the layer for grids and graphs from one code path. The fine level costs $K$ sparse matrix–vector products. The coarse level is applied recursively, V-cycle style, until the system has a few hundred nodes and can be inverted densely, so total cost stays linear in $N$. Aggregation assigns each fine node to a coarse node using affinity-weighted soft assignments computed from $W_\theta$. We will compare this against fixed Graclus or fixed $2\times2$ pooling to isolate the benefit of content-aware coarsening.

During training we estimate $\rho(G)$ with a few steps of power iteration per batch. We add a hinge penalty when it exceeds a target such as 0.5, which directly addresses the divergence problem the Neumann literature flags. We will backpropagate through the unrolled sum.

We will also allow $W_\theta$ to be non-symmetric. A directional, drift-carrying operator moves information about $K$ steps rather than $\sqrt{K}$. Asymmetry helps suggests that non-symmetric operators can also reduce noise bias. We treat this as a secondary arm, because general rank-$r$ non-Hermitian analysis is open.

On the analysis side, we will measure the effective receptive field (gradient magnitude of an output with respect to inputs, as a function of distance) in the style of Luo et al.. We expect plain truncation to show the Gaussian profile described there, and the preconditioned layer to show region-shaped profiles that end at boundaries. We will also inject random feature noise at distant locations and compare measured corruption of $y_K$ against first-order Neumann predictions.

Baselines

The naive reference is the same backbone with the layer replaced by $K$ additional shared-weight local propagation steps, or equivalently the unpreconditioned series $\sum_{k\le K}(\alpha W_\theta)^k b$. It uses identical parameters and FLOPs, and it is the core ablation: if preconditioning matters, this variant should lose specifically on long-distance tasks. A second ablation keeps only the coarse correction $Cb$ with no fine-level terms. This variant is essentially a learned multiscale pooling layer, and it tests whether the fine-level Neumann correction contributes anything. A third ablation swaps affinity-driven aggregation for fixed Graclus or grid pooling.

On graphs the strongest competitor is IM-MPNN. It reports up to 41% relative improvement over GCN on LRGB superpixel graphs and 10% to 16.5% accuracy gains on City-Networks, and it keeps 100% accuracy on CliquePath up to 37 hops where GCN fails after 7. No reported absolute accuracy for LRGB or City-Networks was found on Lacuna, so we will rerun IM-MPNN from its released configuration on identical splits. The comparison will match parameter count, wall-clock training budget, and hyperparameter search trials. Beating it means higher accuracy on City-Networks at matched cost, and perfect CliquePath accuracy beyond 37 hops.

On images the strongest efficient competitor is SegNeXt, whose base model reports 82.6% mIoU on Cityscapes at 275.7G FLOPs. CCNet reports 81.9% mIoU on Cityscapes test and 45.76% on ADE20K validation, and it serves as the global-attention reference. We will insert our layer into the SegNeXt-Tiny and SegNeXt-Base heads with FLOPs matched by removing strip-convolution branches, and train under the same schedule. Beating SegNeXt means at least matching mIoU at no higher FLOPs while improving boundary F-score and accuracy on large, thin, or fragmented classes. An overall mIoU tie with clear boundary gains would count as a partial result, not a win.

Why not just…?

Why not just stack more local layers or use the plain truncated series? Plain diffusion reaches about $\sqrt{K}$ in $K$ steps. The effective receptive field of deep local networks is known to be a centrally concentrated Gaussian much smaller than the theoretical one (Luo et al.), and standard GCN fails on CliquePath after 7 hops (IM-MPNN). Our first ablation runs exactly this alternative at matched cost. If it matches the preconditioned layer on CliquePath and City-Networks, the proposal fails.

Why not just use multiscale coarsening such as IM-MPNN or a U-Net hierarchy? This is the real threat, because coarse levels alone already give long reach. Our argument is that fixed coarsening merges dissimilar nodes, a limitation the file notes for Graclus, while our fine-level terms correct coarse errors and our aggregation follows learned affinities. The coarse-only ablation and the Graclus-swap ablation settle this question. If coarse-only matches the full layer, we will report that the Neumann correction is unnecessary.

Why not just use strip convolutions, criss-cross attention, or Fourier gating for global context? Strip kernels in SegNeXt reach only a fixed distance (up to 21 pixels). Criss-cross attention in CCNet costs $O(N\sqrt{N})$ and needs two sequential passes. Butterworth gating in ABFNet is content-independent in its basis and requires regular grids. None of them propagates along content-defined regions. On Cityscapes these methods may well tie us on overall mIoU, so the decisive image comparison is on boundary accuracy and large-object consistency, not the headline number.

Proposed Experiments

The first check is mechanistic. On synthetic grids with piecewise-constant regions of growing diameter, and on CliquePath with path lengths from 7 to well beyond 37 hops, we will plot task accuracy and measured $\rho(G)$ against distance for the plain series, coarse-only, and the full layer, all with fixed $K$. The prediction is that only the full layer keeps $\rho(G)$ flat and accuracy at ceiling as distance grows.

The second check runs on City-Networks (100–400 hop road graphs) and the LRGB PascalVOC-SP and COCO-SP superpixel graphs against rerun IM-MPNN at matched budget. We will report accuracy alongside receptive-field profiles.

The third check runs on Cityscapes and ADE20K against SegNeXt and CCNet, reporting mIoU, boundary F-score, FLOPs, and latency. It also includes an INT8 run that tests whether bounding $\rho(G)$ avoids the overflow observed in the DeltaNet inversion work.

The fourth check is a noise-propagation study comparing measured and predicted distant-noise corruption. A clean negative on the coarse-only ablation, meaning the full layer is no better, would be the clearest signal to abandon the Neumann component.