Graph Convolutions Enrich the Self-Attention in Transformers!

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:50:41

Abstract: Transformers, renowned for their self-attention mechanism, have achieved state-of-the-art performance across various tasks in natural language processing, computer vision, time-series modeling, etc. However, one of the challenges with deep Transformer models is the oversmoothing problem, where representations across layers converge to indistinguishable values, leading to significant performance degradation. We interpret the original self-attention as a simple graph filter and redesign it from a graph signal processing (GSP) perspective. We propose a graph-filter-based self-attention (GFSA) to learn a general yet effective one, whose complexity, however, is slightly larger than that of the original self-attention mechanism. We demonstrate that GFSA improves the performance of Transformers in various fields, including computer vision, natural language processing, graph-level tasks, speech recognition, and code classification.

Main paper: 
 introduction: 
 Transformers are arguably one of the best feats in the field of deep learning. They are now showing the state-of-the-art performance in various fields, ranging from computer vision to natural language processing to graph pattern classification to speech recognition, and so forth (Vaswani et al., 2017; Devlin et al., 2019; Radford et al., 2018; 2019; Dosovitskiy et al., 2021; Touvron et al., 2021a; Zhou et al., 2021a; Liu et al., 2021; Gulati et al., 2020; Latif et al., 2023; Ying et al., 2021; Rampášek et al., 2022) . Recently, there have been several studies conducted on better understanding them (Gong et al., 2021; Ali et al., 2023; Wang et al., 2022) ; there exists a common agreement among researchers that the self-attention is one of the keys leading to the success.However, there also exist several studies pointing out potential limitations of the self-attention (Zhou et al., 2021a; Dong et al., 2021; Gong et al., 2021; Guo et al., 2023) . For instance, Shi et al. (2022) revealed an analogy between the self-attention and the residual graph convolutional network (GCN), showing that BERT also suffers from a notorious problem of GCNs, called oversmoothing, i.e., tokens' latent representations become similar to each other at the deeper layers. In every selfattention layer, value vectors are aggregated in a weighted average manner since each row-wise sum of the attention matrix is always 1. Although each self-attention layer has its own attention matrix, this aggregation method causes the oversmoothing problem, not only in Transformers but also in graph neural networks (Oono & Suzuki, 2020; Cai & Wang, 2020; Wang et al., 2021a; Rusch et al., 2023; Keriven, 2022; Zhou et al., 2021a; Gong et al., 2021; Yan et al., 2022; Noci et al., 2022; Shi et al., 2022; Wang et al., 2022; Ali et al., 2023; Wu et al., 2023a; b) . However, we confine our discussion to the oversmoothing of Transformers (cf. Section 2).Being inspired by them, we redesign the self-attention from the perspective of graph signal processing (GSP). However, performing graph convolutions in the self-attention layer may incur non-trivial computational overheads. Therefore, our key design point is to learn a general but effective graph filter with minimal overheads. In general, a graph filter on a graph G is represented by a polynomial expression based on its adjacency or Laplacian matrix -in this regard, the existing self-attention mechanism can be understood as the simplest graph filter with Ā only, where Ā ∈ [0, 1] n×n means a learned attention matrix and n is the number of input tokens.Our proposed graph filter consists of an identity term and two matrix polynomial terms, Ā and ĀK -one can design better filters with more polynomial terms but we avoid it since Transformers already require very large computation. The K-th power, ĀK , may also require high computation when the number of tokens is large. To avoid this, we further approximate ĀK using the elementwise first-order Taylor approximation. Therefore, one can consider that our proposed graph filter is the very next complicated filter after the one used by the original self-attention mechanism. However, its efficacy is tremendous for various Transformers in various fields (cf. Figure 1 ).Our proposed filter enriches the self-attention with more diverse frequency information (see Figure 2(a) ) -low (resp. high) frequency signals on G mean neighboring nodes have similar (resp. different) values. Therefore, our method is able to not only effectively address the oversmoothing problem but also learn better latent representations for downstream tasks. We achieve these results with only tens to hundreds of additional parameters to Transformers.There exist a couple of prior works to enrich the self-attention mechanism with high frequency information (Wang et al., 2022; Bai et al., 2022) . In comparison with them, our proposed graph filter is distinctive in the following aspects: i) our proposed filter is more effective and shows better performance with comparable computational overheads, ii) our proposed filter is well-aligned with recent advancements in the GCN community -in other words, some graph filters used by recent advanced GCN methods are special cases of our proposed graph filter, which is not the case for prior works, and iii) other methods were typically studied for certain domains only whereas we test our method in 6 domains -for instance, DiversePatch (Gong et al., 2021) works only for Vision Transformers.We replace the self-attention layer of selected Transformers in various fields with our proposed graph filter-based layer without changing other parts. Therefore, the accuracy increases in them are solely by our proposed graph filter-based self-attention. These enriched Transformers increase the model performance by 1.63% for image classification, 6.25% for natural language understanding, 0.31% for causal language modeling, 4.03% for graph classification, 4.76% for speech recognition, and 2.40% for code classification (see Figure 1 ). We summarize our core contributions as follows:• We provide a novel perspective on self-attention as a graph filter. This perspective allows us to design more effective self-attention that can address the oversmoothing problem. • We propose a graph filter-based self-attention (GFSA) mechanism that is general yet effective. GFSA learns a graph filter with an identity term and two polynomial terms, which is more effective than the simple self-attention mechanism. • We demonstrate that GFSA can significantly improve the performance of Transformers on a variety of tasks. GFSA achieves improved results on computer vision, natural language processing, graph pattern classification, speech recognition, and code classification. 
self-attention in transformers: 
 The core building block of the Transformer architecture is the self-attention mechanism, which enables the model to learn attention patterns over its input tokens (Vaswani et al., 2017) . The selfattention mechanism, denoted as SA : R n×d → R n×d , can be expressed as follows:EQUATIONwhere X ∈ R n×d is the input feature matrix, W key ∈ R d×d , W qry ∈ R d×d , and W val ∈ R d×d are the key, query, and value trainable parameters, respectively, and d is the dimension of each token. The self-attention mechanism allows the model to weigh the importance of each token in the input sequence relative to the others, enabling the model to capture long-range contextual information better. The Transformer architecture includes multiple layers, each with a multi-head self-attention layer followed by a position-wise feed-forward layer.The self-attention matrix used in Transformers can be seen as a symmetrically normalized adjacency matrix of a graph (Shi et al., 2022; Guo et al., 2023; Maskey et al., 2023) . A weighted graph G with adjacency matrix A can be constructed by using the input tokens as n nodes and the edge weights between node i and node j as exp((XW qry ) ⊺ (XW key )). We can rewrite the self-attention matrix Ā asexp (XWqry) ⊺ i (XWkey)j d k=1 exp (XWqry) ⊺ i (XWkey) k. This allows Ā to be interpreted as the symmetrically normalized adjacency matrix. In other words,Ā = D -1 A, where D = diag(d 1 , d 2 , . . . , d n ) and d i = j A i,j .Our new attention method is designed on top of graph signal processing (GSP) which has a close connection to discrete signal processing (DSP) (Sandryhaila & Moura, 2013; 2014) . In DSP, a discrete signal with a length of n can be represented by a vector x ∈ R n . Let g ∈ R n be a filter that we want to apply to x. The convolution x * g can be written as follows:EQUATIONwhere the index, denoted as i, refers to the i-th element in each vector.GSP can be understood as a generalized concept of DSP. Signals are defined on the nodes of a graph, and the graph's structure influences signal processing operations. In addition, the graph convolution filter with n nodes can be written with a shift operator S as follows:EQUATIONwhere x ∈ R n is a 1-dimensional graph signal, K is the maximum order of polynomial, andw k ∈ [-∞, ∞] is a coefficient.S is an n × n matrix where (i, j)-th element is non-zero if and only if there is an edge from node i to j. Two representative samples of S are adjacency and Laplacian matrices. The linear and shift-invariant graph filter H is the same as K k=0 w k S k with a large enough value of K, which is called matrix polynomial (Marques et al., 2020) . We note that this graph filtering operation can be extended to d-dimensional cases as in Equation 1. Being inspired by (Zou et al., 2022; Maskey et al., 2023) , we rely on the singular value domain analysis to understand the low/high-pass filter characteristics of filters (cf. Fig. 2 ). See more discussion in Appendix N.In the context of self-attention within Transformers, the core part of the self-attention in Equation 1, i.e., ĀX, can be considered as a d-dimensional graph filter with Ā only, where H = Ā. Our goal in this paper is design a simple (for computational purposes) yet effective form of H.Oversmoothing is a phenomenon observed in deep learning models, especially in GCNs (Kipf & Welling, 2017; Veličković et al., 2018) . As information is aggregated over multiple layers for multiple nodes (tokens), latent representations tend to become similar to each other, leading to a loss of distinctiveness in the representations (Oono & Suzuki, 2020; Zhou et al., 2020; Rusch et al., 2023) .Surprisingly, an oversmoothing-like phenomenon is also observed in Transformers (Wang et al., 2022; Shi et al., 2022) . Unlike CNNs, Transformers can not benefit from simply deepening layers after a certain depth. Earlier studies hypothesize that this may be due to issues such as the attention or feature collapse or due to uniformity among patches or tokens (Zhou et al., 2021a; Gong et al., 2021; Yan et al., 2022) . Dong et al. (2021) also point out that the output of a pure Transformer, i.e., an attention mechanism without skip connections or MLPs, tends to converge to a rank-1 matrix (Dong et al., 2021 ). This analysis is followed by (Noci et al., 2022) , which suggests that rank collapses incur vanishing gradients of attention queries and keys.In this context, the self-attention acts as a low-pass filter, since the self attention calculates the weighted average of the value vectors of tokens. Wang et al. (2022, Theorem 1 ) also reveal that the self-attention is a low-pass filter, continuously reducing high-frequency information. This nature contributes to the oversmoothing phenomenon as unique high-frequency features are lost in deeper layers of the network, further worsening the uniformity of token representations. Therefore, we extend the term "oversmoothing" to describe the degeneration challenge observed in Transformers.There have been proposed many empirical countermeasures for Vision Transformer (ViT), such as patch diversification (Zhou et al., 2021b; Gong et al., 2021) , rank collapse alleviation (Zhou et al., 2021a; Zhang et al., 2021) , and training stabilization (Touvron et al., 2021a; Zhai et al., 2023) . Similar alleviating methods have been also proposed in the field of NLP, such as unsupervised learning (Chen et al., 2023) , and resolve the oversmoothing and the token uniformity (or information diffusion) problems (Dong et al., 2021; Yan et al., 2022) . There are studies on utilizing high frequency information via frequency domain analyses (Wang et al., 2022; Bai et al., 2022) , but they are not designed on top of graph filtering perspectives. This paper addresses the oversmoothing problem with graph filters since the self-attention mechanism is a basic graph filtering operation as seen in the previous subsection. 
