Understanding Generalization in Node and Link Prediction

• URL: http://arxiv.org/abs/2507.00927v1
• Date: Tue, 01 Jul 2025 16:34:19 GMT
• Title: Understanding Generalization in Node and Link Prediction
• Authors: Antonis Vasileiou, Timo Stoll, Christopher Morris,
• Abstract summary: We introduce a unified framework to analyze the generalization properties of MPNNs in inductive and transductive node and link prediction settings.<n>Our proposed framework can be applied beyond graphs to any classification task under the inductive or transductive setting.
• Score: 4.489098782459289
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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.

Related papers

• Demystifying MPNNs: Message Passing as Merely Efficient Matrix Multiplication [4.002604752467421]
  Graph Neural Networks (GNNs) have achieved remarkable success, their design largely relies on empirical intuition rather than theoretical understanding.<n>We present a comprehensive analysis of GNN behavior through three fundamental aspects.<n>We demonstrate that gradient-related issues, rather than just over-smoothing, can significantly impact performance in sparse graphs.<n>We also analyze how different normalization schemes affect model performance and how GNNs make predictions with uniform node features.
  arXiv  Detail & Related papers  (2025-01-31T19:48:03Z)
• Covered Forest: Fine-grained generalization analysis of graph neural networks [14.729609626353112]
  We extend recent advances in graph similarity theory to assess the influence of graph structure, aggregation, and loss functions on MPNNs' generalization abilities.<n>Our empirical study supports our theoretical insights, improving our understanding of MPNNs' generalization properties.
  arXiv  Detail & Related papers  (2024-12-10T01:45:59Z)
• Towards Bridging Generalization and Expressivity of Graph Neural Networks [11.560730203511111]
  We study the relationship between expressivity and generalization in graph neural networks (GNNs) We introduce a novel framework that connects GNN generalization to the variance in graph structures they can capture. We uncover a trade-off between intra-class concentration and inter-class separation, both of which are crucial for effective generalization.
  arXiv  Detail & Related papers  (2024-10-14T00:31:16Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  We take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain.<n>We prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• On the Topology Awareness and Generalization Performance of Graph Neural Networks [6.598758004828656]
  We introduce a comprehensive framework to characterize the topology awareness of GNNs across any topological feature. We conduct a case study using the intrinsic graph metric the shortest path distance on various benchmark datasets.
  arXiv  Detail & Related papers  (2024-03-07T13:33:30Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  We propose DEGREE to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. We also design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods.
  arXiv  Detail & Related papers  (2023-05-22T10:29:52Z)
• MentorGNN: Deriving Curriculum for Pre-Training GNNs [61.97574489259085]
  We propose an end-to-end model named MentorGNN that aims to supervise the pre-training process of GNNs across graphs. We shed new light on the problem of domain adaption on relational data (i.e., graphs) by deriving a natural and interpretable upper bound on the generalization error of the pre-trained GNNs.
  arXiv  Detail & Related papers  (2022-08-21T15:12:08Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  Graph neural networks (GNNs) rely on the message passing paradigm to propagate node features and build interactions. Recent works point out that different graph learning tasks require different ranges of interactions between nodes. We study two common graph construction methods in scientific domains, i.e., emphK-nearest neighbor (KNN) graphs and emphfully-connected (FC) graphs.
  arXiv  Detail & Related papers  (2022-05-15T11:38:14Z)
• Learning to Extrapolate Knowledge: Transductive Few-shot Out-of-Graph Link Prediction [69.1473775184952]
  We introduce a realistic problem of few-shot out-of-graph link prediction. We tackle this problem with a novel transductive meta-learning framework. We validate our model on multiple benchmark datasets for knowledge graph completion and drug-drug interaction prediction.
  arXiv  Detail & Related papers  (2020-06-11T17:42:46Z)
• Node Masking: Making Graph Neural Networks Generalize and Scale Better [71.51292866945471]
  Graph Neural Networks (GNNs) have received a lot of interest in the recent times. In this paper, we utilize some theoretical tools to better visualize the operations performed by state of the art spatial GNNs. We introduce a simple concept, Node Masking, that allows them to generalize and scale better.
  arXiv  Detail & Related papers  (2020-01-17T06:26:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.