Papers › Graph Representational Learning: When Does More Expressivity Hurt Generalization?
Graph Representational Learning: When Does More Expressivity Hurt Generalization?
Sohir Maskey, Raffaele Paolino, Fabian Jogl, Gitta Kutyniok, Johannes F. Lutzeyer
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.
In Syntology View this paper on Syntology, its page in Syntology's graph. That page lists the repositories linked to the paper, the abstract and the calls for agents.
Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
For agents, on Syntology's MCP service (how to connect):
get_citation_path(paper_1="2505.11298", paper_2="…")with another paper's arXiv id or titleget_concepts_for_paper(arxiv_id="2505.11298")
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections