Graph Convolutions Enrich the Self-Attention in Transformers!
Authors: Jeongwhan Choi
Hyowon Wi
Jayoung Kim
Yehjin Shin
Kookjin Lee
Nathaniel Trask
Noseong Park
Venue: NeurIPS 2024 poster (2024)
Keywords: Transformer
self-attention
oversmoothing
graph filter
Primary area: deep_learning_architectures

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.

Graph Convolutions Enrich the Self-Attention in Transformers!
Jeongwhan Choi"
Hyowon Wi* KAIST hyowon. wi@kaist.ac.
Yonsei University
j jeongwhan choi@yonsei.eee ac.
Jayoung Kim
Yehjin Shin KAIST
KAIST
jayoung www@kaist..c.kk...
yehjin. wwwwwksist..n...
Kookjin Lee Arizona State University kookj in. lee@asu. edu
Nathaniel Trask University of Pennsylvania ntrask@seas upenn edu edu
Noseong Park KAIST noseongkkaist.ad ac. kr
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 Trans- former models the oversmoothing problem, where representations across layers converge to indistinguishable values, leading to significant performance degrada- tion. We interpret the original self-attention simple graph filter and redesign it from graph signal processing (GSP) perspective. We propose a graph-filter based self-attention (GFSA to learn 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 various fields, including computer vision, natural language processing, graph-level tasks, speech recognition, and code classification.
Automatic Speech Recognition
Causal Language Modeling (PTB)
Introduction
(LibriSpeech 960h)
4.55%
Transformers arguably one of the best feats in the field of deep learning. They are now show- ing state-of-the-ar performance in various fields, ranging from computer vision to natural lan- guage processing, prediction tasks on graphs,
Image Classification (ImageNet-1kk
Tangfome
Language Understanding (CoLA)
163%%
4.25%
Backhones
speech recognition, and so forth 777 [6 60 61
2.40%
GFSA
19
74
101
45
51
59
38 95 72
Code
Graph Regression
Recently, there have been several studies con-
Classification (Devign)
(2INC)
ducted on better understanding them 25 80];
there exists a common agreement among re- searchers that the self-attention is one of the
Figure 1: Performance improvements (%) of our GFSA when integrated with different Transformer backbones in various domains. We achieve these results with only tens to hundreds of additional parameters to Transformers.
keys leading to the success.
"Equal contribution. 1 Corresponding author.
'The source code of GFSA is available at: httppp///gghaab..coo/////ccaaacs
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

0.9
DelT
Normatizad Magnitute
Deil + GPSA
DeiT GFSA
0.8
Cogine Siillrity
0.8
Normelize Singuler
6.66
0.6
0.4
0.4
0.3
0.2
DelT
0.2
- DeiT GFSA
0.0
100
100
50
100
150
Frequency
Layer Index
Singular Value
(a) Filter response
(b) Cosine similarity
(c) Singular value
Figure 2: Filter frequency response, cosine similarity, and singular values on ImageNet Ik for DeiT-S and DeiT-S GFSA. Details and more visualizations in Appendices Caddd D
However, there also exist several studies pointing out potential limitations of the self-attention [10 For instance, Shi al. [71] 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 the deeper layers. In every self-attention 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
1 25 28
Transformers but also in graph neural networks [54 79 66. 37 101 25
92 53
80
However, we confine our discussion to the oversmoothing of Transformers (see Section 2
Being inspired by them, we redesign the self-attention from the perspective of graph signal processing (GSP) in particular, we resort to GSP on directed graphs since the attention matrix is asymmetric. However, performing graph convolutions in the self-attention layer may incur non-trivial computa- tional overheads. Therefore, our key design point is to learn a general but effective graph filter with minimal overhead. In general, graph filter on a graph based on its adjacency or Laplacian matrix - in this regard, the existing self-attention mechanism can be understood the simplest graph filter with A only, where A [0, 1]mxn means a learned attention matrix and n is the number of input tokens.
represented by a polynomial expression
Our proposed graph filter consists of an identity term and two matrix polynomial terms, A and AK One can design better filters with more polynomial terms, but we avoid since Transformers already require very large computation. The K-th power, AK may also require a high computation when the number of tokens is large. To avoid this, we further approximate A using the element-wise 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 tremendous in various fields (cf. Fig. I..
Our proposed filter enriches the self-attention with more diverse frequency information (see Fig. 2[a) a)) low (resp. high) frequency signals on 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.
There exist a couple of prior works to enrich the self-attention mechanism with high frequency information 80 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 domains for instance, PavcrsePatch [25] works only for Vision Transformers (ViTs).
We replace the self-attention layer of selected Transformers 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.3 1% for

---

causal language modeling. 4.03% for graph regression, 4.76% for speech recognition, and 2.40% for code classification (see Fig. D Our core contributions are as follows:
We provide novel perspective self-attention as a graph filter. This perspective allows us to design more effective self-attention that can address the oversmoothing problem.
We propose graph filter-based self-attention (GFSA) mechanism, integrating an identity term and two polynomial terms for general yet effective than the simple self-attention mechanism (Section 3)
We demonstrate that GFSA improves the performance of Transformers on variety of tasks. GFSA achieves improved results on natural language processing, computer vision, speech recognition, graph-level tasks, and code classification (Sections 5.1 5.6).
We devise a strategy to selectively apply GFSA to even-numbered layers, effectively miti- gating the computational overhead while preserving GFSA's performance (Section 6
2 Background & Related Work
2.1 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 [77]. The self-attention mechanism,
denoted as SA: Raxd Raxd, can be expressed as follows:
XW gry (Kee))
SA(X) = softmax
X W AXW val:
Vd
where X Raxd is the input feature matrix, Wkey E Rdxd W Rdxd and Waat E Rdddd are the key, query, and value trainable parameters, respectively, and is the dimension of each token. The self-attention mechanism allows the model to weigh the importance 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 position- position-wise feed-forward layer.
2.2 Self-Attention and Graph Convolutional Filter
The self-attention matrix used in Transformers has the form of symmetrically normalized adjacency -the symmetrically normalized adjacency matrix special case of asymmetric (or directed) adjacency matrix where each row normalized and is frequently used for the graph signal processing (GSP) on directed graphs 49] A weighted graph with adjacency matrix A can be constructed by using the input tokens as n nodes and the edge weights between node i and node
matrix where each token become a node 71 28
exp((X Way) ) (X Waey)) )4). We can rewrite the self-attention 2 exp (X Way) (X
matrix Asj as exp ((X W.n)] (X Wwy)y)
This allows to be interpreted as the symmetrically normalized adjacency matrix. In other words, Ā A, where = diag(di, d2,..., dn) and d, -,
Our new attention method is designed on top of GSP which has a close connection to discrete signal processing (DSP) [67 68). DSP, discrete signal with a length can be represented by a vector IR" Let I be filter that we want to apply to The convolution g can be written as follows:
(2)
1=1
where the index, denoted as i, refers to the i-th element each vector.
GSP can be understood generalized concept of DSP. Signals are defined on the nodes of graph, and the graph's structure influences signal processing operations. addition, the linear and shift-invariees graph convolution filter H with n nodes can be written with shift operator S as
3

---

follows- - S can be from a directed graph [48]
y Hæ S x,
where x RR 1-dimensional graph signal, K the maximum order of polynomial, and Wi [-00, oc] is a coefficient. S is an there is an edge from node to j. Two representative samples of S are adjacency and Laplacian matrices. The graph filter H is the same as Ek=o wx with a large enough value of K, which be extended to
matrix where ji. element is non-zero if and only
called matrix polynomial [48] We note that this graph filtering operation d-dimensional cases as in Eq. ①T Being inspired by Zou et al. [106] and Maskey et al. [49], we rely on the singular value domain analysis to understand the low/high-pass characteristics of filters directed graphs (cf. Fig. 2 See more discussion in Appendices and F
In the context of the self-attention within Transformers, the core part of the self-attention in Eq. (.) ie., AX, can be considered as a d-dimensional graph filter with A only, where H = A. Our goal in this paper is to design a simple (for computational purposes) yet effective form of H.
2.3 Oversmoothing in GCNs and Transformers
Oversmoothing is phenomenon observed in deep learning models, especially in GCNs 39 78 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 [54] [14 66].
Surprisingly, an oversmoothing-like phenomenon is also observed in Transformers [80 71 Unlike CNNs, Transformers can not benefit from simply deepening layers after a certain depth. Earlier studies hypothesize that this may be due issues such as the attention feature collapse or due uniformity among patches or tokens [0T 25 92). Dong et al. [18 also point out that the output of a pure Transformer, i.c., an attention mechanism without skip connections MLPs, tends to converge to rank-1 matrix (18). This analysis is followed by (53). 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. [80] Theorem 1] also reveal that the self-attention is 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" describe the degeneration challenge observed in Transformers.
There have been proposed many empirical countermeasures for ViT, such as patch diversification [102] 25 rank collapse alleviation [1o 1991, and training stabilization [74 98). Similar alleviating methods have been also proposed the field of NLP, such as unsupervised learning [9]. and resolve the
oversmoothing and the token uniformity (or information diffusion) problems [8 92 There
studies on utilizing high frequency information via frequency domain analyses 80 4 but they are not designed on top of graph filtering perspectives. Dovonon et al. (20] find that Transformers inherently low-pass filters, but oversmoothing depends on the eigenspectrum of the self-attention layers. They propose a reparametrization of the Transformer weights, ensuring that oversmoothinng does not occur.
not
Our paper addresses the oversmoothing problem with graph filters since the self-attention mechanism a basic graph filtering operation as seen in the previous subsection.
3 Graph Filter-based Self-Attention Layers
Let A E [0, 1jnxn, where n is the number of tokens in the input to the self-attention layer, be a self-attention matrix. Since Transformers use multi-head self-attentions, there multiple such matrices. For simplicity, but without loss of generality, we discuss only one head one layer.
From the GSP perspective, using À as the shift operator, graph filter can be represented as matrix polynomial filter, as mentioned Section 2.2 We aim to design this matrix polynomial filter using the two lowest-order terms and one high-order term in Eq. (3). The following theorem shows that,

---

despite using the three terms, the filter can be either a low-pass filter or a high-past filter, depending on the coefficient values.
Theorem 3.1 (Filter characteristics based coefficient values). Let A be self- reff-attention matrix interpreted as graph with connected components. Consider the polynomial graph filter defined by En= A where W2, W....., WK-- O and only Wo, W1, and wK are non-zero. If the coefficients wx for k 0, 1, K are positive and their sum 1, then the polynomial filter acts as low-pass filter, attenuating high-frequency components and promoting smoothness across the graph. Conversely, wi (-a)* e for 0, K. K and (0,1) with sufficient large K, the polynomial filter exhibits high-pass filter behavior.
The proof of Theorem 3.1 in Appendix G Based on Theorem 3.1
we propose to use the follow- ing graph filter, HoESA, where the two lowest-order terms and one high-order term of the matrix polynomial are used:
HGFSA Wol + i A WK WK A
where wo. Wi, wk are coefficients and K is a hyper-paramete, where K 2 2. The coefficients can be learnable weights and we learn them with gradient descent algorithms.
Approximation of the high-order term. In Eq. 4). it is costly to calculate A when is large, so we need way approximate the high-order term AK in GFSA. We use the first-order Taylor approximation at point 1 for this purpose:
[(x Ma) + (())((
thus, we approximate f(K) A as follows:
S(K) = A (1)+
(6)
Computing the derivative of A directly at the evaluation point requires high computational costs. To overcome this problem, we adopt the forward finite difference method, which approximates derivatives with the difference term:
f(K) = f(K + h) f(K)
A KKth AK
h
where the approximation error is (1 To balance the trade-off between computational efficiency and accuracy, we h This method is inspired by the approach Brouwer et [6], which uses the difference term between two consecutive hidden states in discrete time to approximate the derivatives. Therefore, we approximate A as:
f(K) A f(1) + (A² A)(K -)
(8)
( A).
The approximation for AK with À and - provides simpler computation that can significantly reduce the required computational resources and time.
GFSA: our graph filter-based self-attention. Our proposed graph filter-based self-attention (GFSA) is defined with the graph filter HOESA follows:
GFSA(X) HGFSA X XWaa. val, HoPSA 1o w À wK A (K 1) A)),
(9)
(10)
where the last term is the approximated AK from Eq. ( We replace the original self-attention layer in various Transformers with the proposed graph filter-based layer without changing other parts. Therefore, GFSA can be plugged into any Transformers that rely on the self-attention. For pseudocode, see Appendix[]
*Calculating the power of matrix for small l requires high computational cost since it is calculated by diagonalizing the matrix using Schur normal form (3].
5

---

4 Properties of GFSA
This section analyzes the theoretical error of the A approximation used by GFSA and how GFSA can mitigate oversmoothing. We also explain the meaning of GFSA's high-order term in the context of Transformers and provide comparisons of GFSA in other models.
Theoretical characteristies of approximation error in GFSA. 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 following theorem specifically analyzes the error of matrix A when approximated using a first-order Taylor expansion.
Theorem 4.1 (Error bound for approximated high-order term in GFSA). Define the error term, EK, as the difference between the exact value and approximated value of A", which is given by Ex = || (A+ (K- - (A A)) where || denotes the Frobenius norm. Then, the error bound can be shown that Ex S 2/nk.
The error bound provides an upper limit for the difference between the actual value of A and its approximation. The proof of Theorem 4.1 is in Appendix H It shows theoretical validity for using approximations to the high-order term in the filters of our GFSA. In terms of performance, we report a difference of approximately A between the actual calculated values in Appendix
How to alleviate the oversmoothing problem? The key leading to the low/high pass filtering behavior of our proposed filter is the coefficients {wo, wi; wx] note that in the self-attention of Transformers, wi = WkK = 0 and wi = 1. Since our method can learn any appropriate values for them for a downstream task, it can be reduced to low-pass-only, high-pass-only or combined filters. According to Theorem 3.1] our graph polynomial filter can be said to be low-pass filter when W1, WK are positive and high-pass filter when they negative. Therefore,
method can learn the appropriate coefficients {wo, W1, wx) } for downstream tasks, so it can be reduced to a low-pass-only call-pass-olly. combined filter, alleviating the oversmoothing problem of self-attention.
The meaning of the high-order ferm in GFSA in the context of Transformers. Existing self- attention only captures simple pairwise similarities between tokens and limited in capturing high-order dependencies. For example, given the two sentences, "Books are more expensive than pencils" and "Books are cheaper than computers", to understand the relationship between "computers" and "pencils", we need to capture the high-order dependencies connected through the "Book" token. However, is difficult to capture these high-order dependencies with traditional self-attention [[03] Therefore, from a Transformer perspective, the approximated A in GFSA can be interpreted as being able to capture these high-order dependencies.
Comparison to Transformers. In the field of computer vision, there has been recent research on adjusting the frequency response of VIT. HAT [4] creates adversarial examples by altering clean images with high-frequency perturbations and jointly trains the ViT on clean images and adversarial examples. Through this, they aim to solve the problem of the ViT being unable to capture high- frequency by allowing us to capture the sighfreeuency components of the images. However, HAT has the disadvantage of requiring more epochs than the existing ViT, as it must perform adversarial training some initial epochs and train normally in the remaining epochs. Wang al. [80] use the concept of DSP, which is special case of GSP, to isolate the lowest frequency component in the Fourier domain and use a filter learned by rescaling the low and high-frequency components. On the other hand, our GFSA extends the concept to graph signal processing and redesigns self-attention as a graph filter. While GFSA seeks to design a better graph filter by interpreting self-attention as a graph filter, Shi et al. [71] are inspired by JKNet (91), and they solve the oversmoothing problem by fusing the hidden vectors of each layer. However, their method has a limitation with memory increasing, and they only applied it to BERT.
Comparison to GCNs. Comparisons to GCNs that can be interpreted as graph filters 39 15 24 are inevitable. GFSA without a high-order term is analogous to ChebNet [i5] with K = 1. In
addition, GFSA reduces to the vanilla GCN [39 when K 1, wp = 0, w 1. GPR-GNN [2]
which approximates graph convolutions using the monomial basis, is identical to GFSA if it only considers up to first order and additionally uses a K-order term and learns the coefficients. When

---

use only a high-order term and wK is learned to negative value, GFSA can become similar to the deactionddiffusin layer of GREAD 13 AX + 3(A A²), depending on the higher order terms.
Experiments
In this section, we demonstrate the effectiveness of GFSA through series of experiments. These experiments encompass various tasks: i) language understanding and causal language modeling, ii) image classification, iii) graph-level task, and iv) code classification. We replace the self-attention 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.
5.1 Experiments on Natural Language Understanding
Sefting. We integrate GFSA into 3 pre-trained large language models: BERT, ALBERT, and RoBERTa. We evaluate them on the GLUE benchmark, which includes 3 categories of natural language understanding tasks: single-sentence, ii) similarity and paraphrasing, and iii) natural language inference tasks. For each task, we select the best hyperparameters for GFSA, and the other hyperparameters are fixed. The detailed experimental settings are in Appendix K.1
Results. The results are shown in Table 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 the case of RoBERTa finetuned on the CoL.A dataset; there is significant 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. Fig. 5 in Appendix C shows that these performance enhancements can be attributed to addressing the oversmoothing issue through the designed graph filter.
Table 1: Results comparison on GLUE benchmark. Avg denotes the average performance.
Method
#Params CoLA SST-2 MRPC QQP STS-B MNLI-m/mm QNLI RTE Avg
BERT 16
110M
56.79
93.81
88.70
88.32
88.16
84.96/84.15
91.63 66.06 82.51
ContraNorm
110
59.89
93.92
89.88
88,51
88.36
85.11/84.50
91.84
69.31 83.48
GFSA
110M
59.56
94.15
90.60
88.46
88.33
85.12/85.06
91.95 68.95 83.58
ALBERTBASE BASE
40
11M
57.86
92.32
91.80
85,30
90.37
85.37/84.37
91.76
76.90 84.01
+ ContraNorm
11M
57.45
93.00
92.83
87.78
90.55
85.06/84.57
92.28 78.70 84.69
GFSA
11M
60.21
93.23
92.47
87.79
90.63
85.29/84.92
92.17
78.70 85.05
ROBERTABASE
44
125M
60.34
94.84
92.28
88.86
89.99
87.94/87.30
92.57
78.70 85.87
ContraNorm
125M
63.06
95.41
93.17
88.91
90.34
87.88/87.40 40
92.82
80.51 86.61
GFSA
125M
64.11
95.41
93.52
89.09
90.35
87.99/87.54
92.97 80.14 86.79
5.2 Experiments on Causal Language Modeling
Setting. We also validate the effectiveness of GFSA on causal language modeling problems. We finetune GPT2 [ on the following datasets: Penn Treebank (PTB) [47]. WikiText-2, and WikiText- 103 [50] Following the evaluation method in Yao et al. [93). 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. The detailed experimental settings are in Appendix L.
Results. Table 2sows the perplexity on PTB, WitiText-2, and WikiText-119% Across all datasets, GPT2 with GFSA consistently outperforms the vanilla GPT2. Our GFSA improves the aver- age perplexity from 18.806 to 764. Note that performance improvements
Table 2: Results comparison on GPT-2 finetuned with GFSA. Avg denotes the average performance.
Method #Params PTB
WikiText-2 WikiText 103
Avg
GPT2
117M 19.513
20.966 20.923
15.939
18.806
+ GESA
117M
19.450
15.919
18.764
made with only 144 additional learnable parameters for 12 layers with 12 heads.
7

---

5.3 Experiments on Vision Transformers
Sefting. We aim demonstrate the efficacy of our GFSA across a spectrum of ViT backbones. We choose DeiT [74], CaiT [75], and Swin [4]] as the backbone, and the models are trained from scratch. When training the 12-layer DeïT, we follow the same training recipe, hyperparameters, and data augmentation from Touvron et al. 74] For detailed experimental settings, see Appendix M.
Results. The experimental evaluations summarized in Table We compare various models the ImageNet-IK Ik benchmark. The results show that the proposed GFSA successfully enhances DeïT, CaïT, and Swin across all depth settings and training methods. GFSA provides additional parameters less than 72 for 12-layer DeiT while improving top-1 accuracy by 1.63%. To sum up, we observed that both shallow and deep ViTs can achieve the following benefits from GFSA: i) The filter response shows GFSA can preserve GFSA mitigates the increase in the cosine similarity of representation
frenuerrfruuncyy representation (cf. Fig. 2 (a)) and ii) Fig. (b) shows that
the layer gets deeper. We further compare with state-of sate-offthee-rt models that use Fourier transforms rather than graph filters in Appendix M.5
We also show results under the same settings as ContraNorm
Appendix M.6
Table 3: Results comparison on ImageNet- 1k. Our full results with other models are Appendix M.4
Category
Method
Input Size
#Layers
#Params
Top-1 I Acc
DeiT-S 77
224
12
22M
79.8
DeiT-S AttnScale 30
224
12
22M
80.7
DeiT-$ FeatScale
80
224
12
22M
80.9
DeiT-S + ContraNorm
224
12
22M
80.4
Swin-S [45]
224
12
50M
82.9
Transformer
DeiT-S 74
224
24
43M
80.5
CaïT-S 775
224
24
47M
82.6
DeiT-S + AttnScale
80
224
24
44M
81.1
DeiT-S FeatScale
80
224
24
44M
81.3
DeiT-S ContraNorm
224
24
43M
80.7
DeiT-S GFSA
224
12
22M
81.1
DeiT-S GFSA
224
24
43M
81.5
GFSA
CaïT-S + GFSA
224
24
47M
82.8
Swin-S GFSA
224
12
50M
83.0
5.4 Experiments on Graph-level Tasks
Setting. To evaluate the efficacy of GFSA on graph-level tasks, we conduct experiments on broader range of datasets. We use datasets from Long-Rane Range Graph Benchmark (LRGB) [21 (e.g.. Peptide-func and Peptide-struct), Benchmarking GNNs (22] (e.g., ZINC, MNIST, CIFARIO), Open Graph Benchmark (OGB) dataset [32] (e.g.. Molhiv and MolTox21), and OGB-LSC dataset (i.e.,
66 as our backbone architectures. following their original experimental protocols for fair comparison. For GPS, we replace its self-attention module with our GFSA while maintaining its best configuration and other hyperparameters. For Graph- ViT, we apply GFSA to the Hadamard self-attention method, which He et al. (30 propose as optimal. For detailed experimental setting, see Appendix 0.1
PCQM4M-LSC) KK We choose Graphormer (94), Graph- ViT 330 and GPS
Results. Tables 5 and show consistent performance improvements when GFSA integrated
with backbone architectures. Graph-ViT GFSA shows improvements on all datasets. On Peptide- func, achieves a 0.65% increase AP. Notably, in PCQM4M, incorporating GFSA improves validation MAE by 7.20%. Due to space constraints, the results with standard deviation are included in Appendix 0.2
5.5
Experiments Automatic Speech Recognition
Setting. We conduct automatic speech recognition (ASR) experiments on the LibriSpeech which consists of audio recordings paired with their transcriptions. We Branch-
dataset 555
http://www.opesslz

---

Table 5: Results on PCQM4M and PCQM4Mv2
Table 4: Results on ZINC
PCQM4M
PCQM4Mv2
Method
#Params
MAE (4)
Method
#Params
Train (4) Validate (4) Train (L) Validate (L)
Graphormer
500K
0.1240
GFSA
500K
0.1189
Graphormer
48.3M
0.0535
0.1286
0.0250
0.0862
GFSA
48.3M
0.0312
0.1193
0.0249
0.0860
Table 6: Experimental evalutation of GFSA plugged into GPS and Graph- VIT. Results marked
with it indicate settings where we conducted our own experiments due unavailable Hadamard self-attention performance in He et al. [30]'s 's paper.
Peptide-fune Peptide-struct
MNIST
CIFARIO
Molhiv
MolTOX21
ZINC
Method
AP (t)
MAE (L)
Accuracy (1) Accuracy (1) ROCAUC (1) ROCAUC (1)
MAE (4)
GPS
0.6535:t0001
0.2500
0.9805=t0.003 0.7230:10006
0.070
GFSA 0.6593-10.004
0.2496-00.013
0,9814:10004 0.7244 1.000088
0.069++0000
Graph- ViT 0.6919 oos 10,2474:10m16 + GFSA 0.69641a..025 0.2461 10.024
0.9820 0.6967.10.000 0.7792:tn.1149 0.7851 1:000 0.0849
0.982611..00 0.6987 0.7830-Ln.nte 0.7895 n.000 0.0845 10.0032
former [59] and pure Transformer. For implementation, we follow the recipes of SpeechBrain 65 and the detailed settings are in Appendix NN.1
Results. Table 7 compares word error rates (WERs) LibriSpeech 100h and 960h. For 100h, Transformer+GFS. achieves 10. 10.30/25.30 33 on the test clean/other set, which is a 6.53% improvement over the Transformer for the WER of the test clean. For 960h, Transforme++GFAA shows WER result of 2.31 in test clean, a 4.55% improvement over Transformer and Branchformer+GFS. A achieves 2.31/5.49 with LM on the test clean/other sets. Fig. in Appendix N.2 depicts the learning curves of train loss and valid loss when using GFSA, showing the effectiveness of our proposed filter.
Table 7: Results for ASR training on LibriSpeech 100h and 960h with GFSA
LibriSpeech 100h
LibriSpeech 960h
Method
#Params
test-clean WER test-other WER test-clean WER test-other WER
Transformer 71.5M
11.02
25.42
2.42
5.50
+ GFSA
71.5M
10.30
24.30
2.31
5.49
Branchformer
109.8M
9.63
22.43
2.13
5.00
+ GFSA
109.8M
9.60
22.25
2.11
4.94
5.6 Experiments on Code Classification
Table 8: Results on code classi- fication. The number in (f) indi- cates the improvement rate.
Setting. We conduct code defect detection task based on De- vign dataset provided by Zhou et al. [005]. We use RoBERTa [4].
CodeBERT 23]. PLBART and CodeT5 84 as our backbone models. The detailed settings are in Appendix P.I
Method
Accuracy
RoBERTa
62.88
Results. T the accuracy of all models; GFSA results better than the base models. The biggest improvement is 2.40% for RoBERTa. In the case of -- using GFSA shows an accuracy of 64.75, an improvement of 1.95% from 63.51. C5deTT- SFalI+GFSA has only about 100 additional parameters compared to Code -smmll with 60M parameters, and even more impres- sively, it surpasses the accuracy of CodeTS-base. The biggest improvement is 2.40% for RoBERTa. In Appendix P.2 we include case studies for this task, We also report the results of the code clone detection task in Appendix Q
+ GFSA
64.39 (1 2.40%)
CodeBERT
64.31
+ GFSA
64.49 (1 0.12%)
PLBART
62.63
+ GFSA
62.96 0.52%)
CodeT5-small
63.25
+ GESA
63.69 (t 0.70%)
CodeTS-base
63.51
+ GFFAA
64.75 (t 1.95%)

