  Reconstructing a signal on a graph from noisy observations of a subset of the
vertices is a fundamental problem in the field of graph signal processing. This
paper investigates how sample size affects reconstruction error in the presence
of noise via an in-depth theoretical analysis of the two most common
reconstruction methods in the literature, least-squares reconstruction (LS) and
graph-Laplacian regularised reconstruction (GLR). Our theorems show that at
sufficiently low signal-to-noise ratios (SNRs), under these reconstruction
methods we may simultaneously decrease sample size and decrease average
reconstruction error. We further show that at sufficiently low SNRs, for LS
reconstruction we have a $\Lambda$-shaped error curve and for GLR
reconstruction, a sample size of $ \mathcal{O}(\sqrt{N})$, where $N$ is the
total number of vertices, results in lower reconstruction error than near full
observation. We present thresholds on the SNRs, $\tau$ and $\tau_{GLR}$, below
which the error is non-monotonic, and illustrate these theoretical results with
experiments across multiple random graph models, sampling schemes and SNRs.
These results demonstrate that any decision in sample-size choice has to be
made in light of the noise levels in the data.
