Technical report: Graph Neural Networks go Grammatical
This paper introduces a framework for formally establishing a connection
between a portion of an algebraic language and a Graph Neural Network (GNN).
The framework leverages Context-Free Grammars (CFG) to organize algebraic
operations into generative rules that can be translated into a GNN layer model.
As CFGs derived directly from a language tend to contain redundancies in their
rules and variables, we present a grammar reduction scheme. By applying this
strategy, we define a CFG that conforms to the third-order Weisfeiler-Lehman
(3-WL) test using MATLANG. From this 3-WL CFG, we derive a GNN model, named
G$^2$N$^2$, which is provably 3-WL compliant. Through various experiments, we
demonstrate the superior efficiency of G$^2$N$^2$ compared to other 3-WL GNNs
across numerous downstream tasks. Specifically, one experiment highlights the
benefits of grammar reduction within our framework.
Jason Piquenot, Aldo Moscatelli, Maxime Bérar, Pierre Héroux, Romain raveaux, Jean-Yves Ramel, Sébastien Adam
# Technical report : Graph Neural Networks go Grammatical

###### Abstract

This paper proposes a new GNN design strategy. This strategy relies on Context-Free Grammars (CFG) generating the matrix language MATLAB. It enables us to ensure both WL-expressive power, substructure counting abilities and spectral properties. Applying our strategy, we design Grammatical Graph Neural Network G\({}^{2}\)N\({}^{2}\), a provably 3-WL GNN able to count at edge-level cycles of length up to 6 and able to reach band-pass filters. A large number of experiments covering these properties corroborate the presented theoretical results.

## 1 Introduction

In the last few years, characterising the expressive power of Graph Neural Networks (GNNs) has become a major concern in order to theoretically rank the plethora of existing models and to design new provably powerful GNNs [1].

In this field, the Weisfeiler-Lehman hierarchy, based on the eponymous polynomial-time test [2], is the most common way to characterise architectures. An important result using this tool has been the proof that the architectures most used in practice, i.e. Message Passing Neural Networks (MPNNs) [3, 4], are at most as powerful as the first-order Weisfeiler-Lehman test (1-WL) [1, 5].

To go beyond the 1-WL limit, [1, 6] propose some generalisations of GNNs relying on the manipulation of higher-order tensors. In [7], a model called \(k\)-IGN is proven to be equivalent to \(k\)-WL. With \(k\) big enough, \(k\)-IGN is theoretically a universal approximator. However, when \(k\) increases, the computational and memory complexities grow exponentially. To overcome this limitation, the same paper describes Provably Powerful Graph Network (PPGN), that mimics the second-order Folklore Weisfeiler-Lehman test (2-FWL), known to be equivalent to 3-WL.

Even if the WL hierarchy has been useful to evaluate GNNs and to search for better models, most of the time 3-WL and 1-WL are only bounds of expressive power. A recent way to refine this WL hierarchy is to study the substructures GNNs can count in a graph [8, 9]. Following this research direction, [9] were able to classify some recent models that were categorised by [10] between 1-WL and 3-WL.

Both the WL hierarchy and the counting power only focus on the structure of the graph, neglecting the effect of models on the signal handled by the nodes. As shown in [11], the majority of spatially designed MPNNs work as low-pass filters while spectrally designed ones can reach band-pass filters. Yet, such band-pass filters can be useful for certain downstream tasks. Thus, the spectral ability of GNN models is a complementary way of measuring the expressive power of a model.

Taking into consideration the three characterization aspects mentioned above, this paper proposes a new GNN design strategy and a new model called Grammatical Graph Neural Network (G\({}^{2}\)N\({}^{2}\)) resulting from this strategy. Our strategy relies on the MATLAB language introduced in [12] and more particularly on the fragments of MATLAB called \(\operatorname{ML}\left(\mathcal{L}_{1}\right)\) and \(\operatorname{ML}\left(\mathcal{L}_{3}\right)\), shown to be as expressive as 1-WL and 3-WL in [13]. Starting from the operations sets \(\mathcal{L}_{1}\) and \(\mathcal{L}_{3}\), we propose to build Context-Free Grammars (CFG) able to
generate \(\mathrm{ML}\left(\mathcal{L}_{1}\right)\) and \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\). Since the amount of possible operations in the corresponding CFGs is pretty high, those CFGs are reduced, keeping the equivalence with 1-WL and 3-WL. From the variables of those reduced CFGs, GNN inputs can easily be deduced. Then, the rules of the CFGs determine the GNN layers update rules and the readout functions. A direct benefit of this design strategy is that GNN abilities can be deduced from the study of the language derived from the CFG. As an illustration, one of our subsequent contributions is the proposition of algebraic expressions in \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) which, applied on the adjacency matrix, are able to count cycles of length up to 6 and chordal cycles at edge-level.

Our strategy provably ensures that our \(\mathrm{G}^{2}\mathrm{N}^{2}\) model is (i) **exactly as expressive as \(3\)-WL** since it inherits expressive power of \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\), (ii) **able to count important substructures both at node-, graph- and edge-levels**, surpassing the counting abilities of existing MPNNs and subgraph MPNNs and (iii) **able to approximate low-pass, high-pass and band-pass filters** in the spectral domain while most models and in particular PPGN cannot experimentally approximate band-pass filters.

These theoretical results are confirmed by numerous experiments on various well-known dedicated graph datasets. Moreover, we also show that the proposed reduced CFGs can describe many existing MPNNs and even PPGN.

The paper is structured as follows. In section 2, after introducing WL, MATLAB and CFGs, we describe our GNN design strategy and present the resulting \(\mathrm{G}^{2}\mathrm{N}^{2}\) architecture. We also show that our strategy generalizes both existing MPNNs and PPGN. Then, in section 3, we theoretically study the counting power and the spectral ability of \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\). Section 4 validates the theoretical analysis of section 3 through an extensive experimental evaluation of \(\mathrm{G}^{2}\mathrm{N}^{2}\).

## 2 From CFG to the \(3\)-Wl \(\mathrm{G}^{2}\mathrm{N}^{2}\)

Let \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) be a graph with \(n\) nodes, \(\mathcal{V}=\left[\!\left[1\,,n\right]\!\right]\) and an arbitrary number of edges \(\mathcal{E}\subset\mathcal{V}\times\mathcal{V}\). The adjacency matrix \(A\in\{0,1\}^{n\times n}\) represents the connectivity of \(\mathcal{G}\), \(\mathrm{I}\in\{0,1\}^{n\times n}\) is the identity matrix and \(J\in\{0,1\}^{n\times n}\) denotes a matrix filled with ones except for the diagonal.

### MATLAB and the Weisfeiler-Lehman hierarchy

**Definition 2.1** (Matlang [12]): MATLAB is a matrix language with an allowed operation set \(\{+,\cdot,\odot,\ \ \mathbf{{}^{T}},\mathrm{Tr},\mathrm{diag},1,\times,f\}\) denoting respectively matrices addition, usual and element-wise multiplications, transpose and trace computations, diagonal matrix creation from a vector, column vector of 1 generation, scalar multiplication and element-wise custom function applied on scalars, vectors or matrices. Restricting the set of operations to a subset \(\mathcal{L}\), one can define a fragment of MATLAB \(\mathrm{ML}\left(\mathcal{L}\right)\). \(s(X)\in\mathbb{R}\) is a sentence in \(\mathrm{ML}\left(\mathcal{L}\right)\) if it consists of any possible consecutive operations in \(\mathcal{L}\) operating on a given matrix \(X\) and resulting in a scalar value. _As an example, \(s(X)=1^{\mathbf{T}}\left(X\odot\mathrm{diag}\left(1\right)\right)1\) is a sentence of \(\mathrm{ML}\left(\{\cdot,\ \mathbf{{}^{T}},1,\mathrm{diag},\odot\}\right)\) computing the trace of \(X\)._

Applying sentences on the adjacency matrix (i.e. setting \(X=A\)) allows linking the distinguishing power of the WL test and fragments of MATLAB. The equivalences between fragments from \(\mathcal{L}_{1}=\{\cdot,\ \mathbf{{}^{T}},1,\mathrm{diag}\}\) and \(\mathcal{L}_{3}=\{\cdot,\ \mathbf{{}^{T}},1,\mathrm{diag},\odot\}\) and respectively the 1-WL and 3-WL tests are shown in [13]. Two graphs are indistinguishable by the 1-WL and the 3-WL tests if and only if their adjacency matrices are indistinguishable by any sentences of respectively \(\mathrm{ML}\left(\mathcal{L}_{1}\right)\) and \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\).

