G$^2$N$^2$ : Weisfeiler and Lehman go grammatical
Authors: Jason Piquenot
Aldo Moscatelli
Maxime Berar
Pierre Héroux
Romain Raveaux
Jean-Yves RAMEL
Sébastien Adam
Venue: ICLR 2024 poster (2024)
Keywords: Machine learning
GNN
Graph Learning
Primary area: general machine learning (i.e., none of the above)

Abstract: 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 the matricial language 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.

G2 WEISFEILER AND LEHMAN GO GRAMMATICAL
Jason Piquenot
Aldo Moscatelli
Maxime Bérar"
Picrre Héroux
Jean-Yve Rame
Romain Raveaux!
Sébastien Adam"
ABSTRACT
This paper introduces framework for formally establishing connection between 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 contain redundancies in their rules and variables, we present a grammar reduction scheme. By applying this stralegy, we define CFG that conforms to the third-order Weisfeiler-Tehman (3-WI.) test using MATLANG. From this 3-WL CFG, we derive a GNN model, named G2N2, which is provably 3-WL compliant. Through various experiments, we demonstrate the superior efficioncy of G compared to other 3-WL GNNs across numerous downstrcam tasks. Specifically, experiment highlights the benefits of grammar reduction within our framework.
INTRODUCTION
In the last few years, the Weisfeiler-Lehman (WL) hierarchy, based on the eponymous polynomial-time isomorphism test (Lehman and Weisfeiler (1968)), has been the most common way to characterise the expressive power of Graph Neural Networks (GNNs) (Morris let al. (2019) Bodnar et al. (2021b ab; Zhang et al. (2023b)) ). A founding result was the proof that M Message Passing Neural Networks (MPNNs) [Gilmer et al. (2017): Wu et al. (2020) at most powerful as the first-order WL test (1-WL) (Morris et al. (2019) Xu et al. (2019)): ). As a consequence of this result, many subsequent contributions have focused on going beyond this 1-WL, limit, reach
expressive GNNs. For instance, subgraph-based
GNNs [Chen et al. (2020); ZZhang and Li (2021 ;: Zhao et al. (2022) succeed to surpass 1-WT. expressive power
are still bounded by 3 WL (Frasc et al. (2022))
One way to ensure k-WL expressive power is to mimic one iteration of the k-WL test (Maron al. 2019ah) for each GNN layer. Taking as root the colouring and hashing steps of the W- algorithm, Maron et al. (2019a) shows that k-IGN, based on the basis of equivariant operators defined for IGN (Maron et al. (2019b)),
as powerful the k-WL test. Since k-IGN works on k-th order tensors and since the cardinal of the basis is equal to the 2k-th Bell number, is limited in practice by both the layer input memory consumption and the cardinal of IGN operator basis, even for & = 3 (Li et al. (2020)). Concurrently, Provably Powerful Graph Network (PPGN) was also proposed in Maron et al. (2019a). It able to mimic the second-order Folklore WL test (2-FWIJ) colouring and hashing steps with MLPs that are coupled toget with matrix multiplication. Since PPGN only relics on matrices, is more tractable 3- WL architecture than 3-IGN (Zhang et al. (023a )
Taking an algebraic point of view, the groundbreaking paper Geerts 2020g reformulates the 1-WT, and 3- tests languages based on specific subsets of algebraic operations applied on the adjacency matrix. These fragments
the matrix language MATLANG (Brijder
et al. (2019)) called ML (Cn) and ML (Cx) are shown to be as expressive as 1-WL and WL
Geertt (2020]). ). Derived from this result, model called GNNMLI was proposed in Balcilan
"LITIS Lab, Universily of Rouen Normandy, France
LLIFA Lab, Universily of Tours, France
'knwwn equivalent 3. WL test (Huang and Villar (0211)

---

ct al. 2020)). GNNML1 is proven to be 1-WL equivalent since it is able to generate any sentence of ML (C1). A more expressive model called GNNML3 was proposed in the same paper. It is only shown to be more expressive than 1-WL. This is due to the lack of systematic procedure of deriving a GNN model from a given language fragment.
In this paper, we leverage this bottleneck by proposing a generic methodology to produce a GNN from any fragment of an algebraic language, opening new way to ensure expressiveness. The rationale behind our framework to instantiate a language fragment by a reduced of generative rules, translated into layer components of a GNN. Starting from the operations set Cg. we build an exhaustive Context- Grammar (CFG) able to generate ML (Cz). This CFG is reduced to remove unnecessary operalions among the rules while keeping the equivalence with 3-W From the variables of this reduced CFG, GNN inputs are easily deduced. Then, the rules of the CFG determine the GNN layers update functions. As a result of this methodology, we propose a new model called Grammatical Graph Neural Network (G2N²) that is provably 3-WL.
The contributions of this work are the following (i) A generic framcwork to design a GNN from any fragment of an algebraic language; (ii) The instantiation of the framework ML (L3) resulting in G2N?, a provably 3-WL GNN; (iii); An experimental validation of the set of rules; (iv) Numerous experiments demonstrating that G outperforms existing 3-WT. GNNs on various downstream tasks.
The paper is structured as follows. Section 2 introduces the necessary background, by defining MATLANG, its link with WL and CFGs. Section 3 describes our framework and presents the resulting G2 architecture, which is experimentally evaluated in section 4
2 FROM MATLANG AND WEISFEILER-LEHMAN TO CONTEXT-FREE GRAMMARS AND LANGUAGES
Let G = EV.E) be an undirected graph where V = [1.n] is the set of n nodes and & C V x V the set of edges. The adjacency matrix A E {0, 1]"xa represents the connectivity of G.
Definition 2.1 (MATLANG (Brijder et al. 2019
MATLANG is a matrix language with an allowed operation set {+, O, T Tr, diag, 1, f) denoting respectively matrix addition, matrix and element-wise multiplications, transpose and trace computations, diagonal matrix creation from vector, column vector of generation, scalar multiplication, and element-wise function applied on a scalar, a vector or a matrix. Restricting the set of operations to subset L defines fragment of MATLANG denoted ML (C). s(X) E R is a sentence in ML (C) if it consists of consistent consecutive operations in L, operating on given matrix X, resulting in scalar value. As an erample, s( a(X) 1T (x² @ diag (1)) Il is sentence of ML (f:, T diag, @}) computing the trace of x².
Equivalences between ML (L, and ML (Cg) with 41 = {, T II, didg) Lg L3= (: T L, diag, ) and respectively the 1-W,, and 3-WL, tests are shown in Geerts (2020): two graphs are indistinguishable by the 1-WL (resp. 3- 3-LL) test if and only if applying any sentence of ML (21) (resp. ML (Lg)) to their adjacency matrices gives the same scalar. Adding (+, f} does not improve the expressive power of the fragment |Geerts| (2020)).
Transposed in Machine Learning context, a MATLANG-based GNN will inherit the 3-WL expressive power of ML (Cg) if it able generate any sentence of the fragment while learning the downstream task. To reach this objective, we will instantiate the fragment as Context Free Language, entirely described by a set of production rules?]
Definition 2.2 (Context-Free Free Grammar and Language)
A Context-Free Grammar (CFG) G is a 4-tuple (V. Σ, R, S) with V a finite set of variables, Σ finite set of terminal symbols, R finite set of rules V + (V U')", S a start variable. R completely describes a CFG with the convention that S is placed on the top left.
FFigure in appendix illustrates the process of sentence generation from a grammar.
2

---

B is Context-Froe Language (CFL) if there exists CFG G such that B = L(G) = fw, En and + w) where S + w denotes that S can be transformed into by applying an arbitrary number of rules in G.
3 FROM ML. (Lz) TO THE 3-WL G2N2
In this section, the proposed generic framework is described and instantiated on the ML (Lg) fragment generate our GºN² model. As shown by Figure [ 3 steps are involved: (1) defining the exhaustive CFG that generates the language, (2) reducing the exhaustive CFG, (3) translating the variables and the rules of the reduced CFG into GNN input and model layer. To keep the expressive power of the language at each step, the equivalence between the successive representations must be ensured.
GRV layer
Exheuative
Language frngmeent
MUN
K- (k k:0lo/rrggP
4-+ AFR M + [A (. NW1
(ara (0J/MM/////66/ 252.
Figure 1: Overview of the proposed framework instantiated on ML (Cz).
3.1 FROM ML (La) TO THE EXHAUSTIVE CFG G
The first step of the framework translates the language fragment into an exhaustive CFG (variables, terminal symbols and rules). For MT. (Lg), the variables of the exhaustive CFG denoted Gcg are defined using the following proposition proved in appendix A.2
Proposition 3.1
For any square matrir of size n², operations in L3 can only produce square matrices of the same size, row, or column vectors of size n or scalars.
In the context of our study, as in Geerts 2020
ML (C3) is applied on the adjacency matrix. Thus, proposition 3.1 ensures that Gc, variables are restricted lo square matrix (M), column vector (Vc), row vector (V,) and scalar (S). Once the variables defined, the production rules of Gc, are obtained by enumerating all possible operations in MT. (Lg) that produce such variables. The rulc M + A is added in order to be compliant with Geerts (2020). All the rules composing Gr, are synthesised in equation 1 where denotes the classical OR operator since a variable can be produced by different rules. They fully characterise the CFC
The following theorem ensures that the language generated by Gc, is ML (Cz). Thus Gc, is as expressive as ML (Cz).
Theorem 3.1
For Gc, defined by
S + (V))(V))) diag (8) SS ( S)
(1)
V. + (V. V.) MV. (V,) [ V.8 1
V, + (V, O V.) V,M (V2)T SV,
M +
MM (M)T diag (V.) (V))())) A
have
L(G2,) = ML (C₂).
Elements that are not variables in the rule set are said be terminal symbols.
3

---

The full proof is provided in appendix (A.2) Its idea is the following. As any operation in the rules of G2, belongs to L3, it is clear that L(Gc,) ML The reciprocal inclusion proven by induction over the number ML (Lz) operations.
Given the results of theorem 3.1 the next step reduces the CFG by exploiting the redundancies in the exhaustive set of rules and variables.
3.2 FROM G2 TO R,
An example of redundancy can be observed in the following proposition proved in the appendix (see A.2
Proposition 3.2
For any square matrix M, column vector Va and row vector V,, we have
M @ (Ve V,) diag (V:) M Mdiag (V₂)
The following theorem guarantees that the following reduced grammar preserves expressiveness.
Theorem 3.2 (ML. (Lg) reduced CFG) Let r, be defined by
Ve + MV. 1 M + (M O M) MM diag (V.) | A
(2)
r-G is as expressive as GC
Proof. For any scalar S, S", since diag (5), S @ S" and S S' produce a scalar, the only way to produce scalar from other variables is to pass through vector dot product. Hence the scalar variable S and its rules can be removed from Gc, without loss of expressive power.
Since diag (V) w O w for any vector v, w. the vector Hadamard product can be removed from the vector rules. Proposition 3.2 allows to remove V.V, from the rules of M since the results of subsequent mandatory operations MM or MV, can be obtained with other combinations. At this stage, the following intermediate CFG i-Gz, is as expressive G since it can compute any vector of G
V. + MV. (V,)T) 1
V, V,M (V.)
M - (M o M) MM (M)T | diag (V.)
Since the remaining M rules preserve symmetry, (M)T, the variable V,, and its rules can be removed. It conducts to r-G2, defined in equation 2
From these two steps, the resulting CFG r-G2, possesses the expressive power of the fragment ML (Ca). The next step is a translation of r-Gc, into a GNN layer.
3.3 FROM R-GC, TO G LAYER MODEL
In r-G(Lz), any vector V. matrix M is produced by applying sequence of rules on A and 1. As a consequence, every matrix or vector can be attained through an iterative rule selection procedure using matrix and vector memories that store intermediate variables. Figure describes this procedure: each iteration starts by choosing a rule r-G(E3) before selecting corresponding inputs in the memories. Applying the selected rule produces matrix or new vector, which is added to the appropriate memory.
Translating this iterative procedure into GNN based on sequence of layers requires memory management strategy and a selection mechanism for both rules and inputs, while taking into account learning issues related downstream tasks.
4

---

The matrix memory aims at storing the variables M producod by succossive applications of r-G(Ls) rules. This memory is represented by a three order tensor C() where produced matrices (i.e. edges embeddings in GNN context) are slacked across layers on the Chird dimension. In the same way, the vector memory is dedicated to the variables V. that correspond to nodes embeddings. It is as a matrix H() where produced vectors are stacked on the second dimension. C(O) and H are the input of the I-th GNN layer which produces c(++) and H(++1) as output, as depicted in Figure 3 describing G layer. While the memory of the itcrative procodure grows with cach iteration, a tractable GNN architecture constrains the stacking dimension to be set to a given value at each layer.
In order to mimic the rule selection procedure of Figure 2 G layer applies selection among the outputs produced by all the rules. Such a strategy enables to compute in parallel several occurencces of any rule with multiple imputs. Hence, parameterised quantities .idiiigg of the rules (M M), (MM), diag (Vo), MV, are computed in parallel taking as input linear combination L2 of slices of (C) and slices of H(), These linear combinations are able to select among inputs (()) and HU) through a learning paradigm.
Both the matrix rules outputs and the tensor (() (obtained through skip connection which guarantees the memory persistence) are fod to MLP,, M that produces the output tensor C(++1) with selected third dimension size 5(+1). This MLP allows in the same time to simulate the rule selection, to compress the matrix output of the layer to a fixed size and to learn a point wise function for solving specific downstream tasks. It relates to the set of operations {+, x. fl of M LANG and does not modify the expressive power (Geerts
2020); Maron
et al. (0019a)) The output H0+1) is provided similarly through MLPv. Figure describes the whole model of a G2N² layer.
Formally, the update equations are:
c((+1) MLP M (11 (L2 (|C ( (ddaago)) H(+1)= = MLPv, (LS((()) -L)
(3)
(4)
where || is the concatenation. MLPM M and MLPv, vv are learnable MLPs, and L; are learnable
linear blocks acting on the third dimension of c(t) or the second dimension of 10;;; 1
RSSO + RA Lg,1 IR + R Lg RsS RR avv, L6 R + R ddiax, La R
(1)
R
R RMM MLPMM Ms : IR 08 tbo
(1)
@ +bama ( B and MLPv. RR 4b (
- R (
3.4 G2N2 ARCHITECTURE AND ITS EXPRESSIVE POWER
Figure 4 depicts the global N2 architecture. The inputs are (0)) and C(O), H of size
fm +1 is the feature nodes matrix concatenated with 1. C [n*nx(f,+1) is stacking on the third dimension of the adjacency matrix A and the extended adjacency tensor F. of size x Sex where fa is the number of edge features.
After the last layer, permutation equivariant readout functions are applicd on both Hena) and the diagonal and off-diagonal components of ((lms)) Readout outputs are then fed to a dedicated decision layer.
Iteration
Ineration k
Iteration k
14) Oripaitstoong stonge
(1) Pule scintiin
(3) Inpots sclerion
(3) Ralk compstaation
(4) Curpar strnige
23 Tole adoctorn
A A
Mia
Jusl Vi or Al
A A
disg(V))
AP1
or
Matrix nummrry Vixtor nemorry
Matrix nemory Vodio mumory
Makris menzory Veeter mensAy
Figure 2: 4-step iterative procedure (1) Rule selection (2) Inputs selection: inputs relative to the chosen rule are selected from matrix and/or vector memories (opaque matrices) (3) Rule computation (4) Output storage: the produced output is stored into its relative memory.
5

---

50
L1
50
L2
g(+1)
C
50
Lg
b
MLP
M
C
50
L4
S0
bas
L5
(ri tu
fi
bdiag
L6
diag
((+1)
(3)
Jn
MLP
(7())
L7
H
Figure 3: I1-I, combine the S()) slices of ( into 2bg 2b. and YaV, matricos. L In combine the fh columns of ( into baiag and bMv, vectors. From the outputs of L -L7, multiple occurrences of (-G(C3) rules (M O M), (MM), ),, (diag(V.) and (MV)) are computed. The obtained outputs and the layer inputs are fed to MLP M and MLPv, providing the layer outputs C(++1) and H(++)).
C
diag ((k)
Matrix readout function
n
le
offdiag (*)k)
n
Output
Input
Vector readout function
H
GºN layer
Gº Inyer k
H kk)
n
fn
Decision
Figure 4: Model of G architecture from the graph to the output. Each layer updates node and edge embeddings and readout functions are applied independently on (k) and the diagonal and the non-diagonal clements of C(R).
Theorem 3.3 (Expressive power of G#N²) N is able to produce any matriz and vector of L(r-Ges). It is expressive as 3- WL.
Proof. We show that G at layer can produce all matrices and vectors r-G produce, after iterations. is true for 1 1. Indeed, at r-G2, first iteration, we obtain the matrices I, A, 2 and the vectors 1 and A1. Since any of (C(0)) for E [1 5| is a lincar combination of and I, G2N² can produce those vectors and matrices in one layer.
Suppose that there exists >> 0 such that G2N2 can produce any of the matrices and vectors Ge, can after iteeations. We denote by A, the of those matrices and by Vi the set of those vectors. At the 1-th iteration, we have A (MON, MN, diag (V.) J,, E A, E V) and V = {MV. E Ar, V. ViJ- Let M, N E A, and V. E V, then by hypothesis G²N² can produce M, N at layer L. Since L produces at least two different linear combinations of matrices or vectors in respectively A₁ and V/, MN, M @ N, MV. and diag (V,) are reachable at layer 1 1. Thus A+t1 is included in the set of matrices G can produce at layer I and V441 is included in the set of vectors G2N² can produce at layer /+1 1.
3.5 DISCUSSION N IN THE 3-WL GNN LITERATURE
Positioning w.r.t Maron et al. (0019a) From PPGN layer description (see Figure 2 of Maron et al. (2019a)) can build the following CFG:
M MM diag (1) A
(5)
6

---

where M - diag (1) and M A represent inputs of the architecture for G²N?. Compared to GG Ve variable and M - M O M, diag (Vc) and MV. rules are missing. As a consequence, PPGN 3-WL expressive power is not formally inherited from ML (Cz). As stated in the introduction, it relies on PPGN ability to mimic 2-FWI, colouring and hashing steps. Its capacity to implement the colouring step relies on MLP universality. It explains that PPGN can approximate the missing rules of g. To guarantee such an approximation, certain width and depth for MLP are needed. G2N² does not suffer from these computational constraints since it only needs to provide linear combinations as arguments of the operations.
3-IGN processes on sets of third order tensors. As a consequence, it cannot be described by a CFG derived from ML (fz). However, we can connect our approach with k-IGN. For k-IGN, the expressive power related
MLPs and to the basis of lincar equivariant operators defined in Maron et al. (2019b). In some ways, these operators can be linked to the algebraic operations of our framework. An example of such a link is given in appendix A.33 for 2-IGN
Positioning w.r.t Balcilar et al. (2021 In appendix A.1 we show that GNNMLI (Blliiarr et al. (0021 can be seen as the resulting GNN of our framework applied on ML (C1).
Concerning GNNML3, CFG can also be deduced from its layer
V. ... C. VV
where the matrices C,....,C are defined using the adjacency matrix, exponential pointwise function, and matrix Hadamard product. As some rules and variables are missing compared to L. cannot formally inherit the expressive power of ML (Cg).
4 EXPERIMENTS
This section is dedicated to the experimental validation of both the framework and G2N2. It answers 4 questions Q1-Q4. Q1 concerns the validation of the reduced grammars. Q2
and Q3 relate to performance of G on downstream regression, pngression/caassifaatiin /classification tasks. Q4
concerns the model spectral ability. Experimental settings are delailed in appendix C
Q1: Is THE REDUCTION OF GRAMMAR RELEVANT AND OPTIMAL?
This experiment aims at investigating the impact of the CFG reduction scheme through the comparison of different models built using G2 (see Figure in appendix A i-Ge, c. (see Figure 10 in appendix A and r-Ge, (see Figure 3). The comparison is completed by an ablation study the aim of which is to investigate the importance of each rule of r-G
We use a graph regression benchmark called QM9 which is composed of 130K small molecules (Ramakrishnan al. (2014); Wu al.] (2018)). For this study, we focus on the regression target R2, which is known to be the most difficult to predict. As in Maron et al. (2019a), the dataset randomly split into training, validation, and test sets with a respective ratio of 0.8, 0.1 and 0.1. The edge and vector embeddings are always of size 32.
The results are presented in Figure] where each model represented in 2-D space using the Mean Absolute Error (MAE) of the best validation model on the test set and the number of parameters of the model. These results corroborate the theoretical results of section 3. discussed in greater detail in appendix A.5 the MAE scores are comparable for G(Ca), (G) and (C,) while the number of parameters is divided by 2 when reducing from G(Lg) to r-G(Lg). As expected, removing rules in r-G(C3) leads to drop of MAE performance. It also offers insights into the weights of each operation in the model and enables informed pruning of the GNN if the expressiveness is not required.
Q2: DOES G PERFORM BETTER THAN OTHER WL GNNs FOR REGRESSION?
For this second question, we also use the dataset QM9, but we consider the 12 regression targets. The dataset. randomly split into training, validation, and test sets with the same ratio as in Q1. The experimental settings are detailed in appendix C GºN² results are compared to those in Huang et al. (2023); Maron et al. (2019a) including 1-GNN and
7

---

-G1231 13 6 12agg4ie
0.8
0.7
Giaa MMM dag
00.6
Ir-Oles1 IM MY
(-.0(a)) (d
Inculaa (M40)) Ir Cal J
[-G porcs)
0.4
330 400
250 k
500 350
600 k
Number of parameters
Figure 5: Comparison of model size and MAE performance the QM9 R target for GNNs derived from G(Lz). Each GNN model denoted by its set rules. Over-reduced grammar from (C3) denoted with 1, whereas denotes the addition of a rule to the set.
1-2-3-GNN Morris al. 2019
DTNN Wu et al. 20188 DeepLRP (Chen et al. 2020 I--GNN Huang et al. (2023)) and PPGN Maron et al. (2099a) The metric the MAE of the best validation model on the test set. The mean
NGNN Zhang and Li 2021
epoch duration is measured on the same device for comparison between G2N2 and PPGN.
As in Maron et al. (2019a), we made two experiments. The first one consists in learning one target at a time while the second learns every target at once. In the first experiment, we have 5 //6'
64 and in the second 5(0) / 32. Partial results focusing on the two best models are given in Table ] Complete results and experiment, settings are given in appendix C In both cases, G obtains the best results while learning faster.
Table 1: Results QM9 dataset focusing on the best methods. On the left part, each target learned separately while on the right side all targets are learned the same time. The metric is MAE, the lower, the better. Complete results can be found in Table
Target
PPGN
G2N²
PPGN G
/
0.0934
0.0703
0.231
0.102
0.318
0.127
0.382
0.196
Chomo
0.00174
0.00172
0.00276
0.0021
Cumo
0.0021
0.00153
0.00287
0.00211
AC
0.0029
0.00253
0.0029
0.00287
R²
3.78
0.342
16.07
1.19
ZPVE
0.000399
0.0000951
0.00064
0.0000151
U
0.022
0.0169
0.234
0.0502
0.0504
0.0162
0.234
0.0503
II
0.0294
0.0176
0.229
0.0503
G
0.024
0.0214
0.238
0.0504
C. 0.144
0.0429
0.184
0.0707
T/ ep
129 S
98
131 s
57
Q3: DOES G PERFORM BETTER THAN OTHER 3-WL. GNNs FOR CLASSIFICATION?
For graph classification, evaluate G2 on the classical TUD benchmark Morris et al. 2220 ), using the evaluation protocol of Xu et al. (019)). Results of GNNs and Graph Kernel taken from Bouritsas et al. (2022. Since the number of node and edge features is very different from one datasct to another, the parameter scttings for each of the experiments
related to these datasets can be found in Table 5 of appendix C Partial results focusing on
N2N² performance are given in Table 2 Complele results can be seen in Table of appendix G2 achieves better than rank for five of the six datasets.

---

Table 2: Results of G on TUD dataset compared to the best GNN competitor. The rank of N² within GNNs is in parentheses. The metric is accuracy, the higher, the better. Complete results can be seen in Table 6
Dataset
Gº
rank
Best GNN competitor
MUTAG
92.5++5.5
1(1)
92.247.5
PTC
6..3:16.3
1(1)
68.217.2
Proteins
80.113.7
1(1)
77.414.9
NCIL
82.810.9
5(3)
83.512.0
IMDB-B
76.8+288
3(3)
77.8+3.3
IMDB-M
54.0#+2.9
2(2)
54.343.3
Q4: CAN G LEARN BAND-PASS FILTERS IN THE SPECTRAL DOMAIN?
As shown in Balcilar et al. 2020 the spectral ability of GNN and particularly its ability to operate band-pass filter is an important property of a model for certain downstream tasks. In order to assess the spectral ability of G2N² and answer Q4, we use the protocol and node regression dataset of Balcilar et al. (2021) R score is used to compare performance.
Table 3 reports the comparison of GPN2 to CHEBNET (Hammond et al. (2011)., PPGN and GNNML3, citing the results from Balcilar et al. (2021). CHEBNET and GNNML3 are spectrally designed and manage to learn low-pass, high-pass, and band-pass filters. For the three filter types, G2 reaches comparable performance. In appendix B thcoretical analysis shows that 3- WL GNN is able to approximate any type of filter.
As shown in the (able, PPGN fails to learn band-pass filters. This result which contradicts the previous theoretical result is related to memory and complexity issues. Hence, as explained before, PPGN needs a deeper and wider architecture for this task that can not be reached for 900 node graphs (Balcilar et al. (2021)).
Table 3: R score spectral filtering node regression. Results median of 10 runs.
Method
Low-pass
High-pass
Band-pass
CHEBNET
0.9995
0.9901
0.8217
GNNML3
0.9995
0.9909
0.8189
PPGN 0.9991
0.9925
0.1041
GºN²
0.9996
0.9994
0.8206
CONCLUSION
Designing provably expressive GNNs has been the target of many recent works. In this paper, we have proposed new theoretical framework for designing such models. Taking as input a language fragment, i.e. a set of algebraic operations, the framework uses reduced Context Free Grammars to drive the generation of graph neural architectures with provable expressive power. The framework provides insights about the importance of algebraic operations in the resulting model, as shown by the experimental grammar ablative study. Such results can be useful for improving the performance vs. computational cost trado-off for given task.
Through the application of the framework to ML (Cg) fragment, the paper also proposed the provably 3- G model. In addition to these theoretical guarantees, G2N2 also shown to be ellicient for solving graph learning downstream tasks through several experiments on regression, classification and spectral filtering benchmarks. In all cases, G²N² outperforms 3-WL GNNs, while being more tractable.
Beyond these results, we are convinced that our contributions open the door to the design of models surpassing 3-W WL, taking as root language manipulating tensors of greater order
Geerts and Reutter (2022)). ). Moreover, the framework not limited to GNN models since many other learning paradigm can be modeled with algebraic languages.

---

ACKNOLEDGEMENTS
The authors acknowledge the support of the French Agence Nationale de la Recherche (ANR) under grant ANR-21-CE23-0025 (CoDeGNN project). The authors acknowledge the support of the ANR and the Région Normandie under grant ANR-20-THLA-000 (HAISCoDe project).
REFERENCES
M. Balcilar, G. Renton, P. Héroux, B. Gaüzère, S. Adam, and P. Honeine. Analyzing the expressive power of graph neural networks in a spectral perspective. In International Conference on Learning Representations, 2020.
M. Balcilar, P. Héroux, B. Gauzere, P. Vasseur, S. Adam, and P. Honeine. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning, pages 599 608. PMLR, 2021.
C. Bodnar, F. Frasca, N. Otter, Y. Wang, P. Lio, G. F. Montufar, and M. Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34:2625-2644 2021a.
C. Bodnar, F. Frasca, Y. Wang, N. Outer, G. F. Montufar, P. Lio, and M. Bronstein. Weisfeiler and lehunan go topological: Message passing simplicial networks. In International PMLR, 2021b.
Conference on Machine Learning, pages
G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(1):657-666 668, 2022.
R. Brijder, F. Geerts, J. V. den Bussche, and T. Weerwag, On the expressive power of query languages for matrices. ACM Trans. Dalabase Syst., 44(4):15:1 15:31, 2019.
T. Cai, S. Luo, K. Xu, D. He, T,y, Liu, and Wang. Graphnorm: A principled approach to accclerating graph neural network training. In International Conference on Machine Learning, pages 1204-1215. PMLR, 2021.
7. Chen, T.. Chen, S. Villar, and Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383 10395, 2020.
P. de Haan, T. S. Cohen, and M. Welling. Natural graph networks. Advances in Neural Information Processing Systems, 33:3636-3665 3646, 2020.
S. S. Du, K. Hou, R. R. Salakhutdinov, B. Poczos, R. Wang, and K. Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, 32, 2019.
F. Frasca, B. Bevilacqua, M. M. Bronstein, and H. Maron, Understanding and extending subgraph gnns by rethinking their symmetries. In Advances in Neural Information Processing Systems, 2022.
F. Geerts. On the expressive power of lincar algebra on graphs. Theory of Computing Systems, Oct 2020.
F. Geerts and J. L. Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference Learning Representations, 2022.
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages PMLR, 2017.
D. K. Hammond, P. Vandergheynst, and R. Gribonval. Wavelets on graphs via spectral graph theory. Applied and Compulational Harmonic Analysis, 30(2):129 150, 2011. ISSN 1063-5203. doi: https:///oii.nn (tt.:ii.org...1016////11 acw..///..ch............
10

---

N. T. Huang and S. Villar. A short tutorial the weisfeller-lcman test and its variants. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8533 8537. IEEE, 2021.
Y. Huang, X. Peng, J. Ma, and M. Zhang. Boosting the cycle counting power of graph neural networks with I--GNNs. In The Eleventh International Conference on Learning Representations, 2023.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, 2017.
S. Kolouri, N. Naderializadeh, G. K. Rohde, and H. Hoffmann. Wasserstein embedding for graph learning. Xiv preprint or arXim:2006.094 2020.
A. Lehman and B. Weisfeiler. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technickken Technicheskaaa Informalsiya, 2(9):12-11) 16, 1968.
P. Li, Y. Wang, H. Wang, and J. Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Newral Information Processing Systems, volume 33, pages 4465 4478. Curran Associates, Inc., 2020.
H. Maron, H. Ben- HamuHam H. Serviansky, and Y. Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019a.
H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In International Conference Learning Representations, 2019b.
C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. F. Lenssen, G. Rattan, and M. Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602 4609, 2019.
C. Morris, N. M. Kriege, F. Bause, K. Kersting, Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In 1CML 2020 Workshop on Groph Representation Learning and Beyond (GRL+ 2020), 2020.
R. Ramakrishnan, P. O. Dral, M. Rupp, and O. A. Von Lilienfeld. Quantum chemistry structures and propertics of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
N. Shervashidze. P. Schweitzer, E. J. Van Lecuwen, K. Mchlhorn, and K. M. Borgwardt. Weisnailer-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Z. Wu, B. Ramsundar, E. N. Feinberg, J. Gomes, C. Geniesso, A. S. Pappu, K. Leswing, and V. Pande. Moleculenct: benchmark for molccular machine learning. Chemical science, (2):513 530, 2018.
Z. Wu, Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip. A comprehensive survey on graph neural networks. IEEE transactions neural networks and learning systems, 32 (1):4-24, 2020.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
B. Zhang, C. Fan, S. Liu, K. Huang, X. Zhao, J. Huang, and Z. Liu. The expressive power of graph neural networks: A survey. arXiv preprint 20X.:2300..08255, 2023a.
B. Zhang, G. Feng, Y. Du, D. He, and L. Wang. A complete expressiveness hicrarchy for subgraph gnns via subgraph weisfeiler-lehman tests. In International Conference on Machine Learning, 2023b.
M. Zhang and P. Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34:15734-15741 2021.
11

---

M. Zhang, Z. Cui, M. Neumann, and Y. Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018
L. Zhao, W. Jin, L. Akoglu, and N. Shah. From stars to subgraphs: Uplifting any GNN with local structure awarcness. In International Conference on Learning Representations, 2022.
12

---

This appendices provide additional content to the main paper GºN2; Weisfeiler and Lehman go grammalical.
A
CFG AND GNN
A.1 FROM ML (C1) TO 1-WL GNN
In this subsection, the reduction framework described in section ML (f1) as shown by Figure
is applied to the fragment
CNN lover
Echaustive CFG
Targuage Trageen
G4,
Rechnced CHG bG
(tata deald) Pra
Kl4e)) 361 (> 3
lpar (6)) 99%
Werk LAVia
17 MMD3O MAN
Figure 6: Overview of the proposed framework instantiated on MT. (L1).
To determine the variables the CFG, the following proposition is necessary.
Proposition A.1
For any square motrir of size n², operations in &, can only produce square malrices of size n², row or column vectors of size n or scalars.
Proof. Let M be a square matrix of size n², we first need to prove that & can produce square matrices of size n², row and column vectors of size n and scalars.
Yet = 1(M) is a column vector of size n, T is a row vector of size n, ( 1 is a scalar and M is square matrix of size n².
Then let N E RRxn, v E IR", w E (R")", and & E R be words of ML (L,), we have
M N E Raxn
M. E RR" (v) E RR"
w. M E (R")"
W. R (ww) R
Raxn
TT E (R"") 8 w E (R")*
MT Raxn
wT E R
diag (s)
diag (v) E gaxn
1 (M) E R
8 . 5 1(s) R
E R
Since this is an exhanstive list of all operations ML (C,) can produce with these words, we can conclude.
Theorem A.1 (ML (C1) reduced CFG The following CFG denoted r-Ge, is expressive 1- WI.
V. + diag (V.) V. AV, |
(6)
Proof. Proposition A.1 leads to only four variables. M for the square matrices, V. for the column vectors, V, for the row vectors and S for the scalars. We define CFG GG, where the rules given variable is every possible operation (L, that produce this variable:
S (V,)(V)) diag (S) SS
V. + MV. | (V,)T V.S 1
V, - V.M (V.)T] SVV
M MM (M)T) diag (V-) (V))
13

---

As any operation in the rules of Gg, belongs to L1 it is clear that L(G&, ML (L1). For the other inclusion, a simple inductive proof on the maximal number of rules shows that any sentence produced by ML (C,) can be derived from Gc,, We have then ML (4,) 2, For any scalar s,8', since diag (s) and s' produce scalar, the only way to produce scalar from another variable to pass through a vector dot product. It implies that to generate scalars, only need be able generate vectors. We can then reduce Gc, by removing the scalar variable S and setting Va as starting variable.
Ve - MV. | (V,)* |
V, V,M (V.)
M + MM (M)² diag (V.) (V)) A
To ensure that the start variable is Ve a mandatory subsequent operation will be MV. for any matrix variable M. As consequence, by associativity of the matrix multiplication, MM and (V)(V)) can be removed from the rule of M.
V. MV. (V,) 1
V V,M (V.)
M - (M)T diag (V.) A
Since diag produces symmetric matrices and is symmetric, (M)T does not play any role here. As consequence, we can then focus on the column vector and we obtain r-G2,- L
Figure shows how the CFG Ge, produces the sentence A1.
ViVo
T Ve
(Vo) MV.
(V) M1
(1)
(1)
V.V.
1/2
MV
Figure 7: Ge, generating the sentence ATA From the starting variable, Variables are replaced by applying rules until only terminal symbols remain.
A.2 PROOFS OF SECTION 3
This subsection dedicated proof of propositions and theorem of section
Firstly, we prove proposition 3.1
Proof. Since L C C3. we only need to check the rule associated with the matrix Hadamard product can produce. Let M pax= and N E paxx be words ML (Cz) can produce, have M @ N E Raxx, We can conclude.
Secondly, we prove proposition 3.2
Proof. Let M be square matrix, Ve V, be respectively column and row vectors, we have for any i,
(M o (V. v.)) = MVs Vi)iss
= (Vo):Ma
Σ diag (Vo) Mi (V,);
(diag (V.) (V)s(V
Σ (diag (Va) M) diag (Vr)
(diag (V.) Mdiag (V,)),.
We only use the scalar product commutativity here.
14

---

Eventually, we prove theorem 3.1
Proof. As any operation in the rules of Geg belongs to L3, is clear that L(G C ML (Ca).
Let k be a positive integer, we denote by ME, Vel,, Vrž, and St the set of matrices, column vectors, row vectors and scalars that can be produce with at most &o operation in La from A. We also denote by M Veg, Vr& and Sg the set of matrices, column vectors, row vectors and scalars that can be produce with at most l rules applied in Gg.
For k = 0, we have Vel, Vr2, = 52 0, and thus Vel, c CVd. Vr C Vr& and 22 C S Moreover M = (A} and Mg (A).
Let suppose that there exists k 3 0 such that M2, C M& V2ž, c Veg Vrž, c Vi and 22 C S Then since Gcg rules is composed of the exhaustive operations in L3, we have that M C M : Velz C VV V+1 Vr C Vi and sh C St By induction, we have that 2,, C ML (Ez) and we can conclude that L(G = ML (Lz).
A.3
CFG TO DESCRIBE EXISTENT ARCHITECTURES
The following examples show how CFG can be used to characterise GNNs.
Proposition A.2 (GCN CFG)
The following CFG, strictly less expressive than ML (C2), represents GCN Kipf and Welling
2017
Ve CV. where = diag ((A ((1+))1)* (A + Dydiag ((A + 1)1
(8)
In GCN, the only grammatical operation is the message passing given by CV2 where C is the convolution support. The other parts of the model are linear combinations of vectors and MLP, that correspond to +.x, and f in the language. Since +,X, and do not affect the expressive power of the language (Geerts) (2020)), ) they do not appear in the grammar. Actually, any MPNN based on l convolution support C, included in ML (L, can be described by the following CFG which is strictly less expressive than ML (C₁):
V. C.V.l ...
C
GNNMLI is an architecture provably 1-WL equivalent (Balcilar et al. 2021 with the following node update.
H0+1) =HDWa.) (((2) + ((()) @ H(.1)
(10)
Where H the matrix of node embedding at layer I and W(.)) are learnable weight matrices. For any vector v w, since diag (u) w O w, the following CFG that describes GNNML1 equivalent to r-G
V. - V.V AV. 1
(11)
From r-G2, to MPNNs and PPGN We have already shown that most MPNNs can be written with operations in r-G since L, C L3 it stands for r-G2,- PPGN can also be written with r-G Indeed, at each layer, PPGN applies the matrix multiplication matched matrices on the third dimension, an operation included in r-G2,- The node leat ures stacked the third dimension diagonal matrices, the diag operation is also included in r-G2,- As all operations PPGN are included, r-G2, generalises PPGN layer. Actually, the following CFG describes the PPGN layer: :
M MM diag (1) A
(12)
15

---

012
915
Figure 8: Partition of four indices tuples.
[1 if (i, E Op:
2-IGN CFG For perpe [5], define B, E (RR*) as follow, B,
(0 if not.
Where (a,) corresponds to the 15 manners to partition four elements that be in Figure
As shown in Maron al. (2019b), (B,) basis of the set of equivariant linear operators from (2R7)² to (RR)? For the proof in the paper, two isomorphisms vec (IR))² - R=
and mat (R")+ + (IR²)2 was defined for any tensor T T (R")*, matrices M (R"2), N (IR)) and vector E R=*
mat(T)is
mat (M) = M Mm+tjkntt
vec(N); = Nitin,7on
vec (u)i. = Vin+j
We can then define the binary operation as follow
T:N = vec (mma(((Tee
Actually, we obtain the following operation
(T:N) Σ Ned k.
We have all we need to proceed on writing 2-1GN as grammar. The idea is to compute the basis operator to any matrices with set of rules.
(B = Σ (B: (BB))...N
k.
[N,,, if j.
10 if not.
It is pretty easy to see that
B:N=NOF
(BEN)as = Σ (B2)).sh..N.
No if
i not.
16

---

Here, it is sum over the matrix line avoiding the diagonal.
By:N diag ((N @ J)1)
(Ba
Σ (Baa).sk..NN. 1r,
Eigs Mu. if
0 if not.
Here, it is sum over the matrix column avoiding the diagonal.
By-N diag ((N @ 1)
E(Ba).sANNN (B,
[N i
if not.
is the projection of the corresponding column diagonal element.
B = (No)
(Bg:N),. Σ (Bss (B5)).....NN. k.
[NN j
10 if not.
is the projection the corresponding line diagonal element.
B ((N @ ))
(B,:N), Σ (Bo)is.,,Ne.
EiizANa Ne. - N,, N,, if jj j.
if not.
One can recognise B₂ and By.
BEN = (1(N (J - - -B.N
(B--Naa
Σ (B7)a.a,.NH.
k.1
Eies Nig if #
0 if not.
It is just sum over the line avoiding the element.
B -1
17

---

(BgiN)as = Σ (Ba)a...NN..
Nr. - Masifiss
0 if not.
is just a sum over the column corresponding to the line avoiding the transpose element.
Bg-N = ((N @J ON)
(B = (BB)).
Nep N Na if
0 if not.
It is just a sum over the line corresponding to the column avoiding the transpose element.
By-N (11" -N) O
NBi = Σ (Bio)igaa,,
1,1
E No. Nes if
0 if not.
It is just a sum over the column avoiding the element.
Bio-N ((NV @ J)11 -)
(B = > (BII)),A,,AAA
k,1
NI, - No. - N,s if if j.
10 if not.
It is just a sum over the diagonal avoiding the two corresponding diagonal elements.
B = (1 o 1)liJ B - -B,-N
(Bi2 = Σ (..2))a...AA..
k.1
Nus i-
0 if not.
It is just a sum over the diagonal avoiding the corresponding diagonal element.
B -
(B13-N) = Σ (BBB))ig.AN R.I
[ NN. if
0 if not
18

---

It selects the non-diagonal.
B13:N NNJ
(Bia = Σ (Bra)issaiNNa
J, if
0 if not.
It selects the transpose non-diagonal.
= = OT
(B15 Σ ((1IS)aSA,IIA.. 1
Euz Enzi k2 EigiNai Noa
Eiju Ni. - Ejjt N₁a
sサl Ni.- Ni. Na if j,
0 if not.
is fact a composition of other elements of the basis.
B1 -N J)1)J B B N N + N + BLEN
From all this, we can deduce the following grammar that generates 2-IGN:
M + VarT MOJI
V. MV.
As see, there is less operation in the CFG than operators in the basis.
A.4 GNNs DERIVED FROM DIFFERENT GRAMMARS
This subsection is dedicated to description of GNNs derived from different grammars of Q1 experiment (section 4
Figure depicts layer of GNN derived from the exhaustive CFG G The resulting architecTure inherits 3-WT, expressive power from theorem 3.1 In Figure 10 GNN derived
from C,, the CFG obtain during the reduction process of the framework of section 3 is described. Since is missing in r-G(Lg, Figure describes GNN derived from grammar containing r-G(Lz) and MT.
A.5
N EXPRESSIVENESS AT FIXED DEPTI
The following proposition ensures that for architectures with at most three layers, the GNN derived from the exhaustive CFG G(Cz), called E-G2N2, and G2N² have the same expressive power.
Proposition A.3 (Graph isomorphism (WL) expressiveness al fixed depth) Let k (1,2,3), N2 and E-G have the same seporalive power after k layers.
Proof. Remark that, for scalars and 8', if ss' separates two graphs then or already separate those graphs.
19

---

ogg 1p6000
MIP
Ettege
Sibegg
Uise
V. rrdide
Linegg
V. update
Goorg
MLP2
M1.7y
Linowr
Sra Kocoles
Figure 9: Layer of GNN derived from G
nige spebos
MILP
Litage Liuege
Hiuz
Ve vodato
V. upplste
MLP
MLPy
Sirvor
Lisonr
Koeoeer
Figure 10: Layer of a GNN derived from i-G
20

---

Sars x MAX u
50
L1
S0
b.
s(++1)
C
MLP
50
bo
M
C(1+1
Lg
L4
bt
L5
tencepoooo
s0
bys
L6
Cerl x t
fn
briagg
L7
diag
([+1)
H
n
(1)
bav
MLP
Vge
Jn
H(++)
Figure 11: Layer of GNN derived r-G2, U (MT).
We denote by M (k) and s(k) respectively the set of matrices, vectors and scalars that G2N2 can compute at layer k. We also denotes by M(() v(k) v-(k)
"E' : rE and s(k), respectively the set matrices, column and row vectors and scalars that E-G"N" can compute at layer k. Remark that thanks the skip connection in both layer, these sets are increasing for inclusion with respect to For example s() C s(-11)
We will show that SC = ((k) for h: (1,2,3).
First all we have that M = MC (0) = {A} and V = v.(0) v. = {1} by construction of the architectures.
Let compare two architectures with only one layer, we have that v(I) v(1 v(1) since
oF rF
1, but M M u (ew", v, w. E v(0)) Since (owr, u, E V 11 and
this matrix can be approximated by the bias of any of the matrix linear of G² we have M M.. Thus (() s
Let compare two architectures with two layers, we have that cE = V v
cG since like
in Maron et al. (2019a) the vector Hadamard product can be approximated with a multi layer perceptron, but M M U (uw", applying readout function on N would result in
V(2), Let N vwf, v, oG J. then
((1)
1T 1 ES ES
From that have that s(2) s since the final decision multilayer perceptron can approximate ss' for any scalar s'. So our hypothesise is true for k =
Assume that we compare architectures with k 3 layers.
Since A = M U fowe w.w E v(ll), we have for the matrix case,
M (3) = M
(3)
U fse w. v!a))
((M(wWT) or (vw") M ME E M w, v())
U (M O (ow)), M M w, E v(l)).
21

---

We have three cases here. For N {ow", Uu V()), J. it is the same situation than for k = 2.
For N M(vw"), M E g v, w oo either M MC or M {ow", u w V.l J. cG's are in the same case than for A: = 2. In the second case, there exists and w' v- C v such that M = r'("))" which means that after the readout function, we have
v(3) In the first case Mr E GG and since Vid C v(3),
I'
ESG
ES ESG
For N = M @ (vw"), M _ w w v(I)
cG either M Me or M E fow v,w V
In the first case, we have that 1'(M @ (vw")) E (()) Indeed,
(TM @ (ew (ew"))l v- Mw = 1sT (vO Mw)
EV
We have for the vector case,
V-31 cB E
v-3)
=v13
Ufo"" w vG o' e v.2)
Since w² of S for all w, v' oi' we have that S =S c())
B SPECTRAL RESPONSE OF ML. (L3)
The graph Laplacian the matrix D A (or - D- for the normalised Laplacian) where D is the diagonal degree matrix. Since L is positive semidefinite, its cigendecomposition is Udiag (A)U" with U E R= orthogonal and E R7. By analogy with the convolution theorem, one can define graph filtering in the frequency domain by I = Udiag (I())) UTx where Ω the filter applied in the spectral domain.
Lemme B.1
Given A the adjacency matria of graph, ML (Cz) can compute the graph Laplacian L and the normalised Laplacian Ln of this graph.
Proof. ML (Cg) can produce A I which is equal D. Thus it can compute = A. For the normalised Laplacian, since the point-wise application of a function does not improve the expressive power of ML (Lg) (Geerts (2020)). D- is reachable by ML (Cz). Thus, the normalised Laplacian D LD- can be computed.
As in Balcilar et al. 2020 we define the spectral response Φ E R" of C E Raxn as ((A) diagonal(U" CC) where diagonal extracts the diagonal of a given square matrix. Using spectral response, Balcilar et al. (2020) shows that most existing MPNNs act as low- pass filters while high-pass and band-pass filters are experimentally proved be necessary to increase model expressive power.
Theorem B.2
For any continuous filter in the spectral domain of the normalised Laplacian, there erists matrix in ML (Cz) such that its spectral response approzimate Q.
Proof. The spectrum of the normalised Laplacian is included in [0, 2). which is compact. Thanks Stone- Weierstraß theorem, any continuous function can be approximated by
22

---

polynomial function. We just have to ensure the existence of matrix in ML (Lz) such that its spectral response is a polynomial function.
For k E N, the spectral response of L is X since we have
L U UUUdiag (A) (A)UT)*
= Udidd (A)* U diag (A)*
From Lemma B.1 ML (C3) can compute L, and thus can compute L for any k N. Since MT. (La) can produce all the matrices with monome spectral response and since the function that gives the spectral response to a given matrix is linear, ML (Cx) can produce any matrices with polynomial spectral response.
This section shows that 3- WL GNN should be able to approximate any type of filter.
C EXPERIMENTS
C.1 EXPERIMENTAL SETTING
In the experiments, all the linear blocks of layer are the same width S() =b6 (1) ding This means that MLP M takes input third order tensor of dimensions 4S and MLP takes as input matrix of dimensions x 28()) At each layer, the MLP depth is always 2 and the intermediate layer doubled the input dimension.
C.2 QM9
For this experiment, there are edge attributes and 11 node features. We use 3 layers with 5()) = f = 64 when learning one target at time and ( f(() = 32 in the other experiment for / E (1,2.3}. The vector readout function is sum over the components of (3) and the matrix readout function is a over the components of the diagonal and the off-diagonal parts c(3), Finally, fully connected layers, with respective (512/226
12)) applied before using an absolute error loss. Complete results on this dataset can be found in Table
Table Results on QM9 dataset predicting each target at time. The metric is MAE, the lower, the better.
Target
1-GNN
1-2-3-GNN
DTNN
Deep LRP
NGNN
P-GNN
PPGN
GºN²
0.493
0.476
0.244
0.364
0.428
0.428
0.0934
0.0703
0.78
0.27
0.95
0.298
0.29
0.230
0.318
0.127
Chomo
0.00321
0.00337
0.00388
0.00254
0.00265
0.00261
0.00174
0.00172
Guuoo
0.00355
0.00351
0.00512
0.00277
0.00297
0.00267
0.0021
0.00153
Ae
0.0049
0.0048
0.0112
0.00353
0.0038
0.0038
0.0029
0.00253
R
34.1
22.9
17.0
19.3
20.5
18.64
3.78
0.342
ZPVE
0.00124
0.00019
0.00172
0.00055
0.0002
0.00014
0.000399
0.0000951
U
2.32
0.0427
2.43
0.413
0.295
0.211
0.022
0.0169
2.08
0.111
2.43
0.413
0.361
0.206
0.0504
0.0162
H
2.23
0.0419
2.43
0.413
0.305
0.269
0.0294
0.0176
G
1.94
0.0469
2.43
0.413
0.489
0.261
0.024
0.0214
C.
0.27
0.0944
2.43
0.129
0.174
0.0730
0.144
0.0429
C.3
TUD
The parameter setting for each of the 6 experiments related to this dataset can be found in Complete results on this dataset are given in Table
Table 5
23

---

Table N2 parameters detail for each dataset in our experiments on TU
parameters
MUTAG
PTC
Proteins
NCI1
IMDB-B
IMDB-M
node features
22
3
37
1
edge features
0
0
0
# of G²N² layer = mm
3
3
3
3
1 EE [1,4m]] g [1,4m]]
16
32
32
64
32
32
64
32
readout dimension loss
256/128/ BCEloss
512/256/1 BCEloss
512/256/1
128/64/1
512/256/1
512/256/3
BCFloss
BCEloss
BCEloss
C'loss
Table 6: Results TUD dataset.
The metric is accuracy, the higher, the better.
Dalasel
MUTAG
PTC
Proteins
NCI1
IMDB-B
IMDB-M
WL kernel (Shervashidze et al. 2011
90.415.7
59.914.33
75.0.3..1
86.0.1.8
73.8.13.9
50.913.8
GNTK (Du et al. (2199]
90.0.1..5
67.916.9
75.61:4.2
84.211.
76.9113.6
52.814.6
DGCNN Zhang et 2018
85.8.1
58.6112.5
75.5:10.9
74.4100.5
70.0:10.9
47.810.9
IGN Marrn et (20195))
83.9#13.0
58.516.9
76.625.5
74.3+2.7
72.0=5.5
48.7#3.4
GIN Xu et al 2009
89.4+5.6
64.6=7.0
76,24228
82.7#1.7
75.1=5.1
52.3+2.8
PPGNs Maron et al 2019a
90.6
66.216.6
77.2#4.77
83.2#1.1
73.0
5..5#3.6
Natural G/ Idd Haan et al.
2020
89.4+1.60
66.8+11779
71.7+1104
82.7+1135
74.8++2.01
51.3+1.50
WFGL. KKolouri
2022
N/A
67.5+7.7
76.5+44.2
N/A
75.4+5.00
52.3+2.9
GraphhooN Cat et al
2021
91.6+6.5
64.9+7.5
77.4+4.9
82.7+1.7
76.0+3.77
N/A
GSNs [Bourilsas et al. 2022
92.247.5
68.217.2
76.615.0
83.512.0
77.8:13.3
54.313.3
G²
92.5=4.3
7.3
80.1-3.7
82.810.9
76.8:12.8
54.012.9
C.4 SPECTRAL DATASET
This dataset composed of three 2D grids of size 30x30, for respectively training, validation, and testing. We use 3 layers of GºN² with (()) 32 and p! 32 for / E [1,2,3}. Our readout function the identity over the last node embedding and sum over the line of the last edge embedding. We finally apply two fully connected layers on the output of the readout function and then use Mean Square Error (MSE) loss to compare the output the ground truth.
24


Reviews:
[{"review_id": "EgTtBtVB80", "reviewer": "Reviewer_HFhT", "summary": "This paper investigates the expressive power of 3-WL from the aspect of formal language. The authors show that 3-WL is equivalent to a context-free grammar (CFG), and propose a reduced CFG that preserves the same expressiveness. Based on the reduced CFG, the authors develop a new WL algorithm and GNN model that match the expressiveness of 3-WL. The new GNN model achieves competitive performance and efficiency on downstream tasks.", "questions": "* In the theoretical aspect, although the two CFGs r-$G_{\\mathcal{L}_3}$ and $G_{\\mathcal{L}_3}$ have the same expressive power, it may take more steps for r-$G_{\\mathcal{L}_3}$ than $G_{\\mathcal{L}_3}$ to generate the same string. Therefore, how can $G^2N^2$ match the expressiveness of the ordinary 3-WL GNN with a fixed number of layers?\n* I would also like to see how the new GNN model performs on the ZINC-12k and ZINC-full datasets, which are widely used benchmarks for molecular property prediction.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "There are some positive points of this paper. \n* The paper is well-written and easy to follow.\n* The paper exploits the formal language equivalence to investigate the GNN model and design a new GNN model, which I think is a promising direction for future research.", "weaknesses": "I have some concerns about the paper as follows:\n* I am not convinced by the novelty and the contribution of the paper, as the CFG $G_\\mathcal{L_3}$​​ seems to be a straightforward derivation of the MATLANG.\n* The validation and discussion of the reduced CFG and the corresponding GNN may be insufficient, both empirically and theoretically. I have some questions for the authors below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mfRaBGTsCx", "reviewer": "Reviewer_3x4U", "summary": "This paper presents a framework to convert context-free rules over an algebraic matrix language into a GNN architecture. Using this framework, they produce a WL-3 GNN as follows: (1) they write down a set of context-free rules producing a language that is just as expressive as 3-WL, (2) they reduce this set of rules into a smaller set of rules, and (3) they translate these rules directly into a GNN architecture. The resulting architecture performs competitively in practice, outperforming various existing GNNs on a variety of tasks.", "questions": "(1) While many CFGs are equally expressive if we can apply their rules an arbitrary number of times, it seems like what we actually care about is the expressiveness of the grammar after L rule applications, given that in practice our GNNs are finite depth. In light of this intuition, the paper might benefit from some discussion of which CFGs are preferable, given that they have the same expressive power.\n\n(2) From my understanding, it seems that this architecture outperforms other architectures in some datasets but not others (table 6), but has the advantage of being the strongest GNN out of those with provable expressivity (since it dominates PPGN). Is this understanding correct? If so, what is the utility of having provable expressivity, beyond the model's performance on the datasets?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(1) While this is not my area, the contribution of the paper seems strong in that it presents a framework for designing GNN architectures that implement a given CFG.\n\n(2) The experiments seem strong, and the proposed GNN is both provably expressive and performs competitively compared to existing architectures.\n\n(3) The paper is well-written, clear, and well-organized.", "weaknesses": "Some minor weaknesses are discussed in the questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Op2doEGzQL", "reviewer": "Reviewer_giVQ", "summary": "The paper proposes a new architecture for GNNs that captures precisely the expressive power of 3WL. This architecture is based on a grammatical representation of a language over graphs that has the same expressive power as 3WL. The idea is that this new architecture permits a more efficient implementation than the 3WL-based GNNs, which are known not to scale well in practical scenarios.", "questions": "Could you please comment further on the main criticism I posed above: what do you think is the main reason the MATLANG-based GNNs are more practically suitable than the standard ones based on 3WL? This came as a big surprise to me, and it is a bit dissatisfying to stay with an explanation based on experiments only. I feel that a more principled, perhaps theoretical explanation, is lacking.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is very polished and easy to follow\n- The topic is timely and the problem practically relevant\n- Experiments confirm the suitability if the approach", "weaknesses": "There is only one criticism I make to the paper and it is the lack of search for a principled explanation of why the GNNs based on MATLANG are more efficient than the ones based on 3WL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)