Characterizing the Functional Power of Graph Neural Networks

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

Version 1 of 113 papers15 conceptsfrozen 2026-10-04

For years, the gold standard for measuring the "intelligence" of a Graph Neural Network (GNN) has been the Weisfeiler-Lehman (WL) hierarchy. This framework asks a simple binary question: can a GNN distinguish between two different graphs? While the WL test provided a foundational theoretical grounding, it has increasingly become a "coarse" ruler for modern research.

As Pál András Papp and Roger Wattenhofer argue in A Theoretical Comparison of Graph Neural Network Extensions, the gap between 1-WL (basic message passing) and 3-WL is a vast "landscape of power" where most practical GNNs reside. The WL hierarchy tells us if a model is powerful, but it doesn't tell us what that power is for. A new wave of research is shifting the focus from graph isomorphism to functional expressivity: understanding exactly which mathematical functions, logical queries, and structural patterns a GNN can compute.

From Distinguishing Graphs to Computing Functions

The traditional focus on isomorphism testing is essentially a study of failure cases—identifying which graphs a model cannot tell apart. Researchers like Mohammad Fereydounian and Amin Karbasi suggest a more constructive approach. In What Functions Can Graph Neural Networks Generate?, they introduce the concept of permutation compatibility.

Instead of asking if a GNN can distinguish Graph A from Graph B, they ask: what is the exact class of functions a GNN can represent? They prove that GNNs are precisely the class of functions that satisfy this algebraic condition. This shift allows us to see GNNs not just as classifiers, but as algorithmic engines capable of solving problems like shortest paths or min-cuts, provided they are given the right "features" (like unique node IDs) to break the symmetries that otherwise limit them.

Equivariant Polynomials as a Design Roadmap

If we want to build a better GNN, the WL hierarchy offers little guidance on which specific features to add. Omri Puny, Haggai Maron, and Yaron Lipman address this in Equivariant Polynomials for Graph Neural Networks.

They propose measuring expressivity by a model's ability to compute equivariant polynomials—mathematical expressions that respect the symmetry of the graph. By characterizing a complete basis for these polynomials using tensor contractions, they provide a practical toolkit. If a researcher knows their task requires capturing a specific geometric or structural relationship, they can identify the "missing" polynomial features in their architecture and add them systematically, rather than relying on trial and error.

Quantitative Rulers: Homomorphisms and Logic

Another way to move beyond the binary WL test is to measure what a GNN can count. In Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness, Bohang Zhang and Di He introduce homomorphism expressivity. This framework identifies exactly which structural patterns—such as cycles, cliques, or paths—a model can detect and count. This provides a "ruler" that is far more granular than the WL hierarchy, explaining why certain models excel at molecular tasks (where cycles are key) while others fail.

Finally, this functional view connects deep learning to formal logic. Bernardo Cuenca Grau and Przemysław Andrzej Wałęga have established a "Rosetta Stone" in The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic. They show that different GNN architectures correspond to specific fragments of First-Order Logic. This means that if you can express a graph property as a logical query, you can determine exactly which GNN architecture is theoretically capable of "understanding" that property.

Why This Matters

The transition from the WL hierarchy to these functional frameworks represents the maturation of the field. By treating GNNs as functional approximators with specific algebraic and logical constraints, researchers can:

  1. Diagnose failures: Understand why a model fails on a specific dataset by identifying the structural patterns it cannot count.
  2. Design with intent: Build architectures that are provably capable of computing the specific algorithmic properties required for a task.
  3. Bridge disciplines: Use tools from algebraic geometry and mathematical logic to refine neural network design.

As Tuo Xu notes in Towards a Complete Logical Framework for GNN Expressiveness, these frameworks provide the granularity needed to distinguish between high-performing models that the old WL hierarchy would have simply labeled as "more powerful than 1-WL."

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_characterizing_the_functional_power_of_g_c758fbb9,
  title = {Characterizing the Functional Power of Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/characterizing-the-functional-power-of-graph-neural-networks/rdr_c758fbb990624a9abf03fa37ef14f7f7},
  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_characterizing_the_functional_power_of_g_c758fbb9_v1,
  title = {Characterizing the Functional Power of Graph Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/characterizing-the-functional-power-of-graph-neural-networks/rdr_c758fbb990624a9abf03fa37ef14f7f7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}