Superiority of GNN over NN in generalizing bandlimited functions. (arXiv:2206.05904v2 [cs.LG] UPDATED)

We constructively show, via rigorous mathematical arguments, that GNN
architectures outperform those of NN in approximating bandlimited functions on
compact $d$-dimensional Euclidean grids. We show that the former only need
$\mathcal{M}$ sampled functional values in order to achieve a uniform
approximation error of $O_{d}(2^{-\mathcal{M}^{1/d}})$ and that this error rate
is optimal, in the sense that, NNs might achieve worse.

arxiv