---

6 Discussion on Runtime Overheads
Limitation. The introduction of our GFSA layer results in slight increase in training and inference time. We report the runtimes when plugging GFSA A in Appendices R a For GLUE benchmark, integrating GFSA into BERT enhances the average performance from 82.5 % to 83.58% (see Table with more overhead of less than 36 seconds per epoch based on average training time (see Table 23 Considering the improvements. the increases in training time are negligible.
GFSA in selected layers: a strategy to mitigate the limi- tation. As GFSA requires more calculation than the orig- inal self-attention, the runtime after using GFSA slightly
81.5
81
800
Runtime (s per epoch)
88.
Top-1 Accuracy
81.0
81.0
700
increases. Our experiments initially applied GFSA across all Transformer layers (as discussed in Section however, to reduce computational load, we propose selective ap- plication strategy. For this purpose, GFSA is used only on even-number nennnnumeeedd layers. In Tables 35 39 of Appendix TT] the results show that this strategy effectively reduces run- time increases while preserving comparable performance to the full-layer GFSA integration. Notably, the selective application of GFSA cuts the per-epoch runtime increase by 6..90% relative to its full-layer application, with only 7.39% increase in runtime per epoch compared to the
80.5
595
600
551
80.0
79.8
500
79.5
DeiT-S
GFSA
GFSAAvan
Figure 3: Effectiveness of our selective layer strategy ImageNet-1k. This shows out strategy's s ability to maintain accuracy benefits while mitigating run- time increases.
backbone model in Table 39
GFSA in linear Transformers. Although GFSA re-
800
Runtime per 1000 steps
quires additional computation for calculating A we
700
explore integrating GFSA with linear attention vari-
600
Trans. GFSA
ants to maintatin efficiency and scalability. Recent ap-
500
proaches (36] 70 achieve linear complexity by reformu-
400
11.82x
Faster
lating softmax operations and reordering matrix multipli- cation in self-attention. We apply similar principles to compute second-order self-attention efficiently, enabling HarSA calculation with linear complexity with respect to sequence length. Fig. 4 shows the performance, run- time and GPU usage changes when applying our GFSA to Transformers with linear complexity. GFSA still improves performance compared to the backbone model, while the increase in time and GPU usage is minimal. Notably, when GFSA is applied to Efficient Attention [70]. the perfor- mance is improved and the runtime is 11.82 times faster than when GFSA is applied to the vanilla self self-attention. This shows that GFSA can be effectively implemented with linear complexity architectures while preserving its benefits and providing a solution for addressing computational concerns.
300
Trans.
100
Attn.
Lin. YOSO-E
Eff Attn.
GFSA
0 36.8
37
37.2 37.4 37.6
37.8
38
Accuracy (%)
Figure 4: Performance (x-axis), runtime (y-axis), and GPU usage (circle sizes) of various Transformers and integrated GFSA on Long-Range benchmark
7 Conclusion
Our proposed GFSA achieves high performance with improvements on variety of tasks. GFSA is a simple yet effective method that enriches self-attention in Transformers with more diverse frequency information. This enables GFSA to address the oversmoothing problem and Iearn 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 suggests promising new direction for improving Transformers. GFSA can be implement with simple way and used in conjunction with other techniques to further improve the performance of Transformers. Considering the ongoing advancements in large language models, such as GPT-4 I and LLaMA (76), we hope that our approach may offer new insights for enhancing their performance and efficiency.
10

---

Acknowledgements
N. Park was partly supported by the Korea Advanced Institute of Science and Technology (KAIST) grant funded by the Korea government (MSIT) (No. G04240001, Physics-inspired Deep Learning, 10%), Institute for Information & Communications Technology Planning & Evaluation (IIPP) grants funded by the Korea government (MSIT) (No. RS-2020-11201 1366,,,,, Artificial Intelligence Graduate Research Hub Project, 50%),
School Program (Yonsei University), 20%; No. RS-2024-00457888 and Samsung Electronics Co., Ltd. (No. 240136, KAIST Semiconductor Research Fund (2nd), 10%). K. Lee acknowledges support from the U.S. National Science Foundation under grant IIS 2338909. Dr. Trask acknowledges funding under the Department of Energy under the Mathematical Multifaceted Integrated Capability Centers program.
References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report arXiv preprint arXiv:2303.08774, 2023.
[2] Wasi Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. Unified pre-training for program understanding and generation. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2555-2668,, 2021.
[3] Ameen Ali, Tomer Galanti, and Lior Wolf. Centered self-attention layers. arXiv preprint arXiv: 2306.01610 2023.
[4] Jiawang Bai. Li Yuan, Sau-Tao Xia, Shuicheng Yan, Zhifeng Li. and Wei Liu. Improving vision transformers by revisiting high-frequeng, components. In European Conference on Computer Vision, pages 1-18. Springer, 2022.
[5] Luisa Bentivogli, Peter Clark, Ido Dagan, and Danilo Giampiccolo. The fifth pascal recognizing textual entailment challenge. TAC, 7:8, 2009.
[6] Edward De Brouwer, Jaak Simm, Adam Arany, and Yves Moreau. GRU-ODE-Bayes Con- tinuous modeling of sporadically-obsere time series. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[7] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 00:::2006.33318. 2020.
[8] Daniel Cer, Mona Diab, Eneko Agirre, Inigo Lopez-Gazpio, and Lucia Specia. Semeval-2017 task I; Semantic textual mouullarty-multliingee and cross-lingual focused evaluation. arXiv preprint arXiv: 00055, 2017.
[9] Nuo Chen, Linjun Shou, Ming Gong, Jian Pei, Bowen Cao, Jianhui Chang, Daxin Jiang, and Jia Li. Alleviating ovo-sshgg for unsupervised sentence representation. arXiv preprint arXiv:2305.0m 56154, 2023.
[10] Tianlong Chen, Zhenyu Zhang, Yu Cheng, Ahmed Awadallah, and Zhangyang Wang. The principle of diversity: Training stronger vision transformers calls for reducing all levels of redundancy. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12020-12030, 2022.
[11] Zihan Chen, Hongbo Zhang, Xiaoji Zhang, and Leqi Zhao. Quora question pairs, 2018
[12] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized PageRank graph neural network. In Proceedings of the International Conference Learning Representations (ICLR), 2021.
[13] Jeongwhan Choi, Seoyoung Hong, Noseong Park, and Sung-Bae Cho. Gread: Graph neural reaction-diffusion networks. In International Conference on Machine Learning (ICML), pages 5722-5747. PMLR, 2023.

---

[14] George Dasoulas, Kevin Scaman, and Aladin Virmaux. Lipschitz normalization for self- attention layers with application graph neural networks. In International Conference on Machine Learning (ICML., pages 2456 2466. PMLR, 2021.
[15] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
[16] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume I (Long and Short Papers), pages 4171 4186, Minneapolis, Minnesota, June 2019. 9. Association for Computational Linguistics. doi: 10. 18553/ 1423..
org/N19- 1423
[17] Bill Dolan and Chris Brockett. Automatically constructing a corpus of sentential paraphrases. In Third International Workshop Paraphrasing (IWP2005), 2005.
[18] Yihe Dong. Jean- -aatitap Cordonnier, and Andreas Loukas. Attention is not all you need: Pure attention loses rank doubly exponentially with depth. In International Conference on Machine Learning (ICML), pages 2793-2803. PMLR, 2021.
[19] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In Proceedings of the International Conference Learning Representations (ICLR), 2021.
[20] Gbëtondji JS Dovonon, Michael M Bronstein, and Matt J Kusner. Setting the record straight on transformer oversmoothing. arXiv preprint arXiv:2401.0433 2024.
[21] Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Thirty-sixth Conference Neural Information Processing Systems Datasels and Benchmarks Truck, 2022. URL https: https://openrrevees wttp://www...eeooooooiiiiei///a.
[22] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1 1-8,, 2023.
[23] Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al. CodeBERT: pre-trained model for programming and natural languages. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 1536,1577, 2020.
[24] Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[25] Chengyue Gong, Dilin Wang, Meng Li, Vikas Chandra, and Qiang Liu. Vision transformers with patch diversification. arXiv preprint 114.:22304..2753,, 2021.
[26] Alex Graves and Navdeep Jaitly, Towards end-to-end speech recognition with recurrent neural networks. In International Conference on Machine Learning (ICML), pages 1764-1772 PMLR, 2014.
[27] Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, et al. Conformer: Convolution--agmennte transformer for speech recognition. arXiv preprint 00X00:2005.08100, 2020.
[28] Xiaojun Guo, Yifei Wang, Tianqi Du, and Yisen Wang. ContraNorm: A contrastive learning perspective on oversmoothing and beyond. In Proceedings of the International Conference on Learning Representations (ICLR), 2023.
12

---

[29] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[30] Xiaoxin He, Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit/mlp-mixer to graphs. In International conference machine learning (ICML), pages 12724-12745. PMLR, 2023.
[31] Nicholas J Higham. Functions of matrices: theory and computation. SIAM, 2008
[32] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems (NeurIPS),
2020.
[33] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB- LSC: large-scale challenge for machine learning on graphs. arXiv preprint arXiv:2103.09430, 2021.
[34] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 4700-4708, 2017.
[35] John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zine: a free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7):1757-1766 2012.
[36] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In International conference on machine learning, pages 5165. PMLR, 2020.
[37] Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over) smoothing. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 2268- 2281, 2022.
[38] Jayoung Kim, Yehjin Shin, Jeongwhan Choi, Hyowon Wi, and Noseong Park. Polynomial- based self-attention for table representation learning. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp. editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 24509 220020..222...2. PMLR, 21-27 Jul 2024.
URI. htt.ttttt:///reeee
mlm wwa..press/vve press/v235 v235 kim24ae...... html
[39] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference Learning Representations (ICLR), 2017.
[40] Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. arXiv preprint arXiv: 1942, 2019.
[41] Siddique Latif, Aun Zaidi, Heriberto Cuayahuitl, Fahad Shamshad, Moazzam Shoukat, and Junaid Qadir. Transformers in speech processing: A survey, arXiv preprint arXiv:2303.11607, 2023.
[42] James Lee-Thorp. Joshua Ainslie, Ilya Eckstein, and Santiago Ontanon. Fnet: Mixing tokens with fourier transforms. arXiv preprint arXiv:2105.0382. 2021.
[43] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7871-7880, 2020.
13

---

[44] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy. Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: robustly optimized bert pretraining approach. arXiv preprint arXiv:1907 1692, 2019.
[45] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference on computer vision, pages 10012-10022, 2021.
[46] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 1xX1v1771..51001, 2017.
[47] Mitchell Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building a large annotated corpus of english: The penn treebank. 1993.
[48] Antonio G. Marques, Santiago Segarra, and Gonzalo Mateos. Signal processing directed graphs: The role of edge directionality when processing and learning from network data. IEEE Signal Processing Magazine, 37(6):99 116, 2020. doi: 10.1 109/MSPP2020.3314559
[49] Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach to oversmoothing. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
[50] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv: 0774449 2016.
[51] Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to graph transformers. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL HithuumiBi2ddhbh
https://openreviiet
[52] Tam Nguyen, Tan Nguyen, and Richard Baraniuk. Mitigating over-smoothing in transformers via regularized nonlocal functionals. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2023.
[53] Lorenzo Noci, Sotiris Anagnostidis, Luca Biggio, Antonio Orvieto, Sidak Pal Singh, and Aurelien Lucchi. Signal propagation in transformers: Theoretical perspectives and the role of rank collapse. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 27198-27211, 2022.
[54] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In Proceedings of the International Conference on Learning Representa- tions (ICLR), 2020.
[55] Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an asr corpus based on public domain audio books. In 20/5 IEEE international conference on acoustics, speech and signal processing (ICASSP), pages 5206-522 5210. IEEE, 2015.
[56] Daniel Park, William Chan, Yu Zhang, Chung- Chiu, Barret Zoph, Ekin D Cubuk, and Quoc V Le. Specaugment: A simple data augmentation method for automatic speech recognition. Interspeech 2019, 2019.
[57] Badri Patro and Vijay Agneeswaran. Scattering vision transformer: Spectral mixing matters. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2023.
[58] Badri N Patro, Vinay P Namboodiri. and Vijay Srinivas Agneeswaran. Spectformer: Frequency and attention is what you need in a vision transformer. arXiv preprint arXiv:2304.06446. 2023.
[59] Yifan Peng, Siddharth Dalmia, Ian Lane, and Shinji Watanabe. Branchformer: Parallel mlp-attention architectures to capture local and global context for speech recognition and understanding. In International Conference on Machine Learning (ICML.), pages 17627-17643.
PMLR, 2022.
[60] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et Improving language understanding by generative pre-training. 2018.
14

---

[61] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[62] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21()):548-555), 2020.
[63] Ladislav Rampäšek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 14501-14515, 2022.
[64] Yongming Rao, Wenliang Zhao, Zheng Zhu, Jiwen Lu, and Jie Zhou. Global filter networks for image classification. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 980-993, 2021.
[65] Mirco Ravanelli, Titouan Parcollet, Peter Plantinga, Aku Rouhe, Samuele Corell, Loren Lugosch, Cem Subakan, Nauman Dawalatabad, Abdelwahab Heba, Jianyuan Zhong, Ju-Chieh Chou, Sung-Lin Yeh, Szu-Wei Fu, Chien-Feng Liao, Elena Rastorgueva, François Grondin, William Aris, Hwidong Na. Yan Gao, Renato De Mori, and Yoshua Bengio. SpeechBrain: general-purpose speech toolkit, 2021. MiXiv:210.00462.
[66] T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A survey on oversmooth- ing in graph neural networks. arXiv preprint arXiv: Arxiv-2303.10999 2023.
[67] Aliaksei Sandryhaila and José MF Moura. Discrete signal processing graphs. IEEE transactions on signal processing, 6147):144411656 2013.
[68] Aliaksei Sandryhaila and Jose MF Moura. Discrete signal processing on graphs: Frequency analysis. IEEE Transactions on Signal Processing. 62(12):3042-3054 2014.
[69] Roy Schwartz, Jesse Dodge, Noah A Smith, and Oren Etzioni. Green AL. Communications of the ACM, 63(12):54 06.5546-32200 2020.
[70] Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li. Efficient attention: Attention with linear complexities. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, pages 3531-3539, 2021.
[71] Han Shi, Jiahui Gao, Hang Xu, Xiaodan Liang, Zhenguo Li, Lingpeng Kong, Stephen Lee, and James T Kwok. Revisiting over- smoothing in bert from the perspective of graph. In Proceedings of the International Conference on Learning Representations (ICLR), 2022.
[72] Yehjin Shin, Jeongwhan Choi, Hyowon Wi, and Noseong Park. An attentive inductive bias for sequential recommendation beyond the self-attention. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 8984-8992, 2024.
[73] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang. Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing, pages 1631-1642, 2013.
[74] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles. and Hervé Jégou. Training eita--effiiient image transformers & distillation through attention. In International Conference on Machine Learning (ICML), pages 10347-10357. PMLR, 2021.
[75] Hugo Touvron, Matthieu Cord, Alexandre Sablayrolles, Gabriel Synnaeve, and Hervé Jégou. Going deeper with image transformers. In Proceedings of the IEEE/CVE international conference on computer vision, pages 32-42, 2021.
[76] Hugo Touvron, Thibaut Lavril, Gautier Izacard. Xavier Martinet, Maric-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv: 1397/, 2023.
[77] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems (NeurIPS), volume 30, 2017.
15

