Demystifying Oversmoothing in Attention-Based Graph Neural Networks
Authors: Xinyi Wu
Amir Ajorlou
Zihui Wu
Ali Jadbabaie
Venue: NeurIPS 2023 spotlight (2023)
Keywords: graph neural networks
attention mechanisms
oversmoothing
dynamical systems
theory
TL;DR: We rigorously establish that oversmoothing happens exponentially as model depth increases for attention-based graph neural networks.

Abstract: Oversmoothing in Graph Neural Networks (GNNs) refers to the phenomenon where increasing network depth leads to homogeneous node representations. While previous work has established that Graph Convolutional Networks (GCNs) exponentially lose expressive power, it remains controversial whether the graph attention mechanism can mitigate oversmoothing. In this work, we provide a definitive answer to this question through a rigorous mathematical analysis, by viewing attention-based GNNs as nonlinear time-varying dynamical systems and incorporating tools and techniques from the theory of products of inhomogeneous matrices and the joint spectral radius. We establish that, contrary to popular belief, the graph attention mechanism cannot prevent oversmoothing and loses expressive power exponentially. The proposed framework extends the existing results on oversmoothing for symmetric GCNs to a significantly broader class of GNN models, including random walk GCNs, Graph Attention Networks (GATs) and (graph) transformers. In particular, our analysis accounts for asymmetric, state-dependent and time-varying aggregation operators and a wide range of common nonlinear activation functions, such as ReLU, LeakyReLU, GELU and SiLU.

Demystifying Oversmoothing in Attention-Based Graph Neural Networks
Xinyi Wu 1.2
Amir Ajorlou² Zihui 3u Ali Jadbabaie 1.2 Institute for Data, Systems and Society (IDSS), MIT
2 Laboratory for Information and Decision Systems (LIDS), MIT 3 Department of Computing and Mathematical Sciences (CMS), Caltech arinyiwu,ajorlee j jadbabai @mit..... edu zwu2@caltech.ent
Abstract
Oversmoothing in Graph Neural Networks (GNNs) refers to the phenomenon where increasing network depth leads to homogeneous node representations. While previous work has established that Graph Convolutional Networks (GCNs) ex- ponentially lose expressive power, remains controversial whether the graph attention mechanism can mitigate oversmoothing. In this work, provide definitive answer to this question through a rigorous mathematical analysis, by viewing attention-bart based GNNs as nonlinear time-varying dynamical systems and incorporating tools and techniques from the theory of products of inhomogeneous matrices and the joint spectral radius. We establish that, contrary popular belief, the graph attention mechanism cannot prevent oversmoothing and loses expressive power exponentially. The proposed framework extends the existing results over- smoothing for symmetric GCNs to a significantly broader class of GNN models, including random walk GCNs, Graph Attention Networks (GATs) and (graph) transformers. In particular, our analysis accounts for asymmetric, state-dependent and varying aggregation operators and wide range of common nonlinear activation functions, such as ReLU, LeakyReLU, GELU and SiLU.
Introduction
Graph neural networks (GNNs) have emerged as a powerful framework for learning with graph- structured data 4 8 9
38 and have shown great promise in diverse domains such as and recommender systems [40]. Most GNN models follow the molecular biology 45), physics
13
19
32
12] where the representation of each node is computed by recursively aggregating and transforming the representations of its neighboring nodes.
message-passing paradigm
One notable drawback of repeated messagg--pssing
passing is oversmoothing, which refers to the phenomenon that stacking sessaage-asssingg GNN layers makes node representations of the same connected 41 As result, whereas depth has been considered crucial for the success of deep learning many fields such as computer vision [16]
component converge to the same vector (5] 18 19 24 26
most GNNs used in practice remain relatively shallow and often only have few layers the theory side, while previous works have shown that the symmetric Graph Convolution Networks (GCNs) with ReLU and LeakyReLU nonlinearities exponentially lose expressive power, analyzing the oversmoothing phenomenon in other types of GNNs is still an open question (5] [26]_ In particular, the question of whether the graph attention mechanism can prevent oversmoothing has not been settled yet. Motivated by the capacity of graph attention to distinguish the importance of different edges in the graph, some works claim that oversmoothing is alleviated in Graph Attention Networks (GATs), heuristically crediting to GATs' ability to learn adaptive node-wise aggregation operators via the attention mechanism (25 On the other hand, has been empirically observed that similar to
[9] 38 42 On
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the case of GCNs, oversmoothing seems inevitable for attention baseed GNNs such as GATs B1 or (graph) transformers 34]. The latter can be viewed eatentiio-based GNNs on complete graphs.
In this paper, we provide a definitive answer to this question - attention- GNNs also lose expressive power exponentially, albeit potentially at a slower exponential rate compared to GCNs. Given that attention-based GNNs can be viewed as nonlinear time-varying dynamical systems, our analysis is built on the theory of products of inhomogeneous matrices [14 of joint spectral radius [30]. as these methods have been long proved effective in the analysis of While classical results only apply to generic one-dimension linear time-van time-varying systems, we address four major challenges arising in analyzing attention-basee GNNs: (1) the aggregation operators computed by attention are state-dependent in contrast to conventional fixed graph convolutions; (2) the systems are multi-dimensional, which involves the coupling across feature dimensions; (3) the dynamics are nonlinear due to the nonlinear activation function in each layer; (4) the learnable weights and aggregation operators across different layers result time-varying dynamical systems.
33 and the concept
time-inhoue inmooooooooessu markov chains and ergodicity of dynamical systems 22
14
Below, we highlight our key contributions:
As our main contribution, we establish that oversmoothing happens exponentially as model depth increases for attention-based GNNs, resolving the long-standing debate about whether attention-based GNNs can prevent oversmoothing.
We amalyze attention based GNNs through the lens of nonlinear, time-varying dynamical systems. The strength of our analysis stems from its ability to exploit the inherently common connectivity structure among the typically asymmetric state-dependent aggregation operators at different attentional layers. This enables us to derive rigorous theoretical results on the ergodicity of infinite products of matrices associated with the evolution of node representations across layers. Incorporating results from the theory of products of inhomogeneous matrices and their joint spectral radius, then establish that oversmoothing happens an exponential rate for attention- based GNNs from our ergodicity results.
Our analysis generalizes the existing results on oversmoothing for symmetric GCNs to sig- nificantly broader class of GNN models with asymmetric, state-dependent and time-varying aggregation operators and nonlinear activation functions under general conditions. In partic- ular, our analysis can accommodate wide range of common nonlinearities such ReLU, LeakyRel U, and even non-monotone ones like GELU and SiL.U. We validate our theoretical results on six real-world datasets with two attention- based GNN architectures and five common nonlincaritics.
2 Related Work
Oversmoothing problem in GNNs Oversmoothing is well-known problem in deep GNNs, and
many techniques have been proposed in order to mitigate it practically (6) 15 20 21 29 43 47). On the theory side, analysis of oversmoothing has only been carried out for the graph convoluttonn case [5] 26 41) In particular, by viewing graph convolutions as a form of Laplacian filter, prior works have shown that for GCNs, the node representations within each connected component of
a graph will converge to the same value exponentially [5] 26 However, oversmoothing is also empirically observed in coantion-based GNNs such as GATs [1 or transformers [34]. Although
some people hypothesize based on heuristies that attention can alleviate oversmoothing 255 a
rigorous analysis of oversmoothing in attention-based GNNs remains open (5)
Theoretical analysis of snteention-ased GNNs Existing theoretical results on iitention-based GNNs are limited to one-layer graph attention. Recent works in this line include Brody et al. [3] showing that the ranking of attention scores computed by a GAT layer is unconditioned on the query node, and Fountoulakis et al. [11 studying node classification performance of one-layer GATs on random graph model. More relevantly, Wang et al. [39 made a claim that oversmoothing is asymptotically inevitable in GAT'. Aside from excluding nonlinearities in the analysis, there are several flaws in the proof of their main result (Theorem 2). In particular, their analysis assumes the same stationary distribution for all the stochastic matrices output by attention at different layers. This typically not the case given the state-dependent and time varying nature of these matrices. In fact, the main challenge in analyzing multi-layer attention lies in the sependeee and time-varying

---

nature of these input-output mappings. Our paper offers novel contributions to the research on attention-based GNNs by developing rich set of tools and techniques for analyzing multi-layer graph attention. This addresses a notable gap in the existing theory, which has primarily focused on one-layer graph attention, and paves the way for future research to study other aspects of multi-layer graph attention.
3 Problem Setup
3.1 Notations
Let IR be the set of real numbers and N be the set of natural numbers. We use the shorthands [n] == (I,...,n} and Nzo = N U [0}. We denote the zero-vector of length N by R and the all-one vector of length N by 1 RN We represent undirected graph with N nodes by g = X), where A E {0. 13NNNN is the adjacency matrix and E R are the node feature vectors of dimension d. Let E(G) be the of edges of G. For nodes i, E [N]. Aij 1 if and only if and j are connected with an edge in G, i.e., (i, E E(g). For each E [N]. X; E Rd represents the feature vector for node i. We denote the degree matrix g by Dacg diag (A1) and the set of all neighbors of node i by N₁
Let ||- |12. I. Iloo || ||e be the 2-norm, co-norm and Frobenius norm, respectively. We use || |Imax to denote the matrix norm, i.e., for matrix M E "R"x", || := max Misl. We use Sew to
i)
denote element-win inequality. Lastly, for a matrix M, we denote its 1th row by M,. and jth column by g.
3.2 Graph attention mechanism
We adopt the following definition of graph attention mechanism. Given node representation vectors X; and X,. we first apply a shared learnable linear transformation W E RRdxd' to each node, and then use an attention function V IR
x Rdd R to compute a raw attention coefficient
Cjy (W X,, TT))
that indicates the importance of node j's features node Then the graph structure injected into the mechanism by performing masked attention, where for each node i, we only compute its attention its neighbors. To make coefficients easily comparable across different nodes, we normalize eij among all neighboring nodes of node using the softmax function to get the normalized attention coefficients:
exp(eij)
P.j = softmax,(eej) = EXEN, exp(exx)
The matrix P. where the entry in the 5th row and the jth column is P.j, is row stochastic matrix. We refer to P as aggregation operator in message-passing
3.3 Attention-based GNNs
Having defined the graph attention mechanism, we can now write the update rule of single graph attentional layer as
='= ='=o(P OPXW).
where and X' are are the input and output node representations, respectively, a(-) is a pointwise nonlinearity function, and the aggregation operator P is function of XW.
As result, the output of the tth graph attentional layers can be written as (1+1) o (pP()) x ((()))
t N20,
where ( = is the input node features, W E Rd xd' for E N and (()) E Rdxd', For the rest of this work, without loss of generality,
assume that d= d''
The above definition is based on single-head graph attention. Mulli-head graph attention uses E weight matrices W W...., Wx in each layer and averages their individual single-head outputs [1] 38 Without loss of generality, we consider single graph attention in our analysis Section 4 but we note that results automatically apply to the multi-head graph attention setting since K finite.

---

3,4 Measure of oversmoothing
We use the following notion of oversmoothing, inspired by the definition proposed in Rusch et al. BI
Definition 1. For an undirected and connected graph G, p.: Rxxd - Rzo is called a node similarity
measure if satisfies the following axioms:
1. 3c E I& such that X; c.for all node if and only if p(X) for X XEB ERxd;
2. (Y) (X) + p(Y), for all X,Y E RRd
Then oversmoothing with respect to is defined as the layer-wise convergence of the node-similarity measure μ to zero, i.e.,
lim p (xx())== =
We say oversmoathing happens at an exponential rate if there exists constants C1 C2 0, such that for any t E N,
m(x()) S Cce
We establish our results on oversmoothing for attention- GNNs using the following node similarity measure:
1
x(X) :0 1xxlEE, where xx
(4)
N
Proposition | 1 I is a node similarity measure.
The proof of the above proposition is provided in Appendix B Other common node similarity Our measure is mathematically equivalent to the measure inf { YlIx) defined in Oono and Suzuki [26). but our form is more direct
measures include the Dirichlet energy 31 31
Y=1c",eee .cERd
to compute. One way to see the equivalence is to consider the orthogonal projection into the space perpendicular to span{1], denoted by B ( Then our definition of μ satisfies | - 17al= = || where the latter quantity is exactly the measure defined in (26].
3.5 Assumptions
We make the following assumptions (in fact, quite minimal) deriving our results:
A1 The graph connected and non-bipartite.
A2 The attention function ())) )) is continuous.
A3 The sequence {Il IT [W]0 [mmmax is bounded.
A4 The point-wise nonlinear activation function (()) satisfies 0 < o(xx < for x * 0 and (0) 0.
We note that all of these assumptions are either standard or quite general. Specifically, A1 is standard assumption for theoretical analysis graphs. For graphs with more than connected components, the same results apply to each connected component. A1 can also be replaced with requiring the graph G to be connected and have self-loops each node. Non- Non-bipartiteness and self-loops both ensure that long products of stochastic matrices corresponding to aggregation operators in different graph attentional layers will eventually become strictly positive.
The assumptions on the GNN architecture A2 and A4 can be easily verified for commonly used GNN designs. For example, the attention function LeakyReLU(a [W X;| | "X,)), a E gad used in the GAT (38) where F-II.] denotes concatenation, is specific case that satisfies A2. Other architectures that satisfy A2 include GATv2 3 and (graph) transformers [37] As for A4, one way to
We distinguish the definition of oversmoothing and the rate of oversmoothing. This parallels the notion of stability and its rate in dynamical systems.
"In fact. our results are not specific to our choice of node similarity measure μ and directly apply to any Lipschitz node similarity measure, including the Dirichlet energy under our assumptions. See Remark 2 after Theorem I

---

satisfy it is to have a be 1-Lipschitz and (()) < O for x < 0 and ( 2 0 for x > O. Then it is easy verify that most of the commonly used nonlinear activation functions such as ReLU, LeakyReLU, GELU, SILU, ELU, tanh all satisfy A4.
Lastly, A3 is to ensure boundedness of the node representations" trajectories x for all & N20- Such regularity assumptions quite common in the asymptotic analysis of dynamical systems, is also the case for the prior works analyzing oversmoothing in symmetric GCNs 26]
Main Results
In this section, we lay out road- map for deriving main results, highlighting the key ideas of the proofs. The complete proofs are provided in the Appendices.
We start by discussing the dynamical system formulation of attention-based GNNs in Section 4.1 By showing the boundedness of the node representations' trajectories, we prove the existence of common connectivity structure among aggregation operators across different graph attentional layers in Section 4.2 This implies that graph attention cannot fundamentally change the graph connectivity, crucial property that will eventually lead to oversmoothing. In Section 4.3 we develop framework for investigating the asymptotic behavior of attention- -based GNNs by introducing the notion of ergodicity and its connections to oversmoothing. Then utilizing result common connectivity structure among aggregation operators, we establish ergodicity results for the systems associated with attention-based GNNs. In Section 4.4 we introduce the concept of the joint spectral radius for set of matrices (30) and employ it to deduce exponential convergence of node representations to a common vector from our ergodicity results. Finally, present our main result oversmoothing in attention-based GNNs in Section 4.5 and comment on oversmoothing in GCNs in comparison with
attention-based GNNs in Section 4.6
4.1
Attention-based GNNs nonlinear time-varying dynamical systems
The theory of dynamical systems concerns the evolution of some state interest over time. By view- ing the model depth the time variable, the ouput- mapping at each graph attentional layer x(++1) = o (P(t) ( (()) describes a nonlinear time-varying dynamical system. The attention- based aggregation operator p(f) is state-dependent it is a function of (()()) Given the notion of oversmoothing defined in Section 3.4 we are interested in characterizing behavior of x as
t X6.
the activation function o.) is the identity map, then repeated application of gives
(++1) p(t) x("))((00 w
The above linear form would enable us to leverage the rich literature on the asymptotic behavior of the products of inhomogeneous row-stochastic matrices (see, e.g., 14 33) in analyzing the long-term behavior of attention based GNNs. Such neat expansion, however, is not possible when dealing with nonlinear activation function of (-). To find remedy, let us start by observing that element-wise application of to vector y E RRd can be written
(o(8) y
a = diag
y.
(5)
where diag [ty) is a diagonal matrix with (y:)//: on the ith diagonal entry. Defining (0)/0 d0) or if the derivative does not exist along with the assumption (0) in A4, it is easy to check that the above identity still holds for vectors with zero entries.
We can use 5 to write the tth column of (t++) as
x((+2) (x(() = D. p(9) (X D.00) D.00pp p(t)
Σ 1 (0)
(6)
j=1
where 1(99 is diagonal matrix. It follows from the assumption on the nonlinearities A4 that
diag(0) Sow DDO0) Sew diag(1).
5

---

We define D to be the set of all possible diagonal matrices D satisfying the above inequality:
= (d) d BR Sew Sew 1).
Using 6 recursively, we arrive at the following formulation for x((+1);
x (1+1))
Σ
II k=
w Seset1
D Jet1
pip p(s...D)) p(0) x(0))x(00)
Jeti Ee
4.2
Common connectivity structure among aggregation operators across different layers
We can use the formulation in 7 show the boundedness of the node representations' trajectories ( for all E N20. which turn implies the boundedness of the imput graph attention in each layer, (()).
Lemma Under assumptions A3-A4, there exists C such that || | max S for all t N2o-
For continuous (.. the following lemma is direct consequence of Lemma suggesting that the graph attention mechanism cannot fundamentally change the connectivity pattern of the graph.
Lemma Under assumptions A2-A4, there exists >> such that for all E N2o and for any (i.j) E(G), we have p! 2
One might argue that Lemma is an artifact the continuity of the softmax function. The softmax function is, however, often favored in attention mechanisms because of its trainability in back propagation compared to discontinuous alternatives such as hard thresholding. Besides trainability conceptual level whether is reasonable to absolutely drop edge from the
issues, it is unclear graph as the case for hard thresholding. LemmaAiis is an important step towards the main convergence result of this work, which states that all the nodes will converge to the same representation vector an exponential rate. We define the family of row row-stochastic matrices satisfying Lemma benama/bblo...
Definition Let e >
We define Pg.e to be the set of cow-stochastic matrices satisfying the
following conditions:
1. < P. < if (i,g) E E()),
2. P. = (i,5) & E(G),
4.3 Ergodicity infinite products of matrices
Ergodicity, in its most general form, deals with the long-term behavior of dynamical systems. The oversmoothing phenomenon in GNNs defined in the sense of (2) concerns the convergence of all rows of (+) common vector. To this end, we define ergodicity in our analysis as the convergence of infinite matrix products to a rank-one matrix with identical rows.
Definition (Ergodicity). Let B E 1)x N be the orthogonal projection onto the space orthogo- nal to span(1] []. A sequence of matrices [M j is ergodic if
lim 1-000
B
II
M (1) =0
n=0
We will take advantage of the following properties of the projection matrix already established in Blondel et al. (2]:
1. B1 =
2. |Bx||2 = ||||| for N i T 0:
3. Given any row-stochastic matrix P NNN there exists a unique matrix P E ((N-I)x such that BP = PB.
MMore generally, for (..)) :) that outputs bounded attention for bounded inputs.

---

We can use the existing results on the ergodicity of infinite products of inhomogeneous stochastic show that any sequence of matrices in Pa. is ergodic.
matrices [14 33
Lemma 3. Fix > O. Consider sequence of matrices {p(() (e in Pg.e. That is, p(t) E for all t E Ngo- Then pe is ergodic.
The main proof strategy for Lemma to make use of the Hilbert projective metric and the Birkhoff contraction coefficient. These are standard mathematical tools to prove that an infinite product of inhomogeneous stochastic matrices is ergodic. We refer interested readers to the textbooks [4 for comprehensive study of these subjects.
Despite the nonlinearity of a(),, the formulation ( enables to express the evolution of the feature vector trajectories as weighted sum of products of matrices of the form DP where D E D and P E Pg.e. We define the set of such matrices
Mg.e DDP
key step in proving oversmoothing for attention- based GNNs under our assumptions is to show the ergodicity of the infinite products of matrices in MMg.. In what follows, we lay out the main ideas of the proof, and refer readers Appendix(F Ffoo the details.
Consider sequence (D() p(t) define
1 in Mg.er that is, p(t) E Mgg, for all t E N2u- For to t1.
Qua,i == ((t))(())) ... ...o p(to), 5, = IN
where In denotes the x N identity matrix. The common connectivity structure among p() established in Section 4.2 allows to show that long products of matrices DP from Mg,e will eventually become contraction in co-norm. More precisely, we can show that there exists T E N and 0 < 1 such that for all E N2o.
1Q S co.-
Next, define Bx : II cδ.) and let 3 = lim Ba. Note that is well-defined because the k-oc
partial product is non non-increasing and bounded from below. We can the above contraction property to show the following key lemma.
Lemma 4. Let BR o1 co.) and == lim 9k-
k-+00
1. If 3 0, then
lim Qo 10+00
2. If 3 0, then lim BQo = 0.
The ergodicity of sequences of matrices in Mg.e immediately follows from Lemma 4 which in turn implies oversmoothing as defined in (2).
Lemma 5. Any sequence (D()) p(0) = in Mg.. is ergodic.
The proof techniques developed in 5 are restricted symmetric matrices hence cannot be extended to more general family of GNNs, as they primarily rely matrix norms for con- vergence analysis. Analyses solely using matrix norms are often too coarse to get meaningful results when it comes to asymmetric matrices. For instance, while the matrix 2-norm and matrix eigenvalues are directly related for symmetric matrices, same does not generally hold for asymmetric matrices. Our analysis, the other hand, cxploits the inherently common connectivity structure among these matrices in deriving the ergodicity results in Lemma
Remark
4.4
Joint spectral radius
Using the ergodicity results in the previous section, we can establish that oversmoothing happens in attention-base GNNs. show that oversmoothing happens an exponential rate, we introduce the notion of joint spectral radius, which is generalization of the classical notion of spectral radius of a single matrix set of matrices 30) We refer interested readers to the textbook [17 for comprehensive study of the subject.
7

---

Definition 4 (Joint Spectral Radius). For collection of matrices A. the joint spectral radius (SR(.A) defined be (A) = sup sup k-+00 Ar.
|A1
and it is independent of the norn used.
In plain words, the joint spectral radius measures the maximal asymptotic growth rate that can be obtained by forming long products of matrices taken from the set Ao analyze the convergence rate of products of matrices in Mg.. to a rank-one matrix with identical rows, we treat the two cases of linear and nonlinear activation functions, separately.
For the linear case, where (-)) is the identity map, we investigate the dynamics induced by p(t)s on the subspace orthogonal span 1] and use the third property of the orthogonal projection B established in Section 4.3 to write PPP.2 ... Ps Px.2...P.BB. where each P; is the unique matrix
in (N that satisfies BP: P.B. Let us define
pg.e == (P: BP = PB, P
We can use Lemma 3 to show that the joint spectral radius Pg. is strictly less than 1. Lemma 6. Let 0 < < 1. Under assumptions A1-A4, JSR(Pg.c) < 1.
For the nonlinear case, let 0 < 5 < 1 and define
D3 fdiag(d): d E RR, ,, Sew d Sew 8), Mg D D Pg..).
Then again, using the ergodicity result from the previous section, we establish that the joint spectral radius of Mg.e,5 is also less than 1.
Lemma 7. Let e, < Under assumptions A1-A4, JSR(MG...) <1.
The above lemma is specifically useful in establishing exponential rate for oversmoothing when dealing with nonlinearities for which Assumption 4 holds in the strict sense, i... 0 < a < (e.g..
GELU and SiLU nonlinearities). Exponential convergence, however, can still be established under a weaker requirement, making it applicable to ReLU and Leaky ReLU,
will see in Theorem []
follows from the definition of the joint spectral radius that if JSR(A) < 1, for any JSR(A) q < 1, there exists C' for which
|| AnylAAuulll S Ca*
(8)
for all y N-1 and A,, .2.... A A.
4.5 Main Theorem
Applying to the recursive expansion of ((++1) in 7 using the 2-norm, we can prove the exponential convergence of (()())) to zero for the similarity measure uu-) defined in 4 which in turn implies the convergence of node representations
common representation an exponential rate. This completes the proof of the main result of this paper, which states that oversmoothing defined in 2 is unavoidable for attention- GNNs, and that an exponential convergence rate can be attained under general conditions.
Theorem 1. Under assumptions A1-A4,
lim (( = 0, t-00
indicating oversmoothing happens asymptotically in attention-based GNNs with general nonlineari- ties. In addition,
(linear) a(.) is the identity map, or
(nonlinear) there exists K E and 0 < < for which the following holds: For all m E N20. there is nm E {0} U [K- 1] such that for any [d], a rec (mkKmnn--/- ()mm)))))))))))))))))))))))))(
)
xmmmk (m K-n)) 5 for
Xrec
some r. E [N].
(*)
then there exists q < and (g(g) > 0 such that
((x(1)) S C1g', Vt 2 0.
8

---

As a result. node representations ( exponentially converge to the same value as the model depth
t + 00.
Theorem 1 establishes that oversmoothing is asymptotically inevitable for attention-based GNNs with general nonlinearities. Despite similarity- importance assigned to different nodes via the aggregation operator p(t), such attention-based mechanisms yet unable fundamentally change the connectivity structure of P(), resulting in node representations converging to common vector. Our results hence indirectly support the emergence alternative ideas for changing the graph connectivity structure such as edge-dropping [15 29] or graph-rewiring [21], in effort to mitigate oversmoothing.
Remark 1. For nonlinearities such as SiLU or GELU, the condition (*) is automatically satisfied under A3-A4. For ReLU and LeakyRel.U, this is equivalent to requiring that there exists K E N such
that for all m E N2o. there exists Tem [0) U [K- 1] where for any [d], Xree
X(nK+na < 0 for
some Te E [d].
Remark 2. We note that our results are not specific to the choice of node similarity measure
((X)= || -X-11xlle ll considered in our analysis. In fact, exponential convergence of any other Lipschitz node similarity measure ye to O is a direct corollary of Theorem To see this, observe that for a node similarity measure yt with a Lipschitz constant L, holds that
x ( (1,xxx -
Lx(X)..
In particular, the Dirichlet energy is Lipschitz given that the input X has compact domain, es- tablished in Lemma 1 Hence our theory directly implies the exponential convergence of Dirichlet energy.
4.6 Comparison with the GCN
Computing or approximating the joint spectral radius for given set of matrices is known to be hard in general (36]. yet it is straightforward to lower bound JSR(Pg.)) ) as stated in the next proposition.
Proposition 2. Let X be the second largest eigenvalue of D 1/2 AD Then under assumptions A1-A4, holds that À S JP......).
deg
In the linear case, the upper bound on the convergence rate that we get for graph attention in Theorem is lower bounded by JS.( A direct consequence of the above result is that is least as large as A. On the other hand, previous work has already established that in the graph convolution case, the convergence rate of ((X((t) is O(x)) attention-basse GNNs to potentially have better expressive power at finite depth than GCNs, even though they both inevitably suffer from oversmoothing. This is also evident from the numerical experiments that we present the next section.
5 26 It is thus natural to expect
5 Numerical Experiments
In this section, we validate our theoretical findings via numerical experiments using the three commonly used homophilic benchmark datasets: Cora, CiteSeer, and PubMed [4] and the three commonly used heterophilic benchmark datasets: Cornell, Texas, and Wisconsin (28). We note that
our theoretical results are developed for generic graphs and thus hold for datasets exhibiting either homophily or heterophily and even those that are not necessarily either of the two. More details about
the experiments are provided in Appendix K
For each dataset, we trained a 128-layer single-head GAT and a 128-layer GCN with the random walk graph convolution Degg-,, A, each having 32 hidden dimensions and trained using the standard features and splits. The GCN with the random walk graph convolution is special type of attention- based GNNs where the attention function is constant. For each GNN model, we considered various nonlinear activation functions: ReLU, LeakyReLU (with three different negative slope values: 0.01, 0.4 and 0.8) and GELU. Here, we chose GELU as an illustration of the generality of our assumption on nonlinearities, covering even non-monotone activation functions such as GELU. We ran each experiment 10 times. Figure] 1 shows the evolution of po( (0) in log-log scale on the largest connected component of each graph as we forward pass the input X into trained model. The solid curve the average over 10 runs and the band indicates one standard deviation around the average.

---

Cora GAT
GleSeer GAT
Pubiiled GAI
17
2100
54
GCN
CiteSeer GCN
PubMed GON
100
54
150
Se1
19.
38
13.13
320
Comell GAT
Texas GAT
Wisconsin GAT
332
2100
56
MEL
28-
La 18-211
102
26
10
10
100
10 190
number of layers
Figure I: Evolution of (9) (in log-log scale) on the largest connected component of each dataset (top rows: homophilic graphs; bottom 2 rows: heterophilic graphs). Oversmoothing happens exponentially in both GCNs and GATs with the rates varying depending on the choice of activation function. Notably, GCNs demonstrate faster rates of oversmoothing compared to GATs.
We observe that, as predicted by our theory, oversmoothing happens at an exponential rate for both GATs and GCNs, regardless of the choice of nonlinear activation functions in the GNN architectures. Notably, GCNs exhibit a significantly faster rate of oversmoothing compared to GATs. This aligns the observation made in Section 44.6 expecting potentially better expressive power for GATs than GCNs at finite depth. Furthermore, the exponential convergence rate of oversmoothing varies among GNNs with different nonlinear activation functions. From a theory perspective, different activation functions constitute different subsets of Mg.. and different sets of matrices have different joint spectral radii, it is not surprising that the choice of nonlinear activation function would affect the convergence rate. In particular, among the nonlinearties we considered, ReLU in fact magnifies oversmoothing the second most. As result, although ReLU is often the default choice for the standard implementation of many GNN architectures [10 [9], one might wish to consider switching other nonliearities to better mitigate oversmoothing.
Conclusion
Oversmoothing is one of the central challenges in developing more powerful GNNs. In this work, we reveal new insights on oversmoothing in attention- GNNs by rigorously providing a negative answer to the open question of whether graph attention implicitly prevent oversmoothing, By analyzing the graph attention mechanism within the context nonlinear time-varying dynamical systems, we establish that attention-base GNNs lose expressive power exponentially model depth increases.
We upper bound the convergence rate for oversmoothing under very general assumptions on the nonlinear activation functions. One may try to tighten the bounds by refining the analysis separately for each of the commonly used activation functions. Future research should also aim to improve the design of graph attention mechanisms based on our theoretical insights and utilize our analysis techniques to study other aspects of multi-layer graph attention.
10

---

Acknowledgments
Xinyi Wu would like thank Jennifer Tang and William Wang for helpful discussions. The authors are grateful to Zhijian Zhuo and Yifei Wang for identifying an error in an earlier draft of the paper, thank the anonymous reviewers for providing valuable feedback, and acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing computing resources that have contributed to the research results reported within this paper.
This research has been supported in part by ARO MURI W91 INF- 19-021- ONR N00014-20-1-2394, and the MIT-IBM Watson AT Lab.
References
[1] Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and koray kavukcuoglu. Interaction networks for learning about objects, relations and physics. In NeurIPS, 2016.
[2] Vincent D. Blondel, Julien M. Hendrickx, Alexander Olshevsky, and John N. Tsitsiklis. Con- vergence in multiagent coordination, consensus, and flocking. Proceedings of the 44th IEEE Conference on Decision and Control, pages 2996-3000, 2005.
[3] Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In ICLR, 2022.
[4] Joan Bruna, Wojeiech Zaremba, Arthur D. Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
[5] Chen Cai and Yusu Wang. A note over-smoothing for graph neural networks. In ICML Graph Representation Learning and Beyond (GRL+) Workshop. 2020.
[6] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, 2020.
[7] Ingrid Daubechies and Jeffrey C. Lagarias. Sets of matrices all infinite products of which converge. Linear Algebra and its Applications, 161:227-263. 1992.
[8] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. NeurlPS, 2016.
[9] David Kristjanson Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparrageee Iparraguirre, Rafael Gómez- Bombarelli, Timothy D. Hirzel, Alán Aspuru-Guzii and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In NeurIPS, 2015.
[10] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning Graphs and Manifolds, 2019.
[11] Kimon Fountoulakis, Amit Levi, Shenghao Yang, Aseem Baranwal, and Aukosh Jagannath. Graph attention retrospective. ArXiv, abs/2202. 13060 2022.
[12] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. ICML, 2017.
[13] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IJCNN, 2005.
[14] Darald J. Hartfiel. Nonhomogeneons Matrix Products. 2002.
[15] Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick G. Duffield, Krishna R. Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. In ICML, 2020.
[16] Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
[17] Raphaël M. Jungers. The Joint Spectral Radius: Theory and Applications. 2009.

---

[18] Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over)smoothing. In NeurIPS. 2022.
[19] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[20] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
[21] Johannes Klicpera, Stefan Weißenbbrger,, and Stephan Günnemann. Diffusion improves graph learning. In Neural Information Processing Systems, 2019.
[22] Peter D. Lax. Functional Analysis. 2002.
[23] David A. Levin, Yuval Peres, and Flizabeth L. Wilmer. Markov Chains and Mixing Times. 2008.
[24] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
[25] Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering gen: Overcoming oversmoothness in graph convolutional networks. In NeurIPS, 2020.
[26] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
[27] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach Veti,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, 2019.
[28] Hongbin Pei, Bingzhen Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In /CLR, 2020.
[29] Yu Rong, Wen bing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In ICLR, 2020.
[30] Gian-Carlo Rota and W. Gilbert Strang. A note on the joint spectral radius. 1960.
[31]
T.Konstamtin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. ArXiv, abs/2303.10993, 2023.
[32] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. JEEE Transactions on Neural Networks, 20:61-80, 2009.
[33] Eugene Seneta. Non-negative Matrices and Markov Chains. 2008
[34] Han Shi, Jiahui Gao, Hang Xu, Xiaodan Liang, Zhenguo Li, Lingpeng Kong, Stephen M. Lee, and James Tin-Yau Kwok. Revisiting over-smoothing in bert from the perspective of graph. In ICLR, 2022.
[35] Jacques Theys. Joint spectral radius: theory and approximations. Ph. D. dissertation, 2005.
[36] John N. Tsitsiklis and Vincent D. Blondel. The Lyapunov exponent and joint spectral radius of pairs of matrices are hard- not impossible- compute and to approximate. Mathematics of Control, Signals and Systems, 10:31-40, 1997.
[37] Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NewrIPS, 2017.
[38] Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
[39] Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovee. Improving graph attention networks with large basgi constraints. ArXiy, abs/1910.11945, 2019.
12

---

[40] Shiwen Wu, Wentao Zhang, Fei Sun, and Bin Cui. Graph neural networks in recommender systems: survey. ACM Computing Surveys, 55:1 37, 2020.
[41] Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In ICLR, 2023.
[42] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32:4- 24, 2019.
[43] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
[44] Zhilin Yang. William Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICMI, 2016.
[45] Jiaxuan You, Bowen Liu, Rex Ying, Vijay S. Pande, and Jure Leskovec. Graph convolutional molecular graph generation. NeurIPS, 2018.
policy network for
[46] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In ICLR, 2020.
[47] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In ICLR, 2020.
13

---

A Basic Facts about Matrix Norms
In this section, we list some basic facts about matrix norms that will be helpful in comprehending the subsequent proofs.
A.1 Matrix norms induced by vector norms
Suppose vector norm lla on RR and a vector norm Ill on R are given. Any matrix M E RR=x= induces linear operator from IR to R. with respect the standard basis, and one defines the corresponding induced norm or operator norm by
| sup {
||Mull |u||
; E IR", 0
If the p-norm for vectors (1 S S oc) is used for both spaces 12t and R", then the corresponding operator norm
|Mullp
| = sup
||l||p
v
The matrix 1-norm and co-norm can be computed by
|
max
Myy.
that is, the maximum absolute column sum of the matrix M;
[M|]
max Ism
Myy,
j=1
that is, the maximum absolute row sum of the matrix M.
Remark In the special case of p = 2, the induced matrix norm || is called the spectral norm, and is equal to the largest singular value of the matrix.
For square matrices, we note that the name "spectral norm" does not imply the quantity directly related to the spectrum of matrix, unless the matrix is symmetric.
Example We give the following example of a stochastic matrix P. whose spectral radius is 1, but its spectral norm is greater than 1.
0.9
0.1
||l|a xe 1.0188
0.25
0.75
A.2 Matrix (p. norms
The Frobenius norm of matrix M E Rxxx is defined as
|
M
and it belongs to family of entry-wise matrix norms: for S p.q S oc, the matrix (p, norm is defined as
4/p
1/9
n
m
llo.
Mijl 1
The special case p = q the Frobenius norm
||,, and p = q oo yields the max norm
|| maxx-
14

---

A.3 Equivalence of norms
For any two matrix norms || lla and
lla, we have that for all matrices M E Rmxx,
r M|| S || S a||Mi|
for positive numbers and In particular, the following inequality holds for the 2-norm || 1/2 and the co-norm
Iloo:
1 Vn M 1lM s VmllM
B Proof of Proposition 1
is straightforward check that || 17x |F satisfies the two axioms node similarity measure:
1. |X - 17x ||F = = X 17x X; 7x for all node i.
2. Let 7x 7x =
xxx N
and y = 1 L N. then 7x + 7イ (xx++) 7X+Y. So
m(X + Y) = ||(X + Y) 1 + > || 17x + Y -1
$ ||X 1xx + ||Y - 11r|11
= (X)) + u(Y).
C Proof of Lemma 1
According to the formulation
mwc ii R=
Suseet )
x- (1-1
Σ
1 p(t) p(t)..., p(0) p())) p(0)x x
des1mb, do)
we thus obtain that
ii
|X (++1)
100
Σ
inciess
D p(() ,(......0) ((00))0))pp11 plo)
Jets
j4n= (on=ii......o)((dpf
K=
i k=o
Σ
||DS Jots p(t) p(ot...D pt)) p()) [
5
Σ
Ii k==
||x0011
<
2:11 mi (0tm
(h (eskes) 1)
S Co
Σ
I M==
= -C.ll(Iw:().... D.ill.
where Co equals the maximal entry in [X(").
The assumption A3 implies that there exists C' > O such that for all / E Noo and i E [d].
[_ < C'N.
Hence there exists C" 0 such that for all Nz0 and [d]. we have
||x 100 & C"
proving the existence of C> O such that |X(0) max & C. for all & E Noo-
15

---

D Proof of Lemma 2
Lemma 2 is a direct corollary of Lemma and the assumption that (+,-) assigns bounded attention bounded inputs.
E Proof of Lemma 3
E.1 Auxiliary results
We make use of the following sufficient condition for the ergodicity of the infinite products of row-stochastic matrices.
Lemma 8 (Corollary 5.1 [14 Consider sequence of row-stochastic matrices { Let at and by be the smallest and largest entries in Stt), respectively. If Et= b. co, then {5(0) Fr is ergodic.
In order to make use of the above result, we first show that long products of P(t)s from Ps. will eventually become strictly positive. For to S f,, we denote
p(trfo) p(tt) ...)).
Lemma 9. Under the assumption A1, there exist T E N and > 0 such that for all to 2 0,
S ig
p
S 1,,L S SijSN.
Proof. Fix any T E Noo- Since ||P(t) 1| < for any p(t) E Pg... it follows that [ |1o0 S
1 and hence Pij plto+Titta & 1, for all 1 I i,j j $ N.
To show the lower bound, without loss of generality, we will show that there exist N and c such that
((T.) cc v1 s i.
Since each p(t) has the same connectivity pattern as the original graph G, it follows from the assumption A1 that there exists E N such that p(7:0) is a positive matrix, following a similar argument the for Proposition 1.7 in 23 For each pair of nodes i,j, since assume that the p(r((.)):0)
graph G is connected, there exists r(i, j) such that Pij
> on the other hand, since we also assume each node has a self-loop. ((t:0) > for all 2 0 and hence for 2 r(i,)),
plt:0) 2 p ((t-r(i-)) p(r(t.):0) > 0.
For 2 t(() == max (i,,), we have P > for all node j in g. Finally, if 2 T == max f()). jEg
iEG
then (t:0) if > for all pairs of nodes j,j in G. Notice that P (T:0) is weighted sum of walks of length 7 between nodes and and hence p(T.)) 0 if and only if there exists walk of length
T between nodes and j. Since for all t Nzo. Ph if (i, E E(G), conclude that
Pij
(T:0)
2 cc.
E.2 Proof of Lemma 3
Given the sequence [e we use T E N from Lemma and define
p(k) : p((++1)::k)
Then { is ergodic if and only if {K()) 3 k= is ergodic. Notice that by Lemma for all Nzo, there exists e > 0 such that e 5 ((k) < $1,11 S i,j S N. Then Lemma direct consequence of Lemma
16

---

Proof of Lemma
E.1
Notations and auxiliary results
Consider sequence p/ in Mg.e. For to S b define
Qto D((t)) p(t)). ((ta) p(to)
and
6. - ( - 1o
where IN denotes the x N identity matrix. is also useful to define
Qua =p(ti) : p(t-)) p(to),
We start by proving the following key lemma, which states that long products of matrices in Mg.c eventually become a contraction in co-norm.
Lemma 10. There exist 0 < c < and T E N such that for all to S l1,
1 I - (t-c6e)ll@toottllll
Proof. First observe that for every T 2 0,
1 s / 1 ttt
loo
p(( p(h+T+1)) p(th+ || 11 Il
where the second inequality is based on the following element- wise inequality:
(it++) ((ah-++-))p((+77--100 (() Sew p(++T) p(u1++1)) p(1++))
By Lemma there exist 7' E N and 0 < 1 such that
2 c p(t++t)))..)+++))
Since the matrix product p(h+T) p is row-stochastic, multiplying with the diagonal matrix ((4) from right decreases the row sums by at least c(1 (((1)) = co,,, where ((ft) here denotes the smallest diagonal entry of the diagonal matrix ((1), Hence,
plu++T))))++ 1(th+ 1 D S 51-c5- cō,,
F.2 Proof of Lemma
Now define 3x := o1 co.) and let lim 3x. Note that well-defined because the k-+0c partial product is non-increasing and bounded from below. Then we present the following result, which is stated as Lemma 4 in the main paper and from which the ergodicity of any sequence in Mg.. is an immediate result.
Lemma
Let Bg I cō.) and 3 lim 3
k-+00
1. If 3 = 0, then
lim Qo, 0; 1-+00
If 0, then
lim BQ = 0. k-+00
Proof. We will prove the two cases separately.
17

---

[Case 3 = 0] We will show that B 0 implies
lim 11Q = 0, and as result, 10
lim 10, 0. For 0 s ST- 1, let define
R=000
8 = I1 (1 6)HET).
k=0
Then by Lemma 10 we get that
lim 11Qu 10 S $0,11000,lllo0 k0000
By construction, 3 1
BJ_ Hence, if B = 0 then 3 = 0 for some S J0 - 1, which
yields lim ||Qo,ell 0. Consequently, lim 1|Q 0 implies that lim Qo, 0. 1e-000
k0000
10-000
[Case 3 >
First observe that if 3 > then v0 < 1 1, there exist N2o such that
II (1 co.) > 1 77.
(9)
tm
Using 1-r S e- for all x E R, we deduce
0
II
E 06 > >1
t=
It also follows from (9) that cō2 > 7, equivalently & < for 2 Choosing 1) <
thus ensures that 6₃ for t 2 Putting this together with the fact that, there exist 6 0 such that 1 e-ba for all [0, 4) obtain
I & Em
II
b6, (1 - =1 n/
(10)
Define the product row-stochastic matrices p(M:m) = plM) ... p(m), easy to verify the following element-wise inequality:
M
a ob) p(M.m) Sow Qm,M Sew p(M:m)
1=
which together with (T0) leads to
(1 r/ ) ((Mmm) Sew Qm.M Sow p(Mam).
(11)
Therefore,
BBQ M a0 = |IB(Qm, p(M:m)) + BP(M.))
B( p(Mmm)) )l (Pamm)) (Mm)
[[ p(dr:m)))l
< 0lQ plMmm) 1000
$ v/ Bocc
< <n'VN,
where the last inequality is due the fact that ||l|| By definition, Qo.M Qm, and hence
BBQ 1ls < [BQm, ssloo 110m..mma S |BQm,.M lloc S V/V
(12)
The above inequality (12) holds when taking M + oc. Then taking 17 - implies T/ 0 and together with (12). we conclude that
lim BBQo O, M+0
'Choose, e.g.. b log
18

---

and therefore,
lim BQ 0. M +000
E.3 Proof of Lemma 5
Notice that both cases = and 3 > 0 in Lemma imply the ergodicity of (D(!) p(0)p |t-0 Hence the statement is a direct corollary of Lemma
1t=0
G Proof of Lemma 6
In order to show that JS.( 1, start by making the following observation.
Lemma 11. A sequence [P(n)] In=o ergodic and only if IT p(m) converges the matrix.
Proof. For any t N2o, it follows from the third property of the orthogonal projection B (see, Page of the main paper) that
B
II p()
II n=0
M
Hence
1 is ergodic
lim B p(n)
n=0
lim
p(n) B
lim
p(n) 0.
Next, we utilize the following result, as a means to ensure joint spectral radius strictly less than for a bounded set of matrices.
Lemma 12 (Proposition 3.2 in 35
For any bounded set of matrices M, JSR(M) < 1 if and only for any sequence [M(")) j in M, Ih M(a) converges to the zero matrix.
Here, "bounded" means that there exists upper bound on the norms of the matrices in the set. Note that Pg.c is bounded because || 1, for all P E .Mg.e. To show that Pg.c is also bounded, let P. E Pg.c, then by definition, have
PB = B Mg.e = P= BPB
since BBT = IN-1- As result,
||||| |BB 2 Σ |||| $ VN. where the first inequality is due to B|| 2 || =
B ||2 and the second ineuality follows from
Combining Lemma Lemma 11 and Lemma
12 we conclude that JSR(Pg..) <
H Proof of Lemma 7
Note that any sequence (0) implies that for any sequence (M joo in Mg.e.5 we have
In in Mg.e,5 satisfies B = 0, where 3 is defined in Lemma 4 This
lim
II (²) 0.
E-000
n=D
19

---

Since M I for all M .M..e.o. again by Lemma 12 we conclude that JSR(Mg.e.)
< 1.
I Proof of Theorem 1
Recall the formulation of X (++1) in 7
x(++1) = (((00
ii
w/( Jeses1
plo) p(o)x
jei= [ee
\==
Then the first part of the theorem directly follows from Lemma
5
To derive the exponential convergence rate, consider the linear and nonlinear cases separately:
I.1 Bounds for the two cases
[Case: linear] In the linear case where all IN, follows from Lemma that
ji kim0
B (xx(+))) 12
Σ
BP(O... p(0) (0)
Jajei1
=
Σ
i A==
W(h))
Bpll) [pp)) x(()
Jesn+t
2
Σ
(()
|| plo... ((0)
Bxx(0)
Jesett
-0
11-1 Jo)
A==0
Σ
II k=
Cap-1
Bx
Jesett)
50
Σ
W II A==
(egg C' |[ Dall.
(13)
where C' Cmax
B. (0) ( l|2 and || denotes the 1-norm. Specifically, the first inequality follows
jE
from the triangle inequality, and the second inequality is due to the property of the joint spectral radius in 8). where JSR((G.)) <
[Case: nonlinear] Consider T N defined in Lemma 10 where there exists N20 and
a2 [K - 1] such that T K + 02. Given the condition (x), and Lemma 10 there exists
0 < 1 such that for all m E N
1mQ mK Km +T I (1-c5'))
where 8' Note that since for all nm, m E N20, 02 + 1mm S 2K, we get that
nm T < (a1 + 2)K.
Since for all m E Noo-
S (1--88),
it implies that for all Nzo.
a(a++2)K
12 S (1--6"') = ((1 -od n
(1 co io 12 x(a1+2)K
20

---

Denote Q = co') lo = By the equivalence of norms, we get that for all Nzo.
(0om(or+2)Kll S VNqu(an
Then for any j E (0} U [(a + 2 1].
[Qum(ar+2) VNgg' Ngg'gn(e:t2)+ & 22)
where C= VNq (a1 k Rewriting the indices, we conclude that
[Qozel2 s Cy' AI 0. The above bound implies that for any q satisfies S < 1,
i
fi jesks1
1BX(+1)) 2
Σ
BD p(o) p(o...D.0 Jet1
x
ji
K==
Σ
II km=
(D( 2e12
p(t) D (0)
p())
x
(0)
21
Jet1 =1, (0)
Σ
II A==
w
| p(t) ... p(o)
111 ( JoE/dd--
ji /w/S3
jasess) 1))
S C'
(14)
where again, C' Cmax BX (0)
1l.
jE(d]
1.2 Proof of the exponential convergence
Based on the inequality extablished for both linear and nonlinear case in 13 and 14). we derive the
rest of the proof. Since || || if x 1 0 for E RN, also have that if X 1 0 for
X E IR Nxd then
|BX = |
using which obtain that
= 17x411 - |BX 1
|BX (Bx((+1)
112
S C4
Σ I(W.0)).....0.)).....
C'' [|(())
I1aa,
where || ||,,1 denotes the matrix (1, norm (recall from Section A.2 that for matrix M mmxn we have || = Em Ez=1 [Ma)). (). The assumption A3 implics that there exists O" such that for all E Noo.
(.. dd
21

---

Thus we conclude that there exists C1 such that for all E N20.
p(X(() S Cig'
Remark 3. Similar the linear case, one can also use Lemma establish exponential rate for oversmoothing when dealing with nonlinearities for which Assumption holds in the strict sense, i.e. 0 a(a) < 1 (e.g., GELU and SiLU nonlinearities). Here, we presented alternative proof requiring weaker conditions, making the result directly applicable to nonlinearities such as ReLU and Leaky ReLU.
J Proof of Proposition 2
Since Dagg is similar to Dágg AD deg they have the same spectrum. For D A, the smallest nonzero entry has value 1/dmaxx where dmax is the maximum node degree in g. On the other hand, follows from the definition of Pg.e that
edmax I 1.
Therefore, I 1/dmax and thus Deeg Pgg..
We proceed by proving the following result. Lemma 13. For any M in M, the spectral radius of M denoted by p(M), satisfies
P(M) S JSR(M).
where the quantity is independent the norm used [22] Then comparing with the definition of the joint spectral radius, we can immediately conclude the statement.
Proof. Gelfand's formula states that p(M) = lim ||M* |M | A0
Let A) = PB. By definition, P Ps.c since D E Ps.c as shown before the lemma. Moreover, the spectrum of is the spectrum of Ddeg A after reducing the multiplicity of eigenvalue 1 by one. Under the assumption A1, the eigenvalue 1 of D A has multiplicity 1, and hence p(P) X. where the second largest eigenvalue deg A. Putting this together with Lemma 13 we conclude that
A < (S.(
as desired.
K
Numerical Experiments
Here we provide more details on the numerical experiments presented Section All models were implemented with PyTorch [27] and PyTorch Geometric [10].
Datasets
We used torch waarch_gemmerrii geometrric.daassees planetoid provided in PyTorch Geometric for the three homophilic datasets: Cora, CiteSeer, and PubMed with their default training and test splits.
daeamttrcc..aaasetts We used torch_ hrrrchhgemetricc..ooo datasets WebKB provided in Py PyTorch Geometric for the three heterophilic datasets: Cornell, Texas, and Wisconsin with their default training and test splits.
Dataset summary statistics are presented in Table
Model details
For GAT, we consider the architecture proposed in Veličković et al. [88 with each attentional layer sharing the parameter Leaky [[T X:I[WT X,)), RR2d to compute the attention scores.
22

---

Dataset
Type
# Nodees
%Nodes in LCC
Cora
2,708
91.8 %
CiteSeer
homophilic
3,327
63.7 %
PubMed
19,717
100
Cornell
183
100 %
Texas
heterophilic
183
100 %
Wisconsin
251
100 %
Flickr
large-scale
89,250
100 %
Table 1:
Dataset summary statisties. LCC: Largest connected component.
For GCN, we consider the standard random walk graph convolution D A. That is, the update rulc of each graph convolutional layer can be written as
= D AXW, where X and X' are the input and output node representations, respectively, and W is the shared learnable weight matrix in the layer.
Compute We trained all of our models on Telsa V100 GPU.
Training details all experiments, we used the Adam optimizer using learning of 0.00001 and 0.0005 weight decay and trained for 1000 epoch
Results large-scale dataset In addition to the numerical results presented in Sec-
we also conducted the same experiment on large-scale dataset Flickr [46 using torch_geometric.. datassetssstsesss...mm Flickr. Figure visualizes the results.
tion S
Flickr GAT
Flickr GCN
ReLU
10a
LeakyReLU (0.01)
LeakyReLU (0.4)
LeakyReLU (0.8)
μ00
GELU
10
10
10-1
10-1
10-1
10-2
number layers
number layers
Figure 2: Evolution of (9)) (in log-log scale) on the largest connected component of the large-
scale benchmark dataset: Flickr.
23


Reviews:
[{"review_id": "sl6wDqPfFr", "reviewer": "Reviewer_QRK7", "summary": "The paper addresses the question of whether graph attention mechanism could prevent oversmoothing in Graph Neural Networks (GNN) and provides a negative result. Existing results on graph attention are available for 1-layer GNN. The current work analyzes the general case of multi-layered graph attention in the context of nonlinear, time-varying dynamical systems. Through a nicely presented rigorous theoretical analysis, the paper shows that (1) oversmoothing happens even for multi-layered attention based GNN (hence attention based mechanisms fundamentally does not change the aggregator operator) (2) oversmoothing happens at exponential rate and the analysis can be also generalized to GCNs. The numerical experiments demonstrate the validation of the claims made in the paper. The presented analysis could be useful in understanding other aspects of graph attention.", "questions": "Q1. Typo: The sub-indices for $W^{(k)}$ in recursive formulation of *Eq (6)* is flipped and should be - $j_k, j_{k+1}$ instead of $j_{k+1}, j_k$. This would match those in *Eq 5* case $W_{ji}^{(t)}$ for $j_{k+1}=i$. Same goes for the supplement. Please check that the proof that The proof the follows is alright.\n\nQ2. In lines $286.287$, how is the existence of $q<1$ justified? I understand that this is an assumption in the *Theorem 1*, but could the authors shed light on nature of values $q$ takes since it dictates the convergence.\n", "limitations": "None", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper addresses an important question of oversmoothing in multi-layered graph attention neural networks. It is very well written and the ideas across different sections are nicely connected. There is ample amount of intuition behind choice of various techniques used in the paper and the theorems/lemmas are well explained.\n\n2. The ideas/techniques introduced in the paper are well developed, original and should be useful in understanding other aspects of attention based GNNs. I like that the authors provide remarks (lines 257) which address how the paper differs from previous techniques used in theoretical analysis of graph attention. \n\n3. The results of the paper are of significance in understanding of GNNs in terms of developing an understanding of trajectory of matrices in graph attention and hence indirectly supporting methods like edge-dropping etc.", "weaknesses": "1. Some of the prior work on reducing oversmoothing [1] and impact of the current work for understanding them could be included as limitation for the current work. It would be great if authors could talk about if some of the techniques developed here applies to them.\n\n[1]  Chen, Deli, et al. \"Measuring and relieving the over-smoothing problem for graph neural networks from the topological view.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 04. 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful comments and positive assessment of our work. After carefully reviewing your feedback, below we provide answers to the comments you raised.\n\n**Q1: Some of the prior work on reducing oversmoothing [1] and impact of the current work for understanding them could be included as limitations for the current work. It would be great if authors could talk about if some of the techniques developed here apply to them.**\n\nThis is an interesting point and is closely related to the discussion right after Theorem 1 (line 297-303). Based on our proof, a key property leading to oversmoothing is that the graph structure does not change across different layers. Our theory hence indirectly endorses empirical strategies such as edge-dropping or graph-rewiring, which modify the graph's connectivity structure to alleviate oversmoothing. In particular, AdaEdge proposed in [1] is a graph rewiring method.\n\n\n**Q2: Typo: The sub-indices for $W^{(k)}$ in recursive formulation of Eq (6) is flipped and should be $j_{k},j_{k+1}$ instead of $j_{k+1},j_{k}$. This would match those in Eq 5 case $W_{ji}^{(t)}$ for $j_{k+1}=i$. Same goes for the supplement. Please check that the proof follows is alright.**\n\nThanks for the good catch! Indeed, the indices are flipped and it should be $W_{j_kj_{k+1}}$ instead. We verified that the rest of the proof had no issues.                                                                                                                                                    \n\n**Q3: In lines 286-287, how is the existence of $q<1$ justified? I understand that this is an assumption in Theorem 1, but could the authors shed light on the nature of values $q$ takes since it dictates the convergence.**\n\nThank you for the question. \n- We note that $q$ is an arbitrary constant between $JSR(\\tilde{\\mathcal{M}}\\_{\\mathcal{G},\\epsilon})$ and 1, which is guaranteed to exist by Lemma 6. The convergence rate dictated by $q$ (as mentioned by the reviewer) is thus determined by the joint spectral radius of the matrix set $\\tilde{\\mathcal{M}}\\_{\\mathcal{G},\\epsilon}$. \n- However, as we explain in the paper (lines 305-306), computing or approximating the joint spectral radius for a given set of matrices is known to be hard in general [2]. It is thus insightful to derive bounds on the joint spectral radius. This is done in Proposition 2 in the paper, where we show that  $JSR(\\tilde{\\mathcal{M}}\\_{\\mathcal{G},\\epsilon})$ is lower-bounded by the second largest eigenvalue of the normalized adjacency matrix ($D_{\\deg}^{-1/2}AD_{\\deg}^{-1/2}$).\n\nWe appreciate your questions and comments very much. Please let us know for any further questions.\n\n---\n**References**\n\n[1] Chen et al.. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In AAAI 2020.\n\n[2] John Tsitsiklis and Vincent Blondel. The Lyapunov exponent and joint spectral radius of pairs of matrices are hard – when not impossible – to compute and to approximate. Mathematics of Control, Signals and Systems, 1997.\n\n\n\n"}, {"review_id": "lLASsFMgNs", "reviewer": "Reviewer_Ac2q", "summary": "This paper provides a definitive answer to the question that whether the graph attention mechanism can mitigate over-smoothing through a rigorous mathematical analysis. The theoretical results establish that the graph attention mechanism cannot prevent over-smoothing and loses expressive power exponentially. ", "questions": "1.Missing a number of reliable literature support the claim of attention-based GNNs' ability to alleviate the over-smoothing problem, and most of the works listed in this paper suggest that attention-based GNNs suffer from over-smoothing. This is insufficient to support the author's argument that there is controversial whether the graph attention mechanism can mitigate over-smoothing.\n\n2.What criteria were used to select the negative slope values in the experiment?\n\n3.How sensitive are the hyperparameters (e.g. negative slope values) to the performance?", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. Exploring theoretical results on the performance of attention-based GNNs on over-smoothing problems is meaningful and challenging.\n\nS2. The theoretical results obtained in this paper can provide some instructive and valuable information on over-smoothing research.", "weaknesses": "Reliability \n1. The reliability of the motivation can be enhanced by adding more literature that discusses the controversy surrounding whether attention-based GNNs alleviate the over-smoothing problem.\n\nSignificance\n1. Only homophily graphs are considered in the paper. In addition, heterophily datasets also should be considered to verify the overall performance of GNN as pointed out by recent publications [1,2].\n2. In addition, experiments on larger datasets will strengthen the significance of the contributions.\n\n[1]Pei, H., Wei, B., Chang, K. C. C., Lei, Y., & Yang, B. (2020). Geom-GCN: Geometric graph convolutional networks. In ICLR.\n\n[2]Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., & Lim, S. N. (2021). Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In NeurIPS, 34, 20887-20902.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper and providing constructive feedback. In line with the reviewer’s suggestion, we have performed additional numerical experiments, validating our theoretical findings on three heterophily datasets (Cornell, Texas and Wisconsin [1]) and a large-scale dataset  (Flickr [2]). The results are provided in the rebuttal pdf file. In what follows, we provide detailed responses to the comments raised by the reviewer.\n\n**Q1: Missing a number of reliable literature support the claim of attention-based GNNs' ability to alleviate the over-smoothing problem, and most of the works listed in this paper suggest that attention-based GNNs suffer from over-smoothing. This is insufficient to support the author's argument that there is controversial whether the graph attention mechanism can mitigate over-smoothing. The reliability of the motivation can be enhanced by adding more literature that discusses the controversy surrounding whether attention-based GNNs alleviate the over-smoothing problem.**\n\nThank you for the comment. We would like to clarify that by \"controversy\" here, we mean it is still an “open question” (especially from a *theoretical* perspective) whether graph attention mechanisms can mitigate oversmoothing [3,4]. For example, Min et al. [5] directly claim that “GAT network typically alleviates oversmoothing using graph attention mechanisms,” while oversmoothing in attention-based GNNs has been observed empirically in some other works [6]. As also pointed out by the reviewer, “exploring theoretical results on the performance of attention-based GNNs on oversmoothing problems is meaningful and challenging.” Our paper fills the gap in the existing theoretical literature by providing a definitive answer to the question whether the graph attention mechanism can mitigate over-smoothing through a rigorous mathematical analysis.\n\n**Q2. Only homophily graphs are considered in the paper. In addition, heterophily datasets also should be considered to verify the overall performance of GNN as pointed out by recent publications. In addition, experiments on larger datasets will strengthen the significance of the contributions.**\n\nThank you for your constructive suggestion. In line with the reviewer’s suggestion, we validate our theoretical findings on three heterophily datasets (Cornell, Texas and Wisconsin [1]) and a large-scaler dataset (Flickr [2]). The results are provided in the rebuttal pdf file.\n\nOur theoretical results are developed for generic graphs and thus hold for datasets exhibiting either homophily or heterophily and even those that are not necessarily either of the two. \n\n**Q3: What criteria were used to select the negative slope values in the experiment?**\n\nThank you for the question. For LeakyReLU, the negative slope value can be selected within the range of 0 to 1, and the default value is 0.01. To illustrate its effects across various scenarios, we consider three distinct representative values: 0.01 for a small slope, 0.4 for a medium slope, and 0.8 for a large slope.\n\n**Q4: How sensitive are the hyperparameters (e.g. negative slope values) to the performance?**\n\nThank you for the question. The sensitivity can be directly observed from Figure 1 in the paper, where for all negative slope values, oversmoothing persists and happens exponentially, although the degree of oversmoothing varies for different choices of nonlinearities.\n\nWe appreciate your questions and comments very much. Please let us know for any further questions.\n\n---\n**References**\n\n[1] Pei et al.. Geom-GCN: Geometric Graph Convolutional Networks. In ICLR 2020.\n\n[2] Zeng et al.. GraphSAINT: Graph Sampling Based Inductive Learning Method. In ICLR 2020.\n\n[3] Kenta Oono and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In ICLR 2020.\n\n[4] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. In ICML Graph Representation Learning and Beyond (GRL+) Workshop, 2020.\n\n[5] Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering GCN: Overcoming oversmoothness in graph convolutional networks. In NeurIPS 2020.\n\n[6] Rusch et al.. Graph-coupled oscillator networks. In ICML 2022.\n\n\n\n\n\n\n"}, {"review_id": "Q8xc67aksC", "reviewer": "Reviewer_DswA", "summary": "The objective of this paper is to examine the occurrence of over-smoothing phenomena in attention-based Graph Neural Networks (GNN). Over-smoothing refers to a situation where deepening the network results in similar node representations. The researchers demonstrate the presence of over-smoothing in attention-based GNNs using a versatile methodology that can be applied to various GNN types. They establish this proof by treating the network as a nonlinear and time-varying dynamical system. Moreover, the authors support their assertions with empirical evidence.", "questions": "* Is it possible to extend the over-smoothing to any node similarity measure as defined in Definition 1 ?\n* Is it possible to directly expand the results from the paper to transformer-based GNNs? What is possible to say about the existence of over-smoothing in that case?\n", "limitations": "There is no evidence of ethical problems with this submission.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper exhibits excellent writing quality, as it effectively communicates the author's intentions even when dealing with complex mathematical concepts. The clarity of the paper makes it easily comprehensible for readers.\n\n* The theoretical claims are clear and the proofs are valid.\n\n* The authors propose a generic approach to examine over-smoothing in GNNs with non-restrictive conditions. While their main focus is on attention-based models, the results include a wider range of models.\n", "weaknesses": "* The main shortcoming of the paper is the lack of suggestions for solving the over-smoothing problem. [1] suggests scaling to avoid the phenomena, are they any other ways to alleviate the problem? \n\n[1] Oono et al. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification, ICLR (2020)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your positive assessment and insightful comments, which have helped strengthen our work. Below, we provide individual responses to your questions.\n\n**Q1: The main shortcoming of the paper is the lack of suggestions for solving the over-smoothing problem. [1] suggests scaling to avoid the phenomena, are there any other ways to alleviate the problem?**\n\nThank you for the comment. As our discussion following Theorem 1 (lines 297-303) reveals, a pivotal factor contributing to oversmoothing is the invariance of the graph structure across different layers. This supports the empirical approaches to mitigate oversmoothing in the existing literature such as edge-dropping or graph-rewiring (citations provided in the paper), as they modify the connectivity pattern of the graph. \n\n**Q2: Is it possible to extend the over-smoothing to any node similarity measure as defined in Definition 1?**\n\nThis is a very good question and helps us strengthen our theoretical results. In fact, our analysis directly applies to any Lipschitz node similarity measure $\\mu$. To see this, observe that for a node similarity measure $\\mu$ with a Lipschitz constant $C$, we have $\\mu(X) =  \\|\\mu(X) - \\mu(1\\_{\\gamma\\_X})\\| \\leq C ||X - 1\\_{\\gamma\\_X}||_F$, where $||X - 1\\_{\\gamma\\_X}||_F$ is the node similarity measure considered in this work. \n\n**Q3: Is it possible to directly expand the results from the paper to transformer-based GNNs? What is possible to say about the existence of over-smoothing in that case?**\n\nThis is again a great question. In fact, one can view the self-attention dynamics in transformers as a special class of attention-based GNNs operating on complete graphs. Then our results would directly apply to transformer-based GNNs under similar assumptions to A2-A4.\n\nWe appreciate your questions and comments very much. Please let us know if there are any further questions.\n\n---\n**References**\n\n[1] Oono and Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. In ICLR 2020.\n\n"}, {"review_id": "sSqhiAOpsV", "reviewer": "Reviewer_UfCo", "summary": "The authors provide theoretical proofs on the oversmoothing problem in GCNs and GATs through Ergodicity analysis of infinite product of matrices. The authors provide a bound in convergence of oversmoothing problem and provides suggestions on choices in activation function to relief oversmoothing problem.", "questions": "- If we break the assumption A4 by using a $\\sigma(x)/x >1$, or $\\sigma(0)\\neq 0$, does GNNs stop having oversmoothing issues or will there be other problems?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- Approaching oversmoothing problem with Ergodicity is fairly new\n- Implications on choices of activation functions are straight forward\n- The article is very easy to follow", "weaknesses": "- It would be better if the authors could add a experiment with a plot directly showing JSR", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your constructive feedback and positive assessment of our work. Below, we provide individual responses to your questions.\n\n**Q1: It would be better if the authors could add a experiment with a plot directly showing JSR.**\n\nThank you for the comment. As mentioned in the paper (line 305-306),  computing or approximating the joint spectral radius for a given set of matrices is in fact an NP-hard problem in general [1]. However, using the proof techniques we develop in the paper, we show that the joint spectral radius of the set of matrices $\\tilde{\\mathcal{M}}\\_{\\mathcal{G},\\epsilon}$ is strictly less than 1, from which we then derive our oversmoothing results. \n\n**Q2: If we break the assumption A4 by using $\\sigma(x)/x > 1$ or $\\sigma(0) \\neq 0$, does GNNs stop having oversmoothing issues or will there be other problems?**\n\nThis is a great follow-up research question that we are currently investigating. \n\n- We conjecture that choosing a nonlinearity with $\\sigma(x)/x>1$ may enable us to break the invariance of the graph structure across layers in the limit (which was the key cause for oversmoothing in our analysis). The idea is that such a $\\sigma(\\cdot)$ may lead to unbounded raw attention scores in the limit. When normalized by softmax, this can result in zero attention coefficient, which is equivalent to edge-dropping. \n\n- There will be both cons and pros for such a choice: while having several disconnected components can potentially lead to a much richer structure for the limit points of the trajectories, allowing for large outputs may lead to optimization issues in training.  \n\nWe appreciate your questions and comments very much. Please let us know for any further questions.\n\n---\n**References**\n\n[1] John Tsitsiklis and Vincent Blondel. The Lyapunov exponent and joint spectral radius of pairs of matrices are hard – when not impossible – to compute and to approximate. Mathematics of Control, Signals and Systems, 1997.\n\n\n"}]

Author rebuttal:

We would like to thank the reviewers for carefully reading our paper and giving insightful comments. We have provided detailed responses to each of the reviews separately. 

In the rebuttal pdf file, we also provide additional numerical results under the same experimental setup as in our paper. Specifically, we validate our theoretical findings on three heterophily datasets (Cornell, Texas and Wisconsin [1]) and a large-scale dataset (Flickr [2]), as suggested by one of the reviewers.

The authors


---
**References**

[1] Pei et al.. Geom-GCN: Geometric Graph Convolutional Networks. In ICLR 2020.

[2] Zeng et al.. GraphSAINT: Graph Sampling Based Inductive Learning Method. In ICLR 2020.




Meta-review: The paper shows that contrary to popular belief, the graph attention mechanism cannot prevent oversmoothing and loses expressive power exponentially. Reviewers have noted the paper's great writing and the well-elaborated and innovative concepts and techniques it presents. The findings in the paper have substantial implications for advancing the understanding of GNNs and offer instructive and valuable insights into research on oversmoothing.
Decision: Accept (spotlight)