Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models

Thank you for your valuable feedback and recognition of our paper. In response to your questions and suggestions, we provide the following clarifications:

1. Additional experiments on more comprehensive datasets:

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.

(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.

(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.

(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.

2. Clarification on the contradiction with [1]:

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.

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.

[1] Wu, X., Ajorlou, A., Wu, Z., and Jadbabaie, A. Demystifying oversmoothing in attention-based graph neural networks.

[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?.

[3] Rusch, T. K., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks.

Thank you for your valuable feedback. Our response is as follows:

1. Additional Experiments

You 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.

These 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.

Furthermore, 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.

2. Comparison of Proof Techniques with Fountalakis et al. (JMLR, 2023)

Our 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:

(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.

The 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.

However, 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.

(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.

Thank you for your thoughtful feedback, and we look forward to further discussions.

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.

1. Practical Benefits in Real-World Scenarios

Our 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).

Moreover, 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.

2. Choice of Parameter $t$

First, 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.

Conceptually, 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}$.

3. Analysis of Heterophily

This 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.

However, 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.

4. Experiments and Analysis

As 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.

Our 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).

5. Visualization of Attention Coefficients

This 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.

Additional Clarifications:

(1) No, the preprocessing of node features is the same as in all GNNs.
(2) See point 2 and 4 for details.
(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}$.

We appreciate your feedback and hope these responses clarify your concerns.