Fine-grained Expressivity in Graph Neural Networks

This direction is split into other directions: binary graph isomorphism testing. Its last version stays readable and citable here.

Version 1 of 128 papers43 conceptsfrozen 2026-10-04

For years, the theoretical foundation of Graph Neural Networks (GNNs) has been built on a binary question: Can this model distinguish Graph A from Graph B? This perspective is rooted in the Weisfeiler-Leman (WL) test, a combinatorial algorithm that determines if two graphs are isomorphic. As Christopher Morris and Haggai Maron have detailed, the WL test serves as the upper bound for the expressive power of standard message-passing GNNs.

However, this "all-or-nothing" approach has a significant flaw. In the real world, graphs are rarely identical, but they are often similar. A binary test cannot tell you if two molecules are nearly identical or fundamentally different; it only tells you they are not the same. Recent research is shifting the field toward fine-grained expressivity, moving away from discrete isomorphism tests and toward continuous geometric metrics.

The Limitation of the Binary Mindset

The traditional WL test works by iteratively refining node "colors" (labels) based on their neighbors. If two graphs end up with different sets of colors, they are non-isomorphic. While powerful, this mechanism is "brittle." A single edge perturbation can "shatter" the color refinement process, making two very similar graphs appear as different as two completely unrelated ones.

Arjun Subramonian and Yizhou Sun argue that this lack of isometry—where structural similarity in the input does not translate to proximity in the output space—is why GNN theory often fails to explain real-world performance. If a model treats a tiny structural change as a total transformation, it cannot generalize to unseen data. This leads to what Antonis Vasileiou and Floris Geerts call "vacuous" generalization bounds: mathematical guarantees that are so loose they offer no practical insight into why a GNN works.

From Hashing to Metrics

To solve this, researchers are replacing the discrete hashing of the WL test with continuous distance measures. The goal is to create a geometric expressivity framework where the distance between two graph embeddings reflects the actual structural distance between the graphs.

Several mechanisms have emerged to achieve this:

  • WL Distance and Optimal Transport: Instead of rigid labels, Samantha Chen and Yusu Wang propose treating neighbor aggregation as a distribution. By using the Wasserstein distance to compare these distributions, they transform the discrete WL test into a continuous metric. This allows the model to quantify how much two neighborhoods differ, rather than just noting that they are not identical.
  • Gradual Refinement: Franka Bause and Nils Morten Kriege introduced Gradual Weisfeiler-Leman (GWL). Instead of using injective hashes that immediately separate different structures, GWL uses neighborhood clustering. This creates a hierarchy of similarity, allowing the model to learn that certain structures are "closer" to each other than others.
  • Graphons and Continuous Limits: To understand what happens as graphs become large and dense, Jan Böker and Ron Levie leverage graphons—continuous limit objects of graphs. By proving that GNNs can approximate functions on graphons, they establish a universal approximation theorem that accounts for small perturbations, providing a theoretical basis for why GNNs are robust to noise.

Why Fine-grained Expressivity Works

The intuition behind this shift is stability. In a standard GNN, the mapping from graph space to embedding space is often discontinuous. Fine-grained expressivity seeks to make this mapping Lipschitz continuous.

When we use metrics like the Forest distance Antonis Vasileiou or the Gromov-Wasserstein distance Samantha Chen, we define a "geometry" for the space of all possible graphs. If a GNN is expressive in a fine-grained sense, it means that if you take a graph and move it slightly in this geometric space (e.g., by adding one edge), its representation in the neural network will also move only slightly.

This stability is the key to generalization. As Martin Carrasco and colleagues demonstrate, there is an inherent trade-off: as you make a model more expressive (better at distinguishing graphs), you risk overfitting. However, by anchoring expressivity in continuous structural metrics rather than binary partitions, we can build models that are powerful enough to distinguish complex patterns but stable enough to recognize that a noisy version of a graph is still "the same" for the task at hand.

The Path Forward

The community is moving toward a "balanced theory" Christopher Morris. This new framework doesn't just ask if a GNN is as powerful as the WL test. Instead, it asks how well the model's latent space preserves the underlying structural geometry of the data. By treating graphs as points in a continuous metric space rather than discrete symbols, we can finally explain why GNNs generalize so well to the messy, non-isomorphic reality of real-world networks.

Papers in this version

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_fine_grained_expressivity_in_graph_neura_7b064774,
  title = {Fine-grained Expressivity in Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fine-grained-expressivity-in-graph-neural-networks/rdr_7b064774b5d146159cec3d62b22101a4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_fine_grained_expressivity_in_graph_neura_7b064774_v1,
  title = {Fine-grained Expressivity in Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fine-grained-expressivity-in-graph-neural-networks/rdr_7b064774b5d146159cec3d62b22101a4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}