Understanding When and Why Graph Attention Mechanisms Work via Node Classification

1. We sincerely thank the reviewers for their valuable feedback. We would like to clarify that although the primary finding of our paper—the graph attention mechanism does not always work—has been mentioned empirically in some prior works, the primary goal of our study is to provide a theoretical understanding of this phenomenon. Specifically, our work achieves the following:

   • (i) Characterizes theoretically when the graph attention mechanism works and when it fails (i.e., identifies the precise regime);
   • (ii) Quantifies the extent to which the mechanism improves performance when it works (i.e., provides the regime where multi-layer GATs achieve perfect node classification and demonstrates the improvement over GCNs);
   • (iii) Examines the role of GATs in mitigating the over-smoothing problem.

   Providing a theoretical foundation for these empirically observed conclusions is a significant contribution of our work.

2. Thank you for raising this point. We emphasize that the CSBM used in our study is an random graph model derived from a wide range of real-world graph data. It captures fundamental properties of real-world graph data, especially featured graphs, and has been widely adopted for theoretical analysis in GNN research (as discussed in the related works section of our paper). Furthermore, the conclusions derived from our theoretical analysis have been validated on three commonly used real-world graph datasets (Cora, Citeseer and Pubmed), which sufficiently demonstrates their correctness (see Figure 2 and related discussions in our paper).

   Regarding more complex scenarios, we note that the CSBM model offers many adjustable parameters and several variants, enabling the generation of datasets that reflect diverse real-world scenarios. Since our study is the first to analyze multi-layer GATs for node classification under the CSBM model, we opted for a relatively simple version of CSBM for clarity. We leave the analysis of more complex models for future work.

3. This is a good question. The attention mechanism we designed in this paper serves two purposes:

   • (i) To facilitate theoretical analysis by enabling precise characterization of the node feature distributions after applying the attention layer;
   • (ii) To represent the core principle of most graph attention mechanisms, namely assigning higher weights to nodes with more similar features during message passing.

   This setup is used only in the theoretical analysis and experiments on synthetic datasets. For real-world datasets, we employed the default GAT layers provided in the PyG library.

4. As mentioned above, the graph attention mechanism we designed was tailored for theoretical analysis rather than for proposing a more advanced attention mechanism for practical applications. Additionally, our experiments on real-world datasets, using standard GAT layers, have validated the correctness of our conclusions.

5. As a paper containing a substantial amount of theoretical results, we have made every effort to improve readability, which has been acknowledged by another reviewer (Reviewer pv7Y: "The paper is reasonably well-written and easy to follow"). We warmly invite the reviewer to raise questions about any sections that remain unclear, and we are happy to provide clarifications.

6. For the minor issue: We greatly appreciate you pointing this out. It was indeed a typo, and we have now corrected it.

Once again, we thank the reviewers for their insightful comments and suggestions, and we look forward to further discussions with you!

Dear Reviewer Afdj,

We would like to provide a supplementary clarification regarding your summary of Weakness 1, which appears to misinterpret our results. Specifically, the statement “Recent research on graph heterophily also indicates that when structure is heterophilic (i.e., noisy as described here), GAT models tend to fail” conflicts with the conclusions presented in our paper.

You suggest that GAT models generally fail on graphs exhibiting heterophily. However, according to our findings, graphs with heterophilic structures—or less apparent homophily—are characterized by larger structural noise. In such cases, if the feature noise is relatively small, this falls within a regime where GAT models are effective. Conversely, for graphs with strong homophily (i.e., low structural noise), GAT models are less likely to perform effectively.

Given this misalignment with our conclusions, we respectfully question your assertion in Weakness 1 that “the main finding in our paper is intuitive.” We believe this interpretation may not fully reflect the nuances of our analysis and contributions.

As the rebuttal phase is nearing its conclusion, we have not yet received a response to our previous clarification. We would greatly appreciate it if you could review our explanation and share your feedback at your earliest convenience. Your insights are critical to ensuring an accurate assessment of our work.

Thank you again for your time and thoughtful review.

First, we sincerely thank the reviewers for their valuable suggestions. We noticed that the first three weaknesses identified are related to the comparison of our work with previous studies, particularly with [2], which was not discussed in our original manuscript. We would like to address this issue in detail here.

We appreciate the reviewer bringing this to our attention, as we had not identified this paper prior to submission. After carefully reading it, we acknowledge that there are some similarities in research motivation. However, there are significant differences in the research process and final results, which we outline as follows:

