PaperlayerView exact revision on arXiv

Source-linked AI summary

How Attentive are Graph Attention Networks?

Shaked Brody, Uri Alon, Eran Yahav

arXiv:2105.14491v3cs.LG

TL;DR

The paper asks whether standard GAT actually provides query-dependent attention, formalizes static and dynamic attention, and introduces GATv2 by reordering GAT’s internal operations. GATv2 is strictly more expressive and outperforms GAT across 11 benchmarks with the same parametric cost, although simpler non-attentive models can sometimes perform better.

  • Problem

    Standard GAT is widely used but computes static attention whose neighbor ranking is unconditioned on the query, limiting its ability to represent query-dependent selections.

  • Method

    The paper formally analyzes attention expressiveness and modifies GAT’s operation order to create GATv2, a dynamic graph-attention variant.

  • Results

    GATv2 outperforms GAT in all 11 OGB and other benchmarks while having the same parametric cost.

  • Takeaways & Limitations

    GATv2 is the supported choice when different nodes require different neighbor rankings, whereas GAT may suffice when influential nodes have a global ranking.

  • Takeaways & Limitations

    In some benchmarks, non-attentive models such as GCN or GIN achieve higher accuracy than all evaluated attention-based GNNs.

Abstract

from arXiv · show

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

1 INTRODUCTION

GNNs learn from graph-structured data by updating node representations through neighborhood interactions, and GAT applies attention to weight those neighbors. This paper shows that standard GAT implements only static attention, then introduces GATv2 by changing the operation order.

  • 1 INTRODUCTION: GNNs provide a general framework for learning from graph-structured data whose predictions depend on relationships between nodes.Applications include molecules, social networks, product recommendation, and computer programs.
  • 1 INTRODUCTION: GAT updates each node by attending to its neighbors while using the node’s own representation as the query.This attention-based aggregation generalizes standard averaging or max-pooling.
  • 1 INTRODUCTION: Standard GAT computes static attention: attention-coefficient rankings are shared across graph nodes and unconditioned on the query node.The paper identifies this restriction as limiting GAT’s expressiveness.
  • 1 INTRODUCTION: GATv2 addresses the limitation by modifying the order of internal operations in GAT.The resulting variant has a universal-approximator attention function and is strictly more expressive than GAT.
  • 1 INTRODUCTION: GATv2 outperforms GAT across 12 benchmarks, including gains of over 1.4% on VarMisuse and 11.5% over extensively tuned GAT on QM9 objectives.The cited results cover node-, link-, and graph-prediction tasks.

2 PRELIMINARIES

GNN layers update node representations by applying a shared function to each node and its neighbors. GAT specializes this aggregation with learned, softmax-normalized attention weights.

  • 2 PRELIMINARIES: A GNN layer aggregates neighbor representations to produce updated representations for every node.The same parametric function is applied to each node given its neighborhood.
  • 2 PRELIMINARIES: The design of the update function and aggregation operation distinguishes different GNN architectures.GraphSAGE, for example, can use element-wise mean aggregation followed by concatenation, a linear layer, and ReLU.
  • 2 PRELIMINARIES: GAT replaces equal neighbor weighting with a learned weighted average of neighbor representations.Its scoring function assigns an importance score to each edge’s neighboring node.
  • 2 PRELIMINARIES: GAT normalizes neighbor scores with softmax to obtain attention coefficients.The coefficients are then used to aggregate transformed neighbor features.
  • 2 PRELIMINARIES: The paper refers to the defining GAT operations as Equations (2) through (4).

3 THE EXPRESSIVE POWER OF GRAPH ATTENTION MECHANISMS