graph filter-based self-attention layers: 
 Let Ā ∈ [0, 1] n×n , where n is the number of tokens in the input to the self-attention layer, be a selfattention matrix. Since transformers use multi-head self-attentions, there are multiple such matrices.For simplicity but without loss of generality, we discuss only one head in one layer.In the perspective of GSP, Ā corresponds to a special case where i) nodes are completely connected, and ii) Ā is normalized. Ā can be used as a shift operator. When K is large, however, it is hard to calculate ĀK . We use the following element-wise first-order Taylor approximation:EQUATIONwhere Ā2 -Ā is an approximated derivative at the position of K = 1 (see details in Appendix P).At the end, we propose to use the following graph filter where the two lowest-order terms and one high-order term of the matrix polynomial are used:EQUATIONwhere w 0 , w 1 , w K are coefficients and K is a hyper-parameter. The coefficients can be learnable weights and we learn them with gradient descent algorithms.Our proposed graph filter-based self-attention (GFSA) is defined with the graph filter H as follows:EQUATIONWe replace the original self-attention layer in various Transformers with the proposed graph filterbased layer without changing other parts. Therefore, GFSA can be plugged into any Transformers that rely on the self-attention.In this subsection, we provide a theorem that provides an upper bound on the error introduced by approximating the power of a matrix, specifically using the first-order Taylor expansion. The theorem specifically analyzes the error for the matrix ĀK when approximated using a first-order Taylor expansion. Theorem 3.1 (Error bound for first-order Taylor approximation). Define the error term as the difference between the exact value and the first-order Taylor approximation of ĀK :EQUATION) where || • || denotes the L ∞ norm. Then, the error E K can be bounded as follows:EQUATIONThe error bound provides an upper limit for the difference between the true value of ĀK and its approximation using the given formula. When the row-sum of Ā is 1 due to softmax. The proof of Theorem. 3.1 is in Appendix A.Computing high-order matrix powers can be computationally intensive, especially for large matrices such as the self-attention in natural language processing where the number of tokens (words) can be tens of thousands. The first-order Taylor approximation provides a simpler computation that can significantly reduce the required computational resources and time. Theorem. 3.1 ensures that even with this simplification, the error can be bounded and is predictable.This subsection provides a discussion on GFSA in terms of the comparison with other models and the mitigation of the oversmoothing problem.In the field of computer vision, there have been recent researches on adjusting the frequency response of ViT. HAT (Bai et al., 2022) improves ViT by directly increasing the high-frequency components of images through adversarial training, i.e., modifying inputs. Wang et al. (2022) suggest that they re-balance the low and high-frequency components of the attention map and feature map, respectively (Wang et al., 2022) . In the NLP domain, Shi et al. (2022) redesign BERT with multiple fusions in (Shi et al., 2022) , inspired by JKNet (Xu et al., 2018) .Comparison to GCNs Comparisons to GCNs that can be interpreted as graph filters (Kipf & Welling, 2017; Defferrard et al., 2016; Gasteiger et al., 2019) are inevitable. GFSA without a highorder term is analogous to ChebNet (Defferrard et al., 2016) with K = 1. In addition, GFSA reduces to the vanilla GCN (Kipf & Welling, 2017) when K = 1, w 0 = 0, w 1 = 1. GPR-GNN (Chien et al., 2021) , which approximates graph convolutions using the monomial basis, is identical to GFSA if our GFSA only considers up to an order of 1 and learns coefficients. When we use only a high-order term and w K is learned to negative value, GFSA can become similar to the reaction-diffusion layer of GREAD (Choi et al., 2023) , ĀX + β( Ā -Ā2 ), depending on the higher order terms.The key leading to the behaviors of our proposed filter is the coefficients {w 0 , w 1 , w K } -note that in the self-attention of Transformers, w 0 = w K = 0 and w 1 = 1. Since our method can learn any appropriate values for them for a downstream task, it can reduce to low-pass-only, high-pass-only, or combined filters. In particular, our filter reduces to GPR-GNN and GREAD, two popular method preventing the oversmoothing for graph convolutional networks, in certain learned settings on {w 0 , w 1 , w K }. We use Ā2 -Ā to approximate ĀK (see Equation 4). As mentioned earlier, the low/high-pass filter characteristics are decided by {w 0 , w 1 , w K }. Therefore, the approximated ĀK by (K -1)( Ā2 -Ā) and the coefficients {w 0 , w 1 , w K } can alleviate the oversmoothing problem of the self-attention by constituting an appropriate graph filter for a downstream task. 
experiments: 
 In this section, we demonstrate the effectiveness of GFSA through a series of experiments. These experiments encompass various tasks: i) language understanding and causal language modeling, ii) image classification, iii) graph classification, and iv) code classification. We replace the selfattention of base Transformers in those fields with our GFSA. Our modification adds only tens to hundreds of parameters, which are negligible in comparison with the original size of base models.We summarize the runtime of base models vs. base models with GFSA in Appendix L.To investigate the efficacy of GFSA, we present experiments on natural language understanding and causal language modeling tasks in the subsections below.Experimental Setting. We integrate GFSA into three pre-trained large language models: BERT, ALBERT, and RoBERTa. We evaluate them on the GLUE benchmark, which includes three categories of natural language understanding tasks: i) single-sentence tasks CoLA and SST-2; ii) similarity and paraphrasing tasks MRPC, QQP, and STS-B; iii) natural language inference tasks MNLI, QNLI, and RTE. For the MNLI task, we experiment on both the matched (MNLI-m) and mismatched (MNLI-mm) versions. Following (Devlin et al., 2019) , we report Matthews correlation for CoLA, F1 scores for QQP and MRPC, Spearman correlations for STS-B, and accuracy scores for the other tasks. For each task, we select the best hyperparameters for GFSA, and the other hyperparameters are fixed. We compare our GFSA with ContraNorm (Guo et al., 2023) , one of the related methods that address oversmoothing. We finetune ContraNorm with the recommended hyperparameters in the original paper. We initialize with pretrained language model and finetune with added GFSA for 5 epochs. The detailed experimental settings are in Appendix E.1.Results. The results are shown in Table 1 . When GFSA was plugged into backbones, average performance scores improved across all models over pure backbones. This indicates that GFSA is effective in both large models like BERT and RoBERTa, as well as relatively smaller models like ALBERT. It is worth mentioning that in the case of RoBERTa finetuned on the CoLA dataset, there is a large margin increase from 60.34% to 64.11%, which is a 3.77% improvement with only 144 additional parameters. When compared to ContraNorm, GFSA shows a greater performance improvement on average. Figure 4 in Appendix D shows that these performance enhancements can be attributed to addressing the oversmoothing issue through the designed graph filter.Experimental Setting. We also validate the effectiveness of GFSA on causal language modeling problems. We finetune GPT2 on the following three datasets: Penn Treebank (PTB) (Marcus et al., 1993) , WikiText-2 and WikiText-103 (Merity et al., 2016) . Following the evaluation method in (Yao et al., 2022) , we finetune models for 15 epochs with PTB, 4 epochs with WikiText-103, and 10 epochs with WikiText-2, and report the perplexity for sensitivity metric, i.e., higher perplexity means higher sensitivity. The detailed experimental settings are in Appendix F.1. Results. Table 19 shows the perplexity on PTB, WitiText-2, and WikiText-103. Across all datasets, GPT2 with GFSA consistently outperforms the vanilla GPT2. Our GFSA improves the average perplexity from 18.806 to 18.764. Note that the performance improvements are made with only 144 additional learnable parameters for 12 layers with 12 heads, which are negligible in comparison with the size of GPT2.Experimental Setting. We aim to demonstrate the efficacy of our GFSA across a spectrum of ViT backbones with different depth settings and training modes. We choose DeiT (Touvron et al., 2021a) , CaiT (Touvron et al., 2021b) , and Swin (Liu et al., 2021) as backbones, and models are trained from scratch. When training the 12-layer DeiT, we follow the same training recipe, hyperparameters, and data augmentation from (Touvron et al., 2021a) . When training the 24-layer DeiT, we follow the settings of (Gong et al., 2021) and set the dropout rate to 0.2. For Cait, we apply our proposed GFSA only to the patch embedding layer. For detailed experimental settings, see Appendix G.1.Results. All experimental evaluations are summarized in Table 3 . We compare various state-ofthe-art models on the ImageNet-1k benchmark. We select them from three classes: CNN only, CNN + Transformer, and pure Transformer. In the Transformer category, we only test with lighter models having comparable numbers of parameters, such as ViT-S and DeiT-S. The results show that the proposed GFSA successfully enhances Deit, CaiT, and Swin across all depth settings and training methods. GFSA provides additional parameters less than 72 for 12-layer DeiT while improving the top-1 accuracy by 1.63%. Compared to existing techniques, improvements by GFSA already surpasses DeepViT-24B (0.6%) (Zhou et al., 2021a) , LayerScale (0.7%) (Touvron et al., 2021b) , LateInsertion (0.6%) (Touvron et al., 2021b) , and HAT (Bai et al., 2022) (1.38%). To sum up, we observed that both shallow and deep ViTs can achieve the following benefits from GFSA: i) The filter response plot shows GFSA can preserve higher-frequency representation (cf. Figure 2 (a)) and ii) Figure 2 (b) shows that GFSA can mitigate the increase in the cosine similarity of representation as the layer gets deeper. We also show experiments with the same ContraNorm setting in Appendix G.4.Experimental Setting. We conduct automatic speech recognition (ASR) experiments on the Lib-riSpeech1 dataset (Panayotov et al., 2015) , which consists of audio recordings paired with their transcriptions. For implementation, we follow the recipes of SpeechBrain (Ravanelli et al., 2021) and describe the detailed settings in Appendix I.1. For our experiments, we use Branchformer (Peng et al., 2022) , one of the state-of-the-art models for speech recognition, as well as a pure Transformer.Results. 7 in Appendix I.2 depicts the learning curves of train loss and valid loss when using GFSA, showing the effectiveness of our proposed filter.Experimental Setting. To corroborate the efficacy of GFSA on graph transformers, we conduct experiments on a commonly used graph-level prediction dataset (i.e., ZINC) from benchmarking- GNN leaderboards (Dwivedi et al., 2020) and the recent OGB-LSC quantum chemistry regression (i.e., PCQM4M-LSC) challenge (Hu et al., 2021) , which is currently the biggest graph-level prediction dataset and contains more than 3.8M graphs in total. We choose Graphormer (Ying et al., 2021) as a backbone architecture and use its framework2 for implementation. Mean absolute errors (MAEs) are reported for both regression tasks. For detailed experimental setting, see Appendix H.1.Results. Tables 5 and 6 show that Graphormer with GFSA consistently outperforms the vanilla model across all datasets. As can be seen from the train MAE values of Experimental Setting. We conduct a code defect detection task based on Devign dataset provided by (Zhou et al., 2019) . We use RoBERTa (Liu et al., 2019) , CodeBERT (Feng et al., 2020) , PLBART (Ahmad et al., 2021) , and CodeT5 (Wang et al., 2021b) as our backbone models. The detailed settings are in Appendix J.1.Results. Table 7 shows the accuracy of all models; GFSA results better than the base models. The biggest improvement is 2.40% for RoBERTa. In the case of CodeT5-base, using GFSA shows an accuracy of 64.75, an improvement of 1.95% from 63.51. CodeT5-small+GFSA has only about 100 additional parameters compared to CodeT5-small with 60M parameters, and even more impressively, it surpasses the accuracy of CodeT5-base. In Appendix J.2, we include case studies for this task. We also report the results of code clone detection task in Appendix K. In Table 17 , CodeT5-small+GFSA outperforms CodeT5-small with an F1 of 94.36.Our GFSA does not significantly increase training time. We summarize the runtime of base models vs. base models with GFSA in Appendix L. On GLUE tasks in natural language understanding, BERT with GFSA improves average performance from 82.51% to 83.58% (see Table . 1) with an overhead of less than 3 minutes in total training time. Considering the performance improvements, we think the increases in training time are negligible. 