1. While both our work and [2] highlight that GAT does not always outperform GCN, the focus of [2] is on when introducing graph convolution before GAT is beneficial and designing a learnable graph attention layer to determine whether such a preprocessing step is necessary. Specifically, [2] concludes that when structural noise is low, introducing graph convolution before GAT improves overall classification performance by expanding the regime where perfect node classification is achievable. However, it does not explicitly address when GCN outperforms GAT or vice versa.

   In contrast, our work innovatively designs a graph attention mechanism that enables precise computation of node feature distributions after the GAT layer (Theorem 2). This allows us to accurately discuss the conditions under which GCN or GAT performs better. We define two types of noise to characterize these regimes more intuitively. Our findings indicate that when structural noise is low and feature noise is high, GCN can outperform GAT even without using graph attention layers. Interestingly, this explains some results in Figure 2c of [1], specifically that "under low structural noise, GCN outperforms MLP-GAT," which was not discussed in [1]. Our conclusions can be viewed as a synthesis of [1] and [2], offering a more precise analysis and explanation.

2. Our paper further analyzes the impact of multi-layer GAT on the over-smoothing problem (Theorem 3), which we are grateful the reviewer recognized. We emphasize that this analysis is also dependent on our ability to precisely compute the node feature distributions after the GAT layer (Theorem 2), underscoring its importance once again.

3. Regarding the comparison between Theorem 4 in our paper and Corollary 2 in [2], we would like to clarify that Corollary 2 is arguably not "much stronger" than our result; rather, the two have their respective strengths. Specifically, when $\frac{\log^2 n}{n} \ll p, q \ll \frac{\log^k n}{n}$, where $k$ is any constant, our Theorem 4 provides stronger results than Corollary 2 in [2]. When $p, q = \Theta(1)$ as mentioned by the reviewer,, the conclusion in Corollary 2 of [2] is stronger. In summary, our results are more advantageous for sparser graphs.

Finally, we would like to clarify that we have added a citation to [2] in the revised version of the paper, along with a corresponding summary.

Dear Reviewer pv7Y,

Thank you for your insightful comments and suggestions on our submission. We have been actively working to address your feedback during the rebuttal phase and greatly value your input in improving our work.

We noticed there hasn't been a follow-up response to our replies or clarifications. If there are any further concerns or suggestions, we would be more than happy to address them before the rebuttal period concludes.

Thank you for your time and effort in reviewing our work. We truly appreciate your help in this process and look forward to hearing back from you.

Regrading questions:

1. Thank you for raising this point. Our study focuses on the mechanisms of graph attention, which are also used in many SOTA models, including the graph transformers mentioned by the reviewer. Thus, our analysis provides valuable insights for these models as well. A more targeted analysis of specific models is left for future work.

2. We explained the purpose of using the CSBM model in our response to Weakness 2. In practice, every graph dataset contains structural information (e.g., whether it has clear community structures) and feature information (e.g., whether the features of nodes from different classes are clearly distinguishable). By estimating the strength of these two aspects, one can decide whether to use graph attention mechanisms.

3. Perfect node classification is mainly a theoretical metric, less commonly used in practice, but it is strongly correlated with standard metrics like classification accuracy. The easier it is to achieve perfect node classification, the higher the accuracy, and vice versa.

In our experiments, we used classification accuracy on real-world datasets, not perfect node classification, and the results confirm the practical relevance of our analysis.

4. As a theory-focused study, our primary goal is to provide insights and theoretical explanations for certain phenomena, with less emphasis on the experimental aspect. Nevertheless, we have designed experiments to validate all our theoretical results on three representative real-world datasets, which are commonly used in GNN theoretical studies. We believe this is sufficient to support the conclusions presented in our paper.

If the reviewer anticipates that large-scale datasets might affect our results, we are open to adding relevant experiments in future versions.

Finally, we sincerely appreciate the reviewers' valuable feedback and warmly invite them to continue engaging in discussion with us.

Regarding weaknesses:

1. We sincerely thank the reviewer for raising this point. While our work is inspired by Fountoulakis et al. (2023), we must emphasize that it is far from a straightforward extension in either theoretical or applied aspects. It introduces numerous novel proof challenges, techniques, perspectives, and discoveries. Below, we provide a detailed explanation:

