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.
- Logic: Tuo Xu in Towards a Complete Logical Framework for GNN Expressiveness and Ouns El Harzli et al. in From Neural Networks to Logical Theories have established bridges between GNN architectures and formal logic. This tells us the "language" a GNN speaks—for instance, mapping Transformers to modal logic—providing a rigorous way to verify what a model can and cannot learn.
- Generalization: Levi Rauchwerger, Stefanie Jegelka, and Ron Levie connected the dots between expressivity and performance in Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs. By defining a "mover's distance" for attributed graphs, they proved that the same structural features that make a GNN expressive also ensure it is stable enough to generalize to unseen graphs.
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.