GATE: How to Keep Out Intrusive Neighbors

We thank the reviewer for the constructive feedback and insightful questions, which we answer below.

• We agree with the reviewer's suggestion that a pictorial representation would help with a reader's intuition. Unfortunately, due to space constraints, it is not easy to add one to the paper.

• As the reviewer has rightly pointed out, GATE was not necessary to get a near 100 score in the single-layer case. We highlight the importance of this observation in paragraph 6 on page 5. The key idea of the experiment is not to discover how many layers are needed for the toy case example, but rather to empirically demonstrate our theoretical insights in Section 4. Our reasoning for why GAT is unable to switch off neighborhood aggregation is related to norm constraints on the parameters imposed by an inherent conservation law in the network. For a single-layer network, the norms are not constrained and hence GAT is able to switch off neighborhood aggregation. In contrast, the 2-layer (or more) network is bound by norm constraints that prevent GAT from achieving the desired behavior. This reinforces our theoretical insight. In contrast, GATE can retain its performance for deeper models as well by switching off neighborhood aggregation in all layers.

• All our experiments were run multiple times. As the motivation behind designing a learning task via a synthetic dataset was to study how well GAT and GATE learn the task at hand, we decided to stick to analyzing one run of each model in detail. We compare the test accuracy of the model when it has achieved its maximum train accuracy (usually 100% except for cases marked with asterisk) to the maximum test accuracy achieved by the model (and when). This provides an insight into whether the model is simply overfitting to the train data or really learning the task. We report the mean accuracy in Table 8 in Appendix C.4. Due to space constraints, both tables can not be added to the main text. If the reviewers suggest that the detailed analysis be moved to the appendix, it can be replaced by the aggregate results across multiple runs in the main paper.

We thank the reviewer for the constructive feedback and insightful questions, which we answer below.

• While our derivations that lead to Insight 4.2 only consider the weight-sharing case, a similar principle also applies to GAT without weight-sharing. Experimental results in Table 1 demonstrate that GATs, both with and without weight sharing, are unable to switch off neighborhood aggregation, as they struggle to assign large magnitudes to the parameters $a$. Contrary to this, GATE, both with and without weight sharing, is able to switch off neighborhood aggregation. We have presented results on real-world datasets for both GATE and GATE$_S$ in Figure 9 and Table 6 (deferred to the appendix due to space limitation and observation of similar results) and also briefly discussed the trade-off between parameter sharing and no parameter sharing in light of training time and generalization accuracy.

• We have now added a comparison of GATE with FAGCN and GraphSAGE on synthetic datasets in Appendix C.5 (Tables 9 and 10) and discuss their ability to switch off neighborhood aggregation. To the best of our knowledge, current techniques to alleviate over-smoothing in GNNs are based on regularization such as dropout and sampling, or architectural elements such as skip connections from a previous layer to the next (or from the input layer to every other layer (FAGCN), or from every layer to the last layer (GCNII)), and concatenation of a node's own features with aggregated neighbors (GraphSAGE). These techniques are complementary and thus could be combined with GATE. Note that GATE also maintains a strong performance for deeper networks that would usually suffer from over-smoothing.

• The lines from 20%ile - 90%ile can be distinguished by their order (bottom to top) for example in the plot for Layer 1 in the bottom right plot of Figure 4. When they are indistinguishable, for example in layers 3-4 of the same plot, it implies that they are (almost) equal (and hence do not need to be differentiated.) Section 5.2 discusses in detail the results in Figure 4 in the context of the effect of depth and how GATE offers interpretable neighborhood aggregation. However, upon the reviewer's identification of the difficulty of interpreting Figure 4 in isolation, we have added a summary of its insights from Section 5.2 to the caption of Figure 4.

• Table 1 does not report the min. loss but rather the test accuracy at the epoch of min loss (most of these cases correspond to 100% train accuracy except the entries marked with an asterisk). Because the reported results are for synthetic data designed specifically to distinguish the behavior of GAT and GATE, we believe it is important to capture the full behavior of both architectures by ensuring that even though GAT can memorize the data to achieve 100% train accuracy, it fails to generalize, unlike GATE. The epoch information helps us to verify that despite being allowed to train for longer, GAT is unable to effectively learn the task, whereas GATE generalizes perfectly almost at the same time when it achieves 100% training accuracy. We have added a sentence that explains this reasoning in more detail.

We thank the reviewer for their response. According to their request, we have added the theoretical analysis of the non-weight-sharing case in Appendix A.1, which completes our theoretical investigation and leaves no gap. The flow of arguments is identical to the weight-sharing case. Yet, the analysis involves the distinction of $6$ cases, which we now discuss all in detail.

We would be happy to answer any further questions upon request.

We thank the reviewer for the constructive feedback and insightful questions, which we answer below.