final remarks: 
 Our proposed graph filter-based self-attention (GFSA) mechanism achieves high performance with improvements on a variety of tasks in computer vision, natural language processing, graph pattern classification, speech recognition, and code classification. GFSA is a simple yet effective method that enriches the self-attention in Transformers with more diverse frequency information. This enables GFSA to address the oversmoothing problem and learn better latent representations for downstream tasks. However, our GFSA does not bring significant overheads in those Transformers' empirical runtime complexity. One can use more complicated graph filters to enhance accuracy more, but our goal is to find a balance between accuracy enhancements and overheads in runtime complexity.We believe that GFSA is a promising new direction for improving Transformers. It is simple to implement and can be used in conjunction with other techniques to further improve the performance of Transformers. We hope that our work will inspire more research on graph filter-based self-attention and its applications.In terms of the broader impact of this research on society, we do not see the very negative impacts that might be expected. However, this paper may have implications for the carbon footprint and accessibility of learning algorithms. The computations required for machine learning research are rapidly growing, resulting in a larger carbon footprint (Schwartz et al., 2020) . Our study improves performance and increases runtime very slightly, but the runtime increase is not very significant. However, in future research, it will also be important to study and improve our GFSA by taking carbon footprints into account.GFSA improves the performance of existing Transformer-based models, which can have many positive impacts on society through services that utilize natural language processing, computer vision, and speech recognition. However, it will also be important to improve GFSA by considering other dimensions of AI, such as robustness to adversarial examples, fairness, and explainability.To ensure the reproducibility and completeness of this paper, we include the Appendix with 12 sections. Appendix A provides the complete proof of Theorem. 3.1. Appendix B contains the empirical study on the error related to Theorem. 3.1. Appendix C provides our PyTorch style pseudo code for our GFSA method. The pseudo code helps to implement our GFSA to any Transformers used a pure self-attention. All experiments in the paper are reproducible with additional implementation details provided in Appendices E to K. In an effort to ensure reproducibility, our GFSA code to reproduce the experiment can be found at https://sites.google.com/view/gfsa-iclr/.A PROOF OF THEOREM. 3.1Proof. We begin by observing that the L ∞ norm of Ā2 is bounded by:∥ Ā2 ∥ ≤ ∥ Ā∥ 2 . (9)By using the induction principle, it follows that for any positive integer k,EQUATION)Given that Ā is a matrix normalized with softmax: i) all the elements of Ā lie within [0, 1], and ii) the sum of all the elements in Ā is equal to 1 (potentially less than 1 if an attention mask is used).Then we can calculate the upper bound of L ∞ norm for Ā as follows:EQUATIONNow, considering the error term E K as given by Theorem 3.1, and applying the triangle inequality for matrix norms:EQUATIONFrom the prior expressions, we deduce that ∥ ĀK ∥ ≤ ∥ Ā∥ K ≤ 1 K = 1. Thus, the upper bound of the error term E K becomes as follows:EQUATIONIn this section, we empirically compare the theoretical error bounds in Theorem. 3.1 with the actual errors. Figure 3 shows the theoretical upper bound of E K and the actual E K for the attention of the last layer in a trained pure backbone. DeiT-S and Graphormer are trained on ImageNet-1k and ZINC, respectively, and BERT is finetuned on STS-B. It can be observed that for all models, the actual E K is always smaller than the theoretical error bound. In Figure 2 , we show the visualizations of oversmoothing characteristics in DeiT. We also provide visualizations in other domains. We show the filter response, cosine similarity, and singular value of BERT finetuned on STS-B dataset of GLUE tasks in Figure 4 and Graphormer finetuned on ZINC dataset in Figure 5 .To characterize self-attention, we first analyze the filter response of self-attention in the frequency domain. We follow the method used by Wang et al. (2022) for spectral visualization of the selfattention matrix. As shown in Figure 2 (a), Deit has a near-zero magnitude for the high frequencies, which is characteristic of a low-frequency filter and is likely to result in oversmoothing when applied multiple times.We follow the calculation method of Guo et al. (2023) for cosine similarity. As shown in Figure 2 (b) , the higher similarity as the layers of the model get deeper is related to the oversmoothing problem. To further analyze this issue, we also consider the dimensionality collapse in Transformerbased models. We plot the singular value distribution of the feature in the last block. As shown in Figure 2 (c), insignificant, near-zero values dominate the feature distribution. As layers get deeper, the similarity of features increases and dimensional collapse occurs. The oversmoothing problem is the same in BERT and Graphormer, as shown in Figure 4 and Figure 5 . COLA The Corpus of Linguistic Acceptability (Warstadt et al., 2019) consists of English acceptability judgments drawn from books and journal articles. The target task is a binary classification task, and each sentence is determined to be grammatically acceptable or not.SST-2 The Stanford Sentiment Treebank (Socher et al., 2013) is a dataset in which each sentence is sourced from movie reviews and accompanied by human annotations of their sentiment. The target task is binary sentiment classification for a single sentence.MRPC The Microsoft Research Paraphrase Corpus (Dolan & Brockett, 2005) is a corpus of sentence pairs, which are automatically extracted from online news sources and annotated by humans.The target is to determine whether the sentences in the pair are semantically equivalent.QQP The Quora Question Pairs (Chen et al., 2018) dataset is a collection of question pairs from the community question-answering website Quora. The target is to determine whether the questions in the pair are semantically equivalent.The Semantic Textual Similarity Benchmark (Cer et al., 2017) is a collection of sentence pairs drawn from news headlines, video and image captions, and natural language inference data with human annotation. The target is a regression task to predict a similarity score from 0 to 5.MNLI The Multi-Genre Natural Language Inference Corpus (Williams et al., 2017 ) is a crowdsourced collection of sentence pairs with textual entailment annotations. Given a premise sentence and a hypothesis sentence, the task is to predict whether the premise entails the hypothesis (entailment), contradicts the hypothesis (contradiction), or neither (neutral). The standard test set consists of private labels from the authors and evaluates both the matched (in-domain) and mismatched (cross-domain) sections.QNLI The Stanford Question Answering (Wang et al., 2018) dataset is a question-answering dataset consisting of question-paragraph pairs, where one of the sentences in the paragraph contains the answer to the corresponding question written by an annotator. The task is to determine whether the context sentence contains the answer to the question.RTE The Recognizing Textual Entailment (Bentivogli et al., 2009) dataset comes from a series of annual textual entailment challenges. The target task is a binary entailment classification task.BERT. BERT (Devlin et al., 2019) consists with 12 layers, 12 heads, 768 hidden size, 512 maximum sequence length, and MLP dimension of 3072. RoBERTa. RoBERTa (Liu et al., 2019) consists with 12 layers, 12 heads, 768 hidden size, 514 maximum sequence length, and MLP dimension of 3072.Training. For implementation, we adopt HuggingFace framework. We trained all models with 5 epochs with 32 batch size. The linear learning rate decay is used and initial learning rate is set to 2 × 10 -5 . We use AdamW (Loshchilov & Hutter, 2017) optimizer, and weight decay is set to 0. All models are trained on 1 GPU and of NVIDIA RTX A5000 24GB.In this section, we explore the influence of the polynomial order, denoted as K, in our GFSA, conducting experiments on BERT BASE finetuned with GLUE tasks. We search for values of K from 2 to 10, and the results are presented in Figure 6 . For each dataset, Optimal K exists and the performance of models using GFSA is generally robust to changes in K.Dataset. The benchmark datasets we used are listed below.PTB Penn Treebank (Marcus et al., 1993) dataset is a collection of text documents that have been extensively annotated with linguistic information, primarily syntactic and grammatical structures.WIKITEXT WikiText (Merity et al., 2016) dataset is a collection of over 100 million tokens extracted from the set of verified good and featured articles on Wikipedia. Compared to the preprocessed version of Penn Treebank (PTB), WikiText-2 is over 2 times larger and WikiText-103 is over 110 times larger.GPT2. GPT-2 (Radford et al., 2019 ) is a Transformer pretrained on a very large corpus of English data in a self-supervised fashion without any human labelling on dataset. It automatically generate inputs and labels from those texts, and trained to guess the next word in sentences. For implementation, we adopt HuggingFace Framework3 . For all experiments, GPT2 has 12 layers with 12 attention heads, 768 hidden size and 1024 maximum sequence length, resulting in a total of 117 million parameters.Training. We finetune GPT2 with 4 batch size, 5 × 10 -5 learning rate and linear learning weight decay using adamW (Loshchilov & Hutter, 2017) optimizer. We also apply dropout with probability 0.1. Following (Yao et al., 2022) , we train models for 15 epochs with PTB, 4 epochs with WikiText-103 and 10 epochs with WikiText-2. We use sensitivity metric, i.e., perplexity, which is a commonly used metric to evaluate the performance of language models, particularly in language modeling and text generation tasks. perplexity measures how well a language modeling can predict a sequence of words in a given text or a test dataset. All the experiments are conducted on 1 GPU and of NVIDIA RTX 3090 24GB.We conducted a sensitivity study on K of GPT-2 across all datasets, and the results are presented in Table 8 . For PTB and WikiText-2, GFSA exhibits the best performance when K is high, typically around 8 or 9. However, for WikiText-103, GFSA achieves the best perplexity when K is small, specifically when K is 3 or 4. CaiT-S shows the highest performance of 82.84 when K = 4. For CaiT-S, the accuracy is slightly lower than that of the original CaiT-S when K = 2, but it starts to exceed the accuracy of CaiT-S when K is 3 or higher. To make a fair comparison with ContraNorm (Guo et al., 2023) , one of the related studies that mitigates oversmoothing, we run additional experiments to match their experimental setup.Experimental Setting. We follow the training recipe used by Guo et al. (2023) , which is a slightly modified version of Touvron et al. (2021a) 's recipe. Guo et al. (2023) use AdamW optimizer with cosine learning rate decay. We select the DeiT-T and DeiT-S for ImageNet-100 and ImageNet-1k, respectively. "T" and "S" denote tiny and small model sizes, respectively. For all experiments, the image size is set to be 224x224. We train each model for 300 epochs and the batch size is set to 1024. For ContraNorm, we train with their recommended hyperparameters. All models are trained on 4 GPUs and of NVIDIA RTX A6000 48GB.Experimental Results. In Table 12 , DeiT-T and DeiT-S with GFSA outperform vanilla DeiT-T and DeiT-S in all layer settings. On ImageNet-100, GFSA improves the performance of DeiT-T with 12 layers by 1.52%. The largest gain is a 4.88% improvement on 16-layer DeiT-T. This shows that the effect of GFSA is larger than the effect of ContraNorm. For ImageNet-1k, surprisingly, with 16 layers, GFSA is able to increase the performance of DeiT-S by 80.83%, meaning that GFSA brings benefits with a 3.23% improvement. Sensitivity to K. In Table 13 , we experiment with a sensitivity analysis for K. For ImageNet-100, the performance of GFSA generally improves when K is 4 or 5. On the other hand, GFSA performs better at lower K for settings that are layers 16 and 24 for ImagNet-1k. Dataset. We conduct experiments on the LibriSpeech4 dataset (Panayotov et al., 2015) , which consists of audio recordings paired with their transcriptions. The LibriSpeech dataset has approximately 1,000 hours of read English speech with a sampling rate of 16 kHz. We keep the original 16,000Hz sampling rate and compute 80-dim log-Mel filterbanks for a 25ms sliding window, strided by 10ms. The filterbank features are then normalized to zero mean and unit variance per input sequence. For implementation, we follow the recipes of SpeechBrain (Ravanelli et al., 2021) .Evaluation Metric. Word error rate (WER (%)) is derived from the Levenshtein distance and compares a reference to a hypothesized word-level transcription. It is calculated by summing the number of word insertions, deletions, substitutions and dividing it by the total number of words in the reference transcription.Vanilla Transformer. We use a vanilla Transformer to apply our GFSA. For implementation, we use a SpeechBrain (Ravanelli et al., 2021) Branchformer. We use one of the SOTA models, Branchformer (Peng et al., 2022) to plug-in our GFSA. Branchformer has two parallel branches, one for capturing global interactions using attention and the other for more localized context using convolutional gating MLP. The Branchformer architecture for speech recognition consists of i) 1D convolution to perform striding, ii) Branchformer encoder with 18 layers, 8 heads, embedding dimension of 512, and MLP dimension of 3072, iii) decoder with 6 layers, 8 heads, embedding dimension of 512, a convolutional spatial gating unit (CSGU) dimension of 3072, joint beamsearch, and iv) external Transformer language model with 12 layers, 12 heads, embedding dimension of 768, and MLP dimension of 3072.Training. We follow a training recipe from SpeechBrain (Ravanelli et al., 2021) . The standard LibriSpeech validation sets (dev-clean and dev-other) are used to tune all parameters and select the best models. Test sets (test-clean and test-other) are used only to report final WER performance. We train the pure Transformer for 100 epochs and the Branchformer for 120 epochs with a batch size of 16. We use a data augmentation method on all models using SpecAugment (Park et al., 2019) . SpecAugment applies time and frequency masking as well as time warping to the input spectrum. For Branchformer, we use AdamW (Loshchilov & Hutter, 2017) optimizer with 0.9 and 0.98 coefficients for computing running averages of gradient and its square. The learning rate and weight decay in all models are 0.0008 and 0.01, respectively. We use a connectionist temporal classification (CTC) loss Graves & Jaitly (2014); Zhang et al. (2016) . We also apply dropout with probability 0.1 and label smoothing with weight 0.1 to mitigate overfitting. We fix the random seed as 74443 on all experiments. All models are trained on 1 GPU and of NVIDIA RTX A6000 48GB.Hyperparameters. In Table 16 , we describe main hyperparameters used in the automatic speech recognition task. For Transformer+GFSA and Branchformer+GFSA, we also report the best K hyperparameter.We compare the training and validation curves for LibriSpeech 100h in Figure 7 . The training loss curve of GFSA is lower than the pure Transformer. GFSA stabilizes the loss curve of pure Transformer slightly earlier. Dataset. We use Devign dataset provided by (Zhou et al., 2019) , which is a binary classification task to evaluate whether a C language code is vulnerable to software systems or not.Implementation. We build our experiments on top of the open-sourced code5 and recipes provided by Wang et al. (2021b) .RoBERTa. RoBERTa (Liu et al., 2019) is an encoder-only model trained with masked language modeling on code. All hyperparameters are consistent with the training method in the source code of Wang et al. (2021b) .PLBART. PLBART (Ahmad et al., 2021) is an encoder-decoder model based on BART (Lewis et al., 2020) architecture. PLBART can support understanding and generation tasks. All hyperparameters are consistent with the training method in the source code of Wang et al. (2021b) .CodeBert. CodeBERT (Feng et al., 2020 ) is a model trained on masked language modeling and replaced token detection. CodeBERT is a bimodal pretrained model based on Transformer with 12 layers for programming language and natural language. All hyperparameters are consistent with the training method in the source code of Wang et al. (2021b) .CodeT5. CodeT5 is an encoder-decoder framework with the same architecture as T5 (Raffel et al., 2020) . It aims to derive generic representations for programming language and natural language via pre-training on unlabeled source code. CodeT5-small has 6 encoder layers, 6 decoder layers, 8 attention heads, 512 dimensional hidden states, and 60M parameters. The other models have 12 encoder layers, 12 decoder layers, 12 attention heads, 768 dimensional hidden states, and 220M parameters. All hyperparameters are consistent with the training method in the source code of Wang et al. (2021b) .Training. The pre-trained models mentioned above are applied to this downstream task. We add GFSA directly on top of self-attention. We finetune baselines and GFSA models for 10 epochs with a batch size of 16. We use early stopping strategy with a patience of 2. Models generate binary labels from unigram sequences at the decoder for defect detection task. We employ accuracy for evaluating the code defect detection task. All models are trained on 1 GPU and of NVIDIA RTX A6000 48GB.Training. We finetune both CodeT5 and CodeT5+GFSA for one epoch with a batch size of 16. We also use early stopping with patience of 2. CodeT5 and CodeT5+GFSA encode source code and take the representation to calculate similarity of two code snippets. We employ F1 score for evaluating this task. All models are trained on 1 GPU and of NVIDIA RTX A6000 48GB.Table 17 shows results comparing CodeT5 and CodeT5 with GFSA. The result shows that by using our GFSA, CodeT5 models improve their performance. CodeT5-small+GFSA provides a 0.61% improvment over Code5T-small. Empirical Runtime Analysis. We report the training time of various methods with GFSA in Tables 18 to 23. In general, the training time of methods with GFSA is slightly longer than that of existing methods. For example, the Transformer for the automatic speech recognition task increases from 190.5 seconds to 191.6 seconds on Librispeech 100h dataset, as increases of only 1 second. Instead of computing higher-order polynomial terms, our GFSA approximates them, with only a small increase in runtime, which is not very significant. (Sandryhaila & Moura, 2013; 2014) can be understood as a generalized concept of DSP -in other words, DSP is a special case of GSP where a line graph with n nodes is used and therefore, the graph Fourier transform (GFT) of the line graph is identical to the discrete Fourier transform.In the definition of GFT, we assume that the graph shift operator (GSO) S is diagonalizable. Considering the eigendecomposition of the GSO S = V ⊺ ΛV with eigenvector V , we can write the graph filter output as follows:EQUATIONwhere x ∈ R n is a 1-dimensional graph signal, Λ is a diagonal matrix with eigenvalues, andw k ∈ [-∞, ∞] is a coefficient.However, one can use the singular value decomposition, S = V ⊺ ΛU , when the GSO is not diagonalizable but symmetrically normalized instead of the eigendecomposition (Maskey et al., 2023) .Both the singular value decomposition and the eigendecomposition project the original signal onto a set of basis, but they use different basis sets. In the singular value decomposition, we sort the set of basis in ascending order of their eigenvalues, i.e., Λ, and perform frequency domain-like analyses (Zou et al., 2022; Maskey et al., 2023) .Since the self-attention matrix's row-wise sum is always 1, the following is the case: Ā = D -1 A = 1 N A, where N is the number of tokens. In [1], they define the following symmetrically normalized adjacency matrix (SNA):D -1/2 in AD -1/2out . Since the degree of every node is N in the self-attention matrix, the following is the case:D -1/2 in AD -1/2 out = D -1/2 AD -1/2 = 1 √ N A 1 √ N = 1N A = Ā. Therefore, the self-attention matrix is a special case of SNAs.There are two paradigms of implementing graph filters: i) matrix polynomial which does not require diagonalizability, ii) graph Fourier transform which uses the eigendecomposition for diagonalizable adjacency matrices or the Jordan decomposition for non-diagonalizable adjacency matrices.Those two paradigms have their own weaknesses: i) the matrix polynomial approach requires explicit matrix multiplications, and ii) the graph Fourier transform approach requires expansive spectral decompositions. The matrix polynomial is preferred when the number of matrix multiplications is not many. Otherwise, the graph Fourier transform approach may be better since since the matrix multiplication can be simplified after the eigendecomposition or the Jordan decomposition or the Jordan normal form.Among those two, we use the first matrix polynomial approach with only three non-zero coefficients {w 0 , w 1 , w K } since it does not require the complicated spectral decomposition. Since we do not rely on any explicit spectral decomposition but on the matrix polynomial, any adjacency matrix can be used.The general formulation of first-order taylor approximation at point a is as follows:EQUATIONWe approximate f (K) = ĀK with first-order taylor approximation at point a = 1:EQUATION)Inspired by Brouwer et al. (2019) , which approximates the derivative of hidden states of RNNs as the difference between hidden states, we effectively approximate f ′ (1), the derivative of ĀK estimated at the position of K = 1, with the difference term as f (2) -f (1) = Ā2 -Ā1 . Then the approximated ĀK becomes as follows:EQUATIONThis approximation has two advantages: 1) The approximation for ĀK with Ā and Ā2 provides a simpler computation that can significantly reduce the required computational resources and time (see theoretical analysis in section 3.2). 2) When approximating derivative of ĀK with difference term for graph filter design, our filter can reduce to GPR-GNN and GREAD, two popular GNN methods preventing the oversmoothing for graph convolutional networks, are special cases of our design (see discussion in section 3.3). In other words, our method is more general than those two GNNs.http://www.openslr.org/12https://github.com/microsoft/Graphormerhttps://github.com/huggingface/transformershttp://www.openslr.org/12https://github.com/salesforce/CodeT5https://www.qemu.orghttps://github.com/qemu/qemu/commit/b13ce26d3e8c6682044ae84920f2417b30ce356bhttps://github.com/salesforce/CodeT5 
 
 Appendix:  


