The expressive power of kth-order invariant graph networks

Floris GeertsarXiv 2020 · arXiv

Abstract

This paper provides a definitive answer to a central question in graph neural network (GNN) theory: how the expressive power of $k$th-order invariant graph networks ($k$-IGNs) compares to the Weisfeiler-Leman ($k$-WL) hierarchy. While it was previously established that $k$-IGNs could simulate $k$-WL, this work proves the corresponding upper bound. The author demonstrates that $k$-IGNs are exactly as powerful as the $k$-WL test at distinguishing non-isomorphic graphs, effectively situating $k$-IGNs precisely within the established logical and combinatorial hierarchy of graph isomorphism tests.

Introduction

In the field of Graph Neural Networks, "expressive power" refers to a model's fundamental ability to distinguish between different graph structures. The standard benchmark for this capability is the Weisfeiler-Leman (WL) hierarchy, a sequence of increasingly sophisticated algorithms used to address the graph isomorphism problem.

Standard message-passing neural networks (MPNNs) are known to be limited by the 1-WL test (or equivalently, 2-WL). To surpass this limitation, researchers have developed higher-order models such as $k$-IGNs, which operate on $k$th-order tensors. While prior research by Maron et al. (2019) proved that $k$-IGNs are at least as powerful as $k$-WL, a significant question remained: because $k$-IGNs consider interactions between all $k$-tuples of vertices simultaneously—whereas $k$-WL only considers "neighboring" tuples that differ by a single vertex—could $k$-IGNs actually be more powerful than $k$-WL? This paper settles the debate for all $k \geq 2$, proving that $k$-IGNs are strictly bounded by the $k$-WL test.

Theoretical Framework

The paper employs a purely theoretical approach to establish the upper bound of $k$-IGN expressivity, utilizing two primary mathematical tools:

  1. Counting Logics ($C_k$): There is a known equivalence between the $k$-WL test and a fragment of first-order logic known as $C_k$ (logic with $k$ variables and counting quantifiers). If two graphs satisfy the same sentences in $C_k$, they are indistinguishable by $k$-WL. The author uses this logical framework to bridge the gap between high-order tensor operations and discrete graph properties.
  2. Equality Patterns: The proof centers on the analysis of "equivariant linear layers." These layers are constrained by symmetry; they must treat $k$-tuples of vertices identically if those tuples share the same "equality pattern" (the internal pattern of vertex overlaps).

The core of the proof involves showing that a single layer of a $k$-IGN can be simulated by $k-1$ iterations of the $k$-WL algorithm. By induction, any function computed by a $k$-IGN can be captured by the colorings produced by a sufficiently deep $k$-WL test.

Key Insights and Results

The $k-1$ Speedup

The most striking insight of this work is the relative "efficiency" of $k$-IGNs compared to $k$-WL. The author demonstrates that one equivariant layer in a $k$-IGN corresponds to $k-1$ rounds of $k$-WL. This implies that while $k$-IGNs are not more powerful in the limit, they can potentially distinguish certain graphs using fewer layers than the number of iterations $k$-WL would require.

Global vs. Local Propagation

The reason for this speedup lies in the nature of information flow. $k$-WL is "local" in the space of tuples, updating a $k$-tuple by swapping out one vertex at a time. In contrast, $k$-IGN layers are "global," allowing information to flow between any two $k$-tuples simultaneously, provided the symmetry constraints (equality patterns) are respected.

Symmetry as a Fundamental Constraint

The proof highlights that the very property that makes GNNs useful—equivariance (the requirement that permuting input nodes permutes output features)—is exactly what limits their power. This requirement forces the network to ignore the specific identities of nodes, tying its capabilities to the same combinatorial limits as the WL test.

Main Result: Theorem 2

The paper's primary contribution is summarized in Theorem 2: For any two graphs $G$ and $H$, if they cannot be distinguished by the $k$-WL test, then they cannot be distinguished by any $k$-order invariant graph network ($k$-IGN). This establishes a complete equivalence between the two methods and generalizes previous results that were limited to $k=2$ and undirected graphs.

Conclusion and Future Directions

While $k$-IGNs are theoretically expressive, they remain computationally expensive, requiring $O(n^k)$ space and time. The author notes that other architectures, such as $k$-PPGNs (Provably Powerful Graph Networks), can simulate $(k+1)$-WL using only $k$th-order tensors by employing matrix multiplication, suggesting that $k$-IGNs may not be the most efficient architecture regarding the trade-off between tensor order and WL-power.

Future research may focus on using "equality patterns" to develop more efficient, "sparse" versions of these networks. Such models could potentially maintain the same expressive power while ignoring the computationally heavy and redundant patterns inherent in dense $k$th-order tensors.

Summary updated

Abstract

The expressive power of graph neural network formalisms is commonly measured by their ability to distinguish graphs. For many formalisms, the k-dimensional Weisfeiler-Leman (k-WL) graph isomorphism test is used as a yardstick. In this paper we consider the expressive power of kth-order invariant (linear) graph networks (k-IGNs). It is known that k-IGNs are expressive enough to simulate k-WL. This means that for any two graphs that can be distinguished by k-WL, one can find a k-IGN which also distinguishes those graphs. The question remains whether k-IGNs can distinguish more graphs than k-WL. This was recently shown to be false for k=2. Here, we generalise this result to arbitrary k. In other words, we show that k-IGNs are bounded in expressive power by k-WL. This implies that k-IGNs and k-WL are equally powerful in distinguishing graphs.
BibTeX
@misc{geerts2020expressive,
  author = {Floris Geerts},
  title = {{The expressive power of kth-order invariant graph networks}},
  year = {2020},
  eprint = {2007.12035},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2007.12035},
}
Figure