Uniform Expressivity in Graph Neural Networks

19 concepts13 papers1 proposal

When training a Graph Neural Network (GNN), a fundamental expectation is that the model will generalize across graphs of varying sizes. A network trained to identify molecular properties on small molecules should theoretically apply the same structural logic when evaluated on much larger molecular graphs.

However, a deep theoretical tension exists between how GNN expressivity is proven and how these models operate in practice. This is the gap between non-uniform expressivity and uniform expressivity.

The Uniformity Gap

To understand why GNN generalization across scales can fail, we must look at how expressivity is defined. Many foundational proofs of GNN capability operate under a non-uniform assumption. As highlighted by Nicolas Keriven in Universal Invariant and Equivariant Graph Neural Networks and by Floris Geerts et al. in Expressiveness and Approximation Properties of Graph Neural Networks, mathematical frameworks often assume a fixed number of nodes or allow the model's parameters to adapt to the specific size of the input graph.

In the real world, we require uniform expressivity: a single, fixed set of parameters must maintain its functional or logical properties across all possible graph sizes without needing adjustment (Martin Grohe in The Logic of Graph Neural Networks; Moritz Schönherr in Logical Characterizations of GNNs with Mean Aggregation). When a model lacks uniform expressivity, a frozen set of weights that perfectly solves a structural query on a small graph can completely fail when deployed on a larger one.

The Aggregator Dilemma: Why Sum and Mean Fail Across Scales

The core mechanism driving this uniform expressivity gap is neighborhood aggregation. To understand why uniform generalization is difficult, consider the two most common choices: sum-aggregation and mean-aggregation.

Sum-aggregation is often celebrated for its theoretical power because it inherently captures neighborhood size, allowing it to distinguish distinct graph structures. However, this power is tightly bound to fixed graph sizes. In Some Might Say All You Need Is Sum, Eran Rosenbluth et al. demonstrated that a single GNN using only sum-aggregation cannot approximate simple mean or max functions when forced to operate across unrestricted graph sizes. Because the output magnitude of a sum aggregator scales linearly with the number of neighbors, transferring a fixed-weight model from small training graphs to larger, denser test graphs causes feature magnitudes to grow uncontrollably. This leads to severe numerical instability and signal explosion, a phenomenon detailed by Gabriele Corso et al. in Principal Neighbourhood Aggregation for Graph Nets and by Dennis Craandijk et al. in Enforcement Heuristics for Argumentation with Deep Reinforcement Learning.

To counteract this instability, practitioners often turn to mean or attention aggregation to normalize node embeddings across varying scales (Ron Levie in A graphon-signal analysis of graph neural networks). However, mean aggregation introduces a different failure mode at scale. In Almost Surely Asymptotically Constant Graph Neural Networks, Sam Adam-Day et al. proved that as graphs grow larger, the outputs of GNNs using weighted mean or attention aggregation asymptotically converge to a single constant value. While sum-based aggregators diverge and explode, mean-based aggregators collapse into structural blindness, losing the ability to express non-constant functions over large graph spaces.

How Activations and Message Types Constrain Uniform Power

The boundaries of uniform expressivity are further constrained by the internal components of the architecture, specifically message types and activation functions.

For example, the directionality of message passing matters. In Are Targeted Messages More Effective?, Martin Grohe et al. showed that making messages depend on both the sender and receiver (2-sided messaging) provides strictly greater expressive power than 1-sided messaging in a uniform setting—but this advantage is unlocked only when paired with sum aggregation.

Activation functions also dictate whether a network can maintain its logical properties across scales. Standard ReLU-based GNNs can express complex logical queries uniformly regardless of graph size. However, as proven by Sammy Khalife et al. in Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks and Is uniform expressivity too restrictive? Towards efficient expressivity of GNNs, GNNs utilizing common smooth activations like sigmoid or tanh completely lose this uniform capability.

To resolve this, the authors offer a practical compromise: these smooth "Pfaffian" GNNs can still compute the desired logic if we relax the strict uniform constraint slightly, allowing the model size to scale logarithmically with the graph's maximum degree. This stands in contrast to networks restricted to polynomial or rational activations, which face hard logical limitations that cannot be overcome even if model size scales with input size (Sammy Khalife in Graph Neural Networks with polynomial activations have limited expressivity).

Designing for Scale-Invariant Expressivity

Understanding why uniform expressivity fails provides a clear roadmap for designing robust GNNs. To achieve true size-invariant generalization, an architecture must navigate between the explosive divergence of sum and the flattening convergence of mean.

One prominent solution is Principal Neighbourhood Aggregation (PNA), introduced by Gabriele Corso et al. in Principal Neighbourhood Aggregation for Graph Nets. Instead of relying on a single aggregator, PNA combines multiple aggregators (sum, mean, max, and variance) and scales them dynamically based on the local node degree. This multi-aggregator approach allows the network to preserve the structural discrimination of sum-aggregation while utilizing mean and variance to stabilize the signal across varying graph densities. By moving beyond fixed-domain assumptions, modern graph representation learning aims to build architectures whose expressive power remains stable and uniform from the smallest molecule to the largest social network.

Key Foundational Work

Universal Invariant and Equivariant Graph Neural Networks (2019) — contributed 1 concept elements to this direction.
Principal Neighbourhood Aggregation for Graph Nets (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_uniform_expressivity_6e0cff22,
  title = {uniform expressivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uniform-expressivity/rdr_6e0cff22f9294f5d8974ceafc80f5b12},
  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_uniform_expressivity_6e0cff22_v1,
  title = {uniform expressivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uniform-expressivity/rdr_6e0cff22f9294f5d8974ceafc80f5b12/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake