A note on the VC dimension of 1-dimensional GNNs
<|reference_start|>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.<|reference_end|>
@article{daniëls2024a,
    title={A note on the VC dimension of 1-dimensional GNNs},
    author={Noah Dani"els and Floris Geerts},
    journal={arXiv preprint arXiv:2410.07829},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.07829},
    primaryClass={cs.LG}
}