Equivariant Polynomials for Graph Neural Networks
Graph Neural Networks (GNN) are inherently limited in their expressive power.
Recent seminal works (Xu et al., 2019; Morris et al., 2019b) introduced the
Weisfeiler-Lehman (WL) hierarchy as a measure of expressive power. Although
this hierarchy has propelled significant advances in GNN analysis and
architecture developments, it suffers from several significant limitations.
These include a complex definition that lacks direct guidance for model
improvement and a WL hierarchy that is too coarse to study current GNNs. This
paper introduces an alternative expressive power hierarchy based on the ability
of GNNs to calculate equivariant polynomials of a certain degree. As a first
step, we provide a full characterization of all equivariant graph polynomials
by introducing a concrete basis, significantly generalizing previous results.
Each basis element corresponds to a specific multi-graph, and its computation
over some graph data input corresponds to a tensor contraction problem. Second,
we propose algorithmic tools for evaluating the expressiveness of GNNs using
tensor contraction sequences, and calculate the expressive power of popular
GNNs. Finally, we enhance the expressivity of common GNN architectures by
adding polynomial features or additional operations / aggregations inspired by
our theory. These enhanced GNNs demonstrate state-of-the-art results in
experiments across multiple graph learning benchmarks.
Omri Puny, Derek Lim, Bobak T. Kiani, Haggai Maron, Yaron Lipman
# Equivariant Polynomials for Graph Neural Networks

###### Abstract

Graph Neural Networks (GNN) are inherently limited in their expressive power. Recent seminal works (Xu et al., 2019; Morris et al., 2019) introduced the Weisfeiler-Lehman (WL) hierarchy as a measure of expressive power. Although this hierarchy has propelled significant advances in GNN analysis and architecture developments, it suffers from several significant limitations. These include a complex definition that lacks direct guidance for model improvement and a WL hierarchy that is too coarse to study current GNNs. This paper introduces an alternative expressive power hierarchy based on the ability of GNNs to calculate equivariant polynomials of a certain degree. As a first step, we provide a full characterization of all equivariant graph polynomials by introducing a concrete basis, significantly generalizing previous results. Each basis element corresponds to a specific multi-graph, and its computation over some graph data input corresponds to a tensor contraction problem. Second, we propose algorithmic tools for evaluating the expressiveness of GNNs using tensor contraction sequences, and calculate the expressive power of popular GNNs. Finally, we enhance the expressivity of common GNN architectures by adding polynomial features or additional operations / aggregations inspired by our theory. These enhanced GNNs demonstrate state-of-the-art results in experiments across multiple graph learning benchmarks.

Machine Learning, Graph Neural Networks, Graph Neural Networks

## 1 Introduction

In recent years, graph neural networks (GNNs) have become one of the most popular and extensively studied classes of machine learning models for processing graph-structured data. However, one of the most significant limitations of these architectures is their limited expressive power. In recent years, the Weisfeiler-Lehman (WL) hierarchy has been used to measure the expressive power of GNNs (Morris et al., 2019; Xu et al., 2019; Morris et al., 2021). The introduction of the WL hierarchy marked an extremely significant step in the graph learning field, as researchers were able to evaluate and compare the expressive power of their architectures, and used higher-order WL tests to motivate the development of new, more powerful architectures.

The WL hierarchy, however, is not an optimal choice for either purpose. First, its definition is rather complex and not intuitive, particularly for \(k\geq 3\). One implication is that it is often difficult to analyze WL expressiveness of a particular architecture class. As a result, many models lack a theoretical understanding of their expressive power. A second implication is that WL does not provide practical guidance in the search for more expressive architecture. Lastly, as was noted in recent works (Morris et al., 2022; 2019), the WL test appears to be too coarse to be used to evaluate the expressive power of current graph models. As an example, many architectures (e.g., (Frasca et al., 2022)) are strictly more powerful than 2-WL and bounded by 3-WL, and there is no clear way to compare them.

The goal of this paper is to offer an alternative expressive power hierarchy, which we call _polynomial expressiveness_ that mitigates the limitations of the WL hierarchy. Our proposed hierarchy relies on the concept of graph polynomials, which are, for graphs with \(n\) nodes, polynomial functions \(P:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}^{n^{2}}\) that are also permutation equivariant -- that is, well defined on graph data. The polynomial expressiveness hierarchy is based on a natural and simple idea -- the ability of GNNs to compute or approximate equivariant graph polynomials up to a certain degree.

Figure 1: Example of two basis elements of equivariant graph polynomials: node-valued (top), and edge-valued (bottom). Basis elements \(P_{H}\) can be described by tensor contraction networks \(H\) (left), corresponding to a matching einsum expression.
This paper provides a number of theoretical and algorithmic contributions aimed at defining the polynomial hierarchy, providing tools to analyze the polynomial expressive power of GNNs, and demonstrating how this analysis can suggest practical improvements in existing models that give state-of-the-art performance in GNN benchmarks.

First, while some polynomial functions were used in GNNs in the past (Maron et al., 2019; Chen et al., 2019; Azizian and Lelarge, 2021), a complete characterization of the space of polynomials is lacking. In this paper, we provide the first characterization of graph polynomials with arbitrary degrees. In particular, we propose a basis for this vector space of polynomials, where each basis polynomial \(P_{H}\) of degree \(d\) corresponds to a specific multi-graph \(H\) with \(d\) edges. This characterization provides a significant generalization of known results, such as the basis of constant and linear equivariant functions on graphs (Maron et al., 2018). Furthermore, this graphical representation \(H\) can be viewed as a type of a tensor network, which provides a concrete way to compute those polynomials by performing a series of tensor (node) contractions. This is illustrated in Figure 1.

