Venue: NeurIPS 2022 Conference

Reviews:

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 paper targets at developing a more expressive pooling layer for GNNs, which allows neighboring nodes to perform high-order multiplicative interactions. The authors leverage a rank R symmetric CANDECOMP/PARAFAC (CP) decomposition to design an efficient parameterization of multilinear maps over a set of node representations. The number of parameters is controlled by the rank R. With appropriate non-linear activation function, the paper proposes the CP layer as a high-order graph pooling layer. Theoretical analysis shows that the CP layer can achieve permutation-invariance and is is universally strictly more expressive than sum and mean pooling. With the CP layer, the authors propose tGNN, which uses both the CP layer and the sum/mean pooling layer. Experimental studies on graph and node classification tasks indicate that tGNN can achieve better performances on multiple benchmark datasets.
strengths_and_weaknesses: Strengths:
1. The theoretical derivation of the CP layer is technically sound and novel.
2. The proposed method shows improved performance across tasks and datasets, along with complete ablation studies.
3. The paper is overall well-written. 

Weaknesses:
1. There is a missing related work like "Wang, Zhengyang, and Shuiwang Ji. "Second-order pooling for graph neural networks." IEEE Transactions on Pattern Analysis and Machine Intelligence (2020)." which also explore higher-order pooling. 
questions: N/A
limitations: N/A
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 paper proposes a novel aggregation (pooling) layer for GNNs, called CP layer. The main idea consists of leveraging multilinear tensor decomposition to model high-order polynomial interaction between the components of node embeddings (the final design also employs non-linear activation functions). The authors show that the proposed layer is strictly more expressive than typical neighborhood aggregation functions, e.g., sum or mean. Experiments on many benchmarks (including OGB) assess the effectiveness of CP layers. 
strengths_and_weaknesses: Overall, the paper reads well and tackles a relevant issue in GNNs: neighborhood aggregation. The evaluation setup is comprehensive. The empirical results are promising but not outstanding. The paper also lacks a stronger motivation to support the novel GNN design, either in terms of GNN's expressiveness or by characterizing relevant inductive biases for certain tasks.  

Strengths
- The evaluation setup considers a number of relevant benchmarks
- The proposed model is simple and easy to grasp
- The contribution is novel in the sense that is the first paper to leverage multilinear tensor decomposition for improved neighborhood aggregation

Weaknesses
- Despite showing positive results for CP layers, tGNN is not provably more expressive than classic 1-WL GNNs (e.g., GIN). Since inductive biases are not universal, the paper does not discuss when (and why) the proposed design is desirable.
- It seems the method suffers from numerical instability. This issue is not properly discussed in the paper.
- Some numbers reported in the paper are inconsistent with the literature.

questions: - In the experiments, tGNN applies sampling "to avoid numerical instability and floating point exception in tGNN training". What is the source of this numerical instability? Is it a strong limitation?
- Table 1 reports numbers for GPRGNN and APPNP from [1]. However, I wonder if there are differences in the evaluation setup between this paper and [1] as [1] reports, e.g., 0.7521 for GCN as opposed to 0.8778 here. Also, there is a big gap between GAT and GCN which is not often observed on Cora, Citeseer, and Pubmed. What is the source of these differences?
- In the node-level experiments, tGNN samples 5 neighbors. It is possible that performance gains come from this regularization. Can you provide evidence that this is not the case?
- Classical GNNs model high-order node interactions by stacking simple low-order layers, possibly interleaved with MLPs. Can you elaborate more about the possible gains of using CP instead? 

[1] https://openreview.net/pdf?id=n6jl7fLxrP
limitations: The limitations are briefly mentioned throughout the paper, but no dedicated section/paragraph is provided.
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: This paper proposes a novel Tensorized Graph Neural Network (tGNN) based on symmetric CP decomposition, which can model high-order non-linear interactions among nodes. It theoretically shows that the CP layer can compute any permutation-invariant multilinear polynomial including sum and mean pooling. Experiments on several benchmark graph datasets demonstrate that the proposed method achieves more effective and expressive results than existing GNN architectures and pooling methods.
strengths_and_weaknesses: Strengths:

