The Vapnik–Chervonenkis dimension of graph and recursive neural networks
Open accessAbstract
The Vapnik-Chervonenkis dimension (VC-dim) characterizes the sample learning complexity of a classification model and it is often used as an indicator for the generalization capability of a learning method. The VC-dim has been studied on common feed-forward neural networks, but it has yet to be studied on Graph Neural Networks (GNNs) and Recursive Neural Networks (RecNNs). This paper provides upper bounds on the order of growth of the VC-dim of GNNs and RecNNs. GNNs and RecNNs are from a new class of neural network models which are capable of processing inputs that are given as graphs. A graph is a data structure that generalizes the representational power of vectors and sequences, via the ability to represent dependencies or relationships between feature vectors. It was shown previously that the ability of recurrent neural networks to process sequences increases the VC-dim when compared to the VC-dim of Neural Networks, which are limited to processing vectors. Since graphs are a more general form than sequences, the question arises how this will affect the VC-dimension of GNNs and RecNNs. A main finding in this paper is that the upper bounds on the VC-dim for GNNs and RecNNs are comparable to the upper bounds for recurrent neural networks. The result also suggests that the generalization capability of such models increases with the number of connected nodes.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Given the number of model parameter p and the number of nodes n, Scarselli et al. derive that the VC dimension of a GNN* is O(p^4 n^2) if it uses the sigmoid or tangent hyperbolic activation and is O(p^2 n) if it uses the piecewise polynomial activation function.
“Given the number of model parameter p and the number of nodes n , Scarselli et al. [103] derive that the VC dimension of a GNN* [15] is O ( p 4 n 2 ) if it uses the sigmoid or tangent hyperbolic activation and is O ( p 2 n ) if it uses the piecewise polynomial activation function.”
From A Comprehensive Survey on Graph Neural Networks (2021) · cites this paper as [103]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Powell, M. J. D. (1964) · The Computer Journal · doi:10.1093/comjnl/7.2.155 · Cited by 4,632 · see citing works
VQA: Visual Question Answering
Antol, S., Agrawal, A., Lu, J., Mitchell, M., Batra, D., Zitnick, C. L., & Parikh, D. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.279 · Cited by 4,487 · see citing works
Geometric Deep Learning: Going beyond Euclidean data
Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., & Vandergheynst, P. (2017) · IEEE Signal Processing Magazine · doi:10.1109/msp.2017.2693418 · Cited by 3,661 · see citing works
Introduction to Statistical Relational Learning
(2007) · doi:10.7551/mitpress/7432.001.0001 · Cited by 1,643 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000 · see citing works
Graph neural networks: A review of methods and applications
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2020) · AI Open · doi:10.1016/j.aiopen.2021.01.001 · Cited by 6,880 · see citing works
- Authors
- Scarselli, F., Tsoi, A. C., & Hagenbuchner, M.
- Affiliations
- University of Siena (IT)
- University of Wollongong (AU)
- Corresponding author
- Scarselli, Franco
- Venue
- Neural Networks
- Publisher
- Elsevier BV
- Published
- 2018-12
- Volume
- 108
- Pages
- 248-259
- ISSN
- 0893-6080 (ISSN-L)
- OpenAlex
- W2889399096
- Cited by
- 69
- References
- 4
- Citations by year
- 2026: 6 · 2025: 8 · 2024: 11 · 2023: 9 · 2022: 6 · 2021: 14 · 2020: 12 · 2019: 2 · 2018: 1
- FWCI
- 4.06
- Type
- journal article
- Language
- en
- Open access
- Licence
- Locations
- Neural Networks (publishedVersion)
- PubMed (publishedVersion)
- Research Online (University of Wollongong) (submittedVersion)
- Use Siena air (University of Siena) (submittedVersion, cc-by-nc-nd)
- Funders
- Fundo para o Desenvolvimento Tecnológico das Telecomunicações
- Fundo para o Desenvolvimento das Ciências e da Tecnologia (059/2010/A3)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Keywords
- VC dimension, graph neural networks, recursive neural networks, model generalization, sample complexity, upper bounds, recurrent neural networks, graph classification
- MeSH terms
- Machine Learning, Computer Graphics, Neural Networks, Computer
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