Decision: This work proposes enhancing self-attention by considering the higher-order powers of the attention matrix, inspired by graph convolutional networks and graph signal processing, to address the oversmoothing issues of transformers. To reduce computational overhead, the authors suggest using a first-order Taylor approximation of the higher-order powers of the attention matrix. With a slightly larger computational complexity, the proposed technique can improve the performance of transformers in various fields.

Reviewer Py4c points out that a hyperparameter, K (power), needs to be determined, and that searching for K can be computationally expensive. The authors provide evidence that GFSA consistently improves performance across a range of K values. Since K is robust, this concern is addressed.

Reviewer XKs2 pointed out that the Taylor approximation may significantly reduce the capacity of the graph filters. The authors address this issue from both the theoretical and experimental perspectives. Reviewer XKs2 also has concerns about the trade-off between gain and complexity. The proposed method consistently shows improvements on various tasks but with a higher computational complexity. The authors offer some ideas to reduce the computational requirements of the proposed approach.

Reviewer k2id is concerned about the weak baseline and provides several recent methods for comparison. The rebuttal addresses this concern. The authors point out that the recent methods suggested by the reviewer are already included in the paper, but they are in the appendix.

Reviewer bzWT has concerns about novelty, which are addressed during the rebuttal. Reviewer bzWT also has some questions and identifies some issues regarding Theorem 3.1. The authors promise to provide a more rigorous proof for Theorem 3.1.

