  Large-scale graph machine learning is challenging as the complexity of
learning models scales with the graph size. Subsampling the graph is a viable
alternative, but sampling on graphs is nontrivial as graphs are non-Euclidean.
Existing graph sampling techniques require not only computing the spectra of
large matrices but also repeating these computations when the graph changes,
e.g., grows. In this paper, we introduce a signal sampling theory for a type of
graph limit -- the graphon. We prove a Poincar\'e inequality for graphon
signals and show that complements of node subsets satisfying this inequality
are unique sampling sets for Paley-Wiener spaces of graphon signals. Exploiting
connections with spectral clustering and Gaussian elimination, we prove that
such sampling sets are consistent in the sense that unique sampling sets on a
convergent graph sequence converge to unique sampling sets on the graphon. We
then propose a related graphon signal sampling algorithm for large graphs, and
demonstrate its good empirical performance on graph machine learning tasks.