---

[78] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph Attention Networks. Proceedings of the International Conference Learning Representations (ICIR), 2018.
[79] Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural network. In IJCAI, 2021.
[80] Peihao Wang. Wenqing Zheng. Tianlong Chen, and Zhangyang Wang. Anti-oversmoothing in deep vision transformers via the fourier domain analysis: From theory to practice. In Proceedings of the International Conference Learning Representations (ICLR), 2022.
[81] Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.0477 2020.
[82] Wei Wang, Ming Yan, and Chen Wu. Multi guati-granuulrity hierarchical attention fusion networks for reading comprehension and question answering. arXiv preprint arXiv: 18l..11994.14 2018.
[83] Wenhan Wang, Ge Li, Bo Ma, Xin Xia, and Zhi Jin. Detecting code clones with graph neural network and flow augmented abstract syntax tree. In 2020 IEEE 27th International Conference Software Analysis, Evolution and Reengineering (SANER), pages 261-271, 2020. doi:
10. 100199/AAAE247752200000000000
[84] Yue Wang, Weishi Wang, Shafiq Joty, and Steven CH Hoi. CodeT5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 8696-
8708. 2021.
[85] Alex Warstadt, Amanpreet Singh, and Samuel R Bowman. Neural network acceptability judgments. Transactions of the Association for Computational Linguistics, 7:625 641, 2019.
[86] Ross Wightman. Pytorch image models.
httpss///giiaub..om//ruuggg
pytorch- inat--iommeemmelesse 2019.
[87] Adina Williams, Nikita Nangia, and Samuel R Bowman. A broad-coverage challenge corpus for sentence understanding through inference. arXiv preprint arXivv1704.054266 2017.
[88] Haiping Wu, Bin Xiao, Noel Codella, Mengehen Liu, Xiyang Dai, Lu Yuan, and Lei Zhang CvT: Introducing convolutions to vision transformers. In Proceedings of the IEEE/CVF international conference on computer vision, pages 22-31, 2021.
[89] Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention-based graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
[90] Xinyi Wu, Zhengdao Chen, William Wei Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2023.
[91] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning (ICML), pages 5453-5462, 2018.
[92] Hanqi Yan, Lin Gui, Wenjie Li, and Yulan He. Addressing token uniformity in transformers via singular value transformation. In Uncertainty in Artificial Intelligence, pages 2181-2191. PMLR, 2022.
[93] Zhewei Yao, Xiaoxia Wu, Conglong Li, Connor Holmes, Minjia Zhang, Cheng Li, and Yuxiong He. Random-Itd: Random and layerwise token dropping brings efficient training for large-scale transformers. arXiv preprint arXiv:221 I1 1586, 2022.
[94] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 28877-28888, 2021.
16

---