Reviews: review: paper_summary: paper_summary: The paper proposed a graph-filter-based self-attention mechanism to improve its effectiveness. The authors conduct experiments in various fields, including natural language understanding, computer vision, automatic speech recognition, graph regression, and code classification, showing the generalization of the proposed method. The proposed method is claimed to make a difference in the over-smoothing problem, where representations across layers converge to indistinguishable values, leading to significant performance degradation.
strength_weakness: strength_weakness: 1. Sensitivity of K. The authors did not give instructions on selecting the value of K. The sensitivity of K is discussed in appendices, showing that 'For each dataset, there is optimal K and the performance of models using GFSA is generally robust to changes in K'. All the experiments searched for values of K. However, the search for K is time-consuming.
2. Misleading Figure. Fig 1 shows the performance of the proposed method. However, the inconsistent proportions exaggerate the model's effectiveness.
questions: questions: 1. Miss code. When I was running the experiment of code classification, using the command “python run_exp.py --model_tag codet5_base --task defect --sub_task none” as instructed in the readme file, an error occurred reporting ‘can't open file '/run_gen.py'’ . It seems that some code is missing.
2. More questions about the sensitivity of K. Is it a necessary step to search the optimal K when facing a new dataset? Or is it robust in K? I noticed that, in Theorem 4.1, Ek is relevant to K.
limitations: limitations: The authors addressed the limitations, including effectiveness and efficiency.
paper_summary: paper_summary: This work proposes to enhance self-attention by considering the high-order power of the attention matrix inspired by graph convolution networks and graph signal processing, to overcome the oversmoothing issues of transformers.
To reduce the computational overhead, the authors propose to use a first-order Taylor approximation to the higher-order power of the attention matrix.
With the slightly larger complexity, the proposed technique can improve the performance of Transformers in various fields, across computer vision, natural language processing, etc.
strength_weakness: strength_weakness: 1. The notation in the equation on Line 99 is confusing (the "exponential" in the self-attention matrix).
2. The Taylor approximation well actually hurt the capacity of the graph filters significantly, degenerating to the power of 2, regardless of the value of $K$. 
The eq (10) to degenerate to $\hat{\omega}_0 \boldsymbol{I} + \hat{\omega}_1 \bar{\boldsymbol{A}} + \hat{\omega}_2 \bar{\boldsymbol{A}}^2$ for all $K$, where $\hat{\omega}_0, \hat{\omega}_1, \hat{\omega}_2$ are learnable coefficients. Therefore, this technique is just for the power of $2$ and the Taylor approximation actually does not contribute.
questions: questions: 1. Besides the runtime, can you also provide the GPU memory consumption comparisons between GFSAs and the base models?
limitations: limitations: No specific aware.
paper_summary: paper_summary: This paper proposes a novel approach to enhance the self-attention mechanism in transformers by drawing on graph signal processing principles. The authors reframe the standard self-attention as a low-pass graph filter and introduce a more generalized filter (GFSA) capable of capturing low-pass, high-pass, or combined filtering behaviors. They evaluate the effectiveness of GFSA across diverse tasks, showcasing its potential to improve performance.
strength_weakness: strength_weakness: - While the oversmoothing problem motivates the proposed method, the experiments lack a focused analysis of its impact on transformers with varying depths (number of layers).
- While the paper conducted experiments in a variety of tasks in different fields to show the versatility of the proposed method, not study in depth each task could also be a potential weakness. In particular for the graph regression task, the authors only considered two datasets and a single baseline model (and the improvement over the larger model on PCQMv2 is marginal 0.860 vs 0.862). Stronger baselines such as [GPS](https://arxiv.org/abs/2205.12454) and additional datasets would provide a more rigorous assessment of GFSA's practical value. Additionally, the choice of the baselines in other tasks might also suffer from the same weakness, as I believe most of them are relatively old methods. Finally, their performance statement in Fig.1 may be misleading to practitioners without acknowledging the limitations with their selected baselines.
- Given the abundance of research on oversmoothing in transformers, the paper should include comparisons with more recent and relevant methods (e.g., [64]) to strengthen its claims. Currently, the paper only compares to very few comparison partners (ContraNorm [27] and [73]) or even without any comparison in some tasks.
- The paper states that the oversmoothing issue is due to the low-pass filter nature of the self-attention. By introducing a 2nd order term in Eq.10, they claim that their proposed method can learn both low-pass and high-pass filters, and even combined filters. To validate this empirically, a deeper analysis of the learned coefficients $w_0,w_1,w_K$ across different layers would provide concrete evidence for the GFSA's ability to learn diverse filter types.
questions: questions: - L205: for the self-attention with the skip connection, shouldn't $w_0$ be positive?
- In the NLP experiments, did the pretrained models use the standard self-attention? If so, does this approach make sense to replace them with GFSA only during fine-tuning?
- The paper only discusses the runtime overheads. Does GFSA introduce any potential memory overheads?
limitations: limitations: The paper discussed the additional runtime overhead of GFSA compared to the original self-attention. However, other potential limitations are not discussed, such as potential memory overheads, scalability of GFSA to long sequences, or extendability to efficient/linear transformers.
paper_summary: paper_summary: To overcome the oversmoothing effects in general transformer settings, the author considers to treat the attention module as the graph filter and propose to use a polynomial graph filter (graph signal processing) techniques to alleviate oversmoothing. Specifically,  the author considers the induced attention matrix from features as the adjacency matrix and construct a filter that allows exhibiting high-pass and low-pass filter. As low-pass filters provides smoothing tendency and high-pass filter provides edge tendency, the author leverages an adaptive filter to alleviate oversmoothing effects on Transformer domain.
strength_weakness: strength_weakness: 1. The novelty is very limited. The idea of building adaptive high-pass, low-pass filter is well studied in GNN field and has been leveraged in many works to solve oversmoothing in GNN. The idea of attention module as graph filter is also proposed in many Graph transformer models. The main contribution of this paper is simply change the direction from using attention as graph filters to use graph filters as attentions, which is not very interesting.
questions: questions: In the Theorem F.1, the description is not very clear. I assume  "the sum w0 +w1σi +wkσi^{k}  will be smaller than g(σi)" indicates that g(σi) will become smaller as i increase, but this depends on the scale of w1 and wk, even as σi^{k}->0 with i is large, if the rate wk/w1 is large, such tendency can only be guaranteed asymptotically, in the limited i case, this doesn't always hold true. Please correct me if I am wrong.
limitations: limitations: None

Comments: title: A gentle reminder
comment: Dear Reviewer k2id,

We would like to thank the reviewer once again for taking the time to provide us with valuable feedback, which has enabled us to strengthen our paper with new experiments and clarifications during this rebuttal period. 

As the rebuttal period is nearing its end, we would like to inquire as to whether our additional responses adequately addressed the concerns you raised.

Furthermore, we would like to express our gratitude for your time and efforts during this rebuttal period. We hope that our responses will allow the reviewer to consider a fresh evaluation of our work.

Best regards,

GFSA Authors
Dear Reviewer Py4c,

We thank the reviewer again for your time and feedback that allowed us to strengthen the paper with clarifications during this important rebuttal period. 

As the end of the rebuttal period is fast approaching we were wondering if our answers in the rebuttal were sufficient enough to address the important concerns.

Finally, we are very appreciative of your time and effort in this rebuttal period and hope our answers are enough for the reviewer to consider a fresher evaluation of our work with a potential score upgrade if it's merited.

Kind regards,

GFSA Authors
Dear Reviewers and ACs,

We sincerely appreciate the constructive feedback from all reviewers. Based on your valuable comments, we have made the following improvements:

1. Extended our experiments with recent models:
    - Added results for GPS and Graph-ViT on additional datasets from LRGB and Benchmarking GNNs.
    - Demonstrated consistent improvements across various datasets, further validating the effectiveness of GFSA.
2. Clarified and refined our theoretical analysis:
    - Provided a more rigorous proof for Theorem 3.1.
    - Offered a detailed explanation of how learned coefficients determine filter characteristics.
3. Conducted additional analyses:
    - Visualized frequency responses across layers to demonstrate GFSA's adaptive filtering behavior.
    - Provided GPU memory usage comparisons between backbone models and GFSA.
4. Addressed scalability and efficiency concerns:
    - Demonstrated GFSA's compatibility with efficient/linear Transformers such as Efficient Attention.
    - Showed performance improvements while maintaining efficiency on long-sequence tasks.

After our rebuttal, 2 reviewers expressed satisfaction with our responses:

- Reviewer bzWT **flipped the decision from reject to borderline accept**, recognizing the positive evidence for learning GFSA filters.
- Reviewer XKs2 acknowledged that we addressed most of their concerns, **maintaining the positive evaluation** of our submission.

We sincerely appreciate the further engagement from these reviewers.

However, reviewer Py4c has not yet responded to our rebuttal, and reviewer k2id has not yet responded to our additional rebuttal. We believe that we have satisfactorily addressed all concerns from reviewers Py4c and k2id.

Again, we would like to thank you and all the reviewers for your great efforts in reviewing our paper. If reviewers are satisfied with our response or have any more concerns, please do not hesitate to let us know.

Best regards,

GFSA Authors
Dear Reviewer bzWT,

It's really encouraging to see that our response effectively addresses the concerns you raised. Thank you for recognizing the efforts we've put into our work.

To show  how our extended Theorem 3.1 with GFSA can be connected to constructing the type of filter in practice, we use a toy example to help you understand that
1) we show that the coefficients determine the filter type and
2) we show that the role of K does not change the filter type.

**[Filter type according to cofficients]**

We assume the singular values $\sigma_1, \cdots ,\sigma_5$ as $\\{1.0, 0.8, 0.6, 0.4, 0.2 \\}$, and $K$ is 5. The graph filter of GFSA is defined as $g(\sigma_i)=w_0 + w_1\sigma_i + w_K(\sigma_i + (K-1)(\sigma_i^2-\sigma_i))$.

In the proof of extended Theorem 3.1 with GFSA, we can see that if we use positive coefficients that sum to 1, it is consistent with our proof that it is an exact low-pass filter because $g(\sigma_i)$ for $i > 1$ is always less than 1.

For the exact high-pass filter, assuming the coefficients to be $w_1, w_2, w_K = (-0.5)^0 /1, (-0.5)^1 /2, (-0.5)^K / (K+1)$ as per the proof, we can see that the results in Table below are consistent with the ratio $\frac{g(\sigma_i)}{g(\sigma_1)} > 1$.

And if we set the coefficients to arbitrary values like the last row, we can create an arbitrary filter.

That is, the characteristics of the filter change depending on the coefficients, and GFSA can learn any graph filter that fits the downstream task by learning the coefficients without strict restrictions.

| filter type | coefficients ($w_0, w_1, w_K$) | $ g(\sigma_1), \cdots ,g(\sigma_5)$ |
| --- | --- | --- |
| exact low-pass filter | (0.2, 0.4, 0.4) | 1.00, 0.58, 0.30, 0.14, 0.10 |
| exact high-pass filter | $((-0.5)^0 / (1), (-0.5)^1 / (2), (-0.5)^K / (K+1))$ | 0.75, 0.80, 0.85, 0.90, 0.95 |
| arbitrary filter | (-0.1 , 1.0 , -0.4) | 0.50, 0.64, 0.65, 0.52, 0.28 |

