Describe the process of graph sampling in GNNs and its benefits.
Instruction: Explain graph sampling strategies and how they impact the efficiency and effectiveness of GNNs.
Updated
Example Answer
Graph sampling builds a manageable computation graph for a minibatch. In node-wise neighbor sampling, I start with the target nodes and sample a limited number of neighbors for each required layer. I then compute the representations needed to produce predictions for those targets.
This is different from layer-wise sampling, which selects a shared set of nodes for a layer, and from subgraph sampling, which trains on a sampled connected portion of the graph. I would choose the scheme based on degree distribution, depth, storage, and which dependencies matter to the task.
Fixed fanouts make a batch more predictable, but they do not make cost independent of depth. Neighbor expansion can grow as a product across layers. Sampling also changes which messages are available, so I would examine variance and quality loss, repeat evaluations when inference is sampled, and avoid claiming a universal speedup.
Worked Example
For 32 target nodes, sampling 10 neighbors and then 5 neighbors per first-hop node can require up to 32 + 32×10 + 32×10×5 = 1,952 node occurrences before overlap is deduplicated. Adding another sampled layer can multiply the cost again.