mlsanityData to 7 Oct 2026

VC dimension of Graph Neural Networks with Pfaffian activation functions

arXiv 2401.12362 ↗First posted 22 Jan 2024stat.ML cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) have emerged in recent years as a powerful tool to learn tasks across a wide range of graph domains in a data-driven fashion; based on a message passing mechanism, GNNs have gained increasing popularity due to their intuitive formulation, closely linked with the Weisfeiler-Lehman (WL) test for graph isomorphism, to which they have proven equivalent. From a theoretical point of view, GNNs have been shown to be universal approximators, and their generalization capability (namely, bounds on the Vapnik Chervonekis (VC) dimension) has recently been investigated for GNNs with piecewise polynomial activation functions. The aim of our work is to extend this analysis on the VC dimension of GNNs to other commonly used activation functions, such as sigmoid and hyperbolic tangent, using the framework of Pfaffian function theory. Bounds are provided with respect to architecture parameters (depth, number of neurons, input size) as well as with respect to the number of colors resulting from the 1-WL test applied on the graph domain. The theoretical analysis is supported by a preliminary experimental study.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 26 of its 60 references that are in the map. First posted on arXiv 22 Jan 2024.

Builds on

26 of 60 references.

References · 26

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  7. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  8. 2019Graph Transformer Networkscited by 520
  9. 2019Tackling Climate Change with Machine Learningcited by 264
  10. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  11. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  12. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
14 more
  1. 2019Understanding Attention and Generalization in Graph Neural Networkscited by 169
  2. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
  3. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  4. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  5. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  6. 2019Nonlinear Approximation and (Deep) ReLU Networkscited by 45
  7. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  8. 2023A Survey on Graph Diffusion Models: Generative AI in Science for Molecule, Protein and Materialcited by 34
  9. 2023WL meet VCcited by 30
  10. 2020Deep learning-based reduced order models in cardiac electrophysiologycited by 22
  11. 2021On the approximation capability of GNNs in node classification/regression taskscited by 9
  12. 2021Invariance, encodings, and generalization: learning identity effects with neural networkscited by 5
  13. 2020Generalizing Outside the Training Set: When Can Neural Networks Learn Identity Effects?cited by 4
  14. 2023Generalization Limits of Graph Neural Networks in Identity Effects Learningcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 2.

6 papers.

  1. 2025Understanding Generalization in Node and Link Predictioncited by 2
  2. 2025Beyond Universal Approximation Theorems: Algorithmic Uniform Approximation by Neural Networks Trained with Noisy Datacited by 1
  3. 2025On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometrycited by 1
  4. 2026Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexitycited by 1
  5. 2024Mesh-Informed Reduced Order Models for Aneurysm Rupture Risk Predictioncited by 0
  6. 2026Tubular Neighbourhoods of Pfaffian Sets and Applications to Neural Networkscited by 0