Scaling a GNN to a Billion-Node Graph

“Billion-node graph” sounds like a GPU problem. Work the arithmetic and it is a memory-and-bandwidth problem, and the GPU turns out to be the part with room to spare. Here is the calculation, with every input named.

The inputs, stated

Assume a graph of 1,000,000,000 nodes and 10,000,000,000 directed edges — an average out-degree of 10, which is typical for a web, social or transaction graph. Assume 128-dimensional node features stored in float32 (4 bytes). Assume a three-layer model with hidden width 256, trained by neighbour sampling with fan-out [15, 10, 5] and a batch of 1,000 seed nodes. Assume the hardware is one GPU with 80 GB of device memory attached to a host over PCIe.

Every figure below is derived from exactly those numbers. For a real anchor: the Open Graph Benchmark’s ogbn-papers100M holds 111,059,956 nodes and 1,615,685,872 edges with 128-dimensional features, so the assumed graph is roughly nine times its node count and six times its edges — the same order, not a fantasy.

The feature store is the wall

nodes                   1,000,000,000
feature dimension       128
bytes per value         4        (float32)

feature matrix  = 1e9 x 128 x 4 bytes
                = 512,000,000,000 bytes
                = 512 GB

Half a terabyte, before any model exists. That single number decides the shape of the whole system. It does not fit in 80 GB of device memory, it does not fit in a 256 GB host, and it is not something sampling reduces — the sampler chooses which rows to read, but all the rows have to be somewhere readable.

Check it against the real dataset: 111,059,956 nodes times 128 times 4 bytes is 56.9 GB. That does fit in a large host’s RAM, which is exactly why ogbn-papers100M is trainable on one well-specified machine and a billion-node graph is not.

What the adjacency costs

Stored in compressed sparse row form, the structure is one index array over edges and one offset array over nodes.

edge index array   1e10 edges x 8 bytes (int64)  =  80 GB
row offset array   (1e9 + 1) x 8 bytes           =   8 GB
                                                   -------
                                                     88 GB

with int32 node ids (valid up to 2,147,483,647 nodes):
edge index array   1e10 x 4 bytes                =  40 GB
row offset array   1e9 x 8 bytes (edge counts
                   exceed int32, keep 64-bit)    =   8 GB
                                                   -------
                                                     48 GB

So structure is 88 GB at int64 and 48 GB if you narrow the node ids, against 512 GB of features. The intuition that a graph with ten billion edges is dominated by its edges is wrong at this feature dimension: the features are roughly six times larger. Only below about 22 dimensions per node does the int64 adjacency overtake the feature matrix, which is far thinner than any learned or text-derived feature set.

The per-batch working set

Neighbour sampling bounds the computation per batch, and the bound is a product, which is why fan-out is the parameter that matters most.

nodes touched per seed, fan-out [15, 10, 5]:
  hop 0 (seed)            1
  hop 1                  15
  hop 2             15 x 10 = 150
  hop 3        15 x 10 x  5 = 750
                        ----
                         916

batch of 1,000 seeds  ->  916,000 node slots (before de-duplication)
feature bytes fetched = 916,000 x 128 x 4 = 469 MB per batch

469 MB of feature reads to train on 1,000 labelled nodes. Now vary only the fan-out and hold everything else fixed:

fan-out        slots/seed   slots/batch   feature bytes/batch
[15, 10]              166       166,000        85 MB
[15, 10,  5]          916       916,000       469 MB
[15, 10, 10]        1,666     1,666,000       853 MB
[25, 10, 10]        2,776     2,776,000     1,421 MB

The growth is multiplicative in depth, which is the single most important fact about training a deep GNN by sampling. Adding one layer with fan-out 10 multiplies the per-batch data by roughly ten. William Hamilton, Rex Ying and Jure Leskovec make this point directly in GraphSAGE (NeurIPS 2017), reporting that in practice they achieved high performance with “K=2 and S1·S2 ≤ 500” — a depth of two and a product of per-hop sample sizes under 500.

De-duplication cuts these numbers, sometimes a lot: on a dense graph many sampled paths land on the same high-degree node, and the unique node count in a batch can be several times below the slot count. It never increases them, so treat the slot count as an upper bound.

One number that is easy to miss: the seed nodes are labelled nodes, and on a billion-node graph the labelled fraction is usually well under a percent. If one million nodes carry labels, an epoch is 1,000 batches, not a million, and the entire training run touches a small neighbourhood-expansion of that one million rather than the full billion. Most of the feature store is never read during training at all. It is read at inference, when you do want a prediction for every node, and that asymmetry is why training capacity and serving capacity are separate sizing questions.

Against 80 GB of device memory, even the largest row above is trivial. The activations are of the same order: 916,000 nodes times 256 hidden units times 4 bytes is 938 MB for one layer’s output, and stored activations for the backward pass are a small multiple of that. Nothing here comes close to filling the GPU. The device is idle waiting for the host to produce the next batch, which is the real finding.

What you can do about each number

• Halve the feature store by narrowing the dtype. float16 features take 256 GB instead of 512 GB and int8 takes 128 GB. Node features are usually already noisy embeddings, so the precision loss is often invisible — but it is a quality decision, not a free one, and it is testable on a held-out split before you commit.
• Cut the fan-out before you cut anything else. The table above is the cheapest lever you have, and the depth you were reaching for probably does not help anyway.
• Partition across hosts. Split the node set, keep each partition’s features on its own machine, and fetch remote features over the network. This is what the distributed modes of the major graph libraries do. The cost is that the network round-trip replaces the PCIe transfer, so partition quality — how few edges cross partitions — becomes the performance variable.
• Change the sampler. Subgraph sampling removes the multiplicative depth term entirely, at the cost of a different bias. That trade is worked in graph sampling strategies.
• Keep features on fast local storage, not RAM. An NVMe-backed feature store with a cache for high-degree nodes turns a 512 GB capacity problem into a bandwidth problem, and high-degree nodes are sampled far more often than uniform, so the cache hit rate is much better than its size suggests.

What none of these levers changes is the sampler itself. Expanding a three-hop neighbourhood for 1,000 seeds means roughly 916,000 random accesses into the CSR structure per batch, each one a pointer chase into 88 GB with no locality. That work is single-threaded per batch in the naive implementation and it is why the standard advice is to run several sampler worker processes and prefetch the next batch while the current one trains. If your GPU utilisation sits low during GNN training, the sampler is the first place to look rather than the model — the arithmetic above says the device has nothing else to be waiting on.