Skip to main content

Sampling and Scaling Large Graphs

Full-batch graph learning keeps all node representations and edges available to every layer. That is simple but can exceed memory on large graphs. Mini-batching is harder than with independent rows because a seed node's representation recursively depends on its neighbors.

Prerequisites​

Complete graph neural networks and message passing. A two-layer model needs the sampled two-hop computation graph that can contribute to each seed.

Learning goals​

  • Explain neighbor explosion and fan-out sampling.
  • Distinguish node-wise, layer-wise, subgraph, and partition batching.
  • Make seeds, direction, replacement, and inclusion probabilities observable.
  • Treat sampled evaluation as an estimator with possible bias and variance.

Scaling contract​

  • Seed: Ada in the valid pre-cutoff, undirected, non-self interaction projection.
  • Sampler: at most one sorted neighbor per frontier node for two hops; this deterministic rule is pedagogical, not statistically representative.
  • Deduplication: repeated sampled nodes are merged; the seed remains in the computation graph.
  • Interpretation limit: lower memory use does not preserve the full-neighborhood result unless the estimator and corrections justify it.

Choosing what to sample​

If each node has up to kk sampled neighbors and the model has LL layers, the sampled dependency tree can still grow on the order of kLk^L before duplicates. Fan-outs should match message-passing depth; extra sampled hops cannot affect the seed through a shallower model.

Uniform neighbor sampling can underrepresent rare edge types or overrepresent nodes reachable by many paths. Weighted sampling changes the estimand. Without-replacement and with-replacement draws have different inclusion probabilities. Partition and subgraph methods trade boundary loss, reuse, and batch correlation. Temporal systems must also prevent the sampler from crossing the prediction cutoff.

Record sampled node and edge counts, high-degree truncation, inclusion rules, seeds, peak memory, throughput, and accuracy by relevant structural slices. A tiny CPU fixture can validate semantics but cannot benchmark production hardware.

Worked example​

neighbors = {
"ada": ["ben", "cy", "fox"],
"ben": ["ada", "cy", "fox"],
"cy": ["ada", "ben", "dia"],
"dia": ["cy", "eli"],
"eli": ["dia"],
"fox": ["ada", "ben"],
}

seed = "ada"
frontier = {seed}
sampled = {seed}
sampled_edges = []
for _ in range(2):
next_frontier = set()
for node in sorted(frontier):
chosen = sorted(neighbors.get(node, []))[:1]
sampled_edges.extend((node, neighbor) for neighbor in chosen)
next_frontier.update(chosen)
sampled.update(next_frontier)
frontier = next_frontier

full_one_hop = sorted(neighbors[seed])
print(f"seed={seed} full_one_hop={full_one_hop}")
print(f"fanouts=[1, 1] sampled_nodes={sorted(sampled)} sampled_edges={sampled_edges}")
print("bias=sorted-first-neighbor-is-not-a-representative-estimator")

Expected output:

seed=ada full_one_hop=['ben', 'cy', 'fox']
fanouts=[1, 1] sampled_nodes=['ada', 'ben'] sampled_edges=[('ada', 'ben'), ('ben', 'ada')]
bias=sorted-first-neighbor-is-not-a-representative-estimator

Limitations​

  • This deterministic sampler is reproducible but intentionally biased.
  • Sampling only nodes can still leave dense induced subgraphs or expensive features.
  • Distributed partitioning introduces communication, staleness, and reproducibility concerns.
  • CPU and memory results from this fixture do not predict accelerator utilization or production latency.

Practice​

Change the per-hop fan-outs to [2, 1]. Write the maximum tree-size bound before running the example, then compare it with the deduplicated node count.

Next steps​

Continue to graph evaluation and leakage to align splits, neighborhoods, negatives, and metrics with the deployment question.

Primary sources​

Checked 2026-10-18: W. L. Hamilton, R. Ying, and J. Leskovec, GraphSAGE; PyTorch Geometric, Scaling GNNs via Neighbor Sampling; PyTorch Geometric, Advanced Mini-Batching.