Polynomial-based Self-Attention for Table Representation learning

Thank you for your thoughtful feedback and questions on our work. We have revised our manuscript following your comments.

Q1. Detailed analysis of the computational complexity

Starting with the self-attention mechanism’s time complexity, the original attention mechanism operates at $\mathcal{O}(n^2d)$, where $n$ represents the number of tokens and $d$ is the dimension of each token. Our method introduces additional complexity to compute $A^k$ with $k-1$ matrix multiplications, resulting in a time complexity of $\mathcal{O}(n^2d + (k-1)n^{2.371552})$, where we assume that we use algorithm in [1]. Practically, if $d > (k-1)n^{2.371552}$, the time complexity of CheAtt becomes $\mathcal{O}(n^2d)$, a condition observed to be met across almost all 10 datasets.

Also, we have updated our manuscript based on your suggestion in red.

Q2. Thorough comparison of CheAtt to other methods

To the best of our knowledge, this study is the first to investigate over-smoothing in transformers applied to tabular data. Unfortunately, this uniqueness made it impossible to compare our work with other methods addressing over-smoothing in Transformer-based tabular data approaches.

Q3. Add up or down arrows in the chart

Thank you for the suggestion; we have added arrows to the tables.

Q4. How the layer would scale to larger datasets or more complex models

We emphasize that our proposed layer is applicable to any transformer-based model, regardless of its complexity. Scaling up the layer for larger or more complex datasets can be achieved through conventional methods, such as increasing the number of transformer blocks or augmenting the hidden vector size. This scaling process enables the attention matrix to expand, and the Chebyshev polynomial of the attention matrix can express a more complex data distribution. Additionally, we are conducting further experiments on larger datasets and will promptly report the results upon completion.

References

[1] Williams et al. New bounds for matrix multiplication: from alpha to omega. In SODA, 2024.

Thank you for your thoughtful feedback and questions on our work. We have revised our manuscript following your comments.

W1. Details of the task of tabular data understanding

Thank you for the comment. In response, we have included additional details about the task in our manuscript.

Q1. Existing research addressing the over-smoothing issue

To the best of our knowledge, our study is the first to address the issue of over-smoothing specifically for tabular data. The mitigation of over-smoothing for GCN has been a long-standing research area [1, 2]. In specific, GREAD [2] is our special case, where Equation (7) in our main paper with $k=2$, $w_0=1$, and $w_1=-1$. Moreover, research to alleviate over-smoothing and feature collapse in ViT (Vision Transformer) has recently become active [3].

References

[1] Rusch et al. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993, 2023.

[2] Choi et al. GREAD: Graph neural reaction-diffusion networks. In ICML, 2023.

[3] Gong et al. Vision transformers with patch diversification. arXiv preprint arXiv:2104.12753, 2021.

Thank you for your thoughtful feedback on our work. Following your comments, we have revised our manuscript.

W1. To include more citations, theorems, and a more rigorous analysis to substantiate the paper's motivation and claims

The self-attention matrix and the PageRank matrix share one key common characteristic that their adjacency matrices are fully connected with many small values. PageRank uses a matrix of $(1-\alpha) \mathbf{A} + \alpha\mathbf{\frac{1}{N}}$, where $\mathbf{A}$ is an adjacency matrix, $N$ is the number of nodes, and $\alpha$ is a damping factor, and therefore, all elements have non-zero (small) values. (Please refer to Section 3.2 PageRank and Equation (5) for details.) In the self-attention matrix, this is also the case since Transformers use the softmax function. Because of this characteristic, in addition, PageRank converges and so does our method.

As you said, the self-attention matrix is unpredictable. As long as the self-attention matrix is fully connected, however, our method is correct (since we rely on the PageRank theory). It is practically unbelievable that the softmax produces zeros although some values are small. Note that in PageRank, small values are also used when $N$ is very large, i.e., a web-scale graph of billions of nodes.

The first and second conditions shown in the paper are obvious. For the last condition, we refer to [1]. An irreducible chain, as defined in [1], has a period that is common to all states. The irreducible chain will be called $***aperiodic***$ if all states have a period of 1. This implies that a Markov chain is aperiodic if there is at least one self-loop. As discussed earlier, the self-attention matrix has non-negative values for all elements, including diagonal elements, making the self-attention matrix aperiodic.

We added a section in Appendix in red regarding this point.

W2. Results with excessive errors

For reproducibility, we repeated all experiments 5 times and reported the mean and standard deviation. We used the same seed numbers for all experiments for fair comparison. The two scores you mentioned have one or two outliers in the set. In Table 2, 70.9±13.90 is the mean and standard deviation of 73.58, 78.07, 79.44, 76.87, 46.30. In Table 3, 58.1±24.32 is the mean and standard deviation of 77.94, 25.98, 78.17, 77.56, 30.72. Among those 5 repetitions, one or two scores are unusually low, attributed to the unstable training of AE.

W3. Improvement on SAINT

We are now testing more hyperparameters for SAINT+CheAtt since as can be seen in Appendix C.3 Table 8, we have searched only 3 hyperparameters recommended in its original paper even though SAINT has a number of hyperparameters to search. We will provide the results as soon as the ongoing experiments are completed. We will also update our paper one more time afterward.

Reference

[1] David A. et al. Markov chains and mixing times. Vol. 107. In American Mathematical Soc., 2017.

W4. Relative time consumption and more comprehensive analysis are needed

We have incorporated your suggestions into our manuscript, and we kindly ask you to refer to the updated version. To begin, we have discussed computational complexity in detail in our revised manuscript, marked in red. Originally, the attention mechanism operated at $\mathcal{O}(n^2d)$, where $n$ represents the number of tokens, and $d$ is the dimension of each token. Our method introduces additional complexity to compute $A^k$ with $k-1$ matrix multiplications, resulting in a time complexity of $\mathcal{O}(n^2d + (k-1)n^{2.371552})$, assuming the use of the algorithm in [2]. In practical terms, if $d > (k-1)n^{2.371552}$, the time complexity of CheAtt becomes $\mathcal{O}(n^2d)$, a condition observed across almost all 10 datasets.

Secondly, we originally reported the absolute wall clock time to emphasize efficiency. However, we also acknowledge the importance of relative time. Therefore, in Table 5, we now present both absolute and relative time consumption. Additionally, we have updated the increase in inference time to the time taken to infer 1,000 samples. We have also included a summary of training time in Table 5, representing the average time for 5 epochs of training, along with reporting the relative time. For training time, we train the model for 5 epochs and average the time. The updated table is presented below.

Lastly, we apologize for any confusion, but the reported reduction in time after using CheAtt on Phishing was a typo. This has been corrected in our updated paper. Thank you for bringing it to our attention.

Below is the updated Table 5:

Reference

[2] Williams et al. "New bounds for matrix multiplication: from alpha to omega." In SODA, 2024.

Dear reviewer gFjL,

Thank you for waiting for the final result. We have finished our additional experiments. To be more specific, we have searched for more hyperparameters for SAINT+CheAtt. The summarized result is as follows:

The improvement of SAINT after applying CheAtt was 0.01% before we searched for more hyperparameters. After additional experiments, we achieved an improvement of 0.64%.

Regarding the "quality of the base model," our initial intention was to emphasize the fact that the performance after applying CheAtt is proportional to the original performance of the base model, irrespective of CheAtt's performance. However, recognizing the potential for confusion, we have opted to remove this statement from the text.

In addition, we have uploaded our new manuscript highlighting changed results in blue. Please refer to our revised manuscript following your comments.