A Unified Hierarchy for Graph Neural Network Expressivity

This direction is merged into another direction: 1-WL expressivity limit. Its last version stays readable and citable here.

Version 1 of 128 papers29 conceptsfrozen 2026-10-04

Graph Neural Networks (GNNs) have long suffered from a "theoretical fragmentation" problem. While new architectures—ranging from subgraph-based models to higher-order simplicial complexes—proliferate rapidly, our understanding of their power has historically been a collection of isolated proofs. Recent research has moved toward a "Rosetta Stone" for GNNs: a unified mathematical framework that maps disparate architectures onto a single hierarchy of expressive power.

The Glass Ceiling of Message Passing

The standard benchmark for GNN expressivity is the Weisfeiler-Leman (WL) test, a classical algorithm for graph isomorphism. Most standard GNNs are limited by the 1-WL test, meaning they cannot distinguish certain non-isomorphic graphs, such as those containing different numbers of triangles but the same node degrees.

To break this "glass ceiling," researchers have introduced various extensions, but comparing them was difficult until the development of unified languages. Floris Geerts and Juan L Reutter in Expressiveness and Approximation Properties of Graph Neural Networks proposed a Tensor Language (TL). By translating GNN operations into tensor equations, they showed that a model's power is strictly determined by two factors: the number of variables and the nesting depth of its equations. This allows researchers to "calculate" the WL-rank of an architecture without needing a custom isomorphism proof.

Subgraph GNNs and the Search for the Sweet Spot

One of the most successful ways to surpass 1-WL is through Subgraph GNNs, which decompose a graph into smaller components and process them in parallel. However, this field was initially a "Wild West" of different selection policies and aggregation schemes.

Bohang Zhang, Guhao Feng, and their colleagues brought order to this landscape in A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests. They proved that all node-based subgraph GNNs fall into exactly six classes of power. Within this hierarchy, they identified SSWL (Symmetrized Subgraph WL) as a theoretical "sweet spot"—it provides maximal expressive power for node-based subgraphs while maintaining manageable computational complexity.

Similarly, Cai Zhou and Muhan Zhang introduced the $k,l$-WL framework in From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks. This framework unifies two previously separate ideas—Relational Pooling and Subgraph GNNs—by showing they both rely on labeling subsets of nodes to "break" the symmetries that limit standard message passing.

Homomorphism Counting as a Meta-Algorithm

If the WL test is the yardstick, homomorphism counting is the mechanism that explains why the yardstick works. Muhan Zhang and Junru Zhou developed the Generalized Folklore Weisfeiler-Leman (GFWL) framework in Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective.

The intuition is elegant: the expressive power of a GNN is exactly equivalent to its ability to count specific structural patterns (homomorphisms). Their "meta-algorithm" can automatically determine which patterns a given GNN can "see." This shifts the focus from abstract isomorphism tests to concrete structural features, like whether a model can count cycles or cliques.

Bridging Expressivity, Logic, and Generalization

A truly unified theory must explain more than just "distinguishing graphs"; it must explain how GNNs approximate functions and generalize to new data.

Summary of the Unified View

The research direction represented by these papers moves GNN theory from a collection of "existence proofs" to a systematic taxonomy. Whether through Tensor Languages, Subgraph Hierarchies, or Homomorphism Counting, the field is converging on a single conclusion: the power of a graph model is not a mystery, but a direct consequence of how it breaks symmetry and which logical patterns it is equipped to count.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_a_unified_hierarchy_for_graph_neural_net_b83eff2e,
  title = {A Unified Hierarchy for Graph Neural Network Expressivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/a-unified-hierarchy-for-graph-neural-network-expressivity/rdr_b83eff2e23b94b2aa9a4f1935018fbe7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_a_unified_hierarchy_for_graph_neural_net_b83eff2e_v1,
  title = {A Unified Hierarchy for Graph Neural Network Expressivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/a-unified-hierarchy-for-graph-neural-network-expressivity/rdr_b83eff2e23b94b2aa9a4f1935018fbe7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}