Introduction
Graph Neural Networks (GNNs) have emerged as the standard architecture for learning on relational data. However, understanding their fundamental limitations—specifically what graph structures they can distinguish and what functions they can approximate—has historically been a fragmented endeavor. The standard benchmark for GNN expressiveness is the Weisfeiler-Leman (WL) hierarchy, a sequence of increasingly powerful graph isomorphism tests.
Previously, determining where a new GNN architecture sat within this hierarchy required bespoke, complex proofs. This paper introduces a Tensor Language (TL) that provides a unified framework for analyzing GNNs. By translating GNN architectures into simple algebraic expressions, the authors demonstrate that a model's power is determined by its syntactic features: the number of variables used and the nesting depth of its summations.
The Tensor Language (TL) Framework
The core contribution of this work is the shift from graph-theoretic proofs to syntactic analysis. The authors propose a procedural language where GNN layers are expressed using basic operations: multiplication, addition, and summation over indices. This abstraction allows researchers to evaluate a model's theoretical limits by looking at the "code" of its layers rather than its geometric implementation.
Key Syntactic Features:
- Index Counting: The authors prove that if a GNN’s TL expression utilizes $k+1$ index variables, its ability to separate non-isomorphic graphs is strictly bounded by the $k$-WL test.
- Summation Depth: The nesting depth of summations within a TL expression corresponds directly to the number of iterations (or "rounds") of the WL test required to achieve equivalent separation power.
- Guarded Fragments: The framework defines a "guarded" version of the language where summations are restricted to immediate neighbors. This perfectly captures the behavior of standard message-passing GNNs (MPNNs) and the basic Color Refinement algorithm.
Treewidth and Structural Bottlenecks
A significant insight of the paper is the connection between tensor operations and the graph-theoretic concept of treewidth. Even if a GNN architecture appears complex or uses many indices, its true expressiveness may be lower than expected if the "connectivity" of those indices (their treewidth) is low. If a tensor operation has low treewidth, it can be optimized into an expression with fewer variables, revealing a hidden bottleneck in the model's expressive power. This provides a rigorous tool for identifying when a GNN is "over-engineered" relative to its actual capacity to distinguish graphs.
Universality and Approximation
Beyond graph separation (expressiveness), the paper addresses universality—the ability of a GNN to approximate any continuous function on graphs. Using a generalized Stone-Weierstrass theorem, the authors establish a formal link between these two concepts. They show that a class of GNNs can approximate any function, provided that the function does not require the model to distinguish between graphs that are already considered equivalent by the GNN's theoretical upper bound (e.g., graphs that $k$-WL cannot tell apart).
Implications for Modern Architectures
Because this framework is unified, the authors were able to resolve several open questions and provide formal bounds for established architectures that previously lacked them:
- Invariant Graph Networks ($k$-IGNs): The authors proved that $k$-IGNs are bounded by $(k-1)$-WL, settling an open problem regarding their placement in the hierarchy.
- CayleyNet: The paper provides the first formal proof that CayleyNet, a popular spectral GNN, is bounded by the 2-WL test.
- Standard Models: The framework successfully recovers known theoretical results for GIN, GCN, GraphSage, and PNA, placing both spatial and spectral GNNs into a single, coherent hierarchy.
Conclusion and Future Directions
This research provides a "general recipe" for evaluating GNN power. By reducing the complexity of graph theory to the counting of variables in a tensor expression, it democratizes the theoretical analysis of new architectures.
While the TL framework currently provides robust upper bounds on separation power, proving lower bounds still requires demonstrating that the specific functions used in a GNN's layers (like the choice of non-linearities) are injective enough to preserve structural information. Future work may explore how different aggregation functions (such as mean or max instead of sum) further constrain these syntactic limits, particularly in scenarios where graph sizes are not fixed.
Summary updated