Seen through the lens of MATLAB, a GNN tries to learn an appropriate sentence to solve a downstream task. Thus, to inherit the 1-WL (resp. 3-WL) language expressivity, we must ensure that the architecture can generate every sentence in \(\mathrm{ML}\left(\mathcal{L}_{1}\right)\) (resp. \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\)) for a given number of layers. However, integrating the whole set of elementary operations directly will result in an inefficient architecture: each elementary operation corresponds in a layer to a large number of parameters and some can be attained through others.

To overcome this issue, we propose to use Context-Free Grammar (CFG) as a tool to reduce the number of elementary operations while keeping the ability to produce all sentences in those languages. As far as we know, it is the first time that a CFG is used to build a GNN.
### Context-Free Grammar and Language

**Definition 2.2** (Context-Free Grammar):

A Context-Free Grammar (CFG) \(G\) is a \(4\)-tuple \(\left(V,\Sigma,R,S\right)\) with \(V\) a finite set of variables, \(\Sigma\) a finite set of terminal symbols, \(R\) a finite set of rules \(V\rightarrow\left(V\cup\Sigma\right)^{*}\), \(S\) a start variable. _Note that \(R\) completely describes a CFG with the convention that the start variable is placed on the top left._

**Definition 2.3** (Derivation):

Let \(G\) be a CFG. For \(u,v\in\left(V\cup\Sigma\right)^{*}\), define \(u\implies v\) if \(u\) can be transformed into \(v\) by applying one rule and \(u\ \overset{*}{\implies}\ v\) if \(u\) can be transformed into \(v\) by applying an arbitrary number of rules in \(G\).

**Definition 2.4** (Context-Free Language):

\(B\) is a Context-Free Language (CFL) if there exists a CFG \(G\) such that \(B=L(G):=\left\{w\ \middle|\ w\in\Sigma^{*}\text{ and }S\ \overset{*}{\implies}\ w\right\}\).

In a CFG, sentences are produced by applying rules to variables until only terminal symbols remain. The variables are the symbols on the left side of a rule and the terminal symbol is any of the other ones. Figure 1 shows how the CFG \(G_{\mathcal{L}_{1}}\) produces the sentence \(1^{\mathbf{T}}A\mathrm{diag}\left(A1\right)1\).

The next two subsections focus on reducing \(\mathrm{ML}\left(\mathcal{L}_{1}\right)\) and \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) CFGs.

### From CFG to GNN

CFG objects and GNN elements are linked as follows. Variables correspond to layers inputs and outputs. Rules translate as update equations and readout functions. Terminal symbols relate to model inputs. In order to exploit the equivalence between WL and \(\mathrm{ML}\left(\mathcal{L}\right)\), the adjacency matrix \(A\) is a terminal symbol of the grammar.

The following proposition is necessary for the proof of Theorem 2.1.

**Proposition 2.1**:

_For any square matrix of size \(n^{2}\), \(\mathrm{ML}\left(\mathcal{L}_{1}\right)\) can only produce square matrices of size \(n^{2}\), row and column vectors of size \(n\) and scalars._
Proof.: Let \(M\) be a square matrix of size \(n^{2}\), we first need to prove that \(\operatorname{ML}\left(\mathcal{L}_{1}\right)\) can produce square matrices of size \(n^{2}\), row and column vectors of size \(n\) and scalars.

Yet \(1(M)\) is a column vector of size \(n\), \(1(M)^{\mathbf{T}}\) is a row vector of size \(n\), \(1(M)^{\mathbf{T}}\cdot 1(M)\) is a scalar and \(\operatorname{diag}\left(1(M)\right)\) is a square matrix of size \(n^{2}\).

Then let \(N\in\mathbb{R}^{n\times n}\), \(v\in\mathbb{R}^{n}\), \(w\in\left(\mathbb{R}^{n}\right)^{*}\), and \(s\in\mathbb{R}\) be words \(\operatorname{ML}\left(\mathcal{L}_{1}\right)\) can produce, we have

\[M\cdot N \in\mathbb{R}^{n\times n} M\cdot v \in\mathbb{R}^{n} w\cdot M\in\left(\mathbb{R}^{n}\right)^{*} w\cdot v \in\mathbb{R}\] \[v\cdot w \in\mathbb{R}^{n\times n} 1(v) \in\mathbb{R}^{n} v^{\mathbf{T}} \in\left(\mathbb{R}^{n}\right)^{*} 1(w) \in\mathbb{R}\] \[M^{\mathbf{T}} \in\mathbb{R}^{n\times n} w^{\mathbf{T}} \in\mathbb{R}^{n} s\cdot w\in\left(\mathbb{R}^{n}\right)^{*} \operatorname{diag}\left(s\right) \in\mathbb{R}\] \[\operatorname{diag}\left(v\right) \in\mathbb{R}^{n\times n} 1(M) \in\mathbb{R}^{n} s\cdot s \in\mathbb{R}\] \[v\cdot s \in\mathbb{R}^{n} 1(s) \in\mathbb{R}\]

Since this is an exhaustive list of all operations \(\operatorname{ML}\left(\mathcal{L}_{1}\right)\) can produce with these words, we can conclude. 

**Theorem 2.1** (\(\operatorname{ML}\left(\mathcal{L}_{1}\right)\) reduced CFG )

_The following CFG denoted r-\(G_{\mathcal{L}_{1}}\) is as expressive as \(1\)-WL._

\[V_{c}\rightarrow\operatorname{diag}\left(V_{c}\right)V_{c}\ \mid\ AV_{c}\ \mid\ 1 \tag{1}\]

Proof.: Proposition 2.1 leads to only four variables. \(M\) for the square matrices, \(V_{c}\) for the column vectors, \(V_{r}\) for the row vectors and \(S\) for the scalars. We define a CFG \(G_{\mathcal{L}_{1}}\) :

\[S \rightarrow(V_{r})(V_{c})\ |\ \operatorname{diag}\left(S\right)\ |\ SS \tag{2}\] \[V_{c} \to MV_{c}\ |\ (V_{r})^{\mathbf{T}}\ |\ V_{c}S\ |\ 1\] \[V_{r} \to V_{r}M\ |\ (V_{c})^{\mathbf{T}}\ |\ SV_{r}\] \[M \to MM\ |\ (M)^{\mathbf{T}}\ |\ \operatorname{diag}\left(V_{c} \right)\ |\ (V_{c})(V_{r})\ |\ A\]

As any sentences produced by \(\operatorname{ML}\left(\mathcal{L}_{1}\right)\) can obviously be derived from \(G_{\mathcal{L}_{1}}\), \(\operatorname{ML}\left(\mathcal{L}_{1}\right)=L(G_{\mathcal{L}_{1}})\). For any scalar \(s,s^{\prime}\), since \(\operatorname{diag}\left(s\right)\) and \(s\cdot s^{\prime}\) produce a scalar, the only way to produce a scalar from another variable is to pass through a vector dot product. It implies that to generate scalars, we only need to be able to generate vectors. We can then reduce \(G_{\mathcal{L}_{1}}\) by removing \(S\) and setting \(V_{c}\) as starting variable.

\[V_{c} \to MV_{c}\ |\ (V_{r})^{\mathbf{T}}\ |\ 1\] \[V_{r} \to V_{r}M\ |\ (V_{c})^{\mathbf{T}}\] \[M \to MM\ |\ (M)^{\mathbf{T}}\ |\ \operatorname{diag}\left(V_{c} \right)\ |\ (V_{c})(V_{r})\ |\ A\]

To ensure that the start variable is \(V_{c}\), a mandatory subsequent operation will be \(MV_{c}\) for any matrix variable \(M\). As a consequence, by associativity of the matrix multiplication, \(MM\) and \((V_{c})(V_{r})\) can be removed from the rule of \(M\).

\[V_{c} \to MV_{c}\ |\ (V_{r})^{\mathbf{T}}\ |\ 1\] \[V_{r} \to V_{r}M\ |\ (V_{c})^{\mathbf{T}}\] \[M \to(M)^{\mathbf{T}}\ |\ \operatorname{diag}\left(V_{c}\right)\ |\ A\]

Since \(\operatorname{diag}\) produces symmetric matrices and \(A\) is symmetric, \((M)^{\mathbf{T}}\) does not play any role here. As a consequence, we can then focus on the column vector and we obtain r-\(G_{\mathcal{L}_{1}}\)
### From r-\(G_{\mathcal{L}_{3}}\) to \(3\)-Wl Gnn

