Graph neural networks (models that update each node's vector by averaging its neighbors' vectors, one layer at a time) face two problems on real networks. Both trace back to the same few nodes. Social, citation and web graphs have a power-law degree distribution: a handful of "hub" nodes touch a large share of all edges. On parallel hardware, hubs create load imbalance. The thread, warp (a group of 32 GPU threads that run in lockstep) or cluster worker that owns a hub does far more work than its peers, and everyone else waits. In the model itself, hubs act as shortcuts that shrink the graph's diameter. Repeated averaging then mixes features across classes within a few layers, until all node vectors look alike. That collapse is called over-smoothing. The two research communities have so far treated these as separate problems.
We propose one change that addresses both. At every layer, each node exchanges messages over at most $k$ edges in each direction. A deterministic schedule chooses which $k$ of a hub's edges are active at which layer, and it rotates through all of them as depth grows. The same schedule runs at training and at test time. Nodes with degree at most $k$ see their full neighborhood at every layer. Only hubs are rate-limited. Every layer's operator therefore has bounded width, so it maps onto fixed-width GPU kernels with no warp divergence and no hub-column atomic contention in the backward pass. The same bound limits how fast features can spread and mix across the graph. The claim is that one depth-dependent schedule does the job currently split between load-balancing kernels and anti-over-smoothing tricks, and does it better than random fixed-fan-out sampling.
Core Claim
Write $E_\ell$ for the set of edges active at layer $\ell$. The schedule enforces
$$ \max_v \deg^{\text{in}}_{E_\ell}(v) \le k, \qquad \max_v \deg^{\text{out}}_{E_\ell}(v) \le k, \qquad \bigcup_{\ell=1}^{L} E_\ell \supseteq \{(u,v): \min(d_u,d_v)\le k\} \cup \mathcal{C}_L, $$
where $d_u$ is the full degree of node $u$, $L$ is the network depth, and $\mathcal{C}_L$ is the portion of hub-hub edges the rotation reaches within $L$ layers. The first two constraints give a load guarantee. Every row and every column of every layer's sparse matrix has at most $k$ nonzeros, so the forward gather and the backward scatter are both uniform.
The third constraint separates the method from sampling. Edges are covered systematically across depth rather than drawn independently.
The representation-side prediction comes from A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks. That paper shows harmful inter-class mixing takes over once receptive fields saturate. Its optimal depth grows like $\log N / \log\log N$, where $N$ is the number of nodes, because receptive fields expand geometrically with average degree. With a cap $k$, the $\ell$-hop receptive field of any node is at most $k^\ell$. The depth at which mixing saturates should then scale roughly as $\log N / \log k$ and should no longer depend on the hub degree. That paper explicitly assumes near-uniform degrees and names power-law hubs as a likely accelerant it does not treat. We test that conjecture directly and propose the cap as the correction.
How This Relates to Existing Work
Three lines of work motivate the problem.
- Theory of the degree gap. The non-asymptotic analysis above supplies the theoretical gap on degree skew.
- Low-degree nodes suffer first. Degree-based stratification of nodes in Graph Neural Networks learns separate weight matrices for low- and high-degree nodes, split at a threshold found by Otsu's method. It reports that under vanilla GCN on CiteSeer, low-degree nodes reach 61.2% accuracy against 90.4% for high-degree nodes, and that stratification lifts low-degree accuracy to 66.1%. That paper changes the transformation weights but leaves the aggregation topology untouched and ignores runtime. It also adds a branch per degree class, which fragments GPU work. We instead change which edges carry messages. We keep its degree-split weights as an optional add-on and an ablation.
- Measurement. Are we measuring oversmoothing in graph neural networks correctly? shows that Dirichlet energy (a measure of how different adjacent nodes' features are) can stay high while effective rank (an entropy of the feature matrix's singular values) collapses. It reports that effective rank correlates with accuracy at 0.91 on average. We adopt effective rank as our primary diagnostic.
Four systems papers supply the hardware methods we compete with rather than reuse.
- AWB-GCN rebalances hub rows at runtime on an FPGA accelerator.
- GCoD trains a shallow GCN to polarize the adjacency matrix into a dense core and a sparse periphery for a two-engine accelerator.
- On Efficient Scaling of GNNs via IO-Aware Layers Implementations buckets nodes into light and heavy groups and tiles heavy ones in 2D on GPUs.
- NeutronTP splits feature dimensions rather than the graph across workers.
All four evaluate only shallow, fixed-depth models and never measure over-smoothing. All four also take the operator as given and balance its execution. We reshape the operator so that it is balanced by construction.
Edge-based Local Push for Personalized PageRank inspires the idea of per-edge rather than per-vertex scheduling. It splits PageRank-style propagation into edge-level pushes with edge-specific thresholds and reports a 130× speedup over MAPPR on Orkut-Links.
The closest representation-side competitors are the following.
- Shedding Light on Random Dropping and Oversmoothing shows that random DropEdge does little against over-smoothing at test time. Its learned dropping masks (Learn2Drop) reach 69.3% with a 64-layer GCN on Cora. That negative result constrains our design: whatever sparsification we use must also run at test time, which is why our schedule is deterministic and always on.
- Deep Graph Neural Networks with Shallow Subgraph Samplers bounds the receptive field by running a deep model inside a small extracted subgraph. It leaves subgraph sizes skewed between hubs and ordinary nodes. Our cap bounds per-layer fan-in globally, with no extraction step.
- ReHub routes long-range messages through virtual hubs. It does not address the intrinsic hubs of the input graph.
Research Program
The work has three parts.
A controlled measurement of whether degree skew speeds up collapse. We generate degree-corrected stochastic block models, meaning random graphs with planted classes and a tunable power-law degree exponent. We hold size, class separation and average degree fixed while varying skew. At each depth up to 128 we record accuracy, effective rank, and the denoising-versus-mixing decomposition of the non-asymptotic analysis. The prediction is that heavier tails move the optimal depth earlier. A $k$-capped schedule should move it back toward $\log N/\log k$. If skew at fixed average degree does not shift the optimal depth, the representation half of the proposal fails, and we would report that.
The schedule construction. Only edges with an endpoint of degree above $k$ need scheduling. For those, we build a sequence of edge subsets that each have in- and out-degree at most $k$. We do this with a greedy bounded-degree edge coloring, which is cheap, linear in the number of edges, and computed once. The model cycles through the colors layer by layer. Low-degree nodes keep their edges in every layer, with symmetric normalization computed on each layer's active edges.
Two variants will be compared:
- a fixed order;
- an order sorted by feature similarity once at preprocessing, so that each hub's most similar neighbors come first. This borrows the center-neighbor similarity idea from When Do GNNs Work but keeps it static, so that load balance is preserved.
$k$ is a single hyperparameter. We will sweep it over 4, 8, 16, 32 and 64, and also test tying it to the degree threshold from the stratification paper.
A fixed-width kernel. Each layer is stored in ELL format (a dense $N\times k$ neighbor-index array, padded where degree is below $k$). Forward aggregation becomes a regular gather. Because out-degree is also capped, the backward scatter needs at most $k$ atomic adds per destination. This targets the backward-pass atomic contention that the file lists as open for edge-centric kernels. We will report warp efficiency, time per layer, and backward time separately.
Baselines
The naive reference point is a plain GCN at 2 and 64 layers on the full graph, run with a standard PyTorch Geometric CSR kernel. The shallow run gives the accuracy that depth has to beat. The deep run shows the collapse that any fix must avoid.
The strongest over-smoothing competitor on the deep Cora protocol is Learn2Drop from Shedding Light on Random Dropping and Oversmoothing, which reports 69.3% accuracy at 64 layers. We will match that paper's split, depth and hyperparameter budget, rerun it ourselves, and beating it means exceeding its reproduced accuracy at 64 layers while also cutting runtime. We also run the following:
- PairNorm, from PairNorm: Tackling Oversmoothing in GNNs. In its missing-features setting on Cora it reports 74.5% for a deep SGC with PairNorm against 42.3% for vanilla SGC. That is the long-range regime where depth is actually needed. Our target is to meet or exceed that 74.5% on the same protocol.
- The critical-variance GCN from Graph Neural Networks Do Not Always Oversmooth, which trains GCNs with over 100 layers on Cora at weight variance near 1.
- The bifurcation-aware sine-activation model from Beyond ReLU.
- Degree stratification, whose 66.1% low-degree CiteSeer accuracy is the target for the per-degree breakdown.
On large graphs the accuracy references are the OGB numbers on ogbn-products. Open Graph Benchmark reports GraphSAINT at 79.08% and GraphSAGE at 78.50% test accuracy, and any deep capped model should at least match these. SHADOW-GNN is also run on ogbn-arxiv and ogbn-products, but no reported result was found on Lacuna for its accuracy on these datasets, so we reproduce it under our own budget.
The systems baseline is the degree-aware tiled reduction kernel of On Efficient Scaling of GNNs via IO-Aware Layers Implementations. The file gives its results only as ratios against DGL: up to 10× faster, median 2.6×. It gives no absolute timing. We therefore run it on the same GPU and graphs and compare full-depth training time at equal accuracy. Winning means lower total wall-clock time than those kernels running the full, uncapped operator.
Every method receives the same splits, the same number of tuning trials, and the same GPU.
Three ablations isolate the key ingredient:
- in-degree cap only versus in- and out-degree caps;
- the deterministic covering schedule versus independent random $k$-neighbor sampling redrawn at every layer and used at test time, with identical $k$, kernel and cost;
- the capped schedule with and without degree-split weights.
Why not just…?
Why not just keep networks shallow? On feature-rich citation graphs this may be exactly right. We will report the 2-layer GCN honestly and do not expect to beat it by much there. The case for depth rests on regimes where information must travel far. PairNorm's missing-features setting shows a large gap (42.3% versus 74.5%), and ReHub's long-range benchmarks exist for the same reason. We therefore make those regimes the primary accuracy test and treat standard Cora as a sanity check.
Why not just add PairNorm or residual connections to the full graph? Two reasons. First, Are we measuring oversmoothing in graph neural networks correctly? finds that normalization and skip connections can preserve energy while rank still collapses by around layer 10. Second, PairNorm's authors note that it does not raise peak accuracy on feature-rich graphs. Neither fix touches hub-induced load skew. Still, PairNorm composes with our schedule. If PairNorm on the full graph plus the tiled kernel matches both our accuracy and our runtime, the schedule adds nothing, and the experiments will show that.
Why not just use fixed fan-out random neighbor sampling? GraphSAGE-style sampling also bounds in-degree and balances forward work. This is the real threat. Our response is not an argument but the random-versus-covering ablation described under Baselines. We expect the covering schedule to win on three counts: lower variance at test time, full coverage of hub edges over depth, and a bounded out-degree for the backward pass, which random in-sampling does not give because a hub can be picked by many neighbors. If random per-layer sampling at test time matches us on accuracy, effective rank and backward time, we would reframe the contribution as a finding that test-time random fan-out sampling fixes both problems. That would still be new relative to the DropEdge negative result, which concerns training-only dropping.
Why not just use tensor parallelism or better kernels and leave the model alone? NeutronTP evens out worker runtimes: competitors differ by 1.38× between workers, while its workers finish in nearly identical time. Tiled kernels balance warps. Both still execute an operator that collapses at depth, and neither addresses representation. The fair test is equal-accuracy wall-clock comparison against those kernels on the full operator.
Proposed Experiments and Decisive Checks
Synthetic check. On the degree-corrected block models, plot optimal depth against degree exponent, with and without the cap, and fit it against $\log N/\log k$. Both claims hold only if uncapped optimal depth falls with skew and the capped curve flattens.
Deep-regime accuracy on real graphs. Run 16 to 128 layers on Cora, CiteSeer and PubMed, in both the standard and the missing-features protocols. Report accuracy broken down by degree stratum, plus effective rank per layer, against every baseline above.
Scale. Run on ogbn-arxiv, ogbn-products and Reddit, where hub skew is severe. Measure accuracy, time per epoch, warp efficiency, and forward and backward time against the tiled kernels and SHADOW-GNN.
Decisive checks. The proposal succeeds only if all three hold:
- The covering schedule beats test-time random fan-out sampling at equal $k$.
- The out-degree cap measurably cuts backward time on hub-heavy graphs.
- A single $k$ gives both the best effective-rank retention and near-uniform per-warp work.
If the $k$ best for accuracy and the $k$ best for load balance turn out far apart, the claim of one unified fix fails. We would then report the two effects as separate.
References
- A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks
- Degree-based stratification of nodes in Graph Neural Networks
- Are we measuring oversmoothing in graph neural networks correctly?
- AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing
- GCoD: Graph Convolutional Network Acceleration via Dedicated Algorithm and Accelerator Co-Design
- On Efficient Scaling of GNNs via IO-Aware Layers Implementations
- NeutronTP: Load-Balanced Distributed Full-Graph GNN Training with Tensor Parallelism
- Edge-based Local Push for Personalized PageRank
- Shedding Light on Random Dropping and Oversmoothing
- Deep Graph Neural Networks with Shallow Subgraph Samplers
- ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment
- When Do GNNs Work: Understanding and Improving Neighborhood Aggregation
- PairNorm: Tackling Oversmoothing in GNNs
- Graph Neural Networks Do Not Always Oversmooth
- Beyond ReLU: Bifurcation, Oversmoothing, and Topological Priors
- Open Graph Benchmark: Datasets for Machine Learning on Graphs