A note on the VC dimension of 1-dimensional GNNs
Graph Neural Networks (GNNs) have become an essential tool for analyzing graph-structured data, leveraging their ability to capture complex relational information. While the expressivity of GNNs, particularly their equivalence to the Weisfeiler-Leman (1-WL) isomorphism test, has been well-documented, understanding their generalization capabilities remains critical. This paper focuses on the generalization of GNNs by investigating their Vapnik-Chervonenkis (VC) dimension. We extend previous results to demonstrate that 1-dimensional GNNs with a single parameter have an infinite VC dimension for unbounded graphs. Furthermore, we show that this also holds for GNNs using analytic non-polynomial activation functions, including the 1-dimensional GNNs that were recently shown to be as expressive as the 1-WL test. These results suggest inherent limitations in the generalization ability of even the most simple GNNs, when viewed from the VC dimension perspective.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Molecular Classification Using Hyperdimensional Graph Classification
Our work introduces an innovative approach to graph learning by leveraging Hyperdimensional Computing. Graphs serve as a widely embraced method for conveying information, and their utilization in learning has gained sign…
ClassificationGraph ClassificationGraph LearningImproved Image Classification with Manifold Neural Networks
Graph Neural Networks (GNNs) have gained popularity in various learning tasks, with successful applications in fields like molecular biology, transportation systems, and electrical grids. These fields naturally use graph…
Classificationimage-classificationImage ClassificationSympGNNs: Symplectic Graph Neural Networks for identifiying high-dimensional Hamiltonian systems and node classification
Existing neural network models to learn Hamiltonian systems, such as SympNets, although accurate in low-dimensions, struggle to learn the correct dynamics for high-dimensional many-body systems. Herein, we introduce Symp…
Node ClassificationMultidimensional unstructured sparse recovery via eigenmatrix
This note considers the multidimensional unstructured sparse recovery problems. Examples include Fourier inversion and sparse deconvolution. The eigenmatrix is a data-driven construction with desired approximate eigenval…
Graph Neural Networks for Motion Planning
This paper investigates the feasibility of using Graph Neural Networks (GNNs) for classical motion planning problems. We propose guiding both continuous and discrete planning algorithms using GNNs' ability to robustly en…
Motion Planning