Graph Representational Learning: When Does More Expressivity Hurt Generalization?
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916740085055488 |
|---|---|
| author | Maskey, Sohir Paolino, Raffaele Jogl, Fabian Kutyniok, Gitta Lutzeyer, Johannes F. |
| author_facet | Maskey, Sohir Paolino, Raffaele Jogl, Fabian Kutyniok, Gitta Lutzeyer, Johannes F. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11298 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph Representational Learning: When Does More Expressivity Hurt Generalization? Maskey, Sohir Paolino, Raffaele Jogl, Fabian Kutyniok, Gitta Lutzeyer, Johannes F. Machine Learning 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. |
| title | Graph Representational Learning: When Does More Expressivity Hurt Generalization? |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.11298 |