Expressiveness and Approximation Properties of Graph Neural Networks

Floris Geerts, Juan L Reutter

Introduction: The Expressiveness Problem

Graph Neural Networks (GNNs) are highly effective for learning on graph-structured data, but measuring their "expressiveness"—their mathematical ability to distinguish between different graph structures—remains a complex challenge. The gold standard for measuring this separation power is the Weisfeiler-Leman (WL) test hierarchy. Historically, proving that a new GNN architecture achieves a specific WL power required bespoke, intricate mathematical proofs that were difficult to generalize.

This paper addresses this gap by introducing a unified "toolbox" for GNN researchers. By translating GNN operations into a simple Tensor Language (TL), the authors provide an elegant framework that allows researchers to determine a model's mathematical power directly from its layer definitions, effectively mapping GNN design to the WL hierarchy without requiring deep expertise in WL intricacies.

The Tensor Language Framework

The authors propose a procedural Tensor Language (TL) that acts as a simplified mathematical syntax for describing how tensors (scalars, vectors, matrices) are combined within a GNN layer. The core of their method reveals that a GNN's expressiveness is dictated by two structural properties of its TL expression:

  1. Index Counting: The number of distinct variables (e.g., $x_1, x_2, \dots, x_k$) used in the expression. The authors prove that an expression utilizing $k+1$ indices corresponds exactly to the distinguishing power of the $k$-WL test.
  2. Summation Depth: The number of nested summations ($\sum$) in the expression. This directly corresponds to the number of "rounds" or layers required in the WL test.

Additionally, the authors introduce a "Guarded" fragment of the language. In this restricted version, summations only occur over neighboring nodes, mimicking the standard "message passing" paradigm. They prove this guarded version is exactly as powerful as Color Refinement (CR), a weaker, 1-WL variant of the test.

Key Insights and Theoretical Breakthroughs

  • Variable Connectivity over Activations: The paper reveals that the true expressive power of a GNN stems from how variables are connected within tensor expressions, rather than the specific activation functions (like ReLU or Sigmoid) or learned weights.
  • Treewidth Connections: The complexity of GNN expressions is linked to the graph-theoretic concept of treewidth. If a GNN's computation has low treewidth, it can be simplified to use fewer variables, indicating it might be less powerful than it initially appears.
  • Universality: The authors show that if a function can be separated by a specific WL level, there exists a GNN in their tensor language that can approximate that function. This provides a roadmap for designing "universal" GNNs for targeted classes of graph problems.

Major Results and Applications

As a theoretical work focused on formal proofs, the paper relies on abstract graph structures rather than empirical datasets to demonstrate separation power.

  • Theorems 4.1 & 4.2: These foundational theorems establish that the separation power of $t$ rounds of $k$-WL is mathematically identical to the power of TL expressions with $k+1$ variables and a summation depth of $t$.
  • Architecture Recovery & New Bounds: The framework effortlessly recovers known expressiveness bounds for popular models like GINs and GCNs. Furthermore, it solves lingering open problems by establishing new bounds for complex models: proving that Invariant Graph Networks (k-IGNs) are bounded by $(k-1)$-WL separation power, and CayleyNet is bounded by 2-WL.
  • Path Detection: The authors demonstrate that detecting a path of length $t$ using a "guarded" GNN strictly requires a summation depth of at least $t$.

Limitations and Future Directions

While the Tensor Language framework is a significant step forward, the authors note a few limitations:

  • Fixed Graph Size: Certain logic-to-tensor translations assume a fixed number of nodes ($n$), which may not perfectly model GNNs that must generalize across varying graph sizes.
  • Summation Bias: The theoretical links are most robust for sum-based aggregators. While mean or max aggregators can be incorporated, the core framework is heavily summation-centric.
  • Beyond WL: The WL hierarchy is the standard, but it struggles with counting certain subgraphs (like cycles). Future extensions of the tensor language could aim to capture more expressive logic that goes beyond standard WL tests.

Summary updated

Abstract

Characterizing the separation power of graph neural networks (GNNs) provides an understanding of their limitations for graph learning tasks. Results regarding separation power are, however, usually geared at specific GNNs architectures, and tools for understanding arbitrary GNN architectures are generally lacking. We provide an elegant way to easily obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests, which have become the yardstick to measure the separation power of GNNs. The crux is to view GNNs as expressions in a procedural tensor language describing the computations in the layers of the GNNs. Then, by a simple analysis of the obtained expressions, in terms of the number of indexes used and the nesting depth of summations, bounds on the separation power in terms of the WL-tests readily follow. We use tensor language to define Higher-Order Message-Passing Neural Networks (or k-MPNNs), a natural extension of MPNNs. Furthermore, the tensor language point of view allows for the derivation of universality results for classes of GNNs in a natural way. Our approach provides a toolbox with which GNN architecture designers can analyze the separation power of their GNNs, without needing to know the intricacies of the WL-tests. We also provide insights in what is needed to boost the separation power of GNNs.
BibTeX
@inproceedings{geerts2022expressiveness,
  author = {Floris Geerts and Juan L Reutter},
  title = {{Expressiveness and Approximation Properties of Graph Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=wIzUeM3TAU},
}
Figure