Understanding Generalization in Node and Link Prediction

Antonis Vasileiou, Timo Stoll, Christopher Morris
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:145-153, 2026.

Abstract

Using message-passing graph neural networks (MPNNs) for node and link prediction is crucial in various scientific and industrial domains, which has led to the development of diverse MPNN architectures. Besides working well in practical settings, their ability to generalize beyond the training set remains poorly understood. While some studies have explored the generalization of MPNNs in graph-level prediction tasks, much less attention has been given to node- and link-level predictions. Existing works often rely on unrealistic i.i.d. assumptions, overlooking possible correlations between nodes or links, and assuming fixed aggregation and impractical loss functions while neglecting the influence of graph structure. In this work, we introduce a unified framework for analyzing the generalization properties of MPNNs in inductive and transductive node and link prediction settings, incorporating diverse architectural parameters and loss functions, and quantifying the influence of graph structure. Additionally, our proposed generalization framework can be applied beyond graphs to any classification task, regardless of whether it is inductive or transductive. Our empirical study supports our theoretical insights, deepening our understanding of MPNNs’ generalization capabilities in these tasks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-vasileiou26a, title = { Understanding Generalization in Node and Link Prediction }, author = {Vasileiou, Antonis and Stoll, Timo and Morris, Christopher}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {145--153}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/vasileiou26a/vasileiou26a.pdf}, url = {https://proceedings.mlr.press/v300/vasileiou26a.html}, abstract = { Using message-passing graph neural networks (MPNNs) for node and link prediction is crucial in various scientific and industrial domains, which has led to the development of diverse MPNN architectures. Besides working well in practical settings, their ability to generalize beyond the training set remains poorly understood. While some studies have explored the generalization of MPNNs in graph-level prediction tasks, much less attention has been given to node- and link-level predictions. Existing works often rely on unrealistic i.i.d. assumptions, overlooking possible correlations between nodes or links, and assuming fixed aggregation and impractical loss functions while neglecting the influence of graph structure. In this work, we introduce a unified framework for analyzing the generalization properties of MPNNs in inductive and transductive node and link prediction settings, incorporating diverse architectural parameters and loss functions, and quantifying the influence of graph structure. Additionally, our proposed generalization framework can be applied beyond graphs to any classification task, regardless of whether it is inductive or transductive. Our empirical study supports our theoretical insights, deepening our understanding of MPNNs’ generalization capabilities in these tasks. } }
Endnote
%0 Conference Paper %T Understanding Generalization in Node and Link Prediction %A Antonis Vasileiou %A Timo Stoll %A Christopher Morris %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-vasileiou26a %I PMLR %P 145--153 %U https://proceedings.mlr.press/v300/vasileiou26a.html %V 300 %X Using message-passing graph neural networks (MPNNs) for node and link prediction is crucial in various scientific and industrial domains, which has led to the development of diverse MPNN architectures. Besides working well in practical settings, their ability to generalize beyond the training set remains poorly understood. While some studies have explored the generalization of MPNNs in graph-level prediction tasks, much less attention has been given to node- and link-level predictions. Existing works often rely on unrealistic i.i.d. assumptions, overlooking possible correlations between nodes or links, and assuming fixed aggregation and impractical loss functions while neglecting the influence of graph structure. In this work, we introduce a unified framework for analyzing the generalization properties of MPNNs in inductive and transductive node and link prediction settings, incorporating diverse architectural parameters and loss functions, and quantifying the influence of graph structure. Additionally, our proposed generalization framework can be applied beyond graphs to any classification task, regardless of whether it is inductive or transductive. Our empirical study supports our theoretical insights, deepening our understanding of MPNNs’ generalization capabilities in these tasks.
APA
Vasileiou, A., Stoll, T. & Morris, C.. (2026). Understanding Generalization in Node and Link Prediction . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:145-153 Available from https://proceedings.mlr.press/v300/vasileiou26a.html.

Related Material