The following propositions are used in the proof of theorem 2.2.

**Proposition 2.2**:

_For any square matrix of size \(n^{2}\), \(\operatorname{ML}\left(\mathcal{L}_{3}\right)\) can only produce square matrices of the same size, row and column vectors of size \(n\) and scalars._

Proof.: Since \(\mathcal{L}_{1}\subset\mathcal{L}_{3}\), we only need to check the words the rule associated to the matrix Hadamard product can produce. Let \(M\in\mathbb{R}^{n\times n}\) and \(N\in\mathbb{R}^{n\times n}\) be words \(\operatorname{ML}\left(\mathcal{L}_{3}\right)\) can produce, we have \(M\odot N\in\mathbb{R}^{n\times n}\). We can conclude. 

**Proposition 2.3**:

_For any square matrix \(M\), column vector \(v\) and row vector \(w\), we have_

\[M\odot\left(v\cdot w\right)=\operatorname{diag}\left(v\right)M\operatorname{ diag}\left(w\right)\]

Proof.: Let \(M\) be a square matrix, \(v,w\) be respectively column and row vectors, we have for any \(i,j\),

\[\left(M\odot\left(v\cdot w\right)\right)_{i,j} =M_{i,j}(v\cdot w)_{i,j}\] \[=v_{i}M_{i,j}w_{j}\] \[=\sum_{l}\operatorname{diag}\left(v\right)_{i,l}M_{l,j}w_{j}\] \[=\left(\operatorname{diag}\left(v\right)M\right)_{i,j}w_{j}\] \[=\sum_{l}(\operatorname{diag}\left(v\right)M)_{i,l}\operatorname {diag}\left(w\right)_{l,j}\] \[=\left(\operatorname{diag}\left(v\right)M\operatorname{diag} \left(w\right)\right)_{i,j}\]

We only use the scalar product commutativity here. 

**Theorem 2.2** (\(\operatorname{ML}\left(\mathcal{L}_{3}\right)\) reduced CFG ):

_The following CFG r-\(G_{\mathcal{L}_{3}}\) is as expressive as \(3\)-WL._

\[V_{c} \to MV_{c}\ |\ 1 \tag{3}\] \[M \to(M\odot M)\ |\ MM\ |\ \operatorname{diag}\left(V_{c}\right)\ |\ A\]

Proof.: \(\mathcal{L}_{3}=\{\cdot,\ ^{\mathbf{T}},1,\operatorname{diag},\odot\}\). Proposition 2.2 leads to the use of a CFG \(G_{\mathcal{L}_{3}}\) with the same variables as \(G_{\mathcal{L}_{1}}\). We

\[S \to(V_{r})(V_{c})\ |\ \operatorname{diag}\left(S\right)\ |\ SS\ |\ (S \odot S)\] \[V_{c} \to(V_{c}\odot V_{c})\ |\ MV_{c}\ |\ (V_{r})^{\mathbf{T}}\ |\ V_{c}S\ |\ 1\] \[V_{r} \to(V_{r}\odot V_{r})\ |\ V_{r}M\ |\ (V_{c})^{\mathbf{T}}\ |\ SV_{r}\] \[M \to(M\odot M)\ |\ MM\ |\ (M)^{\mathbf{T}}\ |\ \operatorname{diag} \left(V_{c}\right)\ |\ (V_{c})(V_{r})\ |\ A\]

As seen in the proof of Theorem 2.1, the scalar variable and rules can be removed. Since \(\operatorname{diag}\left(v\right)w=v\odot w\) for any vector \(v,w\), the vector Hadamard product can be removed from the vector rules. Proposition 2.3 allows to remove \(V_{c}V_{r}\) from the rules of \(M\) since the results of subsequent mandatory operations \(MM\) or \(MV_{c}\) can be obtained with other combinations.

\[V_{c} \to MV_{c}\ |\ (V_{r})^{\mathbf{T}}\ |\ 1\] \[V_{r} \to V_{r}M\ |\ (V_{c})^{\mathbf{T}}\] \[M \to(M\odot M)\ |\ MM\ |\ (M)^{\mathbf{T}}\ |\ \operatorname{diag} \left(V_{c}\right)\ |\ A\]

Since the remaining matrix rules preserve symmetry, \((M)^{\mathbf{T}}\), the variable \(V_{r}\) and its rules can be removed. \(G_{\mathcal{L}_{3}}\) can be reduced into r-\(G_{\mathcal{L}_{3}}\).
From variables to layer input/outputIn order to design G\({}^{2}\)N\({}^{2}\) from r-\(G_{\mathcal{L}_{3}}\), the variables \(M\) and \(V_{c}\) must appear in our architecture. \(V_{c}\) states for nodes embedding, \(M\) for edges embedding. Each layer \(l\) takes as inputs a matrix \(H^{(l)}\) stacking multiple node vectors on the second dimension and a three order tensor \(\mathcal{C}^{(l)}\) stacking square matrices on the third dimension. \(H^{(l)}\) and \(\mathcal{C}^{(l)}\) appear in red in figure 2 depicting a layer of G\({}^{2}\)N\({}^{2}\).

From rules to G\({}^{2}\)N\({}^{2}\) layer update functionsA given layer should implement \(M\) rules and \(V_{c}\) rules of r-\(G_{\mathcal{L}_{3}}\) on different matrix and vector arguments. As the number of layers is finite, in order to maintain expressive power, multiple instances of the rules \((M\odot M)\), \((MM)\), \(\operatorname{diag}{(V_{c})}\) should be computed. To provide arguments to each instance of the rules in parameterised quantities \(b_{\odot}\),\(b_{\odot}\),\(b_{\operatorname{diag}}\), linear combinations \(L_{i}\) of slices of \(\mathcal{C}^{(l)}\) and slices of \(H^{(l)}\) are learned, as shown in figure 2 before each matrix rules.

The output tensor \(\mathcal{C}^{(l+1)}\) with a selected third dimension size is produced by a MultiLayer Perceptron from the concatenation of all the rules results matrices. The output \(H^{(l+1)}\) is provided by the node aggregation of \(H^{(l)}\) with the matrix slices of \(\mathcal{C}^{(l+1)}\) implementing \(MV_{c}\) depicted as agg in figure 2.

Formally, the update equations are :

\[\mathcal{C}^{(l+1)}=mlp(\mathcal{C}^{(l)}|L_{1}(\mathcal{C}^{(l)} )\odot L_{2}(\mathcal{C}^{(l)})| \tag{4}\] \[L_{3}(\mathcal{C}^{(l)})\cdot L_{4}(\mathcal{C}^{(l)})| \operatorname{diag}(L_{5}(H^{(l)}))),\] \[H^{(l+1)}=\sum_{i=1}^{S^{(l+1)}}\mathcal{C}^{(l+1)}_{i}H^{(l)}W^ {(l,i)}. \tag{5}\]

Where all \(L_{i}\) are linear blocks acting on the third dimension of the tensor \(\mathcal{C}^{(l)}\) or the second dimension of \(H^{(l)}\). In particular \(L_{1,2}:\mathbb{R}^{S^{(l)}}\rightarrow\mathbb{R}^{b^{(l)}_{\odot}}\), \(L_{3,4}:\mathbb{R}^{S^{(l)}}\rightarrow\mathbb{R}^{b^{(l)}_{\odot}}\), \(L_{5}:\mathbb{R}^{f^{(l)}}\rightarrow\mathbb{R}^{b^{(l)}_{\operatorname{diag}}}\) and \(mlp:\mathbb{R}^{S^{(l)}+b^{(l)}_{\odot}+b^{(l)}_{\operatorname{\odot}}+b^{(l )}_{\operatorname{diag}}}\rightarrow\mathbb{R}^{S^{(l+1)}}\), and \(W^{(l,i)}\in\mathbb{R}^{f^{(l)}_{n}\times f^{(l+1)}_{n}}\) acts on the second dimension of the feature matrix.

From r-\(G_{\mathcal{L}_{3}}\) to G\({}^{2}\)N\({}^{2}\)The inputs of the architecture illustrated in figure 3 are \(H^{(0)}\) and \(\mathcal{C}^{(0)}\). \(H^{(0)}\) of size \(n\times f_{n}\) is the feature nodes matrix. It corresponds to the terminal symbol 1. \(\mathcal{C}^{(0)}\) is a stacking on the third dimension of the identity matrix \(\mathbb{I}=\operatorname{diag}{(1)}\), the adjacency matrix \(A\) and the extended adjacency tensor \(E\) of size \(n\times n\times f_{e}\), where \(f_{e}\) is the number of edge features. \(\mathcal{C}^{(0)}\in\mathbb{R}^{n\times n\times(e_{f}+2)}\) corresponds to the terminal symbol \(A\).

