  This paper builds theoretical foundations for the recovery of a newly
proposed class of smooth graph signals, approximately bandlimited graph
signals, under three sampling strategies: uniform sampling, experimentally
designed sampling and active sampling. We then state minimax lower bounds on
the maximum risk for the approximately bandlimited class under these three
sampling strategies and show that active sampling cannot fundamentally
outperform experimentally designed sampling. We propose a recovery strategy to
compare uniform sampling with experimentally designed sampling. As the proposed
recovery strategy lends itself well to statistical analysis, we derive the
exact mean square error for each sampling strategy. To study convergence rates,
we introduce two types of graphs and find that (1) the proposed recovery
strategy achieves the optimal rates; and (2) the experimentally designed
sampling fundamentally outperforms uniform sampling for Type-2 class of graphs.
To validate our proposed recovery strategy, we test it on five specific graphs:
a ring graph with $k$ nearest neighbors, an Erd\H{o}s-R\'enyi graph, a random
geometric graph, a small-world graph and a power-law graph and find that
experimental results match the proposed theory well. This work also presents a
comprehensive explanation for when and why sampling for semi-supervised
learning with graphs works.
