  Graph Neural Networks (GNNs) have emerged as formidable resources for
processing graph-based information across diverse applications. While the
expressive power of GNNs has traditionally been examined in the context of
graph-level tasks, their potential for node-level tasks, such as node
classification, where the goal is to interpolate missing node labels from the
observed ones, remains relatively unexplored. In this study, we investigate the
proficiency of GNNs for such classifications, which can also be cast as a
function interpolation problem. Explicitly, we focus on ascertaining the
optimal configuration of weights and layers required for a GNN to successfully
interpolate a band-limited function over Euclidean cubes. Our findings
highlight a pronounced efficiency in utilizing GNNs to generalize a bandlimited
function within an $\varepsilon$-error margin. Remarkably, achieving this task
necessitates only $O_d((\log\varepsilon^{-1})^d)$ weights and
$O_d((\log\varepsilon^{-1})^d)$ training samples. We explore how this criterion
stacks up against the explicit constructions of currently available Neural
Networks (NNs) designed for similar tasks. Significantly, our result is
obtained by drawing an innovative connection between the GNN structures and
classical sampling theorems. In essence, our pioneering work marks a meaningful
contribution to the research domain, advancing our understanding of the
practical GNN applications.
