Graph Representational Learning: When Does More Expressivity Hurt Generalization?

Sohir Maskey, Raffaele Paolino, Fabian Jogl, Gitta Kutyniok, Johannes F. Lutzeyer · 2025

Read Graph Representational Learning: When Does More Expressivity Hurt Generalization? by Sohir Maskey, Raffaele Paolino, Fabian Jogl, Gitta Kutyniok, Johannes F. Lutzeyer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11298.txt.

Description

Sohir Maskey, Raffaele Paolino, Fabian Jogl, Gitta Kutyniok, and Johannes Lutzeyer ask when sharper graph models learn worse, in work from twenty twenty-five. Graph neural networks learn from data with links, like webs or molecules. A sharper model can tell more graph shapes apart. That skill sounds helpful, but it may hurt on new data. The link between sharpness and real skill has stayed unclear.

The team defines a family of distance scores that grade how alike two graphs are. Labels are assumed to track shape traits of the graphs. With that setup, they derive error bounds for new data. The bounds hinge on train-test distance, model size, and training set size. Sharper models can do worse unless training data grows or test graphs sit closer. Lab tests back the bounds, giving builders a clear trade-off to weigh.

Catalog record

CREATORSohir Maskey, Raffaele Paolino, Fabian Jogl, Gitta Kutyniok, Johannes F. Lutzeyer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-11298

Browse the full library · About the Tower of Babel