# Barron Space for Graph Convolution Neural Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 71 references that are in the map.
- First posted on arXiv 6 Nov 2023.

## Builds on (most cited first, 30 of 31)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [A Survey of Convolutional Neural Networks: Analysis, Applications, and Prospects](https://mlsanity.com/paper/2004.02806/) (2020)
- [Recent Advances in Convolutional Neural Networks](https://mlsanity.com/paper/1512.07108/) (2015)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Adaptive Graph Convolutional Neural Networks](https://mlsanity.com/paper/1801.03226/) (2018)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [Discrete Signal Processing on Graphs: Frequency Analysis](https://mlsanity.com/paper/1307.0468/) (2013)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [Representation formulas and pointwise properties for Barron functions](https://mlsanity.com/paper/2006.05982/) (2020)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Understanding neural networks with reproducing kernel Banach spaces](https://mlsanity.com/paper/2109.09710/) (2021)
- [Characterization of the Variation Spaces Corresponding to Shallow Neural Networks](https://mlsanity.com/paper/2106.15002/) (2021)
- [Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nystr"om Method, and Use of Kernels in Machine Learning: Tutorial and Survey](https://mlsanity.com/paper/2106.08443/) (2021)
- [Stationary signal processing on graphs](https://mlsanity.com/paper/1601.02522/) (2016)
- [On Reproducing Kernel Banach Spaces: Generic Definitions and Unified Framework of Constructions](https://mlsanity.com/paper/1901.01002/) (2019)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Nonparametric regression using over-parameterized shallow ReLU neural networks](https://mlsanity.com/paper/2306.08321/) (2023)
- [Optimal rates of approximation by shallow ReLUk neural networks and applications to nonparametric regression](https://mlsanity.com/paper/2304.01561/) (2023)
- [Graph Signal Processing and Deep Learning: Convolution, Pooling, and Topology](https://mlsanity.com/paper/2008.01247/) (2020)
- [Graph Fourier transform based on singular value decomposition of directed Laplacian](https://mlsanity.com/paper/2205.06242/) (2022)

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

- [Hypothesis Spaces for Deep Learning](https://mlsanity.com/paper/2403.03353/) (2024)

## Abstract (arXiv)

Graph convolutional neural network (GCNN) operates on graph domain and it has achieved a superior performance to accomplish a wide range of tasks. In this paper, we introduce a Barron space of functions on a compact domain of graph signals. We prove that the proposed Barron space is a reproducing kernel Banach space, it can be decomposed into the union of a family of reproducing kernel Hilbert spaces with neuron kernels, and it could be dense in the space of continuous functions on the domain. Approximation property is one of the main principles to design neural networks. In this paper, we show that outputs of GCNNs are contained in the Barron space and functions in the Barron space can be well approximated by outputs of some GCNNs in the integrated square and uniform measurements. We also estimate the Rademacher complexity of functions with bounded Barron norm and conclude that functions in the Barron space could be learnt from their random samples efficiently.