As a second contribution, we propose tools for measuring polynomial expressiveness of graph models and placing them in the hierarchy. This is accomplished by analyzing tensor networks using standard contraction operators, similar to those found in Einstein summation (einsum) algorithms. Using these, we analyze two popular graph models: Message Passing Neural Networks (MPNNs) and Provably Powerful Graph Networks (PPGNs). This is done by first studying the polynomial expressive power of prototypical versions of these algorithms, which we define.

Our third contribution demonstrates how to improve MPNN and PPGN by using the polynomial hierarchy. Specifically, we identify polynomial basis elements that are not computable by existing graph architectures and add those polynomial basis elements to the model as feature layers. Also, we add two simple operations to the PPGN architecture (matrix transpose and diagonal / off-diagonal MLPs) to achieve the power of a Prototypical edge-based graph model. After precomputing the polynomial features, we achieve strictly better than \(3\)-WL expressive power while only requiring \(O(n^{2})\) memory -- to the best of our knowledge this is the first equivariant model to achieve this. We demonstrate that these additions result in state-of-the-art performance across a wide variety of datasets.

## 2 Equivariant graph polynomials

We represent a graph with \(n\) nodes as a matrix \(\textbf{X}\in\mathbb{R}^{n^{2}}\), where edge values are stored at off-diagonal entries, \(\textbf{X}_{ij}\), \(i\neq j\), \(i,j\in[n]=\{1,2,\ldots,n\}\), and node values are stored at diagonal entries \(\textbf{X}_{ii}\), \(i\in[n]\).

An _equivariant graph polynomial_ is a matrix polynomial map \(P:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}^{n^{2}}\) that is also equivariant to node permutations. More precisely, \(P\) is a polynomial map if each of its entries, \(P(\textbf{X})_{ij}\), \(i,j\in[n]\), is a polynomial in the inputs \(\textbf{X}_{rs}\), \(r,s\in[n]\). \(P\) is equivariant if it satisfies

\[P(g\cdot\textbf{X})=g\cdot P(\textbf{X}), \tag{1}\]

for all permutations \(g\in S_{n}\), where \(S_{n}\) denotes the permutation group on \([n]\), and \(g\) acts on a matrix **Y** as usual by

\[(g\cdot\textbf{Y})_{ij}=\textbf{Y}_{g^{-1}(i),g^{-1}(j)}. \tag{2}\]

### \(P_{h}\): Basis for equivariant graph polynomials

We next provide a full characterization of equivariant graph polynomials by enumerating a particular basis, denoted \(P_{H}\). In later sections we use this basis to analyze expressive properties of graph models and improve expressiveness of existing GNNs.

The basis elements \(P_{H}\) of degree \(d\) equivariant graph polynomials are enumerated from non-isomorphic _directed multigraphs_, \(H=(V,E,(a,b))\), where \(V=[m]\) is the node set; \(E=\{(r_{1},s_{1}),\ldots,(r_{d},s_{d})\}\), \(r_{i},s_{i}\in[m]\), the edge set, where parallel edges and self-loops are allowed; and \(a,b\in V\) is a pair of not necessarily distinct nodes representing the output dimension. The pair \((a,b)\) will be marked in our graphical notation as a red edge.

Defining the basis \(P_{H}\) will be facilitated by the use of Einstein summation operator defined next. Note that the multi-graph \(H\) can be represented as the following string that encodes both its list of edges and the single red edge: \(H\cong\ {}^{\prime}r_{1}s_{1},\ldots,r_{d}s_{d}\to ab^{\prime}\). The einsum operator is:

\[\texttt{einsum}(H,\textbf{X}^{1},\ldots,\textbf{X}^{d})_{i_{a}, i_{b}}=\] \[\texttt{einsum}(r_{1}s_{1},\ldots,r_{d}s_{d}\to ab,\textbf{X}^{1}, \ldots,\textbf{X}^{d})_{i_{a},i_{b}}=\] \[\sum_{\begin{subarray}{c}j_{1},\ldots,j_{m}\in[n]\\ j_{a}=i_{a},j_{b}=i_{b}\end{subarray}}\textbf{X}^{1}_{j_{r_{1}},j_{s_{1}}} \cdots\textbf{X}^{d}_{j_{r_{d}},j_{s_{d}}}\]

Figure 2 shows how matrix multiplication can be defined using a corresponding multigraph \(H\) and Einstein summation. Such multigraphs span the basis of equivariant polynomials:

Figure 2: Example of matrix multiplication, \(\mathbf{X}\mathbf{Y}\). Computation defined by a multigraph \(H\) and Einstein summation.
**Theorem 2.1** (Graph equivariant basis).: _A basis for all equivariant graph polynomials \(P:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}^{n^{2}}\) of degree \(\leq d\) is enumerated by directed multigraphs \(H=(V,E,(a,b))\), where \(|V|\leq\min\left\{n,2+2d\right\}\), \(|E|\leq d\), and \(V\backslash\left\{a,b\right\}\) does not contain isolated nodes. The polynomial basis elements corresponding to \(H\) are_

\[P_{H}(\textbf{X})=\texttt{einsum}(H,\overbrace{\textbf{X},\ldots,\textbf{X} }^{d\texttt{times}}). \tag{3}\]

