Relation-Stratified Boundary Sampling for Distributed Heterogeneous Graph Training

Large text collections are increasingly modeled as one big graph. Papers, authors, sentences, words and named entities become nodes, and typed edges record who wrote what, which sentence contains which entity, and which mentions refer to the same thing. Training a graph neural network on such a graph needs many machines. A graph neural network is a model that updates each node by aggregating messages from its neighbors. Once the graph is split across machines, every layer of every training step has to ship the hidden vectors of "boundary nodes", meaning neighbors that live on another machine. This shipping, not the arithmetic, dominates training time. Data movement can take up to 80% of training time (Global Neighbor Sampling), and the number of unique boundary nodes is the quantity that sets the cost (BNS-GCN).

The best current fix is to send only a random fraction $p$ of boundary nodes and rescale them by $1/p$. It treats every boundary node alike. In a heterogeneous document graph that is wasteful. A boundary node reached through a cross-document coreference edge and one reached through a generic shared-word edge cost the same bytes but carry very different signal. We propose to treat the per-step communication budget as a sampling-design problem. Boundary nodes are grouped into strata by the relation type that links them into the receiving partition and by a cheap structural centrality score. The budget is then split across and within strata so as to minimize the variance of the aggregated messages. The claim to test is concrete: at a fixed number of bytes per epoch, this allocation reaches the full-communication accuracy of a relation-aware model on heterogeneous graphs, where tuned uniform sampling and degree-based caching fall short. A homogeneous graph serves as a negative control where we expect no gain.

Core Claim

Two facts from the literature motivate the proposal. First, relation types matter for accuracy in exactly the graphs that are hardest to distribute. The Heterogeneous Graph Transformer (HGT) gives each (source type, edge type, target type) triple its own attention projections. On the Open Academic Graph it beats GCN, GAT, RGCN and HAN by 9% to 21%, and removing the type-specific parameters costs 4%. In document graphs, removing coreference or adjacent-sentence edges sharply hurts inter-sentence relation extraction (Sahu et al.). Second, the distributed training systems that reduce communication ignore types entirely. BNS-GCN, DistDGL and GNS were all evaluated on homogeneous graphs. BNS-GCN also reports that cutting partitions off entirely ($p \to 0$) hurts accuracy, so which cross-partition signal survives matters. HGT's own HGSampling balances node types within a single-machine mini-batch but says nothing about cross-machine traffic.

Write $u$ for a boundary node, $v$ for a receiving inner node, $r$ for the relation linking them, $\alpha_{vu}$ for the attention weight and $m_u = W_r h_u$ for the message. If $u$ is kept with probability $p_u$ and reweighted by $1/p_u$, the variance added to the aggregated messages is

$$\mathrm{Var} = \sum_u \left(\tfrac{1}{p_u} - 1\right) c_u, \qquad c_u = \sum_{v} \lVert \alpha_{vu} m_u \rVert^2 .$$

Minimizing this subject to an expected budget of $B$ boundary nodes, $\sum_u p_u = B$, gives the standard optimal-allocation result from survey sampling: $p_u = \min(1, \lambda \sqrt{c_u})$, with $\lambda$ chosen to meet the budget. Uniform BNS is optimal only when all $c_u$ are equal, and in a typed document graph they are not.

The oracle $c_u$ needs the very messages we are trying not to send. So the method replaces it with a cheap proxy. The proxy is a per-relation scale $g_r$ times a structural score of $u$. We estimate $g_r$ from attention mass measured during a few full-communication warm-up epochs and refresh it periodically. For the structural score we will compare the number of inner neighbors, PageRank, and $k$-core depth. A $k$-core is the largest subgraph in which every node has at least $k$ neighbors inside it, so $k$-core depth is a measure of how deeply embedded a node is in a dense cluster.

This is where centrality ranking enters, as a hypothesis rather than an assumption. GoWvis and the related degeneracy study argue that $k$-core membership identifies thematic content better than raw degree, which is inflated by generic hub words. Tian et al. find degree and PageRank to be the most useful structural features for language-model reasoning over knowledge graphs. Neither paper asks whether these scores predict message importance during training, and we test that directly.

Research Program

The system builds on partition-parallel full-graph training in the style of BNS-GCN, with HGT as the relation-aware model. Each step proceeds in three stages. First, each machine computes stratified inclusion probabilities for its boundary set. Second, it pulls only the sampled boundary hidden states. Third, it applies relation-specific projections on the receiving side.

The receiving-side projection is a small but real design choice. A boundary node linked by $R$ relation types then costs one vector rather than $R$. That optimization is available to any method, so we give it to every baseline as well.

Softmax attention breaks the exact unbiasedness of $1/p$ reweighting. We therefore add $\log(1/p_u)$ to the attention logit of each sampled boundary node. This gives a self-normalized importance-weighted estimate, which is consistent but slightly biased. We will measure that bias against full communication instead of assuming it away.

The analysis has three parts. The first characterizes where communication actually goes in heterogeneous graphs: the share of boundary nodes and bytes per relation type under standard METIS partitioning. Gap 2 of the literature asserts that this share is skewed but nobody has measured it. The second measures how well each structural proxy (inner-neighbor count, PageRank, $k$-core depth), with and without the relation scale $g_r$, rank-correlates with oracle $c_u$ computed under full communication over training. The third places the resulting sampling policies on accuracy-versus-bytes curves.