• We would be happy to provide further explanations of the theoretical result.
  • Firstly, note that $\alpha_{ij} << 1$ would not necessarily be sufficient to make the contribution of neighbor $j$ insignificant. For instance, nodes with a high degree $\alpha_{ij} << 1$ could hold for all $j$ and the node $i$ so that each neighbor, as well as node $i$, would still similarly impact the features of $i$. To make $j$ insignificant relative to the contribution of the node's contribution, we actually need $\alpha_{ij}/\alpha_{ii} < < 1$. Also note that the analysis of relative $\alpha_{ij}/\alpha_{ii}$ is simpler, as the normalization constant cancels out. This fact elucidates further why we need to study $\alpha_{ij}/\alpha_{ii}$ and not $\alpha_{ij}$: even if the attention parameter in another neighbor was large, this would affect the normalization constant and thus potentially also weight down $\alpha_{ii}$. Furthermore, to switch off all neighborhood aggregation, we require $\alpha_{ij}/\alpha_{ii} < < 1$ for all neighbors $j$.
  • Next, we provide an intuition of how the limited expressiveness of attention results from the derived conservation law. Theorem 4.1 induces the corollary that $\left\lVert\mathbf{W}^{l}\right\rVert^2 = \left\lVert\mathbf{W}^{l+1}\right\rVert^2 + \left\lVert\mathbf{a}^{l}\right\rVert^2 + c$ during gradient flow. We show that to make the contribution of all neighbors $j$ insignificant, we actually need $\left\lVert\mathbf{a}^{l}\right\rVert^2$ to be large. The above conservation law implies that $\left\lVert\mathbf{W}^{l}\right\rVert^2$ would also need to be large and $\left\lVert\mathbf{W}^{l+1}\right\rVert^2$ relatively small. However, due to the structure of gradients in Equation (6) on page 4, this would require large `relative' gradients $\Delta \mathbf{W}^{l+1} = \nabla \mathbf{W}^{l+1}/ \mathbf{W}^{l}$ of parameters in $\mathbf{W}^{l+1}$ and small relative gradients of parameters in $\mathbf{W}^{l}$, for which the model would need to enter a less trainable regime and thus could not converge to a meaningful model.
• We present additional results on the larger and more recent five datasets introduced in the paper `A critical look at the evaluation of GNNs under heterophily' proposed by the reviewer in Table 6 in Appendix C.1, as well as two large-scale OGB datasets: Arxiv and Product. For most of these datasets, we observe a substantial improvement of GATE over GAT.
• We would like to emphasize that our aim is to provide insights into the attention mechanism of GATs and understand its limitations. While it should be able to flexibly assign importance to neighbors and the node itself without the need for concatenated representation or explicit skip connections of the raw features to every layer, it is currently unable to do so in practice. In order to verify our identification of trainability issues, we modify the GAT architecture to enable the trainability of attention parameters which control the trade-off between node features and structural information. Other architectures could potentially switch off neighborhood aggregation, as we show next. However, they are less flexible in assigning different importance to neighbors, suffer from over-smoothing, or come at the cost of an increased parameter count by increasing the size of the hidden dimensions (e.g. via a concatenation operation). Concretely, we have newly added a comparison of GATE with FAGCN and GraphSAGE on synthetic datasets in Appendix C.5 (Tables 9 and 10) and discuss their ability to switch off neighborhood aggregation as follows.
  • GraphSAGE uses the concatenation operation to combine the node's own representation with the aggregated neighborhood representation. Therefore, it is usually (but not always) able to switch off the neighborhood aggregation for the synthetic datasets designed for the self-sufficient learning task. Mostly, GATE performs better on the neighbor-dependent task, in particular for deeper models, where the performance of GraphSAGE drops likely due to over-smoothing.
  • FAGCN requires a slightly more detailed analysis. Hence, due to space limitations, we make the complete discussion in Appendix C.5 on page 21. The key point is that FAGCN, as we observe, is unable to switch off neighborhood aggregation, particularly for deeper models.
• The first two papers discuss training attention in GNNs with additional supervision. We have discussed the paper "How to Find Your Friendly Neighborhoods" as superGAT in Figure 10 in Appendix C.5 but have missed the citation. The last two papers suggested by the reviewer are important recent works that highlight the interest of the GNN community in understanding and addressing the limitations of graph attention. We thank the reviewer for pointing us towards further relevant literature and have added them all to our related work section.

Firstly, note that $\alpha_{ij} << 1$ would not necessarily be sufficient to make the contribution of neighbor j insignificant. For instance, nodes with a high degree $\alpha_{ij} << 1$ could hold for all j and the node i so that each neighbor, as well as node i, would still similarly impact the features of i.

I do not think it is important for an insignificant node to have a similar impact with other neighbors. What really matters is how much an insignificant node contributes to the overall neighborhoods (including self-loops). Using an example of a high-degree node i, even if insignificant j impacts similar to other neighbors, its contribution will be very small since $\alpha_{ij} << 1$. That is, the insignificant node j will have little effect on the features of node i.

Also note that the analysis of relative $\alpha_{ij}/\alpha_{ii}$ is simpler, as the normalization constant cancels out.

Nevertheless, now I understand that using relative contribution $\alpha_{ij}/\alpha_{ii}$ makes an analytical interpretation simple.