An explicit formula for \(P_{H}\) can be achieved by plugging in the definition of einsum and equation 3:

\[P_{H}(\textbf{X})_{i_{a},i_{b}}=\sum_{\begin{subarray}{c}j_{1},\ldots,j_{m} \in[n]\\ j_{a}=i_{a},j_{b}=i_{b}\end{subarray}}\prod_{(r,s)\in E}\textbf{X}_{j_{r},j_{s }}. \tag{4}\]

Figure 1 depicts an example of graph equivariant basis elements \(P_{H}\) corresponding to two particular multigraphs \(H\). Note that a repeated pair \((a,a)\) in \(H\) leads to a _node-valued_ equivariant polynomial, while a distinct pair \((a,b)\), \(a\neq b\) leads to an _edge-valued_ equivariant polynomial. Furthermore, we make the convention that if \(E\) is empty then \(\prod_{(r,s)\in E}\textbf{X}_{i_{r},i_{s}}=1\). The number of such polynomials increases exponentially with the degree of the polynomial; the first few counts of degree \(d\) equivariant graph polynomials are 2 (\(d=0\)), 15 (\(d=1\)), 117 (\(d=2\)), 877 (\(d=3\)), 6719 (\(d=4\)),...Further details and proofs of these sequences are provided in Appendix I. The full proof of Theorem 2.1 is provided in Appendix B.

Proof idea for Theorem 2.1.: Since the set of monomials form a basis of all (not necessarily invariant) polynomials \(P:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}^{n^{2}}\), we can project them onto the space of equivariant polynomials via the symmetrization (Reynolds) operator to form a basis for the equivariant polynomials. This projection operation will group the monomials into orbits that form the equivariant basis.

To find these orbits, the basic idea is to consider the monomials in the input variables \(\{\textbf{X}_{i,j}:i,j\in[n]\}\) and an additional variable \(\{\delta_{i,j}:i,j\in[n]\}\) to denote the possible output entries of the equivariant map. Any given monomial \(M(\textbf{X},\delta^{a,b})\) takes the form

\[M(\textbf{X},\delta^{a,b})_{i,j}=\delta^{a,b}_{i,j}\prod_{r,s=1}^{n}\textbf{ X}_{r,s}^{\textbf{A}_{r,s}}, \tag{5}\]

where \(\textbf{A}\in\mathbb{N}_{0}^{n^{2}}\), \(\mathbb{N}_{0}=\{0,1,\ldots\}\) is the matrix of powers, and \(\delta^{a,b}_{i,j}=1\) if \(a=i\), \(b=j\), and \(\delta^{a,b}_{i,j}=0\) otherwise. A natural way to encode these monomials is with _labeled_ multi-graphs \(H=(V,E,(a,b))\), where \(V=[n]\), \(E\) is defined by the adjacency matrix **A**, and \((a,b)\) is a special (red) edge. We therefore denote \(M=M_{H}\).

These monomials can be projected onto equivariant polynomials via the Reynolds operator that takes the form,

\[\begin{split} Q_{H}(\textbf{X})&=\sum_{g\in S_{n}}g \cdot M_{H}(g^{-1}\cdot\textbf{X},\delta^{g(a),g(b)})\\ &=\sum_{g\in S_{n}}M_{g\cdot H}(\textbf{X},\delta^{a,b}),\end{split} \tag{6}\]

where the action of \(g\in S_{n}\) on the multi-graph \(H\) is defined (rather naturally) as node relabeling of \(H\) using the permutation \(g\).

From the above, we note: (i) \(Q_{H}\) sums all monomials with multi-graphs in the orbit of \(H\), namely \([H]=\{g\cdot H|g\in S_{n}\}\). This shows that, in contrast to \(M_{H}\), \(Q_{H}\) is represented by an _unlabeled_ multi-graph \(H\) and enumerated by _non-isomorphic_ multi-graphs \(H\). (ii) Since the symmetrization is a projection operator, any equivariant polynomial is spanned by \(Q_{H}\). (iii) Since each \(Q_{H}\) is a sum of \(M_{H}\) belonging to a different orbit, and since orbits are disjoint, the set \(\{Q_{H}\}\) for non-isomorphic \(H\) is linearly independent. These three points establish that \(\{Q_{H}\}\) for non-isomorphic multi-graphs \(H\) is a basis of equivariant graph polynomials.

Noting that \(Q_{H}(\textbf{X})_{ij}\) includes only terms for which \(\delta^{g(a),g(b)}=\delta^{i,j}\), the explicit form below can be derived:

\[Q_{H}(\textbf{X})_{i_{a},i_{b}}=\sum_{\begin{subarray}{c}j_{1}\neq\ldots, \neq j_{m}\in[n]\\ j_{a}=i_{a},j_{b}=i_{b}\end{subarray}}\prod_{(r,s)\in E}\textbf{X}_{j_{r},j_{s }}. \tag{7}\]

\(Q_{H}\) is similar to \(P_{H}\) in equation 4, except we only sum over non-repeated indices. The proof in Appendix B shows that \(P_{H}\) is also a basis for such equivariant polynomials.

**Example: linear basis.** Employing Theorem 2.1 for the \(d=0,1\) case reproduces the graph equivariant constant and linear functions from Maron et al. (2018). Figure 3 depicts the graphical enumeration of the 2 constant and 15 linear basis elements.

