Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The paper compares graph neural networks (GNNs) with graph-augmented multi-layer perceptrons (GA-MLPs) where GA-MLPs are MLPs over nodes with additional node features computed over the graph. The paper contains theoretical results and experimental results for graph isomorphism testing and for node level functions. In the overflow of papers studying the expressivity of GNNs, the originality comes from the study of GA-MLPs and from the comparison for node level functions.

The paper is well written and there is a nice balance between theoretical results and empirical ones. Overall the results are not surprising but, to the best of my knowledge, they are not written elsewhere and the proofs are given. Thus, in my opinion, the paper is an original contribution to the field and can be published. I think that the paper could be improved by stating clearly (at the beginning of the paper) that the expressive power of GA-MLPs heavily rely on the choice of the operator family. And, along the paper, it should be made clear when considering GA-MLPs which class of GA-MLPs is considered (for instance, the class GA-MLPA is introduced in Section 6). Also, a synthetic comparison of the results for GA-MLPs w.r.t. the operator family could be given in the paper.

Please note that I read the proofs but I could not check them in detail.

Comments.

Introduction. In my opinion, there should be a more detailed description of graph operators used in the paper as well as the classes of GA-MLPs considered in the paper. Indeed, as such, the proposed contributions are not precise enough and can be misleading.

Section 3.3. Choices for $\Omega$ used in the paper should be presented here. Perhaps, classes of GA-MLPs should be named accordingly.

Section 4. Only consider GA-MLPs. Already Prop.1, Prop. 2 and last § show the importance of the operator family for GA-MLPs.

Section 5. Could be divided in two sections: one for GNNs and one for GA-MLPs. For GA-MLPs, again there is a clear hierarchy depending on the operator family.

Section 6.2. GA-MLP mean GA-MLPA ?

Section 6.3. The end of the section clearly shows the importance of the choice of the operator family and this should have been made clear before.


Details and Typos
* §Depth in GNNs. the their
* Not easy to find references in Appendix: ref to Appendix J is given before the proposition. Reference to Appendix E is not given.
* Section 5 §2. "analogous to the equivalence relations on $\cal G$ introduced in Section 4". I do not see such relations in Section 4.
* Appendix F is "Lemma 3"

review_title: Expressvity of graph MLPs with operators

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper studies a variant of Graph Neural Networks (GNNs) namely, Graph Augmented MLPs (GA-MLPs). Unlike in GNNs where nodes send messages to neighbors, and aggregate received messages via non-linear MLPs,  GA-MLPs rely on a single augmented embedding computed once and then applying an MLP to the new embeddings. The augmented embeddings can be obtained by applying linear transformations of the form A, A^2, …, A^k to the input representations, thereby capturing larger neighborhoods. The main goal of the paper is to demonstrate a fundamental weakness when using GA-MLPs for solving graph problems as compared to GNNs. Along these line the paper the main results can be characterized as follows:
       1) The paper identifies a specific instance of identifying non-isomorphic graphs that can be solved via a GNN but not by a GA-MLP framework.
       2) The paper provides an empirical and experimental evaluation of the representation power of GNNs versus Graph-Augmented MLPs, and show a separation in expressive power between the two in terms of node level functions on rooted graphs. Specifically, they show that the set of functions that can be represented by a GNN of a certain depth) grows doubly exponentially in k, as opposed to only exponential growth of the function class when considering a similar GA-MLP architecture. They also empirically evaluate the difference in performance of the two models on community detection and counting walk problems. 

To obtain the result in 1, the paper uses the recent equivalence between the computation in a depth-k GNN and the WL graph isomorphism test. The authors use this to construct two non-isomorphic graphs that the  WL test can distinguish using 2 iterations, but on which a GA-MLP will produce the same augmented embeddings. To obtain the result in 2, the authors count the number of distinct rooted trees that can be produced during the computations of a GNN and GA-MLP, and show a gap between the case of a GNN and a GA-MLP.

My main main concern with the paper is that it does not provide sufficiently rigorous findings on either the theoretical or the experimental front.   On the theoretical side, the paper establishes a somewhat expected performance gap between using a full GNN and an approximation such as a GA-MLP. Also it seems that the lower bounds for GA-MLPs only hold for the variant where the linear transformations are of the form A,A^2, and so on. Perhaps the authors can clarify this point?  Further there are no sample complexity or generalization bounds provided.   On the experimental front, it would have been much nicer to understand the tradeoffs in performance versus scalability or provide guidance on which models are more suitable for common, real-world GNN problems and applications. Counting attributed walks and community detection are not very representative problems for GNNs.
review_title: GNNs vs Graph-Augmented MLPs

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper is a theoretical analysis of two different classes of graph neural network: 1) GNN based on neighborhood aggregations (GNN) and 2) feature augmentation before MLP (GA-MLP).
The author contributions may be summarized as:
- exhibiting graphs/problems that may be handled by one method and not the other,
- giving an upper-bound on the number of equivalent clases induceds by linear GA-MLP in term of walks in a rooted tree.
- showing a gap in expressivness between GNN and GA-MLP
- showing that the choice of operator in GA-MLP is crucial and may have expressive power beyond WL.