Figure 2: **Model of a G\({}^{2}\)N\({}^{2}\) layer.** From left to right, the \(S^{(l)}\) slices of the tensor input \(\mathcal{C}^{(l)}\) are linearly combined into \(2b_{\odot}+2b_{\odot}\) different matrices. Products of pairs of these matrices are then computed reflecting the rules \((M\odot M)\), \((MM)\) of r-\(G_{\mathcal{L}_{3}}\). Similarly, slices of \(H^{(l)}\) are linearly combined into \(b_{\operatorname{diag}}\) vectors transformed as diagonal matrices reflecting the rule \(\operatorname{diag}(V_{c})\). The concatenation of all these matrices and the slices of the input tensor are feed into a MultiLayer Perceptron to produce the \(S^{(l+1)}\) slices of the output tensor \(\mathcal{C}^{(l+1)}\). Finally, the slices of \(\mathcal{C}^{(l+1)}\) are aggregated to the node embeddings \(H^{(l)}\) to compute \(H^{(l+1)}\), reflecting rule \(MV_{c}\).
After the last layer, an invariant or equivariant function is applied on both \(H^{(l_{\text{\tiny{end}}})}\), the diagonal and the non-diagonal of \(\mathcal{C}^{(l_{\text{\tiny{end}}})}\).

Expressive power of \(\text{G}^{2}\text{N}^{2}\)The following theorem shows that our design strategy ensures that \(\text{G}^{2}\text{N}^{2}\) is \(3\)-WL.

**Theorem 2.3**: \(\text{G}^{2}\text{N}^{2}\) _is exactly as powerful as \(3\)-WL test._

Proof.: To prove that \(\text{G}^{2}\text{N}^{2}\) is exactly as powerful as \(3\)-WL, we show that \(\text{G}^{2}\text{N}^{2}\) at layer \(l\) can produce any matrices and vectors \(\text{r-}G_{\mathcal{L}_{3}}\) can produce, after \(l\) iterations.

It is true for \(l=1\). Indeed, at \(\text{r-}G_{\mathcal{L}_{3}}\) first iteration, we obtain the matrices \(\text{I}\), \(A\), \(A^{2}\) and the vectors \(1\) and \(A1\). Since any of \(L_{i}(\mathcal{C}^{(0)})\) for \(i\in\llbracket 1\,,6\rrbracket\) is a linear combination of \(A\) and \(\text{I}\), \(\text{G}^{2}\text{N}^{2}\) can produce those vectors and matrices in one layer.

Suppose that there exists \(l>0\) such that \(\text{G}^{2}\text{N}^{2}\) can produce any of the matrices and vectors \(\text{r-}G_{\mathcal{L}_{3}}\) can after \(l\) iterations. We denote by \(\mathcal{A}_{l}\) the set of those matrices and by \(\mathcal{V}_{l}\) the set of those vectors. At the \(l+1\)-th iteration, we have \(\mathcal{A}_{l+1}=\{M\odot N,MN,\text{diag}\left(V_{c}\right)|M,N\in\mathcal{ A}_{l}\,V_{c}\in\mathcal{V}_{l}\}\) and \(V_{l+1}=\{MV_{c}|M\in\mathcal{A}_{k},V_{c}\in\mathcal{V}_{l}\}\). Let \(M,N\in\mathcal{A}_{l}\) and \(V_{c}\in\mathcal{V}_{l}\) then by hypothesis \(\text{G}^{2}\text{N}^{2}\) can produce \(M,N\) at layer \(l\). Since \(L\) produces at least two different linear combinations of matrices or vectors in respectively \(\mathcal{A}_{l}\) and \(\mathcal{V}_{l}\), \(MN\), \(M\odot N\), \(MV_{c}\) and \(\text{diag}\left(V_{c}\right)\) are reachable at layer \(l+1\). Thus \(\mathcal{A}_{l+1}\) is included in the set of matrices \(\text{G}^{2}\text{N}^{2}\) can produce at layer \(l+1\) and \(V_{l+1}\) is included in the set of vectors \(\text{G}^{2}\text{N}^{2}\) can produce at layer \(l+1\). 

From \(\text{r-}G_{\mathcal{L}_{3}}\) to MPNNs and PPGNWe have already shown that most MPNNs can be written with operations in \(\text{r-}G_{\mathcal{L}_{1}}\), since \(\mathcal{L}_{1}\subset\mathcal{L}_{3}\) it stands for \(\text{r-}G_{\mathcal{L}_{3}}\). PPGN can also be written with \(\text{r-}G_{\mathcal{L}_{3}}\). Indeed, at each layer PPGN applies the matrix multiplication on matched matrices on the third dimension, operation included in \(\text{r-}G_{\mathcal{L}_{3}}\). The node features are stacked on the third dimension as diagonal matrices, the diag operation is also included in \(\text{r-}G_{\mathcal{L}_{3}}\). The readout of PPGN last update takes two inputs, the diagonal matrices and the non-diagonal matrices which are computed with the Hadamard product between these matrices and the identity. The Hadamard product is included in \(\text{r-}G_{\mathcal{L}_{3}}\). As all operations in PPGN are included, \(\text{r-}G_{\mathcal{L}_{3}}\) generalises PPGN. Actually, the following CFG describes PPGN :

\[M\to MM\mid\text{diag}\left(1\right)\;\mid M\odot\text{I}\mid M\odot J\mid A \tag{6}\]

Because of matrix product, \(\text{G}^{2}\text{N}^{2}\) has a temporal complexity \(O\left(n^{3}\right)\) and a memory complexity \(O\left(n^{2}\right)\) and thus it has the same complexity as PPGN.

The WL hierarchy is a way to categorize GNN, but the capacity of GNN to count substructures and the ability to approximate certain types of filters in the spectral domain can also categorize GNN. As \(\text{G}^{2}\text{N}^{2}\) is directly built from \(\text{r-}G_{\mathcal{L}_{3}}\), it inherits its expressive powers. That is why the following section focuses on \(\text{ML}\left(\mathcal{L}_{3}\right)\) capacity to count substructures and spectral response.

Figure 3: **Model of \(\text{G}^{2}\text{N}^{2}\) architecture from the graph to the output**. One can see that each layer updates the nodes and the edges embedding and that the readout function acts separately on the diagonal and the non-diagonal of \(\mathcal{C}^{(k)}\) and \(H^{(k)}\).
## 3 Substructure counting and spectral response of \(\mathbf{G}^{2}\mathbf{N}^{2}\)

### Counting substructures

As defined by [8, 9], the count of a substructure \(S\) in a graph \(\mathcal{G}\), denoted by \(C_{S}(\mathcal{G})\), is the total number of non-equivalent substructures \(S\) occurring as subgraphs of \(\mathcal{G}\). In the same way, we denote by \(C_{S}(\mathcal{G},i)\) (resp. \(C_{S}(\mathcal{G},i,j)\)) the count of substructure involving the node \(i\) (resp. the edge \((i,j)\)) in \(\mathcal{G}\). For symmetric substructures like cycles or cliques, there is no ambiguity about the position of a node or of an edge. But for non-symmetric ones, the position in the substructure is important, thus we define ad-hoc substructure counting. The adjacency matrix \(A\in\{0,1\}^{n\times n}\) represents the connectivity of \(\mathcal{G}\), \(\mathrm{I}\in\{0,1\}^{n\times n}\) is the identity matrix and \(J\in\{0,1\}^{n\times n}\) denotes a matrix filled with ones except for the diagonal which contains zeros. Figure 4 shows substructure counting at edge and node level for non-symmetric substructures.

We denote by \(e_{S}^{i}\) the number of edges involving node \(i\) in \(S\) and \(n_{S}\) the number of nodes in \(S\). We have the following relations:

\[C_{S}(\mathcal{G},i) =\frac{1}{e_{S}^{i}}\sum_{j}C_{S}(\mathcal{G},i,j)\quad,\forall\ i \in\llbracket 1\,,n\rrbracket, \tag{7}\] \[C_{S}(\mathcal{G}) =\frac{1}{n_{S}}\sum_{i}C_{S}(\mathcal{G},i). \tag{8}\]

Hence, edge-level counting is more expressive than node-level counting, itself more expressive than graph-level counting.

### \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) counting power

