Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models
Authors: Zhongtian Ma
Qiaosheng Zhang
Bocheng Zhou
Yexin Zhang
Shuyue Hu
Zhen Wang
Venue: ICML 2025 poster (2025)
Keywords: graph attention mechanisms
node classification
contextual stochastic block models
over-smoothing
graph convolution
perfect node classification
Primary area: theory->learning_theory

Abstract: Despite the growing popularity of graph attention mechanisms, their theoretical understanding remains limited. This paper aims to explore the conditions under which these mechanisms are effective in node classification tasks through the lens of Contextual Stochastic Block Models (CSBMs). Our theoretical analysis reveals that incorporating graph attention mechanisms is *not universally beneficial*. Specifically, by appropriately defining *structure noise* and *feature noise* in graphs, we show that graph attention mechanisms can enhance classification performance when structure noise exceeds feature noise. Conversely, when feature noise predominates, simpler graph convolution operations are more effective. Furthermore, we examine the over-smoothing phenomenon and show that, in the high signal-to-noise ratio (SNR) regime, graph convolutional networks suffer from over-smoothing, whereas graph attention mechanisms can effectively resolve this issue. Building on these insights, we propose a novel multi-layer Graph Attention Network (GAT) architecture that significantly outperforms single-layer GATs in achieving *perfect node classification* in CSBMs, relaxing the SNR requirement from $\omega(\sqrt{\log n})$ to $\omega(\sqrt{\log n} / \sqrt[3]{n})$. To our knowledge, this is the first study to delineate the conditions for perfect node classification using multi-layer GATs. Our theoretical contributions are corroborated by extensive experiments on both synthetic and real-world datasets, highlighting the practical implications of our findings.

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models
Zhongtian Ma
Qiaosheng Zhang?2 Bocheng Zhou Yexin Zhang
Shuyue Hu Zhen Wang'
Abstract
1. Introduction
Despite the growing popularity of graph attention mechanisms, their theoretical understanding re- mains limited. This paper aims to explore the con- ditions under which these mechanisms are effec- tive in node classification tasks through the lens of Contextual Stochastic Block Models (CSBMs). Our theoretical analysis reveals that incorporat- ing graph attention mechanisms is not universally beneficial. Specifically, by appropriately defin- ing structure noise and feature noise in graphs, we show that graph attention mechanisms can en- hance classification performance when structure noise exceeds feature noise. Conversely, when feature noise predominates, simpler graph convo- lution operations are more effective. Furthermore, we examine the over- smoothing phenomenon and show that, in the high signal-to-note ratio (SNR) regime, graph convolutional networks suffer from over-smoothing. whereas graph attention mecha- nisms can effectively resolve this issue. Building these insights, we propose novel multi-layer Graph Attention Network (GAT) architecture that significantly outperforms single-layer GATs in achieving perfect node classification in CSBMs, relaxing the SNR requirement from w( (Vlog n) to w( (Vog n/ Vn) To our knowledge, this the first study to delineate the conditions for perfect node classification using multi-layer GATs. Our theoretical contributions corroborated by ex- tensive experiments on both synthetic and real- world datasets, highlighting the practical implica- tions of our findings.
Graph Neural Networks (GNNs) have become essential tools for analyzing graph-structured data, with applications in social networks (Fan et al., 2019), biology (Gligorijevié et al., 2021), computer vision (Ma et al., 2022) and recom- mendation systems (Wu et al., 2020; 2022a). A founda- tional approach within GNNs is the Graph Convolutional Network (GCN) (Kipf & Welling, 2022), which aggregates information from a node's neighbors to generate feature representations. Building on GCNs, Graph Attention Net- works (GATs) (Veličković al., 2018) introduce the graph attention mechanism that dynamically assigns weights to neighboring nodes based on the similarity of their features, thereby enhancing performance by prioritizing the most relevant information.
Despite the growing interest in graph attention mecha- nisms (Wang al., 2019c; Lee et al., 2019; Wang al., 2019a;;; Hu et al., 2020), the understanding of when and why they are effective remains limited. While these mecha- nisms are designed to prioritize relevant nodes in a graph, their effectiveness appears to be highly influenced by the graph's 's properties. particularly in the presence of noise. The graph data commonly used in contemporary tasks featured graph, containing both topological and node fea- ture information. Consequently, two types of noise emerge: structure noise and feature noise. Structure noise disrupts graph connections, complicating the accurate identification of community structures. Feature noise refers to inaccura- cies in node feature information, such as imprecise values or excessive similarity among features of different nodes, which can lead to incorrect classifications (Yang et al., 2024). Given that both types of noise have the potential to affect the performance of attention mechanisms, critical ques- tion arises: What factors influence the effectiveness of graph attention mechanisms, and how do structure noise and feature noise impact their performance in different scenarios?
Northhesterm Polytechnical University Shanghaai Ar- tificial Intelligence Laboratory 'Shanghai Innovation Insti- tute 'Shanghai Jiao Tong University. Correspondence to: Zhen Wang <w-zhen & nwpu.edu.cn>, Qiaosheng Zhang <zhanggiaosheng ceapgiaasssengjpabooor...ooomm pjg.b.org.cn...
This paper addresses this question by providing an in- depth theoretical analysis of the graph attention mecha- nism. We employ the Contextual Stochastic Block Model (CSBM) (Deshpande et al., 2018). commonly used tool for simulating graph structures and node features to model real
Proceedings of the 4nnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'The source code for this article is available on https:// github com/ mttp/t////ttt BaTm////AATTTAA....AA _SBBM.

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
graph data. In the CSBM, the graph structure is generated using the well-known Stochastic Block Model (SBM) (Hol- land et al., 1983)-a random graph model that consists of community structures, while the node features are generated through a Gaussian Mixture Model (GMM) (Reynolds et al., 2009). A key focus in the CSBM is the signal-to-noise ratio (SNR) of the node features, linked to the mean and variance parameters of the GMM. A higher SNR indicates greater dis- tinguishability of the node features. By utilizing the CSBM, we can precisely control levels of structure noise and feature noise relates
by the CSBM, the graph attention mechanism is able to resolve the over-smoothing issue in the high SNR regime (see Theorem 3).
.
Building on our analysis of the graph attention mecha- nism, we design an effective multi-layer GAT and demon- strate that it significantly outperforms the single-layer GAT in achieving perfect node classification (see Defi- nition 1). Specifically, the requirement relaxed from SNR- w(Vlog n) stated in (Fountoulakis et al., 2023), SNR= w(v w(Vlog ni/ Vn) (see Theorem 4). To our knowledge. this is the first study to examine the con- ditions for perfect node classification with multi-layer GATs.
noise by tuning model to connection probabilities between different communities in the SBM, while feature noise is defined as the inverse of the SNR?. Moreover, we use node classification, fun- damental task in graph learning that is widely employed to explore GNN properties (Baranwal et al., 2023; Wei al., 2022), as a benchmark to assess the effectiveness of graph attention mechanisms across different levels of structure and feature noise.
We conduct extensive experiments on synthetic datasets, as well as on three widely used real-world datasets, to validate our theoretical findings.
1.1. Related Works
Through our investigation, we provide a clear understanding of how graph attention mechanisms can be leveraged more effectively, and identify scenarios where simpler GCNs may provide better performance. By rigorously analyzing the impact of graph attention in the context of CSBM, this paper not only advances theoretical understandings but also pro- vides valuable insights for practical applications in various domains. Our main contributions are as follows:
In recent years, there has been growing interest in the theoretical analysis of GNNs, particularly using the CS- BMs (Baranwal et al., 2021; 2023; Luan et al., 2023; Adam- Day et al., 2024; Wang et al., 2024; Javaloy et al., 2023). Among these works, the two most relevant to our study are (Fountoulakis et al., 2023; Javaloy et al., 2023), whose settings are partially adopted in our work. Fountoulakis et al. (2023) primarily investigate the role of graph atten- tion mechanisms in the presence of structural noise, where the graph itself provides limited information. They are the first to establish the feasible region for achieving perfect node classification using a single-layer GAT. Motivated by similar challenges. Javaloy et al. (2023) propose learn- able GAT, termed L-CAT, which combines the strengths of GCNs and GATs to address cases where GATs may not al always outperform GCNs. Our work broadens this perspec- tive by analyzing the effects of both structural and feature noise on graph attention mechanisms. We identify the pre- cise regimes where GCNs or GAT's perform better, extend the feasible region for perfect node classification to multi- layer GAT's, and achieve improved results on sparse graphs compared to Javaloy et al. (2023).
Main Contributions
Inspired by (Fountoulakis et al., 2023), we design a non- linear graph attention mechanism and show that its effec- tiveness comparable to the mechanism in (Fountoulakis et al., 2023), while being simpler and easier to analyze (Theorem 1). Then, by analyzing the changes in SNR af- ter applying graph attention layers (Theorem 2), we show that the graph attention mechanism is not always effec- tive. Specifically, when the structure noise of the graph exceeds the feature noise, incorporating graph attention is beneficial, with higher attention intensity yielding better results. Conversely, when the feature noise of the nodes is greater than the structure noise, using graph attention can degrade node classification performance. In such cases, a simple graph convolution is more effective (see Section 3.2.1 for details).
The issue of over-smoothing in GNNs has also garnered extensive attention (Xu et al., 2018; Keriven, 2022; Liu et al., 2020; Yang et al., 2020; Zhao & Akoglu, 2020). Two closely related works are (Wu et al., 2022b; 2024), both of which theoretically explore the over-smoothing problem in GNNs. Wu et al. (2022b) analyzes how the SNR evolves through GCN layers within the CSBM frame- work, showing that GCNs experience over-smoothing after Ologn (gg(log)) layers. In (Wu et al., 2024), the au- thors examine the impact of the graph attention mechanism on smoothig and concludes that it does not resolve the issue. In contrast, this paper investigates the effect of
We investigate the impact of the graph attention mecha- nism on the over-smoothing problem. First, we introduce refined definition of over-smoo in an asymptotic setting where the number of nodes n approaches infinity, highlighting its occurrence when the network depth is (n). We then show that for featured graphs generated
We refer readers to Eqn. 2 for detailed definitions of structure noise, feature noise, and SNR.
2

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
the graph attention mechanism on over-smoothing within the CSBM framework, demonstrating that under suitable conditions, a well-designed GAT can avoid over-smoothing for up to (n) layers.
(A, X) CSBM(p, 9. J4, σ) denote the featured graph sam- pled from the above CSBM.
2.2. Graph Convolution and Graph Attention Mecha- nism
Finally, research on community detection within SBMs is also pertinent to our study (Abbe, 2018; Abbe & Sandon, 2015; Zhang & Zhou, 2016; Zhang & Tan, 2022; Chen et al., 2020). Specifically, the problem of community detection in CSBMs has recently attracted considerable attention from statisticians, including investigations into thresholds for ex- act and almost exact recovery and algorithm design (Lu & Sen, 2023; Deshpande et al., 2018; Braun et al., 2022; Duranthon& & Zdeborova, 2024; Dreveton et al., 2024). The node perfect classification problem examined in this pa- per is analogous to performing exact node recovery in the community detection problem.
The following provides an overview of graph convolution operations and graph attention mechanisms in their general form. We then detail the multi-layer GAT for CSBMs, where each layer consists of simplified graph convolution layer combined with an attention mechanism.
Graph convolution operation: For a node i E [n]] with feature X; E R4, the output feature X after one layer of graph convolution is given by: X = a Ejenn Axd)) where di (Eietn) Ar)- Here, O E Rd''d is a learnable matrix, and a(-) repre- sents a non-linear activation function.
2. Preliminaries and Problem Setup
Notations: For any positive integer o, let [a] A
{1, aJ. For an undirected graph G with n nodes, we use the adjacency matrix A E {0, 1)ax" to represent the graph, such that for any (i.j) E [n] x [m). Ag = if and j are connected, and A.j = 0 otherwise. Besides, we con- sider a featured graph where we use X E Raxd to represent the features for all n nodes, with X; E R 1 xd denoting the feature of node i. When the dimension d (as considered in Section 2.1 and from Section 3 onwards), we use un-bold letters X or X; instead. We use standard asymptotic nota- tions, including O(.), o()) ().)).((). and (()) to describe the limiting behaviour of functions/sequences (Leiserson et al., 2001).
a}.
Graph attention mechanism: Graph attention mecha- nism enables nodes in a graph to focus on relevant edges when aggregating information, based on the similarity be- tween node features. Assuming an edge connects two nodes i and j. and X; and X, are the features of these two nodes, the attention mechanism is defined as: (X XX) a f(W,, WX,), where f Rdd Rd + R and W Rd' xd is another learnable matrix.
For any node i, let M₁ be the set of neighbors of node i. Then, the attention coefficient cij for a node i and its neighbor E Nr is calculated using a softmax function exp(V(X,,X,)
Let I|-II be the Frobenius norm. Let sgn(.) denote to the sign function that maps a number to 1, 0, or based on its sign. Let Φ(-) be the cumulative distribution function of the standard Gaussian distribution. For event A, we denote by 1 { the indicator function,,, which equals if A is true and 0 otherwise
Cjj EKEN, exp xxp(w(XX.Xx)] By substituting Gi for dej. the output after one layer of attention based graph convolution is given by X [yEjn Aija Axj,,X,))
Generalization to multi-layer GAT in the CSBM: The previous discussion explained the standard operation of each GAT layer. However, we make some adjustments for the CSBM-generated data. First, recall from Section 2.1 that we assume each node feature X, E R is -ineimmesi,,nll, thus the learnable matrices e and W are unnecessary. Ad- ditionally, to simplify our analysis, the non-linear activation function a(-) is applied only to the last layer of the multi- layer GAT. Consequently, the output of each GAT layer is X = EjE(n) Xy.
2.1. Contextual Stochastic Block Model (CSBM)
We consider a CSBM with a balanced setting where the n nodes are divided into two classes of approximately equal size. Let f2. ,,, en ~ Bern(1/2) be n independent Bernoulli random variables, and the class assignment is given by Cs = {j [n]] f = k). where k E 1). For pair of nodes i.j in the same class, they are connected with probability p, i.e., Aij ~ Bern(p); for pair of nodes j in different classes, they are connected with probability g, i.e., Aij ~ Bern(q). For simplicity, we assume node features are mee-iimnssional (i.c., d = 1), with X E R" represent- ing the node feature vector of all n nodes and X, denoting the feature of node i. We employ one-dimensional GMM with parameters (H, o) to generate the feature of each node as X,, ((2e, 1)u, o²), and we assume μ > 0. Let
For multi-layer GAT with L > layers, the output feature
"Note that a graph attention mechanism may consist of multiple layers of neural networks. This paper adopts a standardized defini- tion of a GAT layer, as presented here, regardless of the specific attention mechanism employed, to ensure clarity. This definition indicates that each layer in the GAT involves a graph convolution operation that integrates the graph attention mechanism.
3

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
of node at the 1-th layer is given by
dense graphs that cover many practical graph data. The assumption is primarily motivated by the requirements of the proof technique. For sparser graphs, alternative proof techniques would be required.
X
Σ A x and X² =sgn ) (1) jE[N]
Assumption 1. p, S(log" n/n) and p > q-
where X!-² is the output feature of node in the 1)- th layer, and fclj yee,, the attention coefficients of its neighbors derived from the features of the (1 1)-th layers. Here, X! is the final output of this GAT, i... the classification result for node i.
3.1. A Simple Non-linear Graph Attention Mechanism and Its Performance
In this section, we first present a graph attention mechanism inspired by Fountoulakis al. (2023) and then demonstrate that its performance in node classification is comparable to that of the mechanism described in (Fountoulakis et al., 2023), within a single-layer GAT setting.
Remark 1. In a multi-layer GAT, neighbor coefficients vary across layers and depend on the node features of each specific layer, unlike GCNs that merely average neighbor information. Note that Eqn. I illustrates the single-head atlention selting, which is the main focus of this paper.
In the homophilic CSBMs, edges between nodes in the same class, referred to as intra-class edges, should receive higher weights, while edges between nodes in different classes, re- ferred as inter-class edges, should receive lower weights. Therefore, the goal of incorporating graph attention mecha- nisms in CSBMs is to more effectively distinguish between intra-class and inter-class edges. Fountoulakis et al. (2023) framed this as an "XOR" problem and addressed using a two-layer neural network. A detailed description of their attention mechanism is provided in Appendix B. However, their approach is computationally complex and challenging to analyze, particularly for multi-layer GATs. Therefore, we propose a simpler non-linear function to approximate the attention mechanism from (Fountoulakis et al., 2023), as detailed below.
2.3. Perfect Node Classification
This paper considers the node classification problem for CSBMs using multi-layer GATs, with perfect node clas- sification serving the evaluation metric. This metric is equivalent to exact recovery (Abbe et al., 2015) in the com- munity detection literature.
Definition 1 (Perfect node classification). Suppose we have a GAT with L layers. For a given node i, we say that the GAT correctly classifies this node if its output X satisfies X = when i E C₁, and X = -1 when E Co- We say this GAT achieves perfect node classification if correctly classifies all nodes simultaneously with probability at least 1 o-)(1..
Proposed graph attention mechanism: For node and its neighbor j. with X, and X, representing their respective features, the graph attention mechanism used in this paper is defined
3. Main Results
This section presents number of results derived in this paper. We begin by introducing the graph attention mech- anism used and analyzed in our work (Section 3.1). In Section 3.2, we investigate the conditions under which the graph attention mechanism proves effective on node clas- sification task. Next, we delve into the influence of the graph attention mechanism on the over-smog issue in Section 3.3. Following our analysis, we assess the enhance- ments that a well-designed multi-layer GAT can bring to the node classification task compared to a single-layer GAT (see Section 3.4).
0,
V vXX,, X,)
1-t if X, < 0,
(3)
where f > 0 is referred to as the attention intensity. Next, we compare the performance of the two attention mechanisms described above, using perfect node classifica- tion as the evaluation metric and focusing on the single-layer GAT scenario.
Perfect Node Classification for Single-Layer GAT: Sec- tion 3 of (Fountoulakis et al., 2023) demonstrates that the graph attention mechanism proposed their work can achieve perfect node classification when SNR w(Vlog ni), which is referred as the "easy regime". In this study, we are also interested in the influence of SNR node classification when employing our designed at- tention mechanism in Eqn. 3. Pleasingly, we prove that in the aforementioned "easy regime", a single-layer GAT equipped with the attention mechanism in Eqn. 3 is equally capable for perfect node classification. This implies that our
Before diving into the main text, we first define signal-to- noise ratio (SNR), structure noise Spaise. and feature noise Fnoise: as these concepts are essential for the subsequent analysis:
SNR & 1 Spoise
Pp+q 9 p q" Froise A SNR-!_
(2)
Following Fountoulakis et al. (2023), we introduce the following assumption to focus on homophilic, reasonably
4

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
designed attention mechanism is as efficient those intro- duced in (Fountoulakis et al., 2023). The aforementioned result is summarized in Theorem below.
making the analysis non-trivial. To tackle this challenge. we conduct case-by-case examination of the non-linear attention mechanism, calculating expectations and variances for each scenario and aggregating the results (see Appen- dices E and F). The key to these calculations lies in the higher-order moments of the truncated Gaussian distribu- tion (see Lemma 4). Additionally, during the simplification process, we were pleasantly surprised find two seemingly different pairs of sequences whose sums converge to the same limit. We provide proof for this observation, which led to the final expression (see Lemmas 5 and 6).
Theorem 1. For a featured graph X)
CSBM(P, 9, H. suppose that SNR = w( (ollon and that Assumption! is satisfied. Then, employing the graph attention mechanism in Eqn. 3, a single-layer GAT, as specified in Eqn. 1 with L 1, is capable of achieving perfect node classification (i.e., perfectly classifying all nodes with probability at least 1 - o(1))
3.2. When Does Graph Attention Mechanism Help Node Classification?
The following corollary specializes Theorem 1 to several specific parameter regimes.
The previous subsection shows that node classification per- formance is inherently linked to the SNR, while in this subsection we investigate the conditions under which GAT layers can enhance the SNR and when they fail do so. Two type of noises, Suoise and Froise (as defined in Eqn. 2), are considered. Note that Smoise increases as p and q get closer, making the graph less informative. As Fnoise in- creases, the SNR decreases, resulting in less informative node features. The key implications from our findings is that when Sposse exceeds Fuisee. the graph attention mechanism is effective, with higher attention intensity / yielding better performance. Conversely, when Froise predominates and Spoise is relatively low, the graph attention mechanism is less effective, and a high attention intensity may even be detrimental.
For the expectation and variance of X in Theorem 2, the following statements hold,
Corollary 1.
If = O, then μı' = pTg and (a')² n(p+a) 0².
If SNR= w( ww nlg then μ'
pa' qqe pe' rN and (o')2
Mittooo'
1f SNR= 011) and 1= 0(1,, then pl = O (FFg))) and
(o')² = e @(((e( ((e2- m(p-og) - 0²))
Remark 2. In Corollary 1, when t = O. the GAT layer reduces to a simple graph convolution layer. In this case, our conclusions on expectation and variance align with the results in (Wu et al., 2022b).
3.2.1. DISCUSSIONS
Since the SNR correlated with the expectations and variances of the node features, below we first present the changes in the expectations and variances of the node fea- tures after GAT layer (Theorem 2). Before introducing the theorem, we first define N?" as the set of neighbors of node i that are in the same class as node i, and N as the set of neighbors from the different class.
Having obtained the expectation and variance (i.e., p¹ and o') after a GAT layer, we will now discuss the effectiveness of the graph attention mechanism in two distinct cases. No- tably, our goal is to increase the SNR (i.e., increase p²/ /o' compared to μ/o) after applying the GAT layer, as this en- hances node classification performance, which serves the criterion for evaluating the efficacy of the graph attention mechanism.
E C. where X; N((2; - 1)H, o²). let X; represent the node feature after single GAT layer, with E[X]] denoting the expectation of X and Var(X)) denoting the variance. Then, there exist two computable functions F(-) and F(-) such that as n tends to infinity, with probability at least 1 1- 1o((1,, we have
Theorem 2. For any node
Graph attention mechanism helps when: Spaise (1) and Frxise o( Vlog m
In this case, where structure noise is high and feature noise is low, based on Corollary we obtain
too (2G--1)) Djn = 1, where vt 2 o,, INIIWW
lim
B|X]]
(pel 9)- pe22 + -e--2 21 (4)
vn- 14 where 5(t) A
lim Var(X]) 1, where (a')2 A P FI,,,, WT), (op)
The detailed expressions of F()) and F()) are provided in Appendix C.
Note that 5(t) has a unique inflection point at = 2 log 9
O and is monotonically increasing in the interval >>> 0. Thus, the graph attention mechanism proves effective, with the improvement in the SNR becoming more pronounced as the attention strength t increases. When the attention strength is sufficiently large, the SNR can be enhanced by up to p//o' = /np- p/o.
It is important to highlight that, unlike simple graph con- volutions, graph attention mechanisms perform non-linear operations on node features. As a result, the output node features no longer follows simple Gaussian distribution,
5

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Graph attention mechanism does not help when:
consensus regarding the issue of over-smoothing. namely, that over-smoothing tends occur in shallow layers relative to the number of nodes in the graph (Yang et al., 2020; Wu et al., 2022b). To facilitate our analysis, we consider the scenario where the number of nodes n. approaches infinity, and assume that the number of layers L in the GNN is ((n). The refined definition of oversmoothing is as follows
Suoise (1) and F = =1).
Now we consider the case where feature noise is high and structure noise is low. It follows from Corollary 1 that
pl σ. - P P-1 (a-16----9) 1--12 n(p + 9) ptg
Definition 2 smoothigg). For an undirected featured graph with A being the adjacency matrix and X being the the features of all nodes, we say 7 -R." + R2o is node node-similarity measure if satisfies the following axioms:
(5)
For the above expression, it is clear that as t increases, yL /o' decreases. Furthermore, we observe that if t is not infinitesimal, meaning (e' - 1) is constant, then passing through such a GAT layer does not necessarily guarantee an increase in the SNR. This implies that the GAT layer may not serve useful purpose. Therefore, when feature noise predominates, using the attention mechanism can be counterproductive. In this case, simple graph convolution (with & = 0) performs better, yielding an improvement in SNR of μl /o' = 0(vn((p + 9)) 1//o.
3 c E IR such that X; c for all E [n] if isand only if (X) = 0, for X E ;
7( + +Y) (X)
for all E,YYER.. ER..
We denote the output node features after I laaers as X(). For GNN with L layers (where L, = O(n)). we define over-smoothing to occur if there exist constants C1 C2 0 such that for all l E [[]: (0))) S &C1e C1e-Coly((((0)
Remark 3. Note that the previous discussion does not cover all possible parameter regimes of Fooise and Snoise- and be- low we present our comments or conjectures for the remain- ing regimes. When Snoise (1) and Fnoise M Tog n ) both structure and feature noise are strong, meaning the feature graph contains very little information. In such a scenario, no method is likely to perform well in node classi- fication, making the discussion of the attention mechanism meaningless. When Snoise = (1) and Vlog & FFoisse & 1, we conjecture that the graph attention mechanism may have some effect, but smaller value of would be re- quired. When Suoise = 011 and Fnoise = ol To both structure and feature noise are minimal, leading to strong performance from both GCN and GAT, with little additional benefu from the graph attention mechanism.
In this paper, we employ a node-similarity measure function similar to (Wu et al., 2024), which has been proved to satisfy the above axioms and takes the form
1
1.1T X||r-
xX)
X
(6)
The difference from (Wu et al., 2024) is that the function 7 we use incorporates normalization; however, this does not prevent it from serving as node-similarity measure.
The above definition of over-smoothing is a general one applicable to any featured graph. Within the CSBM, it be- comes apparent that smotthin is related to the model's parameters, particularly the model's expectation and vari- ance. The following lemma describes their relationship.
Lemma 1. For
featured graph ()
To summarize, our theoretical analysis indicates that the graph attention mechanism is not always effective for node classification tasks. When Faeise is high and Smoise is low, it performs worse than simple graph convolutions. This occurs because graph convolution leverages structure information for message passing, whereas the graph attention mecha- nism assigns edge weights based on feature similarity. Un- der these conditions, GAT's weights become unreliable and may introduce additional noise. This finding complements the results in (Fountoulakis et al., 2023), which highlighted the benefits of graph attention in reducing structure noise. Furthermore, carefully timing the application of graph at- tention can enhance SNR in both scenarios.
CSBM 9 14, J), as n approaches infinity, with probability at least 1 - o(1), the mode-similarity measure in Eqn. 6
satisfies: lim 7(X) 1.
Vu=+o3
We focus on cases with low feature noise, i.e., SNR w( Vlogn), as the previous section concluded that when feature noise is high, the attention mechanism offers no improvement for node classification. Therefore, discussing over-smoothing in such cases is irrelevant.
The following theorem demonstrates that when SNR is suf- ficiently high, GCN suffers from over-smoothing, while the graph attention mechanism can resolve the over-smoothing problem.
3.3. How Does Graph Attention Mechanism Affect Over-smoothing?
Theorem 3. Assume that SNR= w( n). Based on Definition 2, the graph convolutional networks suffer from over smoohhino..ng... However, when t = w( (Togn) n), networks with graph attention mechanisms can prevent this over- smoothing phenomenon.
We begin by introducing a formal definition of over- smoothing, based on the definition in (Rusch et al., 2023) with some improvements. Our improvement stems from a
6

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
To prove Theorem 3, we begin by analyzing how the expec- tations of node features evolve through multiple layers of GCN or GAT. Subsequently, we use Lemma to assess how the node-similarity measure function changes in these two network architectures, allowing us to determine whether over-smoothing occurs. Specifically, for an L-layer GCN, we show that 7 (x(()= = (1 -1-38 2²y )²y''''( (x(()) holds for every I E [4], indicating that over-smoothing occurs. In contrast, for an L-layer GAT with L = (n) and t = w( (Vllgg n). 29
ensures that each layer effectively enhances the SNR while preventing the over-smoothing problem.
Importantly, although this approach is tailored for the CSBM for theoretical convenience, it also offers practi- cal insights for GAT design in real-world applications. In scenarios with substantial feature noise, one can initially set low intensity for the graph attention mechanism to fully leverage structure information. As the network depth increases, the intensity of the attention mechanism can be gradually increased to prevent premature over-smoothing.
we demonstrate that (Xx1)) = (1 pe p +, )'
(((())))) holds for every / [Z]. thereby resolving the
over-smoothing problem according to Definition 2. The
4. Experiments
detailed proof is provided in Appendix H. A synthetic ex- periment is presented in Section 4.1, and the results (see
In this section, we perform extensive experiments on both synthetic and real-world datasets to validate the theorems and findings of this paper. The synthetic datasets are created using CSBMs, while the real-world datasets include the widely used Ci citeseer, Cora, and Pubmed, utilizing the default train-test splits provided by Py PyTorch Geometric (Fey & I Lenssen, 2019). The characteristics of the real-world datasets are provided in Table 2 in Appendix K. All experi- ments are conducted on machine equipped with Intel(R) Xeon(R) Silver 4215R CPU @ 3.20GHz, 64GB RAM, and an NVIDIA GeForce RTX 3090.
Figure Ic) support this theoretical result.
3.4. Perfect Node Classification in Multi-layer GATs
Based on the preceding discussion, we have identified sce- narios where the graph attention mechanism enhances node classification and mitigates the over-smoothing issue. Lever- aging these insights, we can strategically design more ef- fective multi-layer GATs for node classification tasks, i.e., using our proposed graph attention mechanism with differ- ent values of for different layers. Furthermore, we show that the well-designed multi-layer GAT's can significantly relax the "easy regime" conditions required by single-layer
Classification Accuracy
Classification Accuracy
1.0
1.0
0.9
GATs to achieve perfect node classification (Theorem 1).
0.8
0.8
Theorem 4. For a featured graph (A,
2-2.1, b-2
SNR=0.2
CSBM 9, 1b, J) suppose p- alog" a and q blog? a
2=2.5, b=2
07
SNR=0,5
n O are positive constants". When
a-3.0, b-2
SNR-1
where a > b
there exists a multi-layer GAT capable of achieving perfect node classification.
SNR- = w V/log n. Vn
0.00
0.05 0.10 015
Attention Intensity t
Attention Intensity (b)
04
066
0.
1.0
(a)
By comparing Theorem 4 with Theorem 1, we find that the multi-layer GATs can significantly expand the condi-
Node mide--imillriity Measure
60-
Classification Accuracy
50-
0.
40-
tions for achieving perfect node classification from SNR w( w(Vlog n) to SNR = w(1 /Tog n/ (n) when the structure noise is not excessively high. This represents a considerable advancement, indicating that while previously an infinitely large SNR used to be required for perfect classification, now even an infinitely small SNR suffices. This underscores the superior noise tolerance of multi-layer GATs compared to single-layer GATs.
30-
0.8
20-
1.1.5
0.
GAT
10-
0.6
GCN
GAT
0.5
20
40
60
80
100
0.00
0.5
0.50
0.75
1.50 SNR
1.00
1.25
1.75 2.00
Number of Layers
(c)
(d)
Figure 1. Results of the four experiments conducted on synthetic datasets. Here, Figure la shows the results of node classification with high Spáse and low Frise: Figure 1b presents the results for node classification with high Frese and low Suase Figure shows the results of the over-smo experiment; and Figure Id illus- trates node classification results across three different networks.
In our proof, we employ a hybrid network combining GCN and GAT layers (introduced in Appendix J). Specifically, for layers where the input SNR is less than /log n, we utilize graph convolution layers without the attention mechanism (i.e., setting = 0). As the SNR increases beyond vlog n after multiple layers of graph convolution, we switch to graph attention layers with higher values of t. This design
4.1. Synthetic datasets
We conduct four experiments on synthetic datasets. Experi- ments 1 and 2 are designed to validate the conclusions from Section 3.2.1 on the conditions under which the graph atten- tion mechanism is effective. Experiments 3 and are aimed
Here, we adopt a slightly stricter assumption than Assumption to ensure that the structure noise is not excessively large.
7

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
at confirming Theorems 3 and 4, respectively. In all exper- iments, the CSBMs used generate the data share some identical settings: n = 3000, o = 10, p = log" n and q = blog2 n where a and b are positive constants. For Ex- periments 1, 2, and 4, classification accuracy is used as the evaluation metric, defined Eig[n] [(, = 2c;- 1)/n. All results are averaged over 100 trials.
accuracy, especially at low SNRs, where it significantly out- performs the other models. As SNR increases, GAT"s perfor- mance approaches that of GAT*, with both models surpass- ing GCN. The figure also highlights the line SNR
//ogg
When SNR exceeds approximately 2y/og GAT* achieves In perfect classification accuracy, thus validating Theorem 4.
For Experiment 1, we investigate the effectiveness of the graph attention mechanism in a high Spoise and low Fooise scenario. We use a four-layer GAT as specified in Eqn. with the attention mechanism defined in Eqn. 3, setting the attention intensity t. We fix μ = 20 /log n and b 2, and explore cases with 2.1, 2.5, and fication accuracy as a function of is recorded, with each data point representing the average of 100 independent tri- als, as shown in Figure la. The trends in Figure la indicate that the graph attention mechanism enhances classification performance under these conditions, supporting the conclu- sions in Section 3.2.1. Performance improvements become more pronounced with higher values of and Smoise.
4.2. Real-world datasets
We select three commonly used real-world datasets, Citeseer, Cora and Pubmed, and constructed three different models to compare their classification accuracy under varying levels of feature noise. Specifically, we build two-layer GCN, two-layer GAT, and hybrid model where the first layer is graph convolution layer and the second layer is graph attention layer, referred to as GAT*, To control the feature noise, we added Gaussian noise with zero mean to the features of the three datasets, where the noise intensity is determined by the variance of the Gaus- sian distribution. The experiment tracked the classification accuracy of the three models function of the Gaussian noise intensity, with the results shown in Figure 2. From Figure 2, we observe that when the feature noise is small, GAT outperforms GCN. However, as the feature noise in- creases, GAT's performance begins to fall behind that of GCN, which is consistent with our theoretical analysis in Section 3.2.1. Furthermore, GAT* exhibits greater robust- ness to feature noise, maintaining high accuracy regardless of the noise strength, which also validates our thcoretical results in Section 3.4.
3. Classi-
Experiment 2 examines scenario with low Spoise and high Fnoise. We fix = 6 and b = 2. and test three values for μ:: 2, 5, and 10, while recording the relationship between classification accuracy and t. Using a three-layer GAT with a uniform attention intensity I across all layers, we find that classification accuracy decreases with increasing t, indicat- ing that the graph attention mechanism becomes counter- productive. This observation corroborates the conclusions drawn in Section 3.2.1 regarding the conditions under which the graph attention mechanism fails.
0.70 0.ss
Classification Accuracy
GCN
Accuracy
2.80
GCN
Experiment 3
aims to validate Theorem 3, which sug-
GAT
0.75
GAT
gests that the graph attention mechanism can prevent over-
5.70
GAT
smoothing under certain conditions. We set 2, 6 3, and u 10, using the similarity metric y from Eqn. 6 to
0.50
0.4
Checoification
0.00
2.00
measure node similarity. We construct a 100-layer GAT, var-
0.50
0.50
ied t, and record changes in y after each attention layer, as shown in Figure lc. The results show that, for small values of t, decreases exponentially, indicating weorssmothhing As increases, the rate of decrease in y slows, and for suf- ficiently large f, the node similarity metric y approximates linear decline rather than an exponential one. This indi- cates that, under the current settings, wer-shoothing can be eliminated when t is sufficiently large.
0.5
Gaussian Noise Strength (a)
030
6.5
6.5
0.30
0.00
03)
Gaussian Noise Strength (b)
042
0.00
0.04
025 03c
Classification Accuracy
GCN
GAT
GAT*
2,5
In Experiment 4, we compare three graph neural network models for node classification across different SNRs, set- ting to a 2 and b 4. The first model a four-layer GCN. The second is four-layer GAT with fixed attention intensity/ = 5. The third model, referred to as GAT* uses gradually increasing attention intensity, with values of [0, 0.5. 0.5. 5] across the four layers. Figure l shows that GAT* consistently delivers the highest classification
Gaussian Noise Strength
(6)
Figure 2. Experimental results on real-world datasets. Fig- ures 2a, 2b and 2c illustrate the results for the Citeseer, Cora and Pubned datasets, respectively.
We also conduct more extensive experiments on a larger dataset ogbn -axiv (Hu et al., 2020) to evaluate the ef- fects of the two types of noise. The results further validate
8

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
our theoretical findings. Detailed experimental results and analysis are provided in Appendix I..2.
We thank our friend Yizi Wang for the helpful discussions the proofs of certain lemmas.
5. Conclusion
References
This paper analyzes the graph attention mechanism using CSBM, revealing its potential failures under certain con- ditions. We rigorously define its effective and ineffective ranges based on structure and feature noise and explore its role mitigating the over-smoothing problem. particularly in high SNR regime. We also propose multi-layer GAT, establishing conditions for perfect node classification and demonstrating its superiority over single-layer GATs. Our findings provide insights for practical applications, such as selecting graph attention based on graph data characteristics and designing noise-robust networks, which we validate through experiments on real datasets.
Abbe, E. Community detection and stochastic block mod- els: recent developments. Journal of Machine Learning Research, 18(177):1-8)) 1-66 2018.
Abbe, E. and Sandon, C. Community detection in gen- eral stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th An- nual Symposium on Foundations of Computer Science, pp. 370-688. IEEE, 2015.
Abbe, E., Bandeira, A. S., and Hall, G. Exact recovery the stochastic block model. IEEE Transuctions on Information Theory, 62(11):71-447) 2015.
While our analysis provides valuable theoretical insights, it has several limitations that suggest directions for future work. First, the attention mechanism study is simpli- fied version that omits learnable parameters and does not incorporate multi-head attention. While this simplification enables clearer analysis, it may not fully reflect the com- plexity of modern attention- GNNs. Second, we focus on multi-layer GATs but apply attention only at the final layer; incorporating attention at every layer would introduce intricate dependencies that require more advanced theoret- ical tools. Extending the analysis to these more general and expressive settings is an important avenue for future research.
Adam-Day, S., Benedikt, M., Ceylan, i. I., and Finkelshtein,
Graph neural network outputs are almost surely asymp- totically constant. arXiv preprint arXiv:2403.033: 2403000000 2024.
Baranwal, A., Fountoulakis, K., and Jagannath, A. Graph convolution for semi-supervised classification: Improved linear separability and In International Conference on Machine Learning, pp.
generalization.
684-693. PMLR, 2021.
Baranwal, A., Fountoulakis, K., and Jagannath, A. Effects of graph convolutions in multi-layer networks. In Inter- national Conference on Learning Representations, 2023.
Impact Statement
Braun, G., Tyagi, H., and Biernacki, C. An iterative cluster- ing algorithm for the contextual stochastic block model with optimality guarantees. In International Conference on Machine Learning, pp. 2257-2291. PMLR, 2022.
This work provides theoretical analysis of the graph at- tention mechanism, demonstrating that it is not universally effective and offering a precise mathematical characteriza- tion of its applicable range. Additionally, it presents the first theoretical sufficient conditions for exact recovery using multi-layer GAT's on the CSBM model, highlighting the performance gains enabled by deep architectures. Moreover, extensive experimental validation further supports the con- clusions, offering valuable insights for the design of future algorithms in the GNN field.
Chen, Z., Li, L., and Bruna, J. Supervised community de- tection with line graph neural networks. In International Conference on Learning Representations, 2020.
Deshpande, Y., Sen, S., Montanari, A., and Mossel, E. Con- textual stochastic block models. In Advances in Neural Information Processing Systems, volume 31, 2018.
Dreveton, M., Fernandes, F., and Figueiredo, D. Exact re- covery and bregman hard clustering of node-atrributed stochastic block model. In Advances in Neural Informa- tion Processing Systems, volume 36, 2024.
Acknowledgements
This work was supported by the National Natural Science Foundation of China (Nos.U22B200) 62261136549,, the National Science Fund for Distinguished Young Schol-
Duranthon, O. and Zdeborova, L. Optimal inference in con- textual stochastic block models. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
ars (Grant No.62025602), the Fundamental Research Funds for the Central Universities (Nos.G2024WD0115 D5000240309), the Tencent Foundation and XPLORER PRIZE, and Shanghai Artificial Intelligence Laboratory.
Edition, F., Papoulis, A., and Pillai, S. U. Probability, ran- dom variables, and stochastic processes. McGraw-Hill Europe: New York, NY, USA, 2002.
9

---

Graph Attention is Not Always Bencficial: A Thcoretical Analysis of Graph Attention Mechanisms via CSBMs
Fan, W., Ma, Y., Li, Q.. He, Y., Zhao, E., Tang, J., and Yin, D. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Lu, C. and Sen, S. Contextual stochastic block model: Sharp thresholds and contiguity. Journal of Machine Learning Research, 24(54):1-34, 2023.
Fey, M. and Lenssen, J. E. Fast graph representation learning with PyTorch Geometric. In ICLR 2019 Workshop Representation Learning on Graphs and Manifolds, 2019.
Luan, S., Hua, C., Xu, M., Lu, Q. Zhu, J., Chang, X.-W.. Fu, J., Leskovec, J., and Precup. D. When do graph neural networks help with node classification? investigat- ing the homophily principle on node distinguishability, In Advances in Neural Information Processing Systems, 2023.
Fountoulakis, K., Levi, A., Yang, S., Baranwal, A., and Jagannath, A. Graph attention retrospective. Journal of Machine Learning Research, 24,
Ma. Z., Jiang, Z., and Zhang, H. Hyperspectral image classification using feature fusion hypergraph convolution neural network. IEEE Transactions on Geoscience and Remote Sensing, 60:1-14, 2022. doi: 10.1109/TGRS. 2021.3123423.
Frieze, A. and Karoński, M. Introduction to random graphs. Cambridge University Press, 2015.
Gligorijević, V., Renfrew, P. D., Kosciolek, T., Leman, J. K., Berenberg, D., Vatanen, T., Chandler, C., Taylor, B. C., Fisk, I. M., Vlamakis, H., et al. Structure- based protein function prediction using graph convolutional networks. Nature communications, 1261))3168, 2021.
Reynolds, D. A. et al. Gaussian mixture models. Encyclo- pedia of biometrics, 741(659-663), 2009.
Rusch, T. K., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303. 10993, 2023.
Holland, P. W., Laskey, K. B., and Leinhardt, S. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018.
Hu, W. Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, volume 33, pp. 20118-22133, 2020.
Wang. J., Guo, Y., Yang, L., and Wang, Y. Understanding heterophily for graph neural networks. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 50489-50529, PMLR, 21-27 Jul 2024.
Javaloy, A., Martin, P. S., Levi, A., and Valera, I. Learnable graph convolutional attention networks. In The Eleventh International Conference Learning Representations, 2023.
Wang, L.,, Huang, Y., Hou, Y., Zhang, S., and Shan, Graph attention convolution for point cloud semantic segmen- tation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10296- 10305, 2019a.
Keriven, N. Not too little, not too much: theoretical anal- ysis of graph (over) smoothing. In Advances in Neural Information Processing Systems, 2022.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2022.
Wang. M., Zheng, D., Ye, Z., Gan, Q., Li, M., Song, X., Zhou, J., Ma, C., Yu, L.,, Gai, Y., et al. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint 1xXiv:1909.01315 2019b.
Lee, J. B., Rossi, R. A., Kim, S., Ahmed, N. K., and Koh, E. Attention models in graphs: A survey. ACM Transactions on Knowledge Discovery from Data, 16):11225, 2019.
Wang. He, X., Cao, Y., Liu, M., and Chua, T.-S. Kgat: Knowledge graph attention network for recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 950-958, 2019c.
Leiserson, C. E., Rivest, R. L., Cormen, T. H., and Stein, C. Introduction to algorithms, volume 6. MIT press Cambridge, MA, USA, 2001.
Liu, M.. Gao, H., and Ji, S. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 338-348, 2020.
Wei, R., Yin, H., Jia, J., Benson, A. R., and Li, P. Under- standing non non-linenn con-iincrrtty in graph neural networks from the bayesian-inference perspective. In Advances in Neural
10

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Information Processing Systems, volume 35, pp. 34024- 34038, 2022.
Wu, S., Sun, F.. Zhang, W., Xie, X., and Cui, B. Graph neural networks in recommender systems: survey, ACM Computing Surveys, 55(5):1-37, 2022a.
Wu, X., Chen, Z., Wang, W., and Jadbabaie, A. A non- asymptotic analysis of oversmoothing in graph neural networks. arXiv preprint arXiv:2212.107700 2022b.
Wu, X., Ajorlou, A., Wu, Z., and Jadbabaie, A. Demys- tifying oversmoothing in attention-based graph neural networks. 36, 2024.
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C.,, and Philip, S. Y. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2020.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
Yang, C., Wang, R., Yao, S., Liu, S., and Abdelzaher, T. Revisiting smor-snog in deep gens. arXiv preprint arXiv:2003. 13663, 2020.
Yang, T., Meng, J., Zhou, M., Yang, Y., Wang, Y., Li, X., and Tong, Y. You can't ignore either: Unifying structure and feature denoising for robust graph learning. arXiv preprint arXiv:2408.0005 00700, 2024.
Yeh, J. J. Real analysis: theory of measure and integration. World Scientific Publishing Company, 2014.
Zhang, A. Y. and Zhou, H. H. Minimax rates of commu- nity detection in stochastic block models. The Annals of Statistics, 44(5):2252-2280) 2016.
Zhang, Q. and Tan, V. Y. Exact recovery in the general hypergraph stochastic block model. IEEE Transactions on Information Theory, (91))
Zhao, L. and Akoglu, L. Paimnorm Tackling oversmooth- ing in gnns. In International Conference on Learning Representations, 2020.

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
A. Outline of Appendices
Outline: In Appendix B, we provide additional details on the graph attention mechanism designed (Fountoulakis et al., 2023) and explain how the mechanism used in this paper approximates it. Appendix C supplements definitions and vital lemma that will be referenced throughout the proofs. Appendix presents the proof of Theorem 1. Appendices and provide the proof of Theorem 2 in two parts: the expectation and variance components. Appendix G details the proof of Corollary I, while Appendix H covers the proof of Lemma 1. Appendix provides the proof of Theorem 3, and Appendix J presents the proof of Theorem 4. Appendix K includes additional proofs of lemmas, and Appendix L gives the results of additional experiments.
B. Graph Attention Mechanism in Fountoulakis et al. (2023)
In the referenced work (Fountoulakis et al., 2023), the authors indicate that the edge classification problem is essentially an "XOR problem" and have designed two-layer neural network architecture v to address this XOR issue, detailed below,
(s
X, Xj
(X, X,) A LeakyRelu
where
1
-1 -1 R
S -
(8)
where R > 0 is the scaling parameter. Furthermore, LeakyRelu(-) is a non-linear activation function characterized as
if x 2 0, if < 0, Ba
LeakyRelu(z)
where 3 > 0 typically refers to a very small constant.
Substituting Eqn. into Eqn. 7, we have
-2R(1 B)X,, V (X,,))
if X; S - if - |Xil <X, < [X.),
211(1 - ()sgn(X,))))
(9)
2R(1 - X)
if X, |X,]|
Then we find that when the features of the two imput nodes, X, and X,. have the same sign. the value v is greater than 0. Conversely, when X, and X, have opposite signs, the value of less than After applying the softmax function, edges with positive v values considered intra-class edges and are assigned higher weights, while edges with negative values treated as inter-class edges and are given lower weights. Additionally, the disparity in the weights can be regulated by the scaling parameter R.
Motivated by the preceding insights, in this paper we abandon the neural network framework and adopt a simpler graph attention mechanism for CSBM, that is,
V(X,, x,) {
if X,20, 20 if; X, <0
(10)
where 0 serves similar role to R, which refer the attention intensity.
Additionally, it is worth noting that the attention mechanism proposed in (Fountoulakis et al., 2023) can handle cases where the dimensionality of node features d is greater than 1. In (Fountoulakis et al., 2023), when the CSBM generates node features, the following change occurs: for a node i, its feature X; is generated by N ((2e; 1)μ, o² I). where E Rd E R and I E f0, 1 the identity matrix. Thus, for a pair of nodes (i.j) and their features X, and X,, the attention mechanism in (Fountoulakis et al., 2023) becomes
7T X;
L (X,, & r LeakyRelu
S
(11)
X
12

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
where S and follow from Eqn. 8.
In this case, our proposed attention mechanism can also approximate the above-mentioned one with minor modifications, leading to the following expression:
y ,²X; 2 0, ( if" x²X, O.
XX),
(12)
By comparing Eqns. 1I and 12, we observe that our proposed attention mechanism eliminates two matrix multiplication operations, resulting in greater efficiency.
Note that since the node features in real datasets have 1, the attention mechanisms in Eqns. 11 and 12 are employed in experiments with real datasets in Appendix K.
C. Preliminaries for Proofs
WW7), which We begin by providing the complete expressions for functions F (1, 0, 1, (WT)) and F (4,,, (WT)), were omitted in Theorem of the main text. For simplicity, we define
y
-
202
22 +
A(2,t) a el (v + 1(1 =)) + (0-0-110
- y pzz)
2
(13)
jyy + 1² 2) + 0a z)) e ( my + 4²= + oo2)) (2, B 2 21
Then we present that
F Fw, 4, (N7 = S (=.4, WPD - T 2, 2, IV71,
where
(14)
AT
1 ) 11 1- @/
S (2,,4,N7) WW)) &
Σ
+r s)e² + ((V - s)e-
(15)
T 2, &,7.
WPl
-1) - 1NN9 (1 (1-2) ()=,) -t) + =A(e,
and
F(..o.E.11/P11100 3 (..7, WTD - (..,,
where
(16)
IA (INII) (1AT)) (1 16 (1) 1 : 11771+0- (#) ((r ( + (WW - -
((3,417711W7)) - Σ T 7 (NP1,1,7) & (1NP12 + (e' - -
11---10 2) (2y + n((1 - -2z))
(17)
2M77I (e' -c- (-2(1- - 2)1 + uz(1 22)) (1- ((1=))A(2,t) 1) + +2A(2,-1) -t) WI (11 ([==)))(,,,)+=((<..>-> + W ((1 (11=))B2z, -1) =B((z,
Then we introduce an important lemma from the referenced paper (Fountoulakis et al., 2023). which plays a key role the proofs of several theorems. This lemma concerns series of high-probability events, which can be proven by directly use of the Cherooff bound and the union bound. See (Fountoulakis et al., 2023) for the detailed proof.
Lemma 2. Consider the following events,
1. Ai: |Col = + O(Vnloggnn and Cil = 2T + O(vn logn) n)
2. 22: for each node i E [m], Wil -(p+g) 2
[ +
/ng n
10
13

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
3. A: for each node i E [m]. [ = [ ptg
+
Alggn n 10
and [ = |
_ p-g
[ +
Aogg x2
16
4. A:: for each node i E [m]. X; E[X;]] & 10 log n.
Suppose that Assumption I holds. For a featured graph (A, sampled from CSBM(P, q, u. σ), the event A a A
A 0 44 happens with probability at least o(1).
D. Proof of Theorem
Without loss of generality, we first discuss a node i that belongs to C1. For any neighbor j E N using the graph attention defined in Eqn. 3, we have
X, = -) P(X; X, 0 = -1-1 )
1 (
2 + 12 4
(18)
([ = -t P(x; X, < 0} = 2(1 1b 4
The following lemma gives tail bound of +
Lemma 3. Assume random variable y (0, 1), then for any constant
0, the following tail bound holds,
p 2 s) (s)) I min {
c
(19)
2T
Proof. See Appendix K for the detailed proof.
Next, we illustrate the concentration of the attention coefficients in the easy regime. Consider the probability of the following event of node i, P(Yj E N?: X = P(3j E N? X; X, < 0}
(4)
2 11 WP1 (1 - +b 11
Φ 11
(4)
(20)
2 1 WW
w( (L(Vlo log n.) 2
(0)
1
2 1 - 2 WW? of
= o(1),
nVllog
where (i) derived using the union bound, (ii) follows from SNR= w(Vlogn) and Lemma 3, (iii) due to the fact that [V?| Onn).
Similarly, for the inter-class neighbors of node i, we have
P(Yj E NT X, x)
(21)
Then, for any j E N?, the attention coefficient Cij, with high probability, is determined as
exp(V((X,, X,))
Gj ΣLEN, exp( V (X,, Xx))
exp(v(X,,,))
(22)
EKENY exwppxXppxXppppce Xn)) + EVENy exp ( (X;,
W + +W
where (1) is due to Eqn. 20 and Eqn. 21. Accordingly, for any j' E A,7
Cit'
WPle' + - w.h.p.
(23)
14

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Then, after a single-layer GAT as outlined in Eqn. with L 1, the output of node i is determined as
X
sgn
Σ
A
jEIn
Σ
Ki + Σ Exxx))
sgn
jENT
S'EN?
(24)
INT
W We + WTle- (-p + 10
sgn
N el WeM (u+ 100 100 log
10011lllg Vlogn)
w.h.p.
(iX)
pe
ge pe¹ + qe- p (1 +1))
sgn
w.h.p.
where (i) directly follows from the high probability events A4 in Lemma 2 and Eqn. 22- 23, (fi) is due to the high probability
event Ag in Lemma 2 and the fact that = w(ollog n). Notably, for a sufficienst large t, we have
pe qe pet + qe
24 pe +
= 1 - o(1).
(25)
Thus, Eqn. 24 can be further calculated as
X w.h.p.
sgn (u- (1 = =1 1.
(26)
Likewise, for any node i' Co, it can be proven that, with high probability, the output X equals -1.
E. Proof of Theorem 2 (Expectation Part)
We first present two lemmas that play a significant role in the proofs of the expectation part of Theorem 2. Lemma 4. Assume a random variable x ~ NN,, 0²) with f(x) being the probability density function of x, then
1 to0 xf(x) dr V2
20
22
+ 1 (4)
(27)
1 xf(z) =
#ेt
+ w (*),
and
1 f²)(x)) dr
2
+ 112 (2 1 (M)
0² 1 $ (4) (7)) 2 (1) + 0² 2 (1)
(28)
S f(x) - 2
+ p
Accordingly, if N( N(--1,02), then
11000 xf(x) = 7
202 - 1& (W)
e
V2x
(29)
2
zf)x
(1))
20
1
2
and
Iot 1o dff(zd - -
20d
2²
+
2 (2) + 2 (5)
(30)
S f()(() do = 1 /3/3 e
20
+ - $ (H) + 0² 1 - 1 (
Proof. Refer to Appendix K for the complete proof.
Lemma 5. Assume 0 < x < 1/2, any constants > 0 and k: > 0, let
T(n,m) m) A n
m
(m) (1 - x) i
1=0 (1+ + (n + m - t)
15

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Then the following equation holds
[(n, m) 1,
lim
(31)
[(n + c1, +22)
where and 02 are positive integer constants.
Proof. See Appendix K for the full proof.
For the expectation part of Theorem 2, without loss of generality, assume that node E C₁ then we have
Xj. X(xx
Xy XxxxexX..X,) DIEN, e((x...))
x Σ
+
Σ
(32)
EIEN, elXxxx))
JEN?
S'EN?
And the expectation of X is then given by
X, ((x,x,
Xy ((Xxe)( LIEN, eV(X),)))
E|
E
Σ
EIEN, EIENEEWXANN el(X..)))
JENT
JEENY
X2 ((xxx))))
Xy Xyr eX(exX)))))
(33)
NP
E
+ E
EIEN, ((X,,X))
ΣIEN, (x(in))))
B
where (i) follows from the fact that each node's 's feature generated independently.
Next, calculate [[[A] and [[ in Eqn.33 separately.
E.1. Calculation of [F[AA)
Caleulating [[[A] essentially entails determining the expectation of joint probability distribution, with the random variables of this distribution being the features of node and the features of all the neighboring nodes of i. Here, denote them as {X1, X2, ]. Then, for every j E N,, it follows that
X,. exxex
EE
DIENT (IX,,()) + EveNy e vV))..x,)
-J
x. X1 .x. -Smm E EreNge (X(
X, e(x,x,
(34)
X, ((X,x,)) (4) Ja Jam ElENpe e(X.Ni)) + EVENgeM(X,,)) ex(x)))))
where (1) due to the fact that each node's feature is generated independently.
Noting that E C₁ and considering the graph attention mechanism outlined Eqn.3, we categorize the discussions into four cases depending on the values of X; and X, being above or below zero. Thus we have
E[A]
E[AX, 0,X, > 0|- P(X, > 0, > E 0,X, < < P(X, 0,X, <
(35)
+ ELAIX <0,X; 0) P(X; <0,,; > 0) E X; < X3 < P(X: <,,; <).
Case 1: X; 0, X, 0, V Xj) t.
Excluding node j, node has 11) intra-class neighbors and |A7'| inter-class neighbors. Let & (lEATIX 2 0} and A' & {l' A Xr 2 0}. For some integers r, 0, we define the event Are as
A Wn and Wsl s.
(36)
16

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
For every j E AV,, given that i is in Co. it follows that X, N(,, o²). Conversely, for every j' ENY, Xy M(-u,
Then have
0 f(Xy) dXy. =1 =1-
f(X))
(37)
[ ((X,) dx, = =|0 -/00 f(Xy) dX,. = 16 (())
100
Hence,
B[ > 0, > P(X, > 0, 0
-
Σ
Σ E[A[X, > 0, 0. > 0,X, > 0.
(38)
IP N
(INT ((N?) ee
Σ
+
1)et= + (IN1) 8 1---
0=0
+00
0
f(X,) ... -(X ... dx wP1-1
INP
.... 1/00 Xzf(X,) dx,
...
|N
|
(WT) +
(1A22) et
Σ Σ 1) + (Wil
- 1)e-
-=
(1 1 (m)) IN +
too
(X,
where (i) due to Eqn. 37.
Note that X, (H, )²), according to Lemma 4, we get that
+
2 50(1 $ )
XxX(Xx)
e 20
+
(39)
25
Hence,
- el
B[A|X,>0,X, > 0, 0] P(X, 0, > 0) Σ
Σ
(r+s+ + 1)et + ([N r l)e-t
-1- 1b (m)) A
① (
IN? -r+s-1
c 22 μ 1 ① (1) )
2tT
(40)
Case 2: X,>0, X, <0, X,), -t.
17

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Similar to the analysis of Case 1, we have that
B[A[X; > X, > 0] P(X, > 0,x,>00
W
Σ
Σ
B[ > O, X, > A..) P(X; > P[X,> > 0,0,>0,A..)
==0
II
( ((471) -
Σ
Σ
1)et + (IVi -r- 1)e
0=0
5=0
(41)
+00
+00
f(Xif ... (XXII--)) ..X
0
r+1
WW
0
F(X ((XINN)) (x dXpai S Xxf(X)) dx,
W
| ΣΣ> 4=0
1 e-
(r + + 1)et + (LVi) - - 1)e-
(1 + (M)
W W
(0 (t) ) 1
(-
+ 1 (1)
e 20
V 2m
where (1) is due to Lemma 4.
Case 3: X; < 0, X, > 0, (Xx,, Xj) = -b.
In this case, have that
E[A[X; <0,X, > 0] P(X, <0,X,
W
(42)
= Σ Σ
P[X. <0,,,
> 0,A,.
0=
INPI-1 N
(AT (LAV3) -
1)et + (IN,) - 8 1)e-
0
[(x))(())) ... ((X dx N!1-
W
0
f(XWF)+1) ... (XX ......Xiiiii S. Xzf(X,) dx,
IN WY
(1A (1A7I) e
= Σ Σ
r
s 1)et + (N1 - 1)e-
(1 - क (M)
W +
( (1)
I
o
e
20
2²
+ 11
+b (() ))
22T
Case 4: X, <, X, <0, ((X,,X,) =t_
18

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Similarly, in this case, we get that
B[A < X, < 0] P(X, < 0,,,, <0}
Σ
Σ
B[AXX, < X, < <.. P(X, < 0, <..)..)
W
( ( (1421) c²
Σ
Σ
s)ct + (Wii -r- -)-
0
+oc
f(x))((x)) ... - ... .d
1+
W!
(43)
+:00
1:00
0
S Xxf(X))
F(X ... ((X(IN))).. dX (X..x)II....XXX ...
W
(WT!--) (1A2T)) e²
= Σ
Σ
(r + s) + (IV.1 r
s)e-
-= ==
(1- 1 (M)
W W7
(0) (
I WP
E 20 + u (
2²
- (2/2 2t
Recall that, for the sake of brevity, the following definations are given in Eqn. 13,
y
A
e
z)) = + L ( A(z, a e² (u+ u(1 u(1 -)) + +e- (-y + 12)
(44)
V2
By substituting Eqns. 40-43 into Eqn. 35, we obtain
E[A]
= E[A[X, > 0,X, > - > 0, > 03 + E[A[X; > 0,X, < P[X > 0,X, <0}
+ E[A[X; X, >
< x, > 0) + E[AIX, <0,X, < P(X, <0,x, <0}
W
(w?! 1 (1171)) e²
= Σ Σ (r (++ 1)et + (Wiil -- 1)e-
(1- & (t) ) | | (o (0(H)) (A? [W71-rto-1
2² 20
+ 4 (1 - 1 (1) )
e
( 1) (W??)) -t
(r 8 + 1)et= + (Wh)
s 1)e-
(1 1 (4)) +
1 11) (1))
17 -
2 22
2 + p (1) )
(r+ 1)e² + ((N6)
--1e-
(1-1) $ (1)) W2/++-=
@ (1)
(
u2 2
ra(
1
T (1)
v 2m
(1 ee
( + .ee + (Wil -T ste-
(1 (1- 1b (4) 1471+1=971
(0 11 WPI WiI
0
+
u
(4)
22T
19

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
I
[A]
-1- 2 gl (r+ s)et + (1VV1 - -res
Σ
wchpp
0=0
0
(1 (1-2) 2) (é'v+ + (11 - 2)) te (-v + u22) + (o + 11(1 - 2)) + c + m2l)
(45)
(1 -
(6s)
(1-z)A(zz)) +z((z,
w.h.p.
(r + 8)e + (IN1 - s)e-
where (1) holds since Lemma 2 ensures that [Na] = n(gtz)
I +
Mlgn 10
= w(1), and (ii) follows from Eqn. 44.
2
E.2. Calculation of [[]
The process for calculating E[B] is the same as for E[A], focusing on finding the expectation of a joint probability distribution for all the features of node i's neighbors. Moreover, because of the graph attention mechanism, both calculations require a discussion for when the product of X, and Xy is positive, involving four different cases. The main difference between calculating E[B] and E[[A] is that X,, is considered an inter-class neighbor, implying follows a different normal distribution, Xy N He o²). Similarly, we have that
B
B X; > 0, X, > 0] P(X, > 0, > 0) + E > 0, < < > 0, <0} X < 0, X, > 0] P(X; < 0, X, 0} + E < 0, X, < 0 P(X; < 0, <
(46)
Additionally, we continue to use the event A,s as defined in Eqn. 36. Notably, with j' being an inter-class neighbor, r is constrained to a maximum of [A['], and correspondingly, reaches its upper limit at ([AV - 1).
Then for the case that X; > 0 and Xy > O, we have that
E X > 0, y 0] P(X; > 0, X. > 0}
I W
Σ Σ
E| > X, > 0, A. P(X, > 02 > 0, 0r
=
(1221) 111 e²
s 1)et (WWl 1)e-
((x))((1)) ... ((X ... dx
r+1
0
[(X ... (X .x /o (x]((x)dX, (47)
INTI- I
(1 ((479)) e²
1)et (Wil -- 1)e-
(1 + (4) |
(o) (# [A7' frr Xz5(Xy)
(
( (LA7 et
(r r 1)et + (Wii) - - 1)e-t
(1 1 (4) - ( (()) ) | (
..2
c (M)
2
20

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
where (i) holds since Xy N(-,, o²) and Lemma 3.
As the other three cases follow the similar approach, we directly state the final result for B[ as
FB3 = [ x > 0, X, > 0] P(X; > 0, X, > + E| > 0, <
<0)
+ E| < O,X, > P(X, < 0, > 0) + E| < 0, X, < 0J P(X, < x0,x,
(WIT)-
(1 ((()))
Σ (++ 1)ee + (Wii -r- 8- D)e-
(1- ② (4) ( 1 ① (5) |
0
1
c 2n²
4
2T
( 1) (W??) ) -
(48)
(r s)e* + (WVi) s)e
(1 4 (1) ) |
① (1) WT -++
2² 26
1
(1 -
1b (-))
c
2T
-
(r + 1)ee + (LAG)
1)e-
(1 - + (1)) w. 1
(o) (1))
2 20
uD (1)
22T
(W77) (W (1W71)
(r s)et + ([Va) s)e-t
(1 (1-0) 1 )
(o (()))
) 1.72 1r++++
0
20 - m(1 1b (())
e
V2T
W! NM (ITII-I(((N?)))) - 11
(11=))A(z, -t) + = AA22
()e*)e + ((W)) s)e-t
w.h.p
where (1) is due to [M] = (1) and Eqn. 44.
After obtaining B[ and E[B]. by revisiting Eqn. 33, it follows that
E[X] who.
(IN7I-
=2)00 (1) (1-=))((20)+ + -2((2
W
Σ
Σ
r
(r+ s)et + (1NV) - s)e-t
WF
(IATI) (177 (1
(49)
+ W
Σ
Σ
(1-=)A((z, -1) + -1)+
=)2,1())
(r + s)et + (WW1) - s)e-t
whp WTI S (2.4 1,1,7) (11 (1-2) (0-22))A220) + --((z, -t))
+ +
W. 1) (a- A((, -t) + A(2.t)) +)2+)))(ttt)
where
WT WT (IA?I) (1 1 (*)) ) $117++-- (#)
S WTD &
(r + s)e* + (W - s)e-
Notably, given that 2 (1) E (0, 1/2) and t 0. applying Lemma 5, it follows that
5 (2,4, 4, IN? - 1. W!! who (33,41A7) 1).
(50)
21

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Hence, is sufficient to show that
E
w.h.P.
(51)
where
((..A1111) WW! (1- (1 +) +=At,, - (1-=))((2, -1) -0) =0)0((21))
- -1)
Similarly, if node belongs to community Co. by symmetry, we obtain that
X
w w.h.p
S
U, WF)).
(52)
Thus, for any node i Ce., with probability 1 o1), B[X]] equals (2e, 1)p', where
p' = (1 [(2, y. [V?), (WTI).
(53)
F. Proof of Theorem (Variance Part)
We first present a key lemma for proving the variance part of Theorem 2.
Lemma 6. Assume 0 < x. 1/2, any constant i 0, define A(n, m) A E.= Ei=o ((+j)ee (ottm)==((----))e-e- and
B(n, m) & (Ei= Ej= (")) (
Then, for n + m - -00, we have
((t))e t-j
m) = +(n+m))(++)) B(n,m) = O(n m)- A(n, B(n, = o((n + m))
Proof. We provide the detailed proof in Section K.
Without loss of generality, we assume that node i E Cj. Note that
(xr( = [[(x) E [X]].
(54)
Since we have obtained E[X]] in the proof of Theorem 2, the key now is how to calculate E[(()) By Eqn. 32, have
(X/)² Σ X, c(
+ Σ
JEENY EIEN, cV(X..))) )²
Xy. ey.ee
EieN CXXNN
JENT
X, ((G,)))) JEN Eiey, ev(xxd))
X,, e
E
Σ
EIEN, ex(x..)))
JENN
B
X, x....e ((X,)))) ( (X),))))) (EEN, exxx.)))
Σ Σ
JEAP J'ENN
(55)
Thus, we have established that [ = E[A] + E + E[C]. components in turn.
Subsequently, we will calculate each of these three
22

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
F.1. Calculation of [[[A]
Firstly, since the node features generated independently, we have e ((X.,))) DIENp ((x,)))) EveNy e((,,N,))
E[ - E (E JENT
Σ
X1, Xzz ((X ((X,)(s))
-(W?) E
(EIENp el((ki EvENy e (x(N)))))
(56)
A
X3 (20(X;,),))
+ W E
EIENN ((Xx..1) + EVENY e eX
where J2 E NV.- The key to compute the expectations of Ai and A2.
F.1.1. CALCULATION OF E[Ai]
Given that node in C1, and using the graph attention mechanism from Eqn. 3, we break down the discussion into eight cases, each defined by the positive or negative values of X,, Xj, and Xj shown in Table
Case 1
Case 2
Case 3
Case 4
Case
Case
Case
Case
X
2
0
IIV IV
0
A I
2
IV <
A IV <
<
<
X
0
0
<
Xj,
0
2
V
0
Table I. Different cases of X,, Xú and X22-
Hence, we have
E[4 Case 1] P[Case 1) +... E[A1| 8) P(Case 8).
(57)
Case 1: X2 2 X,, 2 0, J2 2 0, (X,,, X,,) t. Xx,)
Using the same notion of event Ar, defined in Eqn. 36, have
2
O[A||Case 1] P[Case 1) Σ Σ [[A P(A..}
I N21
(!79) ((77)) _
Σ ((r + + 2)e² + (WW
r -- --22)e--1y
f(X.)((x)).. ... (2) .... ...X
INP
((X dx dXINTTHH .d.
X,, f(X,, dx,, fo {x,)(xx))X,
( [...' 2
((r 2) (Wi r p- 132
+ _ 1 (y + 11(1 - =2))2
(58)
23

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
where (i) follows from Lemma 4, Eqn. 37 and Eqn. 13.
Case 2: X; 2 0, Xn 2 0, X2 < 0, (X,, (,) 1, (XX,, = -t. Following the same approach as in case have that
||A|| Case 2] P(Case 2
1 W?
(r+ 8 + 1)et + ([W 2) (1x21)
Σ
r 8 110-1-e-- 1)2
P=0
(1 - 2)W² +r-st1 1 (y 111 2)) (-y + nz).
(59)
Case 3: X; 2 O, j,i < 0, X2, 2 0, (X,,,
X,,) -t, -,, Xp,) = t.
Similarly, we have
|[A]| Case 3] P[Case 3}
IW?I-2 WT
(1771-2) (1N71)
Σ
((r (s l)et + (IWi 1)2
==0
(1 - u 1-er41 21071- (y 11( - 2)) (-y + μz).
(60)
Case 4: X, 0, Xn1 < 0, X32 <0, -( -t.
Likewise, we have
|[A|/Case Case 4| P( Case 4]
INPI-2 WI
NN -2 ( -2
Σ
Σ
8)et ([Wi) s)e-tz2 (1 a1-220 -1=2)((+++=0411 _1071 (-y + uz)
P=0 ==0
(61)
Case 5: X; < 0, Xj, 2 0, x, 20, 0, V(x Xz,) - -1, V(Y, X,x) -t.
We get that
|[Ai Case 5]
P( P[Case 5}
INPI-2 NTll
( (rr (r++++ e) + (Wi - t)2
(W!l) (W!))) 22
Σ Σ
(1 3) -
(y p(1 2))?
(62)
Case 6: X; 0, X₁, 2 X,2 <0, (XX,, Xz,) = - MxX,, In the same way, find that
[TAA|Cass 6] P(Case 6}
(1 (IA71) (147)) (r+ s 1)e² + ([Wi) r s 192
Σ
(1 - N) tr- 21?!
(y + a(1 - -2)) (-y uzz)
(63)
24

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Case 7: X 0, X <0, X2 0, v(X; X,, 1, V (X,, (2)) -4.
We obtain that
B[A1|Case 7] P( P(Case 7}
I IN?
2 (1499)
Σ
Σ
((+ 1)et + ([Ni) -r- - 1)e
(1 - 2) t--t - (y + m(1 - -2)) (-y + uz).
(64)
Case 8: X; < 0, X X2, <,, VXX,, ,(, =t.
Correspondingly, follows that
B[Ai|Case 8]
P(Case 8}
( 22
Σ Σ
(r+ o (Wil 8)e-t\2 (1 (1==) -1MP1-r-s-1 3 (-y + pz)
(65)
Next, substituting Eqns. 58-65 into Eqn. 57, we have
F[Ai] [E[ Case 1] ((Case 1} +... + F[AA Case 8) P(Case 8)
W W
(IT ((A7I) (1- 22)))///++---- 2/A? -
Σ
w.h.p
((r 8)et + ((Wi) r 8)e-1)2
(66)
r=0
(1 - z). (e u11 2) +e t '-y + uz))) 2 + (e (e- + ((1 2)) + e c'(-u+ 2
where (i) holds since Lemma 2 ensures that [Wa] = m(p+t) (1+
Vogn 10
= w())
F.1.2. CALCULATION OF [b]
Likewise, we categorize the discussion into four distinct cases as
-| 2 0,X, 2 PXX 0, 2 E > 0,X, < 2 0.X, <0}
(67)
+ E < X, 2 0] P(X, < <0,x, 2 0} + |X < 0, <0) < <0,x,< <0).
With the definition of event A,s in Eqn. 36, follows that
IAP IT
E[AA/X 2 0, 2 0J P(X, 2 0, 0, 0)
Σ Σ ELA4A, P(Ar.)
W (WTI-1) (1 2 | Σ
Σ ((++ 1)ee + (WW r 19- (1- z)e2t 1 x3,5(Xn) dXa.
(68)
I [
(I11--) (17)) (1 - 2) + 2/N7 -rts-
Σ
w.h.p.
((r s)et + (WW)) - r- 59-
2) 21 (uy 21 2) + 01 (1-2)) -2)),
where (i) follows from Lemma
25

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Similarly, the results for the remaining three cases are follows,
E A2 ; 2 O, x < 0| PfX: 2 0, x < 0}
ANT - WY
(M ( ) (1 - ,
w.h.p.
Σ
(69)
((r s)et + (Wii) - -
P= S
(1 2) 2) 2t "(-py 1² 12++00 0²)))
E| O, 2 0) P(X; < <0,,, 20}
NP
WT (MTI (1 (1- 2)W -/A7
w.h.p
Σ
(70)
((r + s)et + (Wi -r-
-1 22 (uy + 1²(1 2) + o -2)),
|[ < 0, <0 P(X, < x, <0}
- (1 (V (1 ,
who.p Σ
(71)
((r s)et + r -
(1 (1- 2) 2). 2 (-uu + 2²2 + 0²2).
Subsequently, by integrating Eqn. 68 and 71 into Eqn. 67, we obtain
N 1
(IA!I-))
( ((N2)) (1 - 2)) 2/11 |
E
w.h.
Σ
((r+ (IAG) r (r--)e--a t)2
==0
(1 (1- (1-21 2) (e2 (c 1² 2) + 02 1122) =))) +o (-
12 +2 d²z)
(72)
(e (uy 2 2) + 02 =))) + (- 1²= +222
Next, substituting Eqn. 66 and 72 into Eqn. 56 yields that
F[AA] 1 WFl) F[Ai] WPI F[A2]
( - - (3.
w.h.p
(1->) -) (c(( p(1 - =)) +e te (-v nz)) 2 + + =)) + +e
e e
uz)
+ +WNFI (1,,4177111777
(73)
(1 (1-22) (e (ny + 1² - 2) -21 [[)] - - + 1² 2 (222+022))
( 2t (ny + p² 2) + 02 2)) + + (-My + 2² x22++²²=))
where $ (=,t, is defined in Eqn. 17, and (i) is due Lemmas and
26

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
F.2. Calculation of [[]
The calculation of B follows the exact same steps as that of E[A]]. Initially, leveraging the independence of the node features, decompose the entire expectation into the expectations of two distinct types of random variables, indicated in Eqn. 56. Following this, calculate the expectations of these parts separately through different cases. For the sake of succinctness, we provide the final expressions directly as follows,
E| = - -
who
(1 (1- (d'0 μ2)
a(1 m(1- +
+ WN3 (,, (
(74)
(1 (1-2)- (ett (- 12= 0²2) + c (ny + (2 2) + 02 - =))
+ (6-21 (-py + p² + 0²2) + 2t kny + 2² 2) + t =)))
F33. Calculation of [[[]
First, due to the independence in the generation of node features, we have
X X2, e (Xxx)s)) . (((,))))) (EiENp (((..x))) + EVENy eV(X))))))
E| 2| E
(75)
where ja E N? and j2 E N!"
Then, similarly, we divide X,, X₁, and X,, into eight cases as shown in Table 1. The only difference is that the distribution of Xj2 changes to N(-H,, 2)). After calculation and simplification, we obtain
E who.p 2/NTIIN?1 (7,,1177111177
( (1-2) 2) (d(y (11 - 2)) te '- uz) 1(1 - =))))
(76)
+ z (e-(y) + p(1 z)) + (-x uz)) ((e uz) + +e'(y (g- u(1 - -2)1))
Thus, using Eqns. 73-76, we can obtain the final result for (E(()))) as (E(()))) = [[AA] + E[B] + E.C].
27

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
By incorporating the above results into Eqn. 54, we finally obtain
Var(X;) = [E(x + + [
II (INP ((N2)) - (1-2) -1-=)))(t+5.
(LAT12-1W?7)) - |
w.h.p.
((r s)et + (LV1) -r- -r-))e-jp
0
(1- 1(1 - 2)) + (-v+ (1==)(e0++00=2))+=
2 + +2 + - 2)) + cd me))) 2)
( IN
(1 - =)) ,
+ W
ΣΣ
((r + s)et + (IVi -r s)e-t)2
r=0 ==
(1 - 2) (e2h. (ny + 22(1 - 2) + 0²(1 - 2)) +e 21, + +1= + 0²2))
+ (c-21.
+ + 2t (wy + 1²(1 z) + o²(1 - =)) + + (- +==2
IN I
(INT)) (1771) (1 - zIN? -rt
+ 22
ΣΣ
(I s)e² + (( - - 89e-
0= 0
(77)
(1 (1-2) 2)
+ ((()+((1=)))++c
+ -
( uz)) (c=(-y-nz)++ to (v- 101 - =)))
+ 2 (e + p(1 - 2)) + + + nz) ((e - uz) + c' u(1 - =2111)
+ (WW7 - Wil) IP N (I
(1 2) -21
((r + s)e¹ + +(WV11 - - s)e
(1 - =) (6 - pm) + te (- - 1u1 - =)))} 2 + = s(c c - w2) + -e(())-((1-1-----
| N
(MTTI) (1 (1 - 2) 2|471-
+ W Σ Σ
((r + s)et + (WWi) - r s)²-
0= 0=0
( (1 (1 - 2). (2²t. (-ro + 12z + 0²2) + 2- (mu + (2(11= - =))+ 01 - =)) (1))
2 (o 20-21 (uyy + 12 + 02 2 2h (ny + 21 2) 01 (2)(( .)))
-1 (INII-I) (W71) (1 - 2) 1 -- (1==))(=.0+=a(ce--))
WTT +(W?
ΣΣ
(r+ s)e + (1V1 - r s)e-e
INT I -1 ( - 1- (1- (1-=)A(zz, -t) +1)+ -1)+
+ W Σ
(r s)ct + (ING - s)e-t
S (2,t, WPLIWND) (2...111171111
where (i) follows from Eqn. 49, (ii) is derived through calculations and simplifications utilizing Lemmas 5 and 6. The
terms (2,4, 4, LVP) I. (V and T 2, 4 WV (V71) are defined in Eqn. 17.
28

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Similarly, if node Co. due symmetry, we also have
Var(X;) who.p (N, (311,,
(78)
The conclusion variance in Theorem 2 is hereby proven.
G. Proof of Corollary 1
This corollary consists of three statements, and we will prove each of these statements individually.
G.1.
When = 0, for the expectation part, we have for every node
WI
(LA? (IA71) (1 2)
S (2,1,,
Σ
(r s)c² + (111 - 5)e
W I (A27))
(1 - 2)1 2/N? 1
Σ Σ
(79)
WW
z 2) 2IIIIN
Wi
Substituting the above result into Eqn. 53, get
μ' = S (NPI,, g(,, (WD)) (WVP) (W F
( P
(80)
[
w.h.p. p
where (i) follows from the high probability event A3 in Lemma 2. For the variance part, when / = 0, straightforward calculations calluactoo yield
(AT)) (1 2) No
3 (2,1,117
IN11--3,
(81)
and
7( 2, (.7, = + -2 W (ii
(82)
According to the high probability event As in Lemma 2, we further obtain
0² who.
0².
(83)
M
n(p
9)
G.2.
When SNR = (l) for expectation part in the second statement, we first show that the following equation holds for every node i,
= INP ((,,,,
S
W +1+
(84)
Define
g(r,8) 8) (IN77) (WN)
(W?)
(1 (1- 12 -WPI+o- (r+ + (IN -r - ste-
(85)
Then we have
IN II
8 (=,,6,177) = Σ Σ g(r,s).
(86)
29

---

=llogn) Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Thus, Eqn. 84 indicates that the summation of the sequence S (z, 1, [V]], I I dominated by one of its terms, specifically the term with [A?] and
0. To prove Eqn. 84, it sufficient show that the following equation holds
g(r 1,8) w (g(r, and g(r 8 + 1) = (
(87)
Note that this statement assumes that SNR = 11/0 = (olVog by Lemma 3, we have
S x
=0nn² 1)(
(88)
Hence,
(IAP))
g(r + 115)
(r 1 8 + 1)et + (IN 8 1)e- -t
(r41)
1 1-2
g(1,8) (r + s)et + +[Wi - 8)
(IA71)
2
(89)
1-2 (18) w(n)
= w(1)
W
where is a bounded constant, (i) follows from the fact that W S ((())) S !V? and (ti) is due to Eqn. 88.
Similarly, show that g(r,+1)
o(1). Then Eqn. 84 is proved. Next, since //o w( v log n)) can derive through
simple calculations that g(ri))
4 WT e'u - e - 'n(1 + o1)).
(90)
Hence, by combining Eqn. 84 and Eqn. 90, we have
= (1 (I=))M((N (1+o(1)
n¹ = S (
+ W99
(91)
i 1- 1- (IW7) e'u W 1
(8) pe ge
INPle* + |
(1 (1+)(1))
whhp pe + ge
where (i) is due to the fact that o(n and [Wa] n, (fi) follows from the high probability event As in Lemma 2. For the variance part, we first define
(IN22) (1991) (1-z) 2) -WPl+oor r ((r + s) ((Vil - r s)e
8(),8)= A
(92)
Then
IN
3 (7 Σ Σ g(r,s).
(93)
Following the same steps as Eqns. 87-89, we can deduce that
@(r + 1,s) = (g(r,)) and Ø(r, + 1) 1)= 1))or((r)s)
(94)
This implies that the summation of the sequence S (2, t, NIIINN is dominated by one of its terms, specifically the term with = IN? and = O. Then we have
(1 (1-z) Val
$ (E, (IAPle' + Wile--p2 (1 + o()) +1+)
(
(WAP + WM (1 +1)),
(95)
where (1) is due to Eqn. 88.
Next, since u/o w(Vlogn). we can derive through simple calculations that
4 (WNP 2t + - (1+ o(1)) (1))
(96)
30

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Hence, (o')2 is given by
( (2,t,, IWT) T(2, (TTW,
|NT + + (LV? et + W (1 (1))
@ pe + qe qe-
(97)
whop (pet + ge ge-tyz
where (1) follows from Lemma 2.
G.3.
When SNR = (11 and 1 = O(1), for expectation part in the third statement, note that SNR = 11/0 = (1)) then with high probability z = 1--2-- = 3-
First, we establish the bound for S (2, t, INTI,WN) as
I I
(I?
(
W
(W!
(
Σ
I
<
(98)
Wile
2
[M
2
[
-
W
==0
==0
Since / = (()) the above bound also implies S 1, WND = @(LGG-)) Next, through simple calculations, we
obtain
y. y, L e' +
2 (IW71 ((7 p- - 1)
(99)
Hence, by Lemma and Eqn. 98-99, follows that
= Sz,4 WTD TT,,, v. 7T.. - o ((-V. | W
w) =0 ( 9
(100)
M
p
As for the variance part, note that SNR u/o o[)), then with high probability z 2
Following the same step as Eqn. 98, we establish the bound for 3 (z, t, INP], (V7I) as
1
W2 2 S ( < W e-
(101)
Since / = 0(1), the above bound also implies S (2,4, ( (W = 9(I Next, through simple calculations, we get that
(7,,,41111117 = (INPP+INTT) (e' (e'- + (IN71 + (W7))
21 + 22-
02. (1++
(102)
2x
2
Hence,
-8,,,, 7. @ o -((a-(e--- n(p 9) )00
(103)
where ej and 02 are positive constants and (i) is due the high probability events in Lemma 2.
H. Proof of Lemma 1
Firstly, we have
1 1
T
/ n E - X)²
(X)
X
XI1
(104)
Vn
where X is the mean value of all node features.
31

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Based Lemma 2, approximately half of the nodes' features drawn independently from N(,, while the other half are drawn from N (1-1,,0), d). Consequently, X N(0, r²) ).). As n tends to infinity, we can approximate that X; - X ~ N (2(c, - 1)1, o for each node i. Thus, we obtain that, with high probability,
E[(X; - x) Var(X; X) B X| = 1¹² + +0²
Var((X; x
x) [X: x)
(105)
( 30 + 61²0²² + - (1² + 0 20 + 40²
where (i) follows from the calculation of the moment of Gaussian distribution (see page 148 of (Edition al., 2002)).
Note that, it suffices to prove Σ
-i=l (X; - x equals to n(f² + o²) with high probability. Next, we apply Chebyshev's
inequality to bound Ei=(2 (X; - X)2 as follows
(20* + p2)
P Σ (X - Xx-
+ + n(p
nT S
(106)
nr2
Setting r = (4² + /² Vlog n, then we have
P n(p=² + 0²) (1 1
n
S _ (X, 8)2 s n(u²² +00)-((
Vlogn
Vlg
(107)
2 1 logn- (20+ + 40²
n 1122222 + 02)2
which implies Ei (X, x)² who. n(y² + 0²).
I. Proof of Theorem 3
According to Theorem 2, for GAT layer, when the input node features follow Gaussian distribution, can precisely compute the expectation and variance of the output node features. Therefore, when = O, i.e., the graph attention layer degenerates into a simple graph convolution layer, the attention coefficients become independent of the node features, and the output node features of each layer still follow a Gaussian distribution. Subsequently, according to Corollary 1, for an T-layer GCN, we have
w.h.p.
P (P-1) (
14
(108)
where E [L] denotes the (-th layer and μ indicates the expectation after the I-th layer.
When SNR= w( (Vlogn), according to Eqn. 20, the graph attention mechanism is capable to distinguish all intra-class and inter-class edges with high probability. Consequently, the attention coefficients can be approximated as independent of the node features: setting the attention coefficient to et for all intra-class edges and to e- for all inter-class edges. Thus, the output of each layer in multi-layer GAT also follows a Gaussian distribution. Similarly, according to Corollary 1, for an L-layer GAT where the attention coefficient is the same for each layer, we have
(pe" ge ge-1 pet + ge-
(1) whop
μ..
(109)
According to Lemma 1, we know that 7(X) v22+ Note that we consider the case where SNR= w(V n). According to Corollary 1, along with Eqn. 4, the SNR decreases after every GCN or GAT layer. Therefore, it follows that, for every E [L], () = , (1 ((1).
Then, by Eqn. 108, for an L-layer GCN, we have that for all l E [L]:
(xx)) () (1+ o(1))
(p-g) n. (1 + +(() = (1
29
) 1(1 + o(1) s 26 lo (0/(1-2//tt)))pp..
(110)
p x+g) t
32

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
which indicates that the over-smoothing problem will arise.
For an L-layer GAT where L O(n) and sufficiently large attention coefficient, i.e., t w/ (olllggm) n), Eqn. 109 yields that
7(x")= = pe ge- pet + qe
p. (.(1+
(III)
peat + ) μ 1. (1+ @ (nn)-1)000 O(4))
29
which indicates that the over-smoothing problem is resolved.
J. Proof of Theorem 4
According Theorem we know that a single-layer GAT can achieve perfect node classification when SNR= w( (Vlog n)). Furthermore, from Eqns. 4 and 5, understand that over wide range, GAT by adjusting the value of I. Therefore, considering a simple case where / = O, and the graph attention layer degenerates into a graph convolution layer, we have the following lemma based on the work by (Wu et al., 2022b).
ensure increase in SNR after one layer of
q blog² n and > b > O are positive constants. Given an L-th layer linear GCN with each layer being defined in Eqn. 6 without the non-linear activation function, let jl and g0)) be the expectation and variance of the output node feature after the 1-th layer. For log
Lemma 7. For featured graph generated from CSBM p., o), suppose p alo"" n
=0 log(blog' ) the following holds with high probability:
①) 10 ( n4
(
(ii). (0²)
(c2 log n)) o
(112)
a
where C1, are two positive constants.
Proof. See Appendix K for the detailed proof.
Based on Lemma 7 and Theorem 1, we consider multi-layer GAT network where the first L layers use t= = O, and the (L + 1)-th layer sets t to a sufficiently large value. To achieve perfect node classification, it is sufficient to ensure that the expectation and variance of the node features after I. layers satisfy /g()) w( w(ylogn). Note that, by setting and using Eqn. 112 follows that log(b log n)
(L)
h-b
(V22 log n²
(c' log n) lou m)
log
(log 11) Tlog
n p
(113)
(L)
Voi
b)/(a where d' -ozla-b)/( + b) is constant.
Hence, to satisfy the condition (o(t) w( w(Vlog)) n), sufficient to satisfy condition n² -/o w(vlogn) n), i.e.
SNR w(Vlop / v). This completes the proof.
K. Additional Proofs of Lemmas
In this part, we present the proofs for several lemmas that are utilized in the preceding proofs. For clarity, we restate each lemma before presenting its proof.
Lemma Assume random variable y (0, 1), then for any constant > 0, the following tail bound holds,
2
1
P④y 2 s) = (ss) s min
2
(114)
8V
2T
33

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Proof. We first prove the former part of the tail bound,
+00
Ply 2 8)
=
dy
V
(115)
4.00
1
[xta)
2
dy.
2m
For any y 2 0, we have
(v x)
v +2
e
2
(116)
3
T.
Hence,
1
Ply >
E
dy
12T
+000
x2 dy
(117)
V 2m
1
e
2
Then, we give the proof of the second part. Note that
+.00
Ply
> 8)
dy
V2T
+.00
y
1
dy
(118)
8
V
2m
By integrating Eqn. 117 with Eqn. 118, the proof is completed.
Lemma
Assume a random variable i ~ N(Ju, with (() being the probability density function of x, then
Jo xf(z) dx = a
+ 1 (5)
52x" E
(119)
[ xf(z) = 22n
20
+ w (#),
and
Jo 1ot²0 fl)(x) dr = / 2e
+ 21
1 (M) + 0 2 - (4) (t) 26 (1) + +o+ क
(120)
1m xff()
2 - केन
+
Accordingly, a (N-H,, then
2
1 :f(x)
20 - μ (6)
V2
(121)
xf(x
2
(1)
V2n
and
1ot / xf(((x) dæ -
+
+22 (1)
+ +
(122)
dr 11 11/3
+
- + (4)
+ (5)
34

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Proof. Here, only present the proof when x Nu, oe), the proof for the other case can be obtained similarly. Note that
|
1.00
(z-w) 2nd
=f(z) do
x
dx
0V2T
2T
1
12-
+00
1
(z-w)²
(1)
dx
+
1
dx
(123)
2m
2/
.0
fa
20
1 1
14
20
2²
+
1
1
10 (
v 2m
2m
Likewise, we have
xf(z) de
2² 2x
+
p
(m)
(124)
2
Next, Eqn. 120 is obtained by
l x² f(x) dx = / (I²
dx + 10000 2xp f(x) dx - 12? 1/ f(x)
12) 1xpp +
20p
(125)
= -fo (x- (w- sx)) de + 2pl
to0
_ E-
o
2o0 + (1 - $ (4) 12: (1- 1 (H))
12T
and
0 (00(0= (x- 1z2 dr
1
(=-wi² dr
(x - 11)2
e
0/2
0
(x 11)
(e (--1---) ) dx
V2T
0
(126)
0
(
+00 σ
(--w²
+ 0
2n
dx
2
2t
11
e
207
2
0²
(1
(H))
(t))
2m
Hence,
2² f(x) dr
0 e 25 + (1 - 1b (5) + 2/
- #
+
1 (-)) 12. (2 (
(127)
2m
22T
22
n²² (1 1 (m) ) + o² (1 $ (=))
25
2m
Similarly, it can be calculated that
L 22 f() dr = -4 σ
2
+ 4
2
(g) + 2 (5)
(1)
(128)
V2T
Lemma 5 Assume 0 < < 1/2, for any constants t > 0 and le > 0, let
m
(7) 2) -i
I(n, m)
<= jmn (i+j)ee + (n + m - - i-j)= j)e 1)k-
Then the following equation holds
lim n.m n.m-+00
T(n + 61, m + 62) T(n, m),
(129)
where ej and 02 are positive integer constants.
35

---

Graph Attention is Not Always Bencficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Proof. Our approach the proof starts with establishing the boundedness of the sequence [(n,m) Subsequenty show that the sequence monotonically decreasing in both n and m. Then applying the Monotone Convergence Theorem (Yeh, 2014) is sufficient to complete the proof.
Firstly, since t > 0, it is important to note the following facts that
71
m
(1
22)
n = (1- x x++
(130)
and
x)) -
(T) -
S (n, S Σ>>
(131)
(n + m) cht
(n m)) c-ke
f=0
Thus, [(n, m) is bounded by
(n e I m(n.m)
(132)
(n + k
Then, for a positive integer constant C1, we have
n+o
Σ
m
ni
C1
(m)) ( (1 - z
m
(1 2) - 1.
(133)
i
1=0
0=
And, for any i,j.
(134)
+ j)et + (n + + m -
jje- - (i+ + (n + m - j)e
Hence, [(n m) < m(n,m) holds. Likewise, assuming another positive integer constant cg2 can be deduced that
T(n + 01, m + 02) < [(n, m).
(135)
Consequently, for the sequence I'(n, m), Eqn. 132 and 135 guarantee both the monotonicity and the boundedness of the sequence. By the Monotone Convergence Theorem, it follows that the sequence converges, which also ensures that lim I(n + C1,71 m + c2)/T(n,m) =.
(1-2) 1-
Lemma 6 Assume 0 < x < 1/2, for any constant & > 0, we define A(n, m) En Ey
((++ fo+m- ((tt))e+(tttmm---e -5e
and m) e (E = [1))eeaatm-i-j)
Then, for + to0, have
A(n, m) = ( ((n++)) B(n, = @(n + m)) A(n, m) B(n, m) = m
Proof. Define ay - cn + m) + (e () j),, by e (7) m and [n]] x [m] = ((i s
i S n, S < m, i.j 2), [n] x [m] [n] [m] ((1.f1,12,j2)) S is S n, S je S m, it, Jr Z, (1,2)),
then we can rewrite:
A(n,m) E
bi
B(n,
Σ
bij
a
aij
(1.5)|1) x[m]
(l
36

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
Firstly, note that (6.))[[]xxmm) ml]
Σ
by
this:
!1 m (m) (1 2)) -.
Σ (1
bij
Σ
(1) (0)
6.j)e/m]
Σ
10 (1 2) =))=m=)))
(m) x o1 mmm-))
(x x [m]]
n1
x) x n-
Σ
m
x² (1 - x) =)m
1=
x-))
By definition, it is clear that (n m) s azj S e' + m), then:
by
26
2t
IA(, =
bij
(n m)²
(n + m)
(iJ) (m)
(KJ))(n) x [m)
bij
2-
e-2
(A(,mm)
Σ
bij
(n m)²
(n + m))
(L.))[m]x(i))) im]
Hence, A(n, m) (m)+m))+ Now we show that |Ann, m) (nn, m)) can be upper bounded by r01(1=2)(1 + m key observation is that big P(X i,Y f), where X and Y follow from two Binomial distributions, i.e., X ~ Bino(n, 1- 2), Y Bi),(m, while X and Y are independent:
2)
AA(n, m) B(n, m)
=|
Σ
bij
Σ
bij
agj
[mmm)
(K.) x(m)
bys Csj
Σ
bis) - Σ
(k.))E [m)
birh Vbinia
Diesa / /bennr)
Σ
2
aiisi
aizja
(1 [m] (2))2)))))x(m) m)
Σ
bi Dinsal
aiysi
0igg2 )2
2
aiiji Giajz
((2.j2)E(n)xipp [(m]
1
Σ
bisn bigja
(e' - ( +ii)= (i2 -22l
2
Oi Aizja
(6 (E ((2.da)e|n]x(m
(136)
37

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
e00
Σ
be bestell + 51) (d2 j2)]
2(n
m)
( x (ta.ja)ffn)x(m)
c
(65e)
Σ
P(X1 -1: - = 12, Y22 = =22]((1 + +1) (d2 + j2)1?
2 + m)4
61 J x [mm] (KaJa) (n) x (m)
e
[[((X, - -22 12)
2n m)
(Kv)
cbt
Var(XX) + Var(Yi)) E
(n + m)
(n + m)s
Here is some notes for the above proof: (i) Apply Lagrange's identity; (Mi) Plug in a,Ii (Hii) using previous observe for bij- where X₁ ~ Bino(n, 1 - z), Yi Bino(m, 2), 1 E {1, 2} and they are independent; (iv) Linearity of Expectation.
Finally, given A(n, m)) = ((nn + m)- and A(n, m) - B(n, m) = o((n + m)- it is casy to see B m)) ((n + ?)) so we finish the proof.
Lemma 7 For a featured graph generated from CP 9, 1t, o), suppose a
blog x and a > > are positive constants. Given an L-th layer linear GCN with each layer being defined in Eqn. without the non-linear activation function, let z' and (t)) be the expectation and variance of the output node feature after the l-th layer. For log 12
L == 0 log(b log" n ). the following holds with high probability:
1. n (a- (a-b)) (a+b) M. 2. (03)())
C1 (02 log* n)
(137)
where C1, are two positive constants.
Proof. The proof of the first part in Eqn. 137 can be directly derived by substituting the values of p and q into Eqn. 108. For the second part concerning the change in variance, refer to Theorem from (Wu al., 2022b). By substituting the values of) = a log" and q blog we obtain
C3
0² I {0))(())
C4
(138)
(la log"
2 n)
(a log n)
where Cz C4 are two positive constants. Thus, apparently, there exists two constants e1 E (a, + b) and C2 > 0 such that (0²)(1) log-log"""""
The above equation demonstrates that using multiple layers of graph convolution can reduce the variance of node features. However, Theorem 2 in (Wu et al., 2022b) also indicates that this improvement is only effective in the initial layers. Specifically, the proof of Theorem in (Wu al., 2022b) reveals that the enhancement fundamentally arises from incorporating higher-order neighbor information. In the context of random graphs, we can estimate the graph's 's diameter, which allows determine the maximum number of hops between any two nodes. This estimation consequently indicates the upper limit on the number of graph convolution layers (i.c., the value of L) that can effectively reduce variance.
For graph G generated by the above CSBM, let diam(G) (G) denote its diameter. According to Theorem 7.2 in (Frieze & Karoński, 2015), we have
w.h.p.
log n1
diam(G)
(139)
log(b log n)
which means the maximum number of GCN layers that can reduce the variance of node features is L. O(
log n log(b
38

---

Graph Attention is Not Always Bencficial: A Thcoretical Analysis of Graph Attention Mechanisms via CSBMs
Classification Accuracy
1.0
GCN
Classification Accuracy
1.0
GCN
Classification Accuracy
1.0
0.9
GAT_
jmlr23
0.3
GAT jmLr23
GAT ours
0.8
GAT_ __ors
0.7
0.7
0.0
0.5
0.4
GCN
0.4
GAT jmlr23
0.3
GAT _ur_
10
10-3
10-h
10-1
10-2
10-1
Distance between means
Distance between means
Distance between means
(a)
(b)
(c)
Figure 3. Additional experimental results on real-world datasets. Figures 3a, 3b and 3e illustrate the results for the Citeseer, Cora,
and Pubmed datasets, respectively.
Table 2. Dataset characteristics.
Dataset Number of Nodes
Number of Edges
Number of Classes
Feature Dimension
Citeseer
3,327
4,732
6
3,703
Cora
2,708
5,429
7
1,433
Pubmed
19,717
44,338
500
ogbn-arxiv
169,343
1,166,243
40
128
Table Comparison of running times for GCN, GAT-jmlr and GAT
Method
GCN
GAT-jmlr
GAT*
Runtime (/s)
8.63
10.03
8.93
L. Additional Experiments
L.1. Comparative Analysis of Our Graph Attention Mechanism and Fountoulakis al. (2023)
We conducted additional experiments on three real-world datasets (Citeseer, Cora, and Pubmed) compare the capabilities of our proposed graph attention mechanism with the mechanism from (Fountoulakis et al., 2023). The characteristics of the datasets is provided in Table 2. The experimental setup mirrors that used in the experiments from (Fountoulakis et al., 2023). Specifically, the three datasets contain multiple classes, and in each experiment, we perform one-vs-all classification for a single class, converting it into a binary classification problem, as our attention mechanism is designed for binary classification. To control the mean node features across different classes, we compute the mean of the features for each class using their labels and then adjust the features of nodes that class by subtracting the mean and adding either y or -4.
For the three datasets, we classify the O class in one-vs-all manner and record the classification accuracy for that class. The training and testing set splits follow the default settings of PyTorch Geometric. We designed three models: graph convolutional network, GAT network utilizing the attention mechanism from (Fountoulakis et al., 2023) (denoted as GAT-jmlr), and a GAT employing the attention mechanism defined in Eqn. 12 (denoted as GAT*). Each of these models incorporates a single attention layer. In GAT-jmlr, the parameters / and are set to 0.2 and 1, respectively, while the parameter in GAT* is set to Figure illustrates how the classification accuracy the three models varies with changes in the distance between the means of the node features for the two classes. From Figure 3, we see that when the distance between the means of the node features for the two classes is large, indicating low feature noise, GAT* performs the best. In contrast, when the distance is small, suggesting high feature noise, GAT-jmir delivers the best results. Overall, GAT significantly enhances GCN performance, especially under conditions of low feature noise.
Additionally, Table presents the runtime of the three methods. For the three datasets, we set the number of epochs to 100 and ran each dataset once, recording the total time taken for all runs. Table shows that the graph attention mechanism we designed slightly more computationally efficient than the one presented in (Fountoulakis al., 2023), which confirms our
39

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
analysis in Appendix B.
L.2. Additional experiments on obgn-arxiv dataset
To further substantiate our theoretical findings, we conducted additional experiments on a larger dataset-ogbn wwwrocgnnarxii--iiee arxiv-and employed more advanced graph attention mechanism, GATv2. Specifically, we evaluated the performance of four models under two types of noise: feature noise (fn) and structure noise (s,)) The four models are: GCN, GATv2, GATv2*, and (tTv2) Here. GATv2* denotes a hybrid architecture that uses graph convolutional layers in the first two layers and a GATv2 layer in the final layer, similar to the GAT* model described in 4.2. (tep)) extends this architecture by introducing a tunable temperature parameter = 1 into the softmax computation of the attention coefficients, allowing for precise control over attention intensity. In our implementation, the values of T are set to [2, 2, 0.5] across the three GATv2 layers. Feature noise (fn) is introduced by reducing the expected distance between node features of different classes, while structure noise (s,,) is added by randomly perturbing graph edges. Both fn and 8n take values in the range [0, 1], with larger values indicating higher noise levels. The accuracy heatmaps shown in Figure 4.
0.7
0.7
Structure Naise Level
Accuracy
Structure Noise
Accuracy
0.5
0.5
0.4
0.4
Feature Noise Level
Feature Noise Level
(a) Results of GCN.
(b) Results of GATv2.
00.
007
Structure Noise Leve!
Accuracy
Accuracy
0.5
0.5
Structure
0.4
0.4
0.3
Feature Noise Level
Feature Noise Level
(c) Results GATv2*
(d) Results GATv22((emp).
Figure 4. Accuracy heatmaps of models ogbn-arxe under varying structure and feature noise levels.
From Figure 4, we observe that (tep)) achieves the best overall performance. Moreover, methods incorporating attention mechanisms exhibit significant improvements when structure noise is strong and feature noise is weak. In contrast, when feature noise dominates and structure noise is minimal, the performance gain is marginal. This observation is broadly consistent with our theoretical results. However, there is subtle discrepancy: according to theory, attention based methods are expected degrade performance under strong feature noise and weak structure noise. Yet, in the figure, these methods
40

---

Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via CSBMs
do not show notably worse performance; instead, their results are comparable to those of GCN.
To investigate this discrepancy, we visualized the attention coefficients of the GATv2 model under conditions of high feature noise and low structure noise, focusing on the nine nodes with the highest number of neighbors, as shown in Figure 5. We found that in this setting, the attention mechanism assigns nearly uniform weights to all neighbors through its learnable parameters, effectively degenerating into graph convolutional layer. This indicates that GATv2 possesses stronger learning capability compared to GAT. Importantly, this behavior does not contradict our theoretical analysis, which is based on attention layers without learnable parameters.
Additionally, we visualized the attention coefficients under the opposite setting-strond strong structure noise and weak feature noise-and found that GATv2 assigns highly differentiated weights to neighbors. This selective weighting highlights important neighbors while down-weighting noisy ones, thereby enhancing the model's final classification performance.
Neightor Weight Distrbuution with 0.0
Meighoor Weight Distr with fum Noighoor Weight Ditty lbution with Jq 0.8
Neighber Weight Distribution with 6. hoightit box Weight Disatibution with Sy 0.8
Noighoer Weight Ditrr butian ie 0.2
3060
4006
Neightora of Nodel No. 13553
Neighturrs of Nrdclee Mos. /1bb (b) Node No.67166.
Neighbors of Node No. 2010 (c) Node No.
(a) Node No.1353.
Neighbor Weight Distr buutoon with fu- D.B Neighoor Weight
Neighoor Weight Distr bution with f-- 0.8 Neighter Weight
Neighbor Weight Distribution with 6. 0.8 Nanghbor Weright Distribation with
Poluabiity
Neighbors of Noce No. 09794
Neighbors of Noce No. 93649
Nelghbors of Node No. 115359
(d) Node No.69794.
(e) Node No.936-49.
(I) Node No.115359.
Neighbor Weight Distr Distribution with f,= 0.B Naighber Weight Datr louiian with Aq 0.
Neighoor Weight Ditry bution with f,- 0.8 Naiigoer Weighe Datr bution with D.B
Neighbor Weight Distribution with f, 0.8 Nanghbor Weight Distriution with C..
4c/o
33000
1200
1300
1300
1400 Neightorr
44/00
No: 22035
Neightbors Nio. 133378
Neighborrs
103899
(g) Node 22035.
(h) Node 133777.
(i) Node N6.166425.
Figure 5. Comparison of attention coefficients under high feature noise (fnn = 0.8) and high structure noise (sn, 0.8) on the ogbn-ard rxi i v dataset. The visualization is based on the last layer of the GATv2 model, focusing on the top nodes with the highest degrees.
41


Reviews:
[{"review_id": "iN3BTgEgED", "reviewer": "Reviewer_JGKV", "summary": "The paper theoretically analyzes the effectiveness of graph attention for node classification tasks in graphs with a CSBM structure and varying levels of feature and structure noise and conclude that high feature noise renders graph attion ineffective whereas graph attention is beneficial in the case of low feature noise and high structure noise.\n\n## update after rebuttal: \nI thank the authors for answering my questions and appreciate their efforts in providing further results during the rebuttal. While I am not too fond of tuning another parameter (t) for each layer in the model, the concept of attention intensity is interesting and perhaps it could be possible to make it learnable in the future. Also, while it intuitively makes sense that the attention coefficients would vary more when a node has a more varied neighborhood (possibly due to high structure noise), a rigorous theoretical analysis to back it is good. Secondly, attention coefficients do not necessarily always learn varied and sparser patterns due to trainability issues. In such cases, having an aid such as an attention intensity parameter to improve the attention mechanism could be promising. Therefore, I have raised my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments. In response to multiple reviewers’ suggestions, we have added experiments on a larger dataset (*ogbn-arxiv*) and five heterophily datasets (e.g., *roman-empire*). Please find the details at the following link https://drive.google.com/file/d/1ALWkkazk1LPjaWSSkL28RCM7ywOsoBEW/view?usp=drive_link. Below, we address your concerns point by point.  \n\n### 1. **Practical Benefits in Real-World Scenarios**  \nOur conclusions consider both SNR and structure noise, providing insights into when and how to use graph attention mechanisms. Specifically, by measuring these two factors, we can determine whether to apply graph attention and how to adjust its intensity (see Remark 3 in lines 278-292 and the discussion in lines 369-376).  \n\nMoreover, the SNR of real-world datasets is not entirely unknown. It can be estimated using the expectation and variance of node features for each class. Even if not all node features are observable, we can approximate SNR using only training data. More importantly, the absolute SNR value matters less than its comparison with structure noise, which helps guide the choice and design of GAT. For example, in heterophily graphs with high structure noise, increasing the intensity of graph attention is beneficial. Conversely, if the features of nodes from different classes are not well distinguishable or have high variance, it may be preferable to avoid using GAT or reduce its intensity.\n\n### 2. **Choice of Parameter $t$**  \nFirst, we would like to emphasize that the attention mechanism proposed in this paper is a simplified version, designed to distill the essence of various graph attention mechanisms for theoretical analysis. The parameter $ t $ controls the intensity of attention and is set based on structure and feature noise before running experiments.  \n\nConceptually, if we view our attention mechanism as assigning +1 weight to intra-class edges and -1 to inter-class edges before applying softmax, then $ t $ functions similarly to the temperature coefficient $ T $ in softmax, controlling the sharpness of the output weight distribution, where $ t = \\frac{1}{T} $.  \n\n### 3. **Analysis of Heterophily**  \nThis is a great question. For the binary symmetric CSBM model, a heterophily analysis can indeed be performed. When $ q > p $, we can modify Equation (3) to assign a weight of $ -t $ to edges where $ X_i X_j > 0 $ and $ t $ to edges where $ X_i X_j < 0 $, without significantly affecting later results.  \n\nHowever, we focus on the homogeneity assumption ($ p > q $) because real-world tasks often involve multi-class classification, where simply adjusting $ t $ is insufficient and requires more complex analysis. More fundamentally, in heterophily graphs, a key question is whether GNNs’ message-passing paradigm remains effective. Understanding how to incorporate global structure information into node features should take precedence over studying attention mechanisms in this setting.  \n\n### 4. **Experiments and Analysis**  \nAs noted earlier, our proposed attention mechanism is a simple version designed for theoretical analysis and does not include learnable parameters. However, as discussed in point 2, our findings suggest a simple way to improve existing attention mechanisms by introducing a temperature coefficient $ T $ (i.e., $ t^{-1} $) in the softmax layer to adjust attention intensity.  \n\nOur theory indicates that when structure noise dominates, a larger $ t $ (smaller $ T $) is preferable, whereas when feature noise dominates, a smaller $ t $ (larger $ T $) works better. We add this in GATv2, denoted as GATv2* (temp), and show that it consistently outperforms the unmodified GATv2 across multiple datasets, including heterophily graphs (see Figure 1,2 and Table 1 in the link above). \n\n### 5. **Visualization of Attention Coefficients**  \nThis is a great suggestion. We add visualizations of attention coefficients in our supplementary experiments (see Figure 3 in the link above). We find that, for the *ogbn-arxiv* dataset, when feature noise increases, the performance of the GAT-based model is similar to that of GCN, with neither improvement nor degradation. The visualizations results show that this happens because GAT, by learning to assign equal weights to all neighbors, essentially degenerates into GCN. However, when structure noise increases, GAT shows significant performance gains (see Figure 1 in the link above for the comparison). The attention weight visualization in Figure 3 in the link above confirms that GAT effectively filters important neighbors in such cases.  \n\n### Additional Clarifications:  \n(1) No, the preprocessing of node features is the same as in all GNNs.  \n(2) See point 2 and 4 for details.  \n(3) Not all inter-class edges are considered noise; noise is measured by the ratio of inter-class to intra-class edges, $ \\frac{p+q}{p-q} $.  \n\nWe appreciate your feedback and hope these responses clarify your concerns.", "claims_and_evidence": "The authors supports their theoretical claims with proofs and empirical evidence from experiments on synthetic data.", "methods_and_evaluation_criteria": "- While the theoretical claims are supported by empirical evidence on synthetic datasets, their practical benefits for real-world scenarios is not very clear. For example, the authors mention that their findings provide insights for practical applications  such as selecting graph attention based on graph data characteristics and designing noise-robust networks. However, the SNR ratio, based on which the decision to use graph attention or not is to be made, is not usually a known property of the graph beforehand.\n\n- Secondly, it is unclear how $t$ is determined, for instance, is it a learnable parameter or a hyperparameter to be tuned with grid search In the experiments, it is an independent variable that is manually varied. \n\n- Furthermore, it is mentioned that the new proposed attention mechanism is designed with homophilic graphs in mind. While this is a  limtiation in my opinion given the current focus on devising attention  based methods that adapt to both homophily and heterophily [1-4], I would still like to request the authors for further clarification on this, because intuitively it seems that having both negative and positive and negative values for $t$ based on dot product of  of two node feature vectors that signify their similarity/dissimilarity and/or alignment/unalignment could also possibly deal with both homophily and heterophily. \n\n[1] Eliasof et al. Improving Graph Neural Networks with Learnable Propagation Operator\n\n[2] Bo et al. Beyond Low-frequency Information in Graph Convolutional Networks\n\n[3] Mustafa et al. GATE: How to Keep Out Intrusive Neighbors\n\n[4]  Finkelshtein et al. Cooperative Graph Neural Networks", "theoretical_claims": "The theoretical claims seem correct but the mathematical details were not checked in detail.", "experimental_designs_or_analyses": "While the experiments to verify the theorical claims of the relationship between SNR ratio and effectiveness of attention mechanism are well designed, I do think that experiments that show the benefit of the proposed/analyzed attention mechanism on real-world datasets is missing. Is it competitive with the standard attention mechanism used in GAT [5] or its various variants? See review section 'method and evaluation criteria' for  a similar discussion. \n\n[5] Brody et al. How Attentive are Graph Attention Networks?", "relation_to_broader_scientific_literature": "The role of attention in graph learning is of great interest to the GNN community today. While most literature on improving/understanding graph attention is focused on the original GAT architecture or its various variants, this paper analyzes a simpler attention mechanism but provides novel insights into its relationship with signal-noise ratio of node features. However, its applicability in real-world scenarios is not well-evaluated.", "essential_references_not_discussed": "None that I can recall.", "other_strengths_and_weaknesses": "**Strengths**\n\nThe paper contributes to theoretically understanding an important aspect of graph learning, i.e. graph attention.\n\n\n**Weaknesses**\n\nThe analyzed graph attention is different from the mechanism in the original GAT or its variants that are usually employed and the effectiveness of then proposed attention mechanism is unclear in the real-world setting. A more detailed discussion of this is in the evaluation criteria and experiment design sections of the review.", "other_comments_or_suggestions": "• It may be worthwhile to visualize the distribution of actual attention coefficients ($c_ij$) for the conducted experiments to better understand/verify whats going on under the hood (for example, in a similar way to [3]). \n\n[3] Mustafa et al. GATE: How to Keep Out Intrusive Neighbors", "questions_for_authors": "1. For experiments on real-world datasets, are the original node features discarded, since perfect node classification is achieved?\n\n2. How can the value of $t$ be determined for real-world datasets?\n\n3. Are inter-class edges considered as structural noise? If so, is this a fair assumption as it is not necessarily true and also unlikely in the real-world setting with perfect node classification not always being aligned with the community structure?\n\n4. Further questions inline in the review sections of evaluation criteria and experimental design.\n\nEdit: While I am not too fond of tuning another parameter (t) for each layer in the model, the concept of attention intensity is interesting and perhaps it could be possible to make it learnable in the future. Also, while it intuitively makes sense that the attention coefficients would vary more when a node has a more varied neighborhood (possibly due to high structure noise), a rigorous theoretical analysis to back it is good. Secondly, attention coefficients do not necessarily always learn varied and sparser patterns due to trainability issues. In such cases, having an aid such as an attention intensity parameter to improve the attention mechanism could be promising, as shown by the authors in the additional experiments and analysis during the rebuttal. Therefore, I have raised my score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DI5XcOddOR", "reviewer": "Reviewer_QLjj", "summary": "The paper studies effectiveness of graph attention networks in the contextual stochastic block model (CSBM) setting. It builds on prior work by Fountalakis et al (JMLR, 2023) and graph attention retrospective in the same setting. In comparison to that work, the main difference appears to be a linear multi-layer graph attention mechanism with non-linearity at the end, along with an assumed simpler attention scoring function (Eq. 3).\nThe main focus is on theoretical results in this simplistic setting, and trade-offs between SNR (Eq. 2) and inverse SNR relative to over-smoothing. There are several results on over-smoothing, but most compelling ones are in Theorems 3 and 4 which indicate at setting where linear multi-layer GAT might be helpful and graph convolutions suffer from over-smoothing.\n\n### POST-REBUTTAL\nI will not be arguing against this paper and if the other reviewers feel strongly about it, I'm fine that it is accepted.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. Our response is as follows:\n\n### 1. **Additional Experiments**\n\nYou mentioned that the experiments on real-world datasets were insufficient. We greatly appreciate your feedback and have conducted additional experiments on more comprehensive datasets, with the results available at https://drive.google.com/file/d/1ALWkkazk1LPjaWSSkL28RCM7ywOsoBEW/view?usp=drive_link. We select an additional 6 datasets, including a larger-scale dataset, *ogbn-arxiv*, and 5 heterophily graph datasets (e.g., *roman-empire*). In addition to the basic GAT model, we also employ GATv2 attention mechanism.\n\nThese new experiments on the extended datasets validate both the correctness and practical value of our theoretical results. Specifically, based on our theoretical findings (Theorem 2), similar to GAT*, we design GATv2*(temp), which adjusts the attention intensity (i.e., the parameter $ t $ in the paper). We confirm that by simply selecting the value of $ t $ based on dataset and noise characteristics, we can achieve better results than the baseline GAT model across multiple datasets (see Figure 1 and Table 1 in the above link). In the presence of feature noise and structure noise, we plot accuracy heatmaps for different algorithms to make a more detailed comparison. GATv2*(temp) performed the best, particularly under high noise conditions (see Figure 2 in the above link). Notably, we find that the parameter $ t $, which controls the attention intensity, is actually the inverse of the temperature coefficient $ T $ that controls the sharpness of the softmax output attention coefficients distribution (i.e., $ t = T^{-1} $), so we adjust the attention intensity by tuning the value of $ T $ in the experiments.\n\nFurthermore, we observe that when only feature noise was added, the GAT-based method did not show a clear advantage or disadvantage compared to GCN. By visualizing the attention weights (see Figure 3 in the above link), we find that GAT assigned nearly equal weights to all neighbors, eventually becoming a GCN. However, with strong structure noise, GAT successfully selected valuable neighbors and outperformed GCN.\n\n### 2. **Comparison of Proof Techniques with Fountalakis et al. (JMLR, 2023)**\n\nOur work is inspired by the JMLR paper, but the proof techniques we use are significantly different, and we have derived broader and more novel results. Specifically:\n\n(1) **We consider multi-layer GAT, whereas Fountalakis et al. (JMLR, 2023) considers a single-layer GAT.** We must emphasize that this extension is **non-trivial** and involves several theoretical challenges.\n\nThe analysis of multi-layer GATs requires us to accurately characterize the distribution of node features after passing through the GAT layers, rather than simply focusing on the sign of the output, as in single-layer GAT analysis (as done in JMLR23). The attention mechanism used in JMLR23 is too complex to be analyzed in a multi-layer setting, which is why we choose to design a simpler attention mechanism for theoretical analysis. Although this mechanism is simpler, we theoretically prove that its performance in the CSBM perfect node classification task is comparable to that of the attention mechanism in JMLR23, as shown in Theorem 1. The proof techniques used here are the only part that shares similarities with those in JMLR23. \n\nHowever, the core of our proof is presented in Theorem 2, which precisely characterizes the distribution of node features after one GAT layer. This is a significant challenge because, even with the simplest attention mechanism, the process is highly nonlinear, meaning that after passing through the GAT layer, node features no longer follow a Gaussian distribution. Moreover, this distribution is also influenced by the number and distribution of neighboring nodes, introducing further randomness, all of which make it difficult to accurately characterize this distribution. In our paper, proof of Theorem 2 spans pages 17 to 32 of the appendix, and this part forms the core of our theoretical analysis. Finally, extending from single-layer to multi-layer analysis is a well-known challenge in deep learning theory, with related works published in top venues such as FOCS, COLT, and JMLR.\n\n(2) **We also address the over-smoothing issue (see Theorem 3).** This analysis was not covered in Fountoulakis et al. (2023) and involves many completely different proof techniques. We define a new measure for over-smoothing and, using the results from Theorem 2 on the distribution changes of node features in multi-layer GAT, proved that graph attention mechanisms can positively mitigate the over-smoothing problem. We also find that the effectiveness of graph attention mechanisms in addressing over-smoothing depends on the SNR of the graph data. The higher the initial SNR, the more pronounced the role of the graph attention mechanism.\n\nThank you for your thoughtful feedback, and we look forward to further discussions.", "claims_and_evidence": "Several theoretical results but not really sure how realistic the underlying assumptions are and the overall setting, especially in the context of real-world applications and graph attention architectures. Experimental results provided on synthetic data and three real-world datasets. In the latter, there does not appear to be differentiation in performance between GAT* (multi-layer linear graph attention) and GCNs.", "methods_and_evaluation_criteria": "This is a theoretical paper and might be fine with a limited set of experiments. However, these don’t seem to illustrate difference between GCNs and GAT*s on real-world datasets. Proof techniques, in my understanding, are mimicking prior work by Fountalakis et al (JMLR, 2023) and in that regard the contribution is rather incremental.", "theoretical_claims": "I have not checked the proofs carefully, but have skimmed through few of them. What I did checked seemed fine, but there was one aspect that was confusing. The entire analysis seems to be done via the simplistic attention mechanism in Eq. (3). In that regard, the mechanism in Fountalakis et al (JMLR, 2023) while still simplistic seemed more characteristic of what one can expect in GATs.", "experimental_designs_or_analyses": "Limited set of experiments and this aspect of the paper can be improved, especially when illustrating the point on GCNs and GAT* on real-world datasets.", "relation_to_broader_scientific_literature": "Related work appears to be adequately covered.", "essential_references_not_discussed": "I’d say that the main reference was listed but the discussion could be improved relative to Fountalakis et al (JMLR, 2023), both in terms of proof techniques, limitations of the problem setting, and results.", "other_strengths_and_weaknesses": "See above", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oLXRIxfOAP", "reviewer": "Reviewer_BjhC", "summary": "The paper rigorously investigates when graph attention mechanisms help—and when they do not—in the context of node classification for graphs generated by Contextual Stochastic Block Models (CSBM). It introduces a simplified non-linear attention mechanism and demonstrates theoretically that attention improves classification when structure noise outweighs feature noise, but may degrade performance when the reverse is true. The analysis further claims that, in high signal-to-noise regimes, graph attention can effectively counteract the over-smoothing problem that plagues traditional graph convolutional networks. Building on these insights, the authors propose a novel multi-layer Graph Attention Network architecture that substantially relaxes the conditions for perfect node classification compared to single-layer variants. Experiments on synthetic and real-world datasets seem to corroborate these theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and recognition of our paper. In response to your questions and suggestions, we provide the following clarifications:\n\n### 1. **Additional experiments on more comprehensive datasets:**\n   Based on your suggestion, we conducted supplementary experiments on a larger dataset (*obgn-arxiv*) and five heterophily datasets [2] to validate the correctness and practical value of our theoretical results. Please refer to the following link for the results and details: https://drive.google.com/file/d/1ALWkkazk1LPjaWSSkL28RCM7ywOsoBEW/view?usp=drive_link. Below is a brief overview of the experimental setup and corresponding results.\n\n(1). According to our theoretical findings, when feature noise dominates, the graph attention mechanism becomes ineffective, and we should reduce the attention intensity parameter $t$. Conversely, when structure noise dominates, the attention mechanism becomes effective, and we should increase the attention intensity parameter $t$. Accordingly, we design GATv2*(temp), a graph attention model with adjustable attention intensity, based on this idea. Actually, the parameter $t$ can be seen as the reciprocal of temperature adjustment coefficient $T $ applied to the softmax layer in the attention coefficient computation (i.e., $ T = t^{-1} $). Therefore, we adjust the attention mechanism's intensity by tuning the softmax temperature coefficient $T$.  In the original paper, this experiment was implemented only on simulated datasets, but we extend it to real-world datasets in the supplementary experiments. We conduct experiments on six real-world datasets, and for the heterophily datasets with stronger structure noise, we use a design to enhance the attention intensity by setting $ T = t^{-1} = [0.2, 0.5, 1] $ for the three layers. For the more homophilic *ogbn-arxiv* dataset, we used an initial smaller and then progressively larger attention intensity (corresponding to the discussion in lines 369-376 of the paper), i.e., $ T = t^{-1} = [2, 2, 1] $. The accuracy results of the different models are shown in Figure 1 and Table 1 in the above link, with GATv2*(temp) achieving the best overall performance.\n\n (2). Additionally, we conduct a comparison of different models under two types of noise on the *ogbn-arxiv* dataset and plot accuracy heatmaps for each model. Upon observation, we find that the GAT-based method show an improvement over GCN primarily in areas with stronger structure noise, which is reflected in the upper portion of the heatmap. This validates our theoretical findings.\n\n(3). In the case of strong feature noise, the GAT-based method did not show a significant performance degradation. Upon visualizing the parameters, we find that the GAT method, through learning, assigned nearly equal weights to all neighbors, eventually degenerating into a GCN method. However, when structure noise is strong, GAT perform a noticeable selection of valuable neighbors, which lead to superior performance over GCN. These results can be clearly seen in Figure 3 of the linked material.\n\n### 2. **Clarification on the contradiction with [1]:**\n   This is a very valuable question, and we appreciate your inquiry. The apparent contradiction with the conclusions in [1] lies in the different definitions in the measure of over-smoothing. The over-smoothing definition used in [1] is derived from [3], where the relationship between node features and the number of layers $ L $ is analyzed without considering the relationship between layer depth and the number of nodes $n$. As a result, even if over-smoothing occurs after $ L = \\omega(n) $ layers, the over-smoothing measure defined in [1] would still detect it as an over-smoothing phenomenon, which does not align with real-world scenarios. In practice, over-smoothing typically happens at much smaller depths than the total number of nodes. \n\n   Therefore, we introduce an improved measure of over-smoothing in our paper, restricting $ L = O(n) $, as detailed at the beginning of Section 3.3 and in Definition 2. Additionally, our simulation results, shown in Figure 1(c), demonstrate this phenomenon: in regimes with sufficiently high SNR, as the attention intensity $ t $ increases, the over-smoothing measure (i.e., node-similarity measure) decays from an exponential to a nearly linear change.\n\n[1] Wu, X., Ajorlou, A., Wu, Z., and Jadbabaie, A. Demystifying oversmoothing in attention-based graph neural networks.\n\n[2] Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?.\n\n[3] Rusch, T. K., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks.", "claims_and_evidence": "While the paper provides rigorous theoretical analyses and supportive experiments within the CSBM framework, some claims may be viewed as less convincingly supported in broader contexts. In particular, the assertion that multi-layer GATs can achieve perfect node classification under significantly relaxed signal-to-noise conditions is heavily dependent on idealized assumptions inherent in the CSBM, which might not extend to more heterogeneous real-world graphs.", "methods_and_evaluation_criteria": "One notable limitation is the reliance on only a few standard datasets—Citeseer, Cora, and Pubmed—which, while widely recognized, are relatively small and may not represent the complexity or scale of contemporary real-world graphs. This constrained evaluation could limit the generalizability of the findings, as the performance and robustness of the proposed multi-layer GAT architecture in larger, more diverse networks remain untested. Evaluating on a broader and more challenging collection of datasets would provide stronger evidence of the method’s practical utility across a variety of realistic scenarios.", "theoretical_claims": "I examined the proofs for the core theoretical claims, particularly those underpinning Theorems 1, 2, and 3. Overall, the proofs appear largely rigorous; however, some steps—especially those involving asymptotic bounds and the handling of high-probability events—could benefit from additional clarification.", "experimental_designs_or_analyses": "I reviewed the experimental designs and analyses, particularly those in Section 4. The experiments are generally well-structured to validate the theoretical claims, with controlled synthetic settings that mirror the assumptions of the CSBM and provide clear benchmarks for evaluating over-smoothing and SNR improvements. However, as I mentioned above, the limited number and scale of the real-world datasets used is a notable issue.", "relation_to_broader_scientific_literature": "The paper’s contributions extend a well-established line of research on graph neural networks by deepening our understanding of when and how graph attention mechanisms provide benefits. It builds on previous findings regarding the limitations of standard aggregation methods, such as over-smoothing in deep architectures, and clarifies the interplay between different types of noise in graph data. By deriving precise conditions under which attention mechanisms enhance performance compared to simpler operations, the work refines theoretical models of node classification. Moreover, it introduces a multi-layer architecture that relaxes previously stringent signal-to-noise requirements.", "essential_references_not_discussed": "While I appreciate the contributions of the paper, a discussion of previous attempts at rigorously understanding attention in graph neural networks seems to be missing or at the very least incomplete. In particular, [1] establish that attention in GNNs cannot mitigate oversmoothing. Could the authors clarify why this does not contradict their results? \n\n[1] Wu, X., Ajorlou, A., Wu, Z. and Jadbabaie, A., 2023. Demystifying oversmoothing in attention-based graph neural networks. Advances in Neural Information Processing Systems, 36, pp.35084-35106.", "other_strengths_and_weaknesses": "-", "other_comments_or_suggestions": "I would encourage the authors to extend their experiments to larger datasets. For example, I would appreciate it if the authors could provide some results on the heterophilous node classification datasets [2].\n\n[2] Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A. and Prokhorenkova, L., 2023. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. arXiv preprint arXiv:2302.11640.", "questions_for_authors": "Please see \"Essential References Not Discussed\".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper extends the work of Fountoulakis et al. (JMLR, 2023). The JMLR paper analyzes the single-layer GAT model. The present paper extends this work to the multilayer setting. Analyzing the multilayer setting using CSBM is extremely difficult due to recursive non-linearities. The authors bypass some of these issues by placing an activation layer only at the final layer. However, the non-linearities in the attention weights are retained. It is this fact that makes the current work non-trivial.

I believe this paper makes a valuable theoretical contribution and is worthy of acceptance at ICML. However, I would like the authors to include in the paper all the limitations that have been pointed out by the reviewers.
Decision: Accept (poster)