Summary
In this paper, the authors propose a novel Graph Transformer called STA-GNN (SubTree-attention-GNN) to address the over-smoothing and over-squashing in the message-passing scheme. Different from the previous Graph Transformer, STA-GNN's attention mechanism is called SubTree Attention (STA), which computes a node's attention according to different levels of its subtree. To overcome the exponentially growing computation cost STA brings, the authors leverage the linearized attention technique raised by [19]. Experiments show that STAGNN outperforms SOTA GNN on node classification tasks.
Strengths
1. The authors provide a thorough demonstration of STA's workflow with a theoretical analysis of how STA addresses over-smoothing and over-squishing. Besides. The authors propose an effective computing algorithm, which decreases STA time complexity.
2. The experiment result outperforms SOTA GCN and Graph Transformer.
3. Ablation studies show that STA is beneficial to global attention in graph learning.
Weaknesses
1. STA's timing performance is unclear. The authors leverage kernelized Softmax to design an efficient algorithm with time complexity O(epsilon) (the number of edges). However, it is hard to compare STA with Graph transformers' (O(N) where N is the number of nodes) from the time complexity aspect, since the number of nodes and edges are independent in an undirected graph. This paper lacks experiments on STA's and Graph Transformers' timing performance. Without evidence, people will worry about if STA can achieve superior performance within a reasonable time limit.
2. Analysis of STA's space complexity is missing. STA efficient algorithm reduces the number of calculations by storing and re-using previous calculation results for future calculation. But there is no discussion on the potential problem of STA's memory cost. A memory cost comparison can better show the efficiency of STA.
3. Hop2Token used in NAGphormer [1] also learns the graph at the level of hops like STA. The experiment results against with NAGphormer does not seem very superior, especially when the experiment is not comprehensive to include a comparison of time and memory cost.
4. Equation (5) doesn't match the context in Figure 1 (a). N is defined as the number of nodes at the start of Section 2. However, figure 1 (a) says the STA_{k} should only attend the k-th hop neighbors, which is conflict with Equation (5).
5. Lack of explanation when introducing the rewriting from equation (3) to equation (4) (in Sec. 2.2). It is not obvious how to rewrite a similarity function with a selected kernel and feature map. [2] is about how to rewrite the similarity function using a linear kernel, which should be cited here.
[1] J. Chen, K. Gao, G. Li, and K. He. Nagphormer: Neighborhood aggregation graph transformer for node classification in large graphs. CoRR, abs/2206.04910, 2022.
[2] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret. Transformers are rnns: Fast autoregressive
transformers with linear attention. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5156–5165. PMLR, 2020.
Questions
1. In section 5.2, the authors claim "In contrast to MP-GNNs, STAGNN maintains robust performance even when the height of the subtree reaches 100". Where is the source of "the performance of MP-GNNs doesn't maintain robust when the height of the subtree reaches 100"?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
No limitations are mentioned in this paper.