**Simple graphs.** It is often the case that the input data **X** is restricted to some subdomain of \(\mathbb{R}^{n^{2}}\), e.g., symmetric \(0/1\) matrices with diagonal entries set to zero correspond to simple graph data. In such cases, polynomials \(P_{H}\) that correspond to different multi-graphs \(H\) can coincide, resulting in a smaller basis. For simple graph data **X**, existence of self loops in \(H\) would result in \(P_{H}(\textbf{X})=0\), parallel edges in

Figure 4: Simple \(H\) corresponding to simple graph data.

Figure 3: Basis of equivariant constant (left of bold line) and linear (right of bold line) graph polynomials.
\(H\) can be replaced with single edges without changing the value of \(P_{H}(\textbf{X})\), and since the direction of black edges in \(H\) do not change the value of \(P_{H}(\textbf{X})\) we can consider only _undirected_ multi-graphs \(H\). That is, for simple graph data it is enough to consider simple graphs \(H\) (ignoring the red edge). Figure 4 shows two examples of \(H\) for simple graph data.

**Computing \(P_{H}(\textbf{X})\) with tensor contractions.** A useful observation for the graph model analysis performed later is that computing \(P_{H}(\textbf{X})\) is equivalent to a tensor contraction guided by \(H\). Similarly to \(\mathtt{einsum}\), computing \(P_{H}(\textbf{X})\) can be done iteratively in multiple ways by finding a sequence of contraction paths for \(H\) where we start with each edge of \(H\) endowed with **X** and our end goal is to have a single black edge aligned with the red edge. Figure 5 provides an example of computing a 4th degree polynomial through a sequence of 3 tensor contractions. In gray we indicate nodes that are contracted, namely, their index is summed in the \(\mathtt{einsum}\).

### Generalizations and discussion

**Invariant graph polynomials.** This approach also gives a basis for the invariant polynomials \(P:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}\). In this case, we let \(H\) be a directed multigraph without a red edge, and define \(P_{H}(\textbf{X})=\sum_{j_{1},\ldots,j_{m}\in[n]}\prod_{r,s\in E(H)}\textbf{ X}_{j_{r},j_{s}}\). Computing \(P_{H}\) then corresponds to contracting \(H\) to the trivial graph (with no nodes or edges). Our equivariant basis is a generalization of previous work, which used invariant polynomials analogous to \(P_{H}\) or the alternative basis \(Q_{H}\) to study properties of graphs (Thiery, 2000; Lovasz, 2012).

**Subgraph counting.** The previous work on invariant polynomials mentioned above as well as our proof of Theorem 2.1 suggest \(Q_{H}\) (see equation 7) as another basis of equivariant graph polynomials. In Appendix F, we show that when applied to binary input \(\textbf{X}\in\{0,1\}^{n\times n}\), \(Q_{H}\) performs subgraph counting; essentially, \(Q_{H}(\textbf{X})_{i_{a},i_{b}}\) is proportional to the number of subgraphs of **X** isomorphic to \(H\) such that \(i_{a}\) is mapped to \(a\) and \(i_{b}\) is mapped to \(b\). This \(Q_{H}\) basis is interpretable, but does not lend itself to efficient vectorized computation or the tensor contraction perspective that the \(P_{H}\) basis has.

**Equivariant polynomials for attributed graphs.** One can extend the polynomials discussed here to cover equivariant polynomials defined over _attributed graphs_ (i.e., graphs with \(\mathbb{R}^{f}\) features attached to nodes and/or edges), \(P:\mathbb{R}^{n^{2}\times f}\rightarrow\mathbb{R}^{n^{2}}\). A similar basis to \(P_{H}\) can be used in this case as described in Appendix E.

## 3 Expressive power of graph models

In this section we evaluate the expressive power of equivariant graph models from the new, yet natural hierarchy arising from equivariant graph polynomials. By graph model, \(\mathcal{F}=\{F\}\), we mean any collection of equivariant functions \(F:\mathbb{R}^{n^{2}}\rightarrow\mathbb{R}^{n^{k}}\), where \(k=1\) corresponds to a family of node-valued functions, \(F(\textbf{X})\in\mathbb{R}^{n}\), and \(k=2\) to node and edge-valued functions, \(F(\textbf{X})\in\mathbb{R}^{n^{2}}\). For expositional simplicity we focus on graph data **X** representing simple graphs, but note that the general graph data case can be analysed using similar methods. We will use two notions of polynomial expressiveness: exact and approximate. The exact case is used for analyzing Prototypical graph models, whereas the approximate case is used for analyzing practical graph models.

**Definition 3.1**.: A graph model \(\mathcal{F}\) is \(d\) node/edge polynomial _exact_ if it can compute all the degree \(d\) polynomial basis elements \(P_{H}(\textbf{X})\) for every simple graph **X**.

**Definition 3.2**.: A graph model \(\mathcal{F}\) is \(d\) node/edge polynomial _expressive_ if for arbitrary \(\epsilon>0\) and degree \(d\) polynomial basis element \(P_{H}(\textbf{X})\) there exists an \(F\in\mathcal{F}\) such that \(\max_{\textbf{X}\text{ simple}}|F(\textbf{X})-P(\textbf{X})|<\epsilon\).

As a primary application of the equivariant graph basis \(P_{H}\), we develop tools here for analyzing the polynomial expressive power of graph models \(\mathcal{F}\). We define _Prototypical_ graph models which provide a structure to analyze or improve existing popular GNNs such as MPNN (Gilmer et al., 2017) and PPGN (Maron et al., 2019).

### Prototypical graph models

