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 sampled neighbors and the model has layers, the sampled dependency tree can still grow on the order of 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.