**[The role of $K$ on filter type]**

To understand the effect of $K$ on the characteristics of the graph filter, we analyzed the graph filter according to the value of $K$. For the exact high-pass filter, we report the filtered singular values according to the value of $K \in \\{3, 5, 10\\}$. As shown in the table below, even when the value of $K$ changes, the graph filter still maintains the characteristics of the exact high-pass filter.

| $K$ | $ g(\sigma_1), \cdots ,g(\sigma_5)$ |
| --- | --- |
| 3 | 0.719, 0.785, 0.846, 0.902, 0.954 |
| 5 | 0.745, 0.799, 0.852, 0.903, 0.952 |
| 10 | 0.750, 0.800, 0.850, 0.900, 0.950 |

---

We hope our explanation clears up your one last remaining concern.

Best regards,

GFSA Authors
Thanks for the author's detailed response. I have decided to raise my score to 5. While I agree that the experimental results show positive evidence on the learning of high-pass filter, it is still not clear to me how the revised theory really connect to these results. I appreciate these useful discussions.
Dear Reviewer Py4c,

As the Reviewer-Author discussion period ends in less than 24 hours, we wanted to reach out regarding our response to your valuable feedback. Please let us know if you would like us to help with any further details on our response.

We believe that your comments have allowed us to improve our analysis of the sensitivity of $K$ and address potential misunderstandings in Figure 1. In addition, we have addressed concerns and questions about the sensitivity of K. 

Additionally, we would like to draw your attention to our response to other reviewers, `k2id` and `XKs2`, where we discussed **the scalability of GFSA and its extendability to linear/efficient Transformers**. We believe these findings might be of interest to you as they further show the broader applicability and potential of our method.

Thank you again for your time and dedication in reviewing our work! 

Kind regards,

GFSA Authors
Dear Reviewer k2id,

As the Reviewer-Author discussion period ends in less than 24 hours, we wanted to reach out to you to see if you are happy with our responses. 

We have made efforts to address the concerns you raised, particularly:
1. Providing analysis on oversmoothing correlation with DeiT accuracy
2. Clarifying the statistical significance of our improvements
3. Expanding our comparison with recent baselines
4. Addressing limitations in scalability and extendability

We believe that your comments have allowed us to improve our paper. We would appreciate your thoughts on whether our extended responses and additional experiments have satisfactorily addressed your concerns. If there are any remaining issues or points that require further clarification, please let us know. 

Thank you again for your time and dedication in reviewing our work. 

Kind regards,

GFSA Authors
Dear Reviewer bzWT,

We appreciate your questions regarding the role of $K$ and the nature of our graph filter. We address your questions below:

**[Learning high-pass and low-pass filters]**

Our goal is not to create theoretically exact high-pass or low-pass filters. Instead, we aim to learn optimal graph filters based on coefficients, improving the original self-attention. 

This adaptive behavior can be found in the filter response visualizations provided in Figure 2 of our one-page PDF in general response. We visualized the filters for all 12 layers of BERT with and without GFSA applied. In Figure 2, GFSA learns diverse filter types across layers, evolving from low-pass in early layers to a mix of low and high-pass in middle layers and shifting towards higher-frequency responses in deeper layers. Each layer does not function as a theoretically exact high-pass or low-pass filter but rather as a graph filter that can use frequency information of various scales to suit the downstream task via learnable coefficients.

From the perspective of using learnable coefficients, this approach is similar to polynomial GNNs, such as GPR-GNN [1] and BernNet [3]. They can learn arbitrary filters instead of fixed filters by learning $w_k$. For example, in the case of GPR-GNN [1], any graph filter can be expressed by applying gradient descent to the polynomial coefficients.

**[The role of $K$ in GFSA]**

Thank you for your question about the choice of $K$.

Our goal is not to construct an exact low/high pass filter but to create a graph filter that improves on self-attention. We add an approximated $\mathbf{\bar{A}}^K$ to achieve maximum effectiveness with minimum overhead.

In the case of Theorem 3.1 applied to GFSA, the result of the proof does not change depending on the value of $K$ defined as a hyper-parameter. In other words, $K$ does not directly affect whether the graph filter becomes a high-pass or low-pass filter.

Of course, in the proof of the high-pass filter, there is a condition that $K$ has a sufficiently large value. However, since the characteristic of the graph filter is determined by the coefficient once the value of $K$ is determined, this condition does not mean that $K$ directly affects the characteristic of the GFSA graph filter.

As you observed in the sensitivity study, the performance may not change drastically depending on the value of $K$ itself. This is because the learned coefficients have a more impact on filter behavior than the choice of $K$. Also, Figure 2 in a one-page PDF supports this, showing the varied filter response for each layer for a fixed $K$. Therefore, we can see that the coefficients affect the characteristics of the GFSA graph filter.

> [1] Chien, Eli, et al. "Adaptive universal generalized pagerank graph neural network." *arXiv preprint arXiv:2006.07988*(2020).
>
> [2] Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. "Convolutional neural networks on graphs with fast localized spectral filtering." NeurIPS, 2016.
>
> [3] Mingguo He, Zhewei Wei, and Hongteng Xu. "Bernnet: Learning arbitrary graph spectral filters via Bernstein approximation." NeurIPS, 2021.

---

We hope this clarification addresses your concerns.

Best regards,

GFSA authors
Thanks for pointing that out. I get the point for the low-pass filter now. But then doesn't this implies that the choice of K directly affects if it is a low-pass filter or high-pass? Honestly, although the theorem might be correct after these many conditions, it starts to become far from reality from my perspective. Ideally, I think this should be only related to the sign of w0,w1, and w2, but then things become rather complex and even involve with the choice of K. So how exactly can a model learn some layers of high pass filter and some layers of low pass filter theoretically? When does this occur? Your added sensitivity plot suggests that K doesn't affect the model performance very much. What does that indicate in terms of the fixed theoretical analysis?
Dear reviewer XKs2,

We thank you for considering the gain and complexity of the trade-off. We want to address your concerns about our complexity from 3 perspectives below:

**[GFSA in selective layers]**

Regarding the computational overhead of GFSA, we introduced a strategy for computational complexity in Section 6. By applying GFSA only to even layers, we effectively reduced the runtime increase while maintaining performance similar to that of full-layer integration.

**[Possibility of improving complexity by using an efficient matrix operation]**

As we mentioned in Appendix P, our GFSA computes $\bar{\mathbf{A}}^2$, which has a time complexity of $O(n^2d + n^3)$.  However, assuming we use the algorithm in [1], the time complexity becomes $O(n^2d + n^{2.371552})$. In practical terms, if $n^{0.371552}$ is smaller than $d$, the time complexity of GFSA approaches $O(n^2d)$.

In real-world applications, especially those leveraging GPU acceleration, the practical computational cost of matrix operation could be better than the theoretical bound. Because GPUs with multiple CUDA cores provide acceleration for matrix operations. This means that the actual wall-clock time for these computations can be lower than the theoretical time complexity. 

**[Additional results for GFSA with linear complexity]**

We want to share **additional results** that may address your concern about the computational complexity, which we reported in our response to Reviewers `k2id` and `bzWT`. While our method has $O(n^2d + n^3)$ complexity due to the nature of self-attention, we have found that GFSA can be applied with linear complexity calculations while retaining its benefits.

In experiments using Long Range Arena benchmark [2], we successfully integrated GFSA with Efficient Attention [3], an approach that maintains linear complexity. The results show that Efficient Attention+GFSA outperforms Efficient Attention alone while preserving efficiency. For example, on Image dataset (1K sequence length), Efficient Attention+GFSA uses only 1.33GB memory and 135.8s/1K-steps, compared to 11.20GB and 737.2s/1K-steps for Transformer+GFSA.

| Method | ListOps (2K) | Image (1K) |
| --- | --- | --- |
| Transformer | 37.1 | 38.2 |
| **Transformer + GFSA** | **37.6** | **40.2** |
| Linformer | 37.3 | 37.8 |
| Longformer | 37.2 | 39.1 |
| YOSO-E | 37.3 | 39.8 |
| Efficient Attention | 36.9 | 40.2 |
| **Efficient Attention + GFSA** | **37.9** | **40.4** |

> Note: Results are shown as Accuracy (%)

|  | ListOps (2K) | Image (1K) |
| --- | --- | --- |
| Transformer | 198.3/5.50 | 345.1/5.88 |
| **Transformer + GFSA** | 635.8/ 10.87 | 737.2/11.20 |
| Linformer | 63.4/1.73 | 158.5/3.45 |
| Efficient Attention | 49.2/0.57 | 121.1/1.14 |
|  **Efficient Attention + GFSA** | 53.8/0.67 | 135.8/1.33 |

> Note: Results are shown as Running time (s/1K-steps) / Peak training memory usage (GB)

We also found a way to maintain linear complexity even for the squared operation in GFSA. By designing $\mathbf{\bar{A}}$ as $\mathbf{\bar{A}}=\mathbf{QK}$, we can efficiently compute  $\mathbf{\bar{A}}^2\mathbf{V} = (\mathbf{QK})(\mathbf{QK})\mathbf{V}$, similar to recent linear complexity Transformers [3,4].

These findings show that GFSA can be implemented with linear complexity and still provide performance improvements. This addresses the concern about the computational cost and shows that the gain-complexity trade-off can be more favorable than initially presented.

> [1] Williams et al. New bounds for matrix multiplication: from alpha to omega. In SODA, 2024.
>
> [2] Tay, Yi, et al. "Long range arena: A benchmark for efficient transformers." *arXiv preprint arXiv:2011.04006* (2020).
>
> [3] Shen, Zhuoran, et al. "Efficient attention: Attention with linear complexities." WACV 2021.
>
> [4] Katharopoulos, Angelos, et al. "Transformers are rnns: Fast autoregressive transformers with linear attention." ICML 2020.


---

We hope that our responses address your concerns and that you will be able to increase your rating. If you have any questions, please let us know.

Best regards,

GFSA authors
Dear Reviewer bzWT,

Thanks for your thoughtful review.

However, contrary to your concern, the proof of the low-pass filter does not assume that $K$ approaches infinity. It only assumes that the coefficients are positive and their sum is 1, which is why the inequality holds. The assumption that $K$ goes to infinity is only applied in the proof of the high-pass filter.

We hope our response addresses your concern.
$\left| \sigma_i + (K-1) (\sigma_i^2-\sigma_i) \right| = \left| \sigma_i((K-1)\sigma_i - (K-2)) \right| < \left|\sigma_i((K-1)-(K-2))\right| = \sigma_i$ looks suspicious. When $K->\infty$, I don't think you can make an inequality of shrinking $\sigma_i(K-1)$ to $(K-1)$, this is like claiming 2 $\infty$ < 3 $\infty$, which doesn't make sense. Plus, it is weird to see something that tends to $\infty$ can be bounded by 1.

