How Attentive are Graph Attention Networks? 
Authors: Shaked Brody
Uri Alon
Eran Yahav
Venue: ICLR 2022 Poster (2022)
Keywords: graph attention networks
dynamic attention
GAT
GNN

Abstract: Graph Attention Networks (GATs) are one of the most popular GNN architectures and are considered as the state-of-the-art architecture for representation learning with graphs. In GAT, every node attends to its neighbors given its own representation as the query.
However, in this paper we show that GAT computes a very limited kind of attention: the ranking of the attention scores is unconditioned on the query node. We formally define this restricted kind of attention as static attention and distinguish it from a strictly more expressive dynamic attention.
Because GATs use a static attention mechanism, there are simple graph problems that GAT cannot express: in a controlled problem, we show that static attention hinders GAT from even fitting the training data. 
To remove this limitation, we introduce a simple fix by modifying the order of operations and propose GATv2: a dynamic graph attention variant that is strictly more expressive than GAT. We perform an extensive evaluation and show that GATv2 outperforms GAT across 12 OGB and other benchmarks while we match their parametric costs. 
Our code is available at https://github.com/tech-srl/how_attentive_are_gats . GATv2 is available as part of the PyTorch Geometric library, the Deep Graph Library, and the TensorFlow GNN library.

Published as a conference paper at ICLR 2022
HOW ATTENTIVE ARE GRAPH ATTENTION NETWORKS?
Shaked Brudy
Uri Alon
Technion
Language Technologies Institute Carnegie Mellon University ualon@ee cs cmu edu
Eran Yahay
Technion
ABSTRACT
Graph Attention Networks (GATs) are of the popular GNN architectures and are considered as the state-of-the-art architecture for representation learning with graphs. In GAT, every node attends to its neighbors given its represen- tation as the query. However, in this paper we show that GAT computes very limited kind of attention: the ranking of the attention scores is unconditioned on the query node. We formally define this restricted kind of attention static attention and distinguish from a strictly more expressive dynamic attention. Be- cause GATs use a static attention mechanism, there are simple graph problems that GAT cannot express: in a controlled problem, we show that static attention hinders GAT from even fitting the training data. To remove this limitation, we introduce a simple fix by modifying the order of operations and propose GATv2: dynamic graph attention variant that is strictly more expressive than GAT. We perform an extensive evaluation and show that GATv2 outperforms GAT across 12 OGB and other benchmarks while match their parametric costs. Our code is available at https: / //gitt/ttttt thub. com/t teehhtecch-ae sis--rr srl arl/how. arl/how_atteni attent ive__vvrr are gats GATv2 available as part of the PyTorch Geometric library the Deep Graph Library and the TensorFlow GNN library
INTRODUCTION
Scarselli et al. 2008) have increasing popularity over the past few years (Duvenaud et al, 2013 Atwood and Towsley 2016 Bronstein et al. 2017 Monti al. 2017). GNNs provide general and efficient framework to learn from -rrph-structured data. Thus, GNNs are easily applicable in domains where the data can be represented as a set of nodes and the prediction depends on the relationships (edges) between the nodes. Such domains include molecules, social networks, product recommendation. computer programs and more.
Graph neural networks (GNNs; Gori et al. 2005:
In GNN, each node iteratively updates its state by interacting with its neighbors. GNN variants
(Wu et al. 2019: Xu et al.) 2019: Li et al. 2016) mostly differ in how each node aggregates and combines the representations of its neighbors with own. Veličković al. (2018) pioneered the use of attention-basee neighborhood aggregation, in one of the most common GNN variants Graph Attention Network (GAT). In GAT, every node updates its representation by attending to its neighbors using its own representation as the query. This generalizes the standard averaging max max-pooling of neighbors (Kipf and Welling 2017 Hamilton et al. 2017). by allowing every node to compute weighted average of its neighbors, and (sofily) select its most relevant neighbors. The work of
An anmotated implementation of GATv2 is available frrmm torch_geomerric..
conv. gatv2_conv import GATv2Conv
from dgl. ww..npppttt pytorhh import GAT from tenserf1 lonsorfloo_gnnggrrah.... keras. layers.gatt _at__att____ v2 import GATv2Convo1utis

---

Published as a conference paper at ICLR 2022
k0
k1
K2
K3
K4
K5
k6
k7
k8
k9
kO
K1
k2
K3
k4
k5
k6
k7
k8 k9
90
0.08
0.10
0.10
0.07
0.08
0.08
0.11
0.09
0.20
0.08
90
-0.95
0.00
0:00
0.01
0.01
0.00
0.00
0.02
0.01
0.00
q1
q1
92
0.05
0.10 0.10
0.04 0.OS
0.05
0. 0.13
0.06
0.38
0.05
92
0.00
0.00
0.95
0.00
0.00
0.01
0.02
0.01
0.00 0.00
q3
q3
0.01
0.00
0.00
q4
0.08
0.09
0.09
0.07 D.07 0.07
0.10
0.08
0.27
0.07
q4
0.00
0.00
0.00
0.00
0.96
0.00
0.00
0.01
0.01
0.00
q5
0.11
0:11
0.08
0.09
q5
0.00
0.02
0:01
0.01
0.01
0.02
q6
0.04
0.10 0.11 0.03 0.O4
0.04
0.14
0.06
0.40
0.04
q6
0.00
0.03
0.04
0.00
0.01
0.01
0.86
0.02
0.01
0.03
q7
0.07
0.09 0.09
0.06 0.07
0.08
0.29
0.07
q7
0.04
0.02
0.01
0.01
0.03
0.00
0.87
0.00
0.01
48
0.11 6.11 0.02
0.04
q8
0.01
0.01
0.01
0.00
q9
0.07 09 0.09 0.06 0.07
0.07
0.11
0.08
0.30
0.07
q9
0.01
0.02
0.01
0.01
0..01
0.01
0.01
0.00
0.00
0.93
1.0
0.4
q0
q1
q2
0.8
q3
90
0.3
q4
91
q5
0.6
92
q6
q3
0.2
q7
q4
q8
0.4
q5
96
q9
97
0.2
98
99
0.0
kO K1 k2 K3
k4
k5
k6 k7
k8 k9
kO k1 k2 k3 k4 K5 K6 k7 kB k9
(a) Attention in standard GAT Veličković et al. 2018))
(b) Attention in GATv2, our fixed version of GAT
complete bipartite graph of "query nodes" {qD...., 99} and "key nodes" (kO,... ..., A:9 standard GAT (Figure Tab computes static attention the ranking of attention coefficients is global for all nodes in the graph, and unconditioned on the query node. For example, all queries (g0 to 99) attend mostly to the 8th key (k8). In contrast, GATv2 (Figure lb) can actually compute dynamic attention, where every query has a different ranking of attention coefficients of the keys.
Figure/ 1:
Veličković et al.) also generalizes the Transformer's (Vaswani et al. 2017) self-attention mechanism, from sequences to graphs (Joshi 2020).
Nowadays, GAT is of the most popular GNN architectures (Bronstein et al. 2021 and is considered as the state-of sfate-of-the-an the-art neural architecture for learning with graphs (Wang et al. 2019a). Nevertheless, in this paper show that GAT' does actually compute the expressive, well known, type of attention (Bahdanau et al.) 2014), which we call dynamic attention. Instead, we show that GAT computes only restricted "static" form of attention: for any query node, the attention function is monotonic with respect to the neighbor (key) scores. That is, the ranking (the argsort) of attention the query node. This fact
coefficients is identical for all nodes in the graph, and is unconditioned severely hurts the expressiveness of GAT, and is demonstrated in Figure
Supposedly, the conceptual idea of attention as the form of interaction between GNN nodes is orthogonal to the specific choice of attention function. However, Veličković et al. original design of GAT has spread
variety of domains (Yang et al.] 2020 Wang et 2019c Huang and Carley 2019 Ma et al. 2020) Kosaraju al. 2019 Nathani et al. 2219 Wu et al. [2200] Zhang et al. 2020) and has become the default implementation of "graph attention network" in all popular GNN libraries such as PoTorc Geometric (Fey and Lenssen, 2019), DGL (Wang et al. 2019b), and others (Dwivedi jet al. 2020 Gordic 2020 Brockschmidt) (2020). Many other works employed GNNs with attention mechanisms other than the standard GAT's 's (Yun et al. (2019), see also Appendix [A]. However, none of these works identified the monotonicity of GAT's attention mechanism, the theoretical differences between attention types, empirically compared their performance.
2

---

Published as a conference paper at ICLR 2022
To overcome the limitation we identified in GAT, introduce simple fix its attention function by only modifying the order of internal operations. The result is GATv2 - graph attention variant that has a universal approximator attention function, and is thus strictly more expressive than GAT. The effect of fixing the attention function in GATv2 is demonstrated in Figure Tb
In summary, our main contribution is identifying that of the most popular GNN types, the graph attention network, does not compute dynamic attention, the kind of attention that it seems to compute. We introduce formal definitions for analyzing the expressive power of graph attention mechanisms (Definitions 3.1 and 3.2). and derive our claims theoretically (Theorem I from the equations of Veličković et al. (2018). Empirically, we use a synthetic problem to show that standard GAT cannor express problems that require dynamic attention (Section 4.1. We introduce simple fix by switching the order of internal operations in GAT, and propose GATv2, which does compute dynamic attention (Theorem 2). We further conduct thorough empirical comparison of GAT and GATv2 and find that GATv2 outperforms GAT across 12 benchmarks of node-, link-, and graph-prediction. For example, GATv2 outperforms extensively tuned GNNs by over 1.4% in the difficult "UnseenProj Test" set of the VarMisuse task (Allamanis et al.) 2018), without any hyperparameter tuning; and extensively-tuned GAT by 11.5% in 13 prediction objectives in QM9. In mode-predictto benchmarks from OGB (Hu et al. 2020). not only that GATv2 outperforms GAT with respect to accuracy we find that dynamic attention provided much better robustness noise.
GATv2 improves
2 PRELIMINARIES
A directed graph G = (V, E) contains nodes V = (1,..., n) and edges & C V x denotes an edge from a node j to node i. We assume that every node E has an initial representation h E 1o. An undirected graph can be represented with bidirectional edges.
V. where (j.i) E &
2.1 GRAPH NEURAL NETWORKS
graph neural network (GNN) layer updates every node representation by aggregating its neighbors' representations. A layer's input is set of node representations {h; E Rd i V} and the set of
edges E. A layer outputs new set of node representations {h/ Rdd E V}, where the same parametric function is applied to every node given its neighbors N₁ = (j E (,)) EE):
(1) The design of f and AGGREGATE is what mostly distinguishes type of GNN from the other. For example, a common variant of GraphSAGE (Hamilton et al. (017) performs an element-wise mean as AGGREGATE, followed by concatenation with h; a linear layer and ReLU as f.
h Se (h,, AGGREGATE ([h, |j N.)))
2.2 GRAPH ATTENTION NETWORKS
GraphSAGE and many other popular GNN architectures (Xu et al., 2019: Duvenaud et al. 2015) weigh all neighbors j E A₁ with equal importance (e.g.. mean or max- srax-pooling as AGGREGATE). To address this limitation, GAT (Veličković et al. 2018)) instantiates Equation (1) by computing learned weighted average the representations of N, A scoring function e Rd x add + R computes a score for every edge (j. which indicates the importance of the features of the neighbor j to the node i:
e eh,, h2) = LeakyReLU (aT [Wh (h,,)
(2)
where a E 2d We E IRdd xd are learned, and || denotes vector concatenation. These attention scores are normalized across all neighbors e NN using softmax, and the attention function is defined as:
exp (h;; h2))
aij = softmax, (h; h2)) EyEN, exp (e (h, hz))
(3)
Then, GAT computes a weighted average of the transformed features of the neighbor nodes (followed by nonlinearity σ)) as the new representation of using the normalized attention coefficients:
h = a
Σ JEN, asj Wh;)
(4)
From now on, will refer to Equations
2 4 the definition of GAT.
3

---

Published as a conference paper at ICLR 2022
3 THE EXPRESSIVE POWER OF GRAPH ATTENTION MECHANISMS
In this section, we explain why attention is limited when it is not dynamic (Section We then show that GAT is severely constrained, because it can only compute static attention (Section 3.2) Next, we show how GAT can be fixed (Section 3.3), by simply modifying the order of operations.
We refer to neural architecture (e.g., the scoring or the attention function of GAT) a famity of functions, parameterized by the learned parameters. An element in the family is concrete function with specific trained weights. In the following, we use [nx] to denote the set [n] {1,2, -.. n) C N.
3.1 THE IMPORTANCE OF DYNAMIC WEIGHTING
Attention is a mechanism for computing distribution over a set of input key vectors, given an additional query vector. the attention function always weighs one key at least as much as any other key, unconditioned on the query, we say that this attention function is static:
Definition 3.1 (Static attention). A (possibly infinite) family of scoring functions FC (R4 x R - IR) computes static scoring for given set of key vectors K- (k,,.... C IR and
query vectors Q = (q,,.., qm) C CR,, if for every f E F there exists "highest scoring" key js [n]
such that for every query E [m] and key j E [n] it holds that f (q: k;,) f (q: (q. ky)). We say that a family of attention functions computes static atlention given K and Q, if its scoring function computes static scoring, possibly followed by monotonic normalization such softmax.
Static attention is very limited because every function I E F has key that is always selected, regardless of the query. Such functions cannot model situations where different keys have different relevance to different queries. Static attention is demonstrated in Figure Ia
The general and powerful form of attention is dynamic attention:
Definition 3.2 (Dynamic attention). A (possibly infinite) family of scoring functions F C (Rd x Rd -> IR.) computes dynamic scoring for a given set of key vectors IK k= (ki,..., C Red and query vectors Q = (qI..... qm CR, if for any mapping yo: [m] + [m]] there exists f E F such that for any query E [m]] and any key }イ((()) E [n]: I (q,, k()( > ʃ (q:: k2)) We say that a family of attention functions computes dynamic attention for IK and Q, if its scoring function computes dynamic scoring, possibly followed by monotonic normalization such as softmax.
That is, dynamic attention can select every key yo (i) using the query i, by making f (q. ks()) the maximal in (f (q; k5)) | E [n]]. Note that dynamic and static attention are exclusive properties, but they are not complementary. Further, every dynamic attention family has strict subsets of static attention families with respect to the same K and Q Dynamic attention is demonstrated in Figure lb
Attending by decaying Another way to think about attention is the ability to "focus" on the most relevant inputs, given query. Focusing is only possible by decaying other inputs, i.e., giving these decayed inputs lower scores than others. If one key is always given an equal or greater attention score than other keys (as in static attention), no query ignore this key or decay this key's 's score.
3.2 THE LIMITED EXPRESSIVITY OF GAT
Although the scoring function e can be defined in various ways, the original definition of Velickovic al. (2018) (Equation (2) has become the de facto practice: it has spread variety of domains and is now the standard implementation of "graph attention network" in all popular GNN libraries (Fey
and Lenssen 2019 WWag al. 2019b Dwivedi et al. 2020 Gordič 2020 Brockschmidt 2020).
The motivation of GAT is to compute a representation for every node as weighted average of its neighbors. Statedly, GAT is inspired by the attention mechanism Bahdanau al. (2014) and the self-attention mechanism of the Transformer (Vaswani et al. 2017). Nonetheless:
Theorem 1. A GAT layer computes only static attention, for any set of node representations K
Q (11 th.,... .... J. In particular, for 1, GAT layer does not compute dynamic attention.
Proof. Let G = (V,E) ) be graph modeled by a GAT layer with some a and W values (Equations and 33) and having node representations (hi,..,, h. The learned parameter can be written
4

---

Published as a conference paper at ICLR 2022
concatenation =[a1laa] E R2dd' such that d1, 02 E R", and Equation (2) can be re-written as: e (hi, h2) = LeakyRoLU (a) Wh; + a, Why)
(5)
Since V is finite, there exists node Jmar E V such that a Whimaz is maximal among all nodes j V (maz the jf required by Definition 3.1p. Due the monotonicity of LeakyReLU and softmax, for every query node E V. the node maaz also leads to the maximal value of its attention distribution {ate j E VJ. Thus, from Definition 3.1 directly, a computes only static attention. This also implies that does not compute dynamic attention, because in GAT, Definition 3.2 holds only for constant mappings yp that map all inputs to the same output.
The consequence of Theorem i that for any set of nodes V and a trained GAT layer, the attention function defines constant ranking (argsorl) of the nodes, unconditioned on the query nodes That is, we can denote *j 02 W h, and get that for any choice of h;, a is monotonic with respect to the per-node scores {sy neighborhood N₁. The only effect of h, is in the "sharpness" of the produced attention distribution. This is demonstrated in Figure Ia (bottom), where different curves denote different queries (h.). A discussion regarding the generalization to multi-head attention can be found in Appendix
V). This global ranking induces the local ranking of every
3.3 BUILDING DYNAMIC GRAPH ATTENTION NETWORKS
To create dynamic graph attention network, we modify the order of internal operations in GAT and introduce GATv2 simple fix of GAT that has a strictly more expressive attention mechanism.
GATv2 The main problem the standard GAT scoring function (Equation (2) that the learned layers W and a are applied consecutively, and thus can be collapsed into single linear layer. To fix this limitation, we simply apply the a layer after the nonlinearity (LeakyReLU), and the W layer after the concatenation, effectively applying an MLP to compute the score for each query-key pair:
GAT (Veličković et al. 2018):
e (hi, h2) RLeakyReLU (a T -Whh:]Whh.)
(6)
GATv2 (our fixed version):
e (h;, h2) =a LeakyReLU (W (/hh:]/h,))
(7)
The simple modification makes significant difference the expressiveness of the attention function: Theorem 2. A GATv2 layer computes dynamic attention for any set of node representations K Q = (h1,...,h,,) h,)
We prove Theorem in Appendix B The main idea is that we can define an appropriate function that GATv2 will be universal approximator (Cybenko 1989 Hornik 1991) of. In contrast, GAT (Equation (52) cannot approximate any such desired function (Theorem
Complexity GATv2 has the same cime-complexity as GAT's declared complexity: O (DVid + Eld"). However, by merging its linear layers, GAT can be computed faster than stated by Veličković et al. (2018). For detailed time- and parametric-complextty analysis, Appendix
EVALUATION
First, we demonstrate the weakness of GAT using a simple synthetic problem that GAT cannot even fit (cannot even achieve high training accuracy), but is easily solvable by GATv2 (Section 1.1). Second, we show that GATv2 is much more robust edge noise, because its dynamic attention mechanisms allow it to decay noisy (false) edges, while GAT's performance severely decreases as noise increases (Section 4.2) Finally, we compare GAT and GATv2 across 12 benchmarks overall. (Sections 4.3 to 4.6 and appendix
We find that GAT is inferior to GATv2 across all examined benchmarks.
Setup When previous results exist, we take hyperparameters that were tuned for GAT and use them in GATv2, without any additional tuning. Self-supervision (Kim and Oh, 2021 Rong et al. 2020a). graph regularization (Zhao and Akoglu, (2000) Rong et al.) (0206), and other tricks (Wang 2021 I Huang et al.) 2021) are orthogonal to the contribution of the GNN layer itself, and may further improve
We also add hias vector before applying the nonlincarity, we omit this in Equation for brevity.
5

---

Published as a conference paper at ICLR 2022
A.?
B.?
C.?
D.?
100
GATv2 test
90
GATsa test
GAT train
Accuracy
70
GAT1A test
60
50
A,4
B,3
C22
D.I
40
30
Figure 2: The DICTIONARY- LOOKUP problem of size 4=4: ev- cry node in the bottom row has an alphabetic attribute ((A, B, C....) and a numeric value (11, 2, D..)): every node in the upper row has only an attribute; the goal is to pre- diet the value for each node in the upper row, using its attribute.
20
19:20
(number of different keys in each graph)
Figure 3: The DiCTioNARyLoooK problem: GATv2 easily achieves 100% train and test accuracies even for 10100 and using only single head.
all GNNs. all experiments of GATv2, we constrain the learned matrix by setting W = W=
to rule out the increased number of parameters over GAT as the source of empirical difference (see Appendix [.2] Training details, statistics, and code are provided in Appendix D
Our main goal is to compare dynamic and static graph attention mechanisms. However, for reference, we also include non-altentive baselines such as GCN (Kipf and Welling, 2017). GIN (Xu et al. 2019) and GraphSAGE (Hamilton al. 2017). These non-attentive GNNs can be thought of as special case of attention, where every node gives all its neighbors the same attention score. Additional comparison a Transformer-stye scaled dot-product attention ("DPGAT"), which is strictly weaker than our proposed GATv2 (see proof in Appendix G. T,, is shown in Appendix G
4.1 SYNTHETIC BENCHMARK: DICTIONARYLOOKUP
The DICTIONARYLOOKUP problem is a contrived problem that we designed to test the ability of a GNN architecture to perform dynamic attention. Here, we demonstrate that GAT cannot learn this simple problem. Figure shows complete bipartite graph of 2k nodes. Each "key node" in the bottom row has an attribute (fA,B B,C. C....)) and a value 2, ...)). Each "query node" in the upper row has only attribute ((A, B, C..)). The goal is to predict the value of every query node (upper row), according to its attribute. Each graph in the dataset has a different mapping from attributes values. We created separate dataset for each k (1, 2, 3, ...,, for which trained different model, and measured per-node accuracy.
Although this is a contrived problem, it relevant to any subgraph with keys that share more than one query, and each query needs to attend to the keys differently. Such subgraphs are very common in variety of real-world domains. This problem tests the layer itself because it can be solved using single GNN layer, without suffering from multi-layer side-effects such as over- wer-smoothing (Li et al. 2018), over-squashing (Alon and Yahav] 202T), or vanishing gradients (Li et al.) 2019). Our code will be made publicly available, to serve as testbed for future graph attention mechanisms.
Results Figure 3 shows the following surprising results: GAT with a single head (GAT failed to fit the training set for any value of k. no matter for how many iterations it was trained, and after trying various training methods. Thus, expectedly fails to generalize (resulting low test accuracy). Using 8 heads, GATss, sh successfully fits the training set, but generalizes poorly to the test set. In contrast, GATv2 easily achieves 100% training and 100% test accuracies for any value of k. and even for 1=000 (not shown) and using single head, thanks to its ability to perform dynamic attention. These results clearly show the limitations of GAT, which are easily solved by GATv2. An additional comparison to GIN, which could not fit this dataset, is provided in Figure 5 in Appendix F.
Visualization Figure la (top) shows a heatmap of GAT's attention scores in this DICTIONARY- LOOKUP problem. As shown, all query nodes g0 q9 attend mostly the eighth key (k:8,, and have the same ranking of attention coefficients (Figure Ia (bottom)). In contrast, Figure [b]shows how GATv2 can select different key node for every query node, because computes dynamic attention.

---

Published as a conference paper at ICLR 2022
The role of multi-head aftention Veličković et al. (2018) found the role of multi-head attention to be stabilizing the learning process. Nevertheless, Figure shows that increasing the number of heads strictly increases training accuracy, and thus, the expressivity. Thus, GAT depends having multiple attention heads. In contrast, even single GATv2 head generalizes better than a multi-head GAT.
4.2 ROBUSTNESS TO NOISE
We examine the robustness of dynamic and static attention to noise. In particular, we focus on structural noise: given an input graph G = (V,,) 8) and noise ratio 0 S S 1, we randomly sample []] xp non-existing edges E¹ from Vx E.. We then train the GNN on the noisy graph (V=(VEEU8")
72
GATv2 (this work)
GATv2 (this work)
GAT
GAT
32
70
Accuracy
Accuracy
30
68
28
66
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
p noise ratio
p noise ratio
(a) ogbn-arxiv
(b) eghn-mag
Test accuracy compared to the noise ratio: GATv2 is more robust structural noise compared to GAT, Each point an average 10 runs, error bars show standard deviation.
Figure 4:
Results Figure 8 shows the accuracy on two node-prediction datasets from the Open Graph Bench- mark (OGB; Hu et al. 2020) as function of the noise ratio p. As p increases, all models show natural decline in test accuracy in both datasets. Yet, thanks to their ability to compute dynamic attention, GATv2 shows a milder degradation in accuracy compared to GAT, which shows a steeper descent. We hypothesize that the ability to perform dynamic attention helps the models distinguishing between given data edges (E) and noise edges (E"); in contrast, GAT cannot distinguish between edges, because it scores the source and target nodes separately. These results clearly demonstrate the robustness of dynamic attention over static attention in noisy settings, which are common reality.
4.3 PROGRAMS: VARMISUSE
Setup VARMISUSE (Allamanis al. 2018 an inductive node code-pointing problem that depends on 11 types of syntactic and semantic interactions between elements in computer programs.
We used the framework of [Brockschmidt (2020), who performed an extensive hyperparameter tuning by searching over configurations for every GNN type. We took their best GAT hyperparameters and used them to train GATv2, without further tuning.
Table Accuracy (5 t on VARMIS- USF. GATv2 is more accurate than all GNNs in both test sets, using GAT's hyperparameters. previously reported by Brockschmidt 2020))
Model
SeenProj
UnseenProj
Results As shown in T GATv2 is more accu- rate than GAT and other GNNs the SeenProj test sets. Furthermore, GATv2 achieves an even higher improvement in the UnseenProj test set. Overall, these results demonstrate the power of GATv2 in modeling complex relational problems, especially since it outperforms extensively tuned models, without any further tuning by
No- Attention
GCN GIN
87.2+1.5
81.4+2.
87.1
81.1+09
GAT
86.9+0.7
81.2+0.9
Attention
GATv2
88.0+1.1
82.8+1.7

---

Published as a conference paper at ICLR 2022
4.4 NODE- NODE-PREDICTION
We further compare GATv2, GAT, and other GNNs on four node-prediction datasets from OGB.
Table 2: Average accuracy (Table 2ah and ROC-AUC (Table 2b
node-prediction datasets (10
sud) In all datasets, GATv2 outperforms GAT, previously reported by Hu al. (2020).
(a)
(b)
Model
Attn. Hcads
ogbn-arxiv
ogbn-products
ogbn-mag
ogbn-proteins
GCN!
0
71.74=0.29
78.97.0.33
30.43
72.51
GraphSAGE
0
71.49-0.27
78.70+0.36
31.53++0.15
77.68-0.20
1
71.59
1..04
32.20
70.77
GAT
8
7..54
77.23
31.75+1.60
78.63
1
71.78=0.18
80,63
32.61:0.44
77.23+3.32
GATv2 (this work)
8
71.87=0.25
78.464245
32.52+0.39
79.52
Results Results are shown in Table 2 In all settings and all datasets, GATv2 more accurate than GAT and the non-attentive GNNs. Interestingly, in the datasets of Table 2a even single head of GATv2 outperforms GAT with 8 heads. In Table 2b pregbiiprrtins)..... increasing the number of heads results in major improvement for GAT (from 70.77 to 78.63), while GATv2 already gets most of benefit using single attention head. These results demonstrate the superiority of GATv2 over GAT in node prediction (and even with single head), thanks GATv2's dynamic attention.
4.5
PRADICPRE QM9
Setup In the QM9 dataset (Ramakrishnan et al. 2014 Gilmer et al. 2017). each graph a molecule
and the goal regress each graph 13 real-valued quantum chemical properties. We used the implementation of BBBockschmidd (2020) who performed an extensive hyperparameter search over 500 configurations; we took their best-found configuration of GAT implement GATv2.
Table Average error rates (lower is better), runs for each property, on the QM9 dataset. The best result among GAT and GATv2 is marked in bold; the globally best result among all GNNs is marked in bold and underline. was previously tuned and reported by Brockschmidt (2020).
Predicted Property
Rel.
Model
2
4
8
13
GAT
GCN1
3.21
4.22
1.45
1.62
2.42
16.38
17.40 7.82
8.24
9.05
7.00
3.93
1.02
-1.5%
GINt
2.64
4.67
1.42
2.27
15.63
12.93
5.88
18.71
5.62
5.38
3.53
1.0S
-2.3%
GATT
2.68
4.65
1.48
1.53
2.31
52,39
14.87
7.61
6.86
7.64
6.54
4.11
1.48
+0%
GATv2
2.65
4.28
1.41
1.47
2.29
16.37
14.03
6.07
6,28
6.60
5.97
3.57
1.59
-11.5%
Results Table 3 shows the main results: GATv2 achieves lower (better) average error than GAT, by 11 11.5% relatively. GAT achieves the overall highest average error. In some properties, the non-attentive GNNs, GCN and GIN, perform best. We hypothesize that attention is not needed in modeling these properties. Generally, GATv2 achieves the lowest overall average relative error (rightmost column).
4.6 LINK-PREDICTION
We compare GATv2, GAT, and other GNNs in link fink-rredccton datasets from OGB.
Results Table 8 shows that in all datasets, GATv2 achieves higher MRR than GAT, which achieves the lowest MRR. However, the non-attentive GraphSAGE performs better than all attentive GNNs. We hypothesize that attention might not be needed in these datasets. Another possibility is that dynamic attention is especially useful in graphs that have high node degrees: in ogbn-products and ogbn-proteins (Table 2) the average node degrees are 50.5 and 597, respectively (see Table in
8

---

Published as a conference paper at ICLR 2022
Appendix E) ogbl-collab and ogbl-citation2 (Table however, have much lower average node degrees of 8.2 and 20.7. We hypothesize that a dynamic attention mechanism is especially useful to select the most relevant neighbors when the total number of neighbors is high. We leave the study of the effect of the datasets's s average node degrees on the optimal GNN architecture for future work.
4.7 DISCUSSION
In all examined benchmarks, we found that GATv2 is more accurate than GAT. Further, we found that GATv2 is significantly more robust to noise than GAT. In the synthetic DICTIONARYLOOKUD benchmark (Section 4.1p. GAT fails to express the data, and thus achieves even poor training accuracy.
In few of the benchmarks (Table g and some of the properties in Table 3 a non-attentive model such GCN GIN achieved higher accuracy than all GNNs that do use attention. We hypothesize that attention is not needed in these datasets.
Which graph attention mechanism should I use? is usually impossible to determine in advance which architecture would perform best. A theoretically weaker model may perform better in practice, because stronger model might overfit the training data if the task "too simple" and does not require such expressiveness. Intuitively, we believe that the more complex the interactions between nodes are the more benefit GNN can take from theoretically stronger graph attention mechanisms such as GATv2. The main question is whether the problem has global ranking of "influential" nodes (GAT sufficient), or do different nodes have different rankings of neighbors (use GATv2).
Veličković, the author of GAT, has confirmed on Twittes" that GAT was designed to work in the "easy-to-overfit" datasets of the time (2017), such as Cora, Citeseer and Pubmed (Sen al. 2008). where the data might had an underlying static ranking of "globally important" nodes. Veličković agreed that newer and more challenging benchmarks may demand stronger attention mechanisms such GATv2. that depends the traditional assumptions and show that many modern graph benchmarks and datasets contain more complex interactions, and thus require dynamic attention.
the representation of the query node well. In this paper, we revisit
CONCLUSION
In this paper, identify that the popular and widespread Graph Attention Network does not compute dynamic attention. Instead, the attention mechanism in the standard definition and implementations of GAT is only static: for any query, its neighbor-scoring is monotonic with respect to per-node scores. Further, the ranking (the argsort) of attention coefficients is identical for all nodes in the graph, and is unconditioned on the query node. As result, GAT cannot even express simple alignment problems. To address this limitation, we introduce simple fix and propose GATv2: by modifying the order of operations in GAT, GATv2 achieves a universal approximator attention function and thus strictly more powerful than GAT.
We demonstrate the empirical advantage of GATv2 over GAT a synthetic problem that requires dy- namic selection of nodes, and in 12 benchmarks from OGB and other public datasets. Our experiments show that GATv2 outperforms GAT in all benchmarks while having the same parametric cost.
We encourage the community to use GATv2 instead or in addition to GAT whenever comparing new GNN architectures to the common strong baselines. In complex tasks and domains and challenging datasets, model that uses GAT as an internal component can replace it with GATv2 to benefit from a strictly more powerful model. To this end, we make our code publicly available at (httpss //github... com/ /t techeeehhseeeeee srl 1 hhww
are gats and GATv2 2 is available part of the PyTorch Geometric library the Deep Graph Library and the TensorFlow GNN library
https://twitter http:///eee..oeeeeeeee//essssaaa
An annotated implementation of GATv2 available al http://aaaaaaatttaaa/.mm...a.aaa http:aamm.....agggaaps/g//a////a from torch_geometric.
wwn. www.cooovvcc... wwopv.attv__com import GATv2Conv
from dgl.nn mgll.nn.pyee pytorchh import GA1v2Conv
from tenserf1 lennsrfloo.ggnngrrg...ee.... 1alaaas.ayyyss.cooo aaers.gat__s... v2 import GATv2Convo1utio

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We thank Gail Weiss for the helpful discussions, thorough feedback, and inspirational paper (Weiss) ct al, 2018). We also thank Petar Veličković for the useful initial discussion about the complexity and implementation of GAT, Lucio Dery, and the Graph Representation Learning Reading Group at Mila for their useful comments and questions.
A RELATED WORK
Attention in GNNs Modeling pairwise interactions between elements in graph-structured data goes back to interaction networks (Battaglia et al. 2016 Hoshen 2017) and relational networks (Santoro jet al., 2017). The GAT formulation Veličković al. (2018) rose as the most popular framework for attentional GNNs, thanks to its simplicity, generality, and applicability beyond reinforcement learning (Denil et al. 2017 Duan et al., 2017). Nevertheless, in this work, we show that the popular and widespread definition of GAT is severely constrained to static attention only.
Other graph attention mechanisms Many works employed GNNs with attention mechanisms
other than the standard GAT's Zhang al. (2018) Thekumparampil et al. 2018; Gao and Ji 2019
Lukovnikov and Fischer 2021 Shi et al. 2020 Dwivedi and Bresson 2020 Busbridge et al. 2019
Rong et al.) [020aa] Veličković et al. 2020), and Lee et al. (2018) conducted an extensive survey of attention types in GNNs. However, none of these works identified the monotonicity of GAT's attention mechanism, the theoretical differences between attention types, empirically compared their performance. Kim and Ohl (2021) compared two graph attention mechanisms empirically, but in a specific self-supervised scenario, without observing the theoretical difference in their expressiveness.
The static attention of GAT Qiu et al. (2018) recognized the order-preserving property of GAT, but did not identify the severe theoretical constraint that this property implies: the inability to perform dynamic attention (Theorem]) D Furthermore, they presented GAT's monotonicity as a desired trait (!) To the best of our knowledge, our work is the first work to recognize the inability of GAT to perform dynamic attention and its practical harmful consequences.
B PROOF FOR THEOREM
For brevity, we repeat our definition of dynamic attention (Definition 3.2
Definition 3.2 (Dynamic attention). A (possibly infinite) family of scoring functions F C (Rd Fd R) computes dynamic scoring for a given set of key vectors K K= (k, kn Rd and query vectors Q = {q),,... qm C Rdd, if for any mapping yp: [m]] + [ni] there exists f E such
that for any query E [m] and any key }zw(1) E [n]: f (q,, k(p()) > fq: k,) We say that family of attention functions computes dynamic attention for IK and Q, if its scoring function computes dynamic scoring, possibly followed by monotonic normalization such as softmax.
Theorem 2. A GATv2 layer computes dynamic attention for any set of node representations K Q = (hi,...,h,.) hn).
Proof. Let G (V, be graph modeled by GATv2 layer, having node representations (hi,.., }n y and let yp [n] + [n] be any node mapping [n]] + [n]. We define : R2dd - TR. as follows:
Di x /hill/
g (z)
(8)
0
otherwise
Next, we define a continues function g 2d + R that equals to in only specific n inputs:
a( [h,))) = 90 he,)) Vi.j E [m]]
(9)
10

---

Published as a conference paper at ICLR 2022
For all other inputs R2d, 9(x) realizes to any values that maintain the continuity of (this is possible because we fixed the values of for only a finite set of points).
Thus, for every node E V and (z((1) V:
1= g ( (1 (pp))) > 9 (h,,l/b5)) =
(10)
If we concatenate the two input vectors, and define the scoring function e of GATv2 (Equation (7) as function of the concatenated vector [h, [ from the universal approximation theorem (Horiik
et al. 1989 Cybenko 1989 Funahashi 1989
Hormik 1991). can approximate ğ for any compact
subset of 2
Thus, for any sufficiently small c (any 0 < < 1/2) there exist parameters W and a such that for every node i and every 1
ew (h, p()) 1 0 ew,a (hi, hz)
(11)
and due the increasing monotonicity of softmax:
(1pp(()) >> 04.3
(12)
The choice of nonlinearity In general, these results hold if GATv2 had used any common non- polynomial activation function (such as ReLU, sigmoid, or the hyperbolic tangent function). The LeakyRel.U activation function of GATv2 does not change its universal approximation ability (Leshno
al. 1993] Pinkus T999. Park et 2021). D. and it was chosen only for consistency with the original
definition of GAT.
C GENERALIZATION TO MULTI-HEAD ATTENTION
Veličković et al. 2018) found beneficial to employ separate attention heads and concatenate their outputs, similarly to Transformers. In this case, Theorem Daarremmhhhr Tholds for each head separately: every head (H] has a (possibly different) node that maximizes {8. | V). and the output the concatenation of H static attention heads.
D TRAINING DETAILS
In this section we elaborate on the training details of all of our experiments. All models use residual connections as in Veličković et al. (2018). All used code and data are publicly available under the MIT license.
D.1 NODE- AND
We used the provided splits of OGB HHu et al. 2020) and the Adam optimizer. We tuned the following hyperparameters: number of layers (2, 3, 6J. hidden size E {64, 128, 256). learning rate E {0.0005, 0.001, 0.005, 0.01) and sampling method full batch, GraphSAINT (Zeng et al. 2019) and NeighborSampling (Hamilton et al. 2017). We tuned hyperparameters according validation score and early stopping. The final hyperparameters are detailed in Table
The function δ a function that we define for the case proof, because the universal approximation theorem defined for continuous functions, and we only need the scoring function of GATv2 to approximate the mapping in finite set of points. So, need the attention function to approximate (from Equation 8) in specific points. But, since g not continuous, we define ğ and use the universal approximation theorem for ğ. Since approximates g. also approximates g in our specific points, as special case. only require that ğ will be identical to in specific n' points [/,] ] i, [n]]. For the rest of the input space, we don't 't have requirement on the value of g. except for maintaining the continuity of g. There exist infinitely many such possible for every given set of keys, queries and mapping sp, but the concrete functions are not needed for the proof.
11

---

Published as a conference paper at ICLR 2022
Dataset
# layers
Hidden size
Learning rale
Sampling method
oghn-arxiv
3
256
0.01
GraphSAINT
ogbn-products
128
0.001
NeighborSanpling
ogbn-mag
2
256
0.01
NeighborSampling
ogbn-proteins
6
64
0.01
NeighborSampling
ogbl-collab
3
64
0,001
Full Batch
ogbl-citation2
3
256
0.0005
NeighborSampling
Table 4: Training details of node- and likkprediction datasets.
D.2 ROBUSTNESS TO NOISE
In these experiments, we used the same best-found hyperparameters in node-prediction, with attention heads in ogbn-arxiv and I head in ogbn-mag. Each point is an average of 10 runs.
D.3 SYNTHETIC BENCHMARK: DICTIONARYLOOKUP
In all experiments, we used learning rate decay of 0.5, hidden size of d 128, a batch size of 1024, and the Adam optimizer.
We created separate dataset for every graph size (k), and we split each such dataset to train and test with a ratio of 80:20. Since this contrived problem, we did not use validation set, and the reported test results can be thought of validation results. Every model was trained on a fixed value of k. Every key node (bottom row in Figure 2 was encoded as a sum of learned attribute embedding and value embedding, followed by ReLU.
We experimented with layer normalization, batch normalization, dropout, various activation functions and various learning rates. None of these changed the general trend, the experiments in Figure were conducted without any normalization, without dropout and a learning rate 0.001.
D.4 PROGRAMS: VARMISUSE
We used the code, splits, and the same best-found configurations as Brockschmidj (2020), who performed an extensive hyperparameter tuning by searching over 30 configurations for each GNN type. We trained each model five times.
We took the best-found hyperparameters of Brockschmidi (2020) for GAT and used them train GATv2, without any further tuning.
D.S PRAPH-PREDICTION QM9
We used the code and splits Brockschiidt (2020) who performed extensive hyperparameter search over 500 configurations. We took the best-found hyperparameters of Brocksschmidd (2020) for GAT and used them to train GATv2. The only minor change from GAT is placing residual connection after every layer, rather than after every other layer, which within the experimented hyperparameter search that was reported by Brockschmidt (2020).
D.6 COMPUTE AND RESOURCES
Our experiments consumed approximately 100 days GPU in total. We used cloud GPUs of type V100, and we used RTX 3080 and 3090 in local GPU machines.
E DATA STATISTICS
E.1 NODE- AND LINK- PRE-IPREENN DATASETS
Statistics of the OGB datasets used for node- and link-prediction are shown in Table
12

---

Published as a conference paper at ICLR 2022
Dataset
# nodes
# edges
Avg. node degree
Diameter
ogbn-arxiy
169,343
1,166,243
13.7
ogbn-mag
1,939,743
21,111,007
21.7
ogbn-products
2,449,029
61,859,140
50.5
27
ogbn-proteins
132,534
39,561,252
597.0
ogbl-collab
235,868
1,285,465
8.2
ogbl-citation2
2,927,963
30,561,187
20.7
21
Table 5: Statistics of the OGB datasets
(Hu et al.
2020).
E.2 QM9
Statistics of the QM9 dataset, used in Brockschmidi (2020)
are shown in Table
Training
Validation
Test
examples
110,462
10,000
10,000
nodes average
18.03
18.06
18.09
# edges average
18.65
18.67
18.72
Diameter- average
6.35
6.35
6.35
Table 6: Statistics of the QM9 chemical dataset (Ramakrishnan et al. (202)).
2014 as used by |Brockschmidt
E.3 VARMISUSE
Statistics of the VARMISUSE dataset, used in Allamanis et al. (2018) are shown Table
and Brockschmidi (2020).
Training
Validation
UnseenProject Test
SeenProject Test
# graphs
254360
42654
117036
59974
# nodes average
2377
1742
1959
3986
# edges average
7298
7851
5882
12925
Diameter average
7.88
7.88
7.78
7.82
Table 7: Statistics of the VARMISUSE dataset (Allamanis et al. 2018) as used by Brockschmidt (2020).
F ADDITIONAL RESULTS
F.1 DICTIONARYLOOKUP
Figure shows additional comparison between GATv2 and GIN (Xu al. 2019) in the DICTIO- MARYLOOKUD problem. GATv2 easily achieves 100% train and test accuracy even for k=100 and using only a single head. GIN, although considered as more expressive than other GNNs, cannot perfectly fit the training data (with model size of d 128) starting from k=20.
F.2 LINK- PIND-PREDNTIION
Results for link- finkppredcction are showen in Table
13

---

Published as a conference paper at ICLR 2022
100
Accuracy
60
GATv2 train
50
GATv2 test
GIN train
20
GIN test
10
10
20
30
40
50
60
70
k: (number of different keys in each graph)
Figure 5: Train and test accuracy across graph sizes in the DICTIONARYLOOKUP problem. GATv2 easily achieves 100% train and test accuracy even for k=100 and using only single head. GIN (Xu et al. 2019), although considered as more expressive than other GNNs, cannot perfectly fit the training data (with model size of d 128) starting from k=20.
Table Average Hits 50 (Table Sab and mean reciprocal rank (MRR) (Table 8b fink-prediction benchmarks from OGB (10 Esdd) The best result among GAT and GATv2 is marked in bold; the best result among GNNs is marked in bold and underline. was reported by Hu 2020
(b)
ogbl-collab
ogbl-citation2
Model
Attn. Heads
w/o val edges
w/ val edges
No-
GCNt
44.75=1.07
47.14-1445
80.04:0.25
Attention
GraphSAGE
48.10=081
54.63-1.12
80.44
GAT 1b
39.32+3.26
48. 40.40.8.80
79.84
GAT
GATsh sh
42.37=2.99
46.63-2.80
7..95
GATv2
42.00
48.02-2.17
80.33+0.13
GATv2
GATv28h.
42.85
49.70_3.08
80.14
F.3
QM9
Standard deviation for the QM9 results of Section 4.5 are presented in Table 9
F.4 PUBMED CITATION NETWORK
We tuned the following parameters for both GAT and GATv2: number of layers E {0, 1,2). hidden size E {8, 16, 32}. number of heads E {1, 4, 8), dropout E (0.4, 0.6, 0.8). bias E {True, False), share weights {T'rue, False). use residual (Trrue False). Table shows the test accuracy (100 runs-t using the best hyperparameters found for each model.
is important to note that PubMed has only 60 training nodes, which hinders expressive models such as GATv2 from exploiting their approximation and generalization ad advantages. Still, GATv2 more accurate than GAT even in this small dataset. In Table 15] we show that this difference statistically significant (p-value < 0.0001).
G ADDITIONAL COMPARISON WITH TRANSFORMER-STYLA ATTENTION (DPGAT)
The main goal of our paper is to highlight a severe thcoretical limitation the highly popular GAT architecture, and propose minimal fix.
14

---

Published as a conference paper at ICLR 2022
Predicted Property
Model
1
2
7
GCNÍ
3.21
4.22
1.45
1.6220004
2.42
16.38
17 3..4013.56
GIN
2.64+0.11
4.67=0.32
1.42+0.01
1,50+0.09
2.27+0009
15.63+1.40
1.81
GAT 1h
3.08
1.82
1.79
3.9621.51
1.08
25.4
106.5
GAT
2.68
4.65
1.48
1.53
2.31
52.39
14.87
1
3.04
6.38=0.62
1.6800.44
2.18=0.61
2.82++0.25
20.56=0070
437.99
GATv2sh
2.65
4.28=0027
1.41 +0.04
1.07
2.29
16.37=009
14.03+1.39
Predicted Property
Rel.
Model
8
10
GATsa
GCNI
7.82+0.80
1.24
1.25
7.00
3.9320.48
1.02=0.05
-1.5%
GINT
1.08
18.71+23.36
5.62+0.11
5.78
3.53
1.05=0.11
-2.3%
GAT
28. 18.10=16.45
20.40+13.40
15.80-5.8
10.80+2.18
5.37 +0.66
0.14
+134.1%
GAT
2.64
6.8620.53
7.64
0.34
4.11
1.48
+0%
GATv2
10.19
22.56+17.46
15,04-4.58
22.94+17.34
5.23+0.36
2.46-0.65
+91.6%
GATv2sh
6.07:0077
6.28
+0.83
6.60
5.97=0.94
3.57
1.59
11.5%
Table 9: Average error rates (lower is better), 5 runs + standard deviation for each property, on the QM9 dataset. The best result among GAT and GATv2 is marked in bold; the globally best result among all GNNs is marked bold and underline. was previously tuned and reported by Brockschmidt (2020).
Table 10: Accuracy (100 runs- on Pubmed. GATv2 is more accurate than GAT.
Model
Accuracy
GAT 18.59
GATv2
78.510.38
We perform additional empirical comparison DPGAT, which follows Luong et al. (2015) and the dot-produee attention of the Transformer (Vaswani et al.) 2017). We define DPGAT as:
DPGAT VVaswani al. 2017):
(h; h,)
(h. Q) (h, K)
/Vde
(13)
Variants of DPGAT were used in prior work (Gao and Ji 2019 Dwivedi and Bresson 2020 ct al. 2020a Veličković et al. 2020 Kim and Oh (021). and we consider it here for the conceptual
Rong
and empirical comparison with GAT.
Despite its popularity, DPGAT is strictly weaker than GATv2. DPGAT provably performs dynamic attention for any set of node representations only if they are linearly independent (see Theorem and its proof in Appendix G.I). Otherwise, there are examples of node representations that are linearly dependent and mappings sp, for which dynamic attention does not hold (Appendix G.2). This constraint is not harmful when violated in practice, because every node has only a small set of neighbors, rather than all possible nodes in the graph; further, some nodes possibly never need to be "selected" in practice.
G.1 PROOF THAT DPGAT PERFORMS DYNAMIC ATTENTION FOR LINEARLY INDEPENDENT NODE REPRESENTATIONS
Theorem DPGAT layer computes dynamic attention for any set of node representations K Q (hi,... hn) that are linearly independent.
Proof. Let 9 = (V,E) be a graph modeled by a DPGAT layer, having linearly independent node representations (h1, hn). Let yp: [n] [ri] be any node mapping [n] [n).
15

---

Published as a conference paper at ICLR 2022
We denote the 1t row of matrix M M,.
We define a matrix P as:
Pis = {1
-
(14)
otherwise
Let X E IR x Rd be the matrix holding the graph's 's node representations as its rows:
h1
h2
X
(15)
hn
Since the rows of X are linearly independent, necessarily holds that 2 n.
Next, we find weight matrices Q E R Rd and K E IR x R& such that:
(XQ) (XK)* = P
(16)
To satisfy Equation (6). we choose Q and K such that XQ U and XK P where U is
an orthonormal matrix (U = U U = I).
We can obtain U using the singular value decomposition (SVD) of X:
X -VV
(17)
Since Σ E R x R" and X has full rank, Σ is invertible, and thus:
XVE =U
(18)
Now, we define as follows:
Q = VE-!
(19)
Note that XQ U, as desired.
To find K that satisfies XK = PTU, we use Equation 17 and require:
K K K
(20)
and thus:
K = V= U
(21)
We define:
2 =hi h2) (hi, hn) dp Where is the attention score function of DPGAT (Equation (3) Now, for query and a key j. and the corresponding representations hi, hz:
(22)
2 (he h2)) (h Q) (h. K)
(23)
= (X,Q) (X,K)
(24)
Since X2Q (XQ); and K (XK), we get
(hs, (24) = (XQ); (IXK),) Pa.
(25)
Therefore:
2 hhh [1 j=
(26)
otherwise
And thus:
[1/
j j= f()
e eh,,, h2)
(27)
10
otherwise
16

---

Published as a conference paper at ICLR 2022
To conclude, for every selected query i and any key }xp(1)²
(hi, hep(s) > e (h,, h,)
(28)
and due to the increasing monotonicity of softmax:
(1,)(() > Oij
(29)
Hence, a DPGAT layer computes dynamic attention.
In the case that d > n, we apply SVD to the full-rank matrix XXT E R and follow the same steps to construct Q and K.
In the case that Q Rd Rd and K E Rd x Rd and de d, we can use the same Q and K (Equations 19) and 21 padded with zeros. We define the Q' E Rd Rddee and K' E Rd x Rddey as follows:
Qii 0
isc otherwise
Q
(30)
Kij
jsd d otherwise
k
(31)
10
G.2 DPGAT IS STRICTLY WEAKER THAN GATv2
There are examples of node representations that are linearly dependent and mappings ç, for which dynamic attention does not hold. First, we show a simple 2-dimensional example, and then we show the general case of such examples.
h2 = à: + 2ÿ
h1 2 + ÿ
hn ②
Figure 6: An example for node representations that are linearly dependent, for which DPGAT cannot compute dynamic attention, because query vector q E IR22 can "select" h
Consider the following linearly dependent set of vectors K = Q (Figure 6
ho h a
(32)
(33)
h2 = â + 2ÿ
(34)
where è and ý are the cartesian unit vectors. We define 3 E {0, 1, to express (ho, h1, h2) using the same expression:
h मे + Aÿ
(35)
Let q Q be any query vector. For brevity, define the unscaled dot-product attention score
(q, h2)) hz) dx
(36)
Where is the attention score function of DPGAT (Equation 13 The (unscaled) attention score
between q and (hv, h1, h2 is:
8 (g, h2) = (q Q) (h] K) T
(37)
(q Q) ((# + 3g) K)
(38)
(qTQ) Q)) TTT K + BD K)
(39)
Q) (+ (qTQ)
K) T
+ 3 (g Q) (1 K)
(40)
17

---

Published as a conference paper at ICLR 2022
The first term (qT (+T TeTHe ()K is unconditioned on B, and thus shared for every hg. Let us focus on the second term (q Q) K)
If (q (QQ) (i K) > 0, then:
e eqq, h2) (q. h1)
(41)
Otherwise, if (q (y K) < 0:
(g. ho) 2 (q. h1)
(42)
Thus, for any query q, the key h1 can never get the highest score, and thus cannot "selected". That is, the key hı cannot satisfy that (q, h1) is strictly greater than any other key.
In the general case, let ho, h1 E Rd be some non-zero vectors and some scalar such that 0 <<> X 1.
Consider the following linearly dependent set of vectors:
K Q [Bh + 3)
3) ho B 10, 13)
(43)
For any query q E Q and 3 E {0, X, }} we define:
(q. e (g. (Sh1 (1 3) ho)) dd
(44)
Where is the attention score function of DPGAT (Equation Therefore:
13
$ (q. (q ((hh (1- () ho) K)
(45)
(q QQ) (Bh K + (1 3) hgg K)
(46)
(q (Bh, K + [ K Bhg K)
(47)
= =(q (qT (3 (hj]--j -hh K) + ho K) T
(48)
= B (q] (qT)) (h] K- k)) + (q T Q) (ho K)
---ha 1o
(hJK)
(49)
(q (q))) (hT K ho K) T
> 0:
(q. h1) > e hx,
(50)
Otherwise, if (q) (h K ho k) <
(q. ho) > e (q, hs)
(51)
Thus, for any query q. the key h2 cannot be selected. That is, the key h2 cannot satisfy that e (q. hx) strictly greater than any other key. Therefore, there are mappings yo, for which dynamic attention does not hold.
While we prove that GATv2 computes dynamic attention (Appendix B for any set of node represen- tations K Q, there are sets of node representations and mappings yp for which dynamic attention does not hold DPGAT. Thus, DPGAT is strictly weaker than GATv2.
G.3 EMPIRICAL EVALUATION
Here repeat the experiments of Section 4 with DPGAT. We remind that DPGAT is strictly weaker than our proposed GATv2 (see proof in Appendix G.T).
H STATISTICAL SIGNIFICANCE
Here we report the statistical significance of the strongest GATv2 and GAT models the experiments reported in Section
18

---

Published as a conference paper at ICLR 2022
72
DPGAT GATv2 GAT
DPGAT GATv2 GAT
32
70
Accuracy
Accuracy
30
68
28
66
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
p - noise ratio
p - noise ratio
(a) ogbn-arxiv
(b) ogbn-mag
Figure 7: Test accuracy compared to the noise ratio: GATv2 and DPGAT are more robust to structural noise compared GAT. Each point is average of 10 runs, error bars show standard deviation.
Table 11: Accuracy (5 runs=stdev) on VARMISUSE. GATv2 is more accurate than all GNNs both test sets, using GAT's hyperparameters. previously reported by |Brockschmidt (2020).
Model
SeenProj
UnseenProj
No-
GCN
87.2=1.5
81.4-23
Attention
GIN!
87.1=0.1
81.1=09
GAT 86.9=0.7
81.2=09
Attention
DPGAT
88.0=0.8
81.5=122
GATv2
88.0=1.1
82.8=1.7
Table 12: Average accuracy (Table 12a) and ROC-AUC (Table 12b in mode-prediction datasets (10
runsistd). In all datasets, GATv2 outperforms GAT. previously reported by Hu et al (2000)
(b)
Model
Attn. Heads
ogbn-arxiv
ogbn-products
ogbn-mag
ogbn-proteins
GCN!
0
71.74=0.29
78.97
30.43
72.51
GraphSAGE
0
71.49_0.27
78.7040.36
31.53
77.68
71.59
79. 19.04
32.20+
70.77+5.79
GAT
8
71.54=0.30
77.23
3..75
78.63+1.62
1
71.5220.17
76.4910.78
32.77.0.80
63.47-2.79
DPGAT
8
71.4
73.53
27.74.9.97
72.88
1
71.78=0.18
80.63
32.61
77.23
GATv2 (this work)
8
0.25
78.4642.45
32.52+0.39
79.52
19

---

Published as a conference paper at ICLR 2022
Table 13: Average error rates (lower is better), runs standard deviation for each property, on the QM9 dataset. The best result among GAT, GATv2 and DPGAT is marked in bold: the globally best result among all GNNs is marked bold and underline. was previously tuned and reported by Brockschmid (2020).
Predicted Property
Model
2
3
4
5
6
GCNI
3.21
4.22=0045
1.45
1.62+0.04
2.42=0.14
16.38-0.49
17.40+3.56
GIN
2.6440.11
4.67=0552
1,42+0001
1.50
2.27
15.63
1..9
GAT 3.08
7.82=1142
1.79
3.96
3.58
35.43
116.5
GATsn
2.68
4.65=00.4
1.48+00.3
1.53
2.31
52.39:44.558
14.87+2288
DRGAT
2.63
1.37=0.13
1.44
1.40
2.10
32.59
11.66=1.00
DPGAT
3.20
8.35
1.71
2.17
2.88
25.21
65.79439.84
GATv214
3.0440.06
6.38=0062
1.68
2.18+0.61
2.82
20.56
77.13-37.95
GATv28h
2.65
4.28
1..4
1.47
2.29
16.37=097
14.03
Predicted Property
Rel. to
Model
9
10
11
12
13
GAT
GCN1
7.82
8.24
9.05
7.00
3.93
1.02.0.05
-1.5%
GINT
5.88 1.01
18.71
5.62.0.81
5.38
3.53
1.05
-2.3%
GAT
18.10+16.45
20.80+13:40
15,80+5.87
10.80+2.18
5,37+0.26
3.1140.14
+134.1%
GATs
7.614
6.86=0.53
7.64
6.54
4.11=0,27
1.48+087
+0%
DPGAT 14
1279
13.32.2.39
1..42.1.95
13.83
6.37
3.28
+77.9%
DPGAT
6.95+0.32
7.09-0.59
7.30+0.66
6.52+0.61
3.76++0,2
1.18+0.33
-9.7%
GATv2
27.56+17.46 0..6
15,04+4.58
22.94+17.34
5,23+0036
2.46+0.65
+91.6%
GATv2sh
6.0710.77
6.28 0.83
6.60
5.9710.94
2037
1.59
-11.5%
72
GATv2 (p-value)
GATv2 (p-value)
GAT
32
P.ralnesd.00m)
GAT
0.0m6
40,0001
70
Accuracy
Accuracy
(000))
velluedd 50,000
000000
4000001
C000000
0000
30
40.00))
50.000
68
28
66
0.1
0.2
0.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
noise ratio
noise ratio
(a) ogbn-arxiv
(b) ogbn-mag
Figure 8: Test accuracy and statistical significance compared to the noise ratio: GATv2 more robust to structural noise compared to GAT. Each point is average of 10 runs, error bars show standard deviation.
Table 14: Accuracy (5 runs=istdev) on VARMISUSE. GATv2 is more accurate than all GNNs in both test sets, using GAT's hyperparameters. previously reported by Brockschmidt (2020).
Model
SeenProj
UnseenProj
GATi
86.9107
81.24n.9
GATv2
88.0
82.8
p-value
0.048
0.049
20

---

Published as a conference paper at ICLR 2022
Table 15: Accuracy (100 runs--ssdev) on Pubmed. GATv2 is more accurate than GAT.
Model
Accuracy
GAT
78.1
GATv2
78.5+0.38
p-value
0.0001
Table 16: Average accuracy (Table 16a) and ROC-AUC (Table 16b in node-prediction datasets (30
std). We report on the best GAT GATv2 from Table 2
(b)
Model
ogbn-arxiv
ogbn-products
ogbn-mag
ogbn-proteins
GAT
71.65
1.504=1.54
32.36=1.10
78.29 +1.59
GATv2
71.93+0.35
80.63
33.01=0441
78.96=1.19
p-value
0.0022
<0.0001
0.0018
0.0349
Table 17: Average @ots@ (Table 17ah and mean reciprocal rank (MRR) (Table 17b in link-
prediction benchmarks from OGB (30 std). We report the best GAT GATv2 from Table
(a)
(b)
ogbl-collab w/ val edges
ogbl-citation2
Model
w/o val edges
GAT
42.24 43.82:224
46.02.4.09
79.91
GATv2
49.06
80.20.0.62
p-value
0.0043
0.0005
0.0075
Table 18: Average error rates (lower is better), 20 runs + standard deviation for each property, on the QM9 dataset. We report on GAT and GATv2 with attention heads.
Predicted Property
Model
2
GAT
2.74.0.08
4.73
1.47=00.6
1.53
2.44-10.60
55.21
25.36=3142
GATv2
2.67.0.08
4.28
1.03
1..0
2.21
16.64.1.17
13.61
p-vauue
0.0043
<0.0001
0.0138
0.1691
0.0487
0.0001
0.0516
Predicted Property
Model
9
10
11
GAT
7.36.0.87
6.79.20.86
7.36+0.93
6.69
4.10
1.51
GATv2
6.13.0.59
6.33
6.37
5.95
3.66
1.09
p-value
<0.0001
0.0458
0.0006
0.0017
<0.0001
0.0621
21

---

Published as a conference paper at ICLR 2022
1
COMPLEXITY ANALYSIS
We repeat the definitions of GAT, GATv2 and DPGAT:
GAT (Veličković al. 2018):
e (h; h2) -LeakyReL.U (aT [Wh, (Wh,/Whi)) Wh,])
(52)
GATv2 (our fixed version):
(h,, hT) =a LeakyReLU (W [h //,l)
(53)
DPGAT Vaswani et al. 2017)
(h4, hy) = (h, (h) K) )) /Vd'
(h)jk)))
(54)
I.1 TIME COMPLEXITY
GAT As noted by Veličković et al. (2018), the time complexity of single GAT head may be expressed as (Vldd' + Eld"). Because of GAT's static attention, this computation can be further
optimized, by merging the linear layer a₁ with W, merging 02 with W, and only then compute a (11,2) Wh; for every E
GATv2 require the same computational cost as GAT's declared complexity: O ([Vidd' + 18]d"): we denote W [Wi W2]. where W1 E TRd and W xd contain the left half and right half of the columns of W, respectively. We can first compute W,h, and W2hj for every i,j E V. This takes O ([Vld''.
Then, for every edge ().).. we compute ReLU (W [h:]lh;] using the precomputed Wih; and W2hj, since W [h:][hy] = Wi h; W2hj- This takes O ((E|d").
Finally, computing the results of the linear layer a takes additional O ((E)d') time, and overall O ([V]dd' + [Eld").
DPGAT also takes the same time. We can first compute h Q and h K for every i,j E V. This takes O ([Vldd". Computing the dot-product (h, Q) (h. K) for every edge (j. i) takes additional O ((E)d") time, and overall O ([Vldd' + (E)d").
1.2 PARAMETRIC COMPLEXITY
GAT
GATv2 d' 2dd' d' + dd'
DPGAT
Official
2d' + dd'
2dd, + dd'
In our experiments
2d' + dd!
2dd'
Table 19: Number parameters for each GNN type, in single layer and a single attention head.
All parametric costs summarized in Table 19 All following calculations refer to single layer having a single attention head, omitting bias vectors.
GAT has learned vector and matrix: a E 122d and W E gd'xd, xd thus overall 2d' dd' learned parameters.
GATv2 has matrix that is twice larger: W E IRd'xxdd x2d because it is applied on the concatenation [he]] hhy] Thus, the overall number of learned parameters to rule out the increased number of parameters over GAT as the source of empirical difference,
+ 2dd'. However in our experiments,
constrained W [W'] W'), and thus the number of parameters were d' dd'.
DPGAT has and K matrices of sizes ddg each, and additional dd' parameters in the value matrix V. thus 2dd, + dd' parameters overall. However in our experiments, we constrained Q = K and set dę d'. and thus the number of parameters is only 2dd'.
22

---

Published as a conference paper at ICLR 2022
REFERENCES
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to represent programs with graphs. In International Conference on Learning Representations, 2018. URL httpps://opeereeieee. net/
forum? Brrum?dddBJOEETI
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In Interna- tional Conference on Learning Representations, 2021. URL htl..htttps://opeeeeeeeee ntt/ 180OPhOCVH2
James Atwood and Don Towsley. Diffusioon-oonvlutionnll neural networks. In Advances in neural information processing systems, pages 1993-2001, 2016.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine tramslation by jointly learning to align and translate. CoRR, abs/1409.047,, 2014. URL hattatttp//aaaaaa wttp//awwwv...../aaee/ea/oo wwt.://////aaaaaaaaaa/aa 14099, 0473
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and Koray kavukcuoglu. Interaction networks for learning about objects, relations and physics. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 4509-4511 4517,,,5,,40 2016.
Marc Brockschmidt. Gan-film: Graph neural networks with feature-wit linear modulation. Proceedings of 36th International Conference on Machine Learning, ICML, 2020. URL httpp://gittub.cc.
mi www.roofottooo wtw.ooottff-gnn---ttte
es
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond cuclidean data. JEEE Signal Processing Magazine, 34(4) 34(4):18-42, 2017.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković, Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, 2021.
Dan Busbridge. Dane Sherburn, Pietro Cavallo, and Nils Y Hammerla. Relational graph attention networks. arXiv preprint arXiv:1904.00000 1, 2019.
George Cyhenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314 1989.
Misha Denil. Sergio Gómez Colmenarejo, Serkan Cabi, David Saxton, and Nando de Freitas. Programmable agents. arXiv preprint arXiv:/706.0660 2017.
Yan Duan, Marcin Andrychowicz. Bradly Stadie, Jonathan Ho, Jonas Schneider, Ilya Sutskever, Pieter Abbeel, and Wojciech Zaremba. One-shot imitation learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1087-1098, 2017.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafacl Bombarell, Timothy Hirzel, Alán Aspuru- Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances neural information processing systems, pages 2224-2232, 2015.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs, arXiv preprint arXiv:2012.09699 2020.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.0099 2020.
Matthias Fey and Jan F. Lenssen. Fast graph representation learning with Porch Geometrie. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Ken-Ichi Funahashi. On the approximate realization of continuous mappings by neural networks. Neural nenworks, 2(3):183-1))) 192, 1989.
Hongyang Gao and Shuiwang Graph representation learning via hard and channel- wise attention networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 741-749, 2019.
Justin Gilmer, Samuel S Schocnholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, pages 1263-1272. JMLR. JMLR. org, 2017.
Aleksa Gordié, pytorch-gat. httpas///hhhhaa.cco///oococlaaas
2020.
23

---

Published as a conference paper at ICLR 2022
Marco Gori, Gabriele Monfardini, and Franco Searselli. A model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume 2, pages 729- 734. IEEE, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251-257, 1991.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
Yedid Hoshen. Vain: attentional multi-agent predictive modeling. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 2698-200 0098-2708,200 2017.
Weihuaa Hu. Matthias Fey. Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687, 2020.
Binxuan Huang and Kathleen M Carley. Syntax-aware aspect level sentiment classification with graph attention networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (MMNLP-IJCNLP), pages 5480. 2019.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models per-orrs graph neural networks. In International Conference on Learning Representations, 2021. URL httptttttpp:pseeeeeeeeee
net dinrummmmmd------- 33hhXoo
Chaitanya Joshi. Transformers are graph neural networks. The Gradient, 2020.
Dongkwan Kim and Alice Oh. How find your friendly neighborhood: Graph attention design with self-supervision. In International Conference on Learning Representations, 2021. URL httpps:/
openreview net net/forummide 5XUN] 5
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR. 2017.
Vincet Kosaraju, Amir Sadeghian, Roberto Martín-Martin Ian Reid, Hamid Rezatofighi, and Silvio Savarese. Social-bigatt Multimodal trajectory forecasting using bicycle-gan -aneeeeggnnnn and graph attention networks. H. Wallach, H. Larochelle, A. Beygelzimer. F. d Alché- Aich-BBuc, E. Fox, and R. Garnett, editors, Advances in Neural Infor- mation Processing Systems, volume 32. Curran Associates, Inc., 2019. URL ht tps pttpp:sss///pppeiiggge .pd
heurips.cc/papeee http://s.cccpppppp///e///// /ttp//11////9999974//44 333
John Boaz Lee, Ryan A Rossi, Sungchul Kim, Nesreen K Ahmed, and Eunyee Koh. Attention models in graphs:
A survey. arXiv preprint 10XXvv1807.0777 2018.
Moshe Leshno, Vladimir Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a
nonpolynomial activation function can approximate any function. Neurul neiworks, 6(6):861-867, 1993.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In
Proceedings of the IEEF/CVF International Conference on Computer Vision, pages 9267-9276, 2019.
Qimai Li. Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Shirty-Second AAAI Conference on Artificial Intelligence. 2018.
Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016.
Denis Lukovnikov and Asja Fischer. Gated relational graph attention networks, 2021. URL https://
openreview Tweerrevew..eet/Forumng
9E8egy
Thang Luong, Hieu Pham, and Christopher D. Manning. Effective approaches to attention-based neural
machine translation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Longuage Processing, EMNLP 2015, Lishon, Portugal, September 17-21, 2015, pages 1412-1421, 2015. URL https //aclweb. org htwp://.....ggaaaaooooooo///////
Nianzu Ma, Sahisnu Mazumder, Hao Wang, and Bing Liu. Entity-aware dependency- based deep graph attention network for comparative preference classification. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 5782-5788, 2020.
24

---

Published as a conference paper at ICLR 2022
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model enns. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115-5 5124, 2017.
Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. Learning attention-based basond---aeedd embeddings for relation prediction in knowledge graphs. Proceedings of the 57th Annual Meeting of the Association, for Computational Linguistics, pages 47 4710-4723, 2019.
Sejun Park, Chulhee Yun, Jacho Lee, and Jinwoo Shin. Minimum width for universal approximation. In Interna- tional Conference on Learning Representations, 2021. URL htt.hhts:///ppeeeeeeeeeeec htt.:/ewweeeefooteeeeeee
O XJwyo F
Allan Pinkus. Approximation theory of the mlp model. Acta Numerica 1999: Volume 8:143 195, 1999.
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. In Proceedingy of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD' 18), 2018.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo moleculcs. Scientific data, 1:140022, 2014.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self- supervised graph transformer large-scale molecular data. Advances in Neural Information Processing Systems, 33, 2020a.
Yu Rong. Wenbing Huang. Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference Learning Representations, 2020b. URL
htttps://cpenrevier httpiiiwwweeeeeeeeeeeeeeeeeeeeee
Adam Santoro, David Raposo, David GT Barrett, Matcusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. A simple neural network module for relational reasoning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 4974-4983, 2017.
Franco Scarselli, Marco Gori. Ah Chung Tsoi, Markus Hagenbuchner. and Gabriele Monfardini. The graph neural network model. JEEE Transactions on Neural Networks, 20(1):61-80. 2008
Prithviraj Sen, Galileo Namata, Mustafa Bilgie, Lise Getoor, Brian Galligher, and Tina Fliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Yunsheng Shi, Zhengjie Huang, Shikun Feng, and Yu Sun. Masked label prediction: Unified massage passing model for supervisdd classification. arXiv preprint MXXi::0009033009 2020.
Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning, arXiv preprini arXiv: 800. 03735, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pages 6000-6010, 2017.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Petar Veličković, Lars Buesing, Matthew Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell, Pointer graph networks. Advances in Neural Information Processing Systems, 33, 2020.
Petar et al. Veličković. Graph attention networks. 2018.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Improving graph attention networks with large margin-hased constraints. arXiv preprint arXiv: 1910.1 1945, 2019a.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks, arXiv preprint 19X9v:1909.01311 2019b.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yansang Ye. Peng Cui, and Philip S Yu. Heterogemeous graph attention network. In The World Wide Web Conference, pages 2022-2032, 2019c.
Yangkun Wang. Bag of tricks of semi-supervised classification with graph neural networks. arXiv preprint 103.v:2103.13355 2021.
25

---

Published as a conference paper at ICLR 2022
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite precision for language recognition. Proceedings of the 56th Anmual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 740-745, 2018.
Felix Wu, Amauri Souza, Tianyi Zhang. Christopher Fifty, Yu, and Kilian Weinberger. Simplifying graph convolutional networks. International conference on machine learning, pages 6861-6871, PMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen. Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive
survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec. and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019, URL httpps:://ppeeeeeeeww net/ forum?id-ryen 1A5Km
Yiding Yang. Jiayan Qiu, Mingli Song. Dacheng Tao, and Xinchao Wang. Distilling knowledge from graph convolutional networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), June 2020.
Scongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph transformer networks. Advances in Neural Information Processing Systems, 32: 1983 11993, 2019.
Hanqing Zeng, Hongkuan Zhou Ajitesh Srivastava, Rajgopal Kannan. and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv: 197700493,, 2019.
Jiani Zhang, Xingjian Shi, Junyuan Xie. Hao Ma, Irwin King, and Dit- Yan Yeung. Gaan: Gated attention networks for learning large and spatiotemporal graphs. In Proceedings of the Thirty-Fourt Fourth Conference Uncertainty in Artificial Intelligence, pages 339-349, 2018.
Kai Zhang, Yaokang Zhu, Jun Wang, and Jie Zhang. Adaptive structural fingerprints for graph attention networks. In International Conference on Learning Representations, 2020. URL /ttp:///////cccciivww net/
Lingxiao Zhao and Leman Akoglu. Pairorm:: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020. /tth://ppe//ppooorrrreeeee/////r
26


Reviews:
[{"review_id": "xe7RLnR9ji", "reviewer": "Reviewer_MFSQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The explanations and justifications of the proposed methods can be improved. Why is it a problem that, for any query node, the attention function is monotonic with respect to the neighbor (key) scores? As currently presented, the dynamic attention defined in Definition 3.2 seems a convenient choice. Why is it necessary that every key can be selected using a query? Also, if a key is important, why does any query want to ignore this key or decay the key’s score. I am really doubting the method, but just feel the explanations and justifications can be clearer.\n\nThe simple fix captured by Equation 7 was claimed to be able to compute dynamic attention as defined in the paper. Is there a deeper reason for changing the order of local operations? Why LeakyReLU first is better?\n\nSome results show that GATv2 seems to outperform GAT on a set of benchmark datasets, but are mixed in other datasets. In node prediction task in Section 4.4, GATv2 sometimes does better with 1 attention head, and other times better with 8 attention heads. Given it is able to compute dynamic attention, shouldn’t more attention heads be better? In link prediction in Section 4.6, no-attention-based methods outperform attention-based methods. Why is attention not needed in these datasets? Also, why do you think some datasets require dynamic attention? Gaining deeper insights to these questions will be really helpful. \n\n\n", "summary_of_the_paper": "The authors describe a limitation of the GAT, claiming that the ranking of the attention scores is unconditional on the query node. The paper proposes a method named dynamic graph attention by modifying the order of operations. \n", "summary_of_the_review": "The proposed method has potential, but the methods needs better explanations and justifications; and the results seems limited and mixed. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "x4NnmKv9uTb", "reviewer": "Reviewer_QN6d", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The novelty of the proposed model is very simple; the authors just switch the order of two operations (multiplication with attention weights and the activation). However, I recommend accepting this paper since the implications from its theoretical and empirical results can be significant to the graph neural network community.\n\nMany recent papers are designing variants of attention and applying them for various domains, but no paper clearly answers why the attention looks like what they proposed and why it works. We cannot say this paper is totally free from this criticism, but it can be the first step to finding the optimal attention architecture. I believe that future research of designing attentions can leverage the principle and practices in this work.\n\n*Questions:* First, the authors state that DPGAT (in Transformer) is strictly weaker than GATv2. Then, can we get a better version of the Transformer if we replace its attention with GATv2’s? Here, I am not demanding the full experiments on GATv2-Transformer on NLP tasks, just asking what GATv2 authors think about this. Second, what properties of graphs characterize the simplicity of the task (or the necessity of different rankings of each node)? That is, what properties of datasets cause the different performance gap between GATv2 and GAT by datasets (besides an average degree in link prediction)? For example, the proposed DictionaryLookup task seems to be simple but requires using different rankings. GATv2 outperforms GAT on ogbn-arxiv with a small margin (<0.3%p), but on ogbn-proteins with a relatively large margin (nearly 6.0%p on one head). Third, the classical citation benchmarks are considered to be easy-to-overfit, but we know GAT does not outperform baselines on PubMed. How does GATv2 perform on the PubMed dataset with the public split? \n\n*Suggestions:* It would be nice if the authors report the statistical significance test results on the tables. \n", "summary_of_the_paper": "This work proposes GATv2, the improved variant of the graph attention network (GAT). To demonstrate that GATv2 is more expressive than the original GAT, the authors (1) give theoretical justifications with the notion of static/dynamic attention, (2) conduct experiments on the synthetic dataset which GAT cannot learn, but GATv2 can, (3) demonstrate that GATv2 outperforms GAT on various real-world node-, link-, and graph-level prediction benchmarks.\n", "summary_of_the_review": "The proposed GATv2 model is simple but more expressive than the original GAT. The authors’ claim is justified both theoretically and empirically. I would recommend the acceptance since the principles and practices presented by this paper can be useful for future research to design attentional models. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "oLSrJX9v4gZ", "reviewer": "Reviewer_jXKx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. a new type of GAT model, that can have very borader impact.\n\n2. The design is super simple as shown in Eq.(6) and Eq(7).\n\n3. They also show some mathmatical analysis, and the results is good.\n\nWeakness:\n\n1. The theorem is not clear for me, J_max leads to maximal values of its attentions distribution. Why says that the \\alpha compute only static attention?\n\n2. Any example for he continues function \\withhat{g} in Eq.(9)?", "summary_of_the_paper": "In this paper, the author mainly redesign the Graph Attention Network, and they show that the new model can capture the dynamic attention instead of static attention in the original GAT.", "summary_of_the_review": "In summary, I think the algorithm is this paper is simple yet effective, just swap some of operators in the orignal graph attention network. The impacts are broad. The differences of the dynamic attention and static attention can be further discussed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VS91CySe-7E", "reviewer": "Reviewer_BePW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The experiments show some improvement, but the theory has flaws:\n\nThe theory assumes that there is a fixed set of keys shared by all queries,\nbut this assumption cannot fit GAT. \nIn GAT, the softmax normalization is applied to each node's adjacent neighbors,\nwhich means each node will only attend to its adjacent neighbors.\n\nThe example in Figure 1 and Section 4.1 is a **complete** bipartite graph.\nIn this special case, queries have the same set of keys, and the theory works,\nbut the special example is far from the real-world datasets. \nHow do you define static and dynamic attention when different nodes have different key sets?", "summary_of_the_paper": "This paper analyzes the limitation of GAT by pointing out that GAT computes a limited kind of attention: static attention.\nThis paper then introduces a simple fix by modifying the order of operations and proposes GATv2: a dynamic attention variant.\nExperiments show that GATv2 can outperform GAT.", "summary_of_the_review": "The empirical improvement cannot be properly established on static and dynamic attention", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper argues that the widely adopted graph attention networks (GAT) have a shortcoming that with the static nature of the attention mechanism, they may fail to represent certain graphs. This paper presents an alternative, GATv2, a simple variant with the same time complexity as GAT but with more expressivity, able to represent the graphs that GAT fails to. This is shown both empirically and theoretically, with various tasks on synthetic as well as standard benchmark graphs. 

GATs are of high interest to the ICLR community, and this paper makes fundamental progress in how attention works in GNNs. This is one of the few papers that present both empirical and theoretical analyses, and these findings will motivate others in the community to make further advances in this field.
Decision: Accept (Poster)