Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Authors: Anders Aamand
Justin Y Chen
Piotr Indyk
Shyam Narayanan
Ronitt Rubinfeld
Nicholas Schiefer
Sandeep Silwal
Tal Wagner
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph neural network
Weisfeiler-Lehman
graph isomorphism
expressivity

Abstract: Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the “combine” function of size polynomial or even exponential in the number of graph nodes $n$, as well as feature vectors of length linear in $n$. 

We present an improved simulation of the WL test on GNNs with {\em exponentially} lower complexity. In particular,  the neural network implementing the  combine function  in each node has only $\mathrm{polylog}(n)$ parameters, and the feature vectors exchanged by the nodes of GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction. 

Exponentially Improving the Complexity of Simulating the Weisfeller-Lehman Test with Graph Neural Networks
Anders Aamand MIT aamand@mit. edu
Justin Y. Chen MIT justcemit.c edu
Piotr Indyk MIT indyk@mit.edd edu
Shyam Narayanan MIT shyamsn@mit.edd
Ronitt Rubinfeld MIT ronitt vonitt@mit. edu
Nicholas Schiefer MIT schiefer@mit.edd
Sandeep Silwal MIT silwal@mic @mit.edu edu
Tal Wagner'
Amazon AWS
tal. www.wrwwgaia.ccom com
Abstract
Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WI.) graph test. particular, they show that the WI. test can be simulated by GNNs. However, those simulations involve neural networks for the "combine" function of size polynomial or even exponential in the number of graph nodes as well as feature vectors of length linear in
We present improved simulation of the WL test GNNs with exponentially lower complexity. In particular, the neural network implementing the combine function in each node has only polylog(n) parameters, and the feature vectors exchanged by the nodes GNN consists of only O(log n) bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (ntar)-optimallty of our construction.
Introduction
Graph Neural Networks (GNNs) have become a popular tool for machine learning graph- structured data, with applications in social network prediction [HYL17], traffic prediction [YYZ18]. recommender systems [YHC+18) drug discovery [WKK* + 20]. computer vision [LGD + 19, FLM 19, MBM 17, QSMG17]. and combinatorial optimization [CCK*21] Standard message passing GNNs use the topology of the input graph define the network structure: in each step k, a node aggregates messages from each of its neighbors and combines them using a function ((()), computed by a neural network, to determine its message for the next round. Crucially, the aggregation function must be symmetric, ensure that the output of GNNs is invariant under node permutation. This restriction raised questions about how expressive such network architectures are, and in particular what classes of graphs are distinguishable using GNNs.
The seminal works of Xu et al. [XHL_]9 [19] and Morris et al. [MRF+ 19] (see also [Gro21]) showed that GNNs are exactly as powerful in distinguishing graphs the Weisfeiler-Lehman (WL) test (LL68), also known as color refinement. This combinatorial procedure a necessary but not sufficient test for graph isomorphism. It proceeds in repeated rounds: in each round, node labels itself with the "hash" of the multiset of labels of its neighbors. The aforementioned papers show that (i) GNNs can simulate the WL test and (ii) GNNs can only distinguish those graphs that the WL test determines to be different. This provides complete characterization of the expressive power of GNN architectures.
Work done prior to joining Amazon.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Our results compared prior work on GNNs that simulate the WL test.
Construction
Message size Parameters in ((
Oblivious"
Deterministic"
Xu et al. [XHLJ19]
((n)
22(2")
Yes
Yes
Morris et al. [MRF+ 19]
(nn)
poly(n)
No
Yes
This paper
Ologgn)
polylog(n)
Yes No
Oblivious designs use the same weights for any input graph. nonedeteriiiistic constructions require some weights to be assigned by random samples drawn from some distribution, and may err with small probability.
The connection between GNNs and the WL test has spawned wave of new results studying GNN variants that either match the distinguishing power of the WL test or adopt new methods beyond message passing on the edges of the input graph to overcome this barrier (see the excellent sur- veys [MFK21, M 21, Gro21] for an overview of this area). However, the results in the original as well the follow up works mostly focus on qualitative questions (how expressive GNNs are) as opposed to quantitative questions such as the network complexity. In particular, while Xu et al. [XHLJ19] show that there exist GNN architectures that simulate the WL coloring procedure as long as the aggregation step is injective, they rely on the universal approximation theorem to show that there exists neural network that can simulate the hash function used in WL. As result, the size of the network could be exponential in the number of nodes n. In contrast, the construction of Morris et al. [MFK21] uses networks of size polynomial in n. However, the weights of the network implementing (b() in their construction depend the structure of the underlying graph, which suffices for node classification, but is not sufficient for the context of graph classification.
Overall, the quantitative understanding of the complexity of simulating WL remains open problem. Indeed, the survey [Gro21] states "The size of the GNNs and related parameters like depth and width, which directly affect the complexity of inference and learning. definitely require close attention."
Our Results. The main question addressed in this work is: what is the simplest (in terms of the number of neural network units and message length) GNN capable of simulating the WL test? Equivalently, at what point does a GNN become so small that loses its expressive power?
Our main result is a highly efficient construction of a GNN architecture that is capable of simulating the WL test. For graphs with nodes, it can simulate poly(n) steps of the WL test, such that the neural network implementing gi0)) in each round has polylog(n) parameters, and the messages exchanged by the nodes of the GNN in each round consist of O n)) bits. This offers at least an exponential improvement over the prior bounds obtained in [XHLJ19, MRF+ 19] (see Table 1), extending the equivalence between the WL test and the expressive power of GNNs to neural networks of reasonable (in fact, quite small) size. Furthermore, our architecture is simple, using vector sum for aggregation and ReLU units for the combine function (kk)_ Finally, our construction can be generalized to yield a depth-size tradeoff: for any integer t > 0, we can can construct a neural network of depth (t)) and size ((1e)) polylog(n).
To achieve this result, our construction is randomized, i.e., some weights of the neural networks are selected at random, and the simulation of the WI. test is correct with high probability - 1 1/poll((n) Thus, our construction can be viewed as creating distribution over neural networks computing the function (x()22 2 In particular, this implies that, for each graph, there exists a single neural network implementing (b))) that accurately simulates WL on that graph. The size of the network is exponentially smaller than in [MRF+ 19], although the construction is probabilistic.
We complement this results with two lower bounds for executing a WI. iteration. Our first lower bound addresses the communication complexity of this problem, and demonstrates that to solve it, each node must communicate labels that are at least Olog n) bits long, matching the upper bound achieved by our construction. Our second lower bound addresses the computational complexity,
Note that selecting (*)) random is quite different from random node initialization, e.g., investigated in [ACGL21]. In particular, in our model all nodes use the same function t( (with the same parameters), without breaking the permutation invariance property of GNNs, as in the standard GNN model.

---

namely the parameters of the neural network. It shows that if the messages sent between nodes are vectors with entries in [F] = {0, ...... F - 1}, then the network implementing (( must use (log F) ReLU units.
Related work. The equivalence between the discriminative power of GNNs and the WL test has been shown in the aforementioned works [XHLJ19, MRF+ 191. A strengthened version of the theorem of [XHLJ19] 19], where the same combine function Ø is used in all iterations (i.c., ø ((a) for all k)) appeared in the survey [Gro21]. Many works since have studied various representational issues in GNNs; we refer the reader excellent surveys [Gro21, HV21, MLM+ Jeg22]. In particular, [Lou19] established connections between GNNs and distributed computing models such as LOCAL and CONGEST, and derived lower bounds for several computational tasks based on this connection. drew a connection between the expressiveness of GNNs in graph isomorphism testing and in function approximation. [BKM+20] studied the expressiveness of GNNs in computing Boolean node classifiers, and [GMP21] studied the expressiveness of graph convolutional networks (GCNs).
[CVCB] 19]
The emergence of WL as barrier in GNN expressivity has also led to flurry of work enhanc- ing their expressivity by means of more general architectures. These include higher-order GNNs inspired by higher-dimensional analogs of WL [MRF+19 MBHSLL1)). unique node identifiers [Lou19, VLF20J, random node initializations [ACGL21, SYK21J. relational pooling [MSRR19] 19), incorporating additional information on the graph structure [NM20, BGRR21, BFZB22, CMR21, TRWG21J. and more. We refer to [MLM+21] for a comprehensive survey of this line of work.
1.1 Preliminaries
Notation. For the rest of the paper, we use (v) to denote the neighborhood of v in a graph E), including v itself, and we use {.} to denote multisets rather than sets.
GNNs. Let G (V, be a graph with N nodes. GNNs use the graph structure of G to learn node embeddings for all the nodes across multiple iterations. Let (/ denote the embedding vector of node E V in the kth iteration. The vectors h represent the initial node embeddings. In every iteration & 2 1, each node v sends its current embedding (k-1) to all its neighbors, and then computes its new embedding 1 by the equation
h (K) = (a)
.n! 11- : (
(1.1)
where (bk) is implemented by a neural network with ReLU activations (note that ((k)) may differ across different iterations k). The function f is called the 'aggregate' function, and (5(k) is called the 'combine' function. The embeddings h the final iteration K can be used for node classification. For graph classification, they can be aggregated into graph embedding he with a 'readout' function,
hG = READOUT( (2) | V)).
Weisfeiler-Lehman (WL) Test. The WI. test [WL688] is popular heuristic for the graph isomor- phism problem. While the exact complexity of this problem remains unknown [Bab16], the WL test is a powerful heuristic capable of distinguishing a large family of graphs [BK79].
The WL test is as follows. Given graph G(V, E), initially all nodes are given the same fixed label (()) say (0) 1 for all e E V. Then, in every iteration & 2 1, each node v is assigned the new (v)))) where HASH is 1-1 mapping (i.e., different multisets of labels are guaranteed to be hashed into distinct new labels). Performing this procedure on two graphs G, G², the WL test declares them non-isomorphic if the label multiset (E!*) E V) differs between the graphs at some iteration k. Note that the algorithm converges within at most n iterations.
label ((x) HASH(( (k-1)
Simulating WL with GNNs. A GNN simulates WL deterministically if the node embeddings (n( at each iteration & constitute valid labels ((0) for the WL test. We also consider randomized simulation, where the GNN's weights are selected at random and we allow some small failure probability where distinct multisets of labels from iteration k are hashed into the same label at iteration k. This is captured by the next definition.
3

---

Definition 1.1 (Successful lteration of the WL Test). A WL iteration gets existing labels {he V V} for all nodes, and outputs new labels {h', : v E ] given by
h' = & (f (fh w E (()))))
for an aggregate function f and neural network & with random weights. We say the iteration is successful for all E V. the following holds:
. (h : EN(w)) {hr [N(u)) then Ri, = hy with probability I, and
. (h w EN(w)} + {hu w w (NEN()) then hi, + hi with probability 1 - -p,
where the probability is over the choices of the random weights of o.
To ensure the WL simulation is successful across poly(n) iterations and for all pairs of nodes, we can set failure probability p to 1 1/poly(n) and apply a union bound (see Prop. A. in Appendix A).
1.2 Overview of Our Techniques
In this section we give an overview of our GNN architectures for simulating WL. To explain our ideas in stages, we begin with simpler construction of a polynomial size GNN, It is far larger than the ultimate polylogarithmic size we are aiming for, but forms a useful intermediate step toward our second and final construction.
Construction 1 (Section 2). Recall that the kth WL iteration, for a node v, aggregates the labels of its neighbors from the previous iteration, H6 ()) 1) := [hh (k-) w E .N()),, and hashes them into a new label 11 for c. Our GNNs aggregate by summing, i.e., they sum H!! into s!²)
EweN(u) Mhe (k-11 and then hash the sum into (2) using ReLU neural network of our choice.
If two nodes u, satisfy H(*-1) + H (k-1) then WL assigns them distinct labels in iteration k, and therefore we want construction to satisfy h * h!(²) with probability at least 1 -p (as per Definition 1.1). This can fail in two places: either due to summing (if s(k) = S/A) even though 1!(--) * H1,h (2(8-1)) or due to hashing (if h = A even though S.A) + s( To avoid the first failure mode (summing), we use one-hot encodings for the node labels, meaning that for every node e and iteration k. (/) is a one-hot vector in {0, 1). (for F to be determined shortly). This ensures that if (+(--1) # H!!- then S(at) # s(²) due to the linear independence of the one-hot vectors. To handle the second failure mode (hashing), we use random hashing into F = O(1pp) buckets, Mot-Hot
rendering the collision probability no more than p. That is, we let h(*)) g: 2z {1....,A F} is chosen at random from an (approximately) universal hash family. We use the simple hash function g(x)) = (a. . mod where is random vector. It can be implemented with ReLU neural network, since the dot product is just a linear layer, and the mod operation can be implemented with constant width and logarithmic depth, by reduction to the "triangular wave" construction due to Telgarsky [Tel16] (see Appendix B.1). Finally, we show that turning the index of the hash bucket into a one-hot vector can be done with O(F) ReLU units and constant depth.
where
Since our desired collision probability is 1 (m), we set F = O(1p)) = poly(n). Since our one-hot vectors are of dimension F., the resulting GNN has width F poly(n) (and depth Ologn) due to implementing the mod operation with ReLUs), and thus total size poly(n).
polylogarithmic size construction. The weak point in the previous construction was the wasteful use of one-hot encoding vectors, which caused the width to be F.. In the current construction, we still wish hash into F bins that is, to have F distinct possible labels in each iteration - but we aim to represent them using bitstrings of length Olog F), thus exponentially improving the width of the network. That is, for every node and iteration A; the label 1 (k-1) would now be a vector in {0, 1] O F), The challenge is again to avoid the two failure modes above, ensuring that the failure probability does not exceed p. Since we cannot use one-hot encoding, we need to devise another method to avoid the first failure mode, i.c.,
Construction 2 (Section 3). We now proceed to describe
ensure that with high probability s!!)) # (kk) if (k-1) H (k-1)
To this end, suppose for a moment that we had access to truly random vector a E {0, 1)." Then each node v, instead of sending the one-hot encoding of its label h (k-1) we could instead send

---

ind
Ewerr(yy hlo h2r
hu (k-1)
ind2
sum
lin
mod
(R-1) Bapprosl
ind,
Figure 1: Constructions of our GNNs. Construction (section 2): The layer "sum" sums the input vectors (h@-1) w [(v).. "lin" is linear layer that computes the dot product with a random vector and outputs single scalar. "mod" is a neural network that computes the input scalar modulo F, using Theorem 2.2. Each "ind," is a neural network that outputs if its input equals and outputs O otherwise, using eq. (2.1). The ith coordinate of the output vector A equals the output of ind,, Construction 2 (section 3): Similar, except that now each ind, is neural network that gets an input integer j E [F]] and outputs the jth coordinate of a vector a' sampled from an e-biased space, using Theorem C.1. This reduces the total number of units of the network from poly(n) to polylog(n).
the dot product (a, he h which is the single bit "nSe 1)- Each node thus receives the bits { (ong-n: : :ent::eeN(uu EN(w) } from its neighbors and aggregates them into the sum EweN(w) (a, h (
which, by linearity, is equal to (a, ) (using the notation from Construction 1). It is easy to observe that if s(() * S!²² then Sa.) * (a, S.a))))))))) with probability at least 0.5. Repeating this process log independent times decreases the collision probability to the requisite 1/F. Thus, we can define lor that concatenates log F dot products with independent random vectors at ... ...a'ogFF E {0, 1 as just described, failing at the summing operation with probability at most 1/F. The second failure mode (hashing) can again be handled as before.
labeling scheme A {0, 1o
That catch is that, since has length F, the overall number of parameters in the GNN would again be at least F. To avoid this, we appeal the computational theory of pseudorandomness. The idea is to replace the random vector a with an efficient pseudorandom analog. Note that the above approach goes through even if the probability that (a, S(Ai), + (a, s(()) is slightly larger than 0.5, say 0.5 + e for a small constant e. It is well-known in complexity theory that there exist pseudo- random generators, called e-biased spaces, that generate vectors satisfying this property given only Olog F + log(1 I/e)) truly random bits." 3 Crucially, each bit of a can be computed using a threshold circuit with size polynomial O(log F + log(1/<)) and constant depth (Theorem C. which translates to a ReLU neural network with the same parameters (Lemma C.2). Using these generators in our GNN to implement a pseudorandom (c-biased) analog of a yields our final construction.
2 First Construction: Polynomial-size GNN
Our first construction towards Definition 1.1 is exponentially larger compared to our final optimized construction of Section 3. Nevertheless, it is instructive and motivates our optimized construction.
Let (k) denote the label of a vertex u in the kth iteration. For our first construction, we will always
maintain the invariant that (k) will be a one-hot encoded vector in {0, 1) for all E V and all iterations k. F >> 2n will be a prime which also satisfies F = (ppoly(n)) As stated previously, the
aggregate function will just be the sum function. Our construction for the neural network used in the kth iteration, ((k), will take in the sum of the neighbors labels according to Equation (1.1) and output a one-hot encoded vector in {0, 1)a
Teehhicalll, they guarantee this property only when (kk) are binary vectors, but Lemma 3.2 shows how to extend this property general integer vectors well.
5

---

Implementation of Neural Network. notation from (simplified) Equation 1.1:
Our construction for ((()) is the following: First recall the
( = (5 (f :e N(o))))
1. For every node v, the input to (+ is the sum of feature vectors of neighbors from the prior iteration, EweN(n) New (k-1), which is returned by the summing function f. Given any such input x E ZF, (((a) computes the inner product of x with a vector a E ZF where each entry of a is a uniformly random integer in [F] :- (0,...................... F 13.
(i(k) then computes (ar a) mod F.
3. Finally, we represent the value of (a, a) as a one-hot encoded vector in z where the 2-th entry is equal to I and all other entries are O's.
Altogether, (bk) can be summarized as: th = One-Hot ((EwENto)) tww 1 mod F).
Note that we set the initial labels Au to be the same starting vector for all vertices (any one- hot vector). This matches the WL test which also initializes all nodes with the same initial label. Furthermore, the weights of (k()) are independent: the random vector a is sampled independently for each iteration.
Correctness of Construction. The following lemma proves that the above construction satisfies the requirement of Definition 1.1. Its proof is given in Appendix B.
Lemma 2.1. Let {te ( w e [(v) and (h : E (uu) denote the multiset of neighbor- hood labels for vertices u and u respectively. If the multisets are distinct then the labels computed for v and in the kth iteration are the same with probability at most O(1/F). If the multisets are the same then the labels are the same, i... the kth iteration is successful according to Definition 1.1.
Complexity of the GNN. We now evaluate the size complexity of implementing our construction via a neural network 6. Note that Step 1 of the construction can be done with 1 layer as it simply involves taking an inner product. The main challenge to implement the modulo function. We give the following construction in Section B.1 of the appendix.
Theorem 2.2. Suppose F = poly(n). There exists an explicit construction of a network which computes modulo F in the domain (0, (0...., using a ReLU network with O(log n) hidden units and Olog n) depth. More generally, given an integer parameter >> 0, the function can be computed with O ((Fn)))) 0(13)) logn) hidden units and O() depth.
Directly appealing to the theorem above, we can implement modulo F required in Step 2 of the construction using a neural network with O(log n) units, depth Olog n). In addition, we need only O(log n.) bits represent the weights.
Finally, Step 3 of our construction requires outputting a one hot encoding. We can do this by inputting (the output of Step 2 of the construction) into F indicator functions, each of which detect if is equal to a particular integer in [F]. Each indicator function can be implemented via O(1) ReLU
nodes as follows. Let
gxz) = ReLU(minn-RRLLUUj
1/2) - ReLU + 1)))
(2.1)
which can be casily implemented as a ReLU network. (Note min b) = a + b max(a b) and max(a, b) max(a 6, 0) + ReLU - b) 6.) It can be checked that g( for all other integers x + and that g can be implemented with O(1) ReLU function compositions. Thus, Step of the construction requires (1) hidden layers and O(F) total hidden units. Altogether we have proven the following result.
and g(z) 0
Theorem 2.3. There exists a construction of neural network & which performs successful iteration according to Definition 1.1 with failure probability p = O()/ & has depth O n), O(F) hidden units, and requires Ollog(FF) bits of precision. Furthermore, all labels in all iterations are vectors in 40, F)F. More generally, given an integer parameter i > 0, the function can be computed with n ((Ltt) polylog(n) hidden units and O(t) depth.

---

Remark 2.4. In the standard WL test, the number of iterations is chosen to be O(n). Thus the right setting of F in Theorem 2.3 is F (p)) which gives us depth (log n), ((poly(n)) hidden units, and requires (logn) bits of precision in addition to labels in dimension (ppoly(n))
3 Second Construction: Polylogarithmic-size GNN via Pseudo-randomnes
We now present a more efficient construction of a GNN which simulates the WL. test with an exponential improvement in the number of hidden units and label size. To motivate the improvement, we consider Step of the prior construction which outputs a one-hot encoding. The one-ho encoding was useful as it allowed us to index into uniformly random vector a (which we then sum over mod F in order to hash the neighborhood's labels). However, this limited us to use feature vectors of a large dimension and required many hidden units to create one-hot vectors. Instead of working with one-hot encodings as an intermediary, we will directly compute the entries of the random vector needed. This has two advantages: vectors as well as reduce the total size of the neural networks used. We accomplish this via using rreudo-random vectors whose entries can be generated needed with small ReLU neural network (see Corollary 3.3). This allows us to use node labels in dimension O(log n) as opposed to (()).
can significantly reduce the dimension of the feature
The random vectors we employ have their entries generated from an e-biased sample space. These are random vectors which are approximately uniform and they have been well-studied in the complexity- theory literature. We recall some definitions below.
Definition 3.1 (Bias). Let X be a probability distribution over {0.1)"" The bias of X with respect to set of indices Pa-x [Eier I4 = -0 Pa-x [Eier [1:i=]1]]]] where each sum taken modulo 2 and the empty sum is defined to be O.
S (1..... m) is defined as bias; (X) =
Definition 3.2 (E-biased Sample Space). A probability distribution over {0, 13 is called an E-biased sample space if bibs (X) S E holds for all non-empty subsets I S . m...
Note that the uniform distribution has bias O. We now state our construction for the neural network used in the kth iteration, (a(),, We recall that (6) denotes the label of vertex in the kth iteration.
Implementation of Neural Network. Our construction for (b) the following:
1. The input vectors of g((), which are of the form h (k-1) for the kth iteration, are each assumed to be a feature vector in 2Clog" log for sufficiently large constant C. The output of ((*) will also be a feature vector in 2 log", Our aggregation function ff will again be the summation function.
2. Let F be prime of size poly(n) which is at least 2n.
3. For each node v. (sk)) computes 2, (b. EweN(w) 1/ (k-1)) mod F where every entry of b is uniformly random in f 1}. Note EweN(ee 1/ (k-1) is the output of the aggregation f.
4. Let a' 10, for 1,..., C'log be vectors which are independently drawn from an e-biased sample space for a sufficiently small constant E.
5. The output (,(*)) will be a C log n dimensional binary vector where the t-th coordinate is equal to the 2,-th coordinate of the vector a'. In other words, ( = (z²(zx)) the -. coordinate of a!.
C'log where a((z,) denotes
Correctness of Construction. We now prove the correctness of our construction. We will refer to 2. computed in Step 3 of the construction as the index of v for the kth iteration. To prove the correctness of the above construction, it suffices to prove the lemma below which shows our construction satisfies Definition 1.1.
Lemma 3.1. Let (1 (k-1) E [v)) and (be (k-1) w E (w)) denote the multiset of neighbor- hood labels for vertices v and u respectively. If the multisets are distinct then the labels computed for u and u in the kth tteration are distinct with probability 1 - 1/ poly(n). If the multisets are the same then the labels are the same, ie., the kth iteration is successful according to Definition I.1.
We first need the following auxiliary lemma about e-biased sample spaces, proven in Section C.
7

---

Lemma 3.2. Let D be probability distribution over {0, 1 that is an E-biased sample space. Then, for any z, E n such that x + y, Fa-Dlaa, 2) = (a. y) S 2 5.
Note that this lemma is necessary, (over integers), not with binary vectors modulo 2.
will be computing dot products of with integer vectors
We are now ready to prove Lemma 3.1.
Proof of Lemma 3.1. Let x' = EweN((n) tww (k-1) denote the input for v and analogously, define
y' EweN(w) 1o (k-1) to be the input for u. We first show that if (n@ w E (N(v) is not equal to (as multisets) (h(--), : w E [u)) then x' # y' with sufficiently large probability. We further consider the case that & 2 2 since for k = 1 (the first iteration), the statement follows since all node labels are initialized to be the same. Let z be the indices computed in Step 3 of iteration A 1
(which are used to construct the node labels he (R-1) in iteration & 1). Note that there is one to one mapping between z and h (k-1), Thus we can assume (z/y : E (V() # {z4= w (())
without loss of generality.
Let à' be the first E- bibased vector used in the previous neural network (((=1)) Note that the first
entry of x' is equal to EweV(()) à' (z i.e., it is the dot product of à with suitable vector x which is the sum of one-hot encoding of the neighborhood of V. The same statement is true for y': the first entry of y' is equal to the dot product of à' with a vector y which represents the one-hot encoding of the neighborhood of u. This is because we computed the index zy of every node in the previous iteration, as defined in Step 3 of the construction, and passed along the coordinate of āt which corresponds to this computed index. By assumption, we know that o y. Therefore by Lemma 3.2, we have that Pa ((=)) = (v/)1 = Pa ((a), .I) = (@) })) S 2/3 for suitable E. By independence of vectors ä', it follows that Ppax' = v'l I (2/3) C log n S 1/ 1/poly(n) for a suitable constant C O.
We now condition on x' + y'. Without loss of generality, suppose that their first coordinates, z' and v1. differ. We know 2'1 A 11 mod F since 2'1 A 1/1 they are both non-negative and bounded by ni, and |a - 1/1 S ((n) whereas F is a prime at least 2n. It follows that the probability of the event ((x' y'), b) 0 mod F is at most 1/F. To see this, condition all the entries of except bj. Then (a' - y/) 1 bj must be equal to a specific value modulo F for ((x' - y'), b) = 0 mod F to hold, as desired. We now condition this event which equivalently means condition 2, # 2u (see Step 3 of the construction).
Now our task is to show that 1x) f kk) with sufficiently high probability. The first coordinate of h(())) is equal to (a', ez..) where a is the first e-base vector considered in Step 4 of the construction and 6z,, is the basis vector in dimension C'log n which has a 1 entry only in the 2, coordinate and O otherwise. Therefore by Lemma 3.2, we have that, Pa-I(nh
(A(( )1] P., ((a c...) =
(a", c...)l < 2/3 for a suitable choice of E since Cz,, and Cz2 are distinct. By independence of vectors a', it follows that ?(
(k) )= < (2/3) Clogn < 1/ poly(n) for suitable constant C >>> 0. This exactly means that the node labels of u and v in the next iteration are different with probability at desired. Lastly, it is clear that if the multiset of neighborhood labels of
least 1 - 1/ poly(n),
and v are the same, then x' = y' and it's always the case that h = 1 (k)
Complexity of the GNN. We now analyze the overall complexity of representing (k)) as a ReLU neural network. First we state guarantees on generating e-based vectors using a ReLU network. The following corollary is proven in Appendix C.
Corollary 3.3. Let = Olog F log(L/s)). For every e and F, there exists an explicit ReLU network C: : {0, 1]- + {0, 11"² which takes as input s uniform random bits and an index E F and outputs the ith coordinate of an s-biased vector in {0, 13 C uses O(lo F') bits of precision and has poly(s) hidden units. More generally, given an integer parameter & >> 0, the function can be computed with n (11t)) polylog(n) hidden units and O(t) depth.
We can now analyze the complexity of our construction. The complexity can be computed by analyzing each step of the construction separately follows:
8

---

1. For every node v, the sum of feature vectors of neighbors from the prior iteration,
E EwEN( (k-1), returned by the aggregate function f.
The inner product with the random vector b Step 3 of the construction can computed using one layer of the network. Then computing modulo F can be constructed via Theorem 2.2.
3. Given the inner product value &u which is the output of Step 3 of the construction, we compute all of the Ollog n.) coordinates of he (R) in parallel. We recall that each coordinate of h. is indexing onto (loo n) e-biased random vectors and we use the same index for all vectors, namely the 2,-th index. This can be done as follows. We first have Oloog n) edges fanning-out from the node which computes 2.. For all t = 1,..., O(log n),, the other endpoint of the t-th fan-out edge computes the value a' (z,,) where a' is the t-th e-biased vector as stated in Steps 4 and 5 of the construction. This can be done by appealing to the construction guaranteed by Corollary 3.3. The
result of this computation is exactly h.
Altogether, we have proven the following theorem.
Theorem 3.4. There exists construction of ie which performs a successful WL iteration according to Definition 1.1 with p S 1/ poly(n). & has depth Ologn), (poly (log n)) hidden units, and requires Ollog n) bits of precision. All labels in all iterations are binary vectors in {0, 13 (10og n), More generally, given an integer parameter > O, the function can be computed with n ((21)) polylog(n)
hidden units and (() depth.
4 Lower Bounds
We complement our construction with lower bounds on the label size and number of ReLU units required to simulate the WL test. We outline these two lower bounds below and defer the full details to Appendix D.
Message Size. Recall that in our construction, the message (label) size was (logn) bits. Via communication complexity, we give corresponding lower bound. In particular, we construct graph on which any (randomized) communication protocol which simulates WL as in Definition 1.1 must send at least 12(log n.) bits along one edge of the graph. As message- pasgggg-sssingggg GNNs are specific class of communication protocols, this immediately implies that the message sizes must have n)) bits, so our construction is optimal in that respect.
The hard instance is formed by a graph which is a collection of disjoint star subgraphs of sizes ranging from 2 to (Vvn). In order to perform a valid WI. coloring, each node must essentially learn the size of its subgraph, requiring Ω(log( vn)) = Milog n) bits of communication. In addition, this must be done in only iterations the depth of each subgraph is 2, so some node must send O(log n)) bits to its neighbors in a single round. See Appendix D. for the full details and proof.
Number of ReLU Units. In order to show a lower bound the number of units needed to implement a successful WL iteration, we rely on prior work lower bounding the number of linear regions induced by ReLU network (for instance [MPCB14]). In particular, these works show that ReI.U networks induce a partition of the input space into convex regions (where N a function of the size of the network) such that the network acts as a linear function restricted to any given region. Using these results, we describe a fixed graph and a distribution over inputs to the neural network !! (k-1)) for all u E V (sums of the labels from the previous round) which includes ((F) potential special pairs of nodes (where F is defined such that inputs s(k-1) E [F]' for some t). For each such pair u, v, their neighborhoods (u), N NNv) have different multisets of inputs, but both multisets of inputs sum to the same value. We show that if the number of linear regions is small, N = o(F). then it is relatively likely that u, e will be in the same linear region and thus their sums will collide: s(k)) ss!k) even while their neighborhoods had distinct inputs in the (A: 1)st round.
This immediately gives a 2llog F) lower bound on the number of ReLU units (and thus number of parameters) with more refined depth/width tradeoffs given in Appendix D.2.1. Note that F the size of each coordinate in the sum of labels. Even if the labels are binary, F can be as large as depending on the max degree in the graph, which implies a 22 n) lower bound on the number of ReLU units. See Appendix D.2 for full details and proof.

