Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes a generalization of Transformer architecture to hypergraphs, with a particular focus on developing a fast sparse version.
main_review: The paper is well written and the main motivation is clear. The proposed solution is novel, and, even though not so exciting from the modelling point of view, technically correct. The paper goes at great lengths to improve the scalability of the approach, and appears to do so successfully without compromising on the quality of the solutions and without introducing non-differentiable heuristics.

My main pain point is evaluation these models on the TU graph kernel datasets. As there are around 20-30 datasets, it is easy to overfit the model architecture and design choices to that particular task. While I do not believe this is true, it would be really nice to have some actual higher-order interaction dataset (academic co-authorship), even if it takes some time to produce/process.

Overall, seems like a good paper to appear at the conference.


EDIT: After the authors' comments, I raise my score to 8.
limitations_and_societal_impact: Limitations paragraph is written greatly and directly calls for subsequent work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper generalizes Transformer to higher-order Transformer, which is higher-order permutation invariant. To reduce the complexity, the authors propose to use sparse higher-order Transformer to achieve quadratic complexity, and further adopt the kernel attention approach to linear complexity.
main_review: Pros:
- This paper is well-written and well-organized, which is easy to follow.
- The idea taht extend the concept high-order permutation invirant to Transformer, or say self-attention, is novel and indeed practical.
- The design of higher-order self-attention makes sense to me.
- The propsed model works well on synthetic dataset, which demonstrates that the model could match the motivation of this paper.

Cons:
- It lacks a theoretical analysis of the performance (expressivenss, convergence, etc) about the two efficient tricks: sparse and kernel trick.
- It lacks a empirical study about the running time in terms of the number of the nodes.
- The original paper efficient transformers with kernel tricks (Performer, Transformers are RNNs, etc)  that cliam the performance would be degenerated if the models are trained from scratch. I wonder how the proposed higher-order Transformer with kernel trick solve this issue?
- The baseline methods are too weak and old, most of the baseline methods are published at or before 2019. Even though, the proposed method could not outperform all baseline methods on all datasets.

One possible reason is that, the datasets used in this paper are relative small, and Transformer would be benefited from massive data (see Bert or ViT). Please consider to use large dataset to demonstrate your method.




limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors proposed a transformer layer that generalizes the equivariant linear layers with self-attention to higher order tensor input. They defined the attention coefficient for each equivalence class $\mu$ with indices satisfied $(i, j) \in \mu$ to reduce unnecessary computation between queries and keys matrices. To further reduce the computation complexity of higher order transformers, the authors provides 3 steps of approximation: i) a lightweight linear layers defined only for subset of equivalence class to decouple the indices $i$ and $j$. ii) adding proxy hyperedges $E'$ that is contained in original hyperedges $E$ and help reducing the computation to only $m$ hyperedges across different layers. iii) a kernel trick to decompose the attention coefficients into kernel map of query and keyword matrices. 
main_review: pros:
- Generalized higher order linear layers with transformer encoder with self attention. 
- Reduced the complexity of transformer through above-mentioned approximations. 
- Overall, the transformer does have a larger expressive power than simple first order message passing algorithms.
- Extensive and detailed experiments with synthetic and real world datasets in different graph-related tasks. 

cons:
- I am concerned about sharing queries $\tilde Q$ and keys $\tilde K$ across all equivalence classes, as they might correspond to completely different propagation schemes with various bases. 
- Most of the results are still order 1 or 2 transformer layers, and the dataset are ordinary graphs. Lack of actual higher order interactions and hypergraph applications. 
- Some idea of proof is preferable in the main text instead of leaving all to supplementary. 
- The complexity is regarding to the number of matrix multiplication, but it can still be time/memory consuming in cases of large graph with higher feature dimension. An running time comparison in the experiment section would be a nice add-on for showcasing the efficiency. 
- The approximation of kernel attention in equation (20) removes correlations between $j$ and $i$ and shared across different input indices $i$ seems like a big trade-off and may raise some questions on whether the attention mechanism is still needed. 
- More detail on how the edge/node features of synthetic data are generated, how train/valid/test split are done with the chained labeled data is also missing. 
- Dataset statistics are missing. 
- Table 1 does not have any standard error. 