The paper distinguishes static from dynamic attention and proves that standard GAT is restricted to the former. Reordering GAT’s internal operations yields GATv2, which can compute dynamic attention with the same declared time complexity.

  • 3.1 THE IMPORTANCE OF DYNAMIC WEIGHTING: Static attention always gives at least one key the highest score regardless of the query, preventing query-dependent relevance rankings.Such attention cannot model situations where different queries require different keys.
  • 3.1 THE IMPORTANCE OF DYNAMIC WEIGHTING: Dynamic attention can select any key for each query through an appropriate scoring function.The definition permits arbitrary query-to-key mappings, followed by monotonic normalization such as softmax.
  • 3.2 THE LIMITED EXPRESSIVITY OF GAT: Theorem 1 proves that a GAT layer computes only static attention for any node representations when keys and queries are the same set.For n > 1, it therefore does not compute dynamic attention.
  • 3.2 THE LIMITED EXPRESSIVITY OF GAT: In GAT, the query changes attention sharpness but not the global ranking induced by per-node scores.Each attention head separately has a node that maximizes its score.
  • 3.3 BUILDING DYNAMIC GRAPH ATTENTION NETWORKS: GATv2 changes the operation order so its scoring function applies a nonlinearity before the final attention layer.This prevents the consecutive learned layers from collapsing into a single linear layer and effectively applies an MLP to each query-key pair.
  • 3.3 BUILDING DYNAMIC GRAPH ATTENTION NETWORKS: Theorem 2 states that a GATv2 layer computes dynamic attention for any set of node representations.The paper connects this result to GATv2’s universal-approximator attention function.
  • 3.3 BUILDING DYNAMIC GRAPH ATTENTION NETWORKS: GATv2 has the same declared time complexity as GAT: O(|V|dd′ + |E|d′).The paper notes that GAT can nevertheless be computed faster than this declared complexity by merging its linear layers.

4 EVALUATION

Across synthetic, noisy, program, node-, graph-, and link-prediction evaluations, GATv2 consistently outperforms GAT and is more robust to structural noise. The results also show that GAT can fail on dynamic-attention problems, while non-attentive models sometimes remain strongest on simpler tasks.

  • 4.1 SYNTHETIC BENCHMARK: DICTIONARYLOOKUP: GAT fails to fit DICTIONARYLOOKUP with one head, while GATv2 reaches 100% train and test accuracy for any k, including k=100 with one head.GAT with eight heads fits training data but generalizes poorly; increasing heads increases GAT expressivity, whereas a single GATv2 head generalizes better.
  • 4.1 SYNTHETIC BENCHMARK: DICTIONARYLOOKUP: GAT assigns the same attention ranking to all query nodes, whereas GATv2 can select a different key for each query through dynamic attention.This visualization directly contrasts the static ranking in GAT with query-dependent selection in GATv2.
  • 4.2 ROBUSTNESS TO NOISE: As structural noise increases, GATv2’s test accuracy degrades more mildly than GAT’s.The authors hypothesize that dynamic attention helps distinguish data edges from noise edges, unlike GAT’s separate source and target scoring.
  • 4.3 PROGRAMS: VARMISUSE: GATv2 is more accurate than all GNNs on both VARMISUSE test sets using GAT’s hyperparameters, with a higher improvement on UnseenProj.It outperforms extensively tuned models without additional tuning by the authors.
  • 4.4 NODE-PREDICTION: On node-prediction datasets, GATv2 outperforms GAT and non-attentive GNNs in all settings, often with one head outperforming GAT with eight.On ogbn-proteins, GAT improves from 70.77 to 78.63 when increasing heads, while GATv2 obtains most benefits with one head.
  • 4.5 GRAPH-PREDICTION: QM9: On QM9, GATv2 reduces GAT’s average error by 11.5% relatively, although GCN or GIN performs best for some properties.GATv2 generally achieves the lowest overall average relative error, while attention may not be needed for every property.
  • 4.6 LINK-PREDICTION: On OGB link-prediction datasets, GATv2 has higher MRR than GAT, but non-attentive GraphSAGE performs better than all attentive GNNs.The authors suggest attention may be unnecessary on these lower-degree datasets.
  • Overall evaluation: Across all examined benchmarks, GATv2 is more accurate than GAT and significantly more robust to noise.In the synthetic DICTIONARYLOOKUP benchmark, GAT fails to express the data and achieves poor training accuracy.

5 RELATED WORK

The paper situates GAT within attention-based graph learning and distinguishes its analysis from prior work on graph attention mechanisms. It identifies GAT’s monotonicity as a previously unrecognized theoretical limitation with practical consequences.

  • GAT became the most popular framework for attentional GNNs because of its simplicity, generality, and applicability beyond reinforcement learning.
  • Prior work explored alternative graph attention mechanisms and surveyed attention types, but did not identify GAT’s monotonic attention mechanism.
  • Qiu et al. recognized GAT’s order-preserving property but did not identify that it prevents dynamic attention or causes practical harmful consequences.

6 CONCLUSION

The paper shows that standard GAT computes only static attention and therefore cannot express some simple alignment problems. GATv2 fixes this limitation and outperforms GAT across examined benchmarks at the same parametric cost.

  • Standard GAT uses static attention, whose neighbor ranking is monotonic with respect to per-node scores for every query.
  • GATv2 modifies GAT’s operation order to obtain a universal approximator attention function that is strictly more powerful than GAT.
  • GATv2 outperforms GAT in a synthetic dynamic-selection problem and across 11 OGB and other public benchmarks while matching GAT’s parametric cost.
  • The authors make code publicly available and provide GATv2 through PyTorch Geometric and the Deep Graph Library.

