Exact All-Pairs Affinity Supervision for Global Pixel Routing

Convolutional networks see only a small window of the image at each layer, so two pixels on opposite ends of the same bus are only linked after many layers of stacking and downsampling. Attention modules fix this by letting every pixel look at every other pixel, but the pixel-to-pixel table grows with the square of the image size. Existing fixes therefore restrict who can talk to whom. Rows and columns only, in criss-cross attention. A fixed grid of pooled anchors, in asymmetric non-local blocks. Hash collisions, in sampling-based attention. In all of these, which pixels end up linked is learned only indirectly, through the final per-pixel classification loss. No method supervises the full table of pixel pairs, because that table is too large to score.

This note proposes to borrow a trick from sparse network modeling, the Bernoulli-Poisson link, to supervise that full table at linear cost. Under this link, an edge is present when a hidden Poisson count is above zero, and the cost of all absent edges collapses into one sum. Concretely, each pixel gets a small non-negative membership vector. Two pixels "link" with probability $1 - e^{-z_i^\top z_j}$. The likelihood over every pair of pixels in the image, including every pair that should not link, can then be computed exactly in time proportional to the number of pixels. The same membership vectors serve as the routing weights of a global attention block. The result is a long-range module whose connections are trained directly to answer "do these two pixels belong to the same segment?" over all of the image's roughly $N^2$ pairs, not a sampled few.

Core Claim

The Bernoulli-Poisson link was developed for graphs that are genuinely sparse. Infinite Edge Partition Models showed that, with this link, the non-edge term $\exp(-\sum_{(i,j)\notin E}\theta_{ij})$ can be computed in bulk as "all pairs minus observed edges". This makes inference scale with edges rather than with node pairs. Pixel same-segment graphs are not sparse: a road class can cover a third of the image. That observation is the reason the obvious transplant, "Bernoulli-Poisson attention", is uninteresting on its own. With $\theta_{ij} = z_i^\top z_j$ and $z_i \ge 0$, normalized attention over $\theta$ is just linear attention with non-negative features.

The claim here is different. For segmentation supervision, the dense positive structure is itself block-structured: same-class pairs form one block per class. So both the all-pairs term and the same-class term factorize through per-class sums of $z$. Let $z_i \in \mathbb{R}^K_{\ge 0}$ be pixel $i$'s membership vector, $\mathcal{C}_c$ the labeled pixels of class $c$, and $s = \sum_i z_i$, $s_c = \sum_{i\in\mathcal{C}_c} z_i$. The exact negative log-likelihood over all labeled pixel pairs is

$$ \mathcal{L}_{\text{BP}} = \underbrace{s^\top s - \sum_c s_c^\top s_c}_{\text{all different-class pairs, exact, } O(NK)} \;-\; \sum_c \sum_{i,j\in\mathcal{C}_c} \log\!\left(1 - e^{-z_i^\top z_j}\right). $$

The first part is exact and costs $O(NK)$. Only the same-class part needs sampling. That sampling is unbiased if we draw pairs uniformly within each class and reweight by $|\mathcal{C}_c|^2$. Its variance is bounded because $\log(1-e^{-\theta})$ saturates toward zero for large $\theta$, so confident positives contribute almost nothing. The diagonal $i=j$ is subtracted in both terms.

The hard part of the problem is the long-range negatives: distant pixels that look alike but belong to different classes. That part is scored exactly over every pair. A logistic affinity loss cannot do this, because $\log(1+e^{\theta})$ does not factorize.

The routing block uses the same $z$ to compute $y_i = \sum_j \theta_{ij} g(x_j) / \sum_j \theta_{ij}$ in $O(NK)$. Here $x_j$ is the backbone feature at pixel $j$ and $g$ is a learned linear map. Read through the edge-partition lens of Zhou, each of the $K$ coordinates is a soft, overlapping "community" of pixels. Every message passes through these $K$ content-defined hubs. They play the role of anchors, but their shapes are learned and supervised rather than fixed by a pooling grid.

Research Program

We build three pieces.

The first is a membership head: a $1\times1$ convolution followed by softplus, producing $z$ at output stride 8 on a dilated ResNet backbone.

The second is the linear-cost routing block above, inserted where CCNet and the asymmetric pyramid block are inserted. The block output is added back to the backbone features as a residual.

The third is the loss $\mathcal{L}_{\text{BP}}$, added to the standard per-pixel cross-entropy with weight $\lambda$.

GPGBN supplies the template. It couples a neural encoder to a Bernoulli-Poisson link decoder, reaching 96.5% link-prediction AUC on CiteSeer. It also warns that such couplings are sensitive to the loss-balancing weight. We therefore treat $\lambda$ as a first-class object: we report the full sweep, and also try normalizing $\mathcal{L}_{\text{BP}}$ by the number of labeled pairs so that one $\lambda$ transfers across datasets.

