Foveated Shell Kernels: Large Graph Receptive Fields Without Repeated Averaging

Graph neural networks learn about a node by averaging information from its neighbors, one hop per layer. To see ten hops away you stack ten layers, and each extra round of averaging blurs nodes further toward one another until they become indistinguishable. This collapse is called over-smoothing. Vision faced a similar problem when it tried to give convolutional networks very large receptive fields, the region of the image each output can see. The fix there was not to stack many small filters. Instead, one large filter was split into cheap structured pieces. The most instructive version, peripheral convolution, keeps fine, unshared weights in a small central region (the "fovea") and shares weights over exponentially wider bands toward the edge. This proposal carries that idea to graphs. A single layer looks at the whole multi-hop neighborhood, partitioned into disjoint rings of nodes at exactly distance $k$ (called "shells"). The 1-hop ring gets fine per-neighbor weights. The outer rings are grouped into exponentially widening bands that share one per-channel weight each.

The claim that makes this more than a relabeled multi-hop filter concerns how the neighborhood is partitioned. Most multi-hop graph operators sum powers of the averaging matrix. Those powers count walks, so a $k$-step term mostly re-mixes the node itself and its near neighbors, and it converges to the same smoothed vector as $k$ grows. Shells are disjoint. A shell kernel gives each distance band its own identifiable, signed, per-channel weight. We hypothesize that this is what lets the receptive field grow without homogenizing node features. The hypothesis can be falsified with a single matched ablation, and that ablation is the center of the experiments.

Core Claim

For node $v$ with hidden vector $h_v$, let $\mathcal{S}_k(v)$ be the set of nodes at shortest-path distance exactly $k$, and let the peripheral bands be $G_1=\{2\}$, $G_2=\{3,4\}$, $G_3=\{5,\dots,8\}$, and so on up to radius $R$. One foveated shell layer computes

$$ h_v' = \sigma\Big( W\big[\,\theta_0 \odot h_v + \sum_{u \in \mathcal{S}_1(v)} g_{vu} \odot h_u + \sum_{b} \theta_b \odot \bar h_{G_b}(v) \big]\Big), $$

where $\bar h_{G_b}(v)$ is the mean of $h_u$ over all nodes whose distance from $v$ falls in band $G_b$. The terms $\theta_0,\theta_b$ are learned signed vectors, one weight per channel. The term $g_{vu}$ is a per-channel gate computed from $h_v$ and $h_u$ through a sigmoid rather than a softmax. $W$ is a shared channel-mixing matrix, and $\odot$ is elementwise product.

Each design choice copies a specific vision mechanism. The fovea-plus-banded-periphery layout, whose parameter count grows as $\log R$, comes from PeLK. The split into a local filter, a long-range filter and a channel-mixing step comes from large-kernel attention in Visual attention network. Per-channel spatial weights follow the depthwise-separable view of GCNs in Unified GCNs.

The sigmoid gate is a deliberate response to Demystifying Oversmoothing in Attention-Based Graph Neural Networks. That paper proves softmax attention can never assign zero weight to an edge, so attention-based GNNs still collapse exponentially. A sigmoid gate can switch an edge off. Signed band weights let a channel subtract the periphery from the center. This is the high-pass "diversification" of Complete the Missing Half, extended from a single 1-hop scalar to every band.

Relation to Prior Work

The closest existing work is Graph Dilated Network with Rejection Mechanism. It samples nodes at hop intervals set by a dilation rate and learns a per-layer scalar penalty that damps distant messages. Our proposal differs in three ways. It covers the full neighborhood with disjoint shells rather than sampled hops. It uses signed per-channel band weights rather than a single nonnegative damping scalar, which permits high-pass responses. It groups bands geometrically, which bounds the parameter count. That last point matters because GraphDRej's authors report that large neighborhoods cause overfitting and noise intrusion. Geometric sharing is our proposed remedy, and it is tested directly.

Two other papers reach far without deep stacking but take different routes. hpGAT injects a fixed multi-hop proximity from a precomputed hierarchical matrix factorization into a shallow attention layer. Its structure is fixed before training and needs a preset number of hierarchies. Our band weights are learned per channel. Geometric Scattering Attention Networks combines diffusion-wavelet band-pass channels with node-wise attention. Its bands are still built from powers of the diffusion matrix, the walk-based construction we argue leaks. It is also expensive, since it computes several scattering channels per node.

Unified GCNs supplies the per-channel separable view but stays at one hop and on graph classification. We move it to multi-hop node classification under heterophily, where connected nodes often have different labels.

Finally, PeLK reports that splitting 2D kernels into 1D stripes, as SLaK does, hurts dense prediction relative to grids with peripheral sharing. That result motivates a secondary question: whether aggregating along sampled 1D random-walk paths (the graph analogue of a stripe) is worse than shells (the analogue of a grid).

Research Program

The work has three parts.

Building the operator. Shells are computed by breadth-first search to radius $R$ (default 16, capped at the graph diameter). Shell sets for the small and medium graphs are precomputed once. On ogbn-arxiv, where exact shells grow too large, each band mean is estimated from a fixed per-node sample of nodes in that band. We report both the preprocessing cost and the variance the sampling introduces.

