Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspective

• URL: http://arxiv.org/abs/2605.13597v1
• Date: Wed, 13 May 2026 14:32:46 GMT
• Title: Rethinking Generalization in Graph Neural Networks: A Structural Complexity Perspective
• Abstract summary: Graph neural networks (GNNs) have emerged as a fundamental tool for learning from graph-structured data.<n>We ask: does the graph structure actually influence generalization, and if so, by how much?<n>To answer the first question and validate our intuition, we theoretically prove that incorporating more edges into the prediction process transforms the input representations to be overly accommodating to the output model, thereby inducing overfitting.<n>To address the second question, we formulate a structural complexity measure based on the number of effective edges and derive a Rademacher complexity-based generalization bound.
• Score: 41.727617218821386
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) have emerged as a fundamental tool for learning from graph-structured data, achieving strong performance across a wide range of applications. However, understanding their generalization capabilities remains challenging due to the complex structural dependencies inherent in such data. Existing generalization analyses largely follow the classical machine learning paradigm, focusing primarily on model complexity while overlooking the fundamental role of graph structure. Therefore, in this work, we systematically investigate this role by asking: does the graph structure actually influence generalization, and if so, by how much? To answer the first question and validate our intuition, we theoretically prove that incorporating more edges into the prediction process transforms the input representations to be overly accommodating to the output model, thereby inducing overfitting. To address the second question, we formulate a structural complexity measure based on the number of effective edges and derive a Rademacher complexity-based generalization bound. In doing so, we demonstrate that GNN generalization depends explicitly on structural complexity, alongside traditional parameter-dependent factors. Motivated by these theoretical findings, we propose a structural entropy regularization method. This approach controls structural complexity by regulating effective edges to balance underfitting and overfitting, ultimately improving the generalization performance of GNNs.

Related papers

• Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks [21.139538521229273]
  We propose a topology-aware PAC-Bayesian norm-based generalization framework for graph convolutional networks (GCNs)<n>By imposing different structures on sensitivity matrices from both spatial and spectral perspectives, we derive a family of generalization error bounds with graph structures embedded.<n> Notably, the proposed framework explicitly integrates graph structural properties into the generalization analysis, enabling a unified inspection of GNN generalization behavior.
  arXiv  Detail & Related papers  (2026-04-12T09:52:27Z)
• GADPN: Graph Adaptive Denoising and Perturbation Networks via Singular Value Decomposition [6.24191713518868]
  GADPN is a graph structure learning framework that adaptively refines graph topology via low-rank denoising and generalized structural perturbation.<n>It achieves state-of-the-art performance while significantly improving efficiency.<n>It shows particularly strong gains on challenging disassortative graphs, validating its ability to robustly learn enhanced graph structures.
  arXiv  Detail & Related papers  (2026-01-13T05:25:32Z)
• Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds [63.47271262149291]
  We propose a unified framework for PAC-Bayesian norm-based generalization.<n>The key to our approach is a sensitivity matrix that quantifies the network outputs with respect to structured weight perturbations.<n>We derive a family of generalization bounds that recover several existing PAC-Bayesian results as special cases.
  arXiv  Detail & Related papers  (2026-01-13T00:42:22Z)
• 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)
• 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)
• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms [15.473123662393169]
  Deep neural networks (DNNs) show remarkable generalization properties.<n>The source of these capabilities remains elusive, defying the established statistical learning theory.<n>Recent studies have revealed that properties of training trajectories can be indicative of generalization.
  arXiv  Detail & Related papers  (2024-07-11T17:56:03Z)
• On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games [55.2480439325792]
  In a sequential decision-making problem, the information structure is the description of how events in the system occurring at different points in time affect each other. By contrast, real-world sequential decision-making problems typically involve a complex and time-varying interdependence of system variables. We formalize a novel reinforcement learning model which explicitly represents the information structure.
  arXiv  Detail & Related papers  (2024-03-01T21:28:19Z)
• On the Expressiveness and Generalization of Hypergraph Neural Networks [77.65788763444877]
  This extended abstract describes a framework for analyzing the expressiveness, learning, and (structural) generalization of hypergraph neural networks (HyperGNNs) Specifically, we focus on how HyperGNNs can learn from finite datasets and generalize structurally to graph reasoning problems of arbitrary input sizes.
  arXiv  Detail & Related papers  (2023-03-09T18:42:18Z)
• Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equation [6.296104145657063]
  Existing neural operators (NOs) do not necessarily perform well for all physics problems. We propose a subfamily of NOs enabling an enhanced empirical approximation of the nonlinear operator mapping wave speed to solution. Our experiments reveal certain surprises in the generalization and the relevance of introducing depth. We conclude by proposing a hypernetwork version of the subfamily of NOs as a surrogate model for the mentioned forward operator.
  arXiv  Detail & Related papers  (2023-01-27T03:02:12Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  Learning causal structure poses a search problem that typically involves evaluating structures using a score or independence test. We train a variational inference model to predict the causal structure from observational/interventional data. Our models exhibit robust generalization capabilities under substantial distribution shift.
  arXiv  Detail & Related papers  (2022-05-25T17:37:08Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)

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.