# Theoretical guarantees for the advantage of GNNs over NNs in generalizing bandlimited functions on Euclidean cubes

arXiv: https://arxiv.org/abs/2206.05904 · HTML: https://mlsanity.com/paper/2206.05904/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 49 references that are in the map.
- First posted on arXiv 13 Jun 2022.

## Builds on (most cited first, 14 of 14)

- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [On the Expressive Power of Deep Polynomial Neural Networks](https://mlsanity.com/paper/1905.12207/) (2019)
- [Approximation and Non-parametric Estimation of ResNet-type Convolutional Neural Networks](https://mlsanity.com/paper/1903.10047/) (2019)
- [Exponential Convergence of the Deep Neural Network Approximation for Analytic Functions](https://mlsanity.com/paper/1807.00297/) (2018)
- [Deep Representation Learning for Social Network Analysis](https://mlsanity.com/paper/1904.08547/) (2019)
- [Graph Neural Networks for Multimodal Single-Cell Data Integration](https://mlsanity.com/paper/2203.01884/) (2022)
- [A Functional Perspective on Learning Symmetric Functions with Neural Networks](https://mlsanity.com/paper/2008.06952/) (2020)

## Built on by (most cited first, 4 of 4)

- [Transferability of Graph Neural Networks using Graphon and Sampling Theories](https://mlsanity.com/paper/2307.13206/) (2023)
- [Learning from one graph: transductive learning guarantees via the geometry of small random worlds](https://mlsanity.com/paper/2509.06894/) (2025)
- [Bridging Smoothness and Approximation: Theoretical Insights into Over-Smoothing in Graph Neural Networks](https://mlsanity.com/paper/2407.01281/) (2024)
- [Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach](https://mlsanity.com/paper/2609.13836/) (2026)

## Abstract (arXiv)

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 Od((logvarepsilon-1)d) weights and Od((logvarepsilon-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.