Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The work presents a framework to categorize GNN aggregators based on their distinguishing strength. It connects the distinguishing strength to the rank of the aggregation coefficient matrices. Based on the findings, the authors present two GNN layers, ExpandingConv and CombConv, and evaluate them on some graph data sets.

Strengths:
- The paper is mostly well written.
- The formalization of distinguishing strength for aggregators is interesting and novel.
- The relation to the rank of coefficient matrices is a valuable insight and gives a new perspective to the effectivity of multi-head GAT.

Weaknesses/Questions:
- The paper lacks clarity in presentation / technical soundness, up to a point where I am not able to understand some details:
	- It is not clear what it means if f_aggr1 <= f_aggr2 "does not exist" (definition of incomparability)
	- In Lemma 1(ii), the formalization with "or" is confusing. It should probably be "f_aggr1 ⊗ f_aggr2 >= f_aggr1 or f_aggr1 ⊗ f_aggr2 >= f_aggr2".
	- I suggest to call the feature matrix for all nodes H, not h with specific indices, to avoid confusion. Currently, the index, or the lack of it, makes it either a matrix or a vector. Sometimes, h seems to be defined as the matrix containing features from all neighbors of u (as in the GCN definition). At other places, it seems to be just the vector of node u (Equation 3).
	- Page 5, rank(r) < min(rank(M), rank(h)) should probably be <=, otherwise rank(r) = rank(h) can't be achieved.
	- How can P be found? In order to construct it, a canonical order has to be defined and pi needs to be extracted from h. In fact, the permutation invariance does not seem to be relevant for the proposed approaches, since they both process all neighbors individually, have a sum in the end and do not impose an order by e.g. concatenation. Can the authors clarify, why this part is needed?
	- The set of results RES() is not clearly defined. The output of the aggregation is a matrix, not a set.
	- In general, Proposition 2 with the set formulations seems to be out of context and needs at least to be discussed.

- The experiments are not sufficient and do not show significant improvements:
	- Some strong competitors are left out in comparions: E.g. GAT and multi-head GAT.
	- The approach is only validated on a small set of data sets. Since the authors already use OGB, I wonder why only three data sets have been chosen. To me this looks like those three were cherry-picked.
	- Even on the small number of data sets, the results are mediocre.	

- It is unclear why CombConv is proposed. It needs more discussion. In the case of CombConv, the aggregation coefficients have rank 1, similar to a lot of other existing GNN operators, isn't that right? This would mean that CombConv disgards the main argument of the work (having rank > 1) in trade for efficiency.


All in all, I recommend to reject the paper in its current state. While there seems to be some novel insight in this work, which might be of interest to the community, I think the paper needs to be improved in (1) clarity of presentation and (2) experiments. Issues with (1) can maybe be fixed within the rebuttal period. I am not sure about (2). It probably depends on the actual performance of the proposed operator.

review_title: Some interesting insights, clarity can be improved, weak experiments

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: 
	This paper explores the representation power of graph neural networks. Unlike recent work on choosing among simple aggregation functions or combinations thereof, the authors here recognize that these aggregators are the bottleneck in the representation power and generalize simple aggregator functions commonly used in literature to an aggregation coefficient matrix. The paper supports this construction theoretically and also proposes two aggregators that satisfy the rank-preservation requirement for more expressive (distinguishing) GNNs.

Strengths:
* The theoretical results are strong in proving the bottleneck of aggregators (Lemma 1) and clearly contextualize popular existing methods into this result.
* Formulating aggregation in terms of a product with coefficients (indexed by a permutation) allows for framing existing methods and to connect the representation power with the rank of the matrix of coefficients.

Weaknesses:
* The study of the expressiveness of GNNs is a very popular topic right now and not enough context is provided about related work on this topic and other approaches, mainly focusing on GIN and GAT in the development and while a few other GNNs are considered in the experimental results, they are not discussed or explained enough.

Recommendation:
By framing the aggregation in terms of coefficients, the paper provides interesting connections between the rank of these coefficient matrices and the distinguishing power of GNNs.  While analysis and explanation of experiments is extremely limited, the theoretical developments are interesting and novel enough to narrowly recommend publication. Meanwhile, I do think the paper should undergo a reorganization to add more details about related work in the study of expressiveness of GNNs and analyze experiments more thoroughly.


Other comments and clarification needed:
* It’s not quite clear what it means for aggregators to be incomparable (top of page 3), ie what does it mean for the relative strength to “not exist”? This point could be clarified with an additional sentence in this “Distinguishing strength” paragraph. 
* The text on page 4 before Proposition 2 states that “… different M corresponds to different local structures. Therefore, the aggregation results of different aggregators must be different. However, it is not satisfied by existing GNNs.” This statement should be explained more and supported. 
* The details of the ExpandingConv layer overwhelm the paper. The details fo equation 4 and related text can be moved to an Appendix and explained in the main text at a higher level. This would free up space to add context of the paper’s contribution and more properly address the experiments. In the end, the ExpandingConv formulation is a refinement on multi-head GAT.
review_title: Limited context, but useful theoretical framing of distinguishing power of GNN aggregators

final_score: rating: 7: Good paper, accept
review_content: The authors propose two new layers for GNNs. CombConv and ExpandingConv are motivated by the insight that a GNN is only as expressive as the rank of the matrix that represents the coefficients of the aggregation function. To arrive at this statement, the authors formalize all GNNs as being composed of three steps: 1) generation of aggregation coefficients, 2) actual aggregation of the neighbourhood, and 3) feature extraction from the aggregation. Furthermore, it is shown that current approaches have very low distinguishing strength and that CombConv and ExpandingConv, by their construction, yield higher expressive power. 
The effectiveness of different components of their layers (e.g. Re-SUM, applying a ReLU non-linearity before summing when features are computed form the aggregation) are investigated in an ablation study. Additionally, proposed layers are compared with current approaches on 4 data sets. 

