Year: 2022

Abstract:
Recently over-smoothing phenomenon of Transformer-based models is observed in both vision and language fields. However, no existing work has delved deeper to further investigate the main cause of this phenomenon. In this work, we make the attempt to analyze the over-smoothing problem from the perspective of graph, where such problem was first discovered and explored. Intuitively, the self-attention matrix can be seen as a normalized adjacent matrix of a corresponding graph. Based on the above connection, we provide some theoretical analysis and find that layer normalization plays a key role in the over-smoothing issue of Transformer-based models. Specifically, if the standard deviation of layer normalization is sufficiently large, the output of Transformer stacks will converge to a specific low-rank subspace and result in over-smoothing. To alleviate the over-smoothing problem, we consider hierarchical fusion strategies, which combine the representations from different layers adaptively to make the output more diverse. Extensive experiment results on various data sets illustrate the effect of our fusion method.

heading: 1 INTRODUCTION
text: Over the past few years, Transformer (Vaswani et al., 2017) has been widely used in various natural language processing (NLP) tasks, including text classification (Wang et al., 2018a), text translation (Ott et al., 2018), question answering (Rajpurkar et al., 2016; 2018) and text generation (Brown et al., 2020). The recent application of Transformer in computer vision (CV) field also demonstrate the potential capacity of Transformer architecture. For instance, Transformer variants have been successfully used for image classification (Dosovitskiy et al., 2021), object detection (Carion et al., 2020) and semantic segmentation (Strudel et al., 2021). Three fundamental descendants from Transformer include BERT (Devlin et al., 2019), RoBERTa (Liu et al., 2019) and ALBERT (Lan et al., 2020), which achieve state-of-the-art performance on a wide range of NLP tasks.
Recently, Dong et al. (2021) observes the “token uniformity” problem, which reduces the capacity of Transformer-based architectures by making all token representations identical. They claim that pure self-attention (SAN) modules cause token uniformity, but they do not discuss whether the token uniformity problem still exists in Transformer blocks. On the other hand, Gong et al. (2021) observe the “over-smoothing” problem for ViT (Dosovitskiy et al., 2021), in that different input patches are mapped to a similar latent representation. To prevent loss of information, they introduce additional loss functions to encourage diversity and successfully improve model performance by suppressing over-smoothing. Moreover, “overthinking” phenomenon, indicating that shallow representations are better than deep representations, also be observed in (Zhou et al., 2020; Kaya et al., 2019). As discussed in Section 3, this phenomenon has some inherent connection with over-smoothing. In this paper, we use “over-smoothing” to unify the above issues, and refer this as the phenomenon that the model performance is deteriorated because different inputs are mapped to a similar representation.
As the over-smoothing problem is first studied in the graph neural network (GNN) literature (Li et al., 2018; Xu et al., 2018; Zhao & Akoglu, 2020), in this paper, we attempt to explore the cause of such
∗Equal contribution.
problem by building a relationship between Transformer blocks and graphs. Specifically, we consider the self-attention matrix as the normalized adjacency matrix of a weighted graph, whose nodes are the tokens in a sentence. Furthermore, we consider the inherent connection between BERT and graph convolutional networks (Kipf & Welling, 2017). Inspired by the over-smoothing problem in GNN, we study over-smoothing in BERT from a theoretical view via matrix projection. As opposed to Dong et al. (2021), where the authors claim that layer normalization is irrelevant to over-smoothing, we find that layer normalization (Ba et al., 2016) plays an important role in over-smoothing. Specifically, we theoretically prove that, if the standard deviation in layer normalization is sufficiently large, the outputs of the Transformer stacks will converge to a low-rank subspace, resulting in over-smoothing. Empirically, we verify that the conditions hold for a certain number of samples for a pre-trained and fine-tuned BERT model (Devlin et al., 2019), which is consistent with our above observations.
To alleviate the over-smoothing problem, we propose a hierarchical fusion strategy that adaptively fuses representations from different layers. Three fusion approaches are used: (i) Concat Fusion, (ii) Max Fusion, and (iii) Gate Fusion. The proposed method reduces the similarity between tokens and outperforms BERT baseline on the GLUE (Wang et al., 2018a), SWAG (Zellers et al., 2018) and SQuAD (Rajpurkar et al., 2016; 2018) data sets.
In summary, the contributions of this paper are as follows: (i) We develop the relationship between self-attention and graph for a better understanding of over-smoothing in BERT. (ii) We provide theoretical analysis on over-smoothing in the BERT model, and empirically verify the theoretical results. (iii) We propose hierarchical fusion strategies that adaptively combine different layers to alleviate over-smoothing. Extensive experimental results verify our methods’ effectiveness.

