# Graph Convolutions Enrich the Self-Attention in Transformers! ## Reviewer QKyk (2024-02-21) ### Summary The paper introduces Graph-Filter-Based Self-Attention (GFSA), an enhancement for the self-attention mechanism in Transformers, to address the over-smoothing problem. GFSA incorporates graph convolutions into self-attention, enriching it with diverse frequency information. The method is validated on various tasks, including computer vision, natural language processing, and speech recognition. The paper demonstrates that GFSA enhances Transformer performance across multiple domains with minimal computational overhead. ### Strengths and weaknesses ### Strengths 1. The design of GFSA is straightforward and can be used on any Transformer-based model. 2. The performance gain by applying GFSA is obvious, while the additional memory and computation overhead of GFSA is negligible. 3. The experiments are conducted on multiple domains with various datasets, which demonstrates the effectiveness and generality of GFSA. ### Weaknesses 1. The time complexity of GFSA is cubic, which is significantly higher than the quadratic in self-attention. Although the actual running time increase is not much, it will be difficult to scale to those datasets with larger $n$, such as longer sequences and larger graphs. 2. To approximate the high-order term $\bar{A}^K$, the authors use both the first-order Taylor approximation and the approximation of the derivative. However, the magnitude and influencing factors of the approximation error are not clear. 3. In equation (5), the combination of two lowest-order terms, $I$ and $\bar{A}$, is not well-explained, and their influence should be well-studied by the ablation study. 4. L217, "Appendix 3.2" should be "Section 3.2". ### Questions 1. I am curious about the results in Table 30. Only using GFSA on even layers sometimes improves the performance, such as the QQP and RTE datasets. I would like to know if the authors have further analysis on this phenomenon. 2. Since Graphormer also conducts experiments on ogbg-molpcba dataset, I wonder if the authors experiment GFSA on it. Is the actual running time on these larger graphs still slightly more than Graphormer? This may affect the assessment of GFSA efficiency. 3. For other questions, see weaknesses. ### Limitations The authors frankly stated that their method has a disadvantage in time complexity compared to the self-attention mechanism. I think a more efficient design could be the direction of future work. **Soundness:** 3 **Presentation:** 3 **Contribution:** 2 **Rating:** 6 **Confidence:** 4 ## Reviewer 9p1M (2024-03-14) ### Summary This work uses a graph signal processing perspective to motivate a modification of the original self-attention mechanism in transformer models. In particular, they proposed graph filter-based self-attention (GFSA) layers to replace the original self-attention. This modification includes a weighted average between the original self-attentional layer $\bar{A}$ and its second-order form $\bar{A}^2$. The weight between these two terms can be positive, negative, and it is determined by both the weight $w_k$ (learnable during training) and $K$ (hand engineered hyperparameter). They showed empirical result that this modification may help deep transformer model to circumvent the oversmoothing problem. Using this new GFSA, they showed that the modified transformers improve performance compared to models with original self-attentional layers in a broad range of tasks, e.g., image classification, speech recognition, and natural language understanding. ### Strengths and weaknesses Strength: The proposed modification is a generalized version of many previous methods. It is thus well motivated from the GNN literature.  The empirical evaluation includes a broad range of tasks.  Weakness I am not sure if the performance difference comes from only having a single model with GFSA per task (with a fixed random seed), or an average across multiple seeds. Could the authors comment on that?  It seems that the authors need to search for $K$ with the best performance. Would it be possible to also learn $K$? ### Questions I am a bit confused by the sensitivity of $K$. $K$ seems to be merely a weight on $\bar{A}^2-\bar{A}$. It seems that the range of $K$ was hand fixed. $K=2$ seems to work in a number of GLUE tasks. Have the authors tried to use higher order $\bar{A}^K$ rather than the polynomial approximation? Can the authors comment on the interplay between $w_k$ and $K$ (maybe for a particular layer across different heads)? **Limitations:** The authors sufficiently stated the limitations and potential negative societal impact of their work **Soundness:** 3 **Presentation:** 3 **Contribution:** 3 **Rating:** 6 **Confidence:** 4 ## Reviewer p7c4 (2024-03-15) ### Summary The paper designed a new self-attention (GFSA) from the graph signal processing perspective. The new self-attention aims to mitigate the over-smoothing in the transformers. When integrated with GFSA, the model can achieve better performance in various tasks. ### Strengths and weaknesses Strengths: 1. The paper is well written and easy to follow. 2. The proposed new self-attention is well motivated and justified. 3. The performance on various task is promising. Weakness: 1. In GFSA the first two low-order terms would mean identity and similarity score of tokens in transformer, respectively. Can author further explain what does the high-order term in GFSA represent in the context of transformer? 2. It seems that as the model size grows larger, the training time would increase dramatically, which would prevent its application on large models. **Questions:** See weakness. **Limitations:** N/A **Soundness:** 3 **Presentation:** 3 **Contribution:** 3 **Rating:** 6 **Confidence:** 3 ## Reviewer kY1p (2024-03-17) ### Summary This paper addresses the oversmoothing problem encountered in deep Transformer models, where representations across layers become indistinguishable, leading to performance degradation. To overcome this challenge, the authors propose graph-filter-based self-attention (GFSA), which reinterprets the original self-attention mechanism from a graph signal processing (GSP) perspective. Despite slightly increased complexity compared to the original self-attention, GFSA proves to be a more general and effective solution. The authors evaluate GFSA across various tasks including computer vision, natural language processing, graph pattern classification, speech recognition, and code classification, demonstrating its improved performance over traditional Transformers on standard datasets. ### Strengths and weaknesses Strengths: The paper is well-written and easily comprehensible. However, there is room for improvement in conveying the analysis and intuition behind the discussed concepts. The author has presented extensive quantitative results across various tasks. Weaknesses: 1. Complexity and Computational Cost: The proposed approximation method for \(A¯^K\) in Equation 4 simplifies computation, but concerns remain about its computational demands, particularly with large \(K\) or datasets. The authors should offer more insights into the computational complexity and feasibility, especially in scenarios with substantial data or high dimensions. 2. Lack of Theoretical Justification: While a first-order Taylor approximation is proposed for estimating the derivative of \(A¯^K\) in Equation 8, a rigorous theoretical justification is missing. Further theoretical analysis or empirical validation is necessary to ensure the accuracy and reliability of this approximation method. 3. Comparison with Existing Models: The comparison of GFSA with existing models like HAT, Wang et al., and Shi et al. seems cursory. A more comprehensive comparison, including experimental results and performance metrics, would provide better insight into the strengths and limitations of GFSA compared to these existing methods. 4. State-of-the-Art Comparison on ImageNet: The comparison with older techniques like ViT and DeiT is outdated, and the paper should benchmark against current state-of-the-art methods such as SVT[1], WaveVit[2], and SpectFormer[3]. Table 5 needs updating with the latest results for a thorough evaluation. 5. Core Contribution: While the paper discusses graph convolution-based methods, the core contribution seems limited. The authors need to explicitly outline what is novel about their work to distinguish it from existing literature. 6. Readability and Reproducibility: The paper lacks clarity regarding the core mechanism of the proposed explanation method. Providing an algorithm or pseudocode to reproduce results would enhance readability and reproducibility, which are essential aspects of machine learning practice. Reference 1. Patro, Badri, and Vijay Agneeswaran. "Scattering Vision Transformer: Spectral Mixing Matters." Advances in Neural Information Processing Systems 36 (2024). 2. Yao, Ting, Yingwei Pan, Yehao Li, Chong-Wah Ngo, and Tao Mei. "Wave-vit: Unifying wavelet and transformers for visual representation learning." In European Conference on Computer Vision, pp. 328-345. Cham: Springer Nature Switzerland, 2022. 3. Patro, Badri N., Vinay P. Namboodiri, and Vijay Srinivas Agneeswaran. "SpectFormer: Frequency and Attention is what you need in a Vision Transformer." arXiv preprint arXiv:2304.06446 (2023). **Questions:** Please refer to Weaknesses section. **Limitations:** Please refer to Weaknesses section. **Soundness:** 2 **Presentation:** 2 **Contribution:** 1 **Rating:** 5 **Confidence:** 5 ## Discussion, meta-review and decision (in time order) ### Official Comment -- Authors (2024-03-29) ### Comment Thank you for your comments and for the time and effort you put into reading, understanding, and evaluating our paper. We now answer the question posed by the reviewer. --- **Q1. Complexity and Computational Cost: The proposed approximation method for ($\bar{A}^{K}$) in Equation 4 simplifies computation, but concerns remain about its computational demands, particularly with large ($K$) or datasets. The authors should offer more insights into the computational complexity and feasibility, especially in scenarios with substantial data or high dimensions.** For a large $K$, we use the first-order Taylor approximation to avoid calculating $A^K$ directly, thus the complexity does not depends on $K$ in our method. Our method requires $A$ and $A^2$ only. We also introduce a selective GFSA strategy in Section 5.2, where we selectively use GFSA only for some selected layers. It can reduce the runtime. In Appendix O, Table 34 shows that selectively applying GFSA reduces the runtime per epoch by 26.90% compared to the full adoption of GFSA in all layers. The runtime increase per epoch is only 7.39% compared to the backbone model. We can also discuss the amount of computation in the case of large data that you are concerned about. In particular, for GPT-2 in language modeling experiments, the maximum number of tokens is 1,024. We note that in these cases, Table 33 shows that the selective GFSA layer strategy can alleviate the computational burden. On the PTB dataset, when GFSA is used on all layers, the runtime per epoch is 160.3 seconds, whereas when we use the selective strategy, it can be reduced 127.4 seconds, a reduction of 20.5%. At the same time, the accuracy can be maintained (see Table 32). --- **Q2. The first-order Taylor approximation to estimate the derivative of $\bar{A}^{K}$ in Eq. 8 lacks theoretical validity. Is theoretical analysis or empirical validation of this approximation method possible?** We use the first-order Taylor approximation to approximate $\bar{A}^K$ itself. However, computing the derivative of $\bar{A}^K$ directly at the evaluation point requires high computational costs. To overcome this problem, we approximate the derivative with the difference, which is a widely used trick. For instance, the forward finite difference method, which approximates derivatives with difference terms, is widely used in engineering. The formulation is as follows: $$ f'(K) = \frac{f(K+h)-f(K)}{h}=\frac{A^{K+h}-A^{K}}{h},$$ where the approximation error is $\mathcal{O}(h^2)$. Therefore, the smaller the value of $h$, the higher the approximation accuracy. However, calculating the fractional power of a matrix for small $h$ requires a high computational cost since it is calculated by diagonalizing the matrix or using the Shur's normal form. Therefore, considering the trade-off between computational complexity and accuracy, we set $h=1$ in the simplest way. This method is inspired by GRU-ODE [9], which uses the difference term of two consecutive hidden states in discrete time to approximate the derivative of the hidden state. For empirical validation, we report L$_1$-Norm of the error between the actually calculated $\bar{A}^K$ and the approximated $\bar{A}^K$ as follows: \begin{align} \text{Error}_K = \frac{||\bar{A}^K-(\bar{A}+(K-1)(\bar{A}^2-\bar{A}))||}{||\bar{A}^K||} \end{align} And the results of $\text{Error}_K$ for BERT trained on STS-B datasets are as follows: | K | 3 | 4 | 5 | 6 | | -------- | -------- | -------- | -------- | -------- | | BERT | 0.044 | 0.089 | 0.135 | 0.181 | To compare the impact of the actual $\bar{A}^K$ and the approximated $\bar{A}^K$ in terms of the accuracy, we experimented with BERT on GLUE and the results are as follows. BERT$_\text{BASE}$+$\bar{A}^K$ denotes using the exactly calculated $\bar{A}^K$ instead of the approximated $\bar{A}^K$. | Method | CoLA | SST-2 | MRPC | QQP | STS-B | MNLi-m/mm | QNLI | RTE | Avg | | -------- | -------- | -------- |-------- |-------- |-------- |-------- |-------- |-------- |-------- | | BERT$_\text{BASE}$ | 56.79 | 93.81 | 88.70 | 88.32 | 88.16 | 84.96/84.15 | 91.63 | 66.06 | 82.51 | | BERT$_\text{BASE}$+GFSA | 59.56 | 94.15 | 90.60 | 88.46 | 88.33 | 85.12/85.06 | 91.95 | 68.95 | 83.58 | | BERT$_\text{BASE}$+$\bar{A}^K$ | 59.85 | 94.27 | 89.80 | 88.43 | 88.32 | 84.95/84.89 | 91.76 | 68.23 | 83.39 | Although there is an approximate error, the accuracy of GFSA is comparable to the one obtained by the exactly calculated $A^K$. ### Official Comment -- Authors (2024-03-29) ### Comment **Q3. Comparison with Existing Models: The comparison of GFSA with existing models like HAT, Wang et al., and Shi et al. seems cursory. A more comprehensive comparison, including experimental results and performance metrics, would provide better insight into the strengths and limitations of GFSA compared to these existing methods.** Wang et al.[7] use the concept of discrete signal processing, which is a special case of graph signal processing, to isolate the lowest frequency component in the Fourier domain and use a filter learned by rescaling the low and high-frequency components. On the other hand, GFSA extends the concept to graph signal processing and redesigns the self-attention as a graph filter. Through this, based on ImageNet, a performance of 81.1 is achieved based on the 12-layer DeiT-S model, which is higher than the performance of 80.7 of AttnScale proposed by Wang et al. HAT [8] creates adversarial examples by altering clean images with high-frequency perturbations, and jointly trains a ViT model on clean images and adversarial examples. Through this, they aim to solve the problem of the ViT model not being able to capture high-frequency by allowing us to capture the high-frequency components of the image. However, HAT has the disadvantage of requiring more epochs than the existing ViT model, as it must perform adversarial training in some initial epochs and train normally in the remaining epochs. On the other hand, our GFSA designs self-attention as a graph filter without performing adversarial learning, and by learning the three coefficients of the graph filter, it acts as a low- or high-frequency filter to alleviate over-smoothing and improve performance (see **“How to alleviate the oversmoothing problem?”** on page 5). HAT improves the performance of DeiT-S to 80.9, but GFSA has a performance of 81.1, which shows that GFSA's method can be slightly more effective. Additionally, because our method does not perform adversarial learning, it has the advantage of being able to use the same learning strategy as existing ViT models. While GFSA seeks to design a better graph filter by interpreting self-attention as a graph filter $\mathbf{H}$, Shi et al. [6] are inspired by JKNet, which effectively solved over-smoothing in the GNN community, and they solve this problem by fusing the hidden vectors of each layers. However, the methods proposed by Shi et al. revealed in the paper that there was a limitation with memory increasing and they only applied it to BERT. Unfortunately, we cannot compare in terms of performance because the source code for this paper does not exist. --- **Q4. The comparison with older techniques like ViT and DeiT is outdated, and the paper should benchmark against current state-of-the-art methods.** The purpose of our experiment was whether the introduction of the GFSA layer would help improve performance in a base model, such as DeiT, following [6,7,8]. But we can also compare our method with the recent models you suggest. We compare SpectFormer [1], SVT [2], NeuTRENO [3], FNet [4], and GFNet [5], with a 12-layer setup to ensure a fair comparison. As you can see in the table below, GFNet can reduce the number of parameters, but there is a performance penalty. However, the performance improvement of DeiT-S+GFSA is relatively greater than DeiT-S compared to other models. SpectFormer and SVT have advantages in calculation amount and model complexity, and performance is improved over DeiT-S, but Top-1 and Top-5 accuracies are lower than those using GFSA. Additionally, NeuTRENO also improves as much as GFSA compared to DeiT-S, but GFSA still has higher Top-1 accuracy. We will update these results in Table 3 in our next version of the paper. | Method | #Layers | #Params | Top-1 Acc | Top-5 ACC | | -------- | -------- | -------- | -------- | -------- | | DeiT-S | 12 | 22M | 79.8 | 95.0 | | FNet-XS | 12 | 15M | 71.2 | - | | GFNet-XS | 12 | 16M | 78.6 | 94.2 | | SVT-XS | 12 | 20M | 79.9 | 94.5 | | SpectFormer-XS | 12 | 20M | 80.2 | 94.7 | | DeiT-S + NeuTRENO | 12 | 22M | 80.7 | 95.3 | | DeiT-S + **GFSA** | 12 | 22M | 81.1 | 95.4 | ### Official Comment -- Authors (2024-03-29) ### Comment **Q5. While the paper discusses graph convolution-based methods, the core contribution seems limited. The authors need to explicitly outline what is novel about their work to distinguish it from existing literature.** Thank you for your comment. We will follow your suggestions and articulate our novelty at the end of Introduction. We have somehow tried to differentiate ourselves from the existing literature by describing the differences with existing graph convolution-based methods in “Comparison to GCNs” on page 5. In particular, we discuss that other graph-filter-based GNN models can be special cases of our designed graph filter, depending on the coefficients or $K$ in Eq. 5. We also emphasize once again that, as far as we know, this is the first attempt in Transformer models and GNN models in that our graph filter uses approximations of high-order terms. --- **Q6. The paper lacks clarity regarding the core mechanism of the proposed explanation method. Providing an algorithm or pseudocode to reproduce results would enhance readability and reproducibility, which are essential aspects of machine learning practice.** In response to your concerns, we have already included a PyTorch-style pseudocode in Appendix A of our paper to ease the understanding of the core mechanisms of our GFSA. Furthermore, to enhance the reproducibility of our results, we have also provided the hyperlink to the complete source code in Appendix B. We believe these will significantly improve the reproducibility of our study. --- References > [1] Badri Patro, Vinay Namboodiri, and Vijay Srinivas Agneeswaran. "SpectFormer: Frequency and Attention is what you need in a Vision Transformer." arXiv preprint arXiv:2304.06446 (2023). > > [2] Badri Patro, Vijay Agneeswaran. "Scattering Vision Transformer: Spectral Mixing Matters." Advances in Neural Information Processing Systems 36 (2023). > > [3] Tam Nguyen, Tan Nguyen, and Richard Baraniuk. "Mitigating Over-smoothing in Transformers via Regularized Nonlocal Functionals." Advances in Neural Information Processing Systems 36 (2023). > > [4] James Lee-Thorp et al. "FNet: Mixing tokens with fourier transforms." arXiv preprint arXiv:2105.03824 (2021). > > [5] Yongming Rao et al. "Global filter networks for image classification." Advances in neural information processing systems 34 (2021): 980-993. > > [6] Han Shi et al. "Revisiting Over-smoothing in BERT from the Perspective of Graph." International Conference on Learning Representations. 2022. > > [7] Peihao Wang et al. "Anti-Oversmoothing in Deep Vision Transformers via the Fourier Domain Analysis: From Theory to Practice." International Conference on Learning Representations. 2022. > > [8] Jiawang Bai et al. "Improving vision transformers by revisiting high-frequency components." European Conference on Computer Vision. 2022. > > [9] Edward De Brouwer et al. "GRU-ODE-Bayes: Continuous modeling of sporadically-observed time series." Advances in neural information processing systems 32 (2019). ### Official Comment -- Authors (2024-03-29) ### Comment We sincerely thank Reviewer p7c4 for the thorough reading and appreciation of our work, and for raising insightful questions, highlighting our strengths in: 1. The paper is well-written and easy to follow and read. 2. The newly designed self-attention is well-motivated and justified. 3. Performance on a variety of tasks is promising. --- **Q1. In GFSA the first two low-order terms would mean identity and similarity score of tokens in transformer, respectively. Can author further explain what does the high-order term in GFSA represent in the context of transformer?** Existing self-attention captures only simple pairwise similarities between tokens and is limited in capturing high-order dependencies. For example, “Book costs more than pencil.” and “Book costs less than computer.” Given two sentences, to determine the relationship between "computer" and "pencil," we need to capture the higher-order dependency connected through the token "Book." However, it is difficult to capture such high-order dependencies in existing self-attention [1]. So, from a Transformer perspective, the high-order term of GFSA can be interpreted as being able to capture these higher-order dependencies. In other words, our high-order terms can capture complex structural dependencies between tokens beyond simple inter-token similarities in Transformer. To talk more about high-order terms from the perspective of the graph filter that our paper is inspired by, the advantage is that $\omega_K$ coefficients can be learned to have positive or negative values. Negative values of $\omega_K$ allow GFSA to extract high-frequency information from the value vector, which is different from self-attention, which can only extract low-frequency information (see "How to alleviate the oversmoothing problem?" on page 5). --- **Q2. It seems that as the model size grows larger, the training time would increase dramatically, which would prevent its application on large models.** We are aware of the problem of increased training time due to GFSA, and we introduced a strategy in Section 3 that allows GFSA to be applied selectively instead of applying it to all attention layers. This is similar to the strategy of not applying it to all layers like existing studies such as Spectformer[2]. We report in Section 5.2 and Appendix O that with this strategy, we can reduce the increased training time while also improving performance compared to original backbone models. For example, in Table 34, selective application of GFSA reduces runtime by 26.90% compared to full application, which is only a 7.39% increase over the backbone model. Additionally, in Tables 30 and 32, we can see that selective GFSA strategy can be more beneficial in improving performance in terms of average performance. > [1] Haoyi Zhou et al. "Jump Self-attention: Capturing High-order Statistics in Transformers." Advances in Neural Information Processing Systems 35 (2022): 17899-17910. > > [2] Badri Patro, Vinay P. Namboodiri, and Vijay Srinivas Agneeswaran. "SpectFormer: Frequency and Attention is what you need in a Vision Transformer." arXiv preprint arXiv:2304.06446 (2023). ### Official Comment -- Authors (2024-03-29) ### Comment We sincerely thank Reviewer 9p1M for the thorough reading and appreciation of our work, and for raising insightful questions, highlighting our strengths in: 1. The proposed modification is a generalized version of many previous methods and is inspired by the GNN literature. 2. Empirical evaluation involves extensive work. --- **Q1.I am a bit confused by the sensitivity of $K$. $K$ seems to be merely a weight on $A^{2}-A$. It seems that the range of was hand fixed. seems to work in a number of GLUE tasks. Have the authors tried to use higher order $A^{K}$ rather than the polynomial approximation? Can the authors comment on the interplay between $w_k$ and $K$(maybe for a particular layer across different heads)?** 1. Thank you for your thoughtful feedback. To compare the impact of the actual $\bar{A}^K$ and the approximated $\bar{A}^K$ in terms of performance, we experimented with BERT on GLUE task and the results are below. BERT$_\text{BASE}$+$\bar{A}^K$ denotes using directly calculated $\bar{A}^K$ as the high-order term instead of the approximated $\bar{A}^K$. | Method | CoLA | SST-2 | MRPC | QQP | STS-B | MNLi-m/mm | QNLI | RTE | Avg | | -------- | -------- | -------- |-------- |-------- |-------- |-------- |-------- |-------- |-------- | | BERT$_\text{BASE}$ | 56.79 | 93.81 | 88.70 | 88.32 | 88.16 | 84.96/84.15 | 91.63 | 66.06 | 82.51 | | BERT$_\text{BASE}$+GFSA | 59.56 | 94.15 | 90.60 | 88.46 | 88.33 | 85.12/85.06 | 91.95 | 68.95 | 83.58 | | BERT$_\text{BASE}$+$\bar{A}^K$ | 59.85 | 94.27 | 89.80 | 88.43 | 88.32 | 84.95/84.89 | 91.76 | 68.23 | 83.39 | 2. $K$ is the order of polynomial graph filter, and we approximate $K$ power of $\bar{A}$, which is $\bar{A}^K$. $w_k$ is the coefficient of high-order term in our proposed model. It determines the characteristic of graph filter. Depending on the coefficients $\{w_0, w_1, w_k\}$ for $I$, $\bar{A}$, and $\bar{A}^K$, the graph filter can be trained as a low-pass-only, high-pass-only, or combined-pass filter. --- **W1. I am not sure if the performance difference comes from only having a single model with GFSA per task (with a fixed random seed), or an average across multiple seeds. Could the authors comment on that?** We apologize for the confusion. For graph Transformers, the performance results in Tables 5 and 6 are averaged using multiple seeds as suggested in the paper. Tables including standard deviation are reported in Appendix G.2. All other experiments used fixed seeds, strictly following the experimental settings in the paper of backbone model. --- **W2. It seems that the authors need to search $K$ for with the best performance. Would it be possible to also learn?** Thank you for your good comments. Since we designed GFSA from the perspective of GSP, we assumed the order $K$ to be a natural number, and usually fixed as hyperparameters in GNNs. So, we did not consider learning about $K$ in this paper, but learning will be possible if $K$ is assumed to be a fractional order as future work. ### Official Comment -- Authors (2024-03-29) ### Comment We sincerely thank Reviewer QKyk for the thorough reading and appreciation of our work, and for raising insightful questions, highlighting our strengths in: 1. The design of GFSA is straightforward and has the advantage that it can be used on any Transformer-based model. 2. Although the performance improvement by applying GFSA is obvious, the additional memory and computational overhead of GFSA are negligible. 3. Experiments are performed in multiple domains using diverse data sets, which demonstrate the effectiveness and generality of GFSA. --- **Q1. I am curious about the results in Table 30. Only using GFSA on even layers sometimes improves the performance, such as the QQP and RTE datasets. I would like to know if the authors have further analysis on this phenomenon.** Recently, models that have adopted the strategy of applying the proposed self-attention to only some layers of the Transformer, such as Spectformer [1], have achieved good performance. Spectformer suggests that a mixed type of Transformer can provide good performance. In the same context, our model may achieve better performance by applying GFSA to only some layers rather than applying GFSA to all layers in certain cases. > [1] Badri Patro, Vinay P. Namboodiri, and Vijay Srinivas Agneeswaran. "SpectFormer: Frequency and Attention is what you need in a Vision Transformer." arXiv preprint arXiv:2304.06446 (2023). --- **Q2. Since Graphormer also conducts experiments on ogbg-molpcba dataset, I wonder if the authors experiment GFSA on it. Is the actual running time on these larger graphs still slightly more than Graphormer? This may affect the assessment of GFSA efficiency.** In below tables, we report the training and inference times in ogb-molpcba and ogb-molhiv according to the experimental settings of Graphormer. - Training time ($s$/epoch) | | molpcba | molhiv | | -------- | -------- | -------- | | Graphormer | 941 $s$ | 176 $s$ | | Graphormer+GFSA | 1055 $s$ | 195 $s$ | - Inference time | | molpcba | molhiv | | -------- | -------- | -------- | | Graphormer | 105$s$ | 12$s$ | | Graphormer+GFSA | 109$s$ | 14$s$ | --- **W1. The time complexity of GFSA is cubic, which is significantly higher than the quadratic in self-attention. Although the actual running time increase is not much, it will be difficult to scale to those datasets with larger, such as longer sequences and larger graphs.** We can discuss the amount of computation in the case of large data that you are concerned about. In particular, for GPT-2 in language modeling experiments, the maximum number of tokens is 1,024. We note that in these cases, Table 33 shows that the selective GFSA layer strategy can alleviate the computational burden. On the PTB dataset, when GFSA is used on all layers, the runtime per epoch is 160.3 seconds, whereas when we use the selective strategy, it can be reduced 127.4 seconds, a reduction of 20.5%. At the same time, the accuracy can be maintained (see Table 32). --- **W2. To approximate the high-order term $\bar{A}^K$, the authors use both the first-order Taylor approximation and the approximation of the derivative. However, the magnitude and influencing factors of the approximation error are not clear.** For measuring the approximation error, we report L$_1$-Norm of the difference between the actually calculated $\bar{A}^K$ and the approximated $\bar{A}^K$ as follows: \begin{align} \text{Error}_K = \frac{||\bar{A}^K-(\bar{A}+(K-1)(\bar{A}^2-\bar{A}))||}{||\bar{A}^K||} \end{align} And the results of $\text{Error}_K$ for BERT trained on STSB datasets are as follows: | K | 3 | 4 | 5 | 6 | | -------- | -------- | -------- | -------- | -------- | | BERT | 0.044 | 0.089 | 0.135 | 0.181 | To compare the impact of the actual $\bar{A}^K$ and the approximated $\bar{A}^K$ in terms of performance, we experimented with BERT on GLUE task and the results are below. BERT$_\text{BASE}$+$\bar{A}^K$ denotes using directly calculated $\bar{A}^K$ as the high-order term instead of the approximated $\bar{A}^K$. | Method | CoLA | SST-2 | MRPC | QQP | STS-B | MNLi-m/mm | QNLI | RTE | Avg | | -------- | -------- | -------- |-------- |-------- |-------- |-------- |-------- |-------- |-------- | | BERT$_\text{BASE}$ | 56.79 | 93.81 | 88.70 | 88.32 | 88.16 | 84.96/84.15 | 91.63 | 66.06 | 82.51 | | BERT$_\text{BASE}$+GFSA | 59.56 | 94.15 | 90.60 | 88.46 | 88.33 | 85.12/85.06 | 91.95 | 68.95 | 83.58 | | BERT$_\text{BASE}$+$\bar{A}^K$ | 59.85 | 94.27 | 89.80 | 88.43 | 88.32 | 84.95/84.89 | 91.76 | 68.23 | 83.39 | Although there is an approximate error, the performance GFSA is comparable to the performance obtained by directly calculating $\bar{A}^K$. Considering the amount of computation for $\bar{A}^K$, our approximated $\bar{A}^K$ is reasonable. ### Official Comment -- Authors (2024-03-29) ### Comment **W3. In equation (5), the combination of two lowest-order terms $I$,and $\bar{A}$, is not well-explained, and their influence should be well-studied by the ablation study.** Since we are inspired by graph filters, order $k$ starts from 0, as shown in Eq 3. Therefore, the identity matrix $I$ corresponding to $k=0$ is included among the two lowest terms. The role of $I$ in our proposed method is similar to the residual connection of a standard Transformer. The original residual connection adds the input vector $\mathbf{X}$ to the multihead attention result. However, the coefficient of $I$ in GFSA, $\omega_0$, adjusts the weight of the value vector $\mathbf{X}\mathbf{W}_{val}$ of each head. Therefore, our GFSA has the advantage that it can be applied without changing the internal structure of any Transformer except the self-attention matrix. Our GFSA can be reduced to the original self-attention when there is no high-order term $\mathbf{A}^K$, and $\omega_0$ is 0. In ablation studies on the combination of two low-order terms, if the first term $\bar{\mathbf{A}}$ does not exist, the performance is lower than that of the backbone because it change the structure of the existing Transformer backbone. In particular, performance is dropped in finetuning tasks such as the GLUE task, so ablation studies using the first term, $\bar{\mathbf{A}}$, cannot be reported. Instead, we report an ablation study of the use and absence of $\mathbf{I}$ in the GLUE task. GFSA without $\mathbf{I}$ improves over the default BERT, but is lower than GFSA using all three terms in all cases. Therefore, it can be seen that using two low-order terms is effective in GLUE tasks. | Method | CoLA | SST-2 | MRPC | QQP | STS-B | MNLi-m/mm | QNLI | RTE | Avg | | -------- | -------- | -------- |-------- |-------- |-------- |-------- |-------- |-------- |-------- | | BERT$_\text{BASE}$ | 56.79 | 93.81 | 88.70 | 88.32 | 88.16 | 84.96/84.15 | 91.63 | 66.06 | 82.51 | | BERT$_\text{BASE}$+GFSA | 59.56 | 94.15 | 90.60 | 88.46 | 88.33 | 85.12/85.06 | 91.95 | 68.95 | 83.58 | | BERT$_\text{BASE}$+GFSA without $\mathbf{I}$ | 58.80 | 93.46 | 90.40 | 88.41 | 88.17 | 85.06/84.63 | 91.76 | 66.79 | 83.05 | --- **W4. L217, "Appendix 3.2" should be "Section 3.2".** Sorry for the confusion. We will correct the error. ### Official Comment -- Reviewer 9p1M (2024-04-03) **Comment:** I thank the authors for the rebuttals. I will keep my original scoring. ### Official Comment -- Authors (2024-04-04) ### Comment Dear Reviewer kY1p, We appreciate your constructive comments for helping us to improve our paper in many aspects. This is a gentle reminder since the final discussion stage ends soon. We would like to ask if Reviewer kY1p may have any further questions regarding our submission so that we can still respond. Best, Authors ### Official Comment -- Authors (2024-04-04) ### Comment We greatly appreciate your positive evaluation of our paper and constructive comments, which have further improved our paper. ### Official Comment -- Authors (2024-04-04) ### Comment Dear reviewer p7c4, Towards the end of the discussion phase, we believe our response has successfully addressed your inquiries. We look forward to receiving your feedback regarding whether our reply sufficiently resolves any concerns you may have or if further clarification is needed. Thank you, Authors ### Official Comment -- Authors (2024-04-04) ### Comment Dear reviewer QKyk, As the rebuttal deadline approaches, we would like to hear your thoughts on our response. Have we adequately addressed your concerns? Your feedback is very important to us, and we are committed to further improving our paper based on your insights. Best, Authors ### Official Comment -- Reviewer kY1p (2024-04-04) ### Comment Thanks to the authors for their rebuttal. I've read the comments from other reviews and the authors' responses. First, the authors have addressed most of my questions. I am happy to increase my score. ### Official Comment -- Reviewer p7c4 (2024-04-04) **Comment:** Thanks for the author's rebuttal. I would like to maintain my score. ### Decision -- Program Chairs (2024-05-01) **Decision:** Reject ### Comment The paper presents graph-filter-based self-attention (GFSA) to tackle the oversmoothing issue in deep Transformer models, where layer representations become overly similar and negatively affect model performance. GFSA reinterprets traditional self-attention mechanisms using graph signal processing (GSP) techniques and incorporates graph convolutions to add diverse frequency information to the attention layers. The authors demonstrate that GFSA enhances the performance of Transformer models across various tasks, including computer vision, natural language processing, and speech recognition. While this work addresses an interesting problem, it has several weaknesses: 1. The contribution of this work is limited. While it draws heavily on concepts from GSP and incorporates modifications to self-attention accordingly, previous research has already addressed oversmoothing in deep Transformer models through the lens of graph filters. Although this work integrates GSP to enhance attention, the original modifications are relatively minor. Consequently, the overall impact of this work is somewhat diminished. 2. A more comprehensive theoretical analysis is needed. The method approximates \bar{A}^K using the first-order Taylor approximation and also approximates its derivatives. However, this deviation from the original GSP necessitates a rigorous examination of the bound on approximation errors. Though the authors present a simple error analysis and results on a specific dataset in the Rebuttal, it lacks thoroughness. Relying on analysis from just one dataset lacks persuasiveness, as errors may vary across datasets and different values of K. Establishing a strict bound on approximation error is essential for solid theoretical analysis. 3. The overall improvement in performance is not substantial. While it is noteworthy that this work has been applied across various tasks and datasets, resulting in performance enhancements, the magnitude of improvement is modest. Considering the additional computational overhead introduced by the method, particularly in training on large models like GPT2 or on long sequences, which leads to significantly extended training times, the benefits may not outweigh the costs. Given the efforts made in this work to address oversmoothing in deep Transformer models from a graph signal processing perspective, it presents an intriguing contribution. However, to enhance its comprehensiveness, additional elaborations and analyses are necessary.