This paper constructs an interesting theoretical analysis of GNNs and finds the bottleneck of these networks to be in the coefficient matrix of the aggregation scheme. While I was not able to check all proofs, it seems like a solid mathematical analysis. What I find somewhat sobering is the experimental section. First, I am surprised that you only compare your method on four data sets and that you miss some reported by your comparison partners (such as IMDB, REDDIT, PROTEINS, etc.). I understand the Graph Kernel data sets are smaller, however, they’ve been used in comparable papers before. Second, while the title and the theoretical analysis promises much higher distinguishing strength, I am surprised that your performance gains are good but not outstanding. I wonder if you could construct a synthetic data set in which you can show how you break the expressive bottleneck in practice. Would it make sense to compute the rank of M for different networks (including yours ((it is not guaranteed it is $s$, right?)) and plot it as a function of predictive performance? 
In Eq. 4 you start with summing over all neighbours of $v$ for each dimension of $W$, could you comment on how this relates to summing over the subset of the neighbours? I am not sure, I understand what you mean with the “subset of neighbours in each dimension”.

Minor language hiccups:

•	P. 4 2nd sentence below equations: “is the function [that computes] node degrees” and same for the function “that computes” the hidden features?

•	P. 4 second to last paragraph: second sentence suiable -> suitable

•	First sentence in 3.3: Is that what you wanted to say?

•	Same page “We use […] aggregation coefficient matrices [as shown by?] Luan et al.”

•	Page 6: last sentence before “Comparisons with multi-head GAT“: “this can be explained [by the fact] that […]”.

•	Page 7: Paragraph “Effect of powerful aggregators”: Third sentence: “We config[ure]” 

review_title: Strong theoretical insights into GNNs with somewhat weaker experimental results

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Post Rebuttal**

I thank the authors for the extensive experiments and answers. Unfortunately, I still feel that the contribution is rather marginal. I keep my score unchanged.

---

**Summary of Contributions** 
The paper points at the expressive bottleneck of GNNs as the weak distinguishing strength of learned aggregators. The authors then formulate the aggregator operation via a standalone matrix, and analyze the requirements for it to have a sufficient distinguishing strength. 
Then, based on the analysis, 2 aggregation schemes with enlarged strength are proposed. Also, the benefit of applying activation before aggregation is shown. 

**Strengths** 
- *Simplicity of analysis* - The paper presents a simple formulation to the aggregation operator via the matrix coefficients which provide an intuitive view of the requirements from the aggregator functions. 
- The paper presents a general formulation for GNNs under the suggested framework, and shows how other GNNs fall into this framework. 
-  *Thorough ablation study confirming theory* - the ablation study on s nicely shows the improvement in performance as s grows. 
- Achieving SOTA results on some benchmarks.

**Weaknesses** 
- *Contribution and comparison to Corso et. al. (2020)* - Although the paper states results regarding the requirements from strong aggregators, as very similar result has already been introduced in Corso et. al.. In that case, I would have expected to see comparison in performance as both papers tackle the same problem. 
- *Comparison to GAT* - The paper shows how GAT can be formulated under the ExpandingConv formulation, raising the question, does it perform as well as the proposed methods?


**Recommendation**
The paper posses an interesting and simple view of aggregators in GNNs however I have concerns regarding the significance of contribution. Therefore, I rate it as marginally bellow acceptance threshold. 

**Additional Comments**
- Inaccuracies in GCN, GAT aggregation coefficients in p.4, missing the self coefficient. 








review_title: concerns about significance of contribution

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary of the paper: The main objective of the paper is to improve the expressiveness of the GNN by exploring powerful aggregators. The requirements to build more powerful aggregators are analysed. It is closely related to finding strategy for preserving the rank of hidden features, and implies that basic aggregators correspond to a special case of low-rank transformations.

Strengths: The idea is promising. A new GNN formulation is proposed: the aggregation is represented as the multiplication of hidden feature matrix of neighbours and the aggregation coefficient matrix.

Weaknesses: The strength mentioned above (multiplication of hidden features values and the aggregation) is also a weakness: I have an impression that already known results are presented in a much more complex way. The paper is not easy to follow in general ( e.g., the sentence "The difference is that each dimension of hidden features is aggregated with an independent weighted aggregator which works like a comb".)

The paper needs to be throughly read: use \citep instead of \cite where it is necessary. 

The improvements reported in the experimental section seem to be not really significant.

Questions: Could you provide an intuition for the definition of the distinguishing strength? (Section 3.1). 


review_title: The paper proposes to explore powerful aggregators to improve the expressiveness of the GNN. It is quite difficult to read the paper. Not sure that the numerical results show significant improvement.  

Meta-review: The paper explores the representation power of GNNs, in particular, studying the bottleneck and improving expressiveness with new aggregators, which are analyzed theoretically. This issue was highlighted in previous works, but the merit of this paper is a constructive analysis. 

The reviewers were overall not enthusiastic and  raised a few concerns:
- Not enough context is provided about related work, in particular, the early work of Corso et. al. 
- Insufficiently convincing experiments

While the authors provided an elaborate rebuttal and extended the experimental section to address experiment concerns raised by most of the reviewers, the final evaluation was still lukewarm. Given that the conference has a very high bar and there have been many very good submissions on graphs, we find the paper not quite above the bar and hence have no choice but to recommend rejection with a heavy heart. The authors should be commended on their efforts and are encouraged to seek publication elsewhere. 


Decision: Reject