The graph-level counting power of 1-WL and 3-WL is partially covered in [14] : 3-WL can count paths up to length 6 and cycles up to length 7 and cannot count 4-cliques. [15, 16] proposed graph-level counting formulas for cycles up to length 7. In this subsection, algebraic formulas (sentences of \(\mathrm{ML}\left(3\right)\) applied to A) that count substructures at edge level are proved. To the best of our knowledge, for edge-level substructure counting such formulas have not been proposed in the literature. The following lemma is needed for the proof of theorem 3.2.

**Lemme 3.1**: _Let \(A\) be the adjacency matrix, then \(A^{k}\odot J\) computes the number of non-closed walks of size \(k\) between two nodes._

Proof.: Assuming that \((A^{k})_{i,j}\) computes the number of walks of size \(k\) from \(i\) to \(j\), we have that \((A^{k}\odot J)_{i,j}\) computes the number of non-closed walks of size \(k\) from \(i\) to \(j\), since the diagonal of \(J\) is filled with 0. 

**Theorem 3.2** (Path counting at edge-level): _For \(2\leqslant l\leqslant 5\), there exist matrices \(X_{l}\) in \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) where \((X_{l})_{i,j}\) gives the number of \(l\)-paths between nodes \(i\)

Figure 4: Edges and nodes counting in non-symmetric substructures, here a 2-chain and a chordal cycle. One can see in the 2-chain, from equation (8) in one case \(n_{S}=1\) and in the other \(n_{S}=2\), and in the chordal cycle, from equation (7) in one case \(e_{S}^{i}=1\) and in the other \(e_{S}^{i}=2\).
_and \(j\)._

\[X_{2} =A^{2}\odot J \tag{9}\] \[X_{3} =A^{3}\odot J-A(A^{2}\odot\mathrm{I})-(A^{2}\odot\mathrm{I})A+A\] (10) \[X_{4} =A^{4}\odot J-(A(A^{2}\odot\mathrm{I}-2\mathrm{I})A)\odot J\] (11) \[\quad-(A^{2}\odot\mathrm{I})X_{2}-X_{2}(A^{2}\odot\mathrm{I})\] \[\quad-A(A^{3}\odot\mathrm{I})-(A^{3}\odot\mathrm{I})A+3A^{2}\odot A\] \[X_{5} =A^{5}\odot J-A(A^{2}\odot\mathrm{I})(A^{2}\odot\mathrm{I}- \mathrm{I})\] (12) \[\quad-(A^{2}\odot\mathrm{I})A(A^{2}\odot\mathrm{I})-(A^{2}\odot \mathrm{I}-\mathrm{I})(A^{2}\odot\mathrm{I})A\] \[\quad-(A(A^{2}\odot\mathrm{I}-\mathrm{I})X_{2})\odot J\] \[\quad-(X_{2}(A^{2}\odot\mathrm{I}-\mathrm{I})A)\odot J\] \[\quad-(A^{2}\odot\mathrm{I})X_{3}-X_{3}(A^{2}\odot\mathrm{I}- \mathrm{I})\] \[\quad-(A^{3}\odot\mathrm{I})X_{2}-X_{2}(A^{3}\odot\mathrm{I})\] \[\quad-(A(A^{3}\odot\mathrm{I})A)\odot J-A\odot A^{2}\] \[\quad+3(A(A\odot A^{2})+(A\odot A^{2})A)\odot J\] \[\quad-A\mathrm{diag}\left((A\odot X_{3})1\right))-\mathrm{diag} \left((A\odot X_{3})1\right)A\] \[\quad+3A\odot X_{3}+3A\odot A^{2}\odot(A^{2}-(A^{2}>0))\]

The idea of the proof is to compute the number of non-closed walks of size \(l\) with \(A^{l}\odot J\) and then to enumerate the non-closed walks of size \(l\) that are not \(l\)-paths (non-closed walk with exactly \(l\) edges).

Proof.: In the following, for \(2\leqslant k\leqslant 5\), we will enumerate the different non-closed walks of size \(k\) that are not a path of size \(k\).

* For \(k=2\), the only non-closed walk of size \(2\) is the path of size \(2\). Thus lemma 3.1 leads to the conclusion that \(A^{2}\odot J\) computes the number of \(2\)-paths between two nodes. \[X_{2}=A^{2}\odot J\]
* For \(k=3\), two non-closed walks of size \(3\) are not a \(3\)-path: one can do a walk of size \(1\) and a closed walk of size \(2\) or the opposite. The first case is provided by \(A(A^{2}\odot\mathrm{I})\) and the second case by its transpose \((A^{2}\odot\mathrm{I})A\). Crossing an edge three times belongs to both of these cases, thus subtracting \(A\) from the sum of these matrices provides the exact number of such walks linking two nodes. Figure 5 resume this for a better understanding. \[X_{3}=A^{3}\odot J-A(A^{2}\odot\mathrm{I})-(A^{2}\odot\mathrm{I})A+A\]

Figure 5: Enumeration of non-closed walks of size \(3\). Values in nodes represent the number of each type of non-closed walk linking the red node to the others.
* For \(k=4\), there are five non-closed walks of size \(4\) that are not a \(4\)-path. One can do a walk of size \(1\), a closed walk of size \(2\), and then a walk of size \(1\). Directly from what we did for \(k=3\), \(A(A^{2}\odot I)A\) computes the number of such walks between two nodes, we just have to do the Hadamard product with \(J\) to avoid the closed walks. Doing a closed walk of size \(2\) and then a \(2\)-path or the opposite is another way to do such walks. By analogy with the proof for \(k=3\), we can compute this with \((A^{2}\odot I)(A^{2}\odot J)+(A^{2}\odot J)(A^{2}\odot I)-A^{2}\odot J\). Since such walks occur in the first case, we have to subtract another time \(A^{2}\odot J\). Finally, doing a walk of size \(1\) followed by a closed walk of size \(3\) or the opposite are the two last ways to obtain non-closed walks of size \(4\). Still, in analogy with \(k=3\), the number of such walks is computed by \(A(A^{3}\odot I)+(A^{3}\odot I)A-A\odot A^{2}\). Since there is an overlap of such walks and the ones in the previous paragraph between two nodes in the same triangle, \(2A\odot A^{2}\) has to be removed. Since \(A^{4}\odot J\) computes the number of non-closed walks between two nodes, after factorisation, we obtain the formula of the theorem. \[X_{4} =A^{4}\odot J-(A(A^{2}\odot I-2I)A)\odot J\] \[\quad-(A^{2}\odot I)X_{2}-X_{2}(A^{2}\odot I)\] \[\quad-A(A^{3}\odot I)-(A^{3}\odot I)A+3A^{2}\odot A\]
* For \(k=5\), there are many more non-closed walks of size \(5\) but the idea remains the same: count such walks and then subtract the ones that occur in two or more of such walks. First, we can decompose a non-closed walk of size \(5\) with two closed walks of size \(2\) and a walk of size \(1\), this number is computed by \[A(A^{2}\odot I)(A^{2}\odot I-I)+(A^{2}\odot I)A(A^{2}\odot I)\] \[\quad+(A^{2}\odot I-I)(A^{2}\odot I)A.\] We subtract the identity in \(A^{2}\odot I-I\) to remove the overlap walks in those three terms which are computed by \(A(A^{2}\odot I)+(A^{2}\odot I)A\). Second, we can decompose the non-closed walks of size \(5\) with a walk of size \(1\), a closed walk of size \(2\), and finally a \(2\)-path in this order or another. Such compositions of walks are computed by \[(A(A^{2}\odot I-I)X_{2}+X_{2}(A^{2}\odot I-I)A)\odot J.\] The Hadamard product by \(J\) prevents the count of closed walks of such a composition. Third, we can still do a closed walk of size \(2\) and then a \(3\)-path in any order. This is computed by \((A^{2}\odot I)X_{3}+X_{3}(A^{2}\odot I-I)\). Here we remove \(X_{3}\) since it is counted twice. Fourth, the next decomposition is a closed walk of size \(3\) and a \(2\)-path in each order or a walk of size \(1\), followed by a closed walk of size \(3\) and a walk of size \(1\). This is computed by \((A^{3}\odot I)X_{2}+X_{2}(A^{3}\odot I)+A(A^{3}\odot I)A\), to which we subtract \(3(AC_{3}+C_{3}A)\odot J-C_{3}\) to avoid counting such walks in a triangle with \(C_{3}=A\odot X_{2}\). Fifth, the last decomposition is a walk of size \(1\) and crossing a \(4\)-cycle in each order. It is computed by \(A\mathrm{diag}\,(C_{4}1)+\mathrm{diag}\,(C_{4}1)\,A-3C_{4}\) with \(C_{4}=A\odot X_{3}\). And eventually, if a chordal cycle occurs, we remove \(3A\odot A^{2}\odot(A^{2}-(A^{2}>0))\) to avoid counting walks
already counted.

