Budget sampled neighborhoods without losing estimator semantics

Define f₁ as the number of neighbors drawn for each seed and f₂ as the number drawn for each first-hop occurrence. With B seeds and two layers, an occurrence-tree upper budget is B+ Bf₁+ Bf₁f₂ when all requested draws are available. Low degree without replacement can reduce counts. Shared nodes and repeated draws can reduce unique feature rows after compaction. Conversely, returning the induced subgraph can add edges beyond those sampled along the expansion tree, so node and edge budgets need separate limits.

GraphSAGE made bounded neighborhood sampling central to scalable aggregation, while PinSAGE uses random-walk-derived importance to construct neighborhoods for its recommendation setting. Those samplers do not define the same distribution. Record fanout ordering, edge types, incoming or outgoing direction, replacement and time constraints. A heterogeneous graph can have a separate fanout for each relation and therefore a larger combined expansion than a single scalar list suggests. Confirm the loader’s actual sampled-node and sampled-edge counters rather than treating configuration as measurement.

For k independent uniform draws with replacement from d distinct neighbors, each neighbor is omitted with probability (1−1/d)^k. Summing inclusion indicators gives the expected unique count. For d=4 and k=4 it is only 4(1−0.75⁴)=2.734375. Drawing four times therefore does not normally mean fetching four distinct feature rows. Without-replacement sampling has a different unique-count rule, and a sampler that switches policy for low-degree nodes must make that behavior visible.

Duplicate collapse for feature retrieval can preserve computation if the original draw multiplicities or weights remain attached to messages. Dropping multiplicities changes a sum. For neighbors with values 2 and 10, two uniform replacement draws have an unbiased full-sum estimator equal to the draw sum, whose expectation is 12. If duplicates are collapsed and their weights discarded, the possible sums 2,12,12,10 average to 9. This example concerns sums; an unweighted unique-set mean under uniform symmetry is not automatically biased in the same way.

A uniform sample mean can estimate the full neighbor mean before nonlinearities. To estimate a full sum from k uniform replacement draws, scale their sum by d/k. With unequal draw probabilities, importance weights must match the target and sampling design; unique-set estimators instead need inclusion probabilities. Nonlinear activation, sampled normalization and multiple stochastic layers can introduce bias even when one local linear estimate is unbiased. State whether the model intentionally trains on sampled neighborhoods or aims to approximate a particular full-graph operator.

In the probability lab, Reset and set both p=0.25 and n=4. Predict one occurrence on average for a particular neighbor across four independent draws, and zero occurrences with probability 0.75⁴≈0.3164. Play highlights exact binomial outcomes, not neighbor samples. This models one fixed neighbor’s draw count only; the counts of different neighbors are dependent and the lab does not compact a minibatch or estimate nonlinear GNN error. Use the calculation to explain why four draws can cover substantially fewer than four distinct neighbors.