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 MPNNs' generalization 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 to analyze 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 under the inductive or transductive setting. Our empirical study supports our theoretical insights, deepening our understanding of MPNNs' generalization capabilities in these tasks.

翻译：使用消息传递图神经网络（MPNNs）进行节点与链接预测在众多科学与工业领域中至关重要，这推动了多种MPNN架构的发展。尽管在实际应用中表现良好，但其在训练集之外的泛化能力仍未被充分理解。尽管已有研究探索了MPNNs在图级预测任务中的泛化性，但对节点级和链接级预测的关注则少得多。现有工作通常依赖于不现实的独立同分布假设，忽视了节点或链接之间可能存在的相关性，并假设固定的聚合方式和不切实际的损失函数，同时忽略了图结构的影响。在本研究中，我们引入了一个统一框架，以分析MPNNs在归纳式和直推式节点与链接预测设置中的泛化特性，该框架整合了多样化的架构参数和损失函数，并量化了图结构的影响。此外，我们提出的泛化框架可扩展至图以外的任何分类任务，适用于归纳或直推设置。我们的实证研究支持了理论见解，深化了对MPNNs在这些任务中泛化能力的理解。