Understanding Generalization in Node and Link Prediction

Using message-passing graph neural networks (MPNNs) for node and link prediction iscrucial in various scientific and industrial domains, which has led to the development ofdiverse MPNN architectures. Besides working well in practical settings, their ability togeneralize beyond the training set remains poorly understood. While some studieshave explored MPNNs’ generalization in graph-level prediction tasks, much lessattention has been given to node- and link-level predictions. Existing works often rely onunrealistic i.i.d. assumptions, overlooking possible correlations between nodes or links,and assuming fixed aggregation and impractical loss functions while neglecting theinfluence of graph structure. In this work, we introduce a unified framework to analyzethe generalization properties of MPNNs in inductive and transductive node and linkprediction settings, incorporating diverse architectural parameters and loss functions andquantifying the influence of graph structure. Additionally, our proposed generalizationframework can be applied beyond graphs to any classification task under the inductive ortransductive setting. Our empirical study supports our theoretical insights, deepening ourunderstanding of MPNNs’ generalization capabilities in these tasks.