[95] Youn- Yeol Yu, Jeongwhan Choi, Woojin Cho, Kookjin Lee, Nayong Kim. Kiseok Chang, ChangSeung Woo, ILHO KIM, SeokWoo Lee, Joon Young Yang, SOOYOUNG YOON, and Noseong Park. Learning flexible body collision dynamics with hierarchical contact mesh transformer. In The Twelfth International Conference on Learning Representations, 2024. httptttts///oomeee
net/ forum? Serrumiid-9yy22u55
[96] Li Yuan, Yumpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zi-Hang Jiang, Francis EH Tay, Jiashi Feng, and Shuicheng Yan. Tokens-to-token vit: Training vision transformers from scratch imagenet. In Proceedings of the IEEE/CVF international conference computer vision, pages 558-567, 267, 2021.
[97] Zhanpeng Zeng, Yunyang Xiong, Sathya Ravi, Shailesh Acharya, Glenn M Fung, and Vikas Singh. You only sample (almost) once: Linear cost self-attention via bernoulli sampling. In International conference on machine learning, pages 2331-123322 PMLR, 2021.
[98] Shuangfei Zhai, Tatiana Likhomanenko, Etai Littwin, Dan Busbridge, Jason Ramapuram, Yizhe Zhang. Jiatao Gu, and Joshua M. Susskind. Stabilizing transformer training by preventing attention entropy collapse. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202, pages 40803. PMLR, 2023.
[99] Aston Zhang, Alvin Chan, Yi Tay, Jie Fu, Shuohang Wang, Shuai Zhang, Huajie Shao, Shuochao Yao, and Roy Ka-Wei Lee. On orthogonality constraints for transformers. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference Natural Language Processing (Volume 2: Short Papers), pages 375-382, 2021.
[100] Ying Zhang, Mohammad Pezeshki, Philémon Brakel, Saizheng Zhang, César Laurent, Yoshua Bengio, and Aaron Courville. Towards end-to-end speech recognition with deep convolutional neural networks. Interspeech 2016, 2016.
[101] Daquan Zhou, Bingyi Kang, Xiaojie Jin, Linjie Yang, Xiaochen Lian, Zihang Jiang, Qibin Hou, and Jiashi Feng. DeepViT: Towards deeper vision transformer. arXiv preprint arXiv: 103. 1886, 2021.
[102] Daquan Zhou, Yujun Shi, Bingyi Kang, Weihao Yu, Zihang Jiang, Yuan Li, Xiaojie Jin, Qibin Hou, and Jiashi Feng. Refiner: Refining self-attention for vision transformers. arXiv preprint arXiv:2106. 1no.:2206613314 2021.
[103] Haoyi Zhou, Siyang Xiao, Shanghang Zhang, Jieqi Peng, Shuai Zhang, and Jianxin Li. Jump self-attention: Capturing high-order statistics in transformers. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 17899-17910, 2022.
[104] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
[105] Yaqin Zhou, Shangqing Liu, Jingkai Siow, Xiaoning Du, and Yang Liu. Devign: Effective vulnerability identification by learning comprehensive program semantics via graph neural networks. In Advances in neural information processing systems (NeurIPS), volume 32, 2019.
[106] Chunya Zou, Andi Han, Lequan Lin, and Junbin Gao. A simple yet effective svd-gen for directed graphs. arXiv preprint arXiv:2205. X0i:32205.09335. 2022.
17

---

Appendix
18

---

A Reproducibility Statement
To ensure the reproducibility and completeness of this paper, include the Appendix with 12 sections. Appendix 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 inplementation details provided in Appendices K to Q
B Broader Impact
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 larger carbon footprint [69]. 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-bace models, which can have many positive impacts on society through services that utilize natural language processing, computer vision, and speech recognition. However, will also be important to improve GFSA by considering other dimensions of AI, such as robustness to adversarial examples, faimess, and explainability.
C Oversmoothing and Additional Visualizations
In Fig. 22 we show the visualizations of oversmoothing characteristics in DeiT. We also provide visualizations other domains. We show the filter response, cosine similarity, and singular value of BERT finetuned on STS-B dataset of GLUE tasks in Fig. ann Graphormer finetuned on ZINC
dataset in Fig. (
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. (80) for spectral visualization of the self-attention matrix. As shown in Fig. 2 (a), DeiT has a near-zero magnitude for the high frequencies, which is characteristic of low-frequency filter and is likely to result in oversmoothing when applied multiple times.
We follow the calculation method of Guo al. 28 for cosine similarity. As shown in Fig. (b),
the higher similarity as the layers of the model get deeper is related to the oversmoothing problem. To further analyze this issue, also consider the dimensionality collapse in Transformer-basee models. We plot the singular value distribution of the feature in the last block. As shown in Fig. 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 Fig. and Fig.
0.9
Nomallen Wagntude
0.8
BENT GPSA
Casira Serilarity
BERT GFSA
0.6
0.4
0.6-
Normallzes
0.3
BERT
0.0
-60
20
40
Frequancyy
Layer Indox
Singular Value Index
(a) Filter reponse
(b) Cosine Similarity
(c) Singular Value
Figure 5: Filter frequency response, cosine similarity, and singular values on STS-B for BERT and BERT+GFSA
19

---

1.0
Graphormer
Graphemmer
Graphormer
Nomalizzo Negne.uss
Graphormer GFSA
0.8
Graphermer GFSA
Graphormer GPSA
0.6
Cookoo
0.6
0.4
Nomateed
0.3
0.2
9.0
-20
-15
-10
15
0.0
0.0
Froquency
Layer
Singular
(a) Filter reponse
(b) Cosine Similarity
(c) Singular Value
Figure 6: Filter frequency response, cosine similarity, and singular values on ZINC for Graphormer and Graphormer+GFSA
D Analysis of Frequency Responses with Visualizations
We analyze the frequency responses, which represent the impact of learned coefficients, for all 12 layers of BERT with and without GFSA. From Fig. 7 our analysis reveals that GFSA learns various filter types between layers. In early layers, we observe tendency towards low-pass filtering, with prominent peaks at low frequencies. This aligns with the need for broader feature extraction in initial layers. The middle layers show a mix of low-pass and high-pass characteristics, with more complex frequency responses. This suggests GFSA is learning to balance between feature extraction and refinement. deep layers, there noticeable shift towards higher frequency responses, indicating move towards high-pass filtering. This shift supports our claim that GFSA can mitigate oversmoothing deeper layers. BERTBASE BASE shows consistently higher magnitude response at higher frequencies, especially in deeper layers, compared to vanilla BERT. In other word, vanilla self-atter self-attention works primarily as low-pass filter, while GFSA utilizes wider range of frequencies.
EEXT GPSA
0.8
0.6
0.6
0.6
0.6
0.4
0.4
2.9 AW
1AA
0.0
Noommliized Magnitude
-20
20
-20
20
-00
20
-00
-20
20
1.0
0.6
0.6
0.4
0.4
0.4
11
0.2
010
MM
40
-70
20
-00
-20
70
-00
-20
70
-00
-20
70
0.6
0.4
0.4
0.4
0.4
0.2
0.2
000
MW
-20
20
-20
20
-80
-20
20
-00
-20
20
Frequency
Figure 7: Visualization the frequency responses for all 12 layers of BERT trained on STS-B dataset.
The top-left figure corresponds to the first layer, and the bottom-right figure corresponds to the last layer.
20

---

E Frequency Analyses in the Singular Value Domain
Graph signal processing (GSP) 67
generalized concept of DSP in other words. DSP is special case of GSP where a line graph with nodes is used and therefore, the graph Fourier transform (GFT) of the line graph is identical to the discrete Fourier transform.
68
can be understood
In the definition of GFT, we assume that the graph shift operator (GSO) S is diagonalizable. Consid- ering the eigendecomposition of the GSO S VTAV with eigenvector V, we can write the graph filter output as follows:
K Σ k=0
K VT uu V== V== V== (11)
y wk
x
wk k=0
k=0
where I is 1-dimensional graph signal, A is a diagonal matrix with eigenvalues, and Wk E [-00, oo] is a coefficient.
However, one can use the singular value decomposition, when the GSO is not diagonalizable but symmetrically normalized, instead of the eigendecomposition [49. Both the singular value decomposition and the eigendecomposition project the original signal onto 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, and perform frequency domain-likk like analyses [T06] 49).
Since the self-attention matrix's row-wise sum is always 1, the following is the case: A = D-1A=
A, where n is the number of tokens. Maskey et al. [49] define the following symmetrically
1/2 normalized adjacency matrix (SNA): D--1/2 AD out
1/2
Since the degree of every node is n in the AD 1/2 ADD1/2 D-1/2 AD-1/2
self-attention matrix, the following is the case: D 1/2
A vm
v
A = A. Therefore, the self-attention matrix is a special case of SNAs.
F
Matrix Polynomial vs. Graph Fourier Transform
There are two paradigms of implementing graph filters: i) matrix polynomial, which does not require diagonalizability, and ii) graph Fourier transform, which uses the eigendecomposition for diagonaliz- able adjacency matrices or uses the Jordan decomposition or the singular value 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 there are not many matrix multiplications. Otherwise, the graph Fourier transform approach may be better since the matrix multiplication be simplified after the decomposition.
Among those two, we use the first matrix polynomial approach with only three non-zero coefficients {wo, W wx) 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.
G Proof of Theorem 3.1
Theorem 3.1 (Filter characteristics based coefficient values). Let À be a self-atlention matrix interpreted as gruph with connected components. Consider the polynomial graph filter defined by Ek Wi A where W2, W....., ...uK-) O and only Wa, W1, and WK are non-zero. If the coefficients we for ls 0, 1, K are positive and their sum 1, then the polynomial filter acts as low-pass filter, attenuating high-frequency components and promoting smoothness across the graph. Conversely, if wi = (-a)* for = 0, 1, K and a (0, 1) with sufficient large K, the polynomial filter exhibits high-pass filter behavior.
Note that without filtering, the singular value ratio is |o?1/|af1 = < lu(a))/g(a))
the case where 2, implies that after applying graph filter g. the lowest frequency component further dominates, indicating that the graph filter acts as low-pass filter. Conversely, in
21

---