We consider graph computation models, \(\mathcal{F}_{\mathcal{B}}\), that are finite sequences of tensor contractions taken from a bank of primitive contractions \(\mathcal{B}\).

\[\mathcal{F}_{\mathcal{B}}=\left\{C_{i_{1}}C_{i_{2}}\cdots C_{i_{ \ell}}\ |C_{i_{j}}\in\mathcal{B}\right\}, \tag{8}\]

where the bank \(\mathcal{B}=\{C_{1},\ldots,C_{k}\}\) consists of multi-graphs \(C_{i}=(V_{i},E_{i},(a_{i},b_{i}))\), each representing a different primitive tensor contraction. A model \(\mathcal{F}_{\mathcal{B}}\) can compute a polynomial \(P_{H}(\textbf{X})=\mathtt{einsum}(H,\textbf{X},\ldots,\textbf{X})\) if it can contract \(H\) to the red edge by applying a finite sequence of contractions from its bank. If there exists such a sequence then \(P_{H}\) is deemed computable by \(\mathcal{F}_{\mathcal{B}}\), otherwise it is not computable by \(\mathcal{F}_{\mathcal{B}}\). For example, the model with the bank presented in Figure 7 can compute \(P_{H}\) in Figure 5; removing any element from this model, will make \(P_{H}(\textbf{X})\) non-computable. We recap:

**Definition 3.3**.: The polynomial \(P_{H}\) is _computable by \(\mathcal{F}\)_ iff there exists a sequence of tensor contractions from \(\mathcal{F}\) that computes \(P_{H}(\textbf{X})=\mathtt{einsum}(H,\textbf{X},\ldots,\textbf{X})\).

Figure 7: A bank \(\mathcal{B}\) of a model \(\mathcal{F}_{\mathcal{B}}\) that can compute the example in Figure 5.
We henceforth focus on two Prototypical models: the node-based model \(\mathcal{F}_{n}\) and edge-based model \(\mathcal{F}_{e}\). Their respective contraction banks are depicted in Figure 6, each motivated by the desire to achieve polynomial exactness (see Definition 3.1) and contract multi-graphs \(H\) where a member of the bank can always be used to contract nodes with up to \(N\) neighbors. Taking \(N=1\) results in the node-based bank in Figure 6 (left), and \(N=2\) in the edge-based bank in Figure 6 (right). These choices are not unique -- other contraction banks can satisfy these requirements.

**Lemma 3.4**.: \(\mathcal{F}_{n}\) _(for simple graphs) and \(\mathcal{F}_{e}\) (for general graphs) can always contract a node in \(H\) iff its number of neighbors is at-most \(1\) and \(2\), respectively._

A few comments are in order. Node-based contractions can only add self-edges during the contraction process (i.e., new node-valued data) thus requiring only \(O(n)\) additional memory to perform computation. Further note that since we assume simple graph data, \(H\) is also a simple graph, and no directed edges (i.e., non-symmetric intermediate tensors) are created during contraction. Contraction banks with undirected graphs suffice in this setting. We later show that the node-based model acts analogously to message-passing. The edge-based model targets exactness over both node and edge valued polynomial. It generates new edges that can be directed even if **X** is simple, and thus includes directed contractions in its bank. The edge-based model will later be connected to the graph models PPGN (Maron et al., 2019) and Ring-GNN (Chen et al., 2019). We later show that the node-based is 1-WL expressive and the edge-based model is 3-WL expressive.

**Deciding computability of \(P_{H}(\textbf{X})\) with \(\mathcal{F}_{\textbf{{B}}}\).** A key component in analyzing the expressive power of a Prototypical model is determining which polynomials \(P_{H}(\textbf{X})\) can be computed with \(\mathcal{F}\), given \(H\) and **X** encoding simple graph data. A naive algorithm traversing all possible enumerations of nodes in \(H\) and their contractions would lead to a combinatorial explosion that is too costly -- especially since this procedure needs to be repeated for a large number of polynomials. Here, we show that at least for contraction banks \(\mathcal{F}_{n}\) and \(\mathcal{F}_{e}\), Algorithm 1 is a linear time (in \(|V|,|E|\)), _greedy_ algorithm for deciding computability of a given polynomial. Algorithm 1 finds a sequence of contractions using the greedy step until no more nodes are left to contract. That is, it terminates when all nodes, aside from \(a,b\), have more than 1 or 2 neighbors for \(\mathcal{F}_{n}\) or \(\mathcal{F}_{e}\), respectively. If it terminates with just \(\{a,b\}\) as vertices it deems \(P_{H}\) computable and otherwise it deems \(P_{H}\) non-computable. To show correctness of this algorithm we prove:

**Theorem 3.5**.: _Let \(H\) be some multi-graph and \(\mathcal{F}_{\mathcal{B}}\in\{\mathcal{F}_{n},\mathcal{F}_{e}\}\). Further, let \(H^{\prime}\) be the multi-graph resulting after contracting a single node in \(H\) using one or more operations from \(\mathcal{B}\) to \(H\). Then, \(H\) is \(\mathcal{F}_{\mathcal{B}}\)-computable iff \(H^{\prime}\) is \(\mathcal{F}_{\mathcal{B}}\)-computable._

To verify the correctness of this procedure, note that the algorithm has to terminate after at most \(|V|-|\{a,b\}\mid\) node contractions. Now consider two cases: if the algorithm terminates successfully, it must have found a sequence of tensor contractions to compute \(P_{H}(\textbf{X})\). If it terminates unsuccessfully, the theorem implies its last network \(H^{\prime}\) is computable iff the input network \(H\) is computable. Now