\[X_{5} =A^{5}\odot J-A(A^{2}\odot\mathrm{I})(A^{2}\odot\mathrm{I}-\mathrm{I})\] \[\quad-(A^{2}\odot\mathrm{I})A(A^{2}\odot\mathrm{I})-(A^{2}\odot \mathrm{I}-\mathrm{I})(A^{2}\odot\mathrm{I})A\] \[\quad-(A(A^{2}\odot\mathrm{I}-\mathrm{I})X_{2})\odot J\] \[\quad-(X_{2}(A^{2}\odot\mathrm{I}-\mathrm{I})A)\odot J\] \[\quad-(A^{2}\odot\mathrm{I})X_{3}-X_{3}(A^{2}\odot\mathrm{I}- \mathrm{I})\] \[\quad-(A^{3}\odot\mathrm{I})X_{2}-X_{2}(A^{3}\odot\mathrm{I})\] \[\quad-(A(A^{3}\odot\mathrm{I})A)\odot J-A\odot A^{2}\] \[\quad+3(A(A\odot A^{2})+(A\odot A^{2})A)\odot J\] \[\quad-A\mathrm{diag}\left((A\odot X_{3})1\right))-\mathrm{diag} \left(((A\odot X_{3})1\right)A\] \[\quad+3A\odot X_{3}+3A\odot A^{2}\odot(A^{2}-(A^{2}>0))\]

It concludes the proof. 

If there exists a \(l\)-path between a node \(i\) and one of its neighbors \(j\) then the edge \((i,j)\) is part of a \((l+1)\)-cycle (closed walk with exactly \(l\) edges). As a consequence, the following proposition is proved. Figure 6 shows the link between path counting and cycle counting at edge level.

**Proposition 3.1** (cycle counting at edge level):

_For \(3\leqslant l\leqslant 6\), using \(X_{l-1}\) from theorem 3.2 the following formula computes a matrix \(C_{l}\) where \((C_{l})_{i,j}\) gives the number of \(l\)-cycles \((i,j)\) is within._

\[C_{l}=A\odot X_{l-1} \tag{13}\]

Another substructure that can be counted by \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) at edge level is the chordal cycle.

**Theorem 3.3** (chordal cycle counting at edge level):

_The following matrix computes the number of edges shared by two triangles_

\[\frac{1}{2}A\odot A^{2}\odot(A^{2}-(A^{2}>0)) \tag{14}\]

Proof.: The idea of the proof is that the quantity

\[\frac{1}{2}(A^{2}\odot(A^{2}-(A^{2}>0)))_{i,j}=\binom{A_{i,j}^{2}}{2}\]

Figure 6: Hadamard product allows to compute 4-cycle counting at edge level from adjacency and \(X_{3}\).
computes the selection of two different 2-paths linking nodes \(i\) and \(j\), thinking about the number of combinations. In fact, out of the diagonal, it computes the number of squares nodes \(i\) and \(j\) are sharing without being adjacent in the square subgraph. Then the Hadamard product with \(A\) acts like a condition function, since it returns the values already computed before only if \((i,j)\in\mathcal{E}\). 

From equations (7) and (8), one can easily deduce formulas to count at both node and graph levels.

**Theorem 3.4** (path counting at node level): _For \(2\leqslant l\leqslant 5\), using \(X_{l}\) from theorem 3.2 the following vector word computes the number of \(l\)-paths starting from a node._

\[X_{l}1 \tag{15}\]

Proof.: One can see that this formula ensued directly from equation 7. Indeed, in this case, \(e_{S}=1\) because the tip of a path has only one neighbor. 

It is almost the same for cycle counting at node level except that in this case \(e_{S}=2\) for every node.

**Theorem 3.5** (cycle counting at node level): _For \(3\leqslant l\leqslant 6\), using \(C_{l}\) from theorem 3.1 the following vectorial word computes the number of \(l\)-cycles a node is within._

\[\frac{1}{2}C_{l}1 \tag{16}\]

As \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) can count chordal cycles at edge level, it can count it at node level, and because it only counts one edge in this substructure, the previous formula occurs.

**Theorem 3.6** (Chordal cycle at node level): _The following vectorial word computes the number of couple nodes shared by two triangles_

\[\frac{1}{2}(A\odot A^{2}\odot(A^{2}-(A^{2}>0)))1 \tag{17}\]

To get the graph level counting sentences for all the previous substructures, it is necessary to transcript equation 8 into \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\). The transcription comes naturally.

\[C_{S}(\mathcal{G})=\frac{1}{n_{S}}1^{\mathbf{T}}\begin{pmatrix}C_{S}(\mathcal{ G},1)\\ \vdots\\ C_{S}(\mathcal{G},n)\end{pmatrix} \tag{18}\]

As a consequence, we have the following sentences for counting substructures at the graph level.

**Theorem 3.7** (path counting at graph level): _For \(2\leqslant l\leqslant 5\), using \(X_{l}\) from theorem 3.2 the following sentence computes the number of \(l\)-paths in a graph._

\[\frac{1}{2}1^{\mathbf{T}}X_{l}1 \tag{19}\]

Since there are two tips in the path, \(n_{S}=2\).

**Theorem 3.8** (cycle counting at graph level): _For \(3\leqslant l\leqslant 6\), using \(C_{l}\) from theorem 3.1 the following sentence computes the number of \(l\)-cycles in a graph._

\[\frac{1}{2l}1^{\mathbf{T}}C_{l}1 \tag{20}\]

It is clear that there are \(l\) nodes in an \(l\)-cycle and so \(n_{S}=l\).

**Theorem 3.9** (Chordal cycle at graph level): _The following sentence computes the number of chordal cycles in a graph_

\[\frac{1}{4}1^{\mathbf{T}}(A\odot A^{2}\odot(A^{2}-(A^{2}>0)))1 \tag{21}\]
### Spectral response of \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\)

The graph Laplacian is the matrix \(L=D-A\) (or \(L=\mathrm{I}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\) for the normalised Laplacian) where \(D\) is the diagonal degree matrix. Since \(L\) is positive semidefinite, its eigendecomposition is \(L=U\mathrm{diag}\left(\lambda\right)U^{\mathbf{T}}\) with \(U\in\mathbb{R}^{n\times n}\) orthogonal and \(\lambda\in R_{+}^{n}\). By analogy with the convolution theorem, one can define graph filtering in the frequency domain by \(\tilde{x}=U\mathrm{diag}\left(\Omega(\lambda)\right)U^{\mathbf{T}}x\) where \(\Omega\) is the filter applied in the spectral domain.

**Lemme 3.10**: _Given \(A\) the adjacency matrix of a graph, \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) can compute the graph Laplacian \(L\) and the normalised Laplacian \(L_{n}\) of this graph._

Proof.: \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) can produce \(A^{2}\odot\mathrm{I}\) which is equal to \(D\). Thus it can compute \(L=D-A\). For the normalised Laplacian, since the point-wise application of a function does not improve the expressive power of \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\)[13], \(D^{-\frac{1}{2}}\) is reachable by \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\). Thus, the normalised Laplacian \(D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\) can be computed. 

As in [11], we define the spectral response \(\phi\in\mathbb{R}^{n}\) of \(C\in\mathbb{R}^{n\times n}\) as \(\phi(\lambda)=\mathrm{diagonal}(U^{\mathbf{T}}CU)\) where diagonal extracts the diagonal of a given square matrix. Using spectral response, [11] shows that most existing MPNNs act as low-pass filters while high-pass and band-pass filters are experimentally proved to be necessary to increase model expressive power.

**Theorem 3.11**: _For any continuous filter \(\Omega\) in the spectral domain of the normalised Laplacian, there exists a matrix in \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) such that its spectral response approximate \(\Omega\)._

Proof.: The spectrum of the normalised Laplacian is included in \(\left[0,2\right]\), which is compact. Thanks to Stone-Weierstrass theorem, any continuous function can be approximated by a polynomial function. We just have to ensure the existence of a matrix in \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) such that its spectral response is a polynomial function.

For \(k\in\mathbb{N}\), the spectral response of \(L^{k}\) is \(\lambda^{k}\) since we have

