Towards Deep Attention in Graph Neural Networks: Problems and Remedies
Graph neural networks (GNNs) learn the representation of graph-structured
data, and their expressiveness can be further enhanced by inferring node
relations for propagation. Attention-based GNNs infer neighbor importance to
manipulate the weight of its propagation. Despite their popularity, the
discussion on deep graph attention and its unique challenges has been limited.
In this work, we investigate some problematic phenomena related to deep graph
attention, including vulnerability to over-smoothed features and smooth
cumulative attention. Through theoretical and empirical analyses, we show that
various attention-based GNNs suffer from these problems. Motivated by our
findings, we propose AEROGNN, a novel GNN architecture designed for deep graph
attention. AERO-GNN provably mitigates the proposed problems of deep graph
attention, which is further empirically demonstrated with (a) its adaptive and
less smooth attention functions and (b) higher performance at deep layers (up
to 64). On 9 out of 12 node classification benchmarks, AERO-GNN outperforms the
baseline GNNs, highlighting the advantages of deep graph attention. Our code is
available at https://github.com/syleeheal/AERO-GNN.
Soo Yong Lee, Fanchen Bu, Jaemin Yoo, Kijung Shin
# Towards Deep Attention in Graph Neural Networks:

###### Abstract

Graph neural networks (GNNs) learn the representation of graph-structured data, and their expressiveness can be further enhanced by inferring node relations for propagation. Attention-based GNNs infer neighbor importance to manipulate the weight of its propagation. Despite their popularity, the discussion on deep graph attention and its unique challenges has been limited. In this work, we investigate some problematic phenomena related to deep graph attention, including vulnerability to over-smoothed features and smooth cumulative attention. Through theoretical and empirical analyses, we show that various attention-based GNNs suffer from these problems. Motivated by our findings, we propose AERO-GNN, a novel GNN architecture designed for deep graph attention. AERO-GNN provably mitigates the proposed problems of deep graph attention, which is further empirically demonstrated with (**a**) its adaptive and less smooth attention functions and (**b**) higher performance at deep layers (up to 64). On 9 out of 12 node classification benchmarks, AERO-GNN outperforms the baseline GNNs, highlighting the advantages of deep graph attention. Our code is available at [https://github.com/syleeheal/AERO-GNN](https://github.com/syleeheal/AERO-GNN).

Machine Learning, Graph Neural Networks, Graph Neural Networks, Graph Neural Networks, Graph Attention, Graph Neural Networks

## 1 Introduction

Graph neural networks (GNNs) are a class of neural networks for representation learning on graph-structured data. Recently, GNNs have been successfully applied to a wide range of graph-related tasks, including social influence prediction (Qiu et al., 2018), traffic forecast (Derrow-Pinion et al., 2021), physical system modeling (Sanchez-Gonzalez et al., 2020), product recommendation (Wu et al., 2022), and drug discovery (Stokes et al., 2020).

GNNs widely adopt message-passing frameworks, composed of two main pillars: feature transformation and propagation (a.k.a. neighborhood aggregation) (Wu et al., 2019; Gilmer et al., 2017). Feature transformation updates node features from previous layers' features. Propagation involves each node passing its own features to its neighbors, and for each node, the passed-down neighbor features are aggregated to update its own node features. In this framework, a propagation layer determines the propagation weight for each adjacent node pair, and each additional layer allows nodes to propagate to one more hop of neighbors.

Attention-based GNNs aim to learn to propagate by inferring the relational importance between node pairs. Graph attention infers relational importance for node pairs. Among many, GAT and its variants (Velickovic et al., 2018; Wang et al., 2019; Brody et al., 2021; Shi et al., 2021; Kim and Oh, 2021; Bo et al., 2021; Wang et al., 2021; Yang et al., 2021; He et al., 2021) learn edge attention. The _edge-attention_ models infer the importance, or weight, of each neighbor w.r.t. each source node by applying an attention mechanism between adjacent node pairs. During propagation, each source node aggregates features from its neighbors based on the inferred importance.

Another class of GNNs, which we call _hop-attention_ (or _layer-attention_) models, learns the relative importance of each hop (Liu et al., 2020; Chien et al., 2021; Zhang et al., 2022; Chanpuriya and Musco, 2022). Hop-attention models apply attention coefficients at every propagation layer to express the relative importance of a given hop in determining the final node features. Thereby, hop-attention models learn which hops, among multi-hop neighbors, each source node should attend to during propagation. Intuitively, edge-attention models learn importance _within_ each hop, and hop-attention models learn importance _of_ each hop.

Can the existing attention-based GNNs learn expressive attention over deep layers? Prior research does not provide a clear answer. While many studies report the over-smoothing problem of _node features_ at deep layers (Li et al., 2018;
Chen et al., 2020; Liu et al., 2020; Chen et al., 2020), they do not address how it may relate to _graph attention_. Some works focus on designing expressive graph attention layers (Brody et al., 2021; Shi et al., 2021; Kim and Oh, 2021; Bo et al., 2021; Yang et al., 2021; He et al., 2021), but their scope is limited to shallow model depth. Even for attention-based GNNs that generalize their performance over deep layers (Liu et al., 2020; Wang et al., 2021; Chien et al., 2021; Zhang et al., 2022), they do not explicitly discuss properties related to deep attention. Very recently, Zhao et al. (2023) explored the relationship between model depth and attention function for graph transformers. Their analysis, however, was confined to the relationship between model depth and transformer-style attention to substructures. In short, the theoretical underpinnings to understand deep graph attention are under-explored.

In this work, we investigate some problematic phenomena related to deep graph attention. Through both theoretical and empirical analyses, we show that the _vulnerability to over-smoothed features_ and _smooth cumulative attention_ limit the graph attention from becoming expressive over deep layers. Specifically, several representative attention-based GNNs, including GATv2 (Brody et al., 2021), FAGCN (Bo et al., 2021), GPRGNN (Chien et al., 2021), and DAGNN (Liu et al., 2020), suffer from these problems.

Motivated by our analyses, we propose a novel graph attention architecture, **A**tentive d\(\underline{\text{E}}\)ep p\(\underline{\text{R}}\)**O**pagation-GNN (AERO-GNN). We theoretically demonstrate that AERO-GNN can mitigate the stated problems, which is further elaborated empirically by AERO-GNN's (**a**) adaptive and less smooth attention functions and (**b**) higher performance at deep layers (up to 64). On 9 out of 12 node classification benchmarks, including both homophilic and heterophilic graphs, AERO-GNN outperforms all the baselines, highlighting the advantages of deep graph attention.

In summary, our central contributions are two-fold:

1. **Theoretical Findings.** We formulate two theoretical limitations of deep graph attention. AERO-GNN provably mitigates the problems, whereas the representative attention-based GNNs inevitably suffer from them.
2. **Empirical Findings.** AERO-GNN shows superior performance in node classification benchmarks. Also, compared to the representative attention-based GNNs, AERO-GNN learns more adaptive and less smooth attention functions at deep layers.

## 2 Preliminaries

**Graphs.** Let \(G=(V,E)\) be a graph with node set \(V\) and edge set \(E\subseteq\binom{V}{2}\).1 Let \(n=|V|\) and \(m=|E|\) denote the number of nodes and edges, resp. WLOG, we assume \(V=[n]=\{1,2,\dots,n\}\). Let \(A=A(G)\in\{0,1\}^{n\times n}\) denote the adjacency matrix of \(G\), where \(A_{ij}=1\) iff \((i,j)\in E\), and we use \(D=\operatorname{diag}(d_{1},d_{2},\dots,d_{n})\) to denote the degree matrix of \(G\), where \(d_{i}\) is the degree of node \(i\). Let \(X\in\mathbb{R}^{n\times d_{i}}\) denote the initial node feature matrix, where each node \(i\in V\) has node feature \(X_{i}\) of dimension \(d_{x}\). Footnote 1: We assume undirected, unweighted graphs, but our theoretical results can be easily extended to directed and/or weighted graphs.

**Message-Passing GNNs.** Feature transformation and propagation are the two main building blocks of message-passing GNNs (Wu et al., 2019; Gilmer et al., 2017). Feature transformation updates the features of each node based on the node's features of previous layers. A feature transformation layer can be expressed as: \(H^{(k)}=\sigma(H^{(k-1)}W^{(k)}),\forall 1\leq k\leq k_{max}\),2 where \(k\) denotes the index of each layer with \(k_{max}\) being the total number of layers, \(H^{(k)}\in\mathbb{R}^{n\times d_{n}}\) is the _hidden node feature matrix_ at layer \(k\), \(W^{(k)}\) is the weight matrix at layer \(k\), and \(\sigma\) is an activation function.

Footnote 2: Usually, \(H^{(0)}\) is a function on the initial features, i.e., \(X\).

On the other hand, a propagation layer passes node features to its neighbors, and each node's features are updated as an aggregation of the features. Specifically, a propagation layer can be expressed as follows: \(H^{(k)}=\tilde{A}H^{(k-1)},\forall 1\leq k\leq k_{max}\), where \(\tilde{A}=(D+I)^{-1/2}(A+I)(D+I)^{-1/2}\) is the symmetrically normalized adjacency matrix with self-loops.

Many GNNs fuse the two operations in one layer, such that \(H^{(k)}=\sigma(\tilde{A}H^{(k-1)}W^{(k)})\)(Welling and Kipf, 2016; Velickovic et al., 2018; Chen et al., 2020). Some others use only propagation layers to update \(H^{(k)}\), after obtaining \(H^{(0)}\) with feature transformation (Gasteiger et al., 2018; Liu et al., 2020; Chien et al., 2021). Note that \(\tilde{A}\) determines the magnitude in which each node's features propagate to its neighbors, and the number of propagation layers determines the number of hops to propagate to.

**Edge Attention.** Edge-attention GNNs (e.g., GAT and its variants) learn an edge-attention matrix \(\mathcal{A}^{(k)}=(\alpha_{ij}^{(k)})\in\mathbb{R}^{n\times n}\) at each propagation layer (i.e., hop) \(k\),3 where each edge attention coefficient \(\alpha_{ij}^{(k)}\) can be seen as the importance of node \(j\) w.r.t node \(i\) at layer \(k\). At each propagation layer, the edge attention coefficients are used to weigh propagation between each adjacent node pair.

Footnote 3: Single-head attention is assumed for simplicity.

**Hop Attention.** Hop-attention GNNs learn a hop-attention matrix \(\Gamma^{(k)}=\operatorname{diag}(\gamma_{1}^{(k)},\gamma_{2}^{(k)},\dots, \gamma_{n}^{(k)})\in\mathbb{R}^{n\times n}\) at each propagation layer \(k\). With hop attention, different importance \(\gamma_{i}^{(k)}\) can be assigned at different layers \(k\) for every node \(i\). Typically,

\[Z^{(k)} =\sum_{t\sim 0}^{k}\Gamma^{(\ell)}H^{(\ell)},\forall 1\leq k\leq k _{max}, \tag{1}\] \[=\sum_{t\sim 0}^{k}\Gamma^{(\ell)}\tilde{A}^{\ell}H^{(0)},\forall 1 \leq k\leq k_{max}, \tag{2}\]
where the sum of hidden feature matrix \(H^{(t)}\)'s up to layer \(k\), each weighted by the hop attention matrix \(\Gamma^{(\ell)}\), expresses the _layer-aggregated_ node feature matrix \(Z^{(k)}\). Equation (2) highlights that the hop attention matrix \(\Gamma^{(\ell)}\) can be seen as learning weights of \(\ell\) hop neighbors expressed in \(\tilde{A}^{\ell}\) (A similar analysis can be found in Dong et al. (2021)).

## 3 Theoretical Analysis on Deep Attention

Can attention functions of the representative attention-based GNNs remain expressive over deeper layers? Prior research has suggested possible reasons for the performance degradation of deep GNNs, including the over-smoothing of node features, over-squashing (Alon and Yahav, 2021), and over-correlation (Jin et al., 2022). However, discussion dedicated to theoretical limitations of _deep graph attention_ has been little. In this section, we formulate two theoretical limitations of the representative attention-based GNNs concerning their ability to remain expressive over deeper layers.

### A Systematic Understanding of Graph Attention

A systematic understanding of graph attention, integrating edge and hop attention, would allow us to discuss various attention-based GNNs and their theoretical limitations within the same framework.

**Cumulative Attention.** We have observed that edge and hop attention achieve the same goal (i.e., inferring the relational importance between node pairs), but from two different perspectives. Consequently, they both learn weights in which each node's features propagate to its neighbors. This observation motivates us to integrate edge and hop attention under the same umbrella. To this end, we propose a concept of _cumulative attention matrix_, denoted by \(T^{(k)}\), which intuitively represents attention between all node pairs within \(k\) hops (or equivalently, at layer \(k\)) that considers both edge and hop attentions.

Formally, given any \(k_{max}\), for each \(0\leq k\leq k_{max}\),

\[T^{(k)}=\Gamma^{(k)}\prod_{\ell=k}^{1}\mathcal{A}^{(\ell)}, \tag{3}\]

where \(T^{(0)}=\Gamma^{(0)}\).4

Footnote 4: For FAGCN, \(T^{(k)}=\Gamma^{(k)}\prod_{\ell=k_{max}}^{k_{max}-k+1}\mathcal{A}^{(\ell)}\). However, in our theoretical analyses, it is equivalent to Eq. (3) when \(k_{max}\) is fixed.

**Rephrased Propagation w.r.t \(T^{(k)}\)'s.** Here, we discuss various representative attention-based GNNs (spec., GATv2, FAGCN, GPRGNN, and DAGNN). We detail their attention functions in Table 1. Those models are used throughout our theoretical analyses and empirical evaluation.

GATv2 and FAGCN learn edge attention \(\alpha_{ij}^{(k)}\). GATv2 uses hidden features \((H_{i}\|H_{j})\), whereas FAGCN layer-aggregated features \((Z_{i}\|Z_{j})\), in computing each edge attention coefficient \(\alpha_{ij}^{(k)}\). Notably, their \(\alpha_{ij}^{(k)}\) have different bounds, such that GATv2's \(\alpha_{ij}^{(k)}\in(0,1)\) and FAGCN's \(\alpha_{ij}^{(k)}\in(-1,1)\). They do not learn hop attention coefficients, which can be expressed as a constant (1 for GATv2 and \(c_{\gamma}\) for FAGCN).

On the other hand, GPRGNN and DAGNN learn hop attention \(\gamma_{i}^{(k)}\). GPRGNN's hop attention is not explicitly bounded and, thus, can learn negative hop attention \(\gamma_{i}^{(k)}\). While \(\gamma_{i}^{(k)}\in(0,1)\) for DAGNN, it learns _node-adaptive_ hop attention. Neither GPRGNN nor DAGNN learns nontrivial edge attention, and their edge attention coefficients are equivalently degree-normalized constants, i.e., \(\alpha_{ij}^{(k)}=1/\sqrt{d_{i}d_{j}},\forall i,j,k\).

The discussed GNNs consist of a representative and diverse set of attention functions, yet we can succinctly rephrase them w.r.t \(T^{(k)}\) (see Table 2).5

Footnote 5: FAGCN and GATv2’s propagation formulae are rewritten from their original form. Refer to Appendix B for the details.

\begin{table}
\begin{tabular}{c c c c} \hline \hline Model & Pre-normalized Edge Attention & Normalized Edge Attention & Hop Attention \\ \hline \hline
** GATv2** & \(\hat{\alpha}_{i}^{(k)}=\exp((W_{edge}^{(k)})^{\tau}\sigma(H_{i}^{(k-1)}|H_{j} ^{(k-1)}))\) & \(\alpha_{ij}^{(k)}=\hat{\alpha}_{ij}^{(k)}/\sum_{j^{\prime}\in\mathcal{N}(j)} \hat{\alpha}_{ij^{\prime}}^{(k)}\) & \(\gamma_{i}^{(k)}=1\) \\
**FAGCN** & \(\hat{\alpha}_{ij}^{(k)}=\tanh((W_{edge}^{(k)})^{\tau}(Z_{i}^{(k-1)}|Z_{j}^{(k-1 )}))\) & \(\alpha_{ij}^{(k)}=\hat{\alpha}_{ij}^{(k)}/\sqrt{d_{i}d_{j}}\) & \(\gamma_{i}^{(k)}=c_{\gamma},\forall k,i\) (*) \\
**GPRGNN** & \(\hat{\alpha}_{ij}^{(k)}=1\) & \(\alpha_{ij}^{(k)}=1/\sqrt{d_{i}d_{j}}\) & \(\gamma_{i}^{(k)}=\gamma_{ij}^{(k)}=c_{\gamma,\forall k}\) (**) \\
**DAGNN** & \(\hat{\alpha}_{ij}^{(k)}=1\) & \(\alpha_{ij}^{(k)}=1/\sqrt{d_{i}d_{j}}\) & \(\gamma_{i}^{(k)}=\mathrm{sigmoid}(W_{hop}{}^{\tau}H_{i}^{(k)})\) (***) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Attention Functions of Graph Attention Models

\begin{table}
\begin{tabular}{c c c} \hline \hline Model & \(k\)-Layer Propagation & Rephrased Propagation w.r.t \(T^{(k)}\)’s \\ \hline \hline
** GATv2** & \(H^{(k)}=(\prod_{\ell=k}^{1}\mathcal{A}^{(\ell)})X\left(\prod_{\ell=k}^{k}W^{( \ell)}\right)\) & \(H^{(k)}=T^{(k)}X\prod_{\ell=k}^{k}W^{(\ell)}\) \\
**FAGCN** & \(Z^{(k)}=(\Gamma+\Gamma\mathcal{A}^{(k)}+\Gamma\mathcal{A}^{(k)}\mathcal{A}^{(k -1)}+\cdots+\Gamma\prod_{\ell=k}^{1}\mathcal{A}^{(\ell)})H^{(0)}\) (*) & \(Z^{(k)}=\sum_{\ell=k}^{k}T^{(\ell)}H^{(0)}\) \\
**GPRGNN/DAGNN** & \(Z^{(k)}=(\Gamma^{(0)}+\Gamma^{(1)}\mathcal{A}+\Gamma^{(2)}\mathcal{A}^{2}+ \cdots+\Gamma^{(k)}\mathcal{A}^{k})H^{(0)}\) (**) & \(Z^{(k)}=\sum_{\ell=0}^{k}T^{(\ell)}H^{(0)}\) \\ \hline \hline \end{tabular} (*) recall that for FAGCN, \(\Gamma^{(k)}\) is identical for all \(k\), and we use a simplified notation \(\Gamma\) to denote all \(\Gamma^{(k)}\)’s.

(**) recall that for GPRGNN and DAGNN, \(\mathcal{A}^{(k)}\) is identical for all \(k\), and we use \(\mathcal{A}\) to denote all \(\mathcal{A}^{(k)}\)’s (here, \(\mathcal{A}^{k}\) is the \(k\)-th power of \(\mathcal{A}\))

\end{table}
Table 2: Propagation of Graph Attention Models
### Theoretical Problems of Deep Graph Attention

Two assumptions are used throughout our theoretical analyses, and proper normalization and preprocessing may always satisfy them in practice.

**Assumption 1**.: The graph \(G\) is connected and non-bipartite, and the initial node features in \(X\) are pairwise distinct (i.e., \(X_{i}\star X_{j},\forall i\neq j\in V\)) and finite (i.e., \(\left\|X_{i}\right\|_{F}<\infty\), \(\forall i\in V\)).

**Assumption 2**.: There exists a global constant \(C_{param}>0\) such that, for each considered GNN model, each entry of each parameter matrix or vector (e.g., \(W^{(k)}\)'s) and each entry of each intermediate variable (e.g., \(H^{(k)}\)'s and \(Z^{(k)}\)'s) is bounded in \([-C_{param},C_{param}]\).

**Problem 1: Vulnerability to Over-Smoothing.** In the first problem, we establish a connection between attention functions6 and the node feature over-smoothing. Specifically, we examine the _vulnerability_ and _resistance_ of attention functions to over-smoothed node features. Informally, if the pre-normalized edge attention coefficients \(\tilde{\alpha}_{i}^{(k)}\)'s (resp., hop attention coefficients \(\gamma_{i}^{(k)}\)'s) are always identical for the node pairs (resp., nodes) with identical (over-smoothed) hidden features, the attention function is vulnerable to over-smoothing. 7 For simplicity, we use \(f_{att}=f_{att}(\theta)\) to denote \((\bar{\mathcal{A}},\Gamma)\), where \(\theta\) denotes GNN parameters.

Footnote 6: We see attention matrices as functions here.

Footnote 7: We use such a definition using the _equality_ of node features for simplicity. See Appendix A.4 for a relaxed version of Definition 1.

**Definition 1**.: Given \(G=(V,E)\) and initial node features \(X\) satisfying Assumption 1, suppose that \(H_{i}^{(k^{\prime})}=H_{i^{\prime}}^{(k^{\prime})}\) and \(H_{j}^{(k^{\prime})}=H_{j^{\prime}}^{(k^{\prime})}\) holds (due to the over-smoothing of node features) for some \((i,j),(i^{\prime},j^{\prime})\in E\) and \(k^{\prime}\geq 1\). We say that \(f_{att}\) is _vulnerable to over-smoothing_ (V2OS), if \(\forall\theta\), \(\tilde{\alpha}_{ij}^{(k^{\prime}+1)}=\tilde{\alpha}_{i^{\prime}j^{\prime}}^{ (k^{\prime}+1)}\) and \(\gamma_{i}^{(k^{\prime})}=\gamma_{i^{\prime}}^{(k^{\prime})}\); that \(f_{att}\) is _weakly resistant to over-smoothing_ (WR2OS), if \(\exists\theta\), \(\tilde{\alpha}_{ij}^{(k^{\prime}+1)}\neq\tilde{\alpha}_{i^{\prime}j^{\prime}}^ {(k^{\prime}+1)}\) or \(\gamma_{i}^{(k^{\prime})}\neq\gamma_{i^{\prime}}^{(k^{\prime})}\); and that \(f_{att}\) is _strongly resistant to over-smoothing_ (SR2OS), if \(\exists\theta\), \(\tilde{\alpha}_{ij}^{(k^{\prime}+1)}\neq\tilde{\alpha}_{i^{\prime}j^{\prime}}^ {(k^{\prime}+1)}\) and \(\gamma_{i}^{(k^{\prime})}\neq\gamma_{i^{\prime}}^{(k^{\prime})}\).

_Remark 1_.: Definition 1 is practically significant. A GNN with WR2OS/SR2OS \(f_{att}\) can possibly remain expressive, even when some node features in intermediate layers begin to over-smooth. An expressive \(f_{att}\) can mitigate widely known problems of deep GNNs, including over-smoothing and over-squashing.

**Theorem 1**.: _For GATv2, GPRGNN, and DAGNN, \(f_{att}\) is V2OS; for FAGCN, \(f_{att}\) is WR2OS (but not SR2OS)._

Proof.: All the proofs are in Appendix A. 

**Problem 2: Smooth Cumulative Attention.** If Problem 1 does not exist, such that the attention coefficients are non-trivial for any model depth, can the attention functions remain expressive over deeper layers? We argue not. For the representative attention-based GNNs, we show that the cumulative attention matrices \(T^{(k)}\)'s become over-smoothed over increasing layers, such that different nodes have attention close to each other, up to a positive scaling factor. _This is critically contrary to the goal of attention_. Formally, we define a smoothness score \(S:\mathbb{R}^{n\times n}\rightarrow\mathbb{R}_{\geq 0}\) by

\[S(T)=\sum\nolimits_{(i,j)\in\binom{[n^{\times}]}{2}}\left\|\frac{T_{i}^{(k)}}{ \left\|T_{i}^{(k)}\right\|_{1}}-\frac{T_{j}^{(k)}}{\left\|T_{j}^{(k)}\right\|_ {1}}\right\|_{1}\Big{/}\binom{n}{2}.\lx@note{footnote}{We use such a definition using the _equality_ of node features for simplicity. See Appendix A.4 for a relaxed version of Definition 1.} \tag{4}\]

\(S(\cdot)\) is bounded, and a smaller \(S(T^{(k)})\) indicates that \(T^{(k)}\) is smoother. Specifically, when \(S(T^{(k)})=0\), all the rows of \(T^{(k)}\) become equivalent up to a positive scaling factor. See Appendix A for more theoretical properties of \(S(\cdot)\).

**Theorem 2**.: _Given \(G=(V,E)\) and \(X\) with Assumptions 1 and 2 satisfied, for GATv2, GPRGNN, and DAGNN, \(\lim_{k\rightarrow\infty}S(T^{(k)})=0\); for FAGCN, \(\lim_{k\rightarrow\infty}T_{ij}^{(k)}=0,\forall i,j\)._

By Theorem 2, for the aforementioned attention-based GNNs, \(S(T^{(k)})\) converges to 0 and loses expressiveness as \(k\) goes to infinity. Importantly, in our proofs, we show that problem 2 occurs _without assuming problem 1_.

Below, we provide some insights into the reason why the GNNs without _node-adaptive hop attention_ or _negative attention_ may suffer from the problem stated above.

**Definition 2**.: Given \(G=(V,E)\), and \(i,j\in V\), the set of _attention path_ between \(i\) and \(j\) at layer \(k\), denoted as \(\mathcal{P}^{(k)}(i,j)\), is defined as \(\{(i=v_{0},v_{1},v_{2},\ldots,v_{k-1},v_{k}=j):(v_{l-1},v_{l})\in E,\forall 1 \leq l\leq k\}\), i.e., the set of all the paths of length \(k\) from \(i\) to \(j\) in \(G\).9 The _degree of intersection_ between two paths \(\mathbf{p}_{v}=(v_{0},v_{1},v_{2},\ldots,v_{k-1},v_{k})\) and \(\mathbf{p}_{u}=(u_{0},u_{1},u_{2},\ldots,u_{k-1},u_{k})\), denoted by \(\mathrm{doi}(\mathbf{v},\mathbf{u})\), is defined as \(|\{t:1\leq t\leq k,v_{t-1}=u_{t-1},v_{t}=u_{t}\}|\).

Footnote 9: Unlike _simple_ paths, repeated nodes are allowed.

_Remark 2_.: The intuition of Definition 2 is that we can decompose each entry \(T_{ij}^{(k)}\) with respect to attention paths from \(j\) to \(i\). Specifically, \(T_{ij}^{(k)}=\gamma_{i}^{(k)}\sum\nolimits_{(j=v_{0},v_{1},\ldots,v_{k}=i) \in\mathcal{P}^{(k)}(j,i)}\prod_{l=1}^{k}\alpha_{v_{l-1},v_{l}}^{(l)},\forall i,j,k\).

**Lemma 1**.: _Given \(G=(V,E)\) and initial node features satisfying Assumption 1, \(i,j,x\in V\), and any \(N_{1},N_{2}>0\), there exists \(K\) such that \(|\{(\mathbf{p}_{i},\mathbf{p}_{j}):\mathbf{p}_{i}\in\mathcal{P}^{(k)}(i,x), \mathbf{p}_{j}\in\mathcal{P}^{(k)}(j,x),\mathrm{doi}(\mathbf{p}_{i},\mathbf{p} _{j})\geq N_{1}\}|\geq N_{2},\forall k\geq K\)._

Proof.: All the proofs are in Appendix A. 

By Lemma 1 and Remark 2, the constituent terms of \(T_{ix}\) and \(T_{jx}\) increasingly intersect at deeper layers for any \(i,j,x\).
In other words, bounds of \(f_{att}\) and growing degree of intersection in \(T^{(k)}\) together can cause problem 2, irrespective of \(f_{att}\)'s expressive power at each layer. This partially explains why some GNNs without node-adaptive hop attention or negative attention end up with a smooth cumulative attention \(T^{(k)}\). More details can be found in the proof of Theorem 2 in Appendix A.

While we focused on GATv2, which is a representative variant of GAT, in our theoretical analysis, our analysis can be easily extended to other GAT variants, such as SuperGAT (Kim and Oh, 2021) with a self-supervised loss term, and CATs (He et al., 2021) further using structural features. See Appendix A for more discussions on those variants.

## 4 Proposed Method: AERO-GNN

In this section, we introduce the proposed model, Attentive dEep pROpagation-GNN (AERO-GNN). We present the model overview and discuss its attention functions. Finally, we show how AERO-GNN provably addresses the theoretical limitations, with a discussion on model complexity (spec., number of parameters).

### Model Overview

The feature transformation and propagation of AERO-GNN consist of:

\[H^{(k)} =\begin{cases}\mathrm{MLP}(X),&\text{if }k=0,\\ \mathcal{A}^{(k)}H^{(k-1)},&\text{if }1\leq k\leq k_{max},\end{cases} \tag{5}\] \[Z^{(k)} =\sum_{\ell\sim 0}^{k}\Gamma^{(\ell)}H^{(\ell)},\forall 1\leq k \leq k_{max},\] (6) \[Z^{*} =\sigma(Z^{(k_{max})})W^{*}, \tag{7}\]

where \(\mathrm{MLP}\) is a multi-layer perceptron for the feature transformation, \(k_{max}\) is the total number of layers, \(W^{*}\) is a learnable weight matrix, \(Z^{*}\) is the final output node features, and \(\sigma=\mathrm{ELU}\)(Clevert et al., 2016) is the activation function.

AERO-GNN computes the edge attention matrix \(\mathcal{A}^{(k)}\) and the hop attention matrix \(\Gamma^{(k)}\) with learnable parameters. The propagation of AERO-GNN can also be written in terms of the cumulative attention matrices \(T^{(k)}\)'s in Eq. (3), like the other attention-based GNNs (see Table 2). Specifically,

\[Z^{(k)}=\sum_{\ell\sim 0}^{k}T^{(\ell)}H^{(0)},\forall 1\leq k\leq k_{max}. \tag{8}\]

### Using Layer-Aggregated Features

We design AERO-GNN to use the layer-aggregated features \(Z^{(k)}\) in computing both the edge attention \(\mathcal{A}^{(k)}\) and the hop attention \(\Gamma^{(k)}\) at each layer \(k\) to make it resistant to over-smoothing. In Theorem 1, FAGCN is the only model that is WR2OS (_weakly resistant to over-smoothing_), since it uses \(Z^{(k)}\)'s for computing its edge attention (see Table 1). Even if the node features become over-smoothed at deep layers, a GNN using layer-aggregated features \(Z^{(k)}\) can adjust the edge (and hop) attention coefficients based on the cumulative information over multiple layers to allow attention functions to be non-trivial.

However, the magnitude of \(Z^{(k)}\) may increase as \(k\) increases, as shown in Eq. (6), which may cause instability. We, thus, utilize weight-decay (Chen et al., 2020) to re-scale \(Z\). Formally, the re-scaling is done by

\[\begin{cases}\lambda_{k}&=\log(\frac{\lambda}{k}+1+\epsilon)\\ \tilde{Z}^{(k)}&=\lambda_{k}Z^{(k)}\end{cases}\]

where \(\lambda>0\) is a hyperparameter, and \(\epsilon>0\) is a small number (we use \(\epsilon=10^{-6}\)) ensuring that \(\lambda_{k}\) does not converge to \(0\). We use \(\tilde{Z}^{(k)}\) in the computation of both attention functions.

### Attention Functions

**Edge Attention.** At every layer \(1\leq k\leq k_{max}\), we compute the pre-normalized edge attention \(\tilde{\mathcal{A}}^{(k)}=(\tilde{\alpha}^{(k)}_{ij})\) and the (normalized) edge attention \(\mathcal{A}^{(k)}=(\alpha^{(k)}_{ij})\) as follows:

\[\begin{cases}\tilde{\alpha}^{(k)}_{ij}&=\mathrm{softplus}\big{(}(W^{(k)}_{edge })^{\tau}\sigma(\tilde{Z}^{(k-1)}_{i}\|\tilde{Z}^{(k-1)}_{j})\big{)}\\ \alpha^{(k)}_{ij}&=\tilde{\alpha}^{(k)}_{ij}/\sqrt{\sum_{j^{\prime}\in N(i)} \tilde{\alpha}^{(k)}_{ij^{\prime}}\sum_{i^{\prime}\in N(j)}\tilde{\alpha}^{( k)}_{ij^{\prime}}}\end{cases}\]

where \(W^{(k)}_{edge}\) is a learnable weight vector, \(\tilde{Z}^{(k-1)}\) is the \(i\)-th row of \(\tilde{Z}^{(k-1)}\), and \(\mathcal{A}^{(k)}\) is symmetrically normalized.

In AERO-GNN, we use the symmetric normalization, instead of the row-wise normalization used in GATv2, due to its theoretical and empirical superiority (Wang et al., 2018; He et al., 2020), especially w.r.t. training stability. Softplus (Zheng et al., 2015) is used to positively map edge attention, with two primary advantages over two other mapping functions, \(\exp\) and \(\tanh\). Compared to \(\exp\) used in GATv2, softplus has the higher computational stability (Kleshchevnikov, 2020; Nbro, 2020). Note that the bound of \(\tanh\), in addition to degree normalization, essentially makes \(\lim_{k\to\infty}T^{(k)}_{ij}=0\), \(\forall i,j\), for FAGCN (see Theorem 2).

**Hop Attention.** At each layer \(0\leq k\leq k_{max}\), we use \(H^{(k)}\) and \(\tilde{Z}^{(k-1)}\) (for \(k\geq 1\)) to compute the hop attention \(\Gamma^{(k)}\):

\[\begin{cases}\gamma^{(0)}_{i}&=(W^{(0)}_{hop})^{\tau}\sigma(H^{(0)}_{i})+b^{(0)} _{hop}\\ \gamma^{(k)}_{i}&=(W^{(k)}_{hop})^{\tau}\sigma(H^{(k)}_{i}\|\tilde{Z}^{(k-1)}_{ i})+b^{(k)}_{hop},\forall 1\leq k\leq k_{max}\end{cases}\]

where \(W^{(k)}_{hop}\) is a learnable weight vector and \(b_{hop}\) is a learnable bias scalar.

Motivated by Theorem 2, we use node-adaptive hop attention to alleviate the problem of "intersecting attention paths" stated in Lemma 1, and we allow both positive and negative hop attention coefficients to prevent \(S(T^{(k)})\) from converging to zero as \(k\) goes to infinity (note that \(\gamma^{(k)}_{i}\)'s of the same sign within the same layer \(k\) cannot change \(S(T^{(k)})\)).
Importantly, \(b_{hop}^{(k)}\) should be initialized as 1s. This contributes significantly to model training stability by biasing the hop attention \(\gamma_{i}^{(k)}\)'s to be initialized positive.

### Theoretical Merits

We summarize below the theoretical merits of AERO-GNN. First, AERO-GNN provably mitigates the problems of deep graph attention stated in Section 3 (Theorems 1 and 2).

**Theorem 3**.: _For AERO-GNN, \(f_{att}\) is SR2OS (see Def. 1)._

**Theorem 4**.: _Given \(G=(V,E)\) and \(X\) with Assumptions 1 and 2 satisfied, for AERO-GNN, \(\forall T^{(k)}\) (spec., even if \(S(T^{(k)})=0\)), \(\exists\theta\) such that \(S(T^{(k+1)})>0\).10_

Footnote 10: Recall that \(\theta\) represents all the parameters in the GNN model.

The number of parameters used by AERO-GNN is comparable to, or even smaller than, those of the edge-attention GNNs. We ignore the parameters used in computing the first hidden features (\(H^{(0)}\)) and those in the output layer, since they are used in all GNN models. Thus, we only consider the number of _additional parameters_. Analysis for more models can be found in Appendix E.

**Theorem 5**.: _Given the dimension \(d_{H}\) of hidden node features and the number of layers \(k_{max}\), for AERO-GNN and FAGCN, the number of additional parameters is \(\Theta(k_{max}d_{H})\); for GATv2, the number is \(\Theta(k_{max}d_{H}^{2})\)._

Proof.: All the proofs are in Appendix A. 

## 5 Experiments

In this section, we conduct experiments to demonstrate the empirical strengths of AERO-GNN and elaborate on the theoretical analyses.

### Experimental Settings

**Datasets.** We use 12 node classification benchmark datasets, among which 6 are homophilic and 6 are heterophilic (McPherson et al., 2001; Pei et al., 2020; Lim et al., 2021). In all the experiments, we use the publicly available train-validation-test splits, unless otherwise specified. We use _sparse-labeled_ training for homophilic graphs and _dense-labeled_ training for heterophilic graphs (small and large proportions of train labels, respectively; refer to Appendix C for details).

**Baseline Methods.** The baseline methods consist of various representative attention-based GNNs, including both _edge-attention GNNs_ (GATv2, GATv2\({}^{R}\), GT (Shi et al., 2021), FAGCN, DMP (Yang et al., 2021))11 and _hop-attention GNNs_ (GPRGNN, DAGNN, MixHop (Abu-El-Haija et al., 2019)). In addition to some _simple GNNs_ (GCN (Welling and Kipf, 2016), APPNP (Gasteiger et al., 2018)), _deep GNNs_ without attention also serve as baselines (GCN-II (Chen et al., 2020), A-DGN (Gravina et al., 2023)). See Appendix E and F for their details.

Footnote 11: GATv2\({}^{R}\) is a GATv2 model with initial residual connection.

**Experiment Details.** The Adam optimizer (Kingma and Ba, 2015) is used to train the models, and the best parameters are selected based on early stopping. In measuring model performance (Section 5.2), we use 100 predetermined random seeds and report the mean \(\pm\) standard deviation (SD) of classification accuracy over 100 trials. When analyzing attention coefficient distribution (Section 5.3), attention coefficients are averaged over 10 trials.

### Node-Classification Performance

We evaluate the performance of each model on 12 real-world node classification benchmarks.

\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c} \hline \hline
**Dataset** & Chameleon & Squirrel & Actor & Texas & Cornell & Wisconsin & Computer & Photo & Wiki-CS & Pubmed & Citeseer & Cora & A.R. \\ \hline
**Homopally** & 0.04 & 0.03 & 0.01 & 0.00 & 0.02 & 0.05 & 0.70 & 0.77 & 0.57 & 0.66 & 0.63 & 0.77 & \\ \hline \hline
**GCN** & 67.97 \(\pm\) 2.5 & 53.33 \(\pm\) 1.3 & 30.57 \(\pm\) 0.7 & 65.65 \(\pm\) 4.8 & 58.41 \(\pm\) 3.3 & 62.02 \(\pm\) 5.9 & 81.27 \(\pm\) 1.4 & 90.24 \(\pm\) 1.3 & 79.08 \(\pm\) 0.5 & 79.54 \(\pm\) 0.4 & 72.50 \(\pm\) 0.5 & 83.15 \(\pm\) 0.5 & 9.1 \\
**APNP** & 53.04 \(\pm\) 2.2 & 40.37 \(\pm\) 1.5 & 35.49 \(\pm\) 1.0 & 79.89 \(\pm\) 4.2 & 80.16 \(\pm\) 5.9 & 84.24 \(\pm\) 4.6 & 81.27 \(\pm\) 1.4 & 91.12 \(\pm\) 1.2 & 79.05 \(\pm\) 0.5 & 79.90 \(\pm\) 0.3 & 73.06 \(\pm\) 0.3 & 83.60 \(\pm\) 1.3 & 7.8 \\ \hline
**GCN-II** & 60.38 \(\pm\) 1.9 & 48.76 \(\pm\) 2.4 & 35.77 \(\pm\) 1.0 & 78.59 \(\pm\) 6.6 & 78.84 \(\pm\) 6.6 & 83.20 \(\pm\) 4.7 & 84.24 \(\pm\) 1.2 & 91.81 \(\pm\) 0.9 & 79.28 \(\pm\) 0.6 & 80.14 \(\pm\) 0.6 & 72.00 \(\pm\) 0.1 & 86.30 \(\pm\) 0.18 & 5.5 \\
**A-DGN** & 69.63 \(\pm\) 2.0 & 57.77 \(\pm\) 1.9 & 36.41 \(\pm\) 1.0 & 82.22 \(\pm\) 4.8 & **81.41 \(\pm\) 0.7** & **83.44 \(\pm\) 1.5 & 90.53 \(\pm\) 1.3 & 79.11 \(\pm\) 0.6 & 78.68 \(\pm\) 0.6 & 70.16 \(\pm\) 0.9 & 79.84 \(\pm\) 0.9 & 6.4 \\ \hline
**GAT** & 68.01 \(\pm\) 2.5 & 54.49 \(\pm\) 1.7 & 30.36 \(\pm\) 0.9 & 60.46 \(\pm\) 6.2 & 58.22 \(\pm\) 3.7 & 63.59 \(\pm\) 6.1 & 84.46 \(\pm\) 1.3 & 89.88 \(\pm\) 1.1 & 79.44 \(\pm\) 0.5 & 78.94 \(\pm\) 0.4 & 71.89 \(\pm\) 0.6 & 83.78 \(\pm\) 0.8 & 8.5 \\
**GATv2** & 60.08 \(\pm\) 2.2 & 57.62 \(\pm\) 3.02 & 30.83 \(\pm\) 7.0 & 58.38 \(\pm\) 3.8 & 61.94 \(\pm\) 4.7 & 81.94 \(\pm\) 2.1 & 89.87 \(\pm\) 1.2 & 79.64 \(\pm\) 0.5 & 72.92 \(\pm\) 0.3 & 71.23 \(\pm\) 1.12 & 83.88 \(\pm\) 0.6 & 8.9 \\
**GATv2** & **61.92 \(\pm\) 1.91** & **62.18 \(\pm\) 1.37 \(\pm\) 0.9** & 60.86 \(\pm\) 6.5 & 57.32 \(\pm\) 4.5 & 60.15 \(\pm\) 5.1 & 81.73 \(\pm\) 2.8 & 88.71 \(\pm\) 1.7 & 79.55 \(\pm\) 0.6 & 78.28 \(\pm\) 0.4 & 71.00 \(\pm\) 0.8 & 83.24 \(\pm\) 0.6 & 9.3 \\
**GT** & 69.34 \(\pm\) 1.2 & 55.04 \(\pm\) 1.9 & 36.29 \(\pm\) 1.0 & **63.54** & 80.00 \(\pm\) 4.9 & **44.83** & 84.38 \(\pm\) 1.3 & 91.28 \(\pm\) 1.1 & **79.03** \(\pm\) 0.5 & 79.04 \(\pm\) 0.5 & 70.16 \(\pm\) 0.8 & 82.09 \(\pm\) 0.7 & 5.6 \\
**FAGCN** & 69.88 \(\pm\) 2.3 & 42.20 \(\pm\) 1.8 & 36.57 \(\pm\) 0.7 & 77.30 \(\pm\) 7.7 & 78.32 \(\pm\) 6.3 & 82.41 \(\pm\) 3.8 & 28.79 \(\pm\) 1.2 & 91.99 \(\pm\) 1.0 & 79.27 \(\pm\) 0.6 & 79.19 \(\pm\) 0.4 & 71.55 \(\pm\) 0.8 & 83.85 \(\pm\) 0.5 & 7.5 \\
**DMP** & 63.79 \(\pm\) 1.4 & 34.9 \(\pm\) 7.6 & 28.30 \(\pm\) 2.7 & 66.88 \(\pm\) 7.0 & 56.41 \(\pm\) 5.5 & 67.33 \(\pm\) 4.5 & 70.88 \(\pm\)
**On Heterophilic Graphs.** As described in Section 5.1, dense-labeled training is used on heterophilic graphs, following prior research. On heterophilic datasets, AERO-GNN obtains significant and consistent performance gains compared to the baseline models. Even in relatively small graphs (e.g., _texas_, _cornell_, _wisconsin_), where three propagation layers are enough to reach most nodes, AERO-GNN outperforms all the baseline attention-based GNNs. In other words, even when the relative advantage of a deeper model is small, AERO-GNN still maintains competitive performance. Despite being specifically designed to address the heterophily problem, FAGCN, DMP, and GPRGNN are outperformed by AERO-GNN.

**On Homophilic Graphs.** In line with the prior research, sparse-labeled training is used for homophilic graphs. This poses a distinct set of challenges from dense-labeled training in heterophilic graphs, especially for attention-based GNNs. That is because, in homophilic graphs, the relative importance of each neighbor may not vary as significantly as it does in heterophilic graphs. Additionally, with a small number of train labels, deep and complex models may prone to overfitting. As a result, only a few models achieve strong performance in both settings (GCN-II, GT, and GPRGNN perform the best among the baselines). Despite such difficulties, AERO-GNN demonstrates strong performance, ranking first in 5 out of the 6 homophilic datasets.

For further evaluation, we discuss AERO-GNN's performance with multi-head attention and with datasets proposed by Platonov et al. (2023) in Appendix G, where AERO-GNN still has the best average ranking among the competitors.

### Empirical Elaboration of the Theoretical Analysis

In this section, we empirically elaborate on the theoretical limitations of the representative attention-based GNNs (Theorems 1, 2) and show that AERO-GNN effectively mitigates the problems (Theorems 3, 4). Specifically, compared to the baselines, we show that AERO-GNN has

* _edge/node-, hop-, and graph-_adaptive attention function,
* _less smooth_ and _un-smoothing_ cumulative attention \(T^{(k)}\),
* and _higher_ performance at deep layers.

Here, we bring our focus back to GATv2, FAGCN, GPRGNN, DAGNN, and AERO-GNN. 12

Footnote 12: Training of vanilla GATv2 becomes unstable over deeper layers. Thus, for a fair comparison, we use GATv2\({}^{R}\) instead in the following sections.

**Statistics of the Attention Coefficients.** According to Theorems 1 and 3, only AERO-GNN would have both attention functions resistant to the over-smoothed node features. While FAGCN would only have a resistant edge-attention function, the attention coefficient distributions of the other models are expected to shrink or remain stationary with the increasing number of layers (when the over-smoothing of node features is more likely to occur). To test the hypothesis, we train 64 layers of each model and conduct post-hoc analysis of their learned attention distributions.

First, we study the edge-attention coefficients \(\alpha_{ij}^{(k)}\)'s. For each \(k\), Figure 1 presents (**a**) the distribution of \(\alpha_{ij}^{(k)}\)'s and (**b**) the Frobenius norm of the difference between the attention coefficient at layer \(k\) and \((k-1)\), i.e., \(\left\|\left(\alpha_{ij}^{(k)}-\alpha_{ij}^{(k-1)}\right)_{ij}\right\|_{F}= \sqrt{\sum_{i,j}(\alpha_{ij}^{(k)}-\alpha_{ij}^{(k-1)})^{2}}\). 13 If the

Figure 1: **Statistics of \(\alpha_{ij}^{(k)}\)’s for each \(k\) with \(k_{max}=64\). Only AERO-GNN learns edge-, hop-, and graph-adaptive edge attention over deep layers.**
distributions shrink or remain stationary over \(k\) for all graphs, we have strong evidence that attention coefficients are not working properly at deep layers.

For FAGCN, all the coefficients approach zero, and SDs of GATv2's attention coefficients remain stationary for all graphs (see Figure 1(a)). Both FAGCN and GATv2's attention coefficients remain stationary at deep layers, with near 0 difference between \(\alpha_{ij}^{(k)}\) and \(\alpha_{ij}^{(k-1)}\) at large \(k\) (see Figure 1(b)).

Only AERO-GNN's edge attention distributions do not shrink or remain stationary over \(k\). To elaborate, AERO-GNN learns edge attention coefficients that are _edge-adaptive_ (high variances in Figure 1(a)), _hop-adaptive_ (high differences in Figure 1(b)), and _graph-adaptive_ (diverse patterns for different graphs in Figure 1(a)). The results for all 12 datasets are in Appendix G.

We now investigate hop-attention coefficients \(\gamma_{i}^{(k)}\)'s. Figure 2(a) shows the mean value and (b) the SD of \(\gamma_{i}^{(k)}\)'s, for each layer \(k\). Each figure respectively suggests how hop-adaptive and node-adaptive \(\gamma_{i}^{(k)}\)'s are.

Again, as expected, hop attention distributions of DAGNN remain stationary over deep layers, and hence, they are less adaptive to node, hop, or graph (see stationary values in Figure 2(a) and the very small SD values in Figure 2(b)). Since GPRGNN's hop attention \(\gamma_{i}^{(k)}\)'s are free parameters, it learns hop-adaptive and graph-adaptive \(\gamma_{i}^{(k)}\)'s regardless of over-smoothing. However, they are not node-adaptive.

In stark contrast, hop attention coefficients of AERO-GNN are _node-adaptive_ (high SD in Figure 2(b)), _hop-adaptive_ (mean value changes over different layers in Figure 2(a)), and _graph-adaptive_ (diverse patterns for different graphs in Figure 2(a) and (b)). The results for all 12 datasets are in Appendix G.

Through this series of empirical analyses, we present strong evidence that attention functions of the representative attention-based GNNs, except for those of AERO-GNN, are vulnerable to node feature over-smoothing and fail to remain expressive over deep layers.

**Cumulative Attention and Model Performance.** According to Theorems 2 and 4, only AERO-GNN can avoid completely-smoothed cumulative attention (i.e. \(S(T^{(k)})=0\)) over deep layers, highlighting its capacity to learn meaningful attention at any model depth. Here, we empirically elaborate on the theoretical analysis.

Figure 3(a) shows the smoothness scores of cumulative attention matrices \(S(T^{(k)})\). 14 AERO-GNN generally has less smooth \(T^{(k)}\) over deep layers. Notably, there often occurs un-smoothing of \(T^{(k)}\), such that \(S(T^{(k)})>S(T^{(k-1)})\), only for AERO-GNN and FAGCN. This phenomenon is attributable to the use of negative attention in both models. However, \(S(T^{(k)})\) of FAGCN quickly converges to 0. These findings resonate with Theorem 4, showing that AERO-GNN's attention function does remain expressive at deep layers. The results for all 12 datasets are in Appendix G. 15

Footnote 14: Recall that a lower \(S(T^{(k)})\) indicates that the cumulative attention \(T^{(k)}\) is more smoothed

Figure 3(b) illustrates the model performance at layer \(k\in\{2,4,8,16,32,64\}\). AERO-GNN generally achieves better performance over deeper layers. Meanwhile, the performance of the representative attention-based GNNs often drops, even significantly, at deep layers. Table 4 further shows that AERO-GNN generally achieves its best performances at deeper layers than the attention-based GNNs.

In this section, we empirically evaluated the adaptiveness of attention coefficients, smoothness of \(T^{(k)}\), and performance with depth for each model. This set of empirical observa

\begin{table}
\begin{tabular}{c c c c c c c c c c c c c} \hline \hline
**Dataset** & CM & SQ & AT & TX & CN & WC & CP & PT & WK & PM & CS & CR \\ \hline \hline
**GCN-II** & 8 & 4 & 4 & 4 & 4 & 4 & **32** & 4 & 16 & **32** & **64** \\
**A-DGN** & 16 & **32** & **32** & 2 & **32** & 2 & 8 & 16 & 8 & 16 & 4 \\ \hline \hline
**GATv2\({}^{th}\)** & 16 & 16 & 16 & **8** & 2 & 2 & 4 & 4 & 2 & 4 & 2 & 2 \\
**FAGCN** & 2 & 2 & 6 & 7 & 2 & 7 & 7 & 8 & 3 & 8 & 4 & 4 \\
**GPGNN** & 16 & 16 & 4 & 4 & 4 & **8** & 4 & **32** & 16 & 8 & 8 \\
**DAGN** & 5 & 20 & 5 & 5 & 5 & 5 & 5 & 10 & 5 & 20 & 10 \\ \hline
**AERO-GNN** & **32** & 16 & 4 & **8** & 4 & 4 & **32** & **32** & 16 & **32** & **32** & 32 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Best Performing Layers Used in Table 3

Figure 3: **The smoothness of the cumulative attention matrix \(T^{(k)}\) and the model performance. AERO-GNN has (_a_) less smoothed \(T^{(k)}\) over deep layers and (_b_) higher best performance achieved at a deeper layer.**
tions, in concert with the theoretical findings, indicate that AERO-GNN indeed learns the most expressive deep graph attention.

## 6 Discussion

Graph attention has had a significant impact on the research and applications of GNNs. Many attention-based GNNs have been designed, investigating how to better infer relations between node pairs. Some models introduced more features or loss terms (Kim and Oh, 2021; Wang et al., 2019; He et al., 2021), and some others relaxed their attentions to include negative values (Bo et al., 2021; Chien et al., 2021; Yang et al., 2021).

On the other hand, making GNNs deeper to enhance their expressivity has been an important setback to GNN research. A number of problems have been proposed to limit its expressiveness to increase over depth. Not to mention over-smoothing, but also over-squashing and over-correlation have been pointed out as possible problems in building deep GNNs. As such, techniques that modulate propagation or aggregation functions (Chamberlain et al., 2021; Gravina et al., 2023; Li et al., 2020; Bodnar et al., 2022), residual connection functions (Li et al., 2019; Chen et al., 2020; Li et al., 2021), hidden features (Zhou et al., 2020; Zhao and Akoglu, 2020; Guo et al., 2023), or graph topologies (Rong et al., 2020; Chen et al., 2020; Zeng et al., 2021; Topping et al., 2022; Bodnar et al., 2022) have been applied to build deeper GNNs.

In this work, we bridge the two research directions, addressing two underexplored questions: (**a**) what are the unique challenges in deep graph attention, and (**b**) how can we design provably more expressive deep graph attention? We argue that the representative attention-based GNNs suffer from the proposed set of problems, possibly on top of the general problems in deep GNNs. Thus, we design AERO-GNN to theoretically and empirically mitigate the problems.

Under a larger context, these findings extend prior literature on limitations to _deep attention in general_. Specifically, similar problems of deep attention smoothing have been reported for transformers (Vaswani et al., 2017; Dong et al., 2021), in both natural language processing (Shi et al., 2022) and computer vision (Gong et al., 2021; Zhou et al., 2021) domains. We demonstrate that attention-based GNNs share related, yet distinct, problems and propose a novel solution. Hence, we expect this work will inspire future research on deep attention and graph learning in various directions.

The generalizability of the present work is limited in that linear propagation is assumed to define \(T^{(k)}\) of GATs. Also, we deliberately suppress non-linearity in the _propagation layers_ of AERO-GNN to focus on the ability to learn dynamic receptive fields, expressed in \(T^{(k)}\). Still, it can be a promising future work to add non-linear propagation to AERO-GNN to address other challenges and applications to more complex tasks.

## Acknowledgements

This work was supported by Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2022-0-00871, Development of AI Autonomy and Knowledge Enhancement for AI Agent Collaboration) (No. 2019-0-00075, Artificial Intelligence Graduate School Program (KAIST)).
