Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.      

strengths_and_weaknesses: – The paper is very well written, especially for a theoretical paper. I enjoyed reading it.
– 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. 
– 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.

Minor
– lines 160-165 could be improved. I lost the authors there.

questions: 

Relation 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)

– what can we say about deterministic construction? Are the lower any lower bounds?
Limitations
limitations: Properly addressed
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.
The writing was excellent and theoretical analysis is sound. I also appreciate the inclusion of the lower bounds.

However, 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.
While 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. 
GNNs 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).
questions: What issues do you perceive implementing this algorithm in practice? Or any learnability issues?

Could 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.

Of 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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.

strengths_and_weaknesses: # Strengths

- 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.
- 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.
- 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. 

# Weaknessess

- 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:
- 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?
- 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.
- 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)?
- 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). 
questions: - What does the lower bound on the number of the relu units imply about the overall number of parameters?
- Perhaps a relevant work (involving communication capacity) that the authors might want to discuss is the following:
Loukas, "How hard is to distinguish graphs with graph neural networks?", NeurIPS’20
- 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.
- 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)?

- Minor: L41: MFK21 → MRF+19

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.
- This is a purely theoretical paper - no potential negative societal impact can be foreseen.
review_title: null

Meta-review: metareview: Even though there were some concerns regarding the limited practical consequences of these results to the ML/GNN community, the consensus is that the work makes a meaningful theoretical contribution toward the understanding of the connection between the Weisfeiler-Lehman (WL) Isomorphism Test and message-passing graph neural networks (MPNN). The work is well-written, stands out from the typical ML paper, and brings forth novel complexity bounds for the simulation of the 1WL-test with MPNN. 
confidence: Less certain
Decision: Accept