---

Experiments
To demonstrate the expressivity of our construction, i.e., that our small-sized GNN reliably simulates the WL test, we perform experiments both synthetic and real world data sets. Common all of our experiments that we start with some graph = (V, E) (either real world or generated with respect some probability distribution). We then simulate perfect run of the WL test on G where any two nodes which receive different multisets of labels in iteration k -- 1 get distinct labels in iteration A with probability time, the node labels induce partitions of V where two nodes are in the same class if they have the same labels. Denote the partitions after k-iterations using the perfect simulation and our construction respectively by Pk and P Letting ko be minimal such that Pko-1 = Pkg (at which point the WL labels have converged), we consider the implementation using our GNN successful if Px = P/ for all & < ko, i.e., if the the simulation using our implementation induced the same partitions as perfect runs. For all of our experiments it turned out that ku I (see [BK22] for a discussion of this fast convergence).
well run of our construction from Section 3. At any point in
Sparse Erdos Renyt Graphs
Stale Free Grachs
Slogtn|
2.3log(r)
Results
16
Result
Sration of Succoss
Mossage Stew
12
6.2
0.0
107
10
10'
10
35.0
17.5 20.0
22.5 25.022.55..55
Messsag
(a)
(b)
(c)
Figure 2: Plots of our experimental results on Erdös-Rény' Rényi graphs, scale free graphs, and the real world Cora graph. The vertical blue lines in (a) and (b) are the empirical standard deviations over the 5 independent samples of random graphs. Note that the r-axes in (a) and (b) are logarithmic.
Sparse Frdős-Rényí Graphs We generated Erdōs-Rényi random graphs G(n,p) p) with p= 20/ for a varying number of vertices n. For each value of n, we generated five such graphs and for cach of these five graphs, ran 10 independent trials of our GNN implementation with message sizes t = 2, Averaging over the five graphs, we report the minimal such that at least 70% of the 10 iterations successfully simulated the WL test. See Figure 2a. The average message size needed to achieve this is approximately 3 3og n where the logarithmic dependence on n is as predicted theoretically and significantly improves the linear message size required for prior constructions.
Scale Free Graphs We generated samples of the scale free graphs from [BBCR03] with varying number of vertices n using the implementation from [HSS08]. Our experiment design was the same as for Erdös Rényi random graphs. See Figure 2b.
Cora Graph We finally ran experiments on the real world graph Cora² which is the citation network of n = 2708 scientific publications. We simulated our GNN with varying message lengths, for each message length reporting the fraction of successful runs of 30 independent trials. See Figure 2c for plot of the results. We see that with message length 35, all of the 30 trials successfully simulated the WL test.
Acknowledgements Anders Aamand is supported by DFF-Internntional Postdoc Grant 0164- 00022B from the Independent Research Fund Denmark. This research was also supported by the NSF TRIPODS program (award NMMS-202248)) NSF award CCF-2006664, Simons Investigator Award, MIT-IBM Watson AI Lab, GIST- MIT Research Collaboration grant, NSF Graduate Research Fellowship under Grant No. 1745302, and MarkW Engineering Fellowship
"Since our goal is to test whether protocol correctly simulates WL test with small messages, implementing the actual GNNs but instead we are simulating their computation. Further, for simplicity, we replaced the e-biased sample space with random string, which guarantees e https://gnphaanneettttss.memeeee
10