heading: 2 RELATED WORK

heading: 2.1 TRANSFORMER BLOCK AND SELF-ATTENTION
text: Transformer block is a basic component in Transformer model (Vaswani et al., 2017). Each Transformer block consists of a self-attention layer and a feed-forward layer. Let X ∈ Rn×d be the input to a Transformer block, where n is the number of input tokens and d is the embedding size. The self-attention layer output can be written as:
Attn(X) = X + h∑ k=1 σ(XWQk (XW K k ) >)XW Vk W O> k = X + h∑ k=1 ÂkXW V O k , (1)
where h is the number of heads, σ is the softmax function, and WQk ,W K k ,W V k ,W O k ∈ Rd×dh (where dh = d/h is the dimension of a single-head output) are weight matrices for the query, key, value, and output, respectively of the kth head. In particular, the self-attention matrix
Â = σ(XWQ(XWK)>) = σ(QK>) (2)
in (1) plays a key role in the self-attention layer (Park et al., 2019; Gong et al., 2019; Kovaleva et al., 2019). As in (Yun et al., 2020; Shi et al., 2021; Dong et al., 2021), we drop the scale product 1/ √ dh to simplify analysis.
The feed-forward layer usually has two fully-connected (FC) layers with residual connection:
FF (X) = Attn(X) +ReLU(Attn(X)W1 + b1)W2 + b2,
where W1 ∈ Rd×dff ,W2 ∈ Rdff×d (dff is the size of the intermediate layer) are the weight matrices, and b1, b2 are the biases. Two layer normalization (Ba et al., 2016) operations are performed after the self-attention layer and fully-connected layer, respectively.

heading: 2.2 OVER-SMOOTHING
text: In graph neural networks, over-smoothing refers to the problem that the performance deteriorates as representations of all the nodes become similar (Li et al., 2018; Xu et al., 2018; Huang et al., 2020). Its main cause is the stacked aggregation layer using the same adjacency matrix. Recently, several approaches have been proposed to alleviate the over-smoothing problem. Xu et al. (2018) propose a jumping knowledge network for better structure-aware representation, which flexibly
leverages different neighborhood ranges. ResGCN (Li et al., 2019) adapts the residual connection and dilated convolution in the graph convolutional network (GCN), and successfully scales the GCN to 56 layers. Zhao & Akoglu (2020) propose PairNorm, a novel normalization layer, that prevents node embeddings from becoming too similar. DropEdge (Rong et al., 2020; Huang et al., 2020) randomly removes edges from the input graph at each training epoch, and reduces the effect of over-smoothing.
Unlike graph neural networks, over-smoothing in Transformer-based architectures has not been discussed in detail. Dong et al. (2021) introduce the “token-uniformity” problem for self-attention, and show that skip connections and multi-layer perceptron can mitigate this problem. However, Gong et al. (2021) still observe over-smoothing on the Vision Transformers (Dosovitskiy et al., 2021).