\[U^{\mathbf{T}}L^{k}U =U^{\mathbf{T}}(U\mathrm{diag}\left(\lambda\right)U^{\mathbf{T}} )^{k}U\] \[=U^{\mathbf{T}}U\mathrm{diag}\left(\lambda\right)^{k}U^{\mathbf{ T}}U=\mathrm{diag}\left(\lambda\right)^{k}\]

From Lemma 3.10, \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) can compute \(L\), and thus it can compute \(L^{k}\) for any \(k\in\mathbb{N}\). Since \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) can produce all the matrices with a monotone spectral response and since the function that gives the spectral response to a given matrix is linear, \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\) can produce any matrices with a polynomial spectral response. 

As said before, \(\mathrm{G}^{2}\mathrm{N}^{2}\) inherits all the theorems presented in this section related to \(\mathrm{ML}\left(\mathcal{L}_{3}\right)\). The next section aims to answer 4 main questions through experimental evaluation of \(\mathrm{G}^{2}\mathrm{N}^{2}\):

**Q1**: Is \(\mathrm{G}^{2}\mathrm{N}^{2}\) able to distinguish 1-\(\mathrm{WL}\) or 3-\(\mathrm{WL}\) equivalent pairs of non-isomorphic simple graphs?

**Q2**: Can \(\mathrm{G}^{2}\mathrm{N}^{2}\) learn to count cycles of length 3, 4, 5, 6 and chordal cycles at edge level?

**Q3**: Can \(\mathrm{G}^{2}\mathrm{N}^{2}\) learn low-pass, high-pass and band-pass filters in the spectral domain?

**Q4**: Can \(\mathrm{G}^{2}\mathrm{N}^{2}\) generalize on downstream tasks of graph classification and regression?

## 4 Experiments

For reproducibility, we fixed \(S^{(l)}=b_{\otimes}^{(l)}=b_{\odot}^{(l)}=b_{\mathrm{diag}}^{(l)}\). At each layer, the MLP depth is always 1. The search for hyperparameters is conducted on a grid of learning rates \(\{10^{-4},5.10^{-4},10^{-3}\}\), and of learning rate decays \(\{.8,.85,.9\}\) with a patience of 5.
Q1: Is G\({}^{2}\)N\({}^{2}\) able to distinguish \(1\)-WL or \(3\)-WL equivalent pairs of non-isomorphic simple graphs?

The EXP dataset contains 600 pairs of non-isomorphic 1-WL equivalent graphs [17], while SR25 is composed of 105 different pairs of non-isomorphic 3-WL equivalent graphs [18]. We adopt the evaluation procedure proposed in [18] by comparing the graph representations obtained from each pair using random weights and reporting successfully distinguished pairs. In this experiment, there is no learning, the weights are initialised with different random seeds. We apply a forward of the models on each graph of a pair and then compare the embedding of these graphs. If the norm of the difference of the embedding is less than \(10^{-3}\) we consider that the graphs cannot be distinguished. We report the number of distinguished pairs. For this experiment, \(S^{(0)}=2\), \(F_{n}^{(0)}=1\) since the graph are only structural. For \(l\in\{1,2\}\), we have \(S^{(l)}=F_{n}^{(l)}=16\), and \(S^{(3)}=10\), \(F_{n}^{(3)}=10\). There is no decision layer in this case.

We compare G\({}^{2}\)N\({}^{2}\) to GCN, GAT [19], GIN [5], GNNML1 that are known to be upper bounded by 1-WL. The results of these models are reported under the 1-WL-bounded GNN row in table 1. As expected, models bounded by 1-WL achieve 0% accuracy on both datasets. We also compare to models stricly stronger than 1-WL but weaker than 3-WL ID-GNN [20], NGNN [21], GNNAK+ [22] and GNNML3 [18]. The results of these models are reported under the 3-WL-bounded GNN row in table 1. As expected, models bounded by 3-WL achieve 100% accuracy on EXP. Since CHEBNET [23] is a spectrally designed model, despite its closeness to 1-WL-bounded GNN, it manages to distinguish pairs in EXP having different maximum eigenvalues. Last, we compare G\({}^{2}\)N\({}^{2}\) to PPGN known to be 3-WL equivalent and I\({}^{2}\)-GNN[9]. For SR25, the experiments corroborate theoretical results as I\({}^{2}\)-GNN manages to distinguish all pairs of graphs, while all the other models upper-bounded by 3-WL fail.

Q2: Can G\({}^{2}\)N\({}^{2}\) learn to count cycles of length 3, 4, 5, 6 and chordal cycles at edge level?

For these experiments, we use the RandomGraph dataset [8] with the partitioning: train 1500 graphs, validate 1000 and test 2500. We create the ground truth according to formulas in theorem 3.1. The task is a regression on edges aiming to approximate the edge-level counting of 5 different substructures. For this experiment, \(S^{(0)}=2\), \(F_{n}^{(0)}=1\) since the graph are only structural. We use 3,4,4,5,7 layers respectively for triangle, 4-cycle, chordal cycle, 5-cycle, and 6-cycle counting tasks. For \(l\in\llbracket 1\,,7\rrbracket\), \(S^{(l)}=F_{n}^{(l)}=16\). and at last for the decision layer, we apply 2 fully connected layers of size 32 and 1. The loss is an absolute error.

To keep every metric in the same order of magnitude, we used normalised MAE [9], where the MAE value is divided by the standard deviation of the label. Results are given in table 2. They support theorem 3.1: G\({}^{2}\)N\({}^{2}\) learns an approximation of \(C_{l}\) and thus **can learn to count cycles at edge-level**. The slight increase of the metric for the 5-cycle and the 6-cycle can be explained by the fact that we use much more layers for these tasks at the cost of slower convergence, as \(C_{5}\) and \(C_{6}\) need much more operations.

\begin{table}
\begin{tabular}{l l l} \hline \hline Method & EXP & SR25 \\ \hline
1-WL-bounded GNN & 0\% & 0\% \\ CHEBNET & 87\% & 0\% \\
3-WL-bounded GNN & **100\%** & 0\% \\ PPGN & **100\%** & 0\% \\ G\({}^{2}\)N\({}^{2}\) & **100\%** & 0\% \\ I\({}^{2}\)-GNN & **100\%** & **100\%** \\ \hline \hline \end{tabular}
\end{table}
Table 1: The accuracy on EXP and SR25 datasets denotes the ratio of pairs of non isomorphic respectively 1-WL equivalent and 3-WL equivalent graphs that are separate by the model.
Q3: Can G\({}^{2}\)N\({}^{2}\) learn low-pass, high-pass and band-pass filters in the spectral domain?

For these experiments, we use the protocol and datasets of [18]. It aims to answer Q3 through a node regression problem. The dataset is composed of three 2D grids of size 30x30, one for training, testing and validation. We use \(R^{2}\) score to compare the models' performance. We use 3 layers of G\({}^{2}\)N\({}^{2}\) with \(S^{(l)}=32\) and \(f_{n}^{(l)}=16\) for \(l\in\{1,2,3\}\). Our readout function is the identity over the last vectorial embedding. We finally apply two fully connected layers on the output of the readout function and then use MSE loss to compare the output to the ground truth.

Table 3 reports the comparison of G\({}^{2}\)N\({}^{2}\) to MLP, GCN, GAT, GIN, CHEBNET, PPGN, GNNML1 and GNNML3, citing the results from [18]. As CHEBNET and GNNML3 are spectrally designed, they manage to learn low-pass and high-pass filters, with a metric higher than 0.99. PPGN, GNNML1 and G\({}^{2}\)N\({}^{2}\) are the only non-spectrally designed models that can learn high-pass filters with a metric higher than 0.98. It shows that only a part of G\({}^{2}\)N\({}^{2}\) grammar is needed to obtain high-pass filters. Only G\({}^{2}\)N\({}^{2}\) and the spectrally-designed GNNML3 and CHEBNET reach a metric higher than 0.81 when learning the band-pass filter. This result supports theorem 3.11. The results are not higher than 0.83 because the ground truth band-pass filter used for the experiment is very sharp.

Q4: Can G\({}^{2}\)N\({}^{2}\) generalize on downstream tasks of graph classification and regression?

For a regression task, we evaluate our model on a graph learning benchmark called the QM9 dataset [24, 25]. QM9 is composed of 130K small molecules and consists of 12 graph regression tasks. As in [7], the dataset is split into training, validation and test datasets randomly with a respective ratio of 0.8, 0.1 and 0.1. We use a model that predicts the whole targets (G\({}^{2}\)N\({}^{2}\)(12)).

