Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary:
The authors prove several statements about the expressiveness of different classes of graph neural nets (GNNs): conventional message passing networks, linear GNNs (LGNN) and “folklore GNNs” (FGNN). The novel theoretical contributions include analysis of expressiveness of FGNNs that use tensors of arbitrary order in terms of comparison to the Weisfeiler-Lehman tests; a characterization of the functions that these classes of networks can approximate; universality of FGNN as the tensor order goes to infinity. The results are based on a general Stone-Weierstrass-like theorem for equivariant functions. Prior universality results can be recovered as special cases. The authors have a simple experiment that show in a limited setting that a practical implementation agrees with the theory.

Strengths:
-	The paper and appendix are very well written and relatively well understandable for me, unfamiliar with universality proofs. Particular examples of clear writing include: the statement of Theorem 4 is clearly explained below the theorem; providing Example 16 directly after Corollary 15 aids exposition; using example 17 to motivate prop 18. 
-	The authors use a very general statement (Thm 20) to derive their results, making them generally applicable.
-	The authors derive a substantial number of expressiveness results from the general theory.

Weaknesses & suggestions for improvement:
-	The main paper only sets up the problem and states the main results, while all theoretical contributions are done in the appendix. The main paper would be more self-contained if some more intuition for the proofs was given in the main paper.
-	The experiments seem to not compare to LGNN. Adding this comparison would help making an empirical argument for why FGNN is best. 

Recommendation:
Although I am not very familiar with the field of universality proofs, the paper appears to me to be a very solid contribution to the field and I recommend publication.
 
Minor points / suggestions:
-	In several instances, the authors write “a compact” without a noun. Is this conventional language?
-	Below Eq 2, there is an F without subscript. Is this the same for all layers?
-	In App C.3, in the second line of the equation, are there suffices missing on the left-hand side?
-	Sec 4.3, first sentence, “the set invariant”, missing “of” 
-	Sec 4.3, typo “To clarify the meaning of theses statements”
-	App D.3: typo “as every function satisfy” should be “satisfies”
-	Example 16, typo “is able to learn function” should be plural
-	App D.3, proof of Corollary 15: define when a class separates a set around “clearly separates X_\mathcal{F}”. Presumably means same as separates points?
-	Eq 17, Define S \cdot \mathcal{F}, presumably as the scalar-vector product of the outputs of the functions? 
-	Corollary 19, assumption 3, what does “pairwise distinct coordinates” mean?
-	App D.3, typo “For an equivariant function, for any” missing $f$
-	Example 21, \mathcal{C}_{eq} should be \mathcal{C}_E? Happens later more.
-	Lemma 24, define R{X_1, .., X_p] as polynomials

### Post rebuttal
I thank the authors for their response. My previous rating still applies.
review_title: Solid theoretical contribution to universality proofs of equivariant networks

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: #### Goal

The paper describes the approximation power of certain types of graph neural networks.  It considers Message Passing GNNs (MGNNs), and two GNN-type methods proposed by Maron et al., k-FGNN and k-LGNN.

The main challenge with some of the current expressiveness analysis of neural networks is their reliance on discrete attributes. This line of work shows how these can be extended to a general setting.

#### Quality

- This is a great paper, well written, nice appendix, on an interesting topic. The only drawback is that the approach was narrowly applied to k-FGNN and k-LGNN, comparing them to k-WL approaches.

- My main concern is being too narrowly focused on k-FGNN and k-LGNN without a proper empirical comparison with other more expressive competing methods. For instance, it does not even discuss alternative approaches using group averaging. I think the paper would significantly broaden its audience if there is a comparison with novel k-ary group averaging approaches (e.g., Chen et al., 2020, Murphy et al. 2019) in the empirical section. 

#### Clarity

The paper is clear and well-written. The notation follows the standard notation used in prior work.
In one aspect the notation could improve: \subset should be replaced by \subseteq to avoid confusion, and be more in line with the use of \subsetneq. I was not sure what \subseteq meant until I saw \subsetneq. It is unfortunately but different branches of mathematics use \subseteq differently and the symbol should be avoided altogether. 
The appendix is well organized, with an index that helps the reader find proofs and definitions.

#### Originality
- The work follows from prior work of Maehara & Hoang (2019), Chen et al., 2019, Geerts (2020a), etc.
- There is some novelty in the proof approach
- New results related to k-FGNN and k-LGNN.

#### Significance

The work is of interest to a narrow sub-community working on k-FGNN and k-LGNN. The MGNN results were known but recovered here in a different way (i.e., there is value). The k-FGNN and k-LGNN results are new but also very narrow due to the sub-community size.

The empirical results essentially do not compare with any other alternative approach. Until the community is convinced that k-FGNN and k-LGNN can empirically compete with other approaches (e.g., Morris et al. 2019, Permutation group averages like  Chen et al. 2020, Murphy et al. 2019, among others), these methods will not see broad applicability. 

Chen, Zhengdao, Lei Chen, Soledad Villar, and Joan Bruna. "Can graph neural networks count substructures?." NeurIPS (2020).

Murphy, Ryan L., Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. "Relational pooling for graph representations." ICLR (2019).

#### Pros
- Solid theoretical work showing the expressiveness of k-FGNN and k-LGNN
- Interesting ports of ideas from other papers to improve proof techniques of current GNN papers

#### Cons

- The authors seem unfamiliar with group average approaches that increase the expressiveness of MGNNs. These can also be universal approximations. Permutation group averages like  Chen et al. 2020, Murphy et al. 2019, among others, have increased expressiveness of MGNN using the same MGNN architecture.  Since there has been a lot of recent activity related to these methods, this is a blind spot of this work. For instance, “Note also, that if the nodes are given distinct features, MGNNs become much more expressive Loukas (2019) but this is meaningless in some problems such as our graph alignment problem.” does not point to the fact that a simple group average approach would fix the issue. This way, the work feels unnecessarily narrow.

#### Typos:
- "test to express the discriminatory power of equivariant architectures For this" => "test to express the discriminatory power of equivariant architectures. For this"
- "Maron et al. (2018) Geerts (2020a)" => "Maron et al. (2018); Geerts (2020a)"

----------------------------------------

After rebuttal:

Thanks for the answers. I have raised my score even though I still think the paper could have done a better job at comparing against other methods.

- Regarding group-averaging methods for the equivariant case: It is a trivial extension, specially the approach of giving GNNs unique IDs and then averaging their representation, which (Loukas, 2020) shows it is universal (but (Loukas, 2020) did not consider averaging). Regarding training, it is always performed stochastically via data augmentation and Monte Carlo estimated in test. For the generalization error of the stochastic optimization, it is still unknown (some new results show promise (Chen et al. 2020) and (Lyle et al. 2020)) in the same way that the generalization performance of other universal methods is still unknown.

- Chen, S., Dobriban, E., & Lee, J. H. (2020). Invariance reduces Variance: Understanding Data Augmentation in Deep Learning and Beyond.
- Lyle, Clare, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem-Reddy. "On the Benefits of Invariance in Neural Networks." arXiv preprint arXiv:2005.00178 (2020).
- Loukas, Andreas. "How hard is to distinguish graphs with graph neural networks?." Advances in Neural Information Processing Systems 33 (2020).
review_title: Interesting paper with fixable deficiencies (Likely to advocate for it)

final_score: rating: 6: Marginally above acceptance threshold
review_content: 1. Summary:

This paper compares the expressive power of three types of invariant and equivariant GNNs against the Weisfeiler-Lehman (WL) tests, proves function approximation results for these GNNs, and demonstrates that 2-FGNN_E works well for the quadratic assignment problem.

2. Clearly state the recommendation (accept or reject) with one or two key reasons for this choice:

I am slightly leaning towards recommending a rejection to this paper, with the main reason being that I am not sure if the contributions are sufficiently significant, as I will elaborate below.

3. Arguments for the recommendation and questions for the authors:

a) It is nice to establish and summarize a thorough comparison of the expressive powers of different GNN families as well as k-WL, and also to incorporate not only invariant but also equivariant GNNs into consideration. However, among the results in Section 4.2, the only novel one is the equivalence between k-FGNN and (k+1)-WL, which, one may argue, is also not surprising considering the equivalence between k-FWL and (k+1)-WL. The value of 2-FGNN has also been demonstrated by the work of [1].

b) The overall framework for the comparison of expressive power as well as function approximation resembles that of [2], which characterizes the expressive power of GNNs and WL tests by the sigma algebra they induce on the space of graphs, and also establishes an equivalence between the ability to distinguish non-isomorphic graphs and the ability to approximate invariant functions. Hence, the authors may want to elaborate more on the connection between this work and [2].

4. Additional comments:

The authors claim that 3-LGNN or 2-FGNN can count the number of 6-cycles, which is an improvement upon the result in [3], which implies that 6-LGNN can count 6-cycles. Technically, however, it is only known (by [4], to my knowledge) that 3-WL can count the number of times 6-cycles appear as subgraphs of a graph, but not induced subgraphs, whereas [3] is concerned with the counting of both subgraphs and induced subgraphs. Therefore, I would recommend that the authors make this statement more precise.

References:

[1] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks.

[2] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs.

[3] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures?

[4] Martin Fu ̈rer. On the Combinatorial Power of the Weisfeiler-Lehman Algorithm.


=== Post Rebuttal ===

I appreciate the careful response provided by the authors, which reminds me of the significance of extending existing theoretical results from invariant to equivariant models. Therefore I have raised my score by 1 point.
review_title: Review

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: post-discussion:
I read the author's response and other reviews. I still think this is a very strong submission and would like to see it accepted.
I encourage the authors to add a section discussing their generalization of SW theorem + Theorems 31,32 as the authors suggested. another small point: I couldn't easily find the definition of "stable by concatenation".


Summary: 

The paper studies the expressive power of several classes of recently suggested models: message passing neural networks, Linear GNNs, and Folklore GNNs. Understanding the expressivity of GNNs is a timely and important topic since unlike other neural architectures as fully connected networks, the most widely-used models today, message-passing networks, are not universal. The paper first formally defines the three model classes mentioned above. The paper then reviews previous results on the separation power of these models (can a model tell the difference between two non-isomorphic graphs) and summarizes them, as well as new results they obtain, in prop. 3. Theorem 4 then connects these separation results to the approximation power of the model classes by a novel adaptation of a recently introduced generalization of the Stone-Weierstrass theorem.  The authors conclude the paper with an experimental section showing that folklore GNNs perform significantly better than other models in solving the quadratic assignment problem, which supports the theoretical claims


Strong points:

New strong results: the paper closes the following knowledge gaps: (1) Folklore GNNs: k Folklore GNNs are as strong as k+1 WL, (2) Equivariant separation: connecting the separation power of equivariant (rather than invariant) models to their equivariant WL counterpart (3) Link separation results to approximation results: the authors suggest a generalization of the stone Weierstrass theorem and use it to show new approximation results.    
The paper succinctly summarizes the current results on the separation power of various GNN classes.
The paper Introduces new tools from approximation theory. These tools seem important and will be useful for future papers targeting the expressive power of invariant and equivariant deep models
Interesting experimental results. Showing for the first time that more expressive models  (2-FWL) substantially outperform previous (2-WL) models on an important task.

Weak points:

None. I have several comments on the exposition. See below. 
In addition, I would like to ask the authors to explicitly and succinctly state their generalization of the Stone-Weierstrass theorem for general symmetries and deep models so it would be easy for future work to use it. Please do so for both invariant and equivariant case, and consider stating it in the paper itself.



Recommendation: 

This is a high-quality paper with several strong contributions as listed above. Most importantly, the paper proves several important results on the expressive power of GNNs and introduces useful mathematical tools that I am sure will be used by the community. Hence, I strongly encourage the acceptance of this paper (and would also recommend it as a spotlight/oral presentation).

Minor comments:

* Can the authors comment on “Building powerful and equivariant graph neural networks with structural message-passing” (Vignac et al. 2020). Specifically, Theorem 2 shows that their models can separate any pair of non-isomorphic graphs while using only second-order tensors
* “So in terms of separating power, when restricted to tensors of order k, k-FGNN is the most powerful architecture. ” => Among the architectures considered in this paper.
* “For regular-grid graphs, they match classical convolutional networks which by design can only approximate translation-invariant functions and hence have limited expressive power. In this paper, we focus instead on more expressive architectures.” => I believe that mentioning the relation between GNNs and 2-WL here is a better example of the limited expressive power of GNNS.
* “Note that 2-WL solves k-cliques for k <= 6 (Fürer (2017)) so that these networks are probably not comparable to 2-WL.” => As far as I know 2WL cannot detect triangles. Please explain.
* k-FWL: maybe write 2 FGNN layers explicitly and discuss matrix multiplication connection?
* Appendix D is written really nicely with good examples
* Algebras are closed under multiplication but sets of neural networks are not (although products can be easily approximated in most cases). I believe this gap is filled in Appendix D but would like to ask the authors to explain it in the main text.
* The paper has several typos.

review_title: Interesting topic and multiple strong contributions

Meta-review: This paper is concerned with the ongoing research program of mapping the approximation power of different GNN architectures. It provides significant advances in the study of equivariant GNNs and nice extensions in the invariant case by closing existing gaps between distinct GNN families. 
All reviewers agreed that this is a strong submission with substantial new theoretical results. The AC recommends a strong acceptance. 
Decision: Accept (Spotlight)