So I don't think the low-pass filter proof is correct. In fact, It think it means that w2 and $\sigma_i$ term dominates the result. If you divide the K-1 to both denominator and numerator, w0, w1 doesn't seem to have any effect on the final convergence.
Hello, Reviewer. The author has submitted a response to your comments. Whether or not it addresses your concerns, it would be greatly appreciated if you could acknowledge that you have reviewed the reply.
Thank you for the rebuttal.
The rebuttal addresses most of my concerns.

One thing I am not certain about is the gain and complexity trade-off. The proposed method consistently shows improvements on various tasks, with a larger computational complexity $O(N^3)$.

In practice, based on runtime and memory provided, the extra computational cost is acceptable. However, the performance improvement is not remarkable either.

Considering my current score, I tend to retain the current score for now and would like to decide whether to raise the score during the reviewer and AC discussion stage.
**[Responses to Theorem 3.1 and its proof]**

**Response to Q1.**

You are correct, and we thank you for pointing this out. There was a typo in the third step of the high-pass filter proof. We apologize for any confusion this may have caused. To clarify, the corrected one is as follows:

$\left| \frac{\lim_{K \rightarrow \infty} g(\sigma_i)}{\lim_{K \rightarrow \infty} g(\sigma_1)} \right|  = \left|\frac{\lim_{K \rightarrow \infty} w_0 + w_1 \sigma_i + w_K \sigma_i^K}{\lim_{K \rightarrow \infty} w_0 + w_1  + w_K} \right|  =\left|\frac{\lim_{K \rightarrow \infty} 1 - \alpha \sigma_i + (-\alpha)^K \sigma_i^K}{\lim_{K \rightarrow \infty} 1 - \alpha + (-\alpha)^K}\right| = \left|  \frac{ 1 -\alpha\sigma_i }{ 1 -\alpha }\right|  > 1$


**Response to Q2.** 

As you mentioned, Theorem 3.1 assumes that the coefficients have specific values, and the coefficient of the graph filter learned through deep learning cannot always satisfy those exact values. However, what we want to clarify through this theorem is that **the value of coefficients determines the characteristics of the graph filter.**

Our goal in learning the coefficients of GFSA is not to create an exact low-pass or high-pass filter, but to design a graph filter that can appropriately employ frequency information of various scales for downstream tasks. The theorem provides a theoretical foundation for understanding how the coefficients influence the behavior of the filter. In practice, we do not enforce strict constraints on the coefficients during training. Instead, we allow the model to learn the most appropriate coefficients for the task at hand, which may result in filters that combine both low-pass and high-pass characteristics to varying degrees.


**Response to Q3.**

Theorem 3.1 is indeed a proof for the exact $\mathbf{\bar{A}}^K$. However, contrary to your concern, **the characteristic of our GFSA still depends on the value of coefficients** $w_k$. To address your concerns, we extend the proof using the approximated $\mathbf{\bar{A}}^K$ used by our GFSA.

**Proof for low-pass filter:** We prove the low-pass filter result for GFSA. For the case where $w_0, w_1$, and $w_K$ are positive and their sum is 1, we prove that $\left| g(\sigma_i) \right| < 1$.

Since $\sigma_1 = 1$, we have:

$g(\sigma_1)=w_0+w_1\sigma_1+w_K(\sigma_1+(K-1)(\sigma_1^2-\sigma_1))=w_0+w_1+w_K=1$.

Hence, proving the low-pass filter result is equivalent to showing $\left| g(\sigma_i) \right| < 1$, and $g(\sigma_i)$ is bounded as follows:

$\left| g(\sigma_i)\right| =\left| w_0 + w_1\sigma_i  + w_K(\sigma_i + (K-1) (\sigma_i^2-\sigma_i)) \right| \overset{(1)}{<} \left| w_0 + w_1\sigma_i  + w_K\sigma_i \right| = \left|\sigma_i \right|< 1$

This inequality (1) satisfies since $\left| \sigma_i + (K-1) (\sigma_i^2-\sigma_i) \right| = \left| \sigma_i((K-1)\sigma_i - (K-2)) \right| < \left|\sigma_i((K-1)-(K-2))\right| = \sigma_i$.

Therefore, we complete the proof for the low-pass filter.

**Proof for high-pass filter:** When $w_k = (−\alpha)^k/(k+1)$ where $k = 0, 1, K$ and $\alpha \in (0,1)$, we prove:

$\left| \frac{\lim_{K \rightarrow \infty} g(\sigma_i)}{\lim_{K \rightarrow \infty} g(\sigma_1)} \right| = \left|\frac{\lim_{K \rightarrow \infty} w_0 + w_1 \sigma_i + w_K (\sigma_i + (K-1) (\sigma_i^2-\sigma_i))}{\lim_{K \rightarrow \infty} w_0 + w_1  + w_K (1 +  (K-1) (1-1))} \right| \\ =\left|\frac{\lim_{K \rightarrow \infty} 1 - \frac{\alpha}{2}\sigma_i + \frac{(-\alpha)^K}{(K+1)}(\sigma_i + (K-1) (\sigma_i^2-\sigma_i))}{\lim_{K \rightarrow \infty} 1 - \frac{\alpha}{2} + \frac{(-\alpha)^K}{(K+1)}}\right|$
$= \left|\frac{1 - \frac{\alpha}{2}\sigma_i + \big(\lim_{K \rightarrow \infty}\frac{(-\alpha)^K}{(K+1)}(\sigma_i + (K-1) (\sigma_i^2-\sigma_i))\big)}{1 - \frac{\alpha}{2}}\right| \\ \overset{(1)}{=}\left|\frac{1 - \frac{\alpha}{2}\sigma_i}{1 - \frac{\alpha}{2}}\right| > 1$

This equality (1) satisfies since  $\lim_{K \rightarrow \infty}\frac{(-\alpha)^K}{(K+1)}(\sigma_i + (K-1) (\sigma_i^2-\sigma_i)) = \lim_{K \rightarrow \infty}\frac{(-\alpha)^K}{(K+1)}((K-1) (\sigma_i^2-\sigma_i)) = \lim_{K \rightarrow \infty}(-\alpha)^K\frac{(K-1)}{(K+1)}(\sigma_i^2-\sigma_i) = 0$.

Therefore, it shows that the graph filter acts as a high-pass filter.

---

We appreciate your careful analysis of our work. You provide an interesting perspective, which we will gladly add to the revised paper. Your comments have allowed us to focus Theorem 3.1 more closely on our GFSA, which has significantly improved our theoretical foundation.

However, according to our proof, the final ratio you derived is difficult for us to understand. We have encountered some difficulty as the final ratio has $K$ and seems to diverge when $K$ approaches infinity. *If our response does not address your concerns, could you kindly provide us with your derivation?*
Dear Reviewer bzWT,

Thank you for your comments on the computational complexity of GFSA and your careful review and follow-up questions of Theorem 3.1 and its proof. We want to address your questions and concerns in two main parts.

---

**[Response to the computational complexity of GFSA]**

First, to address the computational overhead of GFSA, we have implemented a selective application strategy, as detailed in *Section 6 of* *our main text*. By applying GFSA only to even-numbered layers, we effectively reduce runtime increases while maintaining comparable performance to full-layer integration.

Moreover, we understand your concern about the added complexity in the context of Transformers. As you know, the original self-attention requires quadratic computational cost, which led to the development of efficient/linear Transformers with linear complexity in recent years. To address this, we want to highlight the compatibility of GFSA with efficient/linear Transformers.

As detailed in our response to `Reviewer k2id`, we have conducted experiments showing that:

1. GFSA can be effectively integrated with Efficient attention [1], one of the linear Transformers, maintaining its efficiency benefits while improving performance. Here are some key results:

|  | ListOps (2K) | Image (1K) |
| --- | --- | --- |
| Efficient Attention | 36.9% / 49.2s / 0.57GB | 40.2% / 121.1s / 1.14GB |
| **Efficient Attention + GFSA** | **37.9%** / 53.8s / 0.67GB | **40.4%** / 135.8s / 1.33GB |

> Note: Results are shown as Accuracy (%) / Running time (s/1K-steps) / Peak training memory usage (GB)

2. There are potential efficiency improvements for GFSA itself. By designing $\mathbf{\bar{A}}$ as $\mathbf{\bar{A}}=\mathbf{QK}$, we can compute $\mathbf{\bar{A}}^2\mathbf{V} = (\mathbf{QK})(\mathbf{QK})\mathbf{V}$ in a manner similar to Efficient attention mechanism, maintaining linear complexity even for the squared operation in GFSA.

These findings show that GFSA with a linear Transformer can enhance the performance while preserving the efficiency benefit. For a more detailed discussion of GFSA compatibility with a linear/efficient Transformer, see our response to `Reviewer k2id`, "**4. Limitations (scalability and extendability)**".

> [1] Shen, Zhuoran, et al. "Efficient attention: Attention with linear complexities." WACV 2021.
**4. Limitations (scalability and extendability):**

We apologize for not fully addressing your concerns about limitations earlier and appreciate the opportunity to clarify these important points. 

We conducted additional experiments using the Long Range Arena benchmark[4], which is specifically designed for evaluating performance on long-range dependencies. We tested GFSA on ListOps (2K sequence length) and Image (1K sequence length) datasets using standard Transformers and Efficient Attention [9] models as backbones.

Regarding **scalability** to long sequences, GFSA shows improved performance on these long-sequence tasks. For the Image dataset, Transformer+GFSA outperforms Transformer and some linear Transformers such as Linformer[5], Longformer[6], and YOSO-E[7].

Concerning the **extendability** of efficient/linear Transformers, we successfully integrated GFSA with Efficient Attention[9], demonstrating its compatibility. Efficient Attention+GFSA shows performance gains over Efficient Attention. Importantly, this integration maintains the efficiency benefits of linear transformers. For instance, on the Image dataset, Efficient Attention+GFSA uses only 1.33GB memory and 135.8s/1K-steps, compared to 11.20GB and 737.2s/1K-steps for Transformer+GFSA.

Furthermore, we would like to highlight the potential for efficiency improvements in GFSA. Recent linear complexity Transformers[8,9] propose an approximated self-attention by replacing the softmax operation and rearranging matrix multiplication as $\mathbf{Q(K^\intercal V)}$. In GFSA, the main computational cost comes from calculating $\mathbf{\bar{A}}^2$. However, if we design $\mathbf{\bar{A}}$ as $\mathbf{\bar{A}}=\mathbf{QK}$, then $\mathbf{\bar{A}}^2\mathbf{V} = (\mathbf{QK})(\mathbf{QK})\mathbf{V}$, which allows us to maintain linear complexity even for the squared operation in GFSA by computing it in the same manner as these efficient attention mechanisms. Therefore, the Taylor approximation of the high-order filter in GFSA can be done efficiently.

These results show that our GFSA is scalable to longer sequences and can be effectively extended to efficient/linear transformers. The improvements for longer sequence lengths, along with the efficiency maintained when combined with linear transformers, address concerns about the practical impact of the task.

- Table: Accuracy (%)

|  | ListOps (2K) | Image (1K) |
| --- | --- | --- |
| Transformer | 37.1 | 38.2 |
| **Transformer + GFSA** | **37.6** | **40.2** |
| Linformer | 37.3 | 37.8 |
| Longformer | 37.2 | 39.1 |
| YOSO-E | 37.3 | 39.8 |
| Efficient Attention | 36.9 | 40.2 |
| **Efficient Attention + GFSA** | **37.9** | **40.4** |