even if the attention parameter in another neighbor was large, this would affect the normalization constant and thus potentially also weight down $\alpha_{ii}$. Furthermore, to switch off all neighborhood aggregation, we require $\alpha_{ij}/\alpha_{ii} < < 1$ for all neighbors j.

A small $\alpha_{ii}$ can be a problem when a large portion of neighbors is insignificant. In this case, we might need to switch off all neighborhood aggregation. However, if so, we should ask a basic but important question: why do we use a neighborhood aggregation rather than just MLP on the node itself? I recommend the authors discuss this question and compare the results of MLP with GATE.

We thank the reviewer for the constructive feedback and insightful questions, which we answer below.

• While the architecture is able to completely switch off the contribution of every neighbor if that is adequate, it does not have to do this. On synthetic tasks in which neighbors do not contain any information about a node's label, the ability of GATE to switch off neighborhood aggregation improves its performance. On many real-world data sets, however, the contributions of neighbors are not synchronously switched off. We demonstrate this by comparing the distributions of $\alpha_{uv}$ where $u\in \mathbb{N}(v) \backslash v$ in Fig. 9 in Appendix C.3 for GATE that shows a skewed distribution of $\alpha_{uv}$ over all edges where not all neighbors are switched off. In principle, the self-attention mechanism and neighborhood aggregation in GATE are no different than in GAT and neighboring nodes may still be assigned different levels of importance. The advantage of GATE is that it can distinguish between node and neighbor features and weigh them more flexibly against each other. This fact explains its often superior performance to GAT, especially for heterophilic tasks.

• Ideally, the architecture should be flexible enough to determine the more beneficial case among the two and this is the direction we aim to pursue with GATE as this is an interesting dilemma that manifests itself in most graph representation learning tasks and is a much broader research problem. To the best of our knowledge, so far in the literature, the number of layers of GNNs has been treated as a hyper-parameter and deeper models have been enabled by explicit skip connections and identity mappings. While these techniques are complementary, the ability of GATE to switch off neighborhood aggregation could potentially lead to the network simulating perceptron behavior in certain layers, which may then be able to learn an identity or more complex deeper non-linear transformations of nodes multiple hops away which may then again be aggregated at further depth. We discuss this briefly in the paper in Section 5.2 (paragraph: interpretable neighborhood aggregation) in light of Fig. 4. The bottom line is that this decision is task-dependent and we observe in Table 6 in Appendix C.1 that for larger graphs, deeper GATE models lead to an improvement by possibly gaining information from a larger radius in the neighborhood and/or by learning more complex features of neighbors and the node itself.

• We thank the reviewer for the feedback and would be happy to improve the legends of our figures. It would be really helpful if the reviewer could be slightly more specific with an example of a figure and whether it's a readability problem or the text in the legend is ambiguous. This would allow us to make a more satisfactory improvement.

We thank the reviewer for the constructive feedback and insightful comments, which we address below.

• The suggested paper provides an insightful discussion on 'good' and 'bad' heterophily that we have included in our literature discussion. In similar terminology, as the reviewer has correctly pointed out, the synthetic datasets for the self-sufficient task in Section 5.1 exemplify one use case of 'bad' heterophily. However, they were designed to verify our identification of the cause behind the limited expressivity of the attention mechanism in GATs. Our main contribution is the theoretical insight into the reasoning behind the inability of GATs to switch off neighborhood aggregation, which is rooted in norm constraints imposed by the inherent conservation law. To verify the correctness of this insight, we have designed GATE to address the identified root cause of the problem. Similar reasoning can also be applied to nodes in the neighborhood itself (by comparing $\alpha_{uv}$ and $\alpha_{u'v}$ for $\{u',v\}\in \mathbb{N}(v)$ instead of comparing $\alpha_{uv}$ and $\alpha_{vv}$. We would like to reiterate that our claim is that an effective attention mechanism should be able to adapt neighborhood aggregation according to the task at hand, and the presence of 'good' and 'bad' heterophily are also task-dependent. As we show in this work, the intended capacity of the present attention mechanism to express the importance of neighboring nodes (considering a node to be a neighbor of itself by self-loops generally introduced in GATs) is impeded by trainability issues that we have verified by alleviating the trainability issue of attention parameters for one particular neighbor (the node itself). Therefore, although GATE does not eliminate the problem completely, the identification of the problem in this work serves as a stepping stone that will allow us to address the problem more generally and enable more effective attention mechanisms for GNNs in the future.

• Results on Cora and Citeseer can be found in Table 3 on page 9 with fixed 20 nodes per class. In addition, we present results in Table 6 in Appendix C.1 on more datasets: OGB-arxiv, OGB-product, and larger more recent heterophilic datasets. GATE achieves a substantial improvement over GAT for most of these larger datasets, notably, for OGB-Arxiv and OGB-Product.

• We thank the reviewer for their suggestion and have incorporated their feedback in the updated document. Unfortunately, due to space limitations, we could only include a very brief two-line overview. However, we would like to encourage readers to draw their attention to Section 4, as it discusses the main contribution of our work. Detailed theoretical insights are deferred to Appendix A.