Baselines

The naive reference point is full communication with no boundary sampling, which is the accuracy ceiling. It is run with the same HGT model, the same partitioning and the same number of epochs. We do not trust any speed claim unless accuracy is within a stated margin of this ceiling. The second reference is complete partition isolation ($p=0$), which bounds how much cross-partition signal matters at all on each dataset. If isolation is already near the ceiling on a dataset, that dataset cannot distinguish sampling policies and we will report it as such.

The strongest competitor on the sampling question is BNS-GCN, uniform boundary sampling with $1/p$ scaling. It reports 97.17% test accuracy on Reddit against 97.11% for full-graph training, and cuts ogbn-papers100M epoch time from 554 seconds to 6 seconds at $p=0.01$. We will first reproduce its Reddit behavior with our implementation, then port it to HGT with receiving-side projection. We will tune $p$ over the same grid and the same number of runs that our method gets for its budget $B$.

The second strong competitor is a hub cache in the spirit of GNS. GNS keeps 1% of influential nodes in GPU memory and corrects sampling bias with importance weights, reducing OAG-paper epoch time from 3,203 to 819 seconds. Its cache is static and single-machine. We implement the distributed analogue: replicate input features of the top-degree boundary nodes on every machine and sample the rest uniformly. Because hidden states at deeper layers change every step, only first-layer features can be cached for free. We charge the cache its true synchronization cost at the other layers.

Beating these baselines means one of two things. Either we reach within 0.5 points of the full-communication metric while sending at most half the boundary bytes per epoch that the best-tuned baseline needs for the same accuracy. Or we achieve a higher metric at equal bytes, with gaps larger than the standard deviation over five seeds.

Three ablations isolate the key ingredient: relation stratification with uniform sampling inside each stratum, structural scores without relation strata, and the oracle-$c_u$ policy as an upper bound on what any proxy could achieve.

Why not just…?

Why not just tune the uniform rate $p$ in BNS-GCN? It is the simplest option and it works well on homogeneous graphs, so it is the main threat. The variance expression above shows uniform sampling is optimal only when boundary nodes contribute equally. Whether they differ enough to matter is an empirical question. The relation-share measurement and the proxy-correlation study answer it directly. If per-relation attention mass turns out nearly flat on OAG, uniform BNS will match us there and we will say so.

Why not just cache or replicate the highest-degree boundary nodes? This is a real threat for word-heavy document graphs, where a few shared words may account for most boundary nodes. Caching them may remove most of the traffic. We therefore run the stratified sampler on top of the cache as well as against it. The decisive comparison is cache-plus-uniform versus cache-plus-stratified on the remaining long tail. If the tail carries no exploitable structure, the honest conclusion is that caching suffices and stratification is unnecessary.

Why not just partition by document or relation type so few edges cross machines? Partitioners that combine community detection with load balancing (Onizuka et al.) can shrink the boundary. They cannot remove the edges that matter most in multi-document graphs, namely shared entities and authors that tie communities together. We run every policy under both METIS and a document-grouped partitioner. A gain that disappears under the better partitioner would mean partitioning, not sampling, is the lever.

Why not just skip the graph and use a pretrained transformer, as ATLOP does? For single-document relation extraction this is right. ATLOP reaches 63.4 F1 on DocRED and beats graph models on CDR and GDA. Our setting is corpus-scale graphs whose cross-document links do not fit any attention window. ATLOP is reported as a per-document reference on GDA rather than as a competitor.

Proposed Experiments

The primary benchmark is the Open Academic Graph used by HGT and GNS, with paper-field prediction and author disambiguation. No reported absolute HGT metric was found on Lacuna for OAG. The file gives only the 9–21% relative gain, so our full-communication run sets the reference.

The second benchmark is a corpus-level biomedical graph built from the 30,192 GDA abstracts. It has word, sentence, entity-mention, entity and document nodes, joined by containment, adjacency, coreference and shared-entity edges, following the dual-tier and edge-oriented designs. Relation extraction F1 is compared against DHG's reported 83.1% as a single-document reference. The graph uses parser-produced edges, so parser errors are part of the condition.

ogbn-papers100M and Reddit serve as homogeneous controls. There our method collapses to a single stratum, and we predict no advantage over BNS-GCN. A large gain there would mean the effect comes from something other than relation structure.

All runs use the same cluster of multiple GPU machines, the same epochs and the same tuning budget. We report metric versus boundary bytes per epoch, epoch time and peak memory.

The decisive checks are four:

  • Relation strata. On OAG and the GDA corpus graph, the relation-stratified policy dominates tuned uniform BNS and the degree cache on the accuracy-versus-bytes curve.
  • Centrality proxy. $k$-core depth correlates with oracle $c_u$ better than degree. If it does not, the centrality component is dropped in favor of whichever proxy wins.
  • Homogeneous control. Gains vanish on the homogeneous graphs.
  • Robustness to partitioning and caching. Any advantage survives both the better partitioner and the hub cache.