the case where [ > 1 14 2 2, it implies that after applying the graph filter g. the lowest frequency component o; no longer dominates, indicating that the graph filter acts as a high-pass filter.
Proof. We prove the low-pass filter result. For the case where wp. Wi, and wi are positive and their sum 1, we show that
lg(0z)) = -wo + wi + wxl = 1
(12)
Hence, proving Theorem G is equivalent to show |g(0;)| < 1.
lg(a,)) = [u + w1d; + wx (o; + (K- 1)(o -,)) < lwo + wi + wxo, = 0; < 1 (13)
since 0; + (K 1) a; = 0₁ ((K - 1)0; - (K - 2)) < <,,((K - (K -2)) =
For the high-pass filter result, when W/ = (-a)* /(k 1) where k = 0, 1, K and a E (0, 1), then we show that when Wy 1, w1 a/2,
lim -o g(o))
lim wh + w Wio, + uk (0: + +K o:))
(14)
lim 9(1))
limx- wp + w1 + uk (1 + (K ()(1 1))
limn- 20: + [K-1]
(-a)*
(a; + (K - 1) - -o:))
(15)
lim -00 マ/2
(-a)K
[K+1]
(-0)* K
1 0 + (limx 000 [K+1]
(o; + (K 1) o:)))
(16)
1 2
>
(17)
since
(-a)
(-a)
lim K+
(a + (K - 1)(0, -o,)) lim
(K - 1) -0;)
(18)
(K + 1)
K
(K + 1)
K (K +
= lim
(-a)*
(K -K-)) (0, -oi)= =0
(19)
K
It shows that the graph filter with wy = (-a) /(k + 1) for k = 1,2, K emphasizes frequecyy components and acts as a high-pass filter.
This proof supports that the behavior of the polynomial filter as either a low-pass or high-pass pass filter directly depends on the sign and values of the coefficients, as specified in Theorem 3.1
H Proof of Theorem 4.1
Proof. The Frobeinus norm of the self-attention is directly related to how far the softmax probabilities are from being uniform. For any matrix M E 12mxx. we have
m + E (S, U..
softmax (ofttaaxMMilla (M)l
(20)
where S; is the i-th row of coftmax(M), Un is the uniform distribution over n elements, and drs (p. q) = E, (p://q - 1)2 is the divdiveree between p and q 14. The Frobenius norm is maximized when the whole mass of the probabilities is on one element, which is a case for (S,, U,) = n 1 and ||softma((M]]l = vm. Therefore, we can calculate the upper bound of Frobenius norm for A as follows:
| < Vn.
(21)
Note that A E Raxx is a stoht-stochastic matrix normalized with row-wise softmax: i) all the elements of A lie within [0, 1]. and ii) the row-sum in A is equal to 1. Since the self-attention matrix
22

---

is a right-stochastie matrix, the power of the self-attention is also right-stochaste matrix. Therefore, Eq. (2T is also hold for A as follows:
| 1
||
=
A
=
|| S Vn.
(22)
V
Now, considering the error term Æ as given by Theorem and applying the triangle inequality for matrix norms:
EK || (À (K 1)(4- 1184-1111 -
(23)
S |4 || |||| (K (K- -1)(1122 |A(pp)
(24)
5 n + vn + (K 11)(v + -vn) =2
(25)
I Implementation of GFSA
The pseudo code our GFSA is shown in Algorithm [ as hyperparameters optionally.
For implementation, wo and wi can be set
Algorithm 1 PyTorch-style pseudocode for GFSA
w_0 torch.zeros (h)
w_1 = torch (h)
__K torch.zeroa (h)
I torch.eyes (n) [None, None, ...]
def GFSA (att, K)
att: original self-attention
att_K: high order term
att_K att (K-1) (torch.mm(ttt,att) attt)
gf gt_att: CFSA attention
gfaatt [Non,, :, None, None]
w_1 [None, None, None] * att
w_K [None, :, None, None] att_K
return gf_att
Comparison with Actual and Approximated High-order Terms
To compare the impact of the actual Ā and the approximated ÅK in terms of accuracy, experimented with BERT on GLUB and the results are summarized in Table 9 BERTBASE+A* denotes using the exactly calculated AK instead of the approximated AK
Table 9: Comparison of performance using the exactly calculated A vs. the approximated AK for GLUE tasks
Datasets
#Params CoLA SST-2 MRPC QQP STS-B B MNLI-m/mm QNLI RTE Avg
BERT 11
110M 56,79 93.81 88.70
88.32
88.16
84.96/84.15
91.63 66.06 82.51 91.95 68.95 83.58
GFSA (approximated A
110M
59.56
94.15
90.60
88.46
88.33
85.12/8..06
GFSA (actual A
110M
59.85 94.27
89,80
88.43 88.32 84.95/84.89
91.76 68.23 83.39
23

---

K Natural Language Understanding
K.1 Detailed Experimental Settings
We integrate GFSA into 3 pre-trained large language models: BERT, ALBERT, and RoBERTa. We evaluate them on the GLUE benchmark, which includes 3 categories of natural language understand- ing tasks: i) single-sentence tasks CoLA and SST-2; ii) similarity and paraphrasing tasks MRPC, QQP, and STS-B; B; iii) natural language inference tasks MNLI, QNLI, and RTE. For MNLI task, we experiment on both the matched (MNLI-m) and mismatched (MNLI-mm) versions. Following Devlin et al. [16. we report Matthews correlation for CoLA, FI 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 [28], one of the related methods that address oversmoothing, We finetune ContraNorm with the recommended hyperparameters in Guo et al. (28) We initialize with pre-trained language model and finetune with added GFSA for epochs.
Dataset. The benchmark datasets we used are listed below.
CoLA. The Corpus of Linguistic Acceptability (85) consists of English acceptability judg- ments drawn from books and journal articles. The target task is a binary classification task, and each sentence is determined be grammatically acceptable not.
SST-2. The Stanford Sentiment Treebank (73] is a dataset in which each sentence is sourced from movie reviews and accompanied by human annotations of their sentiment. The target task is to classify binary sentiments for a single sentence.
MRPC. The Microsoft Research Paraphrase Corpus 17 is 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 [11] dataset is 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.
STS-B. The Semantic Textual Similarity Benchmark [ is a collection of sentence pairs drawn from news headlines, video and image captions, and natural language inference data with human annotation. The target a regression task to predict a similarity score from to 5.
MNLL. The Multi-Genre Natural Language Inference Corpus 87 crowdsourced col- lection of sentence pairs with textual entailment annotations. Given a premise sentence and 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.
dataset is question-answeriig 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 determine whether the context sentence contains the answer to the question.
QNLI
The Stanford Question Answering 82
RTE. The Recognizing Textual Entailment (5) dataset comes from series of annual textual entailment challenges. The target task is a binary entailment classification task.
BERT. BERT [16] consists with 12 layers, 12 heads, 768 hidden size, 512 maximum sequence length, and MLP dimension of 3072.
ALBERT. ALBERT 440 consists of 12 layers, 12 heads, 768 hidden dimensions, 512 maximum sequence length, 128 embedding dimensions, and MLP dimension of 3072.
RoBERTa, RoBERTa consists of 12 layers, 12 heads, 768 hidden size, 514 maximum sequence length, and MLP dimension of 3072.
24

---

Training. For implementation, we adopt HuggingFace framework. We trained all models with epochs with 32 batch size. The linear learning rate decay used and initial learning rate is set to 2 x 10-5 We use AdamW [46] optimizer, and weight decay is set to 0. All models are trained on GPU and of NVIDIA RTX A5000 24GB.
K.2
Sensitivity to K
In this section, we explore the influence of the polynomial order, denoted as K, our GFSA, conducting experiments BERT finetuned with GLUE tasks. We search for values of K from 2 to 10, and the results are presented in Table I0 For each dataset, there is an optimal and the performance of models using GFSA is generally robust changes in K.
Table 10: Sensitivity results various K with BERT finetuned GLUE tasks
K
CoLA
SST2
MRPC
QQP
STSB
MNLI-m
MNLI-mm
QNLI
RTE
57.83
94.15
90.60
88.41
88.27
84.96
84.90
91.74
68.23
58,56
93.46
89.77
88.41
88.33
85.08
84.75
91.78
68.59
59.56
93.46
89.77
88.45
88.29
85.06
85.06
91.76
68.59
58.10
93.58
90.07
88.39
88.29
84.87
84.99
91.85
68.95
59,40
93.58
90.40
88.29
88.27
84.93
84.97
91.69
68.23
59.12
94.04
90.48
88.43
88.26
85.12
84.94
91.82
68.94
58.58
93.69
90.12
88.46
88.24
84.92
84.81
91.95
68.95
58.88
93.46
89.54
88.41
88.26
85.06
91.67
67.87
85.04
10
59.31
93.35
89.98
88.41
88.30
84.84
91.73
68.59
84.93
L
Causal Language Modeling
L.1
Detailed Experimental Settings
Dataset.
The benchmark datasets we used are listed below.
PTB. Penn Treebank 47 dataset is collection of text documents that have been extensively annotated with linguistic information, primarily syntactic and grammatical structures.
WikiTeex. WikiText (50) dataset 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 over 2 times larger and WikiText-103 is over 110 times larger.
GPT2. GPT2 61 is Transformer pretrained very large corpus of English data in 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, adopt HuggingFace Framework 4 For all experiments, GPT2 has 12 layers with 12 attention heads, 768 hidden size and 1024 maximum sequence length, resulting in total of 117 million parameters.
Training. We finetune GPT2 with batch size, x 10-5 learning rate and linear learning weight decay using adamW W (46) optimizer. We also apply dropout with probability 0.1. Following [93], we train models 15 epochs with PTB, 4 epochs with WikiText-103 and epochs with WikiText-2. use sensitivity metric, i.e., perplexity, which is commonly used metric to evaluate the performance of language models, particularly in language modeling and text generation tasks. perplexity measures how well language modeling can predict sequence of words in given text test dataset. All the experiments are conducted on GPU and of NVIDIA RTX 3090 24GB.
L.2 Sensitivity K
We conducted a sensitivity study on K of GPT-2 across all datasets, and the results are presented in Table II For PTB and WikiText-2, GFSA exhibits the best performance when K is high, typically
25

---

around or 9. However, for WikiText-103,, GFSA achieves the best perplexity when K is small, specifically when K 3
Table 11: Results comparison on GPT-2 finetuned with GFSA
Method
#Paarms
PTB
WikiText-2
WikiText-
GPT2 61
117M
19.513
20,966
13,939
GPT2 GFSA(K 2)
117M
19.459
20.929
15.920
GPT2 + GFSA(K 3)
117M
19.456
20.927
15,919
GPT2 GESA(K -4)
117M
19.453
20.927
15,919
GPT2 G = -5)
117M
19.452
20.925
15.920
GPT2 GESA(K
117M
19.451
20.925
15.920
= =
117M
19.450
20.925
15,921
GPT2 GFSA(K =8)
117M
19.450
20.924
15,921
GPT2 GFSA(K =9) 117M
19.450
20.923
15.921
M Image Classification
M.1 Detailed Experimental Settings
Our code is implemented based on the timm library [86]. the case of our training recipe, it the same as experimental setting of Wang et al. [0) that follows the training recipes of Touvron et al. [74] and Touvron
[75.. To apply our GFSA to existing base models such as DeiT, Cait, and Swin, we consider range of K between 2 and 5. For 12-layer DeiT, we follow the same hyperparameters from Wang et al. [80]. We set the dropout rate to and 0.2 for 12-layer and 24-layer DeiT, respectively. For CaiT, we apply our GFSA on only to the patch embedding layer. All other hyper-parameters are kept consistent with the original papers of DeiT [74.. CaiT [5] and, Swin 45). models are trained on NVIDIA RTX 3090 24GB.
M.2 FLOPs & Throughput
In Table 12
we report the number of FLOPs and throughput. With GFSA plugged in, the FLOP count is either the same
different. For DeiT-S with 24 layers, which shows a slight FLOP increase with GFSA plugged in. However, for the rest of the settings, models have the same number of Flops. For throughput, it tends to decrease because calculating the high-order term is an additional cost.
Table 12: Experimental evalutation of GFSA plugged into DeiT-S, CaiTsS, and Swin-S
Backbone Method
Input Size #1 Layers
#Params
#FL.OPs #Throughput Top-1 Acc
DeīT-S DeiT-S + GFSA
224
12
22.0M
4.57G
856.07
79.8
224
12
22.0M
4.57G
614.54
81.1 (t 1.3)
DeiT
DeîT-S DeïT-S + GFSA
224
24
43.3M
9,09G
423.68
80.5
224
24
43.3M
9.10G
314.75
81.5 (t 1.0)
CaiT-S CaiT-S GFSA
224
24
46.9M
9.34G
574.66
82.6
CaiT
224
24
47.0M
9.34G
406.96
82.8 (1 0.2)
Swin-S
224
24
49.6M
8.75G
912.38
82.9
Swin
Swin-S + GFSA
224
24
49.6M
8.75G
714.60
83.0 (1 0.1)
M.3 Sensitivity K
We also perform the sensitivity analysis for K. Tables 13 and 14 show the results of sensitivity analysis for DeïT-S and CaiT-S with GFSA plugged in. For 12-layer DeiT-S, GFSA performance of 81.12 is highest when K = 3. When the GFSA has K of 2, the performance is worse than the
26

---

original DeiT-S, but when the K is 3 or higher, the performance is better than the original DeiT-S, and most surprisingly, the performance better than the 24-layer DeïT-S.
CaiT-S shows the highest performance of 82.84 when K = 4. For CaïT-S, the accuracy is slightly lower than that of the original CaiT-S when K = 2, but starts exceed the accuracy of Cail-$ when K is or higher.
Table 13: Sensitivity to K for 12-layer DeïT-S +Tbble 14: Sensitivity K for 24-layer CaiT-S GFSA
GFSA
K
2
K
Top-1 Acc (%) 79.27 81.12 80.86 81.07
Top-1 Acc (%) 82.54 82.65 82.84
M.4 Full Experimental Results
In Table 15 we consider all three classes, CNN only, CNN + Transformer, and pure Transformer, to compare more different models than in Table 3 In particular, in the Transformer category, only test with lightweight models with similar number of parameters, such as VIT-S and DeïT- S. Compared to existing techniques, the improvements by GFSA already surpasses LayerScale (0.7%) [5], LateInsertion (0.6%) [75] and HAT 4 (1.38%).
Table 15: Compared with state-of- fe-thhe-rt models ImageNet- 1k dataset. The number in (f) indicates the performance improvement over the base model.
Category
Method
Input Size
#Layers
#Params
Top-1 Acc
ResNet- 152 29
224
152
230M
78.1
CNN
DenseNet-201
224
201
77M
77.6
CNN
CVT-21
88
224
21
32M
82.5
Transformer
Refiner 102
224
86M
81.2
ViT-S/16 [19
224
49M
78.1
ViT-B/16 19
224
86M
79.8
DeïT-S 74]
224
12
22M
79.8
DeiT-S LayerScale
75
224
12
22M
80.5
DeiT-S LateInsertion
75
224
22M
80.5
DeiT-S ClassAttention
224
22M
80.6
DeiT-S AttnScale 80
224
22M
80.7
DeïT-S + FeatScale
80
224
12
22M
80,9
DeiT-S HAT 4
224
12
22M
80.9
Transformer
DeiT-S Diverse
10
224
22M
80.6
DeiT-S ContraNorm
28
224
22M
Swin-S 45
224
12
50M
82,9
T2T-ViT-24 [96]
224
64M
DeepViT-24B [101
224
24
36M
80.1
DeïT-S [44
224
24
43M
80.5
CaiT-S 75
224
24
47M
82.6
DeiT-S DiversePatch
224
44M
82.2
DeiT-S + LayerScale 75
224
24
44M
82,4
DeiT-S + AttnScale 80
224
24
44M
81.1
DeiT-S FeatScale 80
224
24
44M
81.3
DeiT-S ContraNorm
28
224
43M
80.7
DeiT-S GFSA
224
12
22M
81.1 (1 1.3)
DeiT-S GFSA
224
43M
81.5 (1 1.0)
GESA
CaiT-S GFSA
224
24
47M
82.8 (1 0.2)
Swin- + GFSA
224
12
50M
83.0 (1 0.1)
27

---

M.5 Additional Comparison with SOTA Models
Our main experiment aims determine whether introducing the GFSA layer would help improve performance in a base model, such as DeiT. We also compare our method with the recent models: We use 12-layer setup
SpectFormer [58]. SVT [57], NeuTRENO [2] FNet 422 and GFNet 64
to ensure fair comparison in Table T6
reduce the number of parameters, but there is a performance penalty. However, the performance improvement of DeiT-S+GFSA is relatively greater than DeïT-S compared to other models. SpectFormer [58] and SVT [57] have advantages calculation amount and model complexity, and performance is improved over DeïT-S, but Top-1 and Top-5 accuracies are lower also improves as much GFSA compared
GENet 66
than those using GFSA. Additionally, NeuTRENO [22 to DeiT-S, but GFSA still has higher Top-1 accuracy.
Table 16: Compared with Mate-of-the-an models on ImageNet-1k
Method
Input Size
#Layers
#Params
Top-1 Ace
Top-5 Ace
DeiT-S
12
22M
79.8
95.0
Fnet-XS 42
224
12
20M
71.2
GFNet-XS 64
224
12
16M
78.6
94.2
SpectFormer-XS
58
224
12
20M
80.2
94.7
SVT-XS 57
224
12
20M
79.9
94.5
DeiT-S + NeuTRENO
52
224
12
20M
80.7
95.4
DeïT-S + GFSA
224
12
22M
81.1
95.4
M.6 Additional Experiments with Guo et al. [28]'s setting
To make fair comparison with ContraNorm 28
one of the related studies that mitigates over- smoothing, we run additional experiments to match their experimental setup.
Setting. We follow the training recipe used by Guo et al. (28). which a slightly modified version of Touvron et al. [74)'s recipe. Guo et al. (28) use AdamW optimizer with cosine learning rate decay. We select the DeiT-T and DeiT-S for ImageNet-Ik. "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.
Results. In Table 17 DeiT-T and DeiT-S with GFSA outperform vanilla DeiT-T and DeiT-S in all layer settings. GFSA improves the performance of DeiT-T with 12 layers by 1.52%. The largest gain is 4.88% improvement the effect of ContraNorm. For DeiT-S with 16 layers, surprisingly, GFSA is able to increase the performance by 80.83%, meaning that GFSA brings benefits with 3.23% improvement.
16-layer DeiT-T. This shows that the effect GFSA is larger than
Table 17: Experiment results on Image
Method
#Layers=116 #layers=12
#Layers=24
DeiT-T
76.52
75.34
76.76
DeiT-T+ + ContraNorm
77.03
78.72
78.12
DeiT-T+ GFSA
77.68
79.02
78.64
DeiT-S
77.32
78.25
77.69
DeïT-S ContraNorm
77.80
79.04
78.67
DeïT-S GFSA
79.86
80.83
79.15
Sensitivity to K. In Table 18 we experiment with a sensitivity analysis for K. For DeiT-T, the performance GFSA generally improves when is or 5. On the other hand, GFSA performs better at lower K for settings that are layers 16 and 24 for DeiT-S.
28

---

Table 18: Varying K for DeïT-T and DeiT-S
Method
K
#Layers=12
#Layers=16
#Layers=24
+eiT-T GFSA
76.92
78.14
78,40
+ GFSA
77.41
77.76
78.09
D GFSA
GFSA
77.01
79.02
78.64
DeïT-T + GFSA
77.68
78.14
78.64
DeiT-S + GFSA
79.84
80.83
79.15
DeiT-S + GFSA
79.85
79.39
79.07
DeiT-S + GFSA
79.86
79.44
79.10
N Automatic Speech Recognition
N.1 Detailed Experimental Settings
55 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 65
Dataset. We conduct experiments on the LibriSpeech dataset
Evaluation Metric. Word error rate (WER (%)) derived from the Levenshtein distance and compares reference to hypothesized word-level transcription. It is calculated by summing the number of word insertions, deletions, substitutions and dividing by the total number of words reference transcription.
Vanilla Transformer. We vanilla Transformer to apply GFSA. For implementation, we use a SpeechBrain [65] framework. The vanilla Transformer consists of i) 1D convolution to perform striding, ii) Transformer encoder with 12 layers, 4 heads, embedding dimension of 512, MLP dimension of 2048, and post-LayerNove iii) decoder with 6 layers, 4 heads, embedding dimension of 512, MLP dimension of 2048, joint beamsearch, and iv) external Transformer language model with 12 layers, 12 heads, embedding dimension of 768, and MLP dimension of 3072.
Branchformer. We use one of the SOTA models, Branchformer [59 to plug-in our GFSA. Branch- former 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 1D convolution perform striding, ii) Branchformer encoder with 18 layers, 8 heads, embedding dimension of 512, and MLP dimension of 3072, iii) decoder with 6 layers, 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 MIP dimension of 3072.
Training. We follow a training recipe from SpeechBrain 65 The standard LibriSpeech validation sets (dev-clean and dev-other) are used 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 [56]. SpecAugment applies time and frequency masking well time warping the input spectrum. For Branchformer, AdamW W [46] optimizer with 0.9 and 0.98 coefficients for computing running averages gradient and its square. The learning rate and weight decay in all models are 0.0008 and 0.01, respectively. We use connectionist temporal classification (CTC) loss [26] [00]. We also apply dropout with probability 0.1 and label smoothing with weight 0.1 mitigate overfitting. We fix the random seed as 74443 on all experiments. All models are trained on I GPU and of NVIDIA RTX A6000 48GB.
http://www.openll.. orgg/12
29

---

In Table 19 we describe main hyperparameters used in the automatic speech recognition task. For Gransformer+GFSA and Branchforme++GFAA. we also report the best K hyperparameter.
Hyperparameters.
Table 19: Main hyperparameters used in ASR
Model
Experimental Setting
Encoder: Transformer (12 layers)
Decoder: Transformer layers) (CTC/TTT joint) beamscarch TransformerL.M
Augmeniation: SpecAugment
Pretraining:
Dropout: 0.1
Batchnorm:
Transformer
Number of epochs: 100
Learning rate: 0,0008
Optimizer: Adam
Loss: CTC KT div (Tah Smoothing loss)
CTC weight: 0.3
Transformer layer))
Decoder: Transfonner layens) (CTCATT joint) beamseurch TransformerL.M
Augmentation: SpecAugment
Features: 40 fbanks
Pretraining: DO
Dropout:
Batchnorm:
Transfomer+GGFA
Number epochs:
Batch size: 32
I Learning rate: 0.0008
LR scbeduler. Noam
Optimizer: Adam
Los: CTC
Smoothing loss)
CTC weight: 0.3
Encoder: Branchformer
Transfonner layers) (CTC/ATT joint) TransfommrtL.N
Augmentation: SpecAuggent
Features:
Pretraining:
Dropout: 0.I
Batchnorm:
Branchfoemer
Number of epochs: 120
I Lermnng rate: 0.0008
LR scheduler: Noam
Optimizer: AdamW with coefficients 0,9 and 0.98
Loss: CTC KLdiv (Label Smoothing loss)
weight:
Encoder: Branchformer
Decoder: Transfomner layers) (CTC/TTT joint) beamseurch Transfomeerl.N M.
Augmentation: SpecAugment
Features: fbanks
Pretraining: Do
Drupout:
Batchnom:
BranchformmrrGGFA
Number epochs:
Batch size:
Learning rate: 0.0008
LR scbeduler: Noam
Optimizer: AdamW with cuefficients 0.9 and 0.98
Lass: CTC KLdiv Smoothing loss)
CTC weight: 0.3
K:
30