Analysis. We make the leakage argument precise. The $k$-th power of the normalized adjacency places mass on nodes closer than $k$ through backtracking walks, and its rows converge to the stationary distribution. Shell means have neither property up to the graph diameter. We then measure collapse empirically with the node-similarity decay used by Wu et al. in Demystifying Oversmoothing, tracking it as a function of receptive-field radius rather than only depth.

We state one caveat up front. On small-diameter graphs the outer shells cover most of the graph, so their means also approach the global mean. The signed weights are what allow a channel to subtract that global component. Whether they learn to do so is checked by inspecting the learned $\theta_b$.

Controlled comparisons. Each ingredient is isolated with a matched ablation: shells versus walk powers, geometric bands versus one weight per shell, sigmoid versus softmax fovea, and shells versus random-walk stripes.

Baselines

The naive reference points are a 2-layer GCN and a 2-layer GAT. Revisiting Over-smoothing in Graph Neural Networks reports that shallow models are the best performers on small citation graphs, so they are the bar on homophilic data, where linked nodes tend to share labels. On Chameleon, the file reports GCN at 28.2% accuracy (Geometric Scattering Attention Networks). This shows how badly shallow averaging fails under heterophily.

The strongest heterophily competitor is GSAN, which reports 61.2% accuracy on Chameleon in the same paper. We will run it with its released configuration where one is available, on our splits, and give it the same tuning budget. Beating it means higher mean accuracy over the standard splits, outside one standard deviation, at no more parameters.

On depth robustness and large graphs, the strongest competitor is the isometric-initialization GCN with gradient-guided skip connections from Old can be Gold. It reports about 80% on Cora at up to 64 layers and 72.28% on ogbn-arxiv. GraphDRej is the closest structural baseline, reporting 79.70% on Cora with three dilated kernels. hpGAT reports 0.730 on Citeseer against GAT's 0.721. DSGNN reports 77.5% on Pubmed at 12 layers. For FB-GNN on Texas and Cornell, the file gives only a roughly 10-point gain over GCN and no absolute figure, so we report our own rerun.

All methods share splits, feature preprocessing, early stopping, and a matched hyperparameter search budget. Parameter counts are reported alongside every result.

The key ablation replaces every shell mean $\bar h_{G_b}$ with the band-matched walk term, the average of normalized-adjacency powers $\hat A^k h$ over $k \in G_b$. Everything else is kept fixed: the same number of parameters, the same signed per-channel weights, the same fovea. If this walk version matches the shell version, the central claim is wrong.

Why not just…?

Why not just use a learned polynomial filter with one coefficient per hop? This is the most serious threat. A shell kernel without the fovea resembles a polynomial in the adjacency matrix with learned hop coefficients. The shell-versus-walk ablation above is exactly this comparison, run at matched capacity. We commit to reporting it as the headline result. If walk powers do as well on heterophilic graphs and show equal collapse curves, the proposal reduces to a parameter-sharing trick and we will say so.

Why not just attach loss heads to every layer, as DSGNN does? Deep supervision stabilizes depth on molecular regression and Pubmed (Revisiting Over-smoothing). However, it still loses to shallow models on Cora and Citeseer, and it does not change what each layer aggregates. We compare against DSGNN at equal depth and also try adding its heads to our model. The open question noted in the file is whether an operator change removes the need for such heads.

Why not just fix initialization and gradient flow? Old can be Gold shows this rescues deep vanilla GCNs on homophilic graphs. It still aggregates through repeated low-pass averaging, and it has no reported heterophily result. If it matches us on Chameleon, Texas and Cornell, our operator argument is weakened. Running it there settles the matter.

Why not just use attention? Softmax attention provably cannot break connectivity and only slows exponential collapse (Demystifying Oversmoothing). The sigmoid-versus-softmax fovea ablation tests whether that theoretical point matters in practice inside our layer.

Why not just add one high-pass channel? FB-GNN's two scalars recover roughly 10 points on Texas and Cornell (Complete the Missing Half), but the model stays at one hop. Setting $R=1$ in our model reproduces that regime. The gain from $R=1$ to $R=16$ measures what multi-hop periphery adds beyond it.

Proposed Experiments

We evaluate on Cora, Citeseer and Pubmed (homophilic, with the shallow-model bar), on Chameleon, Texas and Cornell (heterophilic), and on Flickr and BlogCatalog (noisy neighborhoods). We also run ogbn-arxiv for scale, using sampled shells. Metrics are node-classification accuracy (mean and standard deviation over splits), parameter count, preprocessing and training time, and the node-similarity collapse measure.

The first decisive check is the shell-versus-walk ablation on the heterophilic graphs. The second tracks collapse and accuracy as the radius $R$ grows from 1 to 32 at fixed depth. We predict that shell kernels stay flat while walk kernels decay.

Third, geometric bands versus one weight per shell on Cora and Citeseer tests whether peripheral sharing curbs the overfitting that GraphDRej reports. Fourth, shells versus random-walk stripes tests whether the grid-versus-stripe finding from vision carries over to graphs.

Success means beating GSAN's 61.2% on Chameleon and matching the roughly 80% deep-GCN figure and GraphDRej's 79.70% on Cora with a 2-layer model. It also requires a clear margin over the walk-power ablation. Failing only that last condition would redirect the contribution from "shells prevent smoothing" to "foveated parameter sharing is an efficient multi-hop filter."