- The paper is very well motivated and a good application of tensor methods on GNNs.
- Good problem formulation and insight
- Works well on the evaluated datasets

Weaknesses:

- Some important results are given without justification, e.g., why Tanh is chosen for \sigma and ReLu chosen for \sigma’? How effective is Eq. (5) against the inductive bias towards capturing high-order interactions?
- There is no discussion about hyperparameter choices and stability, except for simply listing the hyperparameter values in Tables 8 and 9.

questions: It would be great if the authors could address the following questions.

1. Why Tanh is chosen for \sigma and ReLu chosen for \sigma’?
2. Which equation is used in the CP layer? the one was given in Definition 1 or Eq. (5)? It is interesting to see how effective is Eq. (5) against the inductive bias towards capturing high-order interactions, which terms, high-order interactions or lower-order interactions, dominate the model performance?
3. In Lines 262-263, it was mentioned that "To avoid numerical instability and floating point exception in tGNN training, we sample 5 neighbors for each node." How 5 neighbors are sampled for each node? The 5 nearest ones or others?
4. More discussions about hyperparameter settings should be given based on the results, especially how to set the CP decomposition rank R in practice?
5. What do the different background colors mean in Tables 1 and 2?
6. Is there any reason why different evaluation metrics (e.g., Acc and AUC) are used for different datasets?

Minors:
1. In Figure 1, the three Ns should have the same font size.
2. In Line 94, "mode 1 and 2" --> modes 1 and 2.
3. In Line 147, "see Eq.2" --> see Eq. 2.
4. In Line 151, "RelU" --> ReLU.
5. In Line 321, "asses" --> assess.

limitations: Yes.
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: This paper proposes to consider non-linear high-order multiplicative interactions among nodes with symmetric tensor decomposition, for node aggregations in graph neural networks (GNNs). In particular,
* The authors motivate that existing GNNs rely on naive pooling operations, such as sum or mean, which are insufficient for aggregating nodes for obtaining node- and graph-level representations.
* The authors then propose to consider high-order interactions among nodes with the existing symmetric CP decomposition scheme, and the authors show that the proposed one can approximate permutation-invariant multilinear polynomial including sum and mean aggregations.
* The authors verify their model on node and graph classification benchmark datasets, on which the proposed method named tGNN outperforms existing baselines on most datasets.
strengths_and_weaknesses: ### Strengths
* The authors propose to consider multiplicative interactions among nodes from the lowest-order to k-order polynomials, rather than only considering k-order polynomials, which is reasonable and interesting. 
* The authors theoretically show that the proposed CP layer can approximate any permutation-invariant multilinear polynomial, which is necessary and valuable.
* The authors analyze the complexity of the proposed CP layer against the most naive graph neural network with big-O notation, which I appreciate. Also, it seems if we control the decomposition rank carefully, then the complexity of the proposed CP layer becomes reasonable (i.e., complexity is not much high).
* This paper is well structured and well written.

### Weaknesses
* This work is not well-positioned against existing works. The authors focus on capturing high-order interactions among nodes, and there are various works that consider such interactions, for example, graph attention network and Graphormer that reflect how each node is related to every other node, which are but not mentioned in the introduction section for motivating authors' work. In this vein, which points are different between those previous works and the proposed work, regarding node-level interactions? It should be discussed.
* Further, similarly to the above weak point, while the authors propose to consider high-order node interactions, the related work and discussion section (Section 4) barely describes such a point, but rather describing generic aggregation functions, universal approximators, and tensor methods for deep learning.
* The authors argue that the proposed tGNN achieves state-of-the-art results in Line 13, however, the performance improvements against baselines are marginal. Specifically, in Table 1, it seems the results of the proposed tGNN are not statistically significant compared to the most basic model, namely graph convolutional network (GCN), and further the proposed tGNN underperforms GCN on the Citeseer dataset. 
* The analyses on model complexities are not enough (see suggestions in the Major Questions and Suggestions section below). In particular, the model complexity is not analyzed in terms of the number of sampled nodes, which is currently too small (i.e., 3 or 5) to confirm the proposed tGNN's efficiencies. Also, the computational complexity in Figure 4 is not compared against baselines, but only compared within the proposed models, thus I cannot see how much the proposed tGNN is efficient compared to the previous models, for example, five times slower than the GCN model.