heading: 3 DOES OVER-SMOOTHING EXIST IN BERT?
text: In this section, we first explore the existence of over-smoothing in BERT, by measuring the similarity between tokens in each Transformer layer. Specifically, we use the token-wise cosine similarity (Gong et al., 2021) as our similarity measure:
CosSim = 1 n(n− 1) ∑ i 6=j h>i hj ‖hi‖2‖hj‖2 ,
where n is the number of tokens, hi and hj are two representations of different tokens, and ‖ · ‖2 is the Euclidean norm. Following Dong et al. (2021), we use WikiBio (Lebret et al., 2016) as input to the following Transformer-based models fine-tuned on the SQuAD data set (Rajpurkar et al., 2018): (i) BERT (Devlin et al., 2019), (ii) RoBERTa (Liu et al., 2019) and (iii) ALBERT (Lan et al., 2020).1 For comparison, all three models are stacked with 12 blocks. We calculate each CosSim for each data sample and show the average and standard derivation of CosSim values over all WikiBio data.
In the figures, layer 0 represents original input token representation, and layer 1-12 represents the corresponding transformer layers. As shown in Figure 1(a), the original token representations are different from each other, while token similarities are high in the last layer. For instance, the average token-wise cosine similarity of the last layer of ALBERT and RoBERTa are both larger than 90%.
To illustrate the relationship between “over-thinking” and “over-smoothing”, we compare the tokenwise cosine similarity at each layer with the corresponding error rate. As for the corresponding error rate of layer i, we use the representations from layer i as the final output and fine-tune the classifier. Following Zhou et al. (2020), we experiment with ALBERT (Lan et al., 2020) fine-tuned on the MRPC data set (Dolan & Brockett, 2005) and use their error rate results for convenience. As shown in Figure 1(b), layer 10 has the lowest cosine similarity and error rate. At layers 11 and 12, the tokens have larger cosine similarities, making them harder to distinguish and resulting in the performance drop. Thus, “over-thinking” can be explained by “over-smoothing”.
A direct consequence of over-smoothing is that the performance cannot be improved when the model gets deeper, since the individual tokens are no longer distinguishable. To illustrate this, we increase the number of layers in BERT to 24 while keeping the other settings. As shown in Figure 1(c), the
1Our implementation is based on the HuggingFace’s Transformers library (Wolf et al., 2020).
performance of vanilla BERT cannot improve as the model gets deeper. In contrast, the proposed hierarchical fusion (as will be discussed in Section 6) consistently outperforms the baseline, and has better and better performance as the model gets deeper. Based on these observations, we conclude that the over-smoothing problem still exists in BERT.

heading: 4 RELATIONSHIP BETWEEN SELF-ATTENTION AND GRAPH
text: Since over-smoothing is first discussed in the graph neural network literature (Li et al., 2018; Zhao & Akoglu, 2020), we attempt to understand its cause from a graph perspective in this section.

heading: 4.1 SELF-ATTENTION VS RESGCN
text: Given a Transformer block, construct a weighted graph G with the input tokens as nodes and exp(Q>i Kj) as the (i, j)th entry of its adjacency matrix A. By rewriting the self-attention matrix Â in (2) as Âi,j = σ(QK>)i,j = exp(Q>i Kj)/ ∑ l exp(Q > i Kl), Â can thus be viewed as G’s normalized adjacency matrix (Von Luxburg, 2007). In other words, Â = D−1A, where D = diag(d1, d2, . . . , dn) and di = ∑ j Ai,j . Figure 2 shows an example for the sentence “worth the effort to watch." from the SST-2 data set (Socher et al., 2013) processed by BERT.
Note that graph convolutional network combined with residual connections (ResGCN) (Kipf & Welling, 2017) can be expressed as follows.
ResGCN(X) = X +ReLU(D−1/2AD−1/2XW ) = X +ReLU(ÂXW ), (3)
which has the similar form with the self-attention layer in Eq. (1). By comparing self-attention module with ResGCN, we have the following observations: (i) SinceAi,j 6= Aj,i in general, G in self-attention is a directed graph; (ii) Â = D−1A in self-attention is the random walk normalization (Chung & Graham, 1997), while GCN usually uses the symmetric normalization version Â = D−1/2AD−1/2; (iii) The attention matrices constructed at different Transformer layers are different, while in typical graphs, the adjacency matrices are usually static.

heading: 4.2 UNSHARED ATTENTION MATRIX VS SHARED ATTENTION MATRIX
text: As discussed in Section 2.2, over-smoothing in graph neural networks is mainly due to the repeated aggregation operations using the same adjacency matrix. To compare the self-attention matrices (Â’s) at different Transformer layers, we first flatten the multi-head attention and then measure the cosine similarity between Â’s at successive layers. Experiment is performed with BERT (Devlin et al., 2019), RoBERTa (Liu et al., 2019) and ALBERT (Lan et al., 2020) on the WikiBio data set (Lebret et al., 2016).
Figure 3 shows the cosine similarities obtained. As can be seen, the similarities at the last few layers are high,2 while those at the first few layers are different from each other. In other words, the attention patterns at the first few layers are changing, and become stable at the upper layers.
In the following, we focus on BERT and explore how many layers can share the same selfattention matrix. Note that this is different from ALBERT, which shares model parameters instead of attention matrices. Results are shown in Table 1. As can be seen, sharing attention matrices among the last 8 layers (i.e., layers 5- 12) does not harm model performance. This is consistent with the observation in Figure 3. Note that sharing attention matrices not only reduces the number of parameters in the selfattention module, but also makes the model more efficient by reducing the computations during training and inference. As shown in Table 1, BERT (5-12) reduces 44.4% FLOPs in the selfattention modules compared with the vanilla BERT, while still achieving comparable average GLUE scores.