- Table: Running time (s/1K-steps) and the peak training memory usage (GB)

|  | ListOps (2K) | Image (1K) |
| --- | --- | --- |
| Transformer | 198.3/5.50 | 345.1/5.88 |
| **Transformer + GFSA** | 635.8/ 10.87 | 737.2/11.20 |
| Linformer | 63.4/1.73 | 158.5/3.45 |
| Efficient Attention | 49.2/0.57 | 121.1/1.14 |
|  **Efficient Attention + GFSA** | 53.8/0.67 | 135.8/1.33 |

> [4] Tay, Yi, et al. "Long range arena: A benchmark for efficient transformers." *arXiv preprint arXiv:2011.04006* (2020).
>
> [5] Wang, Sinong, et al. "Linformer: Self-attention with linear complexity." *arXiv preprint arXiv:2006.04768* (2020).
>
> [6] Beltagy, Iz, Matthew E. Peters, and Arman Cohan. "Longformer: The long-document transformer." *arXiv preprint arXiv:2004.05150* (2020).
>
> [7] Zeng, Zhanpeng, et al. "You only sample (almost) once: Linear cost self-attention via bernoulli sampling." ICML 2021.
>
> [8] Katharopoulos, Angelos, et al. "Transformers are rnns: Fast autoregressive transformers with linear attention." ICML 2020.
>
> [9] Shen, Zhuoran, et al. "Efficient attention: Attention with linear complexities." WACV 2021.

---

We hope that our additional responses will address your unresolved concerns.

Best regards,

GFSA authors
Dear Reviewer k2id,

We would like to thank the reviewers for carefully analyzing our work and raising concerns that remain unresolved. We address the 4 concerns you raised below:

---

**1. Regarding oversmoothing correlation with Transformer performance:**

We would like to highlight that we have reported such an analysis, which provides evidence for the effectiveness in mitigating oversmoothing and improving performance across different depths.

As shown in Table 14, while DeiT can potentially improve with 24 layers due to increased parameters, our cosine similarity analysis (See Fig.2 (a)) shows that oversmoothing at deeper depths could limit performance gains. This is where GFSA shows its effectiveness. GFSA allows the DeiT to better use the increased capacity of deeper layers. For example, GFSA improves DeiT-S by 2.54 points at 12 layers and 1.46 points at 24 layers. GFSA also shows larger improvements over ContraNorm at deeper depths.

For convenience, we re-present the results of DeiT-S in Table 14 below:

| #Layers | 12 | 16 | 24 |
| --- | --- | --- | --- |
| DeiT-S | 77.32 | 78.25 | 77.69 |
| DeiT-S + ContraNorm | 77.80 | 79.04 | 78.67 |
| **DeiT-S + GFSA** | **79.86** | **80.83** | **79.15** |

This depth-wise analysis, combined with our previous layer-wise behavior studies (e.g., cosine similarity), provides our empirical results of GFSA in mitigating oversmoothing and improving performance in varying model depths.

---

**2. Statistical significance of improvements:**

While the improvements in CIFAR-10 (p = 0.184, paired t-test comparing GraphGPS and GraphGPS+GFSA) and MNIST (p = 0.108, paired t-test) may not be statistically significant, Cohen's D values of 0.455 and 0.565 respectively indicate medium effect sizes. These medium effect sizes suggest that ***our improvements are still meaningful*** in practice. As [1] argues, effect size can reveal practical significance that p-values alone might miss
Note that statistical testing was only feasible with GraphGPS, which provided results from 10 runs, unlike Graph-ViT.

For Graph-ViT, it is significant that GFSA can support Graph-ViT to outperform the Graph-MLP-Mixer on the MolTOX21 dataset, as shown below.

| Method (GINE as a graph encoder) | MolTOX21 |
| --- | --- |
| Graph-MLP-Mixer | 0.7868 ± 0.0043 |
| Graph-ViT | 0.7851 ± 0.0077 |
| **Graph-ViT + GFSA** | **0.7895 ± 0.0069** |

In this context, we would appreciate it if you could understand that our GFSA can be effective in broader graph benchmark datasets.

> [1] Sullivan, Gail M., and Richard Feinn. “Using effect size—or why the P value is not enough.” Journal of Graduate Medical Education 4.3 (2012): 279-282.

---

**3. Comparison with recent baselines:**

We thank your suggestion for a more systematic comparison. To address this, we would like to emphasize that our full Table 12 in Appendix includes a comprehensive comparison of models aiming to improve upon DeiT, including the most relevant baselines we could fairly compare with our approach.
To strengthen our comparison, we have now included PRepBN[2] and GTP-ViT[3], which were not initially included in our analysis. To ease a clear comparison with our 12-layer DeiT model, we provide a concise overview of GFSA's performance relative to the most relevant and recent baselines, including PRepBN. We believe this addition offers a more systematic evaluation of image classification.

| Method | Top-1 Acc |
| --- | --- |
| DeiT-S (12-layers) | 79.8 |
| + LayerScale | 80.5 |
| + LateInsertion | 80.5 |
| + ClassAttention | 80.6 |
| + AttnScale | 80.7 |
| + FeatScale | 80.9 |
| + HAT | 80.9 |
| + Diverse | 80.6 |
| + ContraNorm | 80.4 |
| + NeuTRENO | 80.7 |
| + *PRepBN* [2] | *80.2* |
| + *GTP* [3]  | *79.5* |
| **+ GFSA** | **81.1** |

> [2] Guo, Jialong, et al. "SLAB: Efficient Transformers with Simplified 
Linear Attention and Progressive Re-parameterized Batch Normalization." ICML 2024. 
>
> [3] Xu, Xuwei, et al. "GTP-ViT: Efficient Vision Transformers via Graph-based Token Propagation." WACV **2024.

---

***continued in the next comment***
Thanks for the clarification on the matrix power part. While I believe that such matrix power has been utilized commonly in the early-works of GNN resolving heterophilic graphs (such as [1]), a taylor approximation does provide an easy computation savoir. However, since the self-attention matrix is dynamically changed rather than a static adjacency, this adds on a matrix power computation for each forward phase, which I believe is non-trivial computation cost. I also believe that this part should be added to the main text rather than appendix, this confused the reader's understanding of what the paper is trying to achieve.

Since the paper proposed to use matrix power directly as a filter for both high and low pass filter learning, it becomes important that Theorem 3.1 should be carefully inspected as it lays the theoretical foundation for the paper. For your revised theorem and proof, I have the following questions:
1. The proof for your high-pass filter case doesn't look right. Although the conclusion I think remains, but in the third step, isn't that be $\frac{1-\alpha \sigma_i + (- \alpha)^K \sigma_i^K}{1 - \alpha+(- \alpha)^K} $ ?
2. The assumption for low pass filter requires learnable constrained by sum to 1 and the assumption for high-pass filter is even stricter. In general, what constrains can we make in either loss or forward process to ensure such conditions? What guarantees we can learn such weights that satisfy the assumptions?
3. Theorem 3.1 is applied to the exact A_{k} case, while the author has provided a bound for how the approximated polynomial is close to the exact case, it seems non-trivial to directly adapt the conclusion of exact singular value analysis to the approximate case. Especially the assumption requires K to be sufficiently large. I made a simple derivation following the revised proof with the formula Equation 10 replacing the A-{K} polynomial. From what I observed, the final ratio is:

$|g(\sigma_i)/g(\sigma_1)| = \frac{\sigma (1- \sigma)}{1-\frac{K-1}{K-2}}$ with $K->\infty$. This suggests that the final filter depends only on the singular value (or the learned directed normalized adjacency matrix), but independent of the learnable w_{0},w_{1},w_{2}. If this is the case, then I would question the necessity of the learnable parameters as this is similar to the red case which is altering the eigenvalue of the learned A directly.

I am very concerned about the accuracy of this part as this is a key novelty (or at least theoretically) and the key reason why method should work and I am worried that the non-trival adaptation from exact case to approximate case leads to a illusion that $w_0,w_1, w_k$ is the key.



[1] Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Steeg, G.V. &amp; Galstyan, A.. (2019). MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing. ICLR.
Thank you for your detailed response. However, some of my concerns are still not fully addressed. 
- W1: to clarify my point, my concern is whether oversmoothing really correlates with the transformer's performance. So a more fair setup would be to measure the performance of a transformer model with varying depth and compare it with GFSA (for each layer number).
- W2: thank you for the additional results. However, the improvement is not statistically significant as is most of the time within the confidence interval of the baseline method.
- W3: thank you for pointing me to the relevant tables. I don't think putting important results in the Appendix is a good practice. Furthermore, after checking the results, I found only one additional baseline (DeiT-S + NeuTRENO) conducted on an image classification task, and the improvement is again very marginal. I believe a more systematic comparison of the proposed method and more recent baselines on all considered tasks would largely strengthen the conclusions of this work.
- Unfortunately, you did not address my points mentioned in the **Limitations**, particularly the scalability of GFSA to long sequences, or extendability to efficient/linear transformers. I believe these points are essential to assess the practical impact of this work.
Dear reviewer XKs2,

We would like to provide additional clarification to address your concern about our Taylor approximation method.

To further demonstrate that our GFSA does not degenerate to second-order terms and that the Taylor approximation contributes meaningfully, we would like to emphasize the empirical result we have already provided in our paper, specifically in Appendix S, Table 37.

For your convenience, as shown in Table 37 of the paper here:
| Datasets | #Params | CoLA | SST-2 | MRPC | QQP | STS-B | MNLI-m/mm | QNLI | RTE | Avg |
|----------|---------|------|-------|------|-----|-------|-----------|------|-----|-----|
| BERT_BASE | 110M | 56.79 | 93.81 | 88.70 | 88.32 | 88.16 | 84.96/84.15 | 91.63 | 66.06 | 82.51 |
| + GFSA (approximated $\mathbf{\bar{A}}^K$) | 110M | 59.56 | 94.15 | 90.60 | 88.46 | 88.33 | 85.12/85.06 | 91.95 | 68.95 | 83.58 |
| + GFSA (actual $\mathbf{\bar{A}}^K$) | 110M | 59.85 | 94.27 | 89.80 | 88.43 | 88.32 | 84.95/84.89 | 91.76 | 68.23 | 83.39 |

This data clearly shows that our GFSA method with the approximated $\mathbf{\bar{A}}^K$ achieves performance very close to that of using the actual $\mathbf{\bar{A}}^K$. The average performance across all GLUE tasks is higher for the approximated $\mathbf{\bar{A}}^K$ compared to the actual $\mathbf{\bar{A}}^K$.

These results successfully relieve the reviewer's concern that our approach degenerates to only second-order terms. If this were the case, we would expect to see a significant performance drop when using the approximated $\mathbf{\bar{A}}^K$ compared to the actual $\mathbf{\bar{A}}^K$. Instead, we observe comparable or even slightly improved performance. Additionally, the approximation allows us to balance computational efficiency with model expressiveness.

We believe this empirical evidence, along with our previous response, addresses your concern about the effectiveness of our Taylor approximation approach. Please let us know if you have any remaining concerns, and we will happily respond. Thank you!

Best regards,

GFSA authors