Covered Forest: Fine-grained generalization analysis of graph neural networks

Antonis Vasileiou, Ben Finkelshtein, Floris Geerts, Ron Levie, Christopher Morris
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:60984-61034, 2025.

Abstract

The expressive power of message-passing graph neural networks (MPNNs) is reasonably well understood, primarily through combinatorial techniques from graph isomorphism testing. However, MPNNs’ generalization abilities—making meaningful predictions beyond the training set—remain less explored. Current generalization analyses often overlook graph structure, limit the focus to specific aggregation functions, and assume the impractical, hard-to-optimize $0$-$1$ loss function. Here, we extend recent advances in graph similarity theory to assess the influence of graph structure, aggregation, and loss functions on MPNNs’ generalization abilities. Our empirical study supports our theoretical insights, improving our understanding of MPNNs’ generalization properties.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-vasileiou25a, title = {Covered Forest: Fine-grained generalization analysis of graph neural networks}, author = {Vasileiou, Antonis and Finkelshtein, Ben and Geerts, Floris and Levie, Ron and Morris, Christopher}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {60984--61034}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/vasileiou25a/vasileiou25a.pdf}, url = {https://proceedings.mlr.press/v267/vasileiou25a.html}, abstract = {The expressive power of message-passing graph neural networks (MPNNs) is reasonably well understood, primarily through combinatorial techniques from graph isomorphism testing. However, MPNNs’ generalization abilities—making meaningful predictions beyond the training set—remain less explored. Current generalization analyses often overlook graph structure, limit the focus to specific aggregation functions, and assume the impractical, hard-to-optimize $0$-$1$ loss function. Here, we extend recent advances in graph similarity theory to assess the influence of graph structure, aggregation, and loss functions on MPNNs’ generalization abilities. Our empirical study supports our theoretical insights, improving our understanding of MPNNs’ generalization properties.} }
Endnote
%0 Conference Paper %T Covered Forest: Fine-grained generalization analysis of graph neural networks %A Antonis Vasileiou %A Ben Finkelshtein %A Floris Geerts %A Ron Levie %A Christopher Morris %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-vasileiou25a %I PMLR %P 60984--61034 %U https://proceedings.mlr.press/v267/vasileiou25a.html %V 267 %X The expressive power of message-passing graph neural networks (MPNNs) is reasonably well understood, primarily through combinatorial techniques from graph isomorphism testing. However, MPNNs’ generalization abilities—making meaningful predictions beyond the training set—remain less explored. Current generalization analyses often overlook graph structure, limit the focus to specific aggregation functions, and assume the impractical, hard-to-optimize $0$-$1$ loss function. Here, we extend recent advances in graph similarity theory to assess the influence of graph structure, aggregation, and loss functions on MPNNs’ generalization abilities. Our empirical study supports our theoretical insights, improving our understanding of MPNNs’ generalization properties.
APA
Vasileiou, A., Finkelshtein, B., Geerts, F., Levie, R. & Morris, C.. (2025). Covered Forest: Fine-grained generalization analysis of graph neural networks. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:60984-61034 Available from https://proceedings.mlr.press/v267/vasileiou25a.html.

Related Material