(i) Consideration of Noise: Fountoulakis et al. (2023) focuses solely on structural noise and examines the performance of graph attention mechanisms under different levels of structural noise. As a result, it only addresses scenarios where graph attention mechanisms are beneficial. However, the broader and more critical question of whether graph attention mechanisms are always effective remains unanswered in their work. This question is of great importance from both theoretical and practical perspectives.

In our paper, we formalize two types of noise to tackle this question. We identify specific regimes where graph attention mechanisms work effectively and others where they do not. These findings offer practical guidance on when to use graph attention mechanisms and when to avoid them.

Another interesting point is that, our theoretical analysis even offers an explanation for a phenomenon observed in the experimental results of Fountoulakis et al. (2023), particularly in Figure 2c. It explains why, under low structural noise (i.e., when $p-q$ is large), GCN outperforms MLP-GAT. This experimental result was not discussed in their paper, likely because their theoretical framework could not account for it.

(ii) Extension to Multi-layer Networks: As noted by the reviewer, another contribution of our work is extending the analysis from single-layer GATs to multi-layer GATs. We must emphasize that this extension is non-trivial and involves several theoretical challenges.

First, we had to redesign a graph attention mechanism that is both simple and effective—amenable to theoretical analysis while still representative of the core functionality of most graph attention mechanisms. The attention mechanism in Fountoulakis et al. (2023) is overly complex and cannot be analyzed in the multi-layer setting. Details of this comparison can be found in Sections Section 3.1 and Appendix B.

Second, multi-layer analysis demands precise derivation of node feature distributions, unlike the rough estimations (e.g., sign determination) in single-layer analysis. Notably, the graph attention mechanism is nonlinear, meaning that the node features after passing through a GAT layer no longer follow a Gaussian distribution. This makes deriving their expressions and analyzing their magnitude particularly challenging. In our paper, simply determining the precise distribution of node features after one GAT layer occupies pages 17 to 32 of the appendix. This part, rich in proof techniques and challenges, forms the core of our theoretical analysis.

Finally, we note that extending from single-layer to multi-layer analysis is a well-known challenge in deep learning theory, with related works published in top venues like FOCS, COLT, and JMLR. Below are some examples:

• [1] Chen, Sitan, Adam R. Klivans, and Raghu Meka. "Learning deep ReLU networks is fixed-parameter tractable." FOCS 2022.
• [2] Chen, Sitan, et al. "Learning narrow one-hidden-layer ReLU networks." COLT 2023.

(iii) Over-smoothing Problem: Another key contribution of our work is analyzing the impact of multi-layer GATs on the over-smoothing problem. Over-smoothing is a significant challenge for graph neural networks in practical applications, and the question of whether graph attention mechanisms alleviate this issue, and to what extent, remains open.

Our theoretical analysis shows that with sufficiently large SNR, multi-layer GATs can address the over-smoothing problem that GCNs cannot resolve for CSBM-generated graphs. This has significant practical implications:

• Graph attention mechanisms can positively mitigate the over-smoothing problem.
• 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.

2. We use the CSBM model to simulate real-world graph data and perform theoretical analysis. As noted in the related works section, random graph models like CSBM are widely used in GNN theory.

Regarding the reviewer's mention of "more complex" and "varied structures," we clarify that the CSBM model is highly flexible, with numerous variants and adjustable parameters to capture different types of real graphs. For simplicity, this paper focuses on a basic version.

If the reviewer could specify the "complex" properties of the graph data, we would be happy to discuss whether a CSBM variant can capture these characteristics.

3. See point 4 in the response to "questions."

Dear Reviewer AYEX,

Thank you for your valuable feedback and constructive comments on our submission. We have carefully addressed each of your questions and provided detailed responses to clarify our methodology, highlight the key contributions of our work, and discuss the challenges we tackled.

In particular, we conducted a thorough comparison with prior work Fountoulakis et al. (2023) and emphasized three key contributions of our approach:

1. A more detailed definition and explicit consideration of two types of noise, which provides a deeper understanding of the problem;
2. An extension of the framework to multi-layer networks, significantly enhancing its applicability;
3. A novel analysis of the over-smoothing issue.

These contributions demonstrate that our work is far from a straightforward extension of existing methods. Instead, it addresses substantial challenges and incorporates non-trivial innovations that advance the state of the art.

We greatly value your input and would sincerely appreciate any further thoughts or feedback you may have before the rebuttal phase concludes. Your perspective is crucial in helping us refine our work and ensure that our contributions are clearly communicated.

Thank you again for your time and effort in reviewing our submission. We look forward to your response.