Graph Convolutions Enrich the Self-Attention in Transformers!

We sincerely thank Reviewer bzWT for the review and feedback, highlighting our strengths in

1. Clear idea applying GNN concepts to transformer models.
2. Analytical approach to high-pass and low-pass filters with polynomial approximation.
3. Extensive experiments across various transformer applications.

Below, we would like to address each of your questions and concerns:

Response to W1: comparison with GNN and Graph Transformer

While inspired by graph signal processing (GSP), we believe our contribution has significant novelty:

GFSA 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].

Polyformer 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.

Our approach is based on the following equation:

$\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}$

When 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.

In 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.

Furthermore, we propose a method to approximate higher-order polynomial terms. This approximation is key to achieving performance gains without computational costs.

In conclusion, GFSA integrates GSP with Transformers, addressing non-diagonalizable self-attention matrices and offering a scalable model applicable across various domains.

[1] Bo et al., "Specformer: Spectral Graph Neural Networks Meet Transformers." ICLR 2023

[2] Jiahong et al., “PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformer”, KDD 2024

Response to Q1: Theorem 3.1 Thanks for your question. We have corrected the typo $g(\sigma_i) \rightarrow \sigma_i$ on line 696.

We 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.

Additionally, we have revised Theorem 3.1 to address your concern:

(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.

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

$\left|g(\sigma_1)\right| = \left|w_0 + w_1 + w_K\right| = 1$,

and

$\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$.

Therefore, as $|g(\sigma_i)/g(\sigma_1)|<1$, the graph filter acts as low-pass filter.

For 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

$\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$

Therefore, as $|g(\sigma_i)/g(\sigma_1)| >1$ with sufficient large $K$, the graph filter acts as high-pass filter.

This proof supports that the behavior filter depends directly on the sign and values of the coefficients.

Dear Reviewer bzWT,

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

[Response to the computational complexity of GFSA]

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

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

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

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

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

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

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

[1] Shen, Zhuoran, et al. "Efficient attention: Attention with linear complexities." WACV 2021.

[Responses to Theorem 3.1 and its proof]

Response to Q1.

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

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

Response to Q2.

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

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

Response to Q3.

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

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

Since $\sigma_1 = 1$, we have:

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

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

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

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

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

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

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

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

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

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

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

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

So I don't think the low-pass filter proof is correct. In fact, It think it means that w2 and $\sigma_i$ term dominates the result. If you divide the K-1 to both denominator and numerator, w0, w1 doesn't seem to have any effect on the final convergence.

We sincerely thank Reviewer XKs2 for the review and positive feedback, highlighting our strengths in

1. Well-written paper.
2. Comprehensive experiments strongly support the advantage of GFSA.

Below, we would like to address each of your questions and concerns:

Response to W1: confusing notation

Thank 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.

Response to W2: Taylor approximation

We 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.

The 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.

In 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.

This 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.

Response to Q1: GPU Memory Thank 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.

The 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.

Moreover, 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.

Considering 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.

Dear reviewer XKs2,

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

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

For your convenience, as shown in Table 37 of the paper here:

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

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

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

Best regards,

GFSA authors

We sincerely thank Reviewer k2id for the review and feedback, highlighting our strengths in

1. Easily understandable core idea with promising results across diverse transformer variants.
2. Versatile performance demonstrated across a wide range of tasks in multiple domains.

Below, we would like to address each of your questions and concerns:

Response to W1: varying depth

We would like to highlight the comprehensive layer-wise analysis we have conducted.

Fig. 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. Similar results are observed for BERT on STS-B (Fig. 3) and Graphormer on ZINC (Fig. 4). The singular value distributions (Fig. 2c, 3c, 4c) further support our findings.

This layer-wise analysis provides strong evidence of GFSA's effectiveness in addressing oversmoothing across the full depth of the studied models.

Response to W2: weak baseline

To 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.

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. These experiments follow the settings used in both papers.

Our new results show consistent improvements across various datasets. These additional experiments show the versatility and effectiveness of GFSA beyond our initial studies.

[1] Rampášek et al. "Recipe for a general, powerful, scalable graph transformer." NeurIPS 2022

[2] He et al. "A generalization of vit/mlp-mixer to graphs." ICML 2023

[3] Dwivedi et al. "Long range graph benchmark." Advances in NeurIPS 2022

[4] Dwivedi et al. "Benchmarking graph neural networks." JMLR

Response to W3: comparison with other recent and relevant methods

We would like to highlight the analysis already present in our paper.

As 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.

Table 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.

Regarding [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.

Response to W4: learned filter analysis

We 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.

Our analysis reveals:

1. 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.
2. BERT+GFSA consistently shows higher magnitude responses at higher frequencies compared to vanilla BERT, especially in deeper layers.
3. While vanilla self-attention functions primarily as a low-pass filter, GFSA utilizes a wider range of frequencies.

These 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.

Response to Q1: skip-connection

We 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.

Response to Q2: fine-tuning PLM with different architecture

Thank you for your question about GFSA implementation in our NLP experiments.

We 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].

Our 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.

[1] Fine-tune BERT with Sparse Self-Attention Mechanism, EMNLP-IJCNLP 2019

[2] Fast transformers with clustered attention, NeurIPS 2020

[3] Enhancing Self-Attention with Knowledge-Assisted Attention Maps, ACL 2022

Response to Q3: memory overheads

Please refer to our Response to Q1 of Reviewer XKs2.

4. Limitations (scalability and extendability):

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

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

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

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

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

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

• Table: Accuracy (%)

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

[4] Tay, Yi, et al. "Long range arena: A benchmark for efficient transformers." arXiv preprint arXiv:2011.04006 (2020).

[5] Wang, Sinong, et al. "Linformer: Self-attention with linear complexity." arXiv preprint arXiv:2006.04768 (2020).

[6] Beltagy, Iz, Matthew E. Peters, and Arman Cohan. "Longformer: The long-document transformer." arXiv preprint arXiv:2004.05150 (2020).

[7] Zeng, Zhanpeng, et al. "You only sample (almost) once: Linear cost self-attention via bernoulli sampling." ICML 2021.

[8] Katharopoulos, Angelos, et al. "Transformers are rnns: Fast autoregressive transformers with linear attention." ICML 2020.

[9] Shen, Zhuoran, et al. "Efficient attention: Attention with linear complexities." WACV 2021.

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

Best regards,

GFSA authors

Dear Reviewer k2id,

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

1. Regarding oversmoothing correlation with Transformer performance:

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

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

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

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

2. Statistical significance of improvements:

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

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

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

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

3. Comparison with recent baselines:

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

[2] Guo, Jialong, et al. "SLAB: Efficient Transformers with Simplified Linear Attention and Progressive Re-parameterized Batch Normalization." ICML 2024.

[3] Xu, Xuwei, et al. "GTP-ViT: Efficient Vision Transformers via Graph-based Token Propagation." WACV **2024.

continued in the next comment

We sincerely thank Reviewer Py4c for the review and feedback, highlighting our strengths in

1. Extensive experimentation across diverse domains demonstrating the generalizability of GFSA.
2. Clear and well-organized presentation of ideas.
3. Strong emphasis on reproducibility with detailed implementation information and code availability.

Below, we would like to address each of your questions and concerns:

Response to W1: Sensitivity of $K$

We 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.

Response to W2: Misleading figure

We 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.

Response to Q1: Missing code

We 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.

Response to Q2. Sensitivity of $K$

Regarding 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. As 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.

Importantly, 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.

Hello, Reviewer. The author has submitted a response to your comments. Whether or not it addresses your concerns, it would be greatly appreciated if you could acknowledge that you have reviewed the reply.