BV-Sampler: Bias-Variance-Aware Sampling for Graph Neural Networks

Neighborhood sampling enables scalable graph neural networks but introduces aggregation error under finite computation budgets. We propose BV-Sampler, a bias-variance-aware framework combining feature-aware sampling, contribution weighting, and sampler-induced contrastive learning under sparse supervision. We characterize optimal weights and proposals when the other is fixed, and develop an efficient diagonal surrogate. We also analyze layer-wise error accumulation and connect independent sampler-induced view disagreement to aggregation variance, yielding an encoded alignment bound. Experiments demonstrate competitive prediction across rich- and sparse-label settings, with the largest gains under sampled inference. On low-label OGBN-arXiv, BV-Sampler improves Micro-F1 by 6.77 percentage points over LABOR and 2.95 points over GraphSAINT with DGI. Ablations and direct diagnostics support the contributions of sampling and weighting and demonstrate reduced MSE through a bias–variance trade-off.