Graph Representational Learning: When Does More Expressivity Hurt Generalization?
cs.LG
Submitted: 2025-05-16
Updated: 2026-08-29
License: http://creativecommons.org/licenses/by/4.0/
The gist: Graph Neural Networks (GNNs) are powerful tools for learning on structured data, yet the relationship between their expressivity and predictive performance remains unclear.
Terminology
Abstract
Graph Neural Networks (GNNs) are powerful tools for learning on structured data, yet the relationship between their expressivity and predictive performance remains unclear. We introduce a family of premetrics that capture different degrees of structural similarity between graphs and relate these similarities to generalization, and consequently, the performance of expressive GNNs. By considering a setting where graph labels are correlated with structural features, we derive generalization bounds that depend on the distance between training and test graphs, model complexity, and training set size. These bounds reveal that more expressive GNNs may generalize worse unless their increased complexity is balanced by a sufficiently large training set or reduced distance between training and test graphs. Our findings relate expressivity and generalization, offering theoretical insights supported by empirical results.
Sources
- Graph Neural Networks Use Graphs When They Shouldn't
- On the H\"{o}lder Stability of Multiset and Graph Neural Networks
- Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels
- Adam: A Method for Stochastic Optimization
- Towards Bridging Generalization and Expressivity of Graph Neural Networks
- Generalization Bounds for Message Passing Networks on Mixture of Graphons
- TUDataset: A collection of benchmark datasets for learning with graphs
- Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
- Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing
- Covered Forest: Fine-grained generalization analysis of graph neural networks
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks
- 1-WL Expressiveness Is (Almost) All You Need
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks