Expressivity and Generalization in Graph Neural Networks

This direction is split into other directions: expressivity-generalization tradeoff. Its last version stays readable and citable here.

Version 1 of 191 papers125 conceptsfrozen 2026-10-04

In the study of Graph Neural Networks (GNNs), the primary yardstick for "power" has long been the Weisfeiler-Leman (WL) test. This combinatorial algorithm determines whether two graphs are isomorphic; if a GNN can distinguish between two different graphs, it is considered expressive. For years, the research community operated under a simple mantra: more expressivity is better.

However, a growing body of work suggests that this relationship is far more complex. While high expressivity allows a model to capture intricate structural nuances, it also introduces a "flexibility trap" where the model may overfit to structural noise. Reconciling the gap between a model's theoretical capacity to distinguish graphs and its empirical ability to predict labels on unseen data has become a central challenge in the field.

The Classical Trade-off: VC Dimension and Overfitting

From the perspective of classical statistical learning theory, the tension between expressivity and generalization is expected. Christopher Morris, Floris Geerts, and their colleagues established a formal link in WL meet VC, proving that a GNN’s learning capacity is fundamentally tied to its structural complexity.

The intuition is straightforward: as a GNN becomes better at distinguishing non-isomorphic graphs, its Vapnik-Chervonenkis (VC) dimension—a measure of the complexity of the functions it can learn—increases. A higher VC dimension means the model can "shatter" more configurations of data, but it also means it requires significantly more training data to avoid overfitting. Martin Carrasco and others furthered this in Rademacher Meets Colors: More Expressivity, but at What Cost ?, showing that the very mechanisms that allow GNNs to partition data into distinct structural classes (like graph coloring) inherently weaken their generalization guarantees.

The Generalization Paradox

Despite these theoretical warnings, practitioners often find that more expressive models—such as those using subgraph counts or higher-order message passing—actually perform better on real-world benchmarks. This creates what Christopher Morris and Fabrizio Frasca describe as a "generalization paradox" in Position: Future Directions in the Theory of Graph Machine Learning.

Why does classical theory fail here? One explanation, proposed by Billy Joe Franks in Weisfeiler-Leman at the margin: When more expressivity matters, is rooted in margin theory. While more expressive models have the capacity to overfit, they also increase the geometric distance (the margin) between different classes of graphs in the feature space. By making the "gap" between a molecule that is toxic and one that is safe wider, the model becomes more robust to small perturbations in the graph structure, leading to better empirical generalization.

The Alignment Principle

The emerging consensus is that expressivity is not a scalar value to be maximized, but a resource that must be aligned with the task. In Graph Representational Learning: When Does More Expressivity Hurt Generalization?, Sohir Maskey and Raffaele Paolino argue that peak performance occurs only when a model’s expressivity matches the structural features that actually define the target labels.

If a task only requires knowing the degree of nodes, using a model that can count complex 4-cliques is counterproductive. The extra capacity allows the model to distinguish graphs based on irrelevant topological differences—essentially "structural noise." This is particularly evident in low-data regimes. For instance, Haitong Luo notes in Generalize across Homophily and Heterophily: Hybrid Spectral Graph Pre-Training and Prompt Tuning that increasing the number of filters or virtual nodes in a model can lead to memorization rather than learning, especially when labels are scarce.

Beyond Binary Expressivity

The research direction is now shifting away from "binary" questions—Can this GNN distinguish Graph A from Graph B?—toward a more holistic "balanced theory." As argued by Nadav Dym and Ron Levie in Future Directions in Foundations of Graph Machine Learning, the community needs frameworks that integrate:

  1. Structural Resolution: The ability to see fine-grained patterns (WL-type expressivity).
  2. Inductive Bias: The "safety net" provided by hard-coded graph priors, which prevents the model from exploring irrelevant parts of the hypothesis space.
  3. Optimization: The ease with which a model can actually find the "correct" expressive features during training.

Models like SpeqNets by Christopher Morris exemplify this balance, offering a hierarchy of expressive power that can be tuned based on the sparsity and requirements of the data, rather than simply aiming for maximum theoretical capacity. By treating expressivity as a tunable parameter rather than an inherent virtue, researchers are beginning to build GNNs that are not just "smarter" at seeing graphs, but better at understanding them.

Papers in this version

Showing 60 of 91 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_expressivity_and_generalization_in_graph_40b70874,
  title = {Expressivity and Generalization in Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressivity-and-generalization-in-graph-neural-networks/rdr_40b70874a65f4f0a9d7ff4a3d68b9b9f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_expressivity_and_generalization_in_graph_40b70874_v1,
  title = {Expressivity and Generalization in Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/expressivity-and-generalization-in-graph-neural-networks/rdr_40b70874a65f4f0a9d7ff4a3d68b9b9f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}