A PROOF FOR THEOREM 2

The proof defines dynamic attention through arbitrary query-dependent key selection and establishes that GATv2 can realize this behavior for node representations used as both keys and queries.

  • Dynamic attention requires a scoring-function family to realize any mapping from queries to selected keys.
  • Theorem 2 states that a GATv2 layer computes dynamic attention for any set of node representations used as both keys and queries.
  • The proof constructs a function on concatenated query-key vectors and uses universal approximation to match the required mapping at finitely many inputs.
  • For sufficiently small ϵ, parameters can separate the selected key’s score from every unselected key’s score, and monotonic softmax preserves that ordering.
  • The result holds for common nonpolynomial activations, including ReLU, sigmoid, hyperbolic tangent, and LeakyReLU.
  • The experiments use public OGB splits, tuned optimization and architecture settings, multiple attention heads in selected node-prediction datasets, and averages over 10 runs.

B.3 SYNTHETIC BENCHMARK: DICTIONARYLOOKUP

The synthetic DICTIONARYLOOKUP benchmark evaluates training and generalization under controlled graph sizes and fixed optimization settings. Its protocol uses encoded key attributes and values while testing models trained separately for each size.

  • All experiments use learning-rate decay of 0.5, hidden size d = 128, batch size 1024, and Adam optimization.
  • Each graph-size dataset is split 80:20 into train and test, with every model trained on a fixed k and no validation set.
  • Key nodes are encoded by summing learned attribute and value embeddings followed by ReLU.
  • Normalization, dropout, activation functions, and learning-rate variations did not change the general trend, so the reported experiments omit normalization and dropout.
  • For comparisons, the study uses previously tuned configurations, trains each model five times, and applies GAT’s best-found hyperparameters to GATv2 without additional tuning.
  • The experiments consumed approximately 100 days of GPU time across V100, RTX 3080, and RTX 3090 hardware.

C.1 NODE- AND LINK-PREDICTION DATASETS

The paper reports dataset statistics for the OGB, QM9, and VARMISUSE benchmarks used in node prediction, link prediction, and related experiments.

  • Dataset statistics are provided for the OGB benchmarks used in node- and link-prediction experiments.
  • The QM9 chemical dataset statistics are reported for the experimental setup used by Brockschmidt (2020).
  • The VARMISUSE dataset statistics are reported for the setup used by Allamanis et al. (2018) and Brockschmidt (2020).
  • In DICTIONARYLOOKUP, k denotes the number of different keys in each graph.

D.1 DICTIONARYLOOKUP

The DICTIONARYLOOKUP comparison shows that GATv2 fits and generalizes on substantially larger key sets, whereas GIN fails to perfectly fit training data earlier.

  • 100% train and test accuracy is achieved by GATv2 at k=100 with a single attention head.
  • GIN cannot perfectly fit the DICTIONARYLOOKUP training data from k=20 onward with model size d = 128.
  • QM9 results include average error rates with standard deviations reported across five runs for each property.
  • PubMed accuracy is reported over 100 runs, and GATv2 is more accurate than GAT.

E.2 DPGAT IS STRICTLY WEAKER THAN GATV2

DPGAT can perform dynamic attention under linear independence, but dependent representations create cases it cannot handle; empirically, GATv2 is more robust to structural noise than GAT.

  • For some linearly dependent representations, DPGAT cannot select a particular key for any query, making it strictly weaker than GATv2.
  • GATv2 and DPGAT are more robust to structural noise than GAT, with each plotted point averaging 10 runs.
  • GATv2 is more accurate than all GNNs in both VARMISUSE test sets when using GAT’s hyperparameters.

G COMPLEXITY ANALYSIS

GATv2 retains GAT’s stated computational complexity while changing the scoring computation, and experiments constrain its parameters to match GAT’s effective parameter cost.

  • GATv2 has time complexity O(|V|dd′ + |E|d′), matching GAT’s declared complexity.
  • GATv2 computes node projections first and then evaluates the query-key score for each edge using their sum before the nonlinearity.
  • Under the experimental constraint W = [W′∥W′], GATv2 uses d′ + dd′ learned parameters, compared with GAT’s 2d′ + dd′.
  • DPGAT uses 2dd′ parameters in the experiments after constraining Q = K and setting dk = d′.
Loading 2105.14491v3…