---

N.2 Training Curve
We compare the training and validation curves for LibriSpeech 100h in Fig. g The training loss curve of GFSA is lower than the pure Transformer. GFSA stabilizes the loss curve of pure Transformer slightly earlier.
30
20
Transformer
Transfomer++GFSt
25
Transformer Transformer GFSA
Train Loss
15
20
15
10
10
0
25
50
100
0
25
50
75
100
Epoch
Epoch
(a) Training loss curve
(b) Validation loss curve
Figure 8: Training curve on LibriSpeech 100h
Graph-level Tasks
O.1 Detailed Experimental Settings
Experimental settings for Graphormer. We describe benchmark datasets and Graphormer as the backbone model we used. ZINC 355 is the most popular real-world molecular dataset to predict graph property regression for constrained solubility, an important chemical property for designing generative GNNs for molecules. Uniform sampling is adopted for data splitting. We use ZINC- subset of small-scale dataset. PCQM4M-LSC 33 is 2D molecular graphs, which is one of the most practically relevant quantum chemical properties of molecule science. The task is to predict density functional theory (DFl)-calculated HOMO-LUMO energy gap of molecules given their graphs. PCQM4M-LSC is unprecedentedly large in scale comparing other labeled graph-level prediction datasets, which contain more than 3.8M graphs. We use PCQM4M and PCQM4Mv2 large-scale datasets.
Following Graphormer 94 we use Graphormer for PCQM4M and GraphormersLIM for ZINC. Graphormer consists of 12 encoder layers, 80 encoder embedding dimension, and 768 MI. dimension. employs 32 encoder heads and 24 hidden dimension for each head. Graphormer consists of 12 encoder layers, 80 encoder embedding dimension, and 80 MLP dimension. It employs 8 encoder heads and 10 hidden dimension for each head. We use adamW (46) optimizer with 0.9 and 0.999
coefficients for running averages of gradient and its square, and use Mean Absolute Error (MAE) as loss function. We use polynomial learning rate decay, with initial learning rate set to 2 x 10 and end learning rate set to 1 x 10 9_ For ZINC, set batch size as 256, max epochs as 10k, and warm-up up stage step as 40k. For PCQM4M and PCQM4Mv2, we set batch size as 1024, max epochs as 300, and warm-up stage step as 60k. All models are trained I GPU and of NVIDIA RTX 3090 24GB. We conduct experiments with different seeds.
Experimental settings for GPS and Graph-Vit VIT. We use various benchmark datasets to experiment with our GFSA on GPS [x and Graph-Vil VIT (30: Peptide-fune and Peptide-struct from Long-Range
Graph Benchmark (LRGB) 21, MNIST, CIFAR1O. 10, and ZINC from Benchmarking GNNs [22] and Moltox21 and Molhiv from OGB (32) We fix all hyperparameters of GPS and Graph- VIT as recommended in their paper ensure fair comparison. To plug GFSA into GPS, replace the self-attention module of GPS with GFSA. For BiT, we apply GFSA instead of the Hadamard self-attention mechanism and compare it with this self-attention method. We conduct experiments GPS and Graph- VIT in their open code frameworks for a fair comparison:
GPS: http::///giaaabbcc/mmmaaaeee///s
Graph- Cttpph//TT...tgggggggtooooooooot Miee
31

---

0.2 Experimental Results with Standard Deviation
We conduct experiments following the experimental environments of Graphormer using different seeds. Due to space constraints, only the mean values are reported in Tables and In Tables 20 and
we report the results with mean and standard deviations.
Table 20: Experimental results and number of parameters on ZINC
Method
#Params
MAE
Graphormer
500K
0.1240
Graphormer GFSA
500K
0.1189:1000
Table 21: Experimental results and number of parameters on PCQM4M and PCQM4Mv2
PCQM4M
PCQM4Mv2
Method
#Params
Train
Validate
Train
Validate
Graphormer
48.3M
0.0535
0.1 2001 0.0250 0.0862
Graphormer + GFSA
48.3M
0.0312:tn.m
0. 0.0249.10.00 0.0860.:.00
P
Code Defect Detection
P.1 Detailed Experimental Settings
Dataset. We use Devign dataset provided by [105], which is a binary classification task to evaluate whether C language code is vulnerable software systems or not.
Implementation. We build our experiments on top of the open-sourced code - and recipes provided by Wang et al. (84.
RoBERTa. RoBERTA 44 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.
84
an encoder-decoder model based on BART + architecture, PLBART support understanding and generation tasks. All hyperparameters consistent with the training method in the source code of Wang et al. [84)
PLBART. PLBART 2
CodeBert. CodeBERT 23 is model trained 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. [84]
CodeT5. CodeT5 is encoder-decoder framework with the same architecture as T5 62 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. [84).
Training. The pre-trained models mentioned above are applied this downstream task. We add GFSA directly on top of self-attention. We finetune baselines and GFSA models for 10 epochs with batch size of 16. We use early stopping strategy with a patience of 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 GPU and of NVIDIA RTX A6000 48GB.
32

---

P.2 Case Study
In Listing I, we show one case for code snippets defects in QEM that T5 TS-base does not predict correctly, but that only as follow:
predicts. The commit message for this case is
Needed for changing cpu_has_wad _ook_ () argument type to CPUState, used c_cede ()
h oeceee() () is the hypercall that asks the hypervisor to shut down the CPU. Previously, this hypercall simply passed the CPUID, so the hypervisor did not know what state the CPU was in. This change allows the hypervisor to know whether the CPU is actually performing work. If the CPU is performing task, the hypervisor waits for the CPU to complete the task.
In this context, accurately predicting defects like the one above is very important, and applying GFSA CodeT5-base helps terms of performance improveent.
QQ
204,7 +204, QQ static target_ulong put_tce_ emu (sPAPRTCETable tcet, target parget_ulong ioba, static target_ulong h_put_ (CPUPPCState *env, sPAPREaviroument spapr
3+ static spapr
__put_tce (PoverPCCPU cpu,, sPAPREnvironment
target_ulong opcode, target_ulong
args)
target_ulong liobn = args [0]; target_ulong ioba args [1];
target_ulong tce args [2] VIOsPAPRDevice *dev
fhapr_vio_find_bee beegnddbbrrreeeeeeeeeeeeeeee (spapr (spaprrsss-iiooo... >ivio_bus, liobn);
VIOsPAPR_RTCE *rtce; if (!dev)
hcall_dprintf ("LIOBM 0r" TARGET_ 1x " does existin", liobn)
13
return H_PARAMETER;
14 }
ioba k= -(SPAPR_VIO_ FI__VIITEEEAAGESIIEE 1);
16
#ifdef DEBUG_ICE
17
on /s ioba 0x" TARGET_FMT, TCE 0x" TARGET_FMT.L "An", dev id, ioba, tce); #endif
fprintf (stderr,
if (ioba dev->rtce_ sandow_sizee {
20
hcall_dprintf (" of bounds IOBA 0x" TARGET_FMT_C "\n", ioba);
21
return H_PARAMETER;
22 }
rtce dev->rtce_tabe table (ioba >> SPAPR_ POOE_PAAE_SHIPPEE
24
tce;
25
return H_SUCCESS;
26
Listing 1: An example commit history for defects in Devign dataset
Code Clone Detection
Q.1
Detailed Experimental Settings
Dataset. Code clone detection aims to measure the similarity between two code snippets and predict whether they have the same functionality. We experiment with the Java data provided by Wang et al.
83
battpa://wws wwwpww.gemmm .qe.. org
https: /tt::///gitbbb http:///gthaauu.oomo////////////
33

---

Implementation. by Wang et al. 84
We build our experiments on top of the open open-sourced code 9 and recipes provided
Training. We finetune both CodeT5 and CodeTS+GFFA for one epoch with a batch size of 16. We also use early stopping with patience CodeT5 and CodeTS+GFSA encode source code and take the representation to calculate similarity of two code snippets. We employ FI score for evaluating this task. All models are trained on GPU and of NVIDIA RTX A6000 48GB.
Q.2 Experiment Result
Table 22 shows results comparing CodeTS and CodeT5 with GFSA. The result shows that by using our GFSA, CodeT5 models improve their performance. Code provides 0.61% % improvment over Code5T-smal
Table 22: Results on the code clone detection task
Method
Clone F1
CodeT5-small [84
94.36
CodeT5-smad GFSA
94.94 (1 0.61%)
CodeT5-base 84
94.31 94.92 (1 0.64%)
CodeT5-base GFSA
R Time Complexity and Empirical Runtime Analysis
Time Complexity. The time complexity of original self-attention (n?d).. But our GFSA has high order term. Therefore, the time complexity of GFSA has On + n²). If is smaller than d, the time complexity approaches O(n"d), which is the complexity of original self-attention.
Empirical Runtime Analysis. We report the training time of various methods with GFSA in Tables 23 to 28 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 Instead of computing higher-order polynomial terms, our GFSA approximates them, with only small increase in runtime, which is not very significant.
191.6 seconds on Librispeech 100h dataset, as increases of only second.
Table 23: Training time (seconds per epoch) on GLUE tasks. 8 denotes the abbreviation for second.
Avg denotes the average training time across all tasks.
Datasets
#Params CoLA SST-2 MRPC QQP
STS-B MNLI-m/mm QNLI
RTE Avg
BERT BASE
16
110M
17s
182s
17s
1483s
24s
2004s
580s
18s
541s
BERT BASE + GFSA
110M
19s
192s
19s
1571s
25s
2147s
621s
20s
577s
ALBERT BASE 40
11M
15s
188s
20s
1506s
25s
2072s
612s
19s
557s
ALBERT
GFSA
11M
16s
197s
21s
1604s
26s
2219s
659s
21s
595s
ROBERTaBASE
44
125M
17s
190s
18s
1492s
25s
2012s
593s
18s
546s
RoBERTaga Tagas
GFSA
125M
19s
200s
19s
1580s
26s
2151s
634s
20s
581s
Table 24: Training time (seconds per epoch) on causal language modeling tasks.
Method
#Params
PTB
WikiText-2
WikiText-103
Avg
GPT2 61
117M
$9.1s
195.7s 354.2s
9638.4s
3307 88
GPT2 + GESA
117M
160.38
17424.6s
5979.7s
http::///gtaab..cc//allleerrre/p
34

---

Table 25: Training time (seconds per epoch) on ImageNet-
Backbone
Method
#Layers
#Params
#FLOPs
#Throughput
Runtime
DeiT-S
12
22.0M
4.57G
856.07
551s
DeiT-S + GFSA
12
22.0M
4.57G
614.54
814s
DeiT
DeïT-S
24
43.3M
9.09G
423.68
1508s
DeïT-S + GFSA
24
43.3M
9.10G
314.75
1798s
CaïT-S
24
46.9M
9.34G
574.66
1530s
CaiT
CaiT-S + GFSA
24
47.0M
9.34G
406.96
1624s
Swin-S
24
49.6M
8.75G
912.38
1897s
Swin
Swin-S GFSA
24
49.6M
8.75G
714.60
1970s
Table 26: Training time (seconds per epoch) on graph-level tasks
Method
ZINC
PCQM4M
PCQM4Mv2
Graphormer 94
98
740s
817s
Graphormer GFSA
98
896s
9558
Table 27: Training time (seconds per epoch) on LibriSpeech datasets
Method
LibriSpeech 100h
LibriSpeech 960h
Transformer
190.5s
3049.3s
Transformer GFSA
191.6s
3398.4s
Branchformer [59]
248.5s
4990.1s
Branchformer GFSA
254.3s
4999.3s
Table 28: Training time (seconds per epoch) on the code defect prediction task
Runtime RoBERTa + GFSA
Method
RoBERTa 44
543.96s
537.79g
CodeBERT 23
555.28s
CodeBERT GFSA
561.43s
PLBART 2
467.80s
PLBART GFSA
470.19s
CodeT5-small [84
301.11s
CodeT5-small GFSA
309.04s
CodeT5-base g
362.28s
CodeTS-base + GFSA
373.22s
35

---

Inference Time Analysis
We report the inference time of various methods with GFSA in Tables
34
Table 29: Inference time on GLUE tasks. s denotes the abbreviation for second. Avg denotes the average training time across all tasks.
Datasets
#Params CoLA SST-2 MRPC QQP
STS-B MNLI-m/mm QNLI
RTE Avg
BERT BASE
16
110M
1.0s
1.4s
1.2s
48.7s
1.9s
15.5s
10.1s
1.2s 10.0s
BERT + GFSA
110M
1.1s
1.4s
1.2s
52.3s
2.0s
16.8s
11.0s
1.3s
11.0s
ALBERT BASE BASE
40
11M
1.18
1.68
1.48
58.4s
2.2s
18.4s
12.1s
1.3s 12.0s
ALBERTBASE GFSA
11M
1.2s
1.78
1.4s
62.1s
2.3s
19.7a
13.1s
1.4s
13.0s
ROBERTaBASE
44
125M
1.0s
1.4s
1.1s
47.0s
1.9s
15.0s
9.9s
1.2s 10.0s
RoBERTaBASE
GFSA
125M
1.1s
1.4s
1.28
50.4s
2.0s
16.3s
10.8s
1.2s 11.0s
Table 30: Inference time on causal language modeling tasks.
Method
#Params
PTB
WikiText-2
WikiText-103
Avg
GPT2 61
117M
3.2s
7.4s
7.4s
6.0s
GPT2 + GFSA
117M
5.58
12.9s
12.9s
10.4s
Table 31: Inference time on ImageNet-Ik
Backbone
Method
#1 Layers
Inference Time
DeiT-S
12
52s
DeiT-S + GFSA
12
53s
DeiT
DeiT-S
24
68s
DeiT-S + GFSA
24
69s
CaiT-S
24
105s
CaiT
CaiT-S + GFSA
24
107s
Swin-S Swin-S + GFSA
24
17s
Swin
24
17s
36

---

Table 32: Inference time graph-level tasks
Method
ZINC
PCQM4M
PCQM4Mv2
Graphormer 99
88
99s
31s
Graphormer GFSA
8s
117s
29s
Table 33: Inference time LibriSpeech datasets
Method
LibriSpeech 100h
LibriSpeech 960h
Transformer
328.1s
323.7s
Transformer GFSA
329.5s
343.3s
Branchformer 59
299.4s
328.7s
Branchformer GFSA
305.5s
354.1s
Table 34: Inference time the code defect prediction task
Method
Inference Time
RoBERTa 44
22.4s
RoBERTa GFSA
23.98
CodeBERT 23
23.8s
CodeBERT GFSA
24.1s
PLBART 2
37.7s
PLBART + GFSA
39.3s
CodeT5- small 84 TodeTTSsmall + GFSA
78.2s
82.5s
Code basse (84)
83.2s
CodeT5- + GFSA
88.5s
37

---

T Results of the Strategy for Efficiency
In Tables to 39 the results show that this strategy can reduce the increase in runtime and maintain performance compared to using GFSA for all layers.
Table 35: Comparison of performance using GFSA on all layers vs. GFSA even layers for
GLUE tasks
Datascts
#Params CoLA SST-2 MRPC QQP STS-B MNLI-m/mm QNLI RTE Avg
BERTBASE 16
110M
56.79
93.81 88.70
88.32 88.16 84.96/84.15
91.63 66.06 82.51 91.95 68.95 83.58
BERT BASE GFSA
110M
59.56
94.15
90.60
88.46
88.33
85.12/85.06
BERTBASE GFSA
110M
58.80
93.69 90.50
88.47 88.27 85.13/85.02
91.65 70.76 83.59
Table 36: Comparison training time (seconds per epoch) using GFSA on all layers vs. GFSAeven layers for GLUE tasks
Datasets
#Params CoLA
SST-2 MRPC
QQP
STS-B MNLI-m/mm QNLI RTE Avg
BERT BASE 16
110M
17s
182s
178
1483s
24s
2004s
580s
18s
541s
BERT GFSA
110M
19s
192s
19s
1571s
25s
2147s
621s
20s
577s
BERT GFSAeven
110M
17s
1858
18s
1506s
24s
2061s
595s
18s
553s
Table 37: Comparison of performance using GFSA on all layers vs. GFSA on even layers for
causal language modeling tasks
Method
#Params
PTB
WikiText-2
WikiTexx-1003
Avg
GPT2 66
117M
19.513
20.966
15,939 15,919
18,806
GPT2 GFSA
117M
19.450
20.923
18.764
GPT2 + GFSA
117M
19.453
20.926
15.923
18.767
Table 38: Comparison of training time (seconds per epoch) using GFSA on all layers vs. GFSAeven on even layers for causal language modeling tasks
Method
#Params
PTB
WikiText-2
WikiTeext-133
Avg
GPT2 61
117M
89.1s
195.7s
9638.4s 17424.6s
3307.8s
GPT2 + GFSA
117M
160.3s
354.2s
5979.7s
GPT2 + GFSAeven
117M
127.48
279.18
13761.4s
4722.6s
Table 39:
Comparison of using GFSA on all layers vs. GFSA even layers for ImageNet- 1k
Method
Input Size
#Layers
#Params
Top-1 Acc
Runtime
DeiT-S DeiT-S + GESA
12
43M
79.8
5518
224
12
43M
81.1
814s
DeiT-S + GFSAeven
224
12
43M
81.0
5958
38

---

U GESA in Linear Transformers
Table 40 shows the accuracy, runtime, and GPU usage results Long Range Arena benchmark using ListOps and Image datasets.
Table 40: Comparison of accuracy (%), runtime (s per 1,000 steps) and GPU usage (GB) on Long Range Arena benchmark
ListOps (2K)
Image (4K)
Method
Accuracy
Runtime
GPU usage
Accuracy
Runtime
GPU usage
Transformer 7
37.1
198.3
5.50
38.2
345.1
5.88
37.6
635.8
10.87
40.2
737.2
11.20
Linformer 88
37.3
63.4
1.73
37.8
158.5
3,45
YOSO-E 997
37.3
85.7
0.37
39.8
114.2
1.42
Efficient Attention 70
36.9
49.2
0.57
40.2
121.1
Efficient Autention + GPSA
37.9
53.8
0.67
40.4
135.8
1.33
39

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly stated our claims in the introduction, including the contributions of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Section 6
we stated the computational overhead as limitation of our method and provided strategies to address it.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
40

---

Answer: [Yes]
Justification: We have included proofs for Theorem 4.1 and Theorem 3.1 in Appendix H and Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Our reproducibility statements are reported in A
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
41

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
See the statement about reproducibility in Appendix A
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https /nips
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental environments, datasets, training methods are reported in Sec- 5.T to [.6]and in Appendix Koo to [.6]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We tried to follow the experimental setup for benchmarking each task. Among the tasks we considered, it is conventional to report results from four experiments in the graph-level tasks task, so we report the mean and standard deviation together in the Appendix (022
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
42

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our paper specifies the type of computer resource information (e.g. GPU) for the experiment. We also indicated the amount of calculation or execution time for the experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:: http:rppp....ppp../c//ccccccllaa
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification: We discuss the potential positive and negative social impacts our research in Appendix B
Guidelines:
43

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is no such risk in our paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: In paper, the authors original owners of code, data, and models used properly credited, and their licenses and terms use are explicitly mentioned.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
44

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code we provided is well documented in the README and is anonymized.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our research does not include crowdsourcing experiments and studies with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Because our research does not involve human subjects, not subject to IRB approval.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
45

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "c9nwciLArI", "reviewer": "Reviewer_Py4c", "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.", "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.\n2. 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": "The authors addressed the limitations, including effectiveness and efficiency.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Sufficient Experiments. The paper conducts experiments on natural language understanding, computer vision, automatic speech recognition, graph regression, and code classification. The authors try their best to show the generalization of the proposed method.\n2. Well Organized. The paper articulated the viewpoint in a clear and organized manner.\n3. Reproducibility. The paper shows the pseudo-code, which clearly presents the implementation of GFSA in the appendix. The paper shows detailed experiment settings in appendices I to O. The code is available with instructions. However, an error occurred when I tried to run it, which is reported in the following questions.", "weaknesses": "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.\n2. Misleading Figure. Fig 1 shows the performance of the proposed method. However, the inconsistent proportions exaggerate the model's effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer Py4c for the review and  feedback, highlighting our strengths in\n1. Extensive experimentation across diverse domains demonstrating the generalizability of GFSA.\n2. Clear and well-organized presentation of ideas.\n3. Strong emphasis on reproducibility with detailed implementation information and code availability.\n\nBelow, we would like to address each of your questions and concerns:\n\n**Response to W1: Sensitivity of $K$**\n\nWe understand your concern about the time required to find the optimal $K$. Our tasks across various domains include both fine-tuning and training from scratch. For fine-tuning tasks with relatively short training times, such as the GLUE benchmark, searching for $K$ values from 2 to 10 is not a significant hindrance (see Appendix I.2). However, for tasks like ImageNet that require training from scratch, we flexibly set a narrower search space of 2 to 5 for the 12-layer DeiT-S model.\n\n**Response to W2: Misleading figure**\n\nWe acknowledge that the different scales and metrics for each task could potentially lead to misinterpretation. We have redrawn the plot based on specific backbones, showing only the percentage of improvement. We hope that the updated Figure 1 in the pdf file of the general response addresses this concern and eliminates any potential for misleading information.\n\n**Response to Q1: Missing code**\n\nWe apologize for the inconvenience. We have uploaded the `run_gen.py` file, and the experiment should now run successfully. Please check the same link provided in the paper for the updated code repository.\n\n**Response to Q2. Sensitivity of $K$**\n\nRegarding the necessity of searching for the optimal $K$ for new datasets, our experiments suggest that while there is an optimal $K$ for each dataset, the performance of models using GFSA is generally robust to changes in $K$. However, for best results, we recommend conducting a search for the optimal $K$ when dealing with a new dataset.\nAs for the relation between $K$ and $E_k$ in Theorem 4.1, you are correct in noticing this connection. The theorem provides a theoretical foundation for understanding how $K$ affects the model's performance. While the model shows robustness to $K$ in practice, the optimal value can vary depending on the specific dataset and task.\n\nImportantly, we would like to draw your attention to Table 8 in Appendix J.2, which demonstrates the effectiveness of GFSA across different $K$ values. This table shows that for the three datasets, all tested $K$ values (from 2 to 9) result in better performance compared to the original GPT2 model. This provides evidence that GFSA consistently improves performance across a range of $K$ values. This robustness to $K$ is a strength of our method.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aLwzsJJtkJ", "reviewer": "Reviewer_XKs2", "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.\nTo reduce the computational overhead, the authors propose to use a first-order Taylor approximation to the higher-order power of the attention matrix.\nWith the slightly larger complexity, the proposed technique can improve the performance of Transformers in various fields, across computer vision, natural language processing, etc.", "questions": "1. Besides the runtime, can you also provide the GPU memory consumption comparisons between GFSAs and the base models?", "limitations": "No specific aware.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well written.\n2. The comprehensive empirical experiments well support the advantage of the proposed method and the statement of the work.", "weaknesses": "1. The notation in the equation on Line 99 is confusing (the \"exponential\" in the self-attention matrix).\n2. 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$. \nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer XKs2 for the review and positive feedback, highlighting our strengths in\n\n1. Well-written paper.\n2. Comprehensive experiments strongly support the advantage of GFSA.\n\nBelow, we would like to address each of your questions and concerns:\n\n**Response to W1: confusing notation**\n\nThank you for pointing out the notation in the equation on Line 99. We have updated the paper to clarify the exponential notation in the self-attention matrix, which should resolve any confusion.\n\n**Response to W2: Taylor approximation**\n\nWe appreciate your careful consideration of our method. We respectfully disagree with the view that our approach degenerates to only second-order terms and would like to provide a more detailed explanation of our Taylor approximation approach.\n\nThe Taylor approximation in our work is specifically used to estimate higher-order terms ($\\bar{\\boldsymbol{A}}^K$ for $K > 2$) efficiently. It is not intended to limit the model to second-order interactions but rather to capture the essence of higher-order terms without incurring computational costs. As detailed in Eqs. (6)-(8) of our paper, we use a first-order Taylor approximation at point $a = 1$, combined with a forward finite difference method to approximate the derivative. This results in the approximation: $\\bar{\\boldsymbol{A}}^K ≈ \\bar{\\boldsymbol{A}} + (K-1)(\\bar{\\boldsymbol{A}}^2 - \\bar{\\boldsymbol{A}})$. This formulation includes both $\\bar{\\boldsymbol{A}}$ and $\\bar{\\boldsymbol{A}}^2$ terms, but importantly, it scales with $K$, allowing it to capture aspects of higher-order interactions.\n\nIn Eq. (10), our GFSA filter is defined as $H_{GFSA} = w_0 \\boldsymbol{I} + w_1 \\bar{\\boldsymbol{A}} + w_K(\\bar{\\boldsymbol{A}} + (K-1)(\\bar{\\boldsymbol{A}}^2 - \\bar{\\boldsymbol{A}}))$. The learnable coefficients $w_0$, $w_1$, and $w_K$ provide the model with the flexibility to balance the contributions of different order terms. Notably, $w_K$ scales the approximated higher-order term, allowing the model to adjust its influence based on the task requirements. Tables 8, 10, and 11 show improved performance as $K$ increases. This improvement would not be observed if the model were limited to second-order interactions.\n\nThis approximation allows us to capture higher-order effects without the full computational burden of calculating $\\bar{\\boldsymbol{A}}^K$ directly for large $K$, which would be expensive for many practical applications. While our approach does use a Taylor approximation to estimate higher-order terms, it is not equivalent to a simple second-order polynomial. The approximation retains a dependency on $K$, allowing it to capture aspects of higher-order interactions in a computationally efficient manner.\n\n**Response to Q1: GPU Memory**\nThank you for your question regarding GPU memory consumption. We have measured GPU memory usage (GB) during training for image classification and natural language understanding tasks. The results are presented in the table below.\n\nThe increase in GPU memory consumption can be attributed to the calculation of $\\bar{\\boldsymbol{A}}^2$ in our GFSA method. However, it's crucial to consider this increase in the context of GFSA's overall impact on model performance and efficiency. GFSA adds only about 100 parameters to the model, yet yields improvements across various tasks.\n\nMoreover, our 12-layer DeiT+GFSA outperforms 24-layer DeiT, which has significant implications for computational efficiency. As detailed in Table 20, 24-layer DeiT requires approximately 50 minutes per epoch, while 12-layer DeiT+GFSA needs only about 30 minutes per epoch yet achieves higher accuracy. This demonstrates that GFSA can achieve better results with lower overall memory requirements and reduced runtime compared to simply increasing the number of layers in the base model.\n\nConsidering these factors - the performance improvements, the minimal increase in parameters, and the potential for reduced runtime - we believe the additional GPU memory usage is acceptable. \n\n| Model  | 12-Layer | 24 Layer |\n| --- | --- | --- |\n| DeiT-S | 1.6 | 3.2 |\n| DeiT-S+GFSA | 2.1 | 4.0 |\n\n| Model | CoLA | SST2 |  MRPC |  QQP |  STSB |  MNLI | QNLI | RTE | Avg |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| BERT$_{BASE}$ | 2.31 |  2.73 |  3.73 |  4.42 |  4.33 |  4.45 |  4.45 | 4.45 | 3.86 |\n| BERT$_{BASE}$   + GFSA |  2.39 |  2.90 |  4.13 | 5.00  |  4.86 |  4.98 | 5.00 |  4.98 | 4.28 |\n| ALBERT$_{BASE}$ |  1.69 |  2.89 |  4.43 |  4.56 |  4.55 |  4.57 |  4.57 |  4.57 |  3.98 |\n| ALBERT$_{BASE}$ + GFSA|  1.77 |  3.15 |  5.01 |  5.14 |  5.12 |  5.14 |  5.14 |  5.14 |  4.45 |\n| RoBERTa$_{BASE}$ |  2.48 |  2.96 |  3.91 |  4.60 |  4.49 |  4.59 |  4.60 |  4.62 |  4.03 |\n| RoBERTa$_{BASE}$ + GFSA | 2.55 | 3.13 | 4.30 | 5.19 | 5.05 |  5.17 |  5.20 |  5.15 |  4.47 |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b6B1FPXvTV", "reviewer": "Reviewer_k2id", "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.", "questions": "- L205: for the self-attention with the skip connection, shouldn't $w_0$ be positive?\n- 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?\n- The paper only discusses the runtime overheads. Does GFSA introduce any potential memory overheads?", "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.", "rating": 4, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "- The core idea is easily grasped and demonstrates promising results across various transformer variants in different domains.\n- The authors evaluate GFSA on a wide range of tasks spanning natural language processing, computer vision, speech recognition, and graph regression, highlighting its versatility.", "weaknesses": "- 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).\n- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer k2id for the review and feedback, highlighting our strengths in\n1. Easily understandable core idea with promising results across diverse transformer variants.\n2. Versatile performance demonstrated across a wide range of tasks in multiple domains.\n\nBelow, we would like to address each of your questions and concerns:\n\n**Response to W1: varying depth**\n\nWe would like to highlight the comprehensive layer-wise analysis we have conducted.\n\nFig. 2 compares DeiT and DeiT+GFSA across all 24 layers. The cosine similarity plot (Fig. 2b) shows how GFSA mitigates oversmoothing as depth increases. DeiT shows increasing cosine similarity in deeper layers, indicating oversmoothing, while DeiT+GFSA maintains lower, more stable similarity across layers.\nSimilar results are observed for BERT on STS-B (Fig. 3) and Graphormer on ZINC (Fig. 4).\nThe singular value distributions (Fig. 2c, 3c, 4c) further support our findings.\n\nThis layer-wise analysis provides strong evidence of GFSA's effectiveness in addressing oversmoothing across the full depth of the studied models.\n\n**Response to W2: weak baseline**\n\nTo provide a rigorous assessment of GFSA's practical value, we have conducted additional experiments applying GFSA to SOTA models that use self-attention, GPS [1], and Graph-ViT [2] on LRGB [3] and Benchmarking GNNs [4]. For experimental results, we refer the reader to Table 1 and Table 2 in the PDF file of the general response.\n\nFor GPS, we replace its self-attention module with our GFSA while maintaining its best configuration and other hyperparameters. For Graph-ViT, we apply GFSA to the Hadamard self-attention method. These experiments follow the settings used in both papers.\n\nOur new results show consistent improvements across various datasets. These additional experiments show the versatility and effectiveness of GFSA beyond our initial studies.\n\n> [1] Rampášek et al. \"Recipe for a general, powerful, scalable graph transformer.\" NeurIPS 2022\n>\n> [2] He et al. \"A generalization of vit/mlp-mixer to graphs.\" ICML 2023\n>\n> [3] Dwivedi et al. \"Long range graph benchmark.\" Advances in NeurIPS 2022\n>\n> [4] Dwivedi et al. \"Benchmarking graph neural networks.\" JMLR\n\n**Response to W3: comparison with other recent and relevant methods** \n\nWe would like to highlight the analysis already present in our paper.\n\nAs shown in Appendix Table 13, we have included comparisons with several SOTA methods. Notably, we have compared GFSA with NeuTRENO, a recent method designed to address oversmoothing. Our GFSA outperforms NeuTRENO while maintaining a similar parameter count to the original DeiT-S.\n\nTable 13 not only includes models addressing oversmoothing but also other recent advanced models such as SpectFormer and SVT. This provides a broader context for GFSA's performance across different types of SOTA approaches.\n\nRegarding [64], we were unable to include a direct comparison since the code is not public. However, we believe our current comparisons, which include both oversmoothing-specific methods and other recent innovations, provide a comprehensive evaluation of GFSA's effectiveness.\n  \n\n**Response to W4: learned filter analysis**\n\nWe have addressed your suggestion by visualizing the frequency responses, which directly represent the impact of learned coefficients, for all 12 layers of BERT with and without GFSA. These visualizations are now included in a PDF file of the general response.\n\nOur analysis reveals:\n1. 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.\n2. BERT+GFSA consistently shows higher magnitude responses at higher frequencies compared to vanilla BERT, especially in deeper layers.\n3. While vanilla self-attention functions primarily as a low-pass filter, GFSA utilizes a wider range of frequencies.\n\nThese findings provide evidence for GFSA's effectiveness in mitigating oversmoothing and preserving high-frequency information. We thank the reviewer for this valuable suggestion, which has enhanced the depth and rigor of our paper's contribution.\n\n\n**Response to Q1: skip-connection**\n\nWe appreciate your careful observation regarding self-attention with skip connections. In standard Transformers, the residual term is positive. However, in our GFSA, $w_0$ serves a slightly different purpose. $w_0$ adjusts the weight of the identity matrix within each attention head, controlling how much of the original input should be preserved. Unlike traditional skip connections, $w_0$ can be learned, set to a fixed value, or even set to 0, depending on task requirements. When learned, $w_0$ provides flexibility to adapt the residual-like connection based on the task. When fixed to a positive value, it can more closely mimic traditional residual connections.\n\n**Response to Q2: fine-tuning PLM with different architecture**\n\nThank you for your question about GFSA implementation in our NLP experiments.\n\nWe replaced standard self-attention with GFSA during the fine-tuning phase of pre-trained models. This approach aligns with recent practices in the field, as seen in works that modify pre-trained model structures during fine-tuning [1,2,3].\n\nOur approach offers flexibility in coefficient initialization and learning. One option is to initialize $w_0$ and $w_K$ to 0 (see Appendix A), allowing them to be learned during fine-tuning. This strategy provides a smooth transition from standard self-attention to GFSA, enabling task-specific adaptation.\n\n> [1] Fine-tune BERT with Sparse Self-Attention Mechanism, EMNLP-IJCNLP 2019\n> \n> [2] Fast transformers with clustered attention, NeurIPS 2020\n> \n> [3] Enhancing Self-Attention with Knowledge-Assisted Attention Maps, ACL 2022\n\n**Response to Q3: memory overheads**\n\nPlease refer to our **Response to Q1** of Reviewer XKs2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BnHhKrAJht", "reviewer": "Reviewer_bzWT", "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.", "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": "None", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "1. The idea is clear and well understood, the author leverages the idea in GNN fields to the transformer models.\n2. The high-pass and low-pass filter is analyzed and the author used an approximation to approximate the polynomial filter.\n3. The experiments covers many different applications of transformers.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer bzWT for the review and feedback, highlighting our strengths in\n1. Clear idea applying GNN concepts to transformer models.\n2. Analytical approach to high-pass and low-pass filters with polynomial approximation.\n3. Extensive experiments across various transformer applications.\n\nBelow, we would like to address each of your questions and concerns:\n\n**Response to W1: comparison with GNN and Graph Transformer**\n\nWhile inspired by graph signal processing (GSP), we believe our contribution has significant novelty:\n\nGFSA uniquely interprets dynamic self-attention as a directed graph shift operator, unlike conventional GNNs and graph Transformers that typically deal with static undirected adjacency matrices. This difference sets GFSA apart from works like Polyformer [1] and Specformer [2].\n\nPolyformer combines a Graph Transformer with a graph filter and defines the graph filter using the adjacency matrix as a graph shift operator. It uses Transformers to learn the coefficients of polynomial expansion. Specformer uses the eigenvalues of the adjacency matrix as input to the Transformer to design a spectral GNN, but it doesn't alter the fundamental structure of Transformers, using them as encoder-decoders.\n\nOur approach is based on the following equation:\n\n$$\\mathbf{y} = \\mathbf{H}\\mathbf{x} =  \\begin{cases}{\\color{blue}{\\sum_{k=0}^{K} w_k \\mathbf{\\bar{A}}^k\\mathbf{x}}} = {\\color{red}{\\mathbf{V}^\\intercal \\big(\\sum_{k=0}^{K} w_k\\mathbf{\\Lambda}^k \\big) \\mathbf{V}\\mathbf{x}}} & \\text{if} \\ \\mathbf{\\bar{A}} \\text{ is undirected} \\\\\\\\ \\color{blue}{\\sum_{k=0}^{K} w_k \\mathbf{\\bar{A}}^k\\mathbf{x}} & \\text{if} \\ \\mathbf{\\bar{A}} \\text{ is directed} \\end{cases}$$\n\nWhen implementing graph filters, the red spectral decomposition requires diagonalization of the graph shift operator matrix. In symmetric cases, such as undirected graphs, spectral decomposition is always guaranteed, allowing consistent application of the red method. However, in directed graphs, spectral decomposition is not guaranteed and thus cannot always be applied.\n\nIn contrast, the blue matrix-polynomial method does not require diagonalization. This enables consistent application of graph signal processing to both directed and undirected matrices. This approach is essential for self-attention matrices where diagonalization is impossible, making GFSA more broadly applicable and theoretically sound.\n\n Furthermore, we propose a method to approximate higher-order polynomial terms. This approximation is key to achieving performance gains without computational costs.\n\nIn conclusion, GFSA integrates GSP with Transformers, addressing non-diagonalizable self-attention matrices and offering a scalable model applicable across various domains.\n\n> [1] Bo et al., \"Specformer: Spectral Graph Neural Networks Meet Transformers.\" ICLR 2023\n>\n> [2] Jiahong et al., “PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformer”, KDD 2024\n\n\n**Response to Q1: Theorem 3.1**\nThanks for your question. We have corrected the typo $g(\\sigma_i) \\rightarrow \\sigma_i$ on line 696. \n\nWe agree that if the ratio $w_k/w_1$ is large, it may not always be a low-pass filter. Theorem 3.1 proves that under specific coefficient conditions, the graph filter becomes either low-pass or high-pass. For example, if the coefficients are all positive and their sum is 1, the graph filter becomes a low-pass filter. Alternatively, if the coefficients are $w_k=(-\\alpha)^k$ with sufficient large $K$, the graph filter becomes a high-pass filter.\n\nAdditionally, we have revised Theorem 3.1 to address your concern:\n\n**(Theorem 3.1 Filter characteristics based on coefficient values)**. Let $\\bar{\\mathbf{A}}$ be a self-attention matrix interpreted as a graph with connected components. Consider the polynomial graph filter defined by $\\sum_{k=0}^K w_k \\bar{\\mathbf{A}}^k$, where $w_2, w_3, \\ldots, w_{K-1} = 0$ and only $w_0$, $w_1$, and $w_K$ are non-zero. If the coefficients $w_k$ for $k=0,1,K$ are positive and their sum is 1, then the polynomial filter acts as a low-pass filter, attenuating high-frequency components and promoting smoothness across the graph. Conversely, if $w_k=(-\\alpha)^k$ for $k=0,1,K$ and $\\alpha \\in (0,1)$, the polynomial filter exhibits high-pass filter behavior.\n\n**Proof.** For the case of low-pass filter, the graph filter acts as low-pass filter if $|g(\\sigma_i)/g(\\sigma_1)|<1$ for $\\forall i \\geq 2$ where $\\sigma_i$ indicates the $i$-th singular value of $\\bar{\\mathbf{A}}$ . From the assumption that the coefficients $w_k$ for $k=0,1,K$ are positive and their sum is 1, we derive that\n\n$\\left|g(\\sigma_1)\\right| = \\left|w_0 + w_1 + w_K\\right| = 1$, \n\nand\n\n$\\left| g(\\sigma_i)\\right| =\\left| w_0 + w_1\\sigma_i  + w_K\\sigma_i^k \\right| < \\left| w_0 + w_1\\sigma_i  + w_K\\sigma_i \\right| < \\left| w_0 + w_1 + w_K \\right| = 1$.\n\nTherefore, as $|g(\\sigma_i)/g(\\sigma_1)|<1$, the graph filter acts as low-pass filter.\n\nFor the case of high-pass filter, the graph filter acts as a high-pass filter if $|g(\\sigma_i)/g(\\sigma_1)| > 1$ for $\\forall i \\geq 2$. From the assumption that the coefficients $w_k=(-\\alpha)^k$ for $k=0,1,K$ and $\\alpha \\in (0,1)$ with sufficient large $K$, we derive that\n\n$\\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} -\\alpha + \\alpha^2 \\sigma_i^2 + (-\\alpha)^K \\sigma_i^K}{\\lim_{K \\rightarrow \\infty} -\\alpha + \\alpha^2 + (-\\alpha)^K}\\right| = \\left|  \\frac{ -\\alpha + \\alpha^2 \\sigma_i^2}{ -\\alpha + \\alpha^2 }\\right|   = \\left| \\frac{ -1 + \\alpha\\sigma_i^2}{ -1 + \\alpha }\\right|  > 1$\n\nTherefore, as $|g(\\sigma_i)/g(\\sigma_1)| >1$ with sufficient large $K$, the graph filter acts as high-pass filter.\n\nThis proof supports that the behavior filter depends directly on the sign and values of the coefficients.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers,

We sincerely appreciate your feedback and constructive comments on our paper. We are grateful for the recognition of several key strengths in our work:
1. Extensive experiments across diverse domains demonstrating the broad applicability of GFSA
2. Clear, well-organized presentation of ideas
3. Emphasis on reproducibility with detailed code and settings
4. Versatility of GFSA across different transformer variants and fields
5. Innovative application of graph filter concepts to transformers
6. Easily graspable core idea facilitating adoption
7. Comprehensive empirical support for the advantages of GFSA

**Important: We have uploaded a one-page PDF file with additional materials addressing your concerns.**


This pdf includes:
- Updated Fig. 1: The original Fig.1 was potentially misleading because different metrics for different tasks were shown in the same figure, so we changed the radar chart to show the improvement ratio compared to the backbone. This change is related to W2 of reviewer Py4c.
- New Tables 1 and 2: To address the weakness (W2) of reviewer k2id that only two datasets were considered for the tasks in the graph domain, we include additional experimental results applying GFSA to GraphGPS and Graph-ViT. We provide more rigorous evaluations of GFSA by adding 7 datasets: Peptide-Func, Peptide-Struct, ZINC, MNIST, CIFAR10, Molhiv, and MolTOX21.
- New Fig. 2:  The analysis of filter responses based on the learned coefficients of GFSA across the different layers of BERT is shown. As the layer deepens, there is a noticeable shift towards higher frequency responses, indicating a move towards high-pass filtering. Therefore, Fig. 2 provides the evidence for GFSA's effectiveness in preserving high-frequency information. This figure is related to W4 of reviewer k2id.

We encourage you to review this material as it provides visualizations and additional results that may enhance your understanding of our responses to your questions and concerns.

Meta-review: 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.
Decision: Accept (poster)