questions: ### Major Questions and Suggestions
* Regarding analyses on the model complexity, I suggest authors increase the number of sampled nodes (currently, they are too small, for example, 3 or 5) and then compare the complexity across different models in this setting of increased sample sizes. 
* Also, regarding analyses on the model complexity, I suggest the authors include the complexities of baselines in Figure 4 of the main paper, and then discuss the complexity by comparing the proposed tGNN and baselines.
* There are two related works: 1) There is a relevant work that considers interactions among nodes on graph pooling, which is also a universal approximator for set aggregation [1]. 2) There is a relevant work that proposes second-order pooling for graph neural networks [2]. Those works should be discussed and compared on the graph classification task.
* In Table 1, why the most basic GCN outperforms all the other recent GNNs, which is quite weird?
* Also, it is quite weird that the performance results in Table 1 and Table 4 are different.
* I suggest authors empirically verify that the CP layer can approximate sum and mean pooling functions. While the authors theoretically analyze that the proposed CP layer can compute them, I am not certain this is empirically possible, as the CP layer tends to capture high-order interactions as in Line 202 while ignoring low-order interactions.
* Also, similarly to the above question, the evidence of tenting to capture high-order interactions and why not exist. I would like to see how much and why the CP layer prefers high-order interactions. 
* In Figure 2, which part is the illustration of sum pooling? It seems there is only the illustration of the proposed CP layer, and the sum pooling is not illustrated but mentioned in the caption.

### Minor Questions and Suggestions
* This is a simple question that is the linear sum pooling in Table 3 the model of equation (5) without using the left (first) term?
* The number of sampled nodes is not consistent across different tables: in Line 263, the authors sample 5 neighbors, however, in Table 4, the authors sample 3 neighbors. Why does there exists inconsistency?
* In Line 288, the description is not matched to the results in Table 1: there are no datasets that the proposed tGNN is ranked at four.
* I cannot see the text in Figure 3 clearly, due to its background color.

### Typos
* In line 154, such at -> such as.

---

[1] Accurate Learning of Graph Representations with Graph Multiset Pooling. ICLR 2021.

[2] Second-Order Pooling for Graph Neural Networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020

---

**Update after the author-reviewer interaction phase**: thanks authors for additionally revising the manuscript. Since I cannot write public comments that the authors can see anymore, I leave my update here. The revision looks good and I am further satisfied with it. Thus, I increase my score from borderline accept to weak accept, and hope the authors move some of the revision in Appendix to the main page, if additional one page is allowed.
limitations: The authors do not describe the limitations and potential negative societal impact of their work, and simply mark the checklist for this category as N/A. However, I think authors can describe the limitations and
review_title: null

Meta-review: metareview: The reviewers initially disagree on whether this paper has sufficiently advanced the research topic of graph pooling and have concerns on missing the comparison with Wang and Ji (2020), which have also introduced higher-order pooling for graph neural networks (GNNs). After extensive discussions with the authors, the reviewers have reached a consensus towards acceptance: While the performance improvement is marginal, and in some cases, not statistically significant, the proposed tensor decomposition-based pooling algorithm is new and provides a theoretically-sound valuable addition to advanced neighborhood aggregation methods for GNNs.

confidence: Certain
Decision: Accept