heading: 5 OVER-SMOOTHING IN BERT
text: In this section, we analyze the over-smoothing problem in BERT theoretically, and then verify the result empirically.

heading: 5.1 THEORETICAL ANALYSIS
text: Our analysis is based on matrix projection. We define a subspaceM, in which each row vector of the element in this subspace is identical.
Definition 1. Define M := {Y ∈ Rn×d|Y = eC,C ∈ R1×d} as a subspace in Rn×d, where e = [1, 1, . . . , 1]> ∈ Rn×1, n is the number of tokens and d is the dimension of token representation.
Each Y in subspaceM suffers from the over-smoothing issue since the representation of each token is C, which is the same with each other. We define the distance between matrix H ∈ Rn×d andM as dM(H) := minY ∈M ‖H − Y ‖F , where ‖ · ‖F is the Frobenius norm. Next, we investigate the distance between the output of layer l and subspaceM. We have the following Lemma.
2For example, in BERT, the attention matrices Â’s for the last 8 layers are very similar.
Lemma 1. For self-attention matrix Â, any H,B ∈ Rn×d and α1, α2 ≥ 0, we have:
dM(HW ) ≤ sdM(H), (4) dM(ReLU(H)) ≤ dM(H), (5)
dM(α1H + α2B) ≤ α1dM(H) + α2dM(B), (6) dM(ÂH) ≤ √ λmaxdM(H), (7)
where λmax is the largest eigenvalue of Â>(I − ee>)Â and s is the largest singular value of W .
Using Lemma 1, we have the following Theorem. Theorem 2. For a BERT block with h heads, we have
dM(Hl+1) ≤ vdM(Hl), (8)
where v = (1 + s2)(1 + √ λhs)/(σ1σ2), s > 0 is the largest element of all singular values of all Wl, λ is the largest eigenvalue of all Â>(I − ee>)Â for each self-attention matrix Â, and σ1, σ2 are the minimum standard deviation for two layer normalization operations.
Proof is in Appendix A. Theorem 2 shows that if v < 1 (i.e., σ1σ2 > (1+s2)(1+ √ λhs)), the output of layer l+ 1 will be closer toM than the output of layer l. An illustration of Theorem 2 is shown in Figure 4. H0 is the graph corresponding to the input layer. Initially, the token representations are very different (indicated by the different colors of the nodes). Recursively, Hl will converge towards to subspaceM if v < 1 and all representations are the same, resulting in over-smoothing. Remark Though we only focus on the case v < 1, over-smoothing may still exist if v ≥ 1. As can be seen, layer normalization plays an important role for the convergence rate v. Interestingly, Dong et al. (2021) claim that layer normalization plays no roles for token uniformity, which seems to conflict with the conclusion in Theorem 2. However, note that the matrix rank cannot indicate similarity between tokens completely because matrix rank is discrete while similarity is continuous. For instance, given two token embeddings hi and hj , the matrix [hi,hj ]> has rank 2 only if hi 6= hj . In contrast, the consine similarity between tokens is h > i hj
‖hi‖2‖hj‖2 .
As discussed in Section 4.1, GCN use the symmetric normalization version Â = D−1/2AD−1/2, resulting in the target subspaceM′ := {Y ∈ Rn×d|Y = D1/2eC,C ∈ R1×d} is dependent with adjacent matrix (Huang et al., 2020). In contrast, our subspaceM is independent of Â thanks to its random walk normalization. Thus, Theorem 2 can be applied to the vanilla BERT even though its attention matrix Â is not similar.

