Official Comment by Authors (1/2)
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 $\textit{\textbf{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.