Figure 5: Computation of \(P_{H}(\textbf{X})\) with a sequence of tensor contractions: The polynomial \(P_{H}(\textbf{X})\) (left-most) is computed when a single black edge parallel to the red edge is left (right-most); above each arrow is the tensor contraction applied (contracted nodes are in gray).

Figure 6: Prototypical node-based (left) and edge-based (right) graph models’ contraction banks. Gray nodes indicate nodes that are contracted. Explicit formula of each element can be found in Appendix D.
since there is _no_ further node contraction possible to do in \(H^{\prime}\) using operations from \(\mathcal{B}\) it is not computable by definition, making \(H\) not computable.

**Polynomial exactness.** To compute the \(d\) polynomial exactness (see Definition 3.1) for the node-based and edge-based Prototypical graph models we enumerate all non-isomorphic simple graphs \(H\) with up to \(d\) edges and one red edge and run Algorithm 1 on each \(H\). This reveals that the node-based model \(\mathcal{F}_{n}\) is 2-node-polynomial-exact, while the edge-based model \(\mathcal{F}_{e}\) is 5-node-polynomial-exact and 4-edge-polynomial-exact. See Figure 8 for the lowest degree polynomials, represented by \(H\) with the smallest number of edges, that are non-computable for \(\mathcal{F}_{n}\) and \(\mathcal{F}_{e}\).

\(k\)**-WL expressive power.** For simple graphs, there is a natural connection between our Prototypical graph models and the \(k\)-WL graph isomorphism tests. This stems from a result of Dvorak (2010); Dell et al. (2018), which states that two graphs \(\textbf{X}^{(1)}\) and \(\textbf{X}^{(2)}\) are \(k\)-FWL equivalent if and only if \(\hom(H,\textbf{X}^{(1)})=\hom(H,\textbf{X}^{(2)})\) for all \(H\) of tree-width at most \(k\). Recall that \(\hom(H,\textbf{X})\) is the number of homomorphisms from \(H\) to **X** (where \(H\) has no red edges), which we show is equivalent to the output of \(P_{H}(\textbf{X})\) for the invariant polynomial \(P_{H}\) in Appendix F. By showing that the Prototypical node-based graph model can contract any \(H\) of tree-width 1 (and no others), and that the Prototypical edge-based graph model can contract any \(H\) of tree-width at most 2 (and no others), we thus have the following result.

**Proposition 3.6**.: _The Prototypical node-based model can distinguish a pair of simple graphs if and only if 1-WL can. The Prototypical edge-based model can distinguish a pair of simple graphs if and only if 3-WL / 2-FWL can._

### GNNs and their expressive power

In this section we turn our attention to commonly used graph neural networks (GNNs), and provide lower bounds on their polynomial expressive power as in Definition 3.2. The Message Passing Neural Network (MPNN) we consider consists of layers of the form

\[\textbf{Y}^{(k+1)}=\mbb\left[\textbf{X}\textbf{Y}^{(k)},\mathbf{1}\mathbf{1}^ {T}\textbf{Y}^{(k)},\textbf{Y}^{(k)}\right], \tag{9}\]

where the intermediate tensor variables are \(\textbf{Y}\in\mathbb{R}^{n\times d}\), \(\mathbf{1}\in\mathbb{R}^{n}\) is the vector of all ones, \(\textbf{Y}^{(0)}=\mathbf{1}\), brackets indicate concatenation in the feature dimension, and \(\mbb\) means a multilayer perceptron (MLP) applied to the feature dimension.

As an application of the Prototypical edge-based model, we propose and implement a new model architecture (PPGN++) that is at least as expressive as the full versions of PPGN/Ring-GNN (Maron et al., 2019; Chen et al., 2019) (which incorporate all \(15\) linear basis elements), but is more efficient -- PPGN++ uses a smaller number of "primitive" operations than the full PPGN/Ring-GNN, and does not need parameters for each linear basis element:

\[\textbf{Z}^{(k+1)}=\mbb_{3}\left[\mbb_{1}\left[\textbf{Z}^{(k)},\textbf{Z}^{( k)T}\right]\otimes\mbb_{2}(\textbf{Z}^{(k)}),\textbf{Z}^{(k)}\right], \tag{10}\]