SDREM constrains the design. It reports that latent-count signals become diffuse when observed links fall below half. That is why we keep positives dense and supervised rather than inferred, and why we avoid Gibbs-style latent count propagation altogether. We use plain backpropagation through the closed-form likelihood. Related deep Bernoulli-Poisson models, HLFM and SDREM, assume a given graph. Our graph is supplied by labels at training time and predicted from features at test time.

Two analyses accompany the main results. The first measures how well the learned $1-e^{-\theta}$ predicts same-class membership on held-out pixel pairs, bucketed by spatial distance. This tests whether the routing actually carries long-range information. The second sweeps $K$, to find where the low-rank membership bottleneck stops capturing class structure. With $K$ below the number of classes, communities must be shared across classes, and this is the main way the idea could fail.

Baselines

The naive reference point is the dilated ResNet with per-pixel cross-entropy and no long-range module, plus the same network with a dense Non-Local block at the resolution where it fits in memory. The dense block shows what full attention buys when it is affordable.

The strongest existing competitor on accuracy is CCNet. Its recurrent row-and-column attention reaches a global receptive field in two passes. It reports 81.9% mIoU on the Cityscapes test set and 45.76% mIoU on ADE20K validation.

The strongest competitor in spirit is the Asymmetric Non-local Network. Its pyramid block pools keys into fixed anchors, the closest analogue to our learned hubs. It reports 81.3% on Cityscapes test, 45.24% on ADE20K validation and 52.8% on PASCAL Context.

CGNL linearizes non-local attention with a Taylor expansion and is included as the kernel-approximation competitor. No reported segmentation result was found on Lacuna for CGNL; the file gives only video and fine-grained classification numbers.

Fairness rules apply to every method. All are reimplemented on one codebase with the same backbone, output stride, crop size, iteration count and augmentation. Each gets the same number of hyperparameter trials (for example, eight); ours spends its trials on $\lambda$ and $K$. We report validation mIoU averaged over three seeds. For Cityscapes validation, no reported result was found on Lacuna for CCNet or the asymmetric network, so our reimplementations define the bar. Cited test numbers are context, not the comparison.

Two ablations isolate the key ingredient. The first is the identical routing block trained with cross-entropy only; this is plain non-negative linear attention. The second is the identical block with a logistic pairwise affinity loss using sampled negatives, at a pair budget matched in compute.

Beating the competitors means one of two things. Either we exceed the reimplemented CCNet's validation mIoU on Cityscapes and ADE20K by more than seed variance. Or we match it while using less memory at full resolution, and also beat both ablations on long-range pairwise AUC.

Why not just…?

Why not just use linear attention with non-negative features? Architecturally that is exactly our block. The only difference is the loss, so the cross-entropy-only ablation answers this directly. If it matches the full model on mIoU and on long-range pair AUC, the Bernoulli-Poisson supervision contributes nothing and the proposal fails. We state this openly.

Why not just add a sampled pairwise affinity loss with a sigmoid link? This is the real threat. With enough sampled pairs it may match ours. Our argument is specific: confusable long-range different-class pairs are rare among uniformly sampled pairs, and only the Bernoulli-Poisson form scores all of them exactly. The pair-budget sweep settles it. We vary sampled negatives from $10^3$ to $10^6$ per image and plot mIoU and far-distance AUC against wall-clock time. Ours should dominate at equal cost and be matched only at a much higher budget. If parity arrives cheaply, the contribution reduces to an efficiency footnote.

Why not just use CCNet or anchor pooling, which already work? Both route along geometry fixed in advance: axis-aligned paths in CCNet, and pyramid grids in the asymmetric block. Neither supervises routing. Our expected gain is concentrated on large, irregular, or fragmented objects, such as roads occluded by cars or sky split by poles. The per-class and per-distance breakdown tests that directly. If aggregate mIoU does not move, those breakdowns tell us whether the idea is useful anywhere at all.

Proposed Experiments

The main experiment trains all methods on Cityscapes fine annotations (dataset), ADE20K with 150 classes (dataset), and PASCAL Context. We report mIoU, per-class IoU, FLOPs and peak GPU memory.

The first decisive check is resolution scaling. We run each long-range block at output stride 8, 4 and 2 on Cityscapes. Dense non-local runs out of memory early. CCNet grows as $N\sqrt{N}$, while ours grows linearly. The test is whether accuracy keeps improving at finer resolution, where downsampling has stopped destroying boundaries.

The second decisive check is the pairwise diagnostic. We plot held-out same-class AUC of each method's affinity as a function of pixel distance. For baselines, the affinity is their normalized attention weight. Gains should appear at the largest distances, since that is where locality hurts.

The third check is calibration. We test whether $1-e^{-\theta}$ is a calibrated same-segment probability, using reliability curves on validation pairs. This is a property none of the baselines' attention weights claim.

Failure is defined in advance. If the cross-entropy-only ablation matches on both mIoU and far-distance AUC, or if a sampled logistic loss matches at under twice our cost, we will report the exact all-pairs likelihood as unnecessary for this task.