heading: 5.2 EMPIRICAL VERIFICATION
text: Theorem 2 illustrates that the magnitude of σ1σ2 is important for over-smoothing issue. If σ1σ2 > (1+s2)(1+ √ λhs), the output will be closer to subspaceM suffered from over-smoothing. Since s is usually small due to the `2-penalty during training (Huang et al., 2020), we neglect the effect of s and compare σ1σ2 with 1 for simplicity. To verify the theoretical results, we visualize σ1σ2 in different fine-tuned BERT models. Specifically, we take the development set data of STS-B (Cer et al., 2017),
CoLA (Warstadt et al., 2019), SQuAD (Rajpurkar et al., 2016) as input to the fine-tuned models and visualize the distribution of σ1σ2 at the last layer using kernel density estimation (Rosenblatt, 1956).
Results are shown in Figure 5. As can be seen, the distributions of σ1σ2 can be very different across data sets. For STS-B (Cer et al., 2017), σ1σ2 of all data is larger than 1, which means that over-smoothing is serious for this data set. For CoLA (Warstadt et al., 2019) and SQuAD (Rajpurkar et al., 2016), there also exists a fraction of samples satisfying σ1σ2 > 1.

heading: 6 METHOD
text: From our proof in Appendix A, we figure out that the main reason is the post-normalization scheme in BERT. In comparison, to train a 1000-layer GCN, Li et al. (2021) instead apply pre-normalization with skip connections to ensure v > 1. However, the performance of pre-normalization is not better than post-normalization for layer normalization empirically (He et al., 2021). In this section, we preserve the post-normalization scheme and propose a hierarchical fusion strategy to alleviate the over-smoothing issue. Specifically, since only deep layers suffer from the over-smoothing issue, we allow the model select representations from both shallow layers and deep layers as final output.

heading: 6.1 HIERARCHICAL FUSION STRATEGY
text: Concat Fusion We first consider a simple and direct layer-wise Concat Fusion approach. Considering a L-layer model, we first concatenate the representations Hk from each layer k to generate a matrix [H1,H2, . . . ,HL] and then apply a linear mapping to generate the final representation ∑L k=1 αkHk. Here {αk} are model parameters independent with inputs. Since this scheme requires preserving feature maps from all layers, the memory cost will be huge as the model gets deep.
Max Fusion Inspired by the idea of the widely adopted max-pooling mechanism, we construct the final output by taking the maximum value across all layers for each dimension of the representation. Max Fusion is an adaptive fusion mechanism since the model can dynamically decide the important layer for each element in the representation. Max Fusion is the most flexible strategy, since it does not require learning any additional parameters and is more efficient in terms of speed and memory.
Gate Fusion Gate mechanism is commonly used for information propagation in natural language processing field (Cho et al., 2014). To exploit the advantages from different semantic levels, we propose a vertical gate fusion module, which predicts the respective importance of token-wise representations from different layers and aggregate them adaptively. Given token representations {Htk}, where t denotes the token index and k denotes the layer index, the final representation for token t is calculated by ∑L k=1 I t k ·Htk, where It1, It2, . . . , ItL = softmax(g(Ht1), g(Ht2), . . . , g(HtL)). Here L is the number of layers and the gate function g(·) is a fully-connected (FC) layer, which relies on the word representation itself in respective layers to predict its importance scores. The weights of the gate function g(·) are shared across different layers. Even though Concat Fusion and Max Fusion have been investigated in the graph field (Xu et al., 2018), their effectiveness for pre-trained language model have not yet been explored. Besides, since the layer-wise Concat Fusion and element-wise Max Fusion lack the ability to generate token representations according to each token’s specificity, we further propose the token-wise Gate Fusion for adapting fusion to the language scenario.

heading: 6.2 EXPERIMENT RESULTS
text: The BERT model is stacked with 12 Transformer blocks (Section 2.1) with the following hyperparameters: number of tokens n = 128, number of self-attention heads h = 12, and hidden layer size d = 768. As for the feed-forward layer, we set the filter size dff to 3072 as in Devlin et al. (2019). All experiments are performed on NVIDIA Tesla V100 GPUs.

heading: 6.2.1 DATA AND SETTINGS
text: Pre-training For the setting in pre-training phase, we mainly follows BERT paper (Devlin et al., 2019). Our pre-training tasks are vanilla masked language modeling (MLM) and next sentence prediction (NSP). The pre-training datasets are English BooksCorpus (Zhu et al., 2015) and Wikipedia (Devlin et al., 2019) (16G in total). The WordPiece embedding (Wu et al., 2016) and the dictionary containing 30, 000 tokens in (Devlin et al., 2019) are still used in our paper. To pre-process text, we use the special token [CLS] as the first token of each sequence and [SEP] to separate sentences in a sequence. The pre-training is performed for 40 epochs.
Fine-tuning In the fine-tuning phase, we perform downstream experiments on the GLUE (Wang et al., 2018a), SWAG (Zellers et al., 2018) and SQuAD (Rajpurkar et al., 2016; 2018) benchmarks. GLUE is a natural language understanding benchmark, which includes three categories tasks: (i) single-sentence tasks (CoLA and SST-2); (ii) similarity and paraphrase tasks (MRPC, QQP and STS-B); (iii) inference tasks (MNLI, QNLI and RTE). For MNLI task, we experiment on both the matched (MNLI-m) and mismatched (MNLI-mm) versions. The SWAG data set is for grounded commonsense inference, while SQuAD is a task for question answering. In SQuAD v1.1 (Rajpurkar et al., 2016), the answers are included in the context. SQuAD v2.0 (Rajpurkar et al., 2018) is more challenge than SQuAD v1.0, in which some answers are not included in the context. Following BERT (Devlin et al., 2019), we report accuracy for MNLI, QNLI, RTE, SST-2 tasks, F1 score for QQP and MRPC, Spearman correlation for STS-B, and Matthews correlation for CoLA. For SWAG task, we use accuracy for evaluation. For SQuAD v1.1 and v2.0, we report the Exact Match (EM) and F1 scores. Descriptions of the data sets and details of other hyper-parameter settings are in Appendix B and in Appendix C, respectively.
6.2.2 RESULTS AND ANALYSIS
Since BERT (Devlin et al., 2019) and RoBERTa (Liu et al., 2019) share the same architecture and the only difference is data resource and training steps, here we mainly evaluate our proposed method on BERT and ALBERT (Lan et al., 2020). Results on the GLUE benchmark are shown in Table 2, while results on SWAG and SQuAD are illustrated in Table 3. For SQuAD task, in contrast to BERT which (Devlin et al.,
2019) utilize the augmented training data during fine-tuning phase, we only fine-tune our model on the standard SQuAD data set. As can be seen, our proposed fusion strategies also perform better than baselines on various tasks consistently.
Following the previous over-smoothing measure, we visualize the token-wise cosine similarity in each layer. Here we perform visualization on the same data sets as Section 5.2 and the results are shown in Figure 6. For all three data sets, the cosine similarity has a drop in the last layer compared
with baseline. It’s remarkable that the similarity drop is the most obvious in STS-B (Cer et al., 2017), which is consistent with our empirical verification that STS-B’s σ1σ2 is the largest in Section 5.2. Since the representation of tokens from prior layers is not similar with each other, our fusion method alleviates the over-smoothing issue and improve the model performance at the same time.
To study the dynamic weights of fusion gate strategy, we visualize the importance weight Itk for each token t and for each layer k. We randomly select three samples and the visualization results are illustrated in Figure 7. Note that our gate strategy will reduce to vanilla model if representation from the last layer is selected for each token. As can be seen, the weight distribution of different tokens is adaptively decided, illustrating that the vanilla BERT stacks model is not the best choice for all tokens. The keywords which highly affect meaning of sentences (i.e. “women”, “water”, “fish”) are willing to obtain more semantic representations from the deep layer, while for some simple words which appear frequently (i.e. “a”, “is”), the features in shallow layers are preferred.

heading: 7 CONCLUSION
text: In this paper, we revisit the over-smoothing problem in BERT models. Since this issue has been detailed discuss in graph learning field, we firstly establish the relationship between BERT and graph for inspiration, and find out that self-attention matrix can be shared among last few blocks without performance drop. Inspired by over-smoothing discussion in graph convolutional network, we provide some theoretical analysis for BERT models and figure out the importance of layer normalization. Specifically, if the standard derivation of layer normalization is sufficiently large, the output will converge towards to a low-rank subspace. To alleviate the over-smoothing problem, we also propose a hierarchical fusion strategy to combine representations from different layers adaptively. Extensive experiment results on various data sets illustrate the effect of our fusion methods.

heading: A PROOF
text: Lemma 1. For self-attention matrix Â, any H,B ∈ Rn×d and α1, α2 ≥ 0, we have: dM(HW ) ≤ sdM(H), (4)
dM(ReLU(H)) ≤ dM(H), (5) dM(α1H + α2B) ≤ α1dM(H) + α2dM(B), (6)
dM(ÂH) ≤ √ λmaxdM(H), (7)
where λmax is the largest eigenvalue of Â>(I − ee>)Â and s is the largest singular value of W .
Proof. Here we only prove the last inequality (7), as the inequity is different from the theories in GCN since Â is not symmetric and shared in Transformer architecture. For the first three inequalities, we refer to Oono & Suzuki (2020) and Huang et al. (2020).
Write HH> = QΩQ> for the eigin-decomposition of HH>, where Q = [q1, q2, . . . , qn] is the orthogonal and Ω = diag(ω1, . . . , ωn) with all ωi ≥ 0. Recall e = n−1/2[1, 1, . . . , 1]> ∈ Rn×1. Note that
dM(ÂH) 2 = ‖(I − ee>)ÂH‖2F = tr{(I − ee>)ÂHH>Â>(I − ee>)}
= n∑ i=1 ωiq > i Â >(I − ee>)Âqi.
Since matrix Â>(I − ee>)Â is positive semidefinite, its all eigenvalues are non-negative. Let λmax be the largest eigenvalue of Â>(I − ee>)Â. Consider
λmaxdM(H) 2 − dM(ÂH)2 = n∑ i=1 ωiq > i {λmax(I − ee>)− Â>(I − ee>)Â}qi.
Let Σ = λmax(I − ee>)− Â>(I − ee>)Â.
Note that Â = D−1A is a stochastic matrix, we have Âe = e. Thus, Â>(I − ee>)Â has an eigenvalue 0 and corresponding eigenvecter e. Let fi be a normalised eigenvector of Â>(I−ee>)Â orthogonal to e, and λ be its corresponding eigenvalue. Then we have
e>Σe = 0,
f>i Σfi = λmax − λ ≥ 0.

heading: It follows that dM(ÂH)2 ≤ λmaxdM(H)2.
text: Discussion Assume further that Â is doubly stochastic (so that Â>e = e) with positive entries. Then by Perron–Frobenius theorem (Gantmakher, 2000), Â>Â has a maximum eigenvalue 1 with associated eigenvector e as well. In this case, the matrix Â>(I − ee>)Â = Â>Â − ee> has a maximum eigenvalue λmax < 1. Theorem 2. For a BERT block with h heads, we have
dM(Hl+1) ≤ vdM(Hl), (8) where v = (1 + s2)(1 + √ λhs)/(σ1σ2), s > 0 is the largest element of all singular values of all Wl, λ is the largest eigenvalue of all Â>(I − ee>)Â for each self-attention matrix Â, and σ1, σ2 are the minimum standard deviation for two layer normalization operations.
Proof. From the definition of self-attention and feed-forward modules, we have
Attn(X) = LayerNorm(X + H∑
k=1
ÂkXW k + 1b>) = (X + H∑ k=1 ÂkXW k + 1b> − 1b>LN )D−1LN
FF (X) = LayerNorm(X + ReLU(XW1 + 1b>1 )W2 + 1b > 2 )
= (X + ReLU(XW1 + 1b>1 )W2 + 1b > 2 − 1b>LN )D−1LN
Based on the Lemma 1, we have
dM(Attn(X)) = dM((X + h∑ k=1 ÂkXW k + 1b> − 1b>LN )D−1LN )
≤ dM(XD−1LN ) + dM( h∑
k=1
ÂkXW kD−1LN ) + dM(1(b− bLN ) >)
≤ σ−11 dM(X) + h∑
k=1
dM(Â kXW kD−1LN )
≤ σ−11 dM(X) + √ λhsσ−11 dM(X) = (1 + √ λhs)σ−11 dM(X).
dM(FF (X)) = dM((X + ReLU(XW1 + 1b>1 )W2 + 1b > 2 − 1b>LN )D−1LN )
≤ dM(XD−1LN ) + dM(ReLU(XW1 + 1b > 1 )W2D −1 LN ) + dM(1(b > 2 − b>LN )D−1LN ) ≤ dM(XD−1LN ) + dM(XW1W2D −1 LN ) + dM(1b > 1 W2D −1 LN ) ≤ σ−12 dM(X) + s2σ −1 2 dM(X) = (1 + s2)σ−12 dM(X).
It follows that dM(Hl+1) ≤ (1 + s2)(1 + √ λhs)σ−11 σ −1 2 dM(Hl).

heading: B DATA SET
text: B.1 MNLI
The Multi-Genre Natural Language Inference (Williams et al., 2018) is a crowdsourced ternary classification task. Given a premise sentence and a hypothesis sentence, the target is to predict whether the last sentence is an [entailment], [contradiction], or [neutral] relationships with respect to the first one.
B.2 QQP
The Quora Question Pairs (Chen et al., 2018) is a binary classification task. Given two questions on Quora, the target is to determine whether these two asked questions are semantically equivalent or not.
B.3 QNLI
The Question Natural Language Inference (Wang et al., 2018b) is a binary classification task derived from the Stanford Question Answering Dataset (Rajpurkar et al., 2016). Given sentence pairs (question, sentence), the target is to predict whether the last sentence contains the correct answer to the question.
B.4 SST-2
The Stanford Sentiment Treebank (Socher et al., 2013) is a binary sentiment classification task for a single sentence. All sentences are extracted from movie reviews with human annotations of their sentiment.
B.5 COLA
The Corpus of Linguistic Acceptability (Warstadt et al., 2019) is a binary classification task consisting of English acceptability judgments extracted from books and journal articles. Given a single sentence, the target is to determine whether the sentence is linguistically acceptable or not.
B.6 STS-B
The Semantic Textual Similarity Benchmark (Cer et al., 2017) is a regression task for predicting the similarity score (from 1 to 5) between a given sentence pair, whose sentence pairs are drawn from news headlines and other sources.
B.7 MRPC
The Microsoft Research Paraphrase Corpus (Dolan & Brockett, 2005) is a binary classification task. Given a sentence pair extracted from online news sources, the target is to determine whether the sentences in the pair are semantically equivalent.
B.8 RTE
The Recognizing Textual Entailment (Bentivogli et al., 2009) is a binary entailment classification task similar to MNLI, where [neutral] and [contradiction] relationships are classified into [not entailment].
B.9 SWAG
The Situations with Adversarial Generations (Zellers et al., 2018) is a multiple-choice task consisting of 113K questions about grounded situations. Given a source sentence, the task is to select the most possible one among four choices for sentence continuity.
B.10 SQUAD V1.1
The Stanford Question Answering Dataset (SQuAD v1.1) (Rajpurkar et al., 2016) is a large-scale question and answer task consisting of 100K question and answer pairs from more than 500 articles. Given a passage and the question from Wikipedia, the goal is to determine the start and the end token of the answer text.
B.11 SQUAD V2.0
The SQuAD v2.0 task (Rajpurkar et al., 2018) is the extension of above SQuAD v1.1, which contains the 100K questions in SQuAD v1.1 and 50K unanswerable questions. The existence of unanswerable question makes this task more realistic and challenging.
C IMPLEMENTATION DETAILS
The hyper-parameters of various downstream tasks are shown in Table 4.

Review summaries:
This paper explored the over-smoothing problem in BERT from the perspective of graph. In detail, empirical analysis first has been provided for demonstrating over-smoothing exist in BERT. Then, the authors theoretically prove the observation through the comparison between self-attention and graph. The authors claim that "layer normalization plays a key role in the over-smoothing issue, namely, if the standard deviation of layer normalization is sufficiently large, the output of Transformer stacks will converge to a specific low-rank subspace and results in over-smoothing". To alleviate the over-smoothing issue, layer fusion methods (which have been widely explored in previous studies) have been presented and verified to be effective in downstream tasks. However, the over-smoothing problem is neither well theoretically analyzed nor empirically proved to be addressed via layer fusion methods. 

The current manuscript explored the token over-smoothing problem in Bert transformer blocks. Empirically, the authors showed that the token over-smooth problem is increasingly severe in deeper layers of a Bert model. The token over-smoothing is potentially harmful to task performance. As the over-smoothing problems have been discussed in graph networks extensively, the authors established a connection between transformer blocks with graph networks and looked at the over-smoothing problem of transformer blocks analogously. The authors revealed that layer normalization in the transformer blocks contributed to the over-smoothing issue both theoretically and empirically. Moreover, the authors proposed to improve the over-smoothing issue by hierarchical fusion strategies, that is utilize token representation from earlier layers. Overall, the author applied a novel approach to shed light on an insufficiently investigated problem. The paper was well written.   

This paper tries to understand the over-smoothing phenomenon of Transformer-based models such as BERT. The analysis is from the perspective of viewing BERT and Transformer as graph neural networks. By analogy and analysis of graph neural networks, authors show some theoretical analysis and find that layer normalization plays a key role in the over-smoothing issue. Specifically, if the standard deviation of layer normalization is sufficiently large, the output of Transformer stacks will converge to a specific low-rank subspace and results in over-smoothing. Then to alleviate the over-smoothing problem, authors consider hierarchical fusion strategies, which combine the representations from different layers adaptively to make the output more diverse.