limitations_and_societal_impact: The authors addressed the limitation in Section 6 and potential social impact in the supplementary.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a framework to generalize transformers to any order permutation invariant data, especially hypergraphs. While the generalization itself is incremental compare to [20], the naïve approach gives unbearable computational complexity. Hence, the authors propose a series of tricks to lower the computational complexity which is their main contribution.
main_review: Strength:

(+) The idea itself sounds appealing.

(+) The experiment results seem to provide evidence that the proposed method has better performance in general.

Weaknesses:

(-) The proposed tricks to reduce computational complexity are lack clarity. Moreover, some of them seem problematic in simple examples. (See detail comments)

(-) The authors only use $L_{2\rightarrow 2}$ layers at most. Hence, it is unclear to see whether the model complexity is indeed $O(m)$, independent of orders $l,k$.

(-) This paper mainly focuses on the case where the input is a hypergraph. However, neither any experiments on hypergraphs nor hypergraph neural network baselines are included in the experiment section. 

Detail comments:

While I like the idea of this paper a lot, its unclarity avoids me from supporting acceptance. My first concern is about its complexity reduction tricks. I find myself have at least one doubt for all three tricks (Section 4.1, 4.2, and 4.3).

In section 4.1, line 191-198. In the example of $L_{1\rightarrow 1}$, the authors mention that they only use the basis $I_n$ and ignore the sum-pooling $11^T$ in Eq (4). Then they claim this light-weighted design is still able to model “interactions” between input elements. However, if we drop the sum-pooling $11^T$ in Eq (4), then no interactions between elements are considered, as now it only uses the basis $I_n$. This part really confuses me. Please elaborate more. Note that in the simple graph example, the proposed light-weighted design of $L_{1\rightarrow 1}$ is to ignore all “edge features” which means the graph information is completely neglected. Clearly, it is impossible to recover this information barely from attention among node features in general.

The heuristic approach of Section 4.2, especially the use of E’ is unclear. Since the authors say it is a heuristic, I expect that this approach will lose some information in (at least) some special cases? Please provide a minimal illustrative example (i.e. k=2, l=1?) to explain the use of E’.

Line 240. The definition of set $\mathcal{I}$ is unclear. Does it mean the set that union all $\mathbf{i},\forall (\mathbf{i},\mathbf{j})\in \mu$ over all possible $\mathbf{j}$? If this is the case, then shouldn’t the term that we actually summing over in eq (19) “less” than eq (20)? Why this resulting in further reduction needs more elaboration.

On the experiment side, since I feel the main contribution of the current paper is reducing the complexity of higher-order Transformer, I think the authors should at least conduct one experiment on it. More precisely, for a fixed hypergraph with $m$ hyperedges, I expect to see the experiment showing the time complexity of the proposed model remain unchanged even for increasing order $l,k$ in $L_{l \rightarrow k}$. I think it is necessary to verify the proposed analysis result by experiments. In line 327-334. The authors mention that due to the growth of $k^{th}$ order bell number, the higher-order model is actually infeasible. In this case, I feel the importance and contribution of the current paper are greatly degraded.

Finally, since the paper mainly focuses on the case where the input is a hypergraph, I think the authors should have some experiments regarding hypergraphs. However, neither any experiments on hypergraphs nor hypergraph neural network baselines are included in the experiment section. I suggest the authors either conduct experiments on hypergraphs and compare with SOTA hypergraph neural networks, or tone down the emphasis of hypergraphs at least in the abstract and introduction.

***
After rebuttal:

I really appreciate the detailed response by the authors, which resolves most of my questions especially those for Section 4. I do think that the work should emphasize more on Transformer side (which is exactly the main focus of this paper) and tone down its application to hypergraphs. Still, I think the new experiments comparing with Hyper-SAGNN and S2G are great to be included in the revision. I will raise my score to 6.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper develops transformers for order permutation invariant data such as sets, graphs  and hypergaphs. Overall, the reviewers and I have enjoyed reading the paper since moving transformers towards structured data is an important research direction. The experimental results presented in the rolling discussion on sharing queries and keys across all equivalence classes as well as the ones comparing with Hyper-SAGNN and S2G have to be included in the final version. They really showed the pros of the proposed approach. While making those changes the authors may also wish to add the clarifications posted in the rolling discussion. 

Decision: Accept (Poster)