where \(\textbf{Z}\in\mathbb{R}^{n^{2}\times d}\) are intermediate tensor variables, \(\textbf{Z}^{(0)}=\mathbf{X}\), \(\mbb_{\frac{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{ \cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot}{\cdot }{\cdot}{\
relevant polynomials \(P_{H}\) (right). For the node based model we count only node-valued polynomials, while for the edge based model we count both node and edge-valued polynomials. Note that the number of non-computable polynomials is substantially smaller than the total number, especially in \(\mathcal{F}_{e}\). Since polynomials are calculated at the data preprocessing step, there is an upfront computational cost for this procedure that must be accounted for. Finding the optimal contraction path that minimizes runtime complexity for a general matrix polynomial is an NP-hard problem (Biamonte et al., 2015) with a naive upper bound in runtime complexity of \(O(n^{d})\). An empirical evaluation of the preprocessing time is in Appendix A; in our experiments, preprocessing time is small compared to training time.

## 4 Related Work

**Relation to Homomorphisms and Subgraph Counts.** Past work has studied invariant polynomials on graphs (Thiery, 2000; Lovasz, 2012). Viewed as functions on binary inputs, the basis consists of functions that count homomorphisms or injective homomorphisms of \(H\) into an input graph \(\mathbf{X}\). Homomorphisms are related to the \(P_{H}\) basis, and injective homomorphisms are related to \(Q_{H}\) (see Appendix F). Also, equivariant homomorphism counts that relate to our \(P_{H}\) or \(Q_{H}\) has been studied (Mancinska and Roberson, 2020; Grohe et al., 2021; Maehara and NT, 2019; Bouritsas et al., 2022). However, these works do not exhibit a basis of equivariant polynomials. Also, our tensor contraction interpretation and analysis does not appear in past work.

**Expressivity Measures for Graph Models.** The \(k\)-WL hierarchy has been widely used for studying graph machine learning (Morris et al., 2021), starting with the works of Morris et al. (2019) and Xu et al. (2019), which show an equivalence between message passing neural networks and 1-WL. Tensor methods resembling \(k\)-WL such as \(k\)-IGN (Maron et al., 2018) and PPGN-like methods (Maron et al., 2019; Azizian and Lelarge, 2021) achieve \(k\)-WL power (Azizian and Lelarge, 2021; Geerts and Reutter, 2022), but scale in memory as \(n^{k}\) or \(n^{k-1}\) for \(n\)-node graphs. Morris et al. (2019, 2022) define new \(k\)-WL variants with locality and sparsity biases, which gives a finer hierarchy and offers a trade-off between efficiency and expressiveness.

A matrix query language (MATLANG) (Brijder et al., 2019; Geerts, 2021) and a more general tensor language (TL) (Geerts and Reutter, 2022) have been used to study expressive power of GNNs (Balcilar et al., 2021; Geerts and Reutter, 2022). These languages define operations and ways to compose them for processing graphs in a permutation equivariant or invariant way. Our edge-based Prototypical model result gives a new perspective on a result of Geerts (2021), which shows that MATLAB can distinguish any two graphs that 2-FWL / 3-WL can. Indeed, our edge-based graph model includes the five linear algebra operations that form the 3-WL expressive MATLAB. While the operations of MATLAB were included in a somewhat ad-hoc manner ("motivated by operations supported in linear algebra package" (Geerts, 2021)), our framework shows that these are the at-most quadratic equivariant polynomials that are required to contract all tree-width 2 graphs.

## 5 Experiments

In this section we demonstrate the impact of increasing the polynomial expressive power of GNNs. We test two families of models. PPGN++ (\(d\)) uses the architecture in equation 10, derived using our edge based Prototypical model, and achieves \(d\) polynomial expressive power by pre-computing polynomial features found in Subsection 3.3; missing (\(d\)) notation means using just PPGN++ without pre-computed features. GatedGCN (\(d\)) uses the base MPNN architecture of (Bresson and Laurent, 2017) with the \(d\)-expressive polynomials pre-computed. We experiment with \(4\) datasets: a graph isomorphism dataset SR (Bodnar et al., 2021), which measures the ability of GNNs to distinguish strongly regular graphs; and \(3\) real-world molecular property prediction datasets including ZINC, ZINC-full (Dwivedi et al., 2020) and Alchemy (Chen et al., 2019).

### Graph Isomorphism Expressiveness

Distinguishing non-isomorphic graphs from families of strongly regular graphs is a challenging task (Bodnar et al., 2021, 2020). The SR dataset (Bouritsas et al., 2022) is composed of 9 strongly regular families. This dataset is challenging since any pair of graphs in the SR dataset cannot be distinguished by the \(3\)-WL algorithm. This experiment is done without any training (same procedure as in (Bodnar et al., 2021)) and the evaluation is done by randomly initialized models. For every family in the dataset, we iterate over all pairs of graphs and report the fraction that the model determines are isomorphic. Two graphs are considered isomorphic if the \(L_{2}\) distance between their embeddings is smaller than a certain threshold (\(\epsilon=0.01\)). This procedure was repeated for \(5\) different random seeds and the averaged fraction rate was reported in Figure 9. This figure portrays the expressiveness boost gained by using high degree polynomial features. While the base models, GatedGCN and PPGN (and PPGN++), cannot distinguish any pair of graphs (as theoretically expected), adding higher degree polynomial features significantly improves the ability of the model to

\begin{table}
\begin{tabular}{l|c|c|c|c|c} \hline  & \(d=3\) & \(d=4\) & \(d=5\) & \(d=6\) & \(d=7\) \\ \hline \(\mathcal{F}_{n}\) & 2/8 & 6/18 & 23/49 & 85/144 & 308/446 \\ \hline \(\mathcal{F}_{e}\) & 0/18 & 0/53 & 1/174 & 11/604 & 72/2193 \\ \hline \end{tabular}
\end{table}
Table 1: Numbers of non-computable polynomials (left) out of all relevant polynomials (right) for the Prototypical models.
distinguish non-isomorphic graphs in this dataset. Optimal results of \(0\%\) failure rate are obtained for PPGN++ (\(d\)) with \(d\geq 6\) (i.e., adding at-least degree \(6\) polynomial features). For the GatedGCN model, although we do not reach the \(0\%\) failure rate, adding the right polynomial features makes GatedGCN outperform \(3\)-WL based models in distinguishing non-isomorphic graphs in this dataset.

### Real-World Datasets

The efficacy of increasing polynomial expressive power on real-world data (molecular graphs datasets) was evaluated on \(3\) graph regression tasks: ZINC, ZINC-full and Alchemy.

**Training.** We followed the training protocol mentioned in (Dwivedi et al., 2020) for ZINC and ZINC-full and the protocol from (Lim et al., 2022) for Alchemy. All of our trained models obey a \(500K\) parameter budget. Further details regarding the training procedure and model parameters can be found in Appendix A.

**Baselines.** The baseline results for the ZINC \(12K\) experiment were obtained from (Zhao et al., 2022), except for PPGN and GatedGCN, which we calculated. For ZINC-full and Alchemy we used the results from (Lim et al., 2022) (again, excluding PPGN).

**Results.** The mean absolute error (MAE) over the test set is reported in Table 3 for ZINC \(12K\) and Table 2 for ZINC-full and alchemy. In both tables, PPGN++ (\(6\)) achieves SOTA results across all \(3\) datasets. In addition, for both test model families there is a clear correlation between higher \(d\) (polynomial expressiveness) and test error. Furthermore, PPGN++ (\(5\)) and PPGN++ (\(6\)), which produce the top results in all \(3\) experiments, are the only \(2\) models (including all baselines) which are provably strictly more powerful than 3-WL. Our results add evidence to the guiding hypothesis that increases in expressivity facilitate improved downstream performance.

## 6 Conclusions

We propose a novel framework for evaluating the expressive power of graph neural networks (GNNs) by evaluating their ability to approximate equivariant graph polynomials. Our first step was introducing a basis for equivariant graph polynomials of any degree. We then utilized Prototypical graph models to determine the computability of these polynomials with practical GNNs. This led to a method for increasing the expressivity of GNNs through the use of precomputed polynomial features, resulting in a significant improvement in empirical performance.

Future research could focus on several promising directions. One direction can reduce the number of features passed into GNNs by working with a generating set of polynomials rather than the complete basis. Additionally, incorporating features on nodes and edges, as outlined in Appendix E, could further improve performance. Another exciting avenue for exploration can incorporate otherwise uncomputable polynomials as computational primitives into GNN layers, rather than as features, to increase expressiveness. Finally, it would be beneficial to study Prototypical graph models to identify families with optimal properties related to expressiveness, memory/computation complexity,

\begin{table}
\begin{tabular}{l|c|c} \hline \multirow{2}{*}{Model} & ZINC-Full & Alchemy \\ \cline{2-3}  & Test MAE & Test MAE \\ \hline GIN (Xu et al., 2019) &.088 \(\pm\).002 &.180 \(\pm\).006 \\ \(\delta\)-2-GNN (Morris et al., 2019) &.042 \(\pm\).003 &.118 \(\pm\).001 \\ SpeedNet (Morris et al., 2022) & - &.115 \(\pm\).001 \\ PF-GNN (Dupty et al., 2022) & - &.111 \(\pm\).010 \\ HIMP (Fey et al., 2020) &.036 \(\pm\).002 & - \\ SignNet (Lim et al., 2022) &.024 \(\pm\).003 &.113 \(\pm\).002 \\ CIN (Bodnar et al., 2021a) &.022 \(\pm\).002 & - \\ \hline PPGN (Maron et al., 2019) &.022 \(\pm\).003 &.113 \(\pm\).001 \\ PPGN++ &.022 \(\pm\).001 &.111 \(\pm\).002 \\
**PPGN++ (5)** & **.020 \(\pm\).001** &.110 \(\pm\).001 \\
**PPGN++ (6)** & **.020 \(\pm\).001** & **.109 \(\pm\).001** \\ \hline \end{tabular}
\end{table}
Table 2: Results on Alchemy (Chen et al., 2019) and ZINC-full (Dwivedi et al., 2020) datasets. Lower is better, best models are marked in **bold**.

\begin{table}
\begin{tabular}{l|c} \hline \multirow{2}{*}{Model} & ZINC-Full & Alchemy \\ \cline{2-3}  & Test MAE & Test MAE \\ \hline GIN (Xu et al., 2019) &.088 \(\pm\).002 &.180 \(\pm\).006 \\ PNA (Corso et al., 2020) &.140 \(\pm\).006 \\ GSN (Bouritsas et al., 2022) &.115 \(\pm\).012 \\ PF-GNN (Dupty et al., 2022) &.122 \(\pm\).010 \\ GIN-AK (Zhao et al., 2021) &.080 \(\pm\).001 \\ CIN (Bodnar et al., 2021a) &.079 \(\pm\).006 \\ SetGNN (Zhao et al., 2022) &.075 \(\pm\).003 \\ \hline GatedGCN (Bresson and Laurent, 2017) &.265 \(\pm\).015 \\ GatedGCN (\(4\)) &.150 \(\pm\).005 \\ GatedGCN (\(5\)) &.138 \(\pm\).003 \\ GatedGCN (\(6\)) &.106 \(\pm\).003 \\ \hline PPGN (Maron et al., 2019) &.079 \(\pm\).005 \\ PPGN++ &.076 \(\pm\).003 \\ PPGN++ (5) &.072 \(\pm\).005 \\
**PPGN++ (6)** & **.071 \(\pm\).001** \\ \hline \end{tabular}
\end{table}
Table 3: Results on ZINC \(12K\)(Dwivedi et al., 2020) dataset. Lower is better, best model is marked in **bold**.

Figure 9: Failure rate (log scale) for distinguishing SR graphs, the lower the better.
and the size of the contraction bank.

## 7 Acknowledgments

OP is supported by a grant from Israel CHE Program for Data Science Research Centers. We thank Nicolas Usunier For his insightful remarks.