G\({}^{2}\)N\({}^{2}\) results are compared to those in [9] and in [7] including 1-GNN and 1-2-3-GNN [1], DTNN [25], DeepLRP [8], NGNN, I\({}^{2}\)-GNN and PPGN predicting the twelve targets and one target at a time. The metric is the MAE on the test of the best validation model. The implemented architecture use 3 layers of G\({}^{2}\)N\({}^{2}\) with \(S^{(l)}=f_{n}^{(l)}=128\) for \(l\in\{1,2,3\}\). The readout function is a sum over the components of \(H^{(3)}\), of the diagonal and the non-diagonal parts of \(\mathcal{C}^{(3)}\). Finally, 3 fully connected layers are applied before using an absolute error loss. Since our goal is to study the expressive power of our model, we intentionally use a model that fits on a simple GPU. The setting of PPGN uses the same matrix embedding dimension (PPGN(12sm)) for comparison.

Partial results focusing on the three better models are given in table 4, complete results are given in table

\begin{table}
\begin{tabular}{l l l l} \hline \hline triangle & 4-cycle & 5-cycle & 6-cycle & chordal cycle \\ \hline
3.99e-04 & 4.55e-04 & 2.93e-03 & 3.58e-03 & 1.56e-04 \\ \hline \hline \end{tabular}
\end{table}
Table 2: G\({}^{2}\)N\({}^{2}\) normalised MAE on counting substructures at edge level.

\begin{table}
\begin{tabular}{l l l l} \hline \hline Method & Low-pass & High-pass & Band-pass \\ \hline MLP & 0.9749 & 0.0167 & 0.0027 \\ GCN & 0.9858 & 0.0863 & 0.0051 \\ GAT & 0.9811 & 0.0879 & 0.0044 \\ GIN & 0.9824 & 0.2934 & 0.0629 \\ CHEBNET & **0.9995** & 0.9901 & **0.8217** \\ PPGN & 0.9991 & **0.9925** & 0.1041 \\ GNNML1 & 0.9994 & 0.9833 & 0.3802 \\ GNNML3 & **0.9995** & **0.9909** & **0.8189** \\ G\({}^{2}\)N\({}^{2}\) & **0.9996** & **0.9994** & **0.8206** \\ \hline \hline \end{tabular}
\end{table}
Table 3: \(R^{2}\) score on spectral filtering node regression problems. Results are median of 10 different runs.
5. Note that G\({}^{2}\)N\({}^{2}\) obtains the best results on four targets when predicting the twelve at once, including \(R^{2}\), which is the hardest target to predict for other GNNs. The fact that the convergence does not go further for the other predictions can be explained by the size of our architecture. As shown by table 4, PPGN encounters the same issue when predicting the twelve targets with a small architecture.

For graph classification, we evaluate G\({}^{2}\)N\({}^{2}\) on the classical TUD benchmarks [26], using the evaluation protocol of [5]. Results of GNNs and Graph Kernel are taken from [27]. Since the number of edge and node features is very different from one dataset to another, we use from 3 to 5 layers of G\({}^{2}\)N\({}^{2}\) with \((S^{(l)},f_{n}^{(l)})\in\{8,16,32,64\}^{2}\). The readout function is the same as in regression tasks. We apply three fully connected layers before using a loss function adapted to the task.
to study the expressive power of G\({}^{2}\)N\({}^{2}\), we did not push our architecture to its limits. It should be a part of our future work. The parameter setting for each of the 6 experiments related to this dataset can be found in table 7.

## 5 Conclusion

This paper proposes a GNN design strategy based on the reduction of Context-Free Grammars 1-WL and 3-WL equivalent. This strategy enables to generate and analyse most of the existing models, but also to build new models with a targeted expressive power. In this context, the paper presents G\({}^{2}\)N\({}^{2}\) which is theoretically shown to be as expressive as the 3-WL test, to have strong substructures counting abilities, and to have a powerful spectral expressive power. A large number of experiments covering these properties corroborate the theoretical results. Beyond these results, we are convinced that our design strategy opens the door to models surpassing the 3-WL equivalence, taking as root a language manipulating tensors of greater order as the Tensor Language proposed in [34]. Moreover we are confident that grammars far from the WL equivalence could lead to another generation of GNNs taylored for specific problems.

\begin{table}
\begin{tabular}{l l l l l l l} \hline \hline parameters & MUTAG & PTC & Proteins & NCI1 & IMDB-B & IMDB-M \\ \hline \(f_{n}^{(0)}\) & 7 & 22 & 3 & 37 & 1 & 1 \\ \(S^{(0)}\) & 8 & 2 & 2 & 2 & 2 & 2 \\ number of layer\(=l_{m}\) & 3 & 3 & 3 & 3 & 3 & 3 \\ \(f_{n}^{(l)}l\in\llbracket 1,l_{m}\rrbracket\) & 16 & 32 & 16 & 16 & 32 & 32 \\ \(S^{(l)}\)\(l\)\(l\) & 16 & 32 & 8 & 64 & 32 & 32 \\ decision layer dimension & 256/128/1 & 512/256/1 & 512/256/1 & 512/256/1 & 512/256/1 & 512/256/3 \\ loss & BCEloss & BCEloss & BCEloss & BCEloss & BCEloss & CEloss \\ \hline \hline \end{tabular}
\end{table}
Table 7: G\({}^{2}\)N\({}^{2}\) parameters detail for each dataset in our experiments on TU

\begin{table}
\begin{tabular}{l l l l l l l} \hline \hline Dataset & MUTAG & PTC & Proteins & NCI1 & IMDB-B & IMDB-M \\ \hline WL kernel [28] & 90.4\(\pm\)5.7 & 59.9\(\pm\)4.3 & 75.0\(\pm\)3.1 & **86.0\(\pm\)1.8** & 73.8\(\pm\)3.9 & 50.9\(\pm\)3.8 \\ GNTK [29] & 90.0\(\pm\)8.5 & 67.9\(\pm\)6.9 & 75.6\(\pm\)4.2 & 84.2\(\pm\)1.5 & 76.9\(\pm\)3.6 & 52.8\(\pm\)4.6 \\ DGCNN [30] & 85.8\(\pm\)1.8 & 58.6\(\pm\)2.5 & 75.5\(\pm\)0.9 & 74.4\(\pm\)0.5 & 70.0\(\pm\)0.9 & 47.8\(\pm\)0.9 \\ IGN [6] & 83.9\(\pm\)13.0 & 58.5\(\pm\)6.9 & 76.6\(\pm\)5.5 & 74.3\(\pm\)2.7 & 72.0\(\pm\)5.5 & 48.7\(\pm\)3.4 \\ GIN [5] & 89.4\(\pm\)5.6 & 64.6\(\pm\)7.0 & 76.2\(\pm\)2.8 & 82.7\(\pm\)1.7 & 75.1\(\pm\)5.1 & 52.3\(\pm\)2.8 \\ PPGNs [7] & 90.6\(\pm\)8.7 & 66.2\(\pm\)6.6 & 77.2\(\pm\)4.7 & 83.2\(\pm\)1.1 & 73.0\(\pm\)5.8 & 50.5\(\pm\)3.6 \\ Natural GN [31] & 89.4\(\pm\)1.60 & 66.8\(\pm\)1.79 & 71.7\(\pm\)1.04 & 82.7\(\pm\)1.35 & 74.8\(\pm\)2.01 & 51.3\(\pm\)1.50 \\ WEGL [32] & N/A & 67.5\(\pm\)7.7 & 76.5\(\pm\)4.2 & N/A & 75.4\(\pm\)5.0 & 52.3\(\pm\)2.9 \\ GIN+GraphNorm [33] & 91.6\(\pm\)6.5 & 64.9\(\pm\)7.5 & 77.4\(\pm\)4.9 & 82.7\(\pm\)1.7 & 76.0\(\pm\)3.7 & N/A \\ GSNs [27] & **92.2\(\pm\)7.5** & 68.2\(\pm\)7.2 & 76.6\(\pm\)5.0 & 83.5\(\pm\)2.0 & **77.8\(\pm\)3.3** & **54.3\(\pm\)3.3** \\ G\({}^{2}\)N\({}^{2}\) & 92.0\(\pm\)4.3 & **71.8\(\pm\)6.7** & **77.8\(\pm\)3.2** & 80.2\(\pm\)2.1 & 76.8\(\pm\)2.8 & 54.0\(\pm\)2.93 \\ \hline \hline \end{tabular}
\end{table}
Table 8: Results on TUD dataset. The metric is accuracy, the higher, the better.