---

References
[ACGL21] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In IJCAI, 2021.
[Bab16] László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pages 684-697, 2016.
[BBCR03] Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. Directed scale- free graphs. In Proceedings of the Fourteenth Anmual ACM-SIAM Symposium on Discrete Algorithms. SODA '03, page 132-139, USA, 2003. Society for Industrial and Applied Mathematics.
[BFZB22] Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Im- proving graph neural network expressivity via subgraph isomorphism counting. IEEE Trunsactions on Pattern Analysis and Machine Intelligence, 2022.
[BGRR21] Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. Advances in Neural Information Processing Systems, 34, 2021.
[BK79] László Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pages 39-46. IEEE, 1979.
[BK22] Franka Bause and Nils M. Kriege. Gradual weisfeiler-leman: Slow and steady wins the race. CoRR, abs/2209.09044 2022.
[BKM+20] Pablo Barceló, Egor Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan- Pablo Silva. The logical expressiveness of graph neural networks. 8th International Conference Learning Representations (ICLR 2020), 2020.
[CCK+21] Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. IJCAI, 2021.
[CMR21] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. Advances in Neural Information Processing Systems, 34, 2021.
(CV Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
[FLM+19] 19] Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. International Conference on Learning Represen- lations, 2019.
[GMP21] Floris Geerts, Filip Mazowiecki, and Guillermo Perez. Let's agree degree: Compar- ing graph convolutional networks in the message-passingg framework. International Conference Machine Learning, pages 3640-3649, PMLR, 2021.
[Gro21] Martin Grohe. The logic of graph neural networks. In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (IJCS), pages 1-17. IEEE Computer Society, 2021.
[HSS08] Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. In Gaël Varoquaux. Travis Vaught, and Jarrod Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11 15, Pasadena, CA USA, 2008
[HV06] Alexander Healy and Emanuele Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. In Annual Symposium on Theoretical Aspects of Computer Science, pages 673.683. Springer, 2006.

---

[HV21] Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the weisfeiler-lhhman test and its variants. ICASSP 2021-2021 IEEE International Conference on Acous- tics, Speech and Signal Processing (ICASSP), pages
IEFF, 2021.
[HYL17] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances neural information processing systems, 30, 2017.
[Jeg22] Stefanie Jegelka. Theory of graph neural networks: Representation and learning. arXiv preprint arXiv:2204.07693 2022.
[LGDD19] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In Interna- tional conference on machine learning, pages 3835-3845. PMLR, 2019.
[Lou19] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference Learning Representations, 2019.
[MBHSLI9] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[MBM 17] Federico Monti, Davide Boscaini. Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 5115-5124, 2017.
[MFK21] Christopher Morris, Matthias Fey, and Nils M Kriege. The power of the weisfeiler- leman algorithm for machine learning with graphs. IJCAI, 2021.
[MLM*21] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story far. arXiv preprint arXiv: 12.0999. 2021.
[Mon17] Guido Montúfar. Notes on the number of linear regions of deep neural networks. 2017.
[MPCB14] Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. Advances in neural information processing systems, 27, 2014.
IMRF+ 19] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman Go Neural: Higher- Order Graph Neural Networks. 19/AAA 19/EAAI 19. AAAI Press, 2019.
[MSRR19] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Re- lational pooling for graph representations. In International Conference on Machine Learning, pages 4663-4673, PMLR, 2019.
[NM20] Hoang Nguyen and Takanori Maehara. Graph homomorphism convolution. In Inter- national Conference on Machine Learning, pages 7306-7316. PMLR, 2020.
[QSMG17] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. Proceedings of the IEEE conference on computer vision and pattem recognition, pages 652-660, 2017.
17] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. the expressive power of deep neural networks. In international conference on machine learning, pages 2847-2854 PMLR, 2017.
[STR18] Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pages 4558-4566. PMLR, 2018.
[SYK21] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 333-341. SIAM, 2021.
12

---

[Tel16] Matus Telgarsky. Benefits of depth in neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 1517-1539. Jogg 2016.
[RWG21]] Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with 1d convolutions on random walks. arXiv preprint arXiv:2 1eee22002.87788 2021.
[VLF20] Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equiv- ariant graph neural networks with structural message-passing. Advances in Neural Information Processing Systems, 33:14143-14155 2020.
[WKK* 20] Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, and Thierry Langer. A compact review of molecular property pre- diction with graph neural networks. Drug Discovery Today: Technologies, 37:1-12, 2020.
[WL68] Boris Weisfeiler and Andrew Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Mauchno-Technicheseee Informatsiya, Ser 2, no. (1968), 12-16 (in Russian), 1968.
[XHLJ19] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OpenReview.net, 2019.
[YHC+18] 18] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender sys- tems. In Proceedings of the 24th ACM SIGKDD international conference knowledge discovery & data mining, pages 974-983 2018.
[YYZ18] Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional net- works: a deep learning framework for traffic forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 3634-3640 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This paper is focused on fundamental research on graph neural networks with no direct social impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
13

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "x5aAuSZiFm7", "reviewer": "Reviewer_Kh1P", "summary": "This paper proposes a collection of GNN constructions that can simulate the Weisfeler-Leman algorithm with high probability. Prior works showed the equivalence between the WL algorithm and GNNs using mainly the universal approximation theorem for MLPs, in order to prove that MLPs can be used to approximate injective message and update functions, so as to simulate the hash functions used in the WL algorithm. However, as the authors of the present manuscript note, this construction might in the worst case necessitate an exponential number of parameters for the MLP. To this end, the authors devise a special GNN construction, that can simulate the hash functions using $O(poly(logn))$ random parameters (as a warm-up they show a simple construction that requires a $O(poly(n))$ number of parameters) and $O(logn)$ bits of precision, and will succeed with probability at least $1 - 1/O(poly(n))$. Finally, the above results are complemented with lower bounds: the authors construct a graph, for which any communication protocol requires at least $\\Omega(logn)$ bits of precision to simulate WL, while a $\\Omega(logn)$ lower bound is also given for the number of ReLU units.\n", "questions": "- What does the lower bound on the number of the relu units imply about the overall number of parameters?\n- Perhaps a relevant work (involving communication capacity) that the authors might want to discuss is the following:\nLoukas, \"How hard is to distinguish graphs with graph neural networks?\", NeurIPS’20\n- One suggestion to better motivate the paper, would be to include a small experimental section. This may include any potential shortcomings of GNNs to simulate WL, dependence on the number of parameters, scaling with the number of vertices, contrasting between random and learned GNNs etc. Also, here it might be interesting to observe if GNNs are actually simulating WL, or if they simply manage to distinguish the same non-isomorphic pairs.\n- Is it possible that the ability to simulate WL correctly can be a useful inductive bias  (e.g., in order to counteract the oversquasing phenomenon) and lead to better generalising GNNs (this might be also an interesting motivation)?\n\n- Minor: L41: MFK21 → MRF+19\n", "limitations": "- As I mentioned above, a discussion about the broader scope, including the limitations (especially about how this theoretical construction can be useful in practice) is missing.\n- This is a purely theoretical paper - no potential negative societal impact can be foreseen.", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- This paper devises a intricate construction of a GNN that can simulate the WL algorithm with an exponentially smaller size than previous constructions.  From a theoretical standpoint this result is interesting since it shows that GNNs can be easily used as a fast heuristic for graph isomorphism (replacing WL), without the need for large parameter sizes in order to obtain strong guarantees of validity.\n- Compared to previous works that simply used the universal approximation theorem to prove that GNNs can have injective message and update functions, this paper uses a special construction to approximate hash functions, in order to reduce the required number of parameters, which might be of independent theoretical interest. Of independent interest might also be the constructions for the lower bounds, which provide further insights.\n- Although the paper is mostly directed to an audience versed in complexity theory and involves complicated concepts that the ML audience will be less familiar with, the authors have put a good effort to present their results in a clear and concise way, so that the interested reader can understand the high-level message. \n\n# Weaknessess\n\n- Most of my important concerns regarding this paper have to do with its relevance and practical significance. Although, I do believe that the constructions are theoretically interesting per se, it is unclear to me how this paper might benefit the GNN community and what insights we can gain from it. My impression is that the presentation of the theoretical results is kind of “dry” and the broader scope of the paper is unclear. In my opinion, a discussion is very much missing from the paper in order to better place it in the GNN context and explain its benefits to the community. I have several questions w.r.t. the above:\n- The premise of the paper has to do with exactly simulating the WL algorithm. Could the authors explain why this is important per se? My intuition is that what we are usually mostly interested in is being able to distinguish the same non-isomoprhic graphs as the WL test, rather than simulating its exact iterations. Is it possible that we can obtain better bounds in this scenario? Are there cases where we will fail to distinguish a pair of graphs unless exactly simulating the WL algorithm?\n- The paper presents worst case results. However, it has been widely observed in the GNN community that even random GNNs of small size (definitely not exponential) can be used in order to distinguish non-isomorphic, WL distinguishable, pairs of graphs. This naturally leads to the following question: in which circumstances are the results of this paper relevant? Is it the case that for real-world graphs (or for known graph distributions, e.g., Erdos-Renyi) we can obtain even better bounds? I believe that such a question would have been much more influential across the community.\n- If I am not mistaken, throughout the paper, the authors use integer representations. Is it possible that the results can be improved with continuous representations (after all this is what we use in practical NNs)?\n- Finally, it is my impression that this construction needs to be enforced in a NN and cannot be learned, which kind of defeats the purpose of having a NN in the first place. This is because, either the functions to be implemented are hard to learn with SGD (e.g., the mod function) or are not even differentiable (e.g., the indexing in step 5 L270). ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pn1Ilqt_b0v", "reviewer": "Reviewer_j9Sq", "summary": "The paper studies the complexity of simulating the WL test with message-passing neural networks. The fact that this can be done is well known since 2019, but an efficient computation was lacking. The main result of this paper is a construction of a neural network implementing the local update function in polylog(n) parameters using feature vectors of size lo O(log n) bits. This is significantly better than previous constructions but comes at a cost of a certain probability of failure since the construction relies on random weight initialization. In addition to this main result, the authors also propose three other results: (1) A simpler and less efficient construction (as the first step toward efficient architecture); and (2) two logarithmic lower bounds on the feature length and the size of the network.      \n", "questions": "\n\nRelation to ML - the way this paper is currently written emphasizes the construction and its complexity. Since NeurIPS is conference on machine learning and other close fields, I feel it would be great to add a discussion on the meaning of this result to ML people: can we leverage this result in order to modify existing MPNNs? To propose new ones? How hard is it to learn weights leading to this construction (which is heavily based on discrete quantities)? How is the randomness related to the learning process? (to be fair, most papers that belong to this type of paper ignore my last questions)\n\n– what can we say about deterministic construction? Are the lower any lower bounds?\nLimitations", "limitations": "Properly addressed ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "– The paper is very well written, especially for a theoretical paper. I enjoyed reading it.\n– Interesting problem and results - the ability of MPNNs to simulate the WL test is a significant result in the GNN community. Nevertheless, the actual constructions proposed till now were not efficient. I am happy to see a paper that targets this important but often overlooked problem. \n– Uses methods that are not often used in the GNN community - the paper used methods and ideas that come from the TCS community. I think it is a great addition to the toolbox of the GNN community.\n\nMinor\n– lines 160-165 could be improved. I lost the authors there.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "giu4hYr0cFa", "reviewer": "Reviewer_epxq", "summary": "The authors provide a new theoretical GNN construction that is able to simulate a 1-WL test with fewer parameters and smaller messages, by borrowing some ideas from randomized algorithms.", "questions": "What issues do you perceive implementing this algorithm in practice? Or any learnability issues?\n\nCould you provide a theoretical estimate (a plot) of when  the poor scaling of traditional GNNs (GIN) would start to matter (how many nodes should there be in a graph)  if we assume use of real-valued embedding vectors (and are generous w.r.t. what a GNN/NN can learn)? Essentially, could you estimate the constants hidden in the O notation for message size.\n\nOf course what would really convince me is a practical implementation of the proposed construction and a synthetic experiment, which shows a better scaling of the proposed approach (at least with fixed weights but ideally learned ones) compared to a traditional GNN woth learned weights. ", "limitations": "I do not perceive any negative societal impact and any limitations besides the drawbacks meantioned above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I really liked, that the authors decided to look at GNNs like a true algorithm as one does in theoretical computer science. I also liked the introduction of randomization and use of ideas from randomized algorithms. I think this can be a fruitful avenue for design of more efficient neural network architectures in general.\nThe writing was excellent and theoretical analysis is sound. I also appreciate the inclusion of the lower bounds.\n\nHowever, the man problem of the paper is that it is very far removed from any practical considerations. Authors do not implement their GNN or do any experiments.\nWhile their approach results in smaller message size (which is one of the main benefits of their approach) it's unclear to me how much it would matter in practice. \nGNNs use real-valued embedding vectors, that even with modest vector lengths already provide us very large effective bit count. It's possible that we do not run into any message size problems for any real-world-sized graph (graphs used in graph classification are rarely larger than a few thousand nodes).", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept