For years, the theoretical benchmark for designing Graph Neural Networks (GNNs) has been a simple, binary question: Can this network tell two different graphs apart?
This focus stems from a foundational insight by Keyulu Xu et al. in their paper, How Powerful are Graph Neural Networks?. They proved that standard message-passing neural networks (MPNNs) are at most as powerful as the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test at distinguishing non-isomorphic graph structures. If two distinct graphs look identical to the 1-WL test, a standard GNN will output the exact same representation for both, making it mathematically impossible for the network to learn different target values for them.
This realization triggered an architectural arms race. Researchers rushed to build highly expressive GNNs that break the 1-WL barrier by incorporating higher-order tuples, hierarchical substructures, or node-marking heuristics. However, a growing body of literature reveals a critical catch: maximizing a model's theoretical capacity to distinguish graphs often degrades its ability to generalize to unseen data.
To understand why this gap exists, we must look at how structural expressivity changes what a network actually learns.
The Memorization Trap
In standard machine learning, a model overfits when it has too many parameters and begins memorizing individual training examples instead of learning underlying trends. In graph machine learning, a parallel phenomenon occurs: structural overfitting.
When we engineer a GNN to be highly expressive, we give it the power to resolve subtle topological differences. For example, George Dasoulas et al. introduced Coloring Graph Neural Networks for Node Disambiguation, which uses random node coloring to break structural symmetries and turn GNNs into universal function approximators. Similarly, Billy Joe Franks et al. proposed injecting universal random features via individualization-refinement techniques in A Systematic Approach to Universal Random Features in Graph Neural Networks.
While these techniques successfully grant the network the mathematical capacity to distinguish virtually any pair of graphs, they alter the optimization landscape. When a model can uniquely identify every node or subgraph configuration, it often shifts from learning smooth, invariant structural motifs (like "contains a benzene ring") to memorizing the exact, rigid topologies of the training set. As Billy Joe Franks et al. point out, this makes it incredibly difficult for the model to identify meaningful structural patterns when the dataset size is insufficient to constrain the learning process.
This tension is made explicit by Moshe Eliasof et al. in Graph Positional Encoding via Random Feature Propagation. They note a fundamental trade-off: assigning unique random identifiers to nodes makes the model perfectly expressive in theory, but because those random features carry no semantic meaning, they fail to generalize to unseen real-world graphs.
Feature Distributions vs. Exact Counts
To build intuition for why lower expressivity can be a feature rather than a bug, consider how a GNN aggregates information from a node's neighborhood.
Imagine a task where you want to classify a molecule's solubility based on the ratio of carbon to oxygen atoms in its local neighborhoods. As Keyulu Xu et al. observed, an expressive aggregator like a sum-pooling operation is highly sensitive to exact node counts; it will compute completely different representations for a neighborhood with 2 carbons and 1 oxygen versus one with 20 carbons and 10 oxygens. Conversely, a less expressive aggregator like mean-pooling focuses purely on the relative distribution of features, mapping both neighborhoods to the same proportion.
If the underlying target function depends on proportions rather than scale, the less expressive mean-pooling architecture possesses a superior inductive bias for the task. It naturally filters out the "noise" of graph size, allowing it to generalize better to larger or smaller graphs than those seen during training. This phenomenon is not unique to deep networks; in A survey on graph kernels, Nils Morten Kriege et al. noted that simpler graph kernels frequently achieve better generalization on unseen data precisely because they avoid the overfitting associated with highly expressive structural representations.
The Fragility of Expressive Heuristics
When a model is forced to be highly expressive, it often satisfies that requirement by latching onto fragile structural heuristics rather than a robust understanding of graph topology.
Francesco Campi exposed this vulnerability in Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness. By applying adversarial attacks to models trained on subgraph counting, the author demonstrated that even state-of-the-art, highly expressive GNNs are remarkably fragile. When faced with tiny structural perturbations—such as deleting or adding a single edge—their performance collapses.
This reveals that a model's mathematical capacity to distinguish complex patterns does not mean it has learned a continuous, robust representation of those patterns. Instead, highly expressive models often create highly discontinuous decision boundaries, making them acutely sensitive to noise and out-of-distribution samples.
The Binary Blindspot of Graph Theory
Why did our theoretical frameworks fail to predict this trade-off? The issue lies in the binary nature of the graph isomorphism framework itself.
As the authors of Covered Forest: Fine-grained generalization analysis of graph neural networks argue, traditional generalization bounds based on the 1-WL test treat graphs as either completely identical or completely different. This coarse, binary view leads to "vacuous" generalization bounds—mathematical guarantees that are too loose to offer any practical insight into how a model will perform when a graph is slightly modified.
Isomorphism Perspective (Binary):
Graph A and Graph B ───► [ 1-WL Test ] ───► Equal OR Not Equal
Generalization Perspective (Continuous):
Graph A and Graph B ───► [ Structural Distance ] ───► Smoothly Bound Error
To bridge this gap, the community is shifting toward a more holistic view of graph machine learning. In Position: Future Directions in the Theory of Graph Machine Learning, Christopher Morris et al. argue that graph learning theory must move past the narrow question of structural distinguishability. Instead, future progress requires analyzing how architectural inductive biases interact with optimization and generalization.
For instance, Chenxiao Yang et al. demonstrated in Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs that the primary driver of GNN success is often not their raw representational capacity, but rather the inherent regularizing effect of the message-passing architecture itself.
Ultimately, an optimal graph neural network does not need to see every microscopic difference between two structures. It needs an architecture that balances the power to distinguish meaningful patterns with the smoothness required to ignore structural noise—proving that in graph representation learning, less expressivity can sometimes yield far more utility.
Key Foundational Work
How Powerful are Graph Neural Networks? (2019) — contributed 2 concept elements to this direction.
Provably Powerful Graph Networks (2019) — contributed 1 concept elements to this direction.
Coloring Graph Neural Networks for Node Disambiguation (2020) — contributed 1 concept elements to this direction.