Graph neural networks, models that build each node's representation by repeatedly averaging information from its neighbors, are much more accurate on well-connected "hub" nodes than on the sparsely connected "tail" nodes that make up most of real graphs. On graphs with hundreds of millions of nodes, the practical models are decoupled: they compute the multi-hop neighbor averages once, as a preprocessing step, and then train a plain multilayer perceptron on the cached features. We argue that this cached averaging is exactly where tail nodes get hurt. Averaging behaves like a random walk, and a random walk spends its time at hubs. After a couple of hops, a tail node's cached features describe mostly the hubs next to it rather than the node itself. In heterogeneous graphs, which have several node and edge types, hubs are often whole node types, such as fields of study or venues in an academic graph. Hub-dominated relations can therefore drown out the sparser relations that actually tell tail nodes apart.
The proposal is to change the cached operator itself. When features are precomputed, a hub may send its own raw feature to its neighbors, but it may not pass along the mixture it received from its own thousands of neighbors. We call this hub-sink propagation. The name borrows the trick that disk-based random-walk systems use to stop hubs from causing I/O blowups (Sarkar et al.), and applies it to representation quality instead of I/O. The sink channel is added per relation next to the standard channel. It costs the same kind of sparse matrix products, keeps everything static and cacheable, and lets the downstream model draw each node's multi-hop context from paths that do not pass through hubs.
Core Claim
We make two claims, and the second depends on the first. The first is diagnostic. In decoupled heterogeneous pipelines, the loss of feature diversity with depth, usually called over-smoothing, is degree-stratified. The effective rank of the cached hop-$k$ features, a measure of how many independent directions the features still span, should fall at shallower $k$ for low-degree nodes adjacent to hubs than for the graph as a whole. Tail nodes that share a hub neighbor should also become nearly identical to each other. The second claim concerns the remedy. If that pattern holds, redirecting hubs into sinks during precomputation will raise tail-node accuracy on large heterogeneous benchmarks without lowering hub accuracy and without test-time graph manipulation. Neither hop attention nor degree-aware normalization can reproduce this gain, because both still build multi-hop context from hub-routed paths.
Concretely, for relation $r$ let $P_r$ be the row-normalized adjacency, let $X^{(0)}$ be the input features, and let $M_r$ be a diagonal 0/1 mask that is 0 exactly for nodes whose relation-$r$ degree exceeds a quantile threshold $\tau$. The standard cache is $X^{(k)} = P_r X^{(k-1)}$. The sink cache is
$$X_s^{(k)} = P_r\left(M_r X_s^{(k-1)} + (I - M_r)\,X^{(0)}\right),$$
so a hub always emits its own raw feature, while non-hubs propagate normally. Setting $\tau$ to include no nodes recovers the standard cache. The downstream model receives both caches.
This mechanism has a limit worth stating up front. A degree-1 node whose only neighbor in relation $r$ is a hub cannot be distinguished from its siblings within that relation by any operator. The sink channel does not claim to help there. Its benefit is for nodes with mixed neighborhoods, and for heterogeneous composition: it stops hub-heavy relations, such as paper–field or paper–venue, from overwriting the discriminative signal carried by sparser relations such as paper–author.
Where This Sits in Prior Work
Three papers motivate the diagnosis. Mitigating Degree Bias in Graph Neural Networks documents the hub/tail accuracy gap on power-law graphs. Arun et al. and Kang et al. attribute part of it to hubs dominating gradients. TSP proves, using Dirichlet energy, that message passing inflates hub embedding norms in bipartite recommenders. None of these studies decoupled heterogeneous pipelines. TSP also measures with Dirichlet energy, which Are we measuring oversmoothing in graph neural networks correctly? shows can stay flat while accuracy collapses. That paper instead proposes Numerical Rank and Effective Rank, reporting an average Pearson correlation of 0.91 between Effective Rank and accuracy, but only globally and only on homogeneous graphs. We reuse its rank metrics as the measurement tool and disaggregate them by degree and relation. That analysis is the open question named in the file's first gap.
Three papers supply the scalable substrate, and each marks a point of contrast. NARS precomputes $L$-hop neighbor averages on sampled relation subgraphs and fuses them with a 1D convolution, scaling to OAG with 178 million nodes, but applies the same low-pass average to every node. GAMLP observes that sparse nodes want different receptive fields and learns per-node attention over hops. That attention reweights hops that are all hub-routed; it can choose which hop but cannot create context that avoids hubs. HOPE is the closest existing work on this intersection. It targets long-tail nodes in scalable heterogeneous models through a mixture-of-experts decoder, but explicitly leaves the upstream features, and whatever bias they carry, untouched. Our intervention sits upstream of HOPE and is complementary to it.
Two lines constrain the design. GraphPatcher reports that training-time re-weighting and oversampling cost 2–11% accuracy on well-connected nodes. For that reason we keep the standard channel intact for everyone rather than replacing it. GraphPatcher and TSP both fix degree bias by editing the graph at test time, which conflicts with the static caches that make NARS and GAMLP fast. Hub-sink propagation is designed to live entirely inside the cache. CFGNN routes all messages fringe-to-core-to-fringe through hubs for scalability on homogeneous graphs. It is effectively the opposite design bet, and our diagnostic tests whether hub routing costs tail nodes. HALO avoids collapse through relation-aware energy descent and reports 76.20% versus 67.36% for Simple-HGN on IMDB, but its authors state that it does not yet scale. It serves as a small-graph reference point for what non-decoupled collapse avoidance achieves.
Research Program
The first stage is measurement and acts as a go/no-go gate. On ogbn-mag and the HGB datasets (DBLP, ACM, IMDB, Freebase), we build the NARS-style per-relation caches up to $K$ hops. We bucket target nodes by total degree and by relation-specific degree, and compute three quantities per bucket and hop. The first is Effective Rank of the cached features. The second is a sibling collapse score: the mean cosine similarity among low-degree nodes that share a hub neighbor. The third is the share of each node's hop-$k$ mass that arrived through a hub. If rank decay and sibling collapse turn out to be degree-uniform, the premise fails. In that case we report a degree-uniform collapse in heterogeneous caches as a finding and do not build the method.
The second stage builds the sink caches. We compare two definitions of "hub": degree quantiles per relation, and whole node types, for example all field-of-study nodes treated as sinks. In heterogeneous graphs the type-level definition may be both simpler and nearly as effective, and learning which definition is right is itself useful. The sink computation shares NARS's sparse matrix products and needs one extra cache per relation per hop. We therefore account for memory explicitly and trade sink hops against standard hops at a fixed feature budget.
The third stage plugs both caches into existing decoupled heads: NARS's convolution-plus-MLP, a GAMLP-style hop-attention head, and HOPE's decoder. This shows whether the gain is additive with decoder-side and attention-side tail fixes. Finally, we scale to OAG to check that preprocessing time and memory remain within the NARS envelope.
Baselines
The naive reference point is NARS with its standard caches and default settings, trained on the same splits, which is exactly our method with the sink threshold set to include no nodes. Beating it means higher accuracy in the lowest-degree buckets and on worst-bucket accuracy, with overall accuracy no lower. On ogbn-mag the file reports only NARS's relative gain of roughly 4% over HGT, and no reported result was found on Lacuna for the absolute ogbn-mag accuracy of NARS, GAMLP, or HOPE. We will therefore reproduce all three under our own protocol rather than quote a target number.
The strongest existing competitor for tail nodes at this scale is HOPE on an HGAMLP backbone. It is the only file-listed method that explicitly targets long-tail nodes in scalable heterogeneous models, and the file reports that it improved HGAMLP on ogbn-mag, though without a number. We run it with its published configuration, and test both "HOPE on standard caches" against "HOPE on standard plus sink caches". Beating it means a statistically reliable gain in bottom-quartile-degree accuracy over 10 seeds at matched parameter count.
A GAMLP-style hop-attention head on the same heterogeneous caches isolates the question of whether learned hop selection already solves the problem. For homogeneous scale checks, the file reports GAMLP+RLU at 84.59% test accuracy on ogbn-products and 68.25% on ogbn-papers100M. Matching these overall while improving low-degree buckets would count as success there.
Degree-aware normalization is run as a direct operator competitor: the doubly stochastic normalization of Kang et al. applied to each relation's adjacency before precomputation.
The key ablations have two jobs. They separate the sink operator from simply having more features, by comparing standard caches with $2K$ hops against standard plus sink caches with $K$ hops each at equal memory. They also separate "sink" from "delete": hub-edge removal drops hubs' own features, whereas sinks keep them.
Every method gets the same data splits, the same hop budget, the same total cached-feature memory, the same number of hyperparameter-search trials, and 10 seeds, with preprocessing time reported alongside accuracy. GraphPatcher, which reports gains of up to 3.6% overall and 6.5% on low-degree nodes, is homogeneous-only and runs at test time. We therefore compare against it on ogbn-arxiv and ogbn-products, reporting both inference latency and tail accuracy.
Why not just…?
Why not just let GAMLP-style hop attention pick a short receptive field for tail nodes? Attention can stop a tail node from using its collapsed deep hops, but then the node gets no multi-hop context at all, because every available hop was routed through hubs. The sibling-collapse measurement will show whether the deep hops of tail siblings are nearly identical in the standard cache. The attention-head comparison shows whether sink hops give such nodes information that attention over standard hops cannot. If attention on standard caches matches our tail accuracy, the sink operator adds nothing. That result would settle the question against us, and we would report it.
Why not just fix the normalization, e.g. doubly stochastic normalization? Rebalancing weights reduces how much hubs dominate, but it keeps hubs as transit points, so their thousand-neighbor mixture still reaches every tail neighbor. This is a real threat, because on graphs whose hubs are only moderately large it may do most of the work. It is therefore run as a first-class baseline, and we will report the degree range over which the two methods differ.
Why not just re-weight the loss toward low-degree nodes? GraphPatcher reports 2–11% drops on well-connected nodes for such training-time interventions. KG-Mixup argues that re-weighting adds no new neighborhood context for information-starved tail entities. Our method changes the inputs rather than the loss, and keeps hubs' standard features. Hub-bucket accuracy is reported for every run to check that hubs do not lose accuracy.
Why not just use HOPE's decoder? HOPE corrects tail predictions from features that may already be collapsed. If the upstream diagnosis holds, correcting the decoder alone leaves recoverable information unused. The HOPE-with-and-without-sink comparison measures exactly this complementarity.
Proposed Experiments
The decisive checks come in order. First, on ogbn-mag, does Effective Rank of the cached features decay faster, and does sibling cosine rise faster, in the bottom degree quartile than in the top? Without this gap the project stops at the diagnostic. Second, at equal cached-feature memory, does adding sink caches raise bottom-quartile accuracy on ogbn-mag and on HGB DBLP, IMDB, and Freebase over NARS, GAMLP-style attention, doubly stochastic normalization, and HOPE, without lowering top-quartile accuracy? Third, does the gain follow the predicted pattern: largest for tail nodes with mixed hub and non-hub neighborhoods, near zero for degree-1 nodes attached only to hubs? A flat gain across these groups would suggest the benefit comes from something other than the stated mechanism. Fourth, on OAG, is preprocessing time within a small constant of NARS, and does training throughput stay at MLP speed? On ogbn-products we also check that overall accuracy stays near the 84.59% GAMLP+RLU reference while tail buckets improve. Metrics throughout are overall accuracy, accuracy per degree bucket, worst-bucket accuracy, the hub–tail gap, preprocessing time and memory, and inference latency.
References
- Fast nearest-neighbor search in disk-resident graphs
- L2DGCN: Learnable Enhancement and Label Selection Dynamic Graph Convolutional Networks for Mitigating Degree Bias
- CAFIN: Centrality Aware Fairness Inducing IN-Processing for Unsupervised Representation Learning on Graphs
- RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network
- How Does Topology Bias Distort Message Passing in Graph Recommender? A Dirichlet Energy Perspective
- Are we measuring oversmoothing in graph neural networks correctly?
- Scalable Graph Neural Networks for Heterogeneous Graphs
- Graph Attention Multi-Layer Perceptron
- Scalable Heterogeneous Graph Learning via Heterogeneous-aware Orthogonal Prototype Experts
- GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation
- Bridging Indexing Structure and Graph Learning: Expressive and Scalable Graph Neural Network via Core-Fringe
- Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks
- Toward Degree Bias in Embedding-Based Knowledge Graph Completion