Pros:
+ The paper is well written.
+ The theoretical analysis performed in the paper is new, non trivial, and very interesting, giving light on these two architectures.

Remarks:
- Section 3.1: shouldn't 2-EXP be: log log is polynomial (instead of linear)?
- Section 5, corollary 1: 'poly-exponential'?

Questions:
- How to go beyond linear operators in section 5?

Typos:
- after proposition 6: in words -> on other words
- few sentences without verb and missing punctuation in the appendix
- many references are incomplete, e.g. On the universality of invariant networks is ICML'19, What graph neural networks cannot learn: depth vs width is ICLR'20, etc
review_title: A very good paper about expressive power of GNN vs GA-GNN.

final_score: rating: 7: Good paper, accept
review_content: The paper presents a theoretical analysis to compare expressive power of Graph-Neural Networks (GNNs) w.r.t a class of simpler graph modles called  Graph-Augmented MLPs (GA-MLPs).   GNNs, especially deeper ones can be more difficult to train, and GA-MLPs have a simpler structure, significantly easier to train, and have been shown to have competitive performance on a number of tasks.  The paper dives deep into several problems (graph-isomorphism, node-classification, and community detection) and through innovative analysis shows that GNNs at least theoretically can have significant advantages for some of the problems. 

I enjoyed reading this paper, and in my opinion it's an important contribution to the field.  It's much more common to see papers that do only experimental validations  (which are of course very important in their own right), but little attempt is usually done beyond simple intuition.  This paper employs a number of technical tools to formally establish that for some problems GNNs (at least in theory, and conditioned on being able to learn them well) are significantly more expressive than GA-MLPs.  Some of the discussion can be made clearer,  but overall the paper is very well written.  Experimental validation is fairly basic, but helpful, however, it's mostly on stylized problems, and a general outlook for practical graph-ML problems would be helpful. 

Some comments: 
1)  The applications you consider (apart from community detection) seem quite stylized, (e.g. counting the number of certain types of walks from a node), so it would be nice to make some comments on what your analysis may imply  for typical practical applications of GNNs  (e.g. combinatorial optimization / graph or node classification / various tasks of using graph NNs in material science / chemistry  and give some comments of where do you feel GA-MLPs may be competitive.   
2) You also mentioned that there's recent progress in training deeper GNNs (using residual connections, and other tricks), so the outlook from the paper seems to be that for now GNNs are harder to tune, but more expressive, but the hope is that with advances in training that won't be an issue,  and then GA-MLPs will be less competitive, except on certain applications like graph-isomorphism?  
3)  In section 4,  it seems that distinguishing almost any pair of graphs drawn from a uniform distribution is not a very complex tasks -- as such pairs of graphs are likely to be very different.  Would it be harder to distinguish two graphs, where the second graph starts from the first and includes some modifications / transformations (e.g. swapping edges, e.t.c). 
4) last sentence before the summary in section 1 seems to have grammatical issues. 
5) It could be useful to give a short motivating sentence for Bethe-Hessian (e.g. is connected to Bethe-free-energy?)
6) What is laplacian sub-eigenspaces -- do you mean laplacian eigen sub-spaces?  (section  2). 
7)  I liked the analysis based on attributed walks , and rooted aggregated trees,  it may have some connections to computation-trees and walk-based type of analysis in graphical models literature: 
e.g. self-avoding walks for graphs and independent sets,  Chandrasekaran, Chertkov, Gamarnik et al, "Counitng independent sets using the Bethe Approximation",  and "Walk-Sums and Belief Propagation in Gaussian Graphical Models", johnson, malioutov, willsky, JMLR, 2006,  and  Yedidia, Freeman, Weiss, "understanding belief propagation and its generalizations". 

review_title: Very insightful theoretical analysis, it'd be helpful to attempt to interpret for more practical problems

Meta-review: This paper compares “Graph Augmented MLPs” (GA-MLP), which augment node features by a single aggregation of neighbors and then pass the resulting features through an MLP, to graph neural networks (GNNs). The paper establishes results on representational power of some GA-MLP models being less powerful than GNNs. While practitioners may not change their behavior as a result, the work appears carefully done, is novel, and reviewers are mostly in agreement that the paper is a